В чем заключается принцип работы алгоритма Apriori для анализа ассоциативных правил?

Принцип работы алгоритма Apriori для анализа ассоциативных правил заключается в обнаружении часто встречающихся отдельных элементов в базе данных и последующем расширении их на более крупные наборы, если эти наборы также встречаются достаточно часто. 1

Алгоритм состоит из нескольких этапов, каждый из которых включает два шага: 2

1. Формирование кандидатов (candidate generation). 2 Алгоритм сканирует базу данных и создаёт множество i-элементных кандидатов (i — номер этапа). 2 На этом этапе поддержка кандидатов не рассчитывается. 2
2. Подсчёт кандидатов (candidate counting). 2 Вычисляется поддержка каждого i-элементного кандидата. 2 Осуществляется отсечение кандидатов, поддержка которых меньше минимума, установленного пользователем. 2 Оставшиеся i-элементные наборы считаются часто встречающимися. 2

Отсечение кандидатов происходит на основе предположения о том, что у часто встречающегося набора товаров все подмножества должны быть часто встречающимися. 2 Если в наборе находится подмножество, которое на предыдущем этапе было определено как нечасто встречающееся, этот кандидат уже не включается в формирование и подсчет кандидатов. 2

Алгоритм завершает работу, когда больше не найдено успешных расширений. 1