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

Алгоритм AprioriAll

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

Генерация кандидатов по алгоритму Apriori производится следующим образом. Обозначим F_{k−1}— множество всех частых k−1-последовательностей. Исключим все последовательности так, что k−1-последовательности не будут принадлежать множеству F_{k−1}, т.е. не являются частыми. Например, рассмотрим множество 3-последовательностей F_3, представленное в первом столбце таблицы 1.

После отсечения последовательностей, подпоследовательности которых не содержатся в F_3, получим единственную последовательность, представленную в 3-м столбце. В частности, <1, 2, 4, 3> отсекается, поскольку <2, 4, 3> не лежит в F_3. Например, рассмотрим базу данных, представленную в таблице 2.

Клиентские последовательности получены путем замены транзакций содержащимися в них частыми предметными наборами. Минимальная поддержка определена на уровне 40% (две клиентских последовательности).

На первом проходе производится поиск больших предметных наборов, и, соответственно, частых 1-последовательностей (Таблица 3). Частые последовательности длиной 2, 3 и 4, а также их поддержки представлены в таблицах 4 — 6 соответственно.

На 5-м проходе новых кандидатов получено не было. Таким образом, максимальными частыми последовательностями являются <1, 2, 3, 4>, <1, 3, 5> и <4, 5>, поскольку они не содержатся в последовательностях большей длины. Они и буду представлять собой искомые последовательные шаблоны. Обобщенная блок-схема алгоритма AprioriAll представлена на рисунке 2, где F_1 — множество всех частых 1-последовательностей k — длина последовательности, C_k — множество кандидатов длины k, S_i — кандидаты, входящие в C_k, Sup — оператор вычисления поддержки.

Алгоритм AprioriSome

На каждом проходе базы данных алгоритм AprioriAll обрабатывает последовательности только определенной длины k. При этом анализ последовательностей всех длин может оказаться затратной по времени процедурой. Возникает вопрос: нельзя ли сократить время, требуемое на поиск кандидатов за счет пропуска некоторых длин, и что мы при этом потеряем?

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

Если обозначить номер прохода t, то можно записать, что k(t+1)=k(t)+p. Это означает, что на следующем проходе будут анализироваться последовательности с длиной на p больше, чем на предыдущем. В случае если p=1, алгоритм идентичен AprioriAll, т.е. будут анализироваться все последовательности. Задача заключается в том, чтобы определить, какие длины последовательностей могут быть пропущены.

Обозначим отношение числа частых k-последовательностей к числу всех k-последовательностей-кандидатов, т.е h_{k}=\frac{F_{k}}{C_{k}}. Интуитивно понятно, что если количество кандидатов, удовлетворяющих условию минимальной поддержки, найденных на текущем проходе, увеличивается, то время, затраченное на анализ кандидатов с небольшими длинами, при пропуске длин, уменьшается. Методика выбора длин последовательностей-кандидатов алгоритмом AprioriSome представлена на рисунке 3.

Если на k-м проходе обнаружится, что множество частых последовательностей F_{k−1} окажется пустым, т.е. на предыдущем проходе частых последовательностей обнаружено не было, то сформировать множество кандидатов C_k для текущего прохода окажется невозможным. Тогда для формирования C_k можно использовать множество кандидатов C_{k−1}, что является корректным, поскольку C_{k−1}⊇F_{k−1} .

Пример

Вновь используя базу данных, рассмотренную при описании алгоритма AprioriAll (таблица 2), мы находим множество частых 1-последовательностей (рисунок 1) в процессе первого прохода по БД. Примем k(t+1)=k+2. На 2-м проходе определяем множество кандидатов C_2 для того чтобы получить множество частых последовательностей F_2. На следующем проходе из F_2 получаем C_3 (таблица 7).

Поскольку k не принимает значение 3, множество кандидатов C_3 не будет проверяться на соответствие его последовательностей условию минимальной поддержки. Следовательно, не будет сформировано множество F_3. Непосредственно на основе C_3 будет сформировано множество C_4, которое после упрощения будет тем же самым, что показано в 3-м столбце таблицы 1. После анализа с целью формирования F_4 (таблица 3), производится попытка сформировать C_5, которое, очевидно, оказывается пустым.

Затем начинается обратная фаза. Из F_4 ничего не исключается, поскольку более длинные последовательности вообще отсутствуют. Вычисление поддержки для последовательностей в множестве C_3 на прямой фазе было пропущено. После исключения тех последовательностей в C_3, которые содержатся в последовательностях F_4 (т.е. в <1, 2, 3, 4>), остаются последовательности <1, 3, 5> и <3, 4, 5>. Из них последовательность <1, 3, 5> будет определена как максимальная частая 3-последовательность. Затем, все последовательности, кроме <4, 5>, из множества F_2 исключаются, поскольку они содержатся в некоторых более длинных последовательностях. По этой же причине исключаются все последовательности F_1.

Алгоритм DynamicSome

Так же как и алгоритм AprioriSome, алгоритм DynamicSome на прямой фазе пропускает вычисление поддержки последовательностей-кандидатов определенных длин. На этапе инициализации вычисляются все последовательности-кандидаты, длина которых определяется некоторой переменной L. Затем на прямой фазе обрабатываются все последовательности, длины которых являются множителями L. Таким образом, при L=3 будут обрабатываться последовательности с длинами 1, 2 на фазе инициализации, и с длинами 3, 6, 9, 12... на прямой фазе. Следовательно, представляют интерес только последовательности с длинами 3, 6, 9, 12…

В некоторых случаях фазу инициализации можно опустить. Последовательности с длиной 6 могут быть сформированы путем объединения 2-х последовательностей длины 3. Последовательности с длиной 9 можно сформировать путем объединения последовательностей с длинами 3 и 6. Однако для формирования последовательностей длины 3 понадобятся последовательности с длинами 1 и 2, а, следовательно, и фаза инициализации.

Пример

Зададим значение параметра L=2. Будем использовать множество F_2 из таблицы 4, сформированное на фазе инициализации. На прямой фазе мы получим две последовательности-кандидата в C_4: (1, 2, 3, 4) с поддержкой 2 и (1, 3, 4, 5) с поддержкой 1. Следовательно, только последовательность (1, 2, 3, 4) является частой. На следующем проходе формируется множество C_6, которое будет пустым. Теперь на промежуточной фазе формируются C_3 из F_2 и C_5 из F_4. Поскольку C_5 будет пустым, формируется только C_3 для получения на обратной фазе F_3.

Сравнительная эффективность алгоритмов

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

Основное преимущество AprioriSome над AprioriAll заключается в том, что он позволяет избежать вычисления большого числа немаксимальных последовательностей. Однако данное преимущество сокращается по двум причинам. Во-первых, кандидаты C_k в AprioriAll формируются с использованием L_{k−1}, а в AprioriSome — с использованием C_{k−1}. Поскольку C_{k−1} является подмножеством L_{k−1}, число кандидатов, формируемых AprioriSome может быть больше. Во-вторых, хотя AprioriSome пропускает анализ последовательностей некоторых длин, они генерируются неявно и сохраняются в памяти до окончания работы алгоритма.

Заключение

Мы рассмотрели задачу поиска последовательных шаблонов на базе данных клиентских транзакций и три алгоритма для решения данной задачи. Два алгоритма, AprioriAll и AprioriSome, имеют сравнимую производительность, хотя второй алгоритм несколько выигрывает в случае малых значений минимальной поддержки, когда создается большое количество частых последовательностей. Оба алгоритма являются масштабируемыми, т.е. время выполнения линейно возрастает с увеличением числа транзакций.

Литература

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

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

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

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

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