Методы и алгоритмы анализа ассоциаций

Алгоритм AIS. Первый алгоритм поиска ассоциативных правил, называвшийся AIS, (предложенный Agrawal, Imielinski and Swami) был разработан сотрудниками исследовательского центра IBM Almaden в 1993 году. С этой работы начался интерес к ассоциативным правилам; на середину 90-х годов прошлого века пришелся пик исследовательских работ в этой области, и с тех пор каждый год появляется несколько новых алгоритмов. В алгоритме AIS кандидаты множества наборов генерируются и подсчитываются "на лету", во время сканирования базы данных.

Алгоритм SETM. Создание этого алгоритма было мотивировано желанием использовать язык SQL для вычисления часто встречающихся наборов товаров. Как и алгоритм AIS, SETM также формирует кандидатов "на лету", основываясь на преобразованиях базы данных. Чтобы использовать стандартную операцию объединения языка SQL для формирования кандидата, SETM отделяет формирование кандидата от их подсчета.

Неудобство алгоритмов AIS и SETM - излишнее генерирование и подсчет слишком многих кандидатов, которые в результате не оказываются часто встречающимися. Один из первых алгоритмов, эффективно решающих подобный класс задач, – это алгоритм Apriori [7]. Кроме этого алгоритма в последнее время был разработан ряд других алгоритмов: DHP[12], Partition[13], DIC[14] и другие.

Позднее были предложены другие методы поиска ассоциаций, такие как Eclat алгоритм [15], FP-growth алгоритм [16], OPUS алгоритм [17], эволюционные алгоритмы [18] и другие, а также модификации алгоритма Apriori, устраняющие повторный проход по базе данных (AprioriTid, AprioriHybrid и др.) [7], решающие проблемы с распараллеливанием [19] и масштабируемостью алгоритма [20].

В [28] бал представлен алгоритм поиска ассоциативных правил CARMA (Continuous Association Rule Mining Algorithm), разработанный для OLAP-систем. Этот двухэтапный алгоритм позволяет пользователю изменять значение уровня поддержки в любое время первого прохода по базе данных. Во время второго прохода подсчитываются точные характеристики правил. Особенности алгоритма позволяют сократить использование памяти, но время на обработку увеличивается по сравнению с алгоритмом Apriori.

Поиск ассоциативных правил совсем не тривиальная задача, как может показаться на первый взгляд. Одна из проблем - алгоритмическая сложность при нахождении часто встречающих наборов элементов, т.к. с ростом числа элементов рыночной корзины экспоненциально растет число потенциальных наборов элементов. Примитивный подход к решению данной задачи – простой перебор всех возможных наборов элементов. Это потребует O( ) операций, где |I| – количество элементов.

Все алгоритмы поиска ассоциативных правил ищут только те правила, что удовлетворяют ограничениям на минимальную частоту и минимальную достоверность, которые выбирает пользователь. Такие правила называют допустимыми. Цель поиска ассоциативных правил – найти все допустимые ассоциативные правила для исходного множества транзакций.

При поиске часто встречающихся наборов данных используется только первый параметр – минимальный уровень поддержки. Из определения уровня поддержки следует, что правило X=>Y только тогда будет допустимым, если будет часто встречающимся набор, полученный объединением наборов X и Y.

Поиск часто встречающихся наборов опирается на свойство антимонотонности: поддержка любого набора элементов не может превышать минимальной поддержки любого из его подмножеств, то есть, если , то .

Следствие: любое подмножество часто встречаемого набора данных также является часто встречаемым набором.

Например, поддержка 3-элементного набора {Хлеб, Масло, Молоко} будет всегда меньше или равна поддержке 2-элементных наборов {Хлеб, Масло}, {Хлеб, Молоко}, {Масло, Молоко}. Дело в том, что любая транзакция, содержащая {Хлеб, Масло, Молоко}, также должна содержать {Хлеб, Масло}, {Хлеб, Молоко}, {Масло, Молоко}, причем обратное не верно.

