Алгоритм Apriori. 
Интеллектуальные системы

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

Алгоритм Apriori относится к алгоритмам на основе объединений шаблонов, суть которых состоит в том, чтобы последовательно открывать частотные шаблоны длины к + 1 путем объединения шаблонов длины к. Для фильтрации шаблонов длины к используется подсчет количества транзакций, соответствующих данному паттерну и выбираются только те, которые имеют достаточное значение поддержки, все остальные отбрасываются. Причина, по которой можно отбрасывать шаблоны длины к и не использовать их в генерации шаблона к + 1, заключается в том, что для каждого частотного k+i-шаблона все его подмножества являются частотными — так что если в алгоритме встретится^{-шаблон,} который не является частотным, то он точно не может быть частью большего частотного шаблона.

Ниже представлен алгоритм Apriori (рис. 6.7). Основной его задачей является модификация обобщенного алгоритма так, чтобы сократить пространство поиска частотных шаблонов исходя из наблюдения, что ни в одном частотном шаблоне не может быть низкочастотных подшаблонов.

Вход:

• • База данных D.
• • Минимальная поддержка s.

Выход:

• Множество частотных шаблонов FP.

Алгоритм:

• 1. Сгенерировать два множества частотных шаблонов F, и F₂ длины 1 и 2 соответственно.
• 2. k = 2.
• 3. Пока множество шаблонов F_k не пусто:
• 3.1. Сгенерировать Q₊₁ — всевозможные шаблоны длины k + 1 за счет попарного объединения шаблонов из F_k и F_k__x.
• 3.2. Исключить из С*₊₁ все шаблоны длины k + 1, у которых хотя бы один подшаблон не имеет достаточной поддержки.
• 3.3. Сгенерировать множество F_{k +} j копированием в него всех оставшихся шаблонов в Q₊₁ и подсчитать их поддержки.
• 4. Вернуть и4

к

Рис. 6.7. Процесс генерации частотных шаблонов по алгоритму Apriori.

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