Проверяемый текст
Матвейкин В.Г., Дмитриевский Б.С., Ляпин Н.Р. Информационные системы интеллектуального анализа. – М.: Машиностроение, 2008.
[стр. 88]

нельзя объединять разные правила, хотя и имеющие общую смысловую нагрузку.
Например, следующие правила:
.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
[стр. 12]

включаются в решение задачи.
С этой точки зрения нельзя объединять разные правила, хотя и имеющие общую смысловую нагрузку.
Например, следующие правила: }{},{
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 выполнить

[Back]