Выявление обобщенных ассоциативных правил

Введение

В данной статье будет обсуждаться проблема выявления обобщенных ассоциативных правил. Здесь мы будем использовать некоторые определения и термины, которые были описаны в статье «Введение в анализ ассоциативных правил». Наряду с уже известными параметрами правила такими как поддержка и достоверность опишем такой параметр, как уровень интереса. Также будут приведены два алгоритма вычисления обобщенных ассоциативных правил: базовый алгоритм и улучшенный алгоритм.

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

Определение 1. Иерархией (таксономией) элементов называется лес направленных ациклических деревьев, листьями которых являются элементы транзакций, а внутренними узлами — группы элементов.

Пример иерархии товаров и товарных групп приведен на рис. 1. Имея такую иерархию, можно получить, например, такие правила: «Если покупатель купил Сок, то он, скорее всего, захочет купить Кефир»‎; «Если покупатель купил Молочные продукты, то он, скорее всего, захочет купить Минеральную воду»‎. То есть, в получаемых правилах, как в условии, так и в следствии могут присутствовать элементы, находящиеся на разных уровнях таксономии.

Введение информации о принадлежности элементов транзакций к той или иной группе может дать следующие преимущества:

1. Будут выявлены ассоциативные правила не только между отдельными элементами, но и между различными уровнями иерархии.
2. В некоторых случаях отдельные элементы могут иметь очень маленькую поддержку, однако, значение поддержки всей группы, в которую входит этот элемент, может быть больше порога минимальной поддержки. Это приводит к тому, что ранее не выявленное потенциально интересное правило, построенное на элементах нижнего уровня иерархии, может быть получено, но его элементами будут либо элементы транзакции, либо предки этих элементов.
3. Введение информации о группировке элементов может использоваться для отсечения «неинтересных»‎ правил.

Пусть I={i_1,i_2,...i_m} — это множество элементов. Пусть I — это лес направленных деревьев. Дуги в I — это зависимости между элементами. Пусть элементы, принадлежащие I, расположены в некой иерархии. Если есть дуга от a к b, то говорят, что a — предок b, и b — потомок a (a — это обобщение b).

Пусть имеется множество транзакций D, где каждая транзакция T — это множество элементов (событий), произошедших одновременно. Имеет место следующее утверждение: T⊆I.

Определение 2. Расширенной транзакцией называется транзакция, расширенная предками всех элементов, входящих в эту транзакцию.

Определение 3. Обобщенным ассоциативным правилом называется импликация X \Rightarrow Y, где X⊂I, Y⊂I и X∩Y=\varnothing, и где ни один из элементов, входящих в набор Y, не является предком ни одного элемента, входящего в X. Правило X⇒Y имеет поддержку s (support), если s расширенных транзакций, содержат X∪Y, supp(X∪Y)=supp(X⇒Y). Достоверность правила показывает, какова вероятность того, что из X следует Y. Правило X⇒Y справедливо с достоверностью c (confidence), если c расширенных транзакций, содержащих X, также содержат Y, conf(X⇒Y)=supp(X∪Y)/supp(X).

Мы называем правило X⇒Y обобщенным, потому что элементы, входящие в него, могут находиться на любом уровне таксономии. Также будем называть \underline{x} — предком x и x — потомком \underline{x}.

Задача.

Пусть D — это множество транзакций, а I — множество элементов, находящихся в иерархической зависимости. Необходимо найти закономерности, которые являются обобщенными ассоциативными правилами вида X⇒Y, причем supp(X⇒Y)>=minsupp и conf(X⇒Y)>=minconf.

Это определение задачи имеет одну проблему. Дело в том, что при таком определении задачи, будут найдены «излишние» обобщенные ассоциативные правила. Для решения этой проблемы рассмотрим такой параметр правила, как уровень интереса.

Замечания.

Пусть Pr(X) — это вероятность того, что все элементы из X содержаться в одной расширенной транзакции. Тогда supp(X∪Y)=Pr(X∪Y) и conf(X⇒Y)=Pr(Y|X). Если поддержка [x,y] больше значения минимальной поддержки, то и поддержка [\underline{x},y], и поддержка [{x},\underline{y}], и поддержка [\underline{x},\underline{y}] будет больше порога минимальной поддержки. Однако, если достоверность правила X⇒Y больше минимальной достоверности, только правило X \Rightarrow \underline{Y} гарантированно будет иметь достоверность больше, чем минимальная. Поддержка элемента, взятого из внутреннего уровня иерархии не равна сумме поддержек элементов, являющихся непосредственными потомками этого элемента.

