Скачиваний:
29
Добавлен:
01.05.2014
Размер:
11.8 Кб
Скачать
unit AprioriItemSet;

interface

uses
ItemSet,
Instances,
FAstVector,
SysUtils,
dmmTypes,
uContainers,
math,
ContingencyTables,
doubleObject;
type

TDMAprioriItemSet = class (TDMItemSet)
public
constructor Create(totalTrans : integer);
//генерация правил для набора
function confidenceForRule(premise : TDMAprioriItemSet; consequence : TDMAprioriItemSet) : double;
function liftForRule(premise : TDMAprioriItemSet; consequence : TDMAprioriItemSet; consequenceCount : integer) : double;
function leverageForRule(premise : TDMAprioriItemSet; consequence : TDMAprioriItemSet; premiseCount : integer; consequenceCount : integer) :double;
function convictionForRule(premise : TDMAprioriItemSet; consequence : TDMAprioriItemSet; premiseCount : integer; consequenceCount : integer) : double;
function generateRules(minConfidence : double; hashtables : TDMFastVector; numItemsInSet : integer) : TDMFastVectorArray;
function subtract(toSubtract : TDMAprioriItemSet) : TDMAprioriItemSet;
destructor Destroy;override;
private
function moreComplexRules(rules : TDMFastVectorArray; numItemsInSet : integer; numItemsInConsequence : integer; minConfidence : double; hashtables : TDMFastVector) : TDMFastVectorArray;
end;

//формирование k-элементных наборов из k-1-элементных наборов
function mergeAllItemSets( itemSets : TDMFastVector; size : integer; totalTrans : integer) : TDMFastVector;
//наборы из обного элемента
function singletons(instances : TDMInstances) : TDMFastVector;

implementation

constructor TDMAprioriItemSet.Create(totalTrans : integer);
begin
inherited;
end;

function mergeAllItemSets(itemSets : TDMFastVector; size : integer; totalTrans : integer) : TDMFastVector;
var
newVector : TDMFastVector;
curResult : TDMAprioriItemSet;
numFound, k : integer;
i,j : integer;
first, second : TDMAprioriItemSet;
exitWhile : boolean;
begin
newVector := TDMFastVector.Create();
i := 0;
while ( i < itemSets.size()) do
begin
first := itemSets.elementAt(i) as TDMAprioriItemSet;
j := i+1;
while (j < itemSets.size()) do
begin
exitWhile := false;
second := itemSets.elementAt(j) as TDMAprioriItemSet;
curResult := TDMAprioriItemSet.Create(totalTrans);
SetLength(curResult.m_items, length(first.m_items));

numFound := 0;
k := 0;
while (numFound < size) do
begin
if (first.m_items[k] = second.m_items[k]) then
begin
if (first.m_items[k] <> -1) then
inc(numFound);
curResult.m_items[k] := first.m_items[k];
end
else
begin
FreeAndNil(curResult);
exitWhile := true;
break;
end;
inc(k);
end;

if exitWhile then break;

while (k < length(first.m_items)) do
begin
if ((first.m_items[k] <> -1) and (second.m_items[k] <> -1)) then
break
else
begin
if (first.m_items[k] <> -1) then
curResult.m_items[k] := first.m_items[k]
else
curResult.m_items[k] := second.m_items[k];
end;
inc(k);
end;

if (k = length(first.m_items)) then
begin
curResult.m_counter := 0;
newVector.addElement(curResult);
end;
inc(j);
end;
inc(i);
end;
result:= newVector;
end;

function TDMAprioriItemSet.confidenceForRule(premise : TDMAprioriItemSet; consequence : TDMAprioriItemSet) : double;
begin
result := consequence.m_counter/premise.m_counter;
end;

function TDMAprioriItemSet.liftForRule(premise : TDMAprioriItemSet; consequence : TDMAprioriItemSet; consequenceCount : integer) : double;
var
confidence : double;
begin
confidence := confidenceForRule(premise, consequence);
result := confidence / (consequenceCount / m_totalTransactions);
end;

function TDMAprioriItemSet.leverageForRule(premise : TDMAprioriItemSet; consequence : TDMAprioriItemSet; premiseCount : integer; consequenceCount : integer) :double;
var
coverageForItemSet : double;
expectedCoverageIfIndependent : double;
lev : double;
begin
coverageForItemSet := consequence.m_counter / m_totalTransactions;
expectedCoverageIfIndependent := (premiseCount / m_totalTransactions)
* (consequenceCount / m_totalTransactions);
lev := coverageForItemSet - expectedCoverageIfIndependent;
result := lev;
end;

function TDMAprioriItemSet.convictionForRule(premise : TDMAprioriItemSet; consequence : TDMAprioriItemSet; premiseCount : integer; consequenceCount : integer) : double;
var
num : double;
denom : double;
begin
num := premiseCount * (m_totalTransactions - consequenceCount) / m_totalTransactions;
denom := ((premiseCount - consequence.m_counter)+1);

if (num < 0) or (denom < 0) then
raise Exception.Create('convictionForRule имеет недопустимые аргументы');

result := num / denom;
end;

function TDMAprioriItemSet.subtract(toSubtract : TDMAprioriItemSet) : TDMAprioriItemSet;
var
curResult : TDMAprioriItemSet;
i : integer;
begin
curResult := TDMAprioriItemSet.Create(m_totalTransactions);

SetLength(curResult.m_items,length(m_items));

i := 0;
while (i < length(m_items)) do
begin
if (toSubtract.m_items[i] = -1) then
curResult.m_items[i] := m_items[i]
else
curResult.m_items[i] := -1;
inc(i);
end;
curResult.m_counter := 0;
result := curResult;
end;

function TDMAprioriItemSet.moreComplexRules(rules : TDMFastVectorArray; numItemsInSet : integer; numItemsInConsequence : integer; minConfidence : double; hashtables : TDMFastVector) : TDMFastVectorArray;
var
newPremise : TDMAprioriItemSet;
curResult, moreResults : TDMFastVectorArray;
newConsequences,newPremises,newConf : TDMFastVector;
enu : TDMFastVectorEnumeration;
hashtable : TStringHashtable;
current : TDMAprioriItemSet;
i : integer;
PTDMAprioriItemSet : ^TDMAprioriItemSet;
curAprioriItemSet : TDMAprioriItemSet;
begin
newPremises := TDMFastVector.Create();
newConf := TDMFastVector.Create();

if (numItemsInSet > numItemsInConsequence + 1) then
begin
hashtable := hashtables.elementAt(numItemsInSet - numItemsInConsequence - 2) as TStringHashtable;
newConsequences := mergeAllItemSets(rules[1], numItemsInConsequence - 1,
m_totalTransactions);
enu := TDMFastVectorEnumeration.Create(newConsequences);
while (enu.hasMoreElements()) do
begin
current := enu.nextElement() as TDMAprioriItemSet;
current.m_counter := m_counter;
newPremise := subtract(current);
curAprioriItemSet := hashtable.Items[newPremise.hashCode];
newPremise.m_counter := curAprioriItemSet.m_counter;
newPremises.addElement(newPremise);
newConf.addElement(TDMDoubleObject.Create(confidenceForRule(newPremise, current)));
end;
FreeandNil(enu);
SetLength(curResult,3);
curResult[0] := newPremises;
curResult[1] := newConsequences;
curResult[2] := newConf;
pruneRules(curResult, minConfidence);
moreResults := moreComplexRules(curResult, numItemsInSet,
numItemsInConsequence+1,
minConfidence, hashtables);
if (moreResults <> nil) then
begin
i := 0;
while (i < moreResults[0].size()) do
begin
curResult[0].addElement(moreResults[0].elementAt(i));
curResult[1].addElement(moreResults[1].elementAt(i));
curResult[2].addElement(moreResults[2].elementAt(i));
inc(i);
end;
end;
result := curResult;
end
else
begin
FreeandNil(newPremises);
FreeandNil(newConf);
result := nil;
end;
end;

function TDMAprioriItemSet.generateRules(minConfidence : double; hashtables : TDMFastVector; numItemsInSet : integer) : TDMFastVectorArray;
var
premises : TDMFastVector;
consequences : TDMFastVector;
conf : TDMFastVector;
rules : TDMFastVectorArray;
moreResults : TDMFAstVectorArray;
premise, consequence : TDMAprioriItemSet ;
hashtable : TStringHAshtable;
i,j : integer;
PTDMAprioriItemSet : ^TDMAprioriItemSet;
curAprioriItemSet : TDMAprioriItemSet;
begin
premises := TDMFastVector.Create();
consequences := TDMFastVector.Create();
conf := TDMFastVector.Create();
SetLEngth(rules,3);

hashtable := hashtables.elementAt(numItemsInSet - 2) as TStringHashtable;

i := 0;
while (i < length(m_items)) do
begin
if (m_items[i] <> -1) then
begin
premise := TDMAprioriItemSet.Create(m_totalTransactions);
consequence := TDMAprioriItemSet.Create(m_totalTransactions);
SetLength(premise.m_items, length(m_items));
SetLength(consequence.m_items, length(m_items));
consequence.m_counter := m_counter;

j := 0;
while (j < length(m_items)) do
begin
consequence.m_items[j] := -1;
inc(j);
end;
premise.m_items := Copy(m_items,0,length(m_items));
premise.m_items[i] := -1;

consequence.m_items[i] := m_items[i];
curAprioriItemSet := (hashtable.Items[premise.hashCode] );
premise.m_counter := curAprioriItemSet.m_counter;
premises.addElement(premise);
consequences.addElement(consequence);
conf.addElement(TDMDoubleObject.Create(confidenceForRule(premise, consequence)));
end;
inc(i);
end;
rules[0] := premises;
rules[1] := consequences;
rules[2] := conf;
pruneRules(rules, minConfidence);

moreResults := moreComplexRules(rules, numItemsInSet, 1, minConfidence,
hashtables);
if (moreResults <> nil) then
begin
i := 0;
while (i < moreResults[0].size()) do
begin
rules[0].addElement(moreResults[0].elementAt(i));
rules[1].addElement(moreResults[1].elementAt(i));
rules[2].addElement(moreResults[2].elementAt(i));
inc(i);
end;
inc(i);
end;
result := rules;
end;

function singletons(instances : TDMInstances) : TDMFastVector;
var
setOfItemSets : TDMFastVector;
current : TDMAprioriItemSet;
i,j,k : integer;
begin
setOfItemSets := TDMFastVector.Create();

i := 0;
while ( i < instances.numAttributes())do
begin
if (instances.attribute(i).isNumeric()) then
raise Exception.Create('Не поддерживаются количествекнные атрибуты!');

j := 0;
while (j < instances.attribute(i).numValues()) do
begin
current := TDMAprioriItemSet.Create(instances.numInstances());
SetLength(current.m_items,instances.numAttributes());

k := 0;
while (k < instances.numAttributes()) do
begin
current.m_items[k] := -1;
inc(k);
end;
current.m_items[i] := j;
setOfItemSets.addElement(current);
inc(j);
end;
inc(i);
end;
result := setOfItemSets;
end;

destructor TDMAprioriItemSet.Destroy;
begin
inherited destroy;
end;

end.
Соседние файлы в папке DMAssociations