|
Например, поддержка 3-объектного набора {term5, term4, term2} будет всегда меньше или равна поддержке 2-объектных наборов {term5, term4}, {term4, term2}, {term5, term2}. Это объясняется тем, что любая транзакция, содержащая {term5, term4, term3}, содержит также и наборы {term5, term4}, {term4, term3}, {term5, term3}, причем обратное неверно. Алгоритм Apriori определяет часто встречающиеся наборы за несколько этапов. На i-м этапе определяются все часто встречающиеся iэлементные наборы. Каждый этап состоит из двух шагов: формирования кандидатов (candidate generation) и подсчета поддержки кандидатов (candidate counting). Рассмотрим i-и этап. На шаге формирования кандидатов алгоритм создает множество кандидатов из i-элементных наборов, чья поддержка пока не вычисляется. На шаге подсчета кандидатов алгоритм сканирует множество транзакций, вычисляя поддержку наборов-кандидатов. После сканирования отбрасываются кандидаты, поддержка которых меньше определенного пользователем минимума, и сохраняются только часто встречающиеся i-элементные наборы. Во время 1-го этапа выбранное множество наборов-кандидатов содержит все 1-элементные частые наборы. Алгоритм вычисляет их поддержку во время шага подсчета кандидатов. Описанный алгоритм можно записать в виде следующего псевдокода: L1 = {часто встречающиеся 1-элементные наборы} для (k=2; Lk <> ф; к++) Ск = Apriorigen (Fk-1) // генерация кандидатов для всех транзакции t е D выполнить Ct = subset (Ck , t) // удаление избыточных правил для всех кандидатов с е С, выполнять с.count ++ конец для всех конец для всех Lk { с е Ск с.count >= Suppmin} // отбор кандидатов 89 |
включаются в решение задачи. С этой точки зрения нельзя объединять разные правила, хотя и имеющие общую смысловую нагрузку. Например, следующие правила: }{},{ 321 iYiiX =⇒= , }{},{ 421 iYiiX =⇒= нельзя объединить в одно },{},{ 4321 iiYiiX =⇒= , так как достоверности их будут разные, следовательно, некоторые из них могут быть исключены, а некоторые – нет. Если объекты имеют дополнительные атрибуты, которые влияют на состав объектов в транзакциях, а следовательно, и в наборах, то они должны учитываться в генерируемых правилах. В этом случае условная часть правил будет содержать не только проверку наличия объекта в транзакции, но и более сложные операции сравнения: больше, меньше, включает и др. Результирующая часть правил также может содержать утверждения относительно значений атрибутов. Алгоритмы. Алгоритм Apriori. Выявление частых наборов объектов – операция, требующая большого количества вычислений, а следовательно, и времени. Алгоритм Apriori описан в 1994 г. [10]. Он использует одно из свойств поддержки, гласящее: поддержка любого набора объектов не может превышать минимальной поддержки любого из его подмножеств: EF SuppSupp ≤ при FE ⊂ . Алгоритм Apriori определяет часто встречающиеся наборы за несколько этапов. На i -м этапе определяются все часто встречающиеся i -элементные наборы. Каждый этап состоит из двух шагов: формирование кандидатов и подсчет поддержки кандидатов. Рассмотрим i -й этап. На шаге формирования кандидатов алгоритм создает множество кандидатов из i -элементных наборов, чья поддержка пока не вычисляется. На шаге подсчета кандидатов алгоритм сканирует множество транзакций, вычисляя поддержку наборов-кандидатов. После сканирования отбрасываются кандидаты, поддержка которых меньше определенного пользователем минимума, и сохраняются только часто встречающиеся i-элементные наборы. Во время 1-го этапа выбранное множество наборов-кандидатов содержит все 1-элементные частые наборы. Алгоритм вычисляет их поддержку во время шага подсчета кандидатов. Описанный алгоритм можно записать в виде следующего псевдокода: =1L {часто встречающиеся 1-элементые наборы} Для ( 2=k ; <>−1kL Ø; k++) kC = Apriorigen(Fk-1) Для всех Dt ∈ выполнить ),( tCsubsetC kt = Для всех tCc ∈ выполнить ++countc. Конец для всех Конец для всех }Suppc.countC{cL minkk ≥∈= Конец для Результат = U k kL Опишем обозначения, используемые в алгоритме: • kL – множество k-элементных частых наборов, чья поддержка не меньше заданной пользователем. Каждый член множества имеет набор упорядоченных ( pj ii < , если pj < ) элементов F и значение поддержки набора minSuppSuppF < : )},(...,),,(),,{( 2211 qq SuppFSuppFSuppFL = , где }...,,,{ 21 kiiiF = ; • kC – множество кандидатов k-элементных наборов потенциально частых. Каждый член множества имеет набор упорядоченных ( pj ii < , если pj < ) элементов F и значение поддержки набора Supp . Опишем алгоритм по шагам. Шаг 1. Присвоить 1=k и выполнить отбор всех 1-элементных наборов, у которых поддержка больше минимально заданной пользователем minSupp . Шаг 2. 1+= kk . Шаг 3. Если не удается создавать k-элементные наборы, то завершить алгоритм, иначе выполнить следующий шаг. Шаг 4. Создать множество k-элементных наборов кандидатов в частые наборы. Для этого необходимо объединить в kэлементные кандидаты ( 1−k )-элементные частые наборы. Каждый кандидат kCc ∈ будет формироваться путем добавления к ( 1−k )-элементному частому набору p элемента из другого ( 1−k )-элементного частого набора q . Причем добавляется последний элемент набора q , который по порядку выше, чем последний элемент набора p ( 11 .. −− < kk itemqitemp ). При этом первые все 2−k элемента обоих наборов одинаковы ( ,.. 11 itemqitemp = 2222 .....,,.. −− == kk itempitempitemqitemp ). Шаг 5. Для каждой транзакции T из множества D выбрать кандидатов tC из множества kC , присутствующих в транзакции T . Для каждого набора из построенного множества kC удалить набор, если хотя бы одно из его ( 1−k ) подмножеств не является часто встречающимся, т.е. отсутствует во множестве 1−kL . Это можно записать в виде следующего псевдокода. Для всех kCc ∈ выполнить Для всех ( 1−k ) – поднаборов s из c выполнить |