Свойству антимонотонности можно дать и другую формулировку: с ростом размера набора элементов поддержка уменьшается, либо остается такой же. Из всего вышесказанного следует, что любой k-элементный набор будет часто встречающимся тогда и только тогда, когда все его (k-1)-элементные подмножества будут часто встречающимися.

Извлечение правил – менее трудоемкая задача. Для определения достоверности правила X=>Y нужно знать только значения поддержки наборов X и , поэтому если уровень поддержки набора  больше минимального, то и уровень поддержки набора X тоже больше минимального в силу свойства антимонотонности, значит, для генерации ассоциативных правил достаточно выполнить поиск всех часто встречающихся наборов с заданным уровнем поддержки. Это избавляет нас от нежелательного просмотра базы транзакций, который потребовался в том случае, если бы поддержка X была неизвестна.

Чтобы извлечь правило из часто встречающегося набора F, следует найти все его непустые подмножества. И для каждого подмножества s мы сможем сформулировать правило s=>(F – s), если достоверность правила Conf(s=>(F – s)) = Supp(F)/Supp(s) не меньше порога minconf.

Заметим, что числитель остается постоянным. Тогда достоверность имеет минимальное значение, если знаменатель имеет максимальное значение, а это происходит в том случае, когда в условии правила имеется набор, состоящий из одного элемента. Все супермножества данного множества имеют меньшую или равную поддержку и, соответственно, большее значение достоверности. Это свойство может быть использовано при извлечении правил. Если мы начнем извлекать правила, рассматривая сначала только один элемент в условии правила, и это правило имеет необходимую поддержку, тогда все правила, где в условии стоят супермножества этого элемента, также имеют значение достоверности выше заданного порога. Например, если правило A=>BCDE удовлетворяет минимальному порогу достоверности minconf, тогда AB=>CDE также удовлетворяет. Для того, чтобы извлечь все правила используется рекурсивная процедура. Важное замечание: любое правило, составленное из часто встречающегося набора, должно содержать все элементы набора. Например, если набор состоит из элементов {A, B, C}, то правило A=>B не должно рассматриваться.

Таким образом, задача нахождения ассоциативных правил разбивается на две подзадачи:

1) Нахождение всех часто встречающиxся наборов элементов, которые удовлетворяют порогу minsupp.

2) Генерация правил из найденных часто встречающиxся наборов элементов с достоверностью, удовлетворяющей порогу minconf.

Алгоритм Apriori

Принцип Apriori

Все возможные наборы элементов из I можно представить в виде решетки, начинающейся с пустого множества, затем на 1 уровне 1-элементные наборы, на 2-м – 2-элементные и т.д. На k уровне представлены k-элементные наборы, связанные со всеми своими (k-1)-элементными подмножествами.

Рассмотрим рисунок 3.1, иллюстрирующий набор элементов I – {a, b, c, d, e}. Предположим, что набор из элементов {a, b} имеет поддержку ниже заданного порога и, соответственно, не является часто встречающимся. Тогда, согласно свойству антимонотонности, все его супермножества также не являются часто встречающимися и отбрасываются. Вся эта ветвь, начиная с {a, b}, вычеркивается. Использование этой эвристики позволяет существенно сократить пространство поиска.

Рисунок 3.1 – Демонстрация принципа Apriori

Алгоритм Apriori

На первом шаге алгоритма подсчитываются 1-элементные часто встречающиеся наборы. Для этого необходимо пройтись по всему набору данных и подсчитать для них поддержку, т.е. сколько раз встречается в базе.

Работа данного алгоритма состоит из нескольких шагов, каждый из следующих шагов состоит из следующих этапов:

а) формирование кандидатов;

б) подсчет кандидатов.

Формирование кандидатов (candidate generation) ­– этап, на котором алгоритм, сканируя базу данных, создает множество i-элементных кандидатов (i – номер этапа). На этом этапе поддержка кандидатов не рассчитывается.

Подсчет кандидатов (candidate counting) – этап, на котором вычисляется поддержка каждого i-элементного кандидата. Здесь же осуществляется отсечение кандидатов, поддержка которых меньше минимума, установленного пользователем (minsupp). Оставшиеся i-элементные наборы называем часто встречающимися.