Алгоритм AprioriAll

Существует большое число разновидностей алгоритма Apriori, который изначально не учитывал временную составляющую в наборах данных. Первым алгоритмом на основе Apriori, позволившим находить закономерности в последовательностях событий, стал предложенный в 1995 году ( Argwal и Srikant ) алгоритм AprioriALL. Данный алгоритм, также как другие усовершенствования Apriori основывается на утверждении, что последовательность, входящая в часто встречающуюся последовательность, также является часто встречающейся. Формат данных, с которыми работает алгоритм уже был описан выше. Это таблица транзакций с тремя атрибутами (id клиента, время транзакции, id товаров в наборе). Работа алгоритма состоит из нескольких фаз. Фаза сортировки заключается в перегруппировке записей в таблице транзакций. Сперва записи сортируются по уникальному ключу покупателя, а затем по времени внутри каждой группы. Пример отсортированной таблицы приведён ниже.

Идентификатор покупателя	Время транзакции	Идентификаторы купленных товаров
1	Окт 23 08	30
1	Окт 28 08	90
2	Окт 18 08	10, 20
2	Окт 21 08	30
2	Окт 27 08	40, 60, 70
3	Окт 15 08	30, 50, 70
4	Окт 8 08	30
4	Окт 16 08	40, 70
4	Окт 25 08	90
5	Окт 20 08	90

Фаза отбора кандидатов - в исходном наборе данных производится поиск одно-элементных последовательностей в соответствии со значением минимальной поддержки. Предположим, что значение минимальной поддержки 40%. Поддержка рассчитывается не из числа транзакций, в которые входит одно-элементная последовательность (в данном случае это есть набор), но из числа покупателей у которых во всех их транзакциях встречается данная последовательность. В результате получим следующие одно-элементные последовательности.

Последовательности	Идентификатор последовательности
(30)	1
(40)	2
(70)	3
(40, 70)	4
(90)	5

Фаза трансформации. В ходе работы алгоритма нам многократно придётся вычислять, присутствует ли последовательность в транзакциях покупателя. Последовательность может быть достаточно велика, поэтому, для ускорения процесса вычислений, преобразуем последовательности, содержащиеся в транзакциях пользователей в иную форму. Заменим каждую транзакцию набором одно-элементных последовательностей, которые в ней содержатся. Если в транзакции отсутствуют последовательности, отобранные на предыдущем шаге, то данная транзакция не учитывается и в результирующую таблицу не попадает. Например, для покупателя с идентификатором 2, транзакция (10, 20) не будет преобразована, поскольку не содержит одно-элементных последовательностей с нужным значением минимальной поддержки (данный набор встречается только у одного покупателя). А транзакция (40, 60, 70) будет заменена набором одно-элементных последовательностей {(40), (70), (40, 70)} Процесс преобразованная будет иметь следующий вид.

Идентификатор покупателя	Последовательности в покупках	Отобранные последовательности	Преобразованные последовательности
1	<(30)(90)>	<{(30)}{(90)}>	<{1}{5}>
2	<(10, 20)(30)(40, 60, 70)>	<{(30)}{(40)(70)(40, 70)}>	<{1}{2, 3, 4}>
3	<(30, 50, 70)>	<{(30)(70)}>	<{1, 3}>
4	<(30)(40, 70)(90)>	<{(30)}{(40)(70)(40, 70)}{(90)}>	<{1}{2, 3, 4}{5}>
5	<(90)>	<{(90)}>	<{5}>

Фаза генерации последовательностей - из полученных на предыдущих шагах последовательностей строятся более длинные шаблоны последовательностей.

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

<{1,5}{2}{3}{4}>

<{1}{3}{4}{3,5}>

<{1}{2}{3}{4}>

<{1}{3}{5}>

<{4}{5}>

Значение минимальной поддержки выберем 40% (последовательность должна наблюдаться как минимум у двоих покупателей из пяти). После фазы отбора кандидатов мы получили таблицу с одно-элементными последовательностями.

1-Последовательность L1	Поддержка
<1>	4
<2>	2
<3>	4
<4>	4
<5>	5

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

2-Последовательность L2	Поддержка
<1 2>	2
<1 3>	4
<1 4>	3
<1 5>	3
<2 3>	2
<2 4>	2
<3 4>	3
<3 5>	2
<4 5>	2

3-Последовательность L3	Поддержка
<1 2 3>	2
<1 2 4>	2
<1 3 4>	3
<1 3 5>	2
<2 3 4>	2

4-Кандидаты	4-Последовательность L4	Поддержка
<1 2 3 4>	<1 2 3 4>	2
<1 2 4 3>
<1 3 4 5>
<1 3 5 4>

Последовательность <1 2 4 3>, например, не проходит отбор, поскольку последовательность <2 4 3>, входящая в неё, не присутствует в L₃. Так как сформировать пяти-элементные последовательности невозможно, работа алгоритма на этом завершается. Результатом его работы будут три последовательности, удовлетворяющие значению минимальной поддержки и не входящие в более длинные последовательности: <1 2 3 4>, <1 3 5> и <4 5>.

Алгоритм в превдо-коде. L₁ = {одно-элементные последовательности, удовлетворяющие минимальному значению поддержки} //Результат фазы отбора кандидатов (L-itemset) for (k=2; ; k++)

begin

C_k = Генерация кандидатов из L_{k − 1}

foreach последовательность покупок с клиента в базе данных do

Увеличить на единицу поддержку всех кандидатов из C_k, которые содержатся в c

L_k = Кандидаты из C_k с минимальной поддержкой.

end

Результат: последовательности максимальной длинны (не входящие в другие последовательности) в ; Процедура генерации кандидатов выполняется следующим образом: insert into C_k select p.itemset₁,...,p.itemset_{k − 1},q.itemset_{k − 1} from L_{k − 1}p,L_{k − 1}q where ; После чего удалить все последовательности , такие что (k-1) последовательность из c не входит в L_{k − 1}.