Определение «‎интересных» правил

Многие обобщенные ассоциативные правила, которые могут быть найдены, являются потенциально неинтересными (примерно 20% - 70%). Для определения того, какие правила являются «‎интересными», а какие нет, определим такой параметр, как уровень интереса.

Пусть \underline{Z} — это предок Z, где Z и \underline{Z} — множества элементов, входящих в иерархию (Z,Z⊆I). \underline{Z} является предком Z, только в том случае, если \underline{Z} можно получить из Z путем подмены одного или нескольких элементов их предками. Если рассматривать иерархию на рис. 1, то примером могут быть эти два множества: Z={ Сок, Кефир, Бумага }, \underline{Z}={ Напитки, Молочные продукты, Бумага }. Будем называть правила \underline{X} \Rightarrow Y, X \Rightarrow \underline{Y}, X \Rightarrow Y предками правила X⇒Y.

Определение 4. Правило \underline{X} \Rightarrow \underline{Y} является ближайшим предком правила X⇒Y, если не существует такого правила X'⇒Y', что X'⇒Y' — это предок X \Rightarrow и \underline{X} \Rightarrow \underline{Y} — это предок X'⇒Y'.

Подобные определения можно дать и для правил: \underline{X} \Rightarrow Y, X \Rightarrow \underline{Y}.

Рассмотрим правило X⇒Y. Пусть Z=X∪Y. Заметим, что supp(X⇒Y)=supp(Z). Назовем E_{\underline Z}\,\bigl[Pr\,(Z)\bigr] ожидаемым значением Pr(Z) относительно \underline{Z}. Пусть Z=[z_1,...,z_n], Z=[z_1,...,z_j,z_{j+1},...,z_n], 1 < = j < = n. Тогда можно определить:

E_{\underline Z}\,\Bigl[Pr\,(Z)\Bigr] = \frac{Pr\,(z_1)}{Pr\,(\underline z_1)}\,*\,\dots\,*\,\frac{Pr\,(z_j)}{Pr\,(\underline z_j)}\,*\,Pr\,(\underline Z)

Аналогично E_{\underline X \Rightarrow \underline Y}\,\Bigl[Pr\,(Y\,|\,X)\Bigr] определим как ожидаемое значение достоверности правила X⇒Y относительно \underline{X} \Rightarrow \underline{Y}. Пусть Y=[y_1, ..., y_n], \underline{Y}=[\underline{y}_1, ..., \underline{y}_j, y_j+1..., y_n], 1 < = j < = n. Тогда можно определить

E_{\underline X \Rightarrow \underline Y}\,\Bigl[Pr\,(Y\,|\,X)\Bigr] = \frac{Pr\,(y_1)}{Pr\,(\underline y_1)}\,*\,\dots\,*\,\frac{Pr\,(y_j)}{Pr\,(\underline y_j)}\,*\,Pr\,(\underline Y\,|\,\underline X)

Определение 5. Правило X⇒Y называется R-интересным относительно правила-предка, если поддержка правила X⇒Y в R раз больше ожидаемой поддержки правила X⇒Y относительно правила-предка или если достоверность правила X⇒Y в R раз больше ожидаемой достоверности правила X⇒Y относительно правила-предка.

Определение 6. Правило называется интересным, если у него нет предков или оно является R интересным относительно всех своих ближайших предков.

Определение 7. Правило называется частично интересным, если у него нет предков или оно является R-интересным относительно любого своего ближайшего предка.

Пример.

Пусть в результате работы алгоритма мы получили следующие правила (таблица 1). Поддержка элементов входящих в них приведена в таблице 2. Иерархия элементов дана рис. 1. Уровень интереса R=1,3.

Рассмотрим правило номер 3. Определим, является ли это правило интересным, частично интересным или нет. Другими словами, нам необходимо проверить неравенство:

Pr[ \text{Сок} \Rightarrow \text{Кефир}]>E_{\underline \text{Сок}\Rightarrow \underline \text{Кефир} } [Pr( \text{Сок} \Rightarrow \text{Кефир})]* R

