Алгоритм apriori

Рассмотрим набор клиентов, включающий заданные характеристики. Выразим этот набор с помощью переменных. Обозначим множество характеристик за I – {A, B, C, D..P}

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

1. формирование кандидатов (candidate generation);

2. подсчет поддержки кандидатов (candidate counting).

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

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

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

2. для (k=2; Lk-1 <> ; k++) {

3. Ck = Apriorigen(Lk-1) // генерация кандидатов

4. для всех клиентов t T {

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

6. для всех кандидатов c Ct

7. c.count ++

8. }

9. Lk = { c Ck | c.count >= minsupport} // отбор кандидатов

10. }

11. Результат

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

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

L_k = {(F₁,Supp₁),(F₂,Supp₂),...,(F_q,Supp_q)},
где F_j = {i₁,i₂,...,i_k};

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

Опишем данный алгоритм по шагам.
Шаг 1. Присвоить k = 1 и выполнить отбор всех 1-элементных наборов, у которых поддержка больше минимально заданной. Supp_min.
Шаг 2. k = k + 1.
Шаг 3. Если не удается создавать k-элементные наборы, то завершить алгоритм, иначе выполнить следующий шаг.
Шаг 4. Создать множество k-элементных наборов кандидатов из частых наборов. Для этого необходимо объединить в k-элементные кандидаты (k-1)-элементные частые наборы. Каждый кандидат будет формироваться путём добавления к (k-1)-элементному частому набору - p элемента из другого (k-1)-элементного частого набора - q. Причем добавляется последний элемент набора q, который по порядку выше, чем последний элемент набора p (p.item_{k − 1} < q.item_{k − 1}).
При этом все k-2 элемента обоих наборов одинаковы (p.item₁ = q.item₁,p.item₂ =q.item₂,...,p.item_{k − 2} = q.item_{k − 2}).

Шаг 5. Для каждого клиента T из множества D выбрать кандидатов C_t из множества C_k, присутствующих в наборе характеристик клиента T. Для каждого набора из построенного множества C_k удалить набор, если хотя бы одно из его (k-1) подмножеств не является часто встречающимся т.е. отсутствует во множестве L_{k− 1}. Это можно записать в виде следующего псевдокода:

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

Шаг 6. Для каждого кандидата из C_k увеличить значение поддержки на единицу.
Шаг 7. Выбрать только кандидатов L_k из множества C_k, у которых значение поддержки больше заданной пользователем Supp_min. Вернуться к шагу 2.
Результатом работы алгоритма является объединение всех множеств L_k для всех k.

Таблица 4.1. Схематическое изображение работы алгоритма apriori