Поиск ассоциативных правил. Алгоритм AprioriTid

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Государственное образовательное учреждение

высшего профессионального образования

«Омский государственный технический университет»

Кафедра «Автоматизированные системы обработки информации и управления»

Курсовой проект

на тему

«Поиск ассоциативных правил. Алгоритм AprioriTid»

по дисциплине: «Компьютерные системы поддержки принятия решений»

Сургут 2013



Постановка задачи

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

Данные для анализа должны храниться в объекте класса TDMInstances.

Работа с данными, выбор переменных и их значений осуществляются в окне, отдельном от окна главной формы экспертной системы.

Описание алгоритма

Алгоритм AprioriTid определяет часто встречающиеся наборы за несколько этапов. На i-м этапе определяются все часто встречающиеся i-элементные наборы. Каждый этап состоит из двух шагов: формирование кандидатов и подсчета поддержки кандидатов.

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

Описанный алгоритм можно записать в виде следующего псевдокода:



Опишем обозначения используемые в алгоритме:

§ Lk - множество k-элементных частых наборов, чья поддержка не менье заданной пользователем. Каждый член множества имеет набор упорядоченных (ij < ip, если j < p) элементов F и значение поддержки набора SuppF > 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.

Описание классов

unit PredictiveAprioriTid

const

Имя атрибута	Описание
m_numRandRules	количество правил для вычисления априорной оценки
m_numIntervals	количество интервалов для вычисления априорной оценки

class TDMPredictiveAprioriTid

Секция protected

Имя атрибута	Тип атрибута	Описание
m_premiseCount	integer	минимальная поддержка
m_numRules	integer	требуемое количество правил
m_Ls	TDMFastVector	наборы
m_hashtables	TDMFastVector	теже наборы в хэш таблице
m_allTheRules	TDMFastVectorArray	набор правил
m_instances	TDMInstances	вектора на основе которых генерируются правила
m_priors	TStringHashtable	хэш таблица с априорными вероятностями
m_midPoints	DArray	середина интервалов для априорной оценки
m_expectation	double	требуемое значение точности для 'выходного' правила
m_best	TArrayList	n лучших правил
m_bestChanged	boolean	изменился ли набор из n лучших правил
m_count	integer
m_priorEstimator	TDMPriorEstimation	априорная оценка



Секция public

Методы	Имя метода	Используемые значения	Описание	Возвращаемое значение
constructor	Create	i1:integer	создание объекта класса
procedure	buildModel	instances : TDMInstances	Построение дерева хеширования
function	toStrings	instances: TDMInstances; Podd : real; Toch : real	вывод на экран результата работы алгоритма	TStrings
procedure	setNumRules	v : integer	задает максимальное количество правил для вывода
procedure	resetOptions	i1:integer	задает размер создаваемой модели
destructor	Destroy		деструктор класса

Секция private

Методы	Имя метода	Используемые значения	Описание
procedure	findLargeItemSets	-	поиск наборов
procedure	findRulesQuickly	-	поиск правил

Текст программы

unit PredictiveAprioriTid;

interface

uses

Classes, FastVector, Instances, uContainers, dmmTypes, PriorEstimation,

SysUtils, ItemSet, dmmConstants, RuleGeneration, RuleItem, DoubleObject,

uConsts, associator, dmm, Windows;

const

//количество правил для вычисления априорной оценки

m_numRandRules = 100;

//количество интервалов для вычисления априорной оценки

m_numIntervals = 10;

type TDMPredictiveApriori = class (TDMAssociator)

protected

//минимальная поддержка

m_premiseCount : integer;

//требуемое количество правил

m_numRules : integer;

//наборы

m_Ls : TDMFastVector;

//теже наборы в хэш таблице

m_hashtables : TDMFastVector;

//набор правил

m_allTheRules : TDMFastVectorArray;

//вектора на основе которых генерируются правила

m_instances : TDMInstances ;

//хэш таблица с априорными вероятностями

m_priors : TStringHashtable ;

//середина интервалов для оаприорной оценки

m_midPoints : DArray;

//требуемое значение точности для 'выходного' правила

m_expectation : double;

//n лучших правил

m_best : TArrayList;

//изменился ли набор из n лучших правил

m_bestChanged : boolean;

m_count : integer;

//априорная оценка

m_priorEstimator : TDMPriorEstimation;

public

//создание объекта класса TDMPredictiveApriori

constructor Create(i1:integer);

//построение дерева хеширования

procedure buildModel(instances : TDMInstances ); override;

//вывод на экран результата работы алгоритма

function toStrings(instances : TDMInstances; Podd : real; Toch : real; number : integer) : TStrings;

procedure setNumRules(v : integer);

procedure resetOptions(i1:integer);

