Алгоритм поиска ассоциативных правил

Ассоциативные правила позволяют находить закономерности между связанными событиями. Примером такого правила служит утверждение, что покупатель, приобретающий «Хлеб», приобретет и «Молоко». Впервые эта задача была предложена для поиска ассоциативных правил для нахождения типичных шаблонов покупок, совершаемых в супермаркетах, поэтому иногда ее еще называют анализом рыночной корзины (market basket analysis).

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

Ассоциативное правило состоит из двух наборов предметов, называемых условие (англ: antecedent) и следствие (англ: consequent), записываемых в виде X → Y, что читается «из X следует Y». Таким образом, ассоциативное правило формулируется в виде «Если условие, то следствие».

При поиске ассоциативных правил используют показатели, позволяющие оценить значимость правила. В этой связи можно выделить объективные и субъективные меры значимости правил. Объективными являются такие меры, как поддержка и достоверность, которые могут применяться независимо от конкретного приложения. Субъективные меры связаны со специальной информацией, определяемой пользователем в контексте решаемой задачи. Такими субъективными мерами являются лифт и левередж.

Ассоциативные правила описывают связь между наборами предметов, соответствующим условию и следствию. Эта связь характеризуется двумя показателями – поддержкой (s) и достоверностью (с).

Правило «Из Х следует Y» имеет поддержку s, если s % транзакций из всего набора содержат наборы элементов Х и Y.

Достоверность правила показывает, какова вероятность того, что из X

следует Y. Правило «Из X следует Y» справедливо с достоверностью с,

если c % транзакций из всего множества, содержащих набор элементов X,

также содержат набор элементов Y.

Покажем на конкретном примере: пусть 75 % транзакций, содержащих хлеб, также содержат молоко, а 3 % от общего числа всех транзакций содержат оба товара. 75 % – это достоверность правила, а 3 % – это поддержка.

Лифт (L) – это отношение частоты появления условия в транзакциях, которые также содержат и следствие, к частоте появления следствия в целом. Значения лифта большие, чем единица, показывают, что условие более часто появляется в транзакциях, содержащих и следствие, чем в остальных. Можно сказать, что лифт является обобщенной мерой связи двух предметных наборов: при значениях лифта >1 связь положительная, при 1 она отсутствует, а при значениях <1 – отрицательная.

Другой мерой значимости правила является левередж – это разность между наблюдаемой частотой, с которой условие и следствие появляются совместно (т.е. поддержкой ассоциации), и произведением частот появления (поддержек) условия и следствия по отдельности.

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

Алгоритмы поиска ассоциативных правил предназначены для нахождения всех правил вида «Из X следует Y», причем поддержка и достоверность этих правил должны находиться в рамках некоторых, наперед заданных, границ, называемых соответственно минимальной и максимальной поддержкой и минимальной и максимальной достоверностью.

Границы значений параметров поддержки и достоверности выбираются таким образом, чтобы ограничить количество найденных правил. Если поддержка имеет большое значение, то алгоритмы будут находить правила, хорошо известные аналитикам или настолько очевидные, что нет никакого смысла проводить такой анализ. С другой стороны, низкое значение поддержки ведет к генерации огромного количества правил, что, конечно, требует существенных вычислительных ресурсов. Тем не менее, большинство интересных правил находится именно при низком значении порога поддержки, хотя слишком низкое значение поддержки ведет к генерации статистически необоснованных правил. Таким образом, необходимо найти компромисс, обеспечивающий, во-первых, интересность

правил и, во-вторых, их статистическую обоснованность. Поэтому значения этих границ напрямую зависят от характера анализируемых данных и подбираются индивидуально.

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

Поэтому на практике при поиске ассоциативных правил используют различные приемы, которые позволяют уменьшить пространство поиска до размеров, обеспечивающих приемлемые затраты машинного времени. Сейчас одним из наиболее распространенных является алгоритм a priori, основанный на понятии популярного набора (часто встречающийся предметный набор). Этот термин обозначает предметный набор, частота появления которого в общей совокупности транзакций превышает некоторый заранее заданный уровень.

Таким образом, алгоритм a priori включает два этапа:

– поиск популярных наборов;

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

В Deductor Studio для решения задач ассоциации используется обработчик Ассоциативные правила. В нем реализован алгоритм a priori. Обработчик требует на входе два поля: идентификатор транзакции и элемент транзакции.