Правило 2 является ближним предком правила 3, посчитаем ожидаемую поддержку.

E_{ \text{Безалк. напитки}\Rightarrow \text{Кефир} }= \frac{Pr(\text{Сок})}{Pr(\text{Безалк. напитки})}*Pr(\text{Безалк. напитки} \Rightarrow \text{Кефир})=\frac{3}{5}*15=9

Неравенство

Pr(\text{Сок} \Rightarrow \text{Кефир})> E_{ \text{Безалк. напитки}\Rightarrow \text{Кефир} } (\text{Сок} \Rightarrow \text{Кефир})* R

не выполняется, следовательно, правило 3 не является интересным.

Pr(\text{Сок} \Rightarrow \text{Кефир})> E_{ \text{Сок}\Rightarrow \text{Мол. продукты} } (\text{Сок} \Rightarrow \text{Кефир})* R

не выполняется, следовательно, правило 3 не является интересным.

Правило 1 тоже является ближним предком правила 3, посчитаем ожидаемую поддержку.

Пусть D — это множество транзакций, а I — множество элементов, находящихся в иерархической зависимости. Необходимо найти закономерности, которые являются обобщенными ассоциативными правилами вида X⇒Y, причем поддержка правила X⇒Y больше или равна некоему наперед заданному значению минимальной поддержки и достоверность больше или равна значению минимальной достоверности и правила X⇒Y является интересными или частично интересными.

Алгоритм вычисления обобщенных ассоциативных правил

Как может показаться с первого взгляда, для вычисления обобщенных ассоциативных правил можно использовать любой алгоритм выявления ассоциативных правил, дополнив каждую транзакцию предками каждого элемента, входящего в транзакцию. Однако, такой метод «‎в лоб» очень неэффективен и использование его влечет за собой следующие проблемы:

1. Размер каждой транзакции увеличивается в зависимости от глубины дерева от нескольких десятков процентов до нескольких раз. Как следствие, время вычисления и количество правил увеличиваются.
2. Появление избыточных правил, в которых в условии и в следствии находятся элемент и его предок. Примером такого правила может быть «‎Если покупатель купил Кефир, то он, скорее всего, захочет купить Молочные продукты». Совершенно ясно, что практическая ценность этого правила равна нулю при достоверности равной 100%.

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

Процесс вычисления обобщенных ассоциативных правил можно разбить на несколько этапов:

1. Поиск часто встречающихся множеств элементов, поддержка которых больше, чем заданный порог поддержки (минимальная поддержка).
2. Вычисления правил на основе найденных на предыдущем этапе часто встречающихся множеств элементов. Основная идея вычисления правил на основе часто встречающихся множеств заключается в следующем: если ABCD — это часто встречающееся множество элементов, то на основе этого множества можно построить правила X⇒Y (например, AB⇒CD), причем X∪Y=ABCD. Поддержка правила равна поддержке часто встречающегося множества. Достоверность правила вычисляется по формуле conf(X⇒Y)=supp(X⇒Y)/supp(X). Правило добавляется к результирующему списку правил, если достоверность этого правила больше порога minconf.
3. Из результирующего списка правил удаляются все «неинтересные» правила.

Базовый алгоритм поиска часто встречающихся множеств

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

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

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

1. L_1 = \{ Часто встречающиеся множества элементов и групп элементов \};
2.   \text{ для} (k=2, L_{k-1} \verb!<>! \varnothing, k\verb!++! )
3.     \{
4.       C_k = \{ Генерация кандидатов мощностью \ k на основе \ L_{k-1} \}
5.        для всех транзакций t∈D
6.        \{
7.            Расширить транзакцию t предками всех элементов,
8.              входящих в транзакцию
9.                Удалить дубликаты из транзакции t
10.                для всех кандидатов c \in C_k
11.              \text{если } c \subseteq t \text{ , то}
12.            c.count\verb!++!
13.         \}
14.       L_k = [c \in C_k | c.count > = minsupp ] // Отбор кандидатов
15.     \}
16. Результат = U_kL_k

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

Для эффективного подсчета поддержки кандидатов можно использовать хэш-дерево [5]. Хеш-дерево строится каждый раз, когда формируются кандидаты. Первоначально дерево состоит только из корня, который является листом, и не содержит никаких кандидатов-наборов.