destructor Destroy;override;

private

procedure findLargeItemSets(index : integer);

procedure findRulesQuickly();

end;

implementation

constructor TDMPredictiveApriori.Create(i1:integer);

begin

m_Ls:=nil;

m_hashtables:=nil;

m_allTheRules := nil;

m_instances:=nil;

m_priors:=nil ;

m_midPoints :=nil;

m_best:=nil;

m_best:=nil;

resetOptions(i1);

end;

procedure TDMPredictiveApriori.resetOptions(i1:integer);

begin

// m_numRules := i1;

m_numRules := 1000;

m_premiseCount := 1;

m_best := TArrayList.Create(m_numRules-5);

m_bestChanged := false;

m_expectation := 0;

m_count := 1;

end;

procedure TDMPredictiveApriori.findLargeItemSets(index : integer);

var

kMinusOneSets, kSets : TDMFastVector;

hashtable : TStringHashtable;

currentItemSets : TDMFastVector;

i,j : integer;

begin

kSets := TDMFastVector.Create();

i := 0;

//наборы длины 1

if(index = 1) then

begin

kSets := ItemSet.getSingletons(m_instances);

ItemSet.upDateCounters(kSets, m_instances);

kSets := ItemSet.deleteItemSets(kSets, m_premiseCount,IMAX_VALUE);

if (kSets.size() = 0) then

begin

FreeAndNil(kSets);

exit;

end;

m_Ls.addElement(kSets);

end;

//длина > 1

if(index >1) then

begin

if(m_Ls.size() > 0) then

kSets := m_Ls.lastElement() as TDMFastVector;

m_Ls.removeAllElements();

i := index-2;

kMinusOneSets := kSets;

kSets := ItemSet.mergeAllItemSets(kMinusOneSets, i, m_instances.numInstances());

hashtable := ItemSet.getHashtable(kMinusOneSets, kMinusOneSets.size());

kMinusOneSets.elementMemoryManagement(false);

FreeAndNil(kMinusOneSets);

m_hashtables.addElement(hashtable);

kSets := ItemSet.pruneItemSets(kSets, hashtable);

ItemSet.upDateCounters(kSets, m_instances);

kSets := ItemSet.deleteItemSets(kSets, m_premiseCount,IMAX_VALUE);

if(kSets.size() = 0) then

begin

FreeAnDNil(kSets);

exit;

end;

m_Ls.addElement(kSets);

end;

end;

procedure TDMPredictiveApriori.findRulesQuickly();

var

rules : TDMFastVectorArray;

currentItemSet : TDMRuleGeneration;

j : integer;

currentItemSets : TDMFastVector;

enumItemSets : TDMFastVectorEnumeration;

bestFirst : TDMRuleItem;

PTDMRuleItem : ^TDMRuleItem;

plist : PPointerItemList;

begin

j := 0;

while (j < m_Ls.size()) do

begin

currentItemSets := m_Ls.elementAt(j) as TDMFastVector;

enumItemSets := TDMFastVectorEnumeration.Create(currentItemSets);

while (enumItemSets.hasMoreElements()) do

begin

if (terminated) then

begin

ExitThread(1);

destroy;

end;

currentItemSet := TDMRuleGeneration.Create(enumItemSets.nextElement()as TDMItemSet);

m_best := currentItemSet.generateRules(m_numRules, m_midPoints,m_priors,m_expectation,

m_instances,m_best,m_count);

m_count := currentItemSet.m_count;

if(not m_bestChanged) and (currentItemSet.m_change) then

m_bestChanged := true;

if(m_best.Count > 0) then

begin

plist := m_best.ItemList;

bestFirst:= plist^[0];

m_expectation := (bestFirst).accuracy();

end

else m_expectation := 0;

FreeAndNil(currentItemSet);

end;

FreeAndNil(enumItemSets);

inc(j);

end;

end;

procedure TDMPredictiveApriori.buildModel(instances : TDMInstances );

var

temp,exactNumber : integer;

i,k : integer;

PTDMRuleItem : ^TDMRuleItem;

lastBest : TDMRuleItem;

kSets : TDMFastVector;

plist : PPointerItemList;

begin

temp := m_premiseCount;

exactNumber := m_numRules-5;

if (instances.checkForStringAttributes()) then

raise Exception.Create('Количественные аттрибуты не поддерживаются');

m_instances := TDMInstances.Create(instances);

m_instances.setClassIndex(m_instances.numAttributes()-1);

//априорная оценка

m_priorEstimator := TDMPriorEstimation.Create(m_instances,m_numRandRules,m_numIntervals,false);

m_priors := m_priorEstimator.estimatePrior();

m_midPoints := m_priorEstimator.getMidPoints();

