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

— для хранения множества кандидатов в частые множества признаков длины

и

— для хранения частых множеств признаков длины

Алгоритм 2.5.1. Apriori(Context,min_supp)
Процедура AprioriGen для

-элементных частых множеств признаков порождает их

-надмножества и возвращает только множество потенциально частых кандидатов.
Алгоритм 2.5.2. AprioriGen(

Алгоритм Apriori был разработан для извлечения частых множеств признаков из данных о покупках, которые обычно являются разреженными и слабо коррелированными. Для таких данных число частых множеств признаков невелико, и алгоритм работает очень хорошо. Позднее, когда возникла необходимость поиска частых множеств признаков в плотных, сильно коррелированных данных, оказалось, что Apriori неэффективно работает на таких массивах. Как следствие, для решения проблемы были предложены различные варианты оптимизации и расширения исходного алгоритма (например, Apriori-Close, Pascal, Zart).