нельзя объединять разные правила, хотя и имеющие общую смысловую нагрузку. Например, следующие правила: .v = {,-1,;2}=3y = {;J}, нельзя объединить в одно: ^-{;„;2}=»у = {;„;2}, т. к. достоверности их будут разные, следовательно, некоторые из них могут быть исключены, а некоторые — нет. Если объекты имеют дополнительные атрибуты, которые влияют на состав объектов в транзакциях, а следовательно, и в наборах, то они должны учитываться в генерируемых правилах. В этом случае условная часть правил будет содержать не только проверку наличия объекта в транзакции, но и более сложные операции сравнения: больше, меньше, включает и др. Результирующая часть правил также может содержать утверждения относительно значений атрибутов. Например, если у терминов рассматриваются веса, то правила могут иметь следующий вид: если term5. вес > 10 то term2. вес > 7. Данное правило говорит о том, что если запрашивается term5 в документе с весом больше 10, то, вероятно, будут запрошен term2 с весом больше 7. 3.3. Алгоритмы 3.3.1. Алгоритм Apriori Выявление частых наборов объектов — операция, требующая большого количества вычислений, а следовательно, и времени. Алгоритм Apriori описан Срикантом Рамакришнан (Ramakrishnan Srikant) и Ракешом Агравалом (Rakesh Agrawal). Он использует одно из свойств поддержки, гласящее: поддержка любого набора объектов не может превышать минимальной поддержки любого из его подмножеств: SuppF < SuppE , при EcF. 88 |
включаются в решение задачи. С этой точки зрения нельзя объединять разные правила, хотя и имеющие общую смысловую нагрузку. Например, следующие правила: }{},{ 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 выполнить |