Технологии интеллектуального анализа данных : учебное пособие

144 Алгоритм Apriori определяет часто встречающиеся наборы за несколько этапов. На i -м этапе определяются все часто встречаю- щиеся i -элементные наборы. Каждый этап состоит из двух шагов: формирования кандидатов (candidate generation) и подсчета под- держки кандидатов (candidate counting). Рассмотрим i -й этап. На шаге формирования кандидатов ал- горитм создает множество кандидатов из i -элементных наборов, чья поддержка пока не вычисляется. На шаге подсчета кандидатов алгоритм сканирует множество транзакций, вычисляя поддержку наборов-кандидатов. После сканирования отбрасываются кандида- ты, поддержка которых меньше определенного пользователем ми- нимума, и сохраняются только часто встречающиеся i -элементные наборы. Во время первого этапа выбранное множество наборов- кандидатов содержит все 1-элементные частые наборы. Алгоритм вычисляет их поддержку во время шага подсчета кандидатов. Описанный алгоритм можно записать в виде следующего псевдокода: L 1 = {часто встречающиеся 1-элементные наборы} для ( k = 2; L k –1 <> ф; k ++) С k = Apriorigen( Fk –l) // генерация кандидатов для всех транзакций t  D выполнить C t = subset ( C k , t ) // удаление избыточных правил для всех кандидатов с  C t выполнить с.count ++ конец для всех конец для всех L k = { с  Ck | с.count >= Supp min } // отбор кандидатов конец для Результат = k k L 