Strainu onLine

15th
FEB

AIM: Another Itemset Miner

Posted by Strainu | Filed under Referate, Romana

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 i În algoritmul prezentat, arborii lexicografici sunt parcurşi în adâncime. Mai exact, pentru fiecare nod n, se ia un element din tail şi se pune în head. Pentru a mări viteza parcurgerii se folosesc mai multe tehnici prezentate mai jos.
După cum am spus şi în introducere, folosirea vectorilor verticali are un efect important asupra algoritmilor de data mining. Există două metode de a păstra vectorii în memorie: ca atare (ceea ce duce la vectori rari), sau folosind diverse tehnici de compresie. În cazul AIM, autorii au hotărât să folosească vectori rari, pe care să-i comprime prin tehnica proiecţiei numai în cazul în care câştigul de spaţiu este semnificativ (peste 90%).
Seturile de diferenţe sunt o structură de date ce ţine minte diferenţele existente între un candidat şi seturile de date rezultate din el. Se păstrează alfel mult mai puţine date. Tehnica de scoatere a seturilor care nu corespund se numeşte Parent Equivalence Pruning. Ea constă în folosirea următoarei proprietăţi: dacă support(n.head) = support(n.headhα), atunci putem adăuga α la head şi să trecem direct la analiza noului set de obiecte.

AIM-F (n : node, minsupport : integer)
( 1 ) t = n.tail
( 2 ) for each α in t
( 3 ) Compute sα = support(n.headhα)
( 4 ) if (sα = support(n.head))
( 5 ) add α to the list of items removed by PEP
( 6 ) remove α from t
( 7 ) else if (sα < minsupport)
( 8 ) remove α from t
( 9 ) Sort items in t by sα in ascending order.
(10 )While t ≠ ∅
(11 ) Let α be the first item in t
(12 ) remove α from t
(13 ) n’.head = n.headhα
(14 ) n’.tail = t
(15 ) Report n’.headh{All subsets of items removed by PEP} as frequent itemsets
(16 ) AIM-F (n’)

Figura 1: AIM - pseudocod

3. Despre implementare
Implementarea preia date de intrare înformatul obişnuit (căte un set pe linie, cu elementele separate prin spaţiu), şi scoate un fişier de ieşire care are pe prima linie numărul de seturi, iar pe liniile următoare seturi frecvente plus numărul de seturi de date în care apare. Iată de exemplul rezultatul pentru Retail, pragul 26400:
(88162)
48 39 (29142)
48 (42135)
39 (50675)
Codul C++ care corespunde cu pseudocodul de mai sus este următorul:
void CDFSMiner::RecurseMine(int level, CItemset *head, SFixedCItemsetArray *tail, int tailCount, int tailStartPos, int minSupport, int &patternCount, bool useDiffset, bool firstTimeDiffset){
CItemset *newHead;
SFixedCItemsetArray *newHeads = itemsetBufferPool.Alloc();
V_BIT_ARRAY *bitArray = NULL;
CSortedIntArray *sortedSupport = sortedArrayPool.Alloc();//(tailCount);

levelInfo[level + 1].PEPItemCount = 0;
levelInfo[level + 1].PEPItems = intBufferPool.Alloc();

// Loop over the tail
for (int loopTail = tailStartPos; loopTail < tailCount; loopTail++){
CItemset *i = tail->buffer[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< countPEP += levelInfo[loop].PEPItemCount;
}
patternCount += count;

int baseLength = level + 1;
int baseLengthInc = 1;
(*frequentItemsetsFound)[baseLength]++;
for (int loop = 0; loop < countPEP; loop++){
baseLengthInc = (baseLengthInc * (countPEP - loop)) / (loop + 1);
(*frequentItemsetsFound)[baseLength + 1 + loop] += baseLengthInc;
}

levelInfo[level + 1].PEPItemCount = 0;

itemsetPool.Free(newHead);
}
sortedArrayPool.Free(sortedSupport);
itemsetBufferPool.Free(newerTail);
itemsetBufferPool.Free(newHeads);

intBufferPool.Free(levelInfo[level + 1].PEPItems);
levelInfo[level + 1].PEPItems = NULL;
}

4. Rezultatele măsuratorilor

Am efectuat o serie de teste ale implementarii algoritmului AIM pe următoarele baze de date :

ChessBază de date publică cu stări din jocul de sah- 3k tranzactii
- 76 elemente
- Dimensiunea maximă a tranzacţiei = 37ConnectBaza de date publică ce conţine stări din jocul connect 4- Densă
- 67k tranzactii
- 130 elemente
- Dimensiunea maximă a tranzacţiei = 43RetailBaza de date publică ce conţine date despre cupărăturile efectuate dintr-un supermarket din Belgia- 88k tranzacţii
- 16470 elemente
- Dimensiunea maxima a tranzactiei = 50PumsbBază de date publică ce conţine date despre un referendum- 49k tranzacţii
- 7112 elemente
- Dimensiunea maxima a tranzactiei = 71T10I4D100KBază de date generată automat de IBM Almaden Quest- 100k tranzacţii
- 988 elemente
- Dimensiunea maxima a tranzactiei = 24MushroomBaze de date publică cu informaţii despre diverse specii de ciuperci- 8k tranzacţii
- 120 elemente
- Dimensiunea maximă a tranzacţiei = 23Bazele de date sunt chiar cele folosite de autori în lucrarea lor, la care am adăugat Retail, pentru a vedea cum se descurcă algorimtul pe date corespunzătoare scenariului cel mai obişnuit de utilizare.

În figurile de mai jos am reprezentat rezultatele obţinute sub forma unor grafice ale timpului de rulare şi dimensiunii maxime a setului de rezultate în functie de suportul minim. De observar că am încercat să păstrez aceleaşi valori procentuale ale valorii de prag (30%, 40%, 50%, 60% şi 80%), dar acest lucru nu a fost posibil în cazul seturilor de date dense, unde se depăşea dimensiunea maximă a fişierului de ieşire, care era de 2GB.

Calculatorul folosit pentru testare avea un procesor AMD Mobile Sempron la 2 GHz, 1024 MB RAM şi hard-disk pe IDE la 5400 rpm. Sistemul rula SUSE Linux 10.2.

Pentru exemplificare, am pus mai jos output-ul pentru Mushroom, cu pragul de suport 2400:

5.
Concluzii
Rezultatele arată că algoritmul se comportă bine chiar şi în cazul unor baze de date mari pe maşini cu memorie suficientă. Totuşi, rezultatele sunt influenţate mult de natura seturilor de date de test – cu cât o bază de date este mai densă, cu atât valoarea de prag trebuie să fie mai mare. Din grafice se observă o scalabilitate acceptabilă a algoritmului la scaderea pragului reprezentat de suportul minim.

În cazul bazelor de date dense, cum sunt Connect şi Pumsb, valorile de prag de până la 50% inclusiv se dovedesc prea mici, programul producând un fişier de ieşire de 2GB, moment în care iese cu eroare. În schimb în cazul datelor rare, cum sunt cele de la supermarketuri (bazle de date Retail şi T10I4D100K), pragul trebuie să fie mult mai coborât. Testele mele s-au bazat pe acelaşi prag de suport, pentru a putea face o comparaţie, însă rezultatele obţinute sunt prea mici pentru a fi considerate de încredere.

În general se observă aceeaşi formă generală a graficelor – timpul de execuţie scade ceva mai abrupt la început, apoi mai lin, pe când dimensiunea maximă a seturilor frecvente scade aproximativ liniar.

Rezultatele măsurătorilor pentru pragul maxim (80% sau 90%, după caz) pentru toate fişierele de intrare, precum şi alte fişiere de ieşire şi fişierul Excel cu datele se găsesc pe CD. Din păcate nu am avut loc pentru toate rezultatele experimentale, fişierele rezultate fiind prea mari.

6. Bibliografie
1. Amos Fiat, Sagi Shporer, AIM: Another Itemset Miner, în CEUR Workshop Proceedings, 2003
2. R. Agrawal, T. Imielinski, and A. N. Swami. Mining association rules between sets of items in large databases. In SIGMOD, pages 207–216, 1993.
3. Brijs T., Swinnen G., Vanhoof K., and Wets G. (1999), The use of association rules for product assortment decisions: a case study, in: Proceedings of the Fifth International Conference on Knowledge Discovery and Data Mining, San Diego (USA), August 15-18, pp. 254-260. ISBN: 1-58113-143-7.
4. P. Shenoy, J. R. Haritsa, S. Sundarshan, G. Bhalotia, M. Bawa, and D. Shah. Turbo-charging vertical mining of large databases. In SIGMOD, 2000.