|
конец для Результат = Lk Опишем обозначения, используемые в алгоритме: Lk — множество /^-элементных частых наборов, чья поддержка не меньше заданной пользователем. Каждый член множества имеет набор упорядоченных (z) < ip , если j < р) элементов F и значение поддержки набора Suppr> Suppmin: Lk = {(Fb Supp,), (F2, Supp2),(Fq, SupPq)} rfleF7 = {zb z2,..., ik}-, Ck — множество кандидатов ^-элементных наборов потенциально частых. Каждый член множества имеет набор упорядоченных (z, < ip, если j < р) элементов F и значение поддержки набора Supp. Опишем данный алгоритм по шагам. Шаг 1. Присвоить к = 1 и выполнить отбор всех 1-элементных наборов, у которых поддержка больше минимально заданной пользователем Suppmin. Шаг 2. к — к + 1 Шаг 3. Если не удается создавать ^-элементные наборы, то завершить алгоритм, иначе выполнить следующий шаг. Шаг 4. Создать множество ^-элементных наборов кандидатов в частые наборы. Для этого необходимо объединить в ^-элементные кандидаты (к 1) — элементные частые наборы. Каждый кандидат с е Ск будет формироваться путем добавления к {к 1 )-элементному частому набору — р элемента из другого {к 1)-элементного частого набора — q. Причем добавляется последний элемент набора д, который по порядку выше, чем последний элемент набора р (р.йенц., < q.item^i). При этом первые все к 2 элемента обоих наборов одинаковы (p.itemi = q.itemi , p.item2 = q.item2 , —, р.йепц., = q.item^). Это может быть записано в виде следующего SQL-подобного запроса, insert into Ck 90 |
включаются в решение задачи. С этой точки зрения нельзя объединять разные правила, хотя и имеющие общую смысловую нагрузку. Например, следующие правила: }{},{ 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 выполнить |