В продолжении темы о Data Mining поговорим о том, с чего все начиналось. А начиналось все с анализа рыночной корзины (market basket analysis).
Анализ рыночной корзины - процесс поиска наиболее типичных шаблонов покупок в супермаркетах. Он производится путем анализа баз данных транзакций с целью определения комбинаций товаров, связанных между собой. Иными словами, выполняется обнаружение товаров, наличие которых в транзакции влияет на вероятность появления других товаров или их комбинаций.
Результаты, полученные с помощью анализа рыночной корзины, позволяют оптимизировать ассортимент товаров и запасы, размещение их в торговых залах, увеличивать объемы продаж за счет предложения клиентам сопутствующих товаров. Например, если в результате анализа будет установлено, что совместная покупка макарон и кетчупа является типичным шаблоном, то разместив эти товары на одной и той же витрине можно «спровоцировать» покупателя на их совместное приобретение.
Ассоциативные правила
Для решения задачи анализа рыночной корзины используются ассоциативные правила вида «если… то...». Например, «если клиент купил пиво, то он купит и чипсы». Каждая покупка именуется «транзакцией», на основании большего набора таких транзакций и строят исследования поведения клиента.Ассоциативные правила являются очень простой и удобной формой записи знаний . Еще раз хочу уточнить, что информация о транзакциях является исходными данными, а вот полученные ассоциативные правила являются теми знаниями, которые помогли в 80-х большим супермаркетам сэкономить большие деньги.
Для характеристики правила используются некоторые метрики:
Правило X->Y имеет поддержку s (support), если s транзакций из D, содержат пересечение множеств X и Y. Достоверность правила показывает какова вероятность того, что из X следует Y. Правило X->Y справедливо с достоверностью c (confidence), если c транзакций из D, содержащих X, также содержат Y, conf(X-> Y) = supp(X->Y)/supp(X).
Например: «75% транзакций, содержащих хлеб, также содержат молоко. 3% от общего числа всех транзакций содержат оба товара». 75% – это достоверность (confidence) правила, 3% - это поддержка (support), или «Хлеб» -> «Молоко» с вероятностью 75% и поддержкой 3%.
Как правило, очевидные правила имеют поддержку и достоверность высокую (60% и больше), но не являются знаниями де-факто. Основное внимание необходимо уделять правилам, имеющим поддержку 5-10%, именно они могут стать источником идеи промоакции или услуги.
Алгоритм Apriori
Основным алгоритмом, который применяется для получения ассоциативных правил, является алгоритм apriori. Его автором является Ракеш Агравал (Rakesh Agrawal , сейчас сотрудник Microsoft Research).Алгоритм Apriori предназначен для поиска всех частых множеств признаков. Он является поуровневым, использует стратегию поиска в ширину и осуществляет его снизу-вверх.
Алгоритм перебора следующий ():
Основная особенность алгоритма - свойство антимонотонности ():
Apriori использует одно из свойств поддержки, гласящее: поддержка любого набора элементов не может превышать минимальной поддержки любого из его подмножеств. Например, поддержка 3-элементного набора {Хлеб, Масло, Молоко} будет всегда меньше или равна поддержке 2-элементных наборов {Хлеб, Масло}, {Хлеб, Молоко}, {Масло, Молоко}. Дело в том, что любая транзакция, содержащая {Хлеб, Масло, Молоко}, также должна содержать {Хлеб, Масло}, {Хлеб, Молоко}, {Масло, Молоко}, причем обратное не верно.
Благодаря этому свойству перебор не является «жадным» и позволяет обрабатывать большие массивы информации за секунды.
Классический алгоритм apriori уже был несколько раз модифицирован, работы по улучшению скорости ведутся и сейчас.
Кроме apriori используются и другие алгоритмы:
- Eclat algorithm
- FP-Growth algorithm
- One-attribute-rule
- Zero-attribute-rule
Решение других задач
Классическая задача анализа рыночной корзины трансформировалась в новые задачи, которые нужно решать в наше время, а именно:- анализ покупок с помощью кредитных карточек
- анализ шаблонов телефонных звонков (telephone calling patterns)
- и др., связанных с анализом и выявлением мошеннических операций в какой-то области
Современные базы данных имеют очень большие размеры, достигающие гига- и терабайтов, и тенденцию к дальнейшему увеличению. И поэтому, для нахождения ассоциативных правил требуются эффективные масштабируемые алгоритмы, позволяющие решить задачу за приемлемое время. Об одном из таких алгоритмов и пойдет речь в данной статье. Мы опишем алгоритм Apriori. Терминология и обозначения, которыми мы будем пользоваться, даны в статье "Введение в анализ ассоциативных правил" .
Для того, чтобы было возможно применить алгоритм, необходимо провести предобработку данных: во-первых, привести все данные к бинарному виду; во-вторых, изменить структуру данных.
Таблица 1. Обычный вид базы данных транзакций:
Таблица 2. Нормализованный вид:
| TID | A | B | C | D | E | F | G | H | I | K | ... |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 1001 | |||||||||||
| 1002 | 1 | ||||||||||
| 1003 |
Количество столбцов в таблице равно количеству элементов, присутствующих в множестве транзакций D. Каждая запись соответствует транзакции, где в соответствующем столбце стоит 1, если элемент присутствует в транзакции, и 0 в противном случае. (см. Определение 1). Заметим, что исходный вид таблицы может быть отличным от приведенного в таблице 1. Главное, чтобы данные были преобразованы к нормализованному виду, иначе алгоритм не применим.
Более того, как видно из таблицы, все элементы упорядочены в алфавитном порядке (если это числа, они должны быть упорядочены в числовом порядке). Как вы, наверное, уже догадались, это сделано неслучайно. Но, не будем забегать вперед, всему свое время.
Итак, данные преобразованы, теперь можно приступить к описанию самого алгоритма. Как было сказано в предыдущей статье, такие алгоритмы работают в два этапа, не является исключением и рассматриваемый нами алгоритм Apriori. На первом шаге необходимо найти часто встречающиеся наборы элементов, а затем, на втором, извлечь из них правила. Количество элементов в наборе будем называть размером набора, а набор, состоящий из k элементов, – k-элементным набором.
Свойство анти-монотонности
Выявление часто встречающихся наборов элементов – операция, требующая много вычислительных ресурсов и, соответственно, времени. Примитивный подход к решению данной задачи – простой перебор всех возможных наборов элементов. Это потребует O(2 |I|) операций, где |I| – количество элементов. Apriori использует одно из свойств поддержки, гласящее: поддержка любого набора элементов не может превышать минимальной поддержки любого из его подмножеств. Например, поддержка 3-элементного набора {Хлеб, Масло, Молоко} будет всегда меньше или равна поддержке 2-элементных наборов {Хлеб, Масло}, {Хлеб, Молоко}, {Масло, Молоко}. Дело в том, что любая транзакция, содержащая {Хлеб, Масло, Молоко}, также должна содержать {Хлеб, Масло}, {Хлеб, Молоко}, {Масло, Молоко}, причем обратное не верно.
Это свойство носит название анти-монотонности и служит для снижения размерности пространства поиска. Не имей мы в наличии такого свойства, нахождение многоэлементных наборов было бы практически невыполнимой задачей в связи с экспоненциальным ростом вычислений.
Свойству анти-монотонности можно дать и другую формулировку: с ростом размера набора элементов поддержка уменьшается, либо остается такой же. Из всего вышесказанного следует, что любой k-элементный набор будет часто встречающимся тогда и только тогда, когда все его (k-1)-элементные подмножества будут часто встречающимися.
Все возможные наборы элементов из I можно представить в виде решетки, начинающейся с пустого множества, затем на 1 уровне 1-элементные наборы, на 2-м – 2-элементные и т.д. На k уровне представлены k-элементные наборы, связанные со всеми своими (k-1)-элементными подмножествами.
Рассмотрим рисунок 1, иллюстрирующий набор элементов I – {A, B, C, D}. Предположим, что набор из элементов {A, B} имеет поддержку ниже заданного порога и, соответственно, не является часто встречающимся. Тогда, согласно свойству анти-монотонности, все его супермножества также не являются часто встречающимися и отбрасываются. Вся эта ветвь, начиная с {A, B}, выделена фоном. Использование этой эвристики позволяет существенно сократить пространство поиска.
Алгоритм Apriori
На первом шаге алгоритма подсчитываются 1-элементные часто встречающиеся наборы. Для этого необходимо пройтись по всему набору данных и подсчитать для них поддержку, т.е. сколько раз встречается в базе.
Следующие шаги будут состоять из двух частей: генерации потенциально часто встречающихся наборов элементов (их называют кандидатами) и подсчета поддержки для кандидатов.
Описанный выше алгоритм можно записать в виде следующего псевдо-кода:
- F 1 = {часто встречающиеся 1-элементные наборы}
- для (k=2; F k-1 <> $\oslash$; k++) {
- C k = Apriorigen(Fk-1) // генерация кандидатов
- для всех транзакций t $\epsilon$ T {
- C t = subset(C k , t) // удаление избыточных правил
- для всех кандидатов c $\epsilon$ C t
- c.count ++
- F k = { c $\epsilon$ Ck | c.count >= minsupport} // отбор кандидатов
- Результат $\cup$ F k
Опишем функцию генерации кандидатов. На это раз нет никакой необходимости вновь обращаться к базе данных. Для того, чтобы получить k-элементные наборы, воспользуемся (k-1)-элементными наборами, которые были определены на предыдущем шаге и являются часто встречающимися.
Вспомним, что наш исходный набор хранится в упорядоченном виде. Генерация кандидатов также будет состоять из двух шагов.
- Объединение. Каждый кандидат C k будет формироваться путем расширения часто встречающегося набора размера (k-1) добавлением элемента из другого (k-1)- элементного набора.
Приведем алгоритм этой функции Apriorigen в виде небольшого SQL-подобного запроса.
insert into C k
select p.item 1 , p.item 2 , …, p.item k-1 , q.item k-1
From F k-1 p, F k-1 q
where p.item 1 = q.item 1 , p.item 2 = q.item 2 , … , p.item k-2 = q.item k-2 , p.item k-1 < q.item k-1 - Удаление избыточных правил. На основании свойства анти-монотонности, следует удалить все наборы c $\epsilon$ C k если хотя бы одно из его (k-1) подмножеств не является часто встречающимся.
После генерации кандидатов следующей задачей является подсчет поддержки для каждого кандидата. Очевидно, что количество кандидатов может быть очень большим и нужен эффективный способ подсчета. Самый тривиальный способ – сравнить каждую транзакцию с каждым кандидатом. Но это далеко не лучшее решение. Гораздо быстрее и эффективнее использовать подход, основанный на хранении кандидатов в хэш-дереве. Внутренние узлы дерева содержат хэш-таблицы с указателями на потомков, а листья – на кандидатов. Это дерево нам пригодится для быстрого подсчета поддержки для кандидатов.
Хэш-дерево строится каждый раз, когда формируются кандидаты. Первоначально дерево состоит только из корня, который является листом, и не содержит никаких кандидатов-наборов. Каждый раз когда формируется новый кандидат, он заносится в корень дерева и так до тех пор, пока количество кандидатов в корне-листе не превысит некоего порога. Как только количество кандидатов становится больше порога, корень преобразуется в хэш-таблицу, т.е. становится внутренним узлом, и для него создаются потомки-листья. И все примеры распределяются по узлам-потомкам согласно хэш-значениям элементов, входящих в набор, и т.д. Каждый новый кандидат хэшируется на внутренних узлах, пока он не достигнет первого узла-листа, где он и будет храниться, пока количество наборов опять же не превысит порога.
Хэш-дерево с кандидатами-наборами построено, теперь, используя хэш-дерево, легко подсчитать поддержку для каждого кандидата. Для этого нужно "пропустить" каждую транзакцию через дерево и увеличить счетчики для тех кандидатов, чьи элементы также содержатся и в транзакции, т.е. C k $\cap$ T i = C k . На корневом уровне хэш-функция применяется к каждому элементу из транзакции. Далее, на втором уровне, хэш-функция применяется ко вторым элементам и т.д. На k-уровне хэшируется k-элемент. И так до тех пор, пока не достигнем листа. Если кандидат, хранящийся в листе, является подмножеством рассматриваемой транзакции, тогда увеличиваем счетчик поддержки этого кандидата на единицу.
После того, как каждая транзакция из исходного набора данных "пропущена" через дерево, можно проверить удовлетворяют ли значения поддержки кандидатов минимальному порогу. Кандидаты, для которых это условие выполняется, переносятся в разряд часто встречающихся. Кроме того, следует запомнить и поддержку набора, она нам пригодится при извлечении правил. Эти же действия применяются для нахождения (k+1)-элементных наборов и т.д.
После того как найдены все часто встречающиеся наборы элементов, можно приступить непосредственно к генерации правил.
Извлечение правил – менее трудоемкая задача. Во-первых, для подсчета достоверности правила достаточно знать поддержку самого набора и множества, лежащего в условии правила. Например, имеется часто встречающийся набор {A, B, C} и требуется подсчитать достоверность для правила AB $\Rightarrow$ C. Поддержка самого набора нам известна, но и его множество {A, B}, лежащее в условии правила, также является часто встречающимся в силу свойства анти-монотонности, и значит его поддержка нам известна. Тогда мы легко сможем подсчитать достоверность. Это избавляет нас от нежелательного просмотра базы транзакций, который потребовался в том случае если бы это поддержка была неизвестна.
Чтобы извлечь правило из часто встречающегося набора F, следует найти все его непустые подмножества. И для каждого подмножества s мы сможем сформулировать правило s $\Rightarrow$ (F – s), если достоверность правила conf(s $\Rightarrow$ (F – s)) = supp(F)/supp(s) не меньше порога minconf.
Заметим, что числитель остается постоянным. Тогда достоверность имеет минимальное значение, если знаменатель имеет максимальное значение, а это происходит в том случае, когда в условии правила имеется набор, состоящий из одного элемента. Все супермножества данного множества имеют меньшую или равную поддержку и, соответственно, большее значение достоверности. Это свойство может быть использовано при извлечении правил. Если мы начнем извлекать правила, рассматривая сначала только один элемент в условии правила, и это правило имеет необходимую поддержку, тогда все правила, где в условии стоят супермножества этого элемента, также имеют значение достоверности выше заданного порога. Например, если правило A $\Rightarrow$ BCDE удовлетворяет минимальному порогу достоверности minconf, тогда AB $\Rightarrow$ CDE также удовлетворяет. Для того, чтобы извлечь все правила используется рекурсивная процедура. Важное замечание: любое правило, составленное из часто встречающегося набора, должно содержать все элементы набора. Например, если набор состоит из элементов {A, B, C}, то правило A $\Rightarrow$ B не должно рассматриваться.
Литература
- R. Agrawal, T. Imielinski, A. Swami. 1993. Mining Associations between Sets of Items in Massive Databases. In Proc. of the 1993 ACM-SIGMOD Int’l Conf. on Management of Data, 207-216.
- R. Agrawal, R. Srikant. "Fast Discovery of Association Rules", In Proc. of the 20th International Conference on VLDB, Santiago, Chile, September 1994.
Выявление частых наборов объектов - операция, требующая большого количества вычислений, а следовательно, и времени. Алгоритм Apriori описан в 1994 г. Срикантом Рамакришнан (Ramakrishnan Srikant) и Ракешом Агравалом (Rakesh Agrawal). Он использует одно из свойств поддержки, гласящее: поддержка любого набора объектов не может превышать минимальной поддержки любого из его подмножеств:
Например, поддержка 3-объектного набора {пиво, вода, чипсы} будет всегда Меньше или равна поддержке 2-объектных наборов {пиво, вода}, {вода, чипсы}, {пиво, чипсы}. Это объясняется тем, что любая транзакция, содержащая {пиво, вода, чипсы}, содержит также и наборы {пиво, вода}, {вода, чипсы}, {пиво, чипсы}, причем обратное неверно.
Алгоритм Apriori определяет часто встречающиеся наборы за несколько этапов. На i -м этапе определяются все часто встречающиеся i -элементные наборы. Каждый этап состоит из двух шагов: формирования кандидатов (candidate generation) и подсчета поддержки кандидатов (candidate counting).
Рассмотрим i -й этап. На шаге формирования кандидатов алгоритм создает множество кандидатов из i -элементных наборов, чья поддержка пока не вычисляется. На шаге подсчета кандидатов алгоритм сканирует множество транзакций, вычисляя поддержку наборов-кандидатов. После сканирования отбрасываются кандидаты, поддержка которых меньше определенного пользователем минимума, и сохраняются только часто встречающиеся i -элементные наборы. Во время 1-го этапа выбранное множество наборов-кандидатов содержит все i -элементные частые наборы. Алгоритм вычисляет их поддержку во время шага подсчета кандидатов.
Описанный алгоритм можно записать в виде следующего псевдокода:
Опишем обозначения,
используемые в алгоритме:
Опишем данный
алгоритм по шагам.
Шаг 1. Присвоить к= 1 и выполнить отбор всех 1-элементных наборов, у которых поддержка больше минимально заданной пользователем Supp min .
Шаг2.к = к+ 1.
Шаг 3. Если не удается создавать k-элементные наборы, то завершить алгоритм, иначе выполнить следующий шаг.
Шаг
6.
Для каждого кандидата из множества С
к
увеличить
значение поддержки на единицу.
Шаг 7. Выбрать только кандидатов L k из множества С к , у которых значение поддержки больше заданной пользователем Supp min Вернуться к шагу 2.
Результатом работы алгоритма является объединение всех множеств L k для всех к.
Рассмотрим работу алгоритма на примере, приведенном в табл. 6.1, при - Supp min = 0,5. На первом шаге имеем следующее множество кандидатов С 1 (указываются идентификаторы товаров) (табл. 6.5).
Таблица 5.5
Таблица 5.6.
Из построенных кандидатов заданной минимальной поддержке удовлетворяют только кандидаты 2, 4, 5 и 6, следовательно:
На третьем шаге перейдем к созданию 3-элементных кандидатов и подсчету их поддержки. В результате получим следующее множество С 3 (табл. 6.7).
Таблица 5.7
Данный набор удовлетворяет минимальной поддержке, следовательно:
L 3 = {{2,3,5}}.
Так как 4-элементные наборы создать не удастся, то результатом работы алгоритма является множество:
Для подсчета поддержки кандидатов нужно сравнить каждую транзакцию с каждым кандидатом. Очевидно, что количество кандидатов может быть очень большим и нужен эффективный способ подсчета. Гораздо быстрее и эффективнее использовать подход, основанный на хранении кандидатов в хэш-дереве. Внутренние узлы дерева содержат хэш-таблицы с указателями на у потомков, а листья - на кандидатов. Это дерево используется при быстром.подсчете поддержки для кандидатов.
Хэш-дерево строится каждый раз, когда формируются кандидаты. Первоначально дерево состоит только из корня, который является листом, и не содержит никаких кандидатов-наборов. Каждый раз, когда формируется новый кандидат, он заносится в корень дерева, и так до тех пор, пока количество i кандидатов в корне-листе не превысит некоего порога. Как только это происходит, корень преобразуется в хэш-таблицу, т. е. становится внутренним узлом, и для него создаются потомки-листья. Все кандидаты распределяются по «узлам-потомкам согласно хэш-значениям элементов, входящих в набор. Каждый новый кандидат хэшируется на внутренних узлах, пока не достигнет первого узла-листа, где он и будет храниться, пока количество наборов опять же не превысит порога.
После того как хэш-дерево с кандидатами-наборами построено, легко подсчитать поддержку для каждого кандидата. Для этого нужно "пропустить" каждую транзакцию через дерево и увеличить счетчики для тех кандидатов; чьи элементы также содержатся и в транзакции, C k n T , = С к . На корневом уровне хэш-функция применяется к каждому объекту из транзакции. Далее, на втором уровне, хэш-функция применяется ко вторым объектам и т. д. На к-м уровне хэшируется k-элемент, и так до тех пор, пока не достигнем листа. Если кандидат, хранящийся в листе, является подмножеством рассматриваемой транзакции, увеличиваем счетчик поддержки этого кандидата на единицу. После того, как каждая транзакция из исходного набора данных "пропущена" через дерево, можно проверить, удовлетворяют ли значения поддержки кандидатов минимальному порогу. Кандидаты, для которых это условие выполняется, переносятся в разряд часто встречающихся. Кроме того, следует запомнить и поддержку набора, которая пригодится при извлечении правил.
Эти же действия применяются для нахождения (к + 1)-элементных наборов и т. д.
and Swami) был разработан сотрудниками исследовательского центра IBM Almaden в 1993 году. С этой работы начался интерес к ассоциативным правилам ; на середину 90-х годов прошлого века пришелся пик исследовательских работ в этой области, и с тех пор каждый год появляется несколько новых алгоритмов.В алгоритме AIS кандидаты множества наборов генерируются и подсчитываются "на лету", во время сканирования базы данных .
Алгоритм SETM . Создание этого алгоритма было мотивировано желанием использовать язык SQL для вычисления часто встречающихся наборов товаров. Как и алгоритм AIS , SETM также формирует кандидатов "на лету", основываясь на преобразованиях базы данных . Чтобы использовать стандартную операцию объединения языка SQL для формирования кандидата, SETM отделяет формирование кандидата от их подсчета.
Неудобство алгоритмов AIS и SETM - излишнее генерирование и подсчет слишком многих кандидатов, которые в результате не оказываются часто встречающимися. Для улучшения их работы был предложен алгоритм Apriori .
Работа данного алгоритма состоит из нескольких этапов, каждый из этапов состоит из следующих шагов:
- формирование кандидатов;
- подсчет кандидатов.
Формирование кандидатов (candidate generation ) - этап, на котором алгоритм , сканируя базу данных, создает множество i-элементных кандидатов (i - номер этапа). На этом этапе поддержка кандидатов не рассчитывается.
Подсчет кандидатов (candidate counting) - этап, на котором вычисляется поддержка каждого i-элементного кандидата. Здесь же осуществляется отсечение кандидатов, поддержка которых меньше минимума, установленного пользователем (min_sup). Оставшиеся i-элементные наборы называем часто встречающимися.
Рассмотрим работу алгоритма Apriori на примере базы данных D. Иллюстрация работы алгоритма приведена на рис. 15.1 . Минимальный уровень поддержки равен 3.
Рис.
15.1.
На первом этапе происходит формирование одноэлементных кандидатов. Далее алгоритм подсчитывает поддержку одноэлементных наборов. Наборы с уровнем поддержки меньше установленного, то есть 3, отсекаются. В нашем примере это наборы e и f, которые имеют поддержку , равную 1. Оставшиеся наборы товаров считаются часто встречающимися одноэлементными наборами товаров: это наборы a, b, c, d.
Далее происходит формирование двухэлементных кандидатов, подсчет их поддержки и отсечение наборов с уровнем поддержки , меньшим 3. Оставшиеся двухэлементные наборы товаров, считающиеся часто встречающимися двухэлементными наборами ab, ac, bd, принимают участие в дальнейшей работе алгоритма.
Если смотреть на работу алгоритма прямолинейно, на последнем этапе алгоритм формирует трехэлементные наборы товаров: abc, abd, bcd , acd , подсчитывает их поддержку и отсекает наборы с уровнем поддержки , меньшим 3. Набор товаров abc может быть назван часто встречающимся.
Однако алгоритм Apriori уменьшает количество кандидатов, отсекая - априори - тех, которые заведомо не могут стать часто встречающимися, на основе информации об отсеченных кандидатах на предыдущих этапах работы алгоритма.
Ассоциативные правила позволяют находить закономерности между связанными событиями. Примером такого правила служит утверждение, что покупатель, приобретающий «Хлеб», приобретет и «Молоко». Впервые эта задача была предложена для поиска ассоциативных правил для нахождения типичных шаблонов покупок, совершаемых в супермаркетах, поэтому иногда ее еще называют анализом рыночной корзины (market basket analysis ).
Пусть имеется база данных, состоящая из покупательских транзакций. Каждая транзакция – это набор товаров, купленных покупателем за один визит. Такую транзакцию еще называют рыночной корзиной. Целью анализа является установление следующих зависимостей: если в транзакции встретился некоторый набор элементов X , то на основании этого можно сделать вывод о том, что другой набор элементов Y также должен появиться в этой транзакции. Установление таких зависимостей дает нам возможность находить очень простые и интуитивно понятные правила.
Ассоциативное правило состоит из двух наборов предметов, называемых условие (англ: antecedent ) и следствие (англ: consequent ), записываемых в виде X → Y , что читается «из X следует Y ». Таким образом, ассоциативное правило формулируется в виде «Если условие, то следствие».
При поиске ассоциативных правил используют показатели, позволяющие оценить значимость правила. В этой связи можно выделить объективные и субъективные меры значимости правил. Объективными являются такие меры, как поддержка и достоверность , которые могут применяться независимо от конкретного приложения. Субъективные меры связаны со специальной информацией, определяемой пользователем в контексте решаемой задачи. Такими субъективными мерами являются лифт и левередж .
Ассоциативные правила описывают связь между наборами предметов, соответствующим условию и следствию. Эта связь характеризуется двумя показателями – поддержкой (s) и достоверностью (с ).
Правило «Из Х следует Y » имеет поддержку s , если s % транзакций из всего набора содержат наборы элементов Х и Y .
Достоверность правила показывает, какова вероятность того, что из X
следует Y . Правило «Из X следует Y » справедливо с достоверностью с ,
если c % транзакций из всего множества, содержащих набор элементов X ,
Покажем на конкретном примере: пусть 75 % транзакций, содержащих хлеб, также содержат молоко, а 3 % от общего числа всех транзакций содержат оба товара. 75 % – это достоверность правила, а 3 % – это поддержка.
Лифт (L) – это отношение частоты появления условия в транзакциях, которые также содержат и следствие, к частоте появления следствия в целом. Значения лифта большие, чем единица, показывают, что условие более часто появляется в транзакциях, содержащих и следствие, чем в остальных. Можно сказать, что лифт является обобщенной мерой связи двух предметных наборов: при значениях лифта >1 связь положительная, при 1 она отсутствует, а при значениях <1 – отрицательная.
Другой мерой значимости правила является левередж – это разность между наблюдаемой частотой, с которой условие и следствие появляются совместно (т.е. поддержкой ассоциации), и произведением частот появления (поддержек) условия и следствия по отдельности.
Такие меры, как лифт и левередж могут использоваться для последующего ограничения набора рассматриваемых ассоциаций путем установки порога значимости, ниже которого ассоциации отбрасываются.
Алгоритмы поиска ассоциативных правил предназначены для нахождения всех правил вида «Из X следует Y », причем поддержка и достоверность этих правил должны находиться в рамках некоторых, наперед заданных, границ, называемых соответственно минимальной и максимальной поддержкой и минимальной и максимальной достоверностью .
Границы значений параметров поддержки и достоверности выбираются таким образом, чтобы ограничить количество найденных правил. Если поддержка имеет большое значение, то алгоритмы будут находить правила, хорошо известные аналитикам или настолько очевидные, что нет никакого смысла проводить такой анализ. С другой стороны, низкое значение поддержки ведет к генерации огромного количества правил, что, конечно, требует существенных вычислительных ресурсов. Тем не менее, большинство интересных правил находится именно при низком значении порога поддержки, хотя слишком низкое значение поддержки ведет к генерации статистически необоснованных правил. Таким образом, необходимо найти компромисс, обеспечивающий, во-первых, интересность
правил и, во-вторых, их статистическую обоснованность. Поэтому значения этих границ напрямую зависят от характера анализируемых данных и подбираются индивидуально.
Простейший алгоритм поиска состоит в том, что для всех ассоциаций, которые могут быть построены на основе базы данных, определяется поддержка и достоверность, а затем отбираются те из них, для которых эти показатели превышают заданное пороговое значение. Однако в большинстве случаев такое элементарное решение неприемлемо, поскольку число ассоциаций, которое при этом придется анализировать, слишком велико. Так, если выборка содержит всего 100 предметов, количество образуемых ими ассоциаций будет порядка 1031, а в реальных ситуациях (например, при анализе покупок в супермаркете) номенклатура учитываемых продуктов может достигать нескольких тысяч и более. Очевидно, что никаких вычислительных мощностей на такой расчет не хватит.
Поэтому на практике при поиске ассоциативных правил используют различные приемы, которые позволяют уменьшить пространство поиска до размеров, обеспечивающих приемлемые затраты машинного времени. Сейчас одним из наиболее распространенных является алгоритм a priori , основанный на понятии популярного набора (часто встречающийся предметный набор). Этот термин обозначает предметный набор, частота появления которого в общей совокупности транзакций превышает некоторый заранее заданный уровень.
Таким образом, алгоритм a priori включает два этапа:
– поиск популярных наборов;
– формулировка ассоциативных правил, удовлетворяющих заданным ограничениям по уровням поддержки и достоверности.
В Deductor Studio для решения задач ассоциации используется обработчик Ассоциативные правила . В нем реализован алгоритм a priori . Обработчик требует на входе два поля: идентификатор транзакции и элемент транзакции.
