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

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

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

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

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

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

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

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

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

Сургут 2013

Содержание

• 1. Постановка задачи
• 2. Описание алгоритма
• 3. Описание классов
• 4. Текст программы
• 5. Пользовательский интерфейс программы
• 6. Тестовый пример
• Вывод
• 1. Постановка задачи
• Используя среду разработки программных приложений Delphi 7.0 и заданные классы, написать модуль экспертной системы, реализующий алгоритм AprioriTid. Программа должна иметь удобный пользовательский интерфейс и обеспечивать действия пользователя в отдельном окне.
• Данные для анализа должны храниться в объекте класса TDMInstances.
• Работа с данными, выбор переменных и их значений осуществляются в окне, отдельном от окна главной формы экспертной системы.
• 2. Описание алгоритма
• Алгоритм AprioriTid определяет часто встречающиеся наборы за несколько этапов. На i-м этапе определяются все часто встречающиеся i-элементные наборы. Каждый этап состоит из двух шагов: формирование кандидатов и подсчета поддержки кандидатов.
• Рассмотрим i-й этап. На шаге формирования кандидатов алгоритм создает множество кандидатов из i-элементных наборов, чья поддержка пока не вычисляется. На шаге подсчета кандидатов алгоритм сканирует множество транзакций, вычисляя поддержку наборов-кандидатов. После сканирования отбрасываются кандидаты, поддержка которых меньше определенного пользователем минимума, и сохраняются только часто встречающиеся i-элементные наборы. Во время 1-го этапа выбранное множество наборов кандидатов содержит все 1-элементные частые наборы. Алгоритм вычисляет их поддержку во время шага подсчета кандидатов.
• Описанный алгоритм можно записать в виде следующего псевдокода:
• алгоритм aprioritid программа

• Опишем обозначения используемые в алгоритме:
• § 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.
• 3. Описание классов
• 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	-	поиск правил

• 4. Текст программы
• 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.
• 5. Пользовательский интерфейс программы
• Все свои действия пользователь выполняет в окне, показанном на рис.1.

• Рис.1.
• Пользователь задает минимальные значения поддержки и достоверности, а также количество лучших правил. Программа выводит все правила, поддержка и достоверность которых больше заданных пользователем. Количество выводимых правил может быть равным или меньшим заданного при запуске алгоритма. Лучшими считаются правила, с наибольшим значением достоверности.
• После нажатия кнопки «Начало работы» происходит обработка введенных данных. В итоге получается набор правил, которые в специально предназначенном для этого поле.
• Для сохранения данных имеется кнопка «Сохранить».
• Для завершения работы с алгоритмом специально предусмотрена кнопка «Выход».
• 6. Тестовый пример
• Для теста программы загрузим файл
• В этом файле имеются следующие поля:
• - возраст
• - диагноз
• - наличие астигматизма
• - эффект от линз
• - вид линз
• Данные для выборки:
• Количество лучших правил - 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.ru
...