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

Алгоритм Apriori использует одно из свойств поддержки, гласящее: поддержка любого набора объектов не может превышать минимальной поддержки любого из его подмножеств:

, при .

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

Алгоритм Apriori определяет часто встречающиеся наборы за несколько этапов. На i-м этапе определяются все часто встречающиеся i-элементные наборы. Каждый этап состоит из двух шагов: формирования кандидатов и подсчета поддержки кандидатов.

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

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

L₁ = {часто встречающиеся 1-элементные наборы}

для (k=2; L_k-1<>; k++)

С_k = Apriorigen(F_k-1) // генерация кандидатов

для всех транзакций t  D выполнить

C_t = subset(C_k, t) // удаление избыточных правил

для всех кандидатов с  C_t выполнить

с.count ++

конец для всех

конец для всех

L_k = (с  C_k | с.count >= Supp_min} // отбор кандидатов

конец для

Результат = .

Опишем обозначения, используемые в алгоритме:

L_k – множество k-элементных частых наборов, чья поддержка не меньше заданной пользователем. Каждый член множества имеет набор упорядоченных (i_j < i_p, если j < р) элементов F и значение поддержки набора Supp_F > Supp_min:

,

где .

C_k – множество кандидатов k-элементных наборов потенциально частых. Каждый член множества имеет набор упорядоченных (i_j < i_p, если j<р) элементов F и значение поддержки набора Supp.

Опишем данный алгоритм по шагам.

Шаг 1. Присвоить k = 1 и выполнить отбор всех k-элементных наборов, у которых поддержка больше минимально заданной пользователем Supp_min.

Шаг 2. k = k + 1.

Шаг 3. Если не удается создавать k-элементные наборы, то завершить алгоритм, иначе выполнить следующий шаг.

Шаг 4. Создать множество k-элементных наборов кандидатов в частые наборы. Для этого необходимо объединить в k-элементные кандидаты (k – 1) – элементные частые наборы. Каждый кандидат с  С_k будет формироваться путем добавления к (k – 1)-элементному частому набору – р элемента из другого (k – 1)-элементного частого набора – q. Причем добавляется последний элемент набора q, который по порядку выше, чем последний элемент набора р (p.item_k-1 < q.item_k-1). При этом первые все k-2 элемента обоих наборов одинаковы (p.item₁ = q.item₁, p.item₂ = q.item₂, ..., p.item_k-2= q.itemk-₂).

Это может быть записано в виде следующего SQL-подобного запроса.

insert into C_k

select p.item₁, p.item₂,…,p.item_k-1, q.item_k-1

from L_k-1p, L_k-1q

where p.item₁ = q.item₁, p.item₂ = q.item₂, …, p.item_k-2 = q.item_k-2,

p.item_k-1 < q.item_k-1

Шаг 5. Для каждой транзакции T из множества D выбрать кандидатов С_i, из множества С_k, присутствующих в транзакции T. Для каждого набора из построенного множества С_k удалить набор, если хотя бы одно из его (k – 1) подмножеств не является часто встречающимся, т. е. отсутствует во множестве L_k-1. Это можно записать в виде следующего псевдокода:

для всех наборов с  С_k выполнить

для всех (k-1) - поднаборов s из с выполнить

если (s L_k-1) то

удалить с из С_k

Шаг 6. Для каждого кандидата из множества С_k увеличить значение поддержки на единицу.

Шаг 7. Выбрать только кандидатов L_k из множества С_k, у которых значение поддержки больше заданной пользователем Supp_min. Вернуться к шагу 2.

Результатом работы алгоритма является объединение всех множеств L_k для всех k.

Рассмотрим работу алгоритма на примере, приведенном в таблице 2, при Supp_min = 0,5. На первом шаге имеем следующее множество кандидатов С₁ (указываются идентификаторы товаров) (таблица 5).

Таблица 5

№	Набор	Supp
1	{0}	0
2	{1}	0,5
3	{2}	0,75
4	{4}	0,25
5	{3}	0,75
6	{5}	0,75

Заданной минимальной поддержке удовлетворяют только кандидаты 2, 3, 5 и 6, следовательно:

L₁ = {{1}, {2}, {3}, {5}}.

На втором шаге увеличиваем значение k до двух. Так как можно построить 2-элементные наборы, то получаем множество С₂ (таблица 6).

Таблица 6

№	Набор	Supp
1	{1,2}	0,25
2	{1,3}	0,5
3	{1,5}	0,25
4	{2,3}	0,5
5	{2,5}	0,75
6	{3,5}	0,5

Из построенных кандидатов заданной минимальной поддержке удовлетворяют только кандидаты 2, 4, 5 и 6, следовательно:

L₂ ={{1,3}, {2,3}, {2, 5}, {3,5}}.

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

Таблица 7

№	Набор	Supp
1	{2,3,5}	0,5

Данный набор удовлетворяет минимальной поддержке, следовательно:

L₃={{2,3,5}}.

Так как 4-элементные наборы создать не удастся, то результатом работы алгоритма является множество:

L =L₁L₂L₃ = {{1}, {2}, {3}, {5}, {1, 3}, {2, 3}, {2, 5}, {3, 5}, {2, 3, 5}}.

Для подсчета поддержки кандидатов нужно сравнить каждую транзакцию с каждым кандидатом. Очевидно, что количество кандидатов может быть очень большим и нужен эффективный способ подсчета. Гораздо быстрее и эффективнее использовать подход, основанный на хранении кандидатов в хэш-дереве. Внутренние узлы дерева содержат хэш-таблицы с указателями на потомков, а листья – на кандидатов. Это дерево используется при быстром подсчете поддержки для кандидатов.

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

После того как хэш-дерево с кандидатами-наборами построено, легко подсчитать поддержку для каждого кандидата. Для этого нужно "пропустить" каждую транзакцию через дерево и увеличить счетчики для тех кандидатов, чьи элементы также содержатся и в транзакции, С_k  T_i = С_k . На корневом уровне хэш-функция применяется к каждому объекту из транзакции. Далее, на втором уровне, хэш-функция применяется ко вторым объектам и т. д. На k-м уровне хэшируется k-элемент, и так до тех пор, пока не достигнем листа. Если кандидат, хранящийся в листе, является подмножеством рассматриваемой транзакции, увеличиваем счетчик поддержки этого кандидата на единицу.

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

Эти же действия применяются для нахождения (k+1)-элементных наборов и т.д.