Постановка задачи.
Поиск ассоциативных правил.
Алгоритм AprioriTid
Шаг 4. Создать множество k-элементных наборов кандидатов в частые наборы. Для этого необходимо объединить в k-элементные кандидаты (k-1) — элементные частые наборы. Каждый кандидат сСk будет формироваться путем добавления к (k-1) — элементному частому набору — p элемента из другого (k-1) — элементного частого набора — q. Причем добавляется последний элемент набора q, который по порядку выше, чем… Читать ещё >
Постановка задачи. Поиск ассоциативных правил. Алгоритм AprioriTid (реферат, курсовая, диплом, контрольная)
Используя среду разработки программных приложений Delphi 7.0 и заданные классы, написать модуль экспертной системы, реализующий алгоритм AprioriTid. Программа должна иметь удобный пользовательский интерфейс и обеспечивать действия пользователя в отдельном окне.
Данные для анализа должны храниться в объекте класса TDMInstances.
Работа с данными, выбор переменных и их значений осуществляются в окне, отдельном от окна главной формы экспертной системы.
Описание алгоритма
Алгоритм AprioriTid определяет часто встречающиеся наборы за несколько этапов. На i-м этапе определяются все часто встречающиеся i-элементные наборы. Каждый этап состоит из двух шагов: формирование кандидатов и подсчета поддержки кандидатов.
Рассмотрим i-й этап. На шаге формирования кандидатов алгоритм создает множество кандидатов из i-элементных наборов, чья поддержка пока не вычисляется. На шаге подсчета кандидатов алгоритм сканирует множество транзакций, вычисляя поддержку наборов-кандидатов. После сканирования отбрасываются кандидаты, поддержка которых меньше определенного пользователем минимума, и сохраняются только часто встречающиеся i-элементные наборы. Во время 1-го этапа выбранное множество наборов кандидатов содержит все 1-элементные частые наборы. Алгоритм вычисляет их поддержку во время шага подсчета кандидатов.
Описанный алгоритм можно записать в виде следующего псевдокода:
алгоритм aprioritid программа.
Опишем обозначения используемые в алгоритме:
§ Lk — множество k-элементных частых наборов, чья поддержка не менье заданной пользователем. Каждый член множества имеет набор упорядоченных (ij < ip, если j Suppmin:
§ Ck — множество кандидатов k-элементных наборов потенциально частых. Каждый член множества имеет набор упорядоченных (ij < ip, если j < p) элементов F и значение поддержки набора Supp.
Опишем данный алгоритм по шагам:
Шаг 1. Присвоить k=1 и выполнить отбор всех 1-элементных наборов, у которых поддержка больше минимально заданной пользователем.
Шаг 2. k = k+1.
Шаг 3. Если не удается создавать k-элементные наборы, то завершить алгоритм, иначе выполнить следующий шаг.
Шаг 4. Создать множество k-элементных наборов кандидатов в частые наборы. Для этого необходимо объединить в k-элементные кандидаты (k-1) — элементные частые наборы. Каждый кандидат сС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-подобного запроса.
Шаг 5. Для каждой транзакции Т из множества D выбрать кандидатов С1 из множества Сk, присутствующих в транзакции Т. Для каждого набора из построенного множества Сk удалить набор, если хотя бы одно из его (k-1) множеств не является часто встречающимся, т. е. отсутствует во множестве Lk-1. Это можно записать в виде следующего псевдокода:
Шаг 6. Для каждого кандидата из множества Ck увеличить значение поддержки на единицу.
Шаг 7. Выбрать только кандидатов Lk из множества Сk, у которых значение поддержки больше заданной пользователем Suppmin. Вернуться к шагу 2.
Результатом работы алгоритма является объединение всех множеств Lk для всех k.