Ksppr

  • 11 дек. 2012 г.
  • 2123 Слова
Санкт-Петербургский Государственный
Электротехнический Университет


ФКТИ

Кафедра МОЭВМ





Дисциплина: Базы знаний и экспертные системы






Пояснительная записка
к курсовой работе на тему
«Поиск ассоциативных правил. Алгоритм Apriori.»











Выполнили:Руководитель:



















Санкт-Петербург
2007 г.
Содержание

1. Постановка задачи. ……………………………………………………………....……………………...-3-


2. Описание алгоритма......……………………………………....………………………………………...-4-


3. Описание классов. ………………….…….……………………………………………………………...-6-


4. Текст программы …………………………….……………………………………………………….......-8-


5.Пользовательский интерфейс программы….…………………………………………….....-17-


6. Тестовый пример…………………………….………………………………………………………......-18-


7. Выводы…………………………………………....……………………………………………………….…-19-


Ошибка! Закладка не определена.




1. Постановка задачи.
Используя среду разработки программных приложений Delphi 7.0 и заданные классы, написать модуль экспертной системы, реализующий алгоритмApriori. Программа должна иметь удобный пользовательский интерфейс и обеспечивать действия пользователя в отдельном окне.
Данные для анализа должны храниться в объекте класса TDMInstances.
Работа с данными, выбор переменных и их значений осуществляются в окне, отдельном от окна главной формы экспертной системы.



2. Описание алгоритма.
Алгоритм Apriori определяет частовстречающиеся наборы за несколько этапов. На i-м этапе определяются все часто встречающиеся i-элементные наборы. Каждый этап состоит из двух шагов: формирование кандидатов и подсчета поддержки кандидатов.
Рассмотрим i-й этап. На шаге формирования кандидатов алгоритм создает множество кандидатов из i-элементных наборов, чья поддержка пока не вычисляется. На шаге подсчета кандидатов алгоритм сканируетмножество транзакций, вычисляя поддержку наборов-кандидатов. После сканирования отбрасываются кандидаты, поддержка которых меньше определенного пользователем минимума, и сохраняются только часто встречающиеся i-элементные наборы. Во время 1-го этапа выбранное множество наборов кандидатов содержит все 1-элементные частые наборы. Алгоритм вычисляет их поддержку во время шага подсчета кандидатов.
Описанныйалгоритм можно записать в виде следующего псевдокода:


[pic]
Опишем обозначения используемые в алгоритме:
▪ Lk – множество k-элементных частых наборов, чья поддержка не менье заданной пользователем. Каждый член множества имеет набор упорядоченных (ij < ip, если j < p) элементов F и значение поддержки набора SuppF > Suppmin:


[pic]
▪ Ck – множество кандидатов k-элементных наборовпотенциально частых. Каждый член множества имеет набор упорядоченных (ij < ip, если j < p) элементов F и значение поддержки набора Supp.


Опишем данный алгоритм по шагам:
Шаг 1. Присвоить k=1 и выполнить отбор всех 1-элементных наборов, у которых поддержка больше минимально заданной пользователем.
Шаг 2. k = k+1.
Шаг 3. Если не удается создавать k-элементные наборы, тозавершить алгоритм, иначе выполнить следующий шаг.
Шаг 4. Создать множество k-элементных наборов кандидатов в частые наборы. Для этого необходимо объединить в k-элементные кандидаты (k-1) – элементные частые наборы. Каждый кандидат с[pic]Сk будет формироваться путем добавления к (k-1)- элементному частому набору – p элемента из другого (k-1)- элементного частого набора – q. Причем добавляется последнийэлемент набора q, который по порядку выше, чем последний элемент набора p (p.itemk-1 < q.itemk-1). При этом первые все k-2 элемента обоих наборов одинаковы (p.item1 = q.item1, p.item2 = q.item2, …,
p.itemk-2 = q.itemk-2).
Это может быть записано в виде следующего SQL-подобного запроса.


[pic]

Шаг 5. Для каждой транзакции Т из множества D выбрать...
tracking img