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

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

Алгоритм AprioriAll

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

Генерация кандидатов по принципу Apriori

Обозначим F_k-1 - множество всех частых (k-1)-последовательностей. Исключим все последовательности так, что (k-1)-последовательности не будут принадлежать множеству F_k-1, т.е. не являются частыми. Например, рассмотрим множество 3-последовательностей F₃, представленное в первом столбце таблицы 1.

Таблица 1. Множество 3-последовательностей

После отсечения последовательностей, подпоследовательности которых не содержатся в F₃, получим единственную последовательность, представленную в 3-м столбце. Например, последовательность 1243 отсекается, поскольку подпоследовательность 243 не лежит в F₃. Например, рассмотрим базу данных клиентских последовательностей, представленную в таблице 2.

Таблица 2. БД клиентских последовательностей

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

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

F₁

F₂

F₃

F₄

Рисунок 1 - Частые последовательности для F₁-F₄

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

Рисунок 2 - Обобщенная блок-схема алгоритма AprioriAll

Алгоритм AprioriSome

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

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

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

Обозначим отношение числа частых k-последовательностей к числу всех k-последовательностей-кандидатов, т.е. h_k = F_k/C_k. Интуитивно понятно, что если количество кандидатов, удовлетворяющих условию минимальной поддержки, найденных на текущем проходе, увеличивается, то время, затраченное на анализ кандидатов с небольшими длинами, при пропускании длин, уменьшается. Методика выбора длин последовательностей-кандидатов алгоритмом AprioriSome представлена на рисунке 3.

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

Рисунок 3 - Выбор длины последовательностей в алгоритме AprioriSome

Пример

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

Таблица 3

Поскольку k не принимает значение 3, множество кандидатов C₃ не будет проверяться на соответствие его последовательностей условию минимальной поддержки. Следовательно, не будет сформировано множество F₃. Непосредственно на основе C₃ будет сформировано множество C₄, которое после упрощения будет тем же самым, что показано в 3-м столбце таблицы 1. После анализа с целью формирования F₄ (таблица 3), производится попытка сформировать C₅, которое, очевидно, оказывается пустым.

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

Алгоритм 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₂ из таблицы 8, сформированное в фазе инициализации. На прямой фазе мы получим две последовательности-кандидата в C₄: (1,2,3,4) с поддержкой 2 и (1, 3,4,5) с поддержкой 1. Следовательно, только (1,2,3,4) является частой. На следующем проходе формируется множество C₆, которое будет пустым. Теперь на промежуточной фазе формируются C₃ из F₂ и C₅ из F₄. Поскольку C₅ будет пустым, формируется только C₃ для получения на обратной фазе F₃.

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

Как показали численные эксперименты, алгоритм 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. R. Agrawal and R. Srikant. Fast Algorithms for Mining Association Rules / In Proc. of the 20th Int'l Conference on Very Large Databases, Santiago, Chile, September 1994.
2. R. Agrawal and R. Srikant. Mining Sequential Patterns / Journal Intelligent Systems, vol. 9, No.1, 1997, pp. 33 – 56.
3. Srikant R, Agrawal R. Mining Sequential Patterns: Generalizations and Performance Improvements / In Proc. Int'l Conf Extending Database Technology. Springer (1996) 3-17.