Введение
Алгоритм поиска часто встречающихся наборов элементов и обучения правил ассоциации для транзакционных баз данных. Apriori — это алгоритм для поиска часто встречающихся наборов элементов и обучения правил ассоциации в реляционных базах данных. Он работает путем идентификации часто встречающихся отдельных элементов в базе данных и расширения их до все больших и больших наборов элементов, пока эти наборы элементов достаточно часто не встречаются в базе данных. Часто встречающиеся наборы элементов, определяемые алгоритмом Apriori, могут быть использованы для определения правил ассоциации, которые выявляют общие тенденции в базе данных: это находит применение в таких областях, как анализ рыночной корзины.
Apriori is an algorithm for frequent item set mining and association rule learning over relational databases. It proceeds by identifying the frequent individual items in the database and extending them to larger and larger item sets as long as those item sets appear sufficiently often in the database. The frequent item sets determined by Apriori can be used to determine association rules which highlight general trends in the database: this has applications in domains such as market basket analysis.
Ограничения
Априори, хотя и имеет историческое значение, страдает от ряда неэффективностей или компромиссов, что привело к разработке других алгоритмов. Генерация кандидатов порождает большое количество подмножеств (алгоритм стремится максимально заполнить набор кандидатов, включая как можно больше подмножеств перед каждым сканированием базы данных). Поиск подмножеств снизу вверх (по сути, обход решетки подмножеств в ширину) находит любое максимальное подмножество S только после проверки всех его собственных подмножеств. Алгоритм слишком многократно сканирует базу данных, что снижает общую производительность. В связи с этим, алгоритм предполагает, что база данных постоянно находится в оперативной памяти. Кроме того, временная и пространственная сложность этого алгоритма очень высоки: , то есть экспоненциальны, где – горизонтальная ширина (общее количество элементов), присутствующих в базе данных. Более поздние алгоритмы, такие как Max Miner, пытаются идентифицировать максимальные часто встречающиеся наборы элементов без перечисления их подмножеств и осуществляют "переходы" в пространстве поиска, а не используют исключительно подход снизу вверх.