m_Ls := TDMFastVector.Create();

m_hashtables := TDMFastVector.Create();

i := 1;

while (i < m_instances.numAttributes()) do

begin

m_bestChanged := false;

if (terminated) then

begin

ExitThread(1);

destroy;

end;

// поиск наборов

findLargeItemSets(i);

// поиск правил

findRulesQuickly();

if(m_bestChanged) then

begin

temp := m_premiseCount;

while(RuleGeneration.expectation(m_premiseCount, m_premiseCount,m_midPoints,m_priors) <= m_expectation) do

begin

inc(m_premiseCount);

if(m_premiseCount > m_instances.numInstances()) then

break;

end;

end;

if(m_premiseCount > m_instances.numInstances()) then

begin

SetLength(m_allTheRules,3);

m_allTheRules[0] := TDMFastVector.Create();

m_allTheRules[1] := TDMFastVector.Create();

m_allTheRules[2] := TDMFastVector.Create();

k := 0;

while(m_best.count>0) and (exactNumber > 0) do

begin

plist := m_best.itemList;

PTDMRuleItem := plist^[m_best.Count-1];

lastBest := PTDMRuleItem^;

m_allTheRules[0].insertElementAt(lastBest.premise()as TDMItemSet,k);

m_allTheRules[1].insertElementAt(lastBest.consequence() as TDMItemSet,k);

m_allTheRules[2].insertElementAt(TDMDoubleObject.Create(lastBest.accuracy()),k);

m_best.removeAt(m_best.count-1);

inc(k);

dec(exactNumber);

lastBest.OwnValuesCons := false;

FreeAndNil(lastBest);

end;

exit;

end;

if(temp <> m_premiseCount) and (m_Ls.size() > 0) then

begin

kSets := m_Ls.lastElement() as TDMFastVector;

m_Ls.removeElementAt(m_Ls.size()-1);

kSets := ItemSet.deleteItemSets(kSets, m_premiseCount,IMAX_VALUE);

m_Ls.addElement(kSets);

end;

inc(i);

end;

SetLength(m_allTheRules,3);

m_allTheRules[0] := TDMFastVector.Create();

m_allTheRules[1] := TDMFastVector.Create();

m_allTheRules[2] := TDMFastVector.Create();

k := 0;

while(m_best.count>0) and (exactNumber > 0) do

begin

plist := m_best.itemList;

lastBest:= plist^[m_best.Count-1];

m_allTheRules[0].insertElementAt(lastBest.premise() as TDMItemSet,k);

m_allTheRules[1].insertElementAt(lastBest.consequence() as TDMItemSet,k);

m_allTheRules[2].insertElementAt(TDMDoubleObject.Create(lastBest.accuracy()),k);

m_best.removeAt(m_best.count-1);

inc(k);

dec(exactNumber);

lastBest.OwnValuesCons := false;

FreeAndNil(lastBest);

end;

end;

function TDMPredictiveApriori.toStrings(instances : TDMInstances;

Podd : real; Toch : real;

number : integer) : TStrings;

var

strtext : AnsiString;

text : TStrings;

i : integer;

tochn : AnsiString;

podder : String;

TochnReal : real;

PodderReal : real;

val : integer;

begin

text := TStringList.Create;

text.Clear;

if (m_allTheRules[0].size() = 0) then

begin

text.Add('наборы не найдены');

result:=text;

exit;

end;

text.Add(' Apriori');

text.Add('==========');

i := 0;

val := 1;

while ((i < m_allTheRules[0].size()) and (val<=number)) do

begin

Str((((m_allTheRules[1].elementAt(i)) as TDMItemSet).m_counter

/instances.numInstances) : 4 : 5, podder);

PodderReal:=(((m_allTheRules[1].elementAt(i)) as TDMItemSet).m_counter

/instances.numInstances);

Str(((m_allTheRules[2].elementAt(i) as TDMDoubleObject).doubleValue) :4 : 4, tochn);

TochnReal:=((m_allTheRules[2].elementAt(i) as TDMDoubleObject).doubleValue);

if ((TochnReal >= Toch) and (PodderReal >= Podd)) then

begin

strtext:='';

strtext := IntToStr(val)+')' + ' . ' + ((m_allTheRules[0].elementAt(i)) as TDMItemSet).

toString(m_instances) + ' ==> ' + ((m_allTheRules[1].elementAt(i)) as TDMItemSet).

toString(m_instances) +' точность:(';

text.Add(strtext + tochn+')');

text.Add(' поддержка ' + podder);

inc(val);

end;

inc(i);

end;

result := text;

end;

procedure TDMPredictiveApriori.setNumRules(v : integer);

begin

m_numRules := v+5;

end;

destructor TDMPredictiveApriori.Destroy;

var i,j :integer;

first :TDMItemSet;

curItemSets : TDMFastVector;

curItemSetsHashtables : TStringHashtable;

begin

if(m_Ls <> nil) then

begin

j := 0;

while (j < m_Ls.size()) do

begin

curItemSets := m_Ls.elementAt(j) as TDMFastVector;

curItemSets.removeAllElements();

inc(j);

end;

m_Ls.removeAllElements();

m_Ls := nil;

end;

if(m_hashtables <> nil) then

begin

j := 0;

while (j < m_hashtables.size()) do

begin

curItemSetsHashtables := m_hashtables.elementAt(j) as TStringHashtable;

curItemSetsHashtables.OwnValues := true;

FreeAndNil(curItemSetsHashtables);

inc(j);

end;

m_hashtables.removeAllElements();

m_hashtables := nil;

end;

FreeAndNil(m_instances);

//удаление правил

if(length(m_allTheRules)<>0)then

begin

for i:=0 to m_allTheRules[0].size - 1 do

begin

first := m_allTheRules[0].elementAt(i) as TDMItemSet;

first.OwnValues := true;

end;

m_allTheRules[0].removeAndClearAllElements();

m_allTheRules[1].removeAndClearAllElements();

m_allTheRules[2].removeAndClearAllElements();

FreeandNil(m_allTheRules[0]);

FreeandNil(m_allTheRules[1]);

FreeandNil(m_allTheRules[2]);

setlength(m_allTheRules,0);

end;

m_priors.OwnValues:=true;

FreeAndNil(m_priors);

FreeAndNil(m_best);

FreeAndNil(m_priorEstimator);

m_midPoints :=nil;

end;

end.

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

Все свои действия пользователь выполняет в окне, показанном на рис. 1.



Рис.1

Пользователь задает минимальные значения поддержки и достоверности, а также количество лучших правил. Программа выводит все правила, поддержка и достоверность которых больше заданных пользователем. Количество выводимых правил может быть равным или меньшим заданного при запуске алгоритма. Лучшими считаются правила, с наибольшим значением достоверности.

После нажатия кнопки «Начало работы» происходит обработка введенных данных. В итоге получается набор правил, которые в специально предназначенном для этого поле.

Для сохранения данных имеется кнопка «Сохранить».

Для завершения работы с алгоритмом специально предусмотрена кнопка «Выход».

объект класс алгоритм правило

Тестовый пример

Для теста программы загрузим файл

В этом файле имеются следующие поля:

- возраст

- диагноз

- наличие астигматизма

- эффект от линз

- вид линз

Данные для выборки:

Количество лучших правил - 10

Минимальная поддержка - 0,2

Минимальная достоверность - 0,3

Результат работы алгоритма:

PredictiveAprioriTid

===================

1) . tear-prod-rate=reduced 12 ==> contact-lenses=none 12 точность:(0.9452)

поддержка 0.50000

2) . contact-lenses=soft 5 ==> astigmatism=no tear-prod-rate=normal 5 точность:(0.9004)

поддержка 0.20833

3) . spectacle-prescrip=myope contact-lenses=none 7 ==> tear-prod-rate=reduced 6 точность:(0.7984)

поддержка 0.25000

4) . astigmatism=no contact-lenses=none 7 ==> tear-prod-rate=reduced 6 точность:(0.7984)

поддержка 0.25000

5) . spectacle-prescrip=hypermetrope astigmatism=yes 6 ==> contact-lenses=none 5 точность:(0.7468)

поддержка 0.20833

6) . astigmatism=no tear-prod-rate=normal 6 ==> contact-lenses=soft 5 точность:(0.7468)

поддержка 0.20833

7) . contact-lenses=none 15 ==> tear-prod-rate=reduced 12 точность:(0.7303)

поддержка 0.50000

8) . age=presbyopic 8 ==> contact-lenses=none 6 точность:(0.6306)

поддержка 0.25000

9) . spectacle-prescrip=hypermetrope 12 ==> contact-lenses=none 8 точность:(0.5641)

поддержка 0.33333

10) . astigmatism=yes 12 ==> contact-lenses=none 8 точность:(0.5641)

поддержка 0.33333



Вывод

В результате выполнения курсовой работы был получен модуль, выполняющий поиск ассоциативных правил по алгоритму AprioriTid. Программа имеет простой и понятный пользовательский интерфейс и корректно выполняет необходимые действия.

Данный модуль взаимодействует с ядром следующим образом: при запуске ядра в модуль загружаются данные типа Instances, с которыми впоследствии и работает наша программа.

Кроме того, в ходе выполнения курсовой работы нами были получены навыки объектно-ориентированного программирования в среде Dephi 7.

Размещено на Allbest.ur

...