Алгоритм GSP

Алгоритм GSP ( алгоритм обобщенного последовательного шаблона ) — это алгоритм, используемый для анализа последовательностей . Алгоритмы решения задач последовательного анализа в основном основаны на априорном (поуровневом) алгоритме. Один из способов использования поуровневой парадигмы — сначала обнаружить все часто встречающиеся предметы поуровнево. Это просто означает подсчет вхождений всех одноэлементных элементов в базу данных. Затем транзакции фильтруются путем удаления нечастых элементов. В конце этого шага каждая транзакция состоит только из часто встречающихся элементов, которые она изначально содержала. Эта модифицированная база данных становится входными данными для алгоритма GSP. Этот процесс требует одного прохода по всей базе данных .

Алгоритм GSP выполняет несколько проходов к базе данных. При первом проходе подсчитываются все отдельные элементы (1-последовательности). Из частых элементов формируется набор 2-последовательностей-кандидатов и делается еще один проход для определения их частоты. Часто встречающиеся 2-последовательности используются для генерации 3-последовательностей-кандидатов, и этот процесс повторяется до тех пор, пока не перестанут быть найдены более частые последовательности. В алгоритме есть два основных шага.

Поколение кандидатов. Учитывая набор частых (k-1)-частых последовательностей F _k-1 , кандидаты на следующий проход генерируются путем соединения F(k-1) с самим собой. Фаза сокращения исключает любую последовательность, по крайней мере одна из подпоследовательностей которой не является частой.
Поддержка подсчета. Обычно хеш-дерева для эффективного подсчета поддержки используется поиск на основе . Наконец, удаляются немаксимально частые последовательности.

Алгоритм

   F₁ = the set of frequent 1-sequence
   k=2,
   do while F_k-1 != Null;
       Generate candidate sets C_k (set of candidate k-sequences);
       For all input sequences s in the database D
       do
           Increment count of all a in C_k if s supports a
       End do
       Fk = {a ∈ C_k such that its frequency exceeds the threshold}
       k = k+1;
   End do
   Result = Set of all frequent sequences is the union of all F_k's

Приведенный выше алгоритм выглядит как алгоритм Априори . Однако одним из основных отличий является создание наборов кандидатов. Предположим, что:

А → Б и А → С

представляют собой две частые 2-последовательности. Элементами, участвующими в этих последовательностях, являются (A, B) и (A, C) соответственно. Генерация кандидатов в обычном стиле Априори дала бы (A, B, C) как набор из 3 элементов, но в данном контексте мы получаем следующие 3-последовательности в результате объединения вышеуказанных 2-последовательностей

A → B → C, A → C → B и A → BC.

Это учитывается на этапе генерации кандидатов. Алгоритм GSP обнаруживает частые последовательности, учитывая временные ограничения, такие как максимальный и минимальный разрыв между элементами последовательности. Более того, он поддерживает идею скользящего окна, т. е. временного интервала, в течение которого элементы рассматриваются как принадлежащие к одному и тому же событию, даже если они происходят из разных событий.

См. также

Последовательный майнинг

Ссылки

Р. Шрикант и Р. Агравал. 1996. Последовательные схемы майнинга: обобщения и улучшения производительности . В материалах 5-й Международной конференции по расширению технологий баз данных: достижения в технологии баз данных (EDBT '96), Питер М.Г. Аперс, Мокран Бузегуб и Жорж Гардарен (ред.). Спрингер-Верлаг, Лондон, Великобритания, Великобритания, 3–17.
Пуджари, Арун К. (2001). Методы интеллектуального анализа данных . Университетская пресса. стр. 256–260. ISBN 81-7371-380-4 .
Заки, MJ Machine Learning (2001) 42:31 .

Внешние ссылки

SPMF включает в себя реализацию алгоритма GSP с открытым исходным кодом, а также PrefixSpan , SPADE, SPAM, ClaSP, CloSpan и BIDE.