Каждый раз, когда формируется новый кандидат, он заносится в корень дерева, и так до тех пор, пока количество кандидатов в корне-листе не превысит некоего порога.

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

Улучшенный алгоритм поиска часто встречающихся множеств

К базовому алгоритму можно добавить несколько оптимизаций, которые увеличат скорость работы базового алгоритма:

1. Целесообразно единожды вычислить множества предков для каждого элемента иерархии: как для элемента нижнего уровня таксономии (лист дерева), так и для элемента внутреннего уровня.

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

1. Лемма 1. Поддержка множества X, содержащего и элемент x и его предок \underline{x} вычисляется по формуле supp(X)=supp(X-\underline{x}). Принимая во внимание эту лемму, мы будем удалять кандидаты, содержащие и элемент и его предок из списка кандидатов до начала процесса подсчета поддержки.

   Лемма 2. Если L_k — это список часто встречающихся множеств, не содержащий множеств, включающих и элемент и его предок в одном множестве, то C_{k+1} (список кандидатов, получаемых из L_k) также не будет содержать множеств, включающих и элемент и его предок. Учитывая утверждение, данное в этой лемме, мы будем удалять кандидатов, включающих и элемент и его предок, из списка кандидатов только на первой итерации внешнего цикла.

2. Нет необходимости в добавлении всех предков всех элементов, входящих в транзакцию. Если какой-то элемент, у которого есть предок, не находится в списке кандидатов, то в списке элементов с предками он помечается как удаленный. Следовательно, из транзакции удаляются элементы, помеченные как удаленные, или производится замена этих элементов на их предков. К транзакции добавляются только не удаленные предки.
3. Не «пропускать»‎ транзакцию через хэш-дерево, если ее мощность меньше чем мощность элементов, расположенных в хэш-дереве.
4. Целесообразно помечать транзакции как удаленные и не использовать их при подсчете поддержки на следующих итерациях, если на текущей итерации в эту транзакцию не вошел ни один кандидат.

Учитывая написанное выше, получаем следующий алгоритм:

1. // Оптимизация 1
2.    Вычислить I* множества предков элементов для каждого элемента
3.     L_1 = \{ Часто встречающиеся множества элементов и групп элементов \};
4.        \text{ для} (k=2, L_{k-1} \verb!<>! \varnothing, k\verb!++! )
5.         \{
6.           C_k = \{ Генерация кандидатов мощностью \ k на основе \ L_{k-1} \}
7. // Оптимизация 2
8.    если k=2 то
9.      удалить те кандидаты из C_k, которые содержат элемент и его предок
10. // Оптимизация 3
11.    Пометить как удаленные множества предков элемента, которые не содержатся в списке кандидатов
12.      для всех транзакций t \in D
13.       \{
14. // Оптимизация 3
15.     для каждого элемента x \in t
16.        добавить всех предков x из I* к t
17.          Удалить дубликаты из транзакции t
18. // Оптимизация 4,5
19.    если (t не помечена как удаленная) и (|t|>=k) то
20.     \{
21.        для всех кандидатов c \in C_k
22.          если c \subseteq t то
23.        c.count\verb!++!;
24. // Оптимизация 5
25.    если в транзакцию t не вошел ни один кандидат то
26.      отметить эту транзакцию как удаленную;
27.     \}
28.       \}
29. // Отбор кандидатов
30.    L_k = [c\in C_k | c.count = minsupp]
31.     \}
32. Результат = U_k<L_k

Заключение

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

Появление такого инструмента, как алгоритм поиска обобщенных ассоциативных правил, значительно расширило круг задач, решаемых при помощи методов выявления стандартных шаблонов событий [3]. Примером может служить задача нахождения зависимостей между товарами, продаваемыми некой фирмой и ее покупателями. Цель такой задачи — это найти тех покупателей на конкретные товары (например, товары, которые «‎завалялись»‎ на складе), которые их никогда не покупали, но покупали схожие.

Литература

Другие материалы по теме:

Введение в анализ ассоциативных правил

Apriori - масштабируемый алгоритм поиска ассоциативных правил 

«Ситилинк» задействует Loginom в управлении товарными запасами

Поиск последовательных шаблонов| Часть 1