Алгоритм Apriori

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

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

и

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

. Каждая структура имеет два поля — itemset, сохраняющее множество признаков, и support, которое хранит величину поддержки этого множества признаков. Алгоритм представлен в виде псевдокода и состоит из двух частей: самого Apriori — алгоритм2.5.1 и вспомогательной процедуры AprioriGen — алгоритм 2.5.2 .

Алгоритм 2.5.1. Apriori(Context,min_supp)

Процедура AprioriGen для

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

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

Алгоритм 2.5.2. AprioriGen(

)

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

Содержание раздела

---

---