Постановка задачи. 
Поиск ассоциативных правил. 
Алгоритм 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.