Strainu onLine

Descriere: Scopul acestui referat este prezentarea algoritmului Another Itemset Miner pentru determinarea cosurilor de produse frecvente, realizat de Amos Fiat şi Sagi Shporer.
Materie: Evaluarea Performantelor, Complemente de Informatica
Referat făcut la facultate.

Download

Mai jos aveţi la dispoziţie o variantă text a referatului. Vă rugăm să reţineţi că această variantă nu are nici un fel de formatare sau poze. Unele caractere pot să nu fie arătate corect. Pentru varianta integrală vă rugăm să downloadaţi referatul.

AIM: Another Itemset Miner

Proiect Complemente de Informatică
1.
Introducere

Scopul acestui referat este prezentarea algoritmului Another Itemset Miner pentru determinarea cosurilor de produse frecvente (problema FSC), realizat de Amos Fiat şi Sagi Shporer[1].
Autorii au plecat de la mai mulţi algoritmi care îmbunătăţesc algoritmul Apriori şi au preluat mai multe idei pe care le-au combinat pentru a realiza un algoritm mai rapid. Printre ideile preluate se numără:
• Vectori de biţi verticali pentru a păstra seturile de date. A fost demonstrat experimental[4] că acestă metodă oferă performanţe bune.
• Proiecţia este o tehnică de a reduce dimensiune vectorilor de biţi păstrând numai informaţia relevantă pentru partea analizată în momentul respectiv
• Seturi de diferenţe – nu se pstrează tot tidsetul, ci doar diferenţele care apar în el (economie de memorie)
• Reordonarea dinamică permite schimbarea ordinii în care este parcurs spaţiul posibilelor soluţii în aşa fel încât tuplurile infrecvente să fie eliminate cât mai rapid
• Eliminarea seturilor echivalente, care nu aduc informaţii noi
Deşi unele din aceste idei mai fuseseră combinate şi în alţi algoritmi, altele erau folosite pentru prima dată împreună.
În anul următor, 2004, autorii au prezentat o versiune îmbunătăţită a algoritmului, care reduce şi mai mult timpul de execuţie.
2. Algoritmul Another Itemset Miner (AIM)
Algoritmul AIM în sine este foarte simplu. Pseudocodul de nivel înalt este prezentat în Figura 1. El se bazează însă pe mai multe sub-programe care vor fi prezentate în continuare.
Un arbore lexicografic este un arbore în care fiecare nod este format din 2 părţi: head, care conţine fix setul de obiecte reprezentat de nivelul curent (cu un număr de elemente egal cu nivelul la care se află nodul) şi tail care conţine elementele rămase. Condiţia este ca ibuffer[loopTail];
int support = 0;

// 1-itemset
if (head == NULL){
bitArray = i->transactionBitMask->Clone();
support = bitArray->CountElements();
}
else{

// 2-itemsets matrix – check if 2-itemset is frequent
if ((level == 1)&&(p2ItemsMatrix != NULL)){
int sup;
if (head->lastItem > i->lastItem)
sup = p2ItemsMatrix[head->lastItem][i->lastItem];
else
sup = p2ItemsMatrix[i->lastItem][head->lastItem];

if (minSupport > sup)
continue;
}

// For 2-itemsets don’t use diffsets
if (useDiffset == false){
if ((float)transactionCount * 0.10 > head->support )
// Simple bit vector AND
bitArray = i->transactionBitMask->And(head-> transactionBitMask);
else
// Projection
bitArray = i->transactionBitMask->Project(head->transactionBitMask);

support = bitArray->CountElements();
}
// Starting to use diffsets
else if (firstTimeDiffset == true){
bitArray = head->transactionBitMask->AndNot(i->transactionBitMask);
support = head->support – bitArray->CountElements();
}
else{ // diffsets already in use
bitArray = i->transactionBitMask->AndNot(head->transactionBitMask);
support = head->support – bitArray->CountElements();
}

// PEP
if (support == head->support){
levelInfo[level].PEPItems->buffer[levelInfo[level].PEPItemCount] = i->lastItem;
levelInfo[level].PEPItemCount++;

sparseBitArrayPool.Free(bitArray);
continue;
}
}

// New FI found, add to list
if (support > minSupport){
newHead = itemsetPool.Alloc();
newHead->support = support;
newHead->transactionBitMask = bitArray;
newHead->lastItem = i->lastItem;

sortedSupport->Add(support, loopTail);
newHeads->buffer[loopTail] = newHead;
}
else
sparseBitArrayPool.Free(bitArray);
}

// Resort the tail – Dynamic reordering
sortedSupport->Sort();
SFixedCItemsetArray *newerTail = itemsetBufferPool.Alloc();
for (int loop = 0; loop < sortedSupport->Count; loop++)
newerTail->buffer[loop] = newHeads->buffer[(*sortedSupport)[loop]];//tail->buffer[sortedSupport[loop]];

// Init diffset selection mode
bool nextUseDiffset, nextFirstTimeDiffset;
float baseSupport;
if (head == NULL)
baseSupport = (float)this->transactionCount;
else
baseSupport = (float)head->support;

for (int loopHeads = 0; loopHeads < sortedSupport->Count; loopHeads++){
newHead = newHeads->buffer[(*sortedSupport)[loopHeads]];
levelInfo[level].item = newHead->lastItem;

// Check if diffsets should be used
nextUseDiffset = useDiffset;
nextFirstTimeDiffset = firstTimeDiffset;

if (firstTimeDiffset == true)
nextFirstTimeDiffset = false;

if (useDiffset == false){
if ((float)newHead->support / baseSupport > 0.5){
nextUseDiffset = true;
nextFirstTimeDiffset = true;
}
}

// Recurse only if there are items in the tail
if (loopHeads < sortedSupport->Count – 1)
RecurseMine(level + 1, newHead, newerTail, sortedSupport->Count, loopHeads + 1, minSupport, patternCount, nextUseDiffset, nextFirstTimeDiffset);

// Print frequent itemsets found
if (out != NULL)
CreateFI(level, newHead->support);

// Count frequent itemsets
int count = 1;
int countPEP = 0;
for (int loop = 1; loop < level + 2; loop++){ count *= 1<