Identificarea Sabloanelor Frecvente Automatica
CUPRINS
1. Introducere in data mining 2
2. Despre identificarea sabloanelor frecvente 7
3. Descriere problemei 11
4. Baze de date ce contin tranzactii 14
5. Spatiul de cautare 16
6. Structuri de date 18
6.1 Hash-tree 18
6.2 Trie 19
7. Algoritmul Apriori 21
7.1 Itemset Mining 21
7.2 Identificarea regulilor de asociere 23
7.3 Optimizari 25
7.3.1 AprioriTid, AprioriHybrid 25
7.3.2 DHP 26
8. Algoritmul DIC (Dynamic Intemset Counting) 28
9. O comparatie intre algoritmii Eclat si FP-growth 34
9.1 Definirea problemei 34
9.2 Eclat vs. FP-growth 36
9.3 Eclat 37
9.4 FP-growth 38
9.5 Medic 42
10. Implementarea algoritmului Apriori 44
11. Implementarea algoritmului DIC 51
12. Implementarea algoritmului Eclat 56
13. Rularea aplicatiei 58
14. Fisier cu rezultate 59
15. Aspecte experimentale 62
16. Bibliografie 65
Anexa A – Surse 66
1. Introducere Data Mining
Data mining poate produce rezultate remarcabile pentru aproape orice organizatie care colecteaza date de la proprii clienti, de la piete comerciale sau produse . Descoperind tipare ascunse si relatii intre date, data mining permite utilizatorilor sa obtina rezultate excelente din datele colectate in baze de date mari .
Pentru a descoperi sabloane ascunse in date, trebuie sa construim un model constand in variabile independente(ex: venit, casatorit/necasatorit) care pot fi folosite pentru a determina variabile dependente(ex: riscul creditului). A construi un model data mining inseamna a identifica variabile independente relevante si minimiza erorile predictive. Pentru a identifica un model care are cea mai mica eroare si care este cel mai bun predictor ar putea solicita construirea a sute de modele pentru a alege pe cel mai bun.
Din fericire, am atins un prag al dezvoltarii computationale, ca capacitatii de inmagazinare a informatiei si datelor si costuri care ne permit sa adunam si sa analizam cantitati insemnate de date.Cat timp probleme de date mining apar la birou sau la un simpla legatura client-server, multe probleme cer un produs data mining scalabil
Literal, scalabilitate inseamna ca un sistem cat creste, performanta se imbunatateste corespunzator. Pentru data mining , scalabilitatea inseamna ca folosind avantajul de a lucra in paralel unui sistem care manageriaza o baza de date si procesoarele aditionale, poti rezolva o clasa mare de probleme fara a fi nevoit sa schimbi mediul de jos de data mining. Se poate lucra cu mai multe date, construi mai multe modele si se poate imbunatati acuratetea lor prin simpla adaugare de procesoare aditionale. Ideal ar fi ca scalabilitatea sa fie liniara sau mai buna. De exemplu, daca se dubleaza numarul de procesoare intr-un sistem paralel , poti construi de 2 ori mai multe modele in acelasi timp sau acelasi numar de modele intr-un timp redus la jumatate. Data mining este un instrument si nu un magician. Nu va sta in baza de date sa vada ce se intampla si te va atentiona cand vede un tipar interesant. Nu elimina necesitatea de a-ti cunoaste afacerea, de a intelege datele sau metodele analitice. Data mining ajuta analistii prin indentificarea unor tipare si relatii intre date, dar nu iti spune valoarea tiparelor pentru organizatie. Pe de alta parte, tiparele descoperite de data mining trebuiesc verificate in realitate.
Primul si cel mai simplu pas in data mining este descrierea datelor – a rezuma calitatile ei statistice (cum ar fi medii si abateri standard), a le observa utilizand grafice si a cauta potentiale legaturi importante printre variabile (cum ar fi valori care apar des impreuna). Colectarea,studiul si selectia datele corecte prezinta o importanta cruciala.
Dar descrierea datelor nu poate sa genereze un plan de una singura. Trebuie construit un model predictiv bazat pe tiparele create pe baza rezultatelor cunoscute, apoi trebuie testat modelul rezultat in alte conditii decat datele initiale. Un bun model nu ar trebui sa fie niciodata confruntat cu realitatea (se stie ca o harta a drumurilor nu ofera o reprezantare perfecta a drumurilor respective), dar poate fi un ajutor important pentru a intelege afacerea respectiva.
Ultimul pas este sa verificam empiric acel model. De exemplu, dintr-o baza de date de clienti care au raspuns deja unei oferte, s-a construit un model care prezice ce categorii de clienti ar putea sa raspunda aceleiasi oferte. Dar putem fi siguri de aceasta predictie? Pentru aceasta, trimitem un e-mail unei portiuni a listei de clienti presupusa ca va raspunde ofertei si vedem care sunt raspunsurile.
In principiu , motivul alegerii scalabilitatii este de a fi capabil sa construiesti un model data mining bun cat mai repede cu putinta. Aceasta ofera 2 beneficii.
Primul , este de apreciat faptul de a putea desfasura si folosi un model cat mai repede cu putinta. In al doilea exemplu de mai jos, gasirea unui model bun va duce la cresterea platii finale inclusiv a notei de plata. Vanzatorul ce foloseste credit cardul nu doreste sa lase multe facturi sa treaca fara a folosi rezultatele data mining aspura datelor din credit carduri.
Al doilea , intoarcere de mai multe ori produce modele mai bune. Dupa cum vom vedea, cautarea in baze de date foarte mari si construirea de modele complexe solicita o baza hardware serioasa ca si pentru a o putea testa , valida si a extrage exemple. Daca analistul trebuie sa astepte ore sau nopti pentru un model pentru a putea lucra, atunci efortul lor o sa fie foarte mare comparativ cu cazul cand ar putea obtine modelul calificat in cateva minute. Timpul folosit pentru a astepta rezultate ar putea fi folosit pentru a gasi care model este cel mai bun si ofera solutia cea mai viabila.
De exemplu, daca in cateva minute un analist poate crea un grup de modele si sa analizeze grafic activitatea lor, atunci ei pot alege dintr-un numar foarte mare de modele posibile. Insa daca sunt nevoiti sa astepte “nopti si zile” pentru fiecare model in parte, vor lua masuri de a reduce numarul de modele investigate, cum ar fi studierea unor baze de date mici si includerea unor coloane putine. Nesurprinzator, rezultatele lor vor fi diferite si probabil nefolositoare ( sau folositoare intr-o mica masura).
Construirea unui model este in stransa legatura cu puterea sistemului pe care lucreaza. Modelul cere o putere substantiala si o performanta ridicata. Nimic nu e mai folositor decat un sistem puternic si nimic nu influenteaza mai mult munca analisului decat un sistem inadecvat.
Exemplu: Departamentul de marketing al unei companii de cercetare decide sa investigheze posibilitatea folosirii tehnicilor data mining pe cateva baze de date ale lor. Au luat ceva software data mining si au cerut catorva statisticieni in cercetare sa-i asiste ca analisti experti. Statisticienii au statii de lucru care sunt excelente pentru analiza pe care o fac de obicei pe baze de date modeste.
Initial, statisticienii sunt incantati de dimensiunea mare si complexa a bazei de date( trebuiau sa analizeze si proceseze displayuri grafice). Interesul lor a scazut treptat cand au observat ca timpul de asteptare era de ordinul orelor.Au raportat ca metodele data mining sunt greoaie si nefolositoare, si nu au gasit sabloane in date. Au recomandat ca eforturile sa se opreasca.
Daca acesti statisticieni ar fi avut o unealta de data mining care sa scaleze pentru a manui cantitatea enorma de date pe care o foloseau, pe un hardware paralel ( pentru o baza de date cu cantitati de date mari ar fi trebuit un sistem hardware corespunzator, care sa nu impiedicea obitnerea unor rezultate intr-un timp foarte scurt), ei ar fi avut o cu totul alta parere despre data mining.
Dimensiunea unei baze de date nu este singurul motiv pentru al folosirii tool-urile de scalare; alti factori: construirea, testarea si desfasurarea solutiilor de data mining intervin si influenteaza. Am obesrvat in exemplul de mai sus cum intr-o singura baza de date, o problema a fost cu o parte de date care necesitau scalare datorita numarului mare de procese(cazuri), in timp ce complexitatea unei alte portiuni conduce la nevoie unei solutii de scalare.
Noile tehnici includ algoritmi relative recenti cum ar fi retele neurale sau arbori de decizie, precum si noi adaptari ale vechilor algoritmi cum ar fi analizele discriminante. Prin eficienta introdusa de puterea mare a calculatoarelor asupra volumelor imense de date disponibile, aceste tehnici pot aproxima aproape orice forma functionala de interactiune dintre date. Tehnicile statistice traditionale se bazeaza pe specificatiile modelatorului privind formele functionale si interactiunile.
Punctul cheie este ca data mining este aplicarea acestor tehnici si a altor tehnici statistice si de inteligenta artificiala in problemele din obisnuite afaceri intr-un mod care face aceste tehnici disponibile muncitorilor experimentati si talentati la fel de usor ca personalului calificat in statistici. Data mining este un instrument pentru a creste productivitatea persoanelor care incearca sa cosntruiasca modele predictive.
Bazele de date din ziua de azi pot atinge dimensiuni de ordinul terabytes-ilor (peste 1.000.000.000.000 bytes de date). In aceasta imensa masa de date se ascund informatii ascunse care au o importanta strategica. Dar cand avem atatea date, cum putem sa tragem concluzii utile despre intreaga baza de date.
In procesul de gasire a sabloanelor ascunse in interiorul bazei de date, poti fi nevoit sa filtrezi o cantitate enorma de date. Platforma optima de a indeplini cerinta este de a rula in paralel algoritmi de data mining si algoritmi DBMS(Database management systems.) pe hardware paralel.
Urmatorul exemplu ilustreaza cum marimea unei baze de date care se doreste a fi investigata poate creste rapid. De asemenea prezinta si cum cautarea datelor dorite necesita diferite modele.
Exemplu: O uzina chimica nu este satisfacuta de productia sau calitatea unui produs si doreste investigarea factorilor care variaza si pot afecta cele 2 variabile( productia si calitatea) . O baza de date online stocheaza variabile cum ar fi temperatura, presiunea si timpul pentru fiecare dintre cele 6 ore de rulare.Aceste observatii sunt luate la fiecare secunda. Uzina functioneaza 7 zile pe saptamana, 24 de ore pe zi . In total sunt peste 20000 de observari pe schimb si deci o cantitate de date enorma.
Chimistii si inginerii chimisti au identificat cateva variabile de care ei erau siguri ca afecteaza productia si calitatea. Au speculat ca alte conditii ale mediului cum ar fi umiditatea mediului ar putea afecta resultatele.
Au decis ca o imbunatatire cu cel putin 20% a productiei si 10% a calitatii este un tel acceptabil pentru proiectul lor de data mining. Au listat toate variabilele pe care le vor investiga si ce modele le-ar fi de ajutor. Au scris totul intr-un raport care le va ghida investigatiile in saptamanile urmatoare.
Analiza datelor, a storage-urilor si procesele necesare sunt afectate de dimensiunea bazei de date. O masurare utila a marimii bazei de date este numarul de randuri si coloane. Randurile se refera la numarul de unitati sau procese(cazuri)- clienti, tranzactii, produse, pacienti,item-uri pe o linie de asamblare. Coloanele au referinta la numarul de masurari luate pe fiecare item. De exemplu , un rand ar putea sa fie o tranzactie cu case si coloanele ar include : informatii despre client, numerele din catalog ale articolelor comandate, pretul lor, cartea de credit utilizata , daca clientul doreste livrare la domiciliu samd.
Randurile si coloanele sunt un indicator foarte bun al timpului ce va fi pierdut pentru a construi un model. Cand numarul de randuri al unei baze de date este foarte mare , ori toate randurile trebuiesc procesate ori o parte random din ele vor trebui luate in considerare. In oricare mod, timpul necesar construirii m ce modele le-ar fi de ajutor. Au scris totul intr-un raport care le va ghida investigatiile in saptamanile urmatoare.
Analiza datelor, a storage-urilor si procesele necesare sunt afectate de dimensiunea bazei de date. O masurare utila a marimii bazei de date este numarul de randuri si coloane. Randurile se refera la numarul de unitati sau procese(cazuri)- clienti, tranzactii, produse, pacienti,item-uri pe o linie de asamblare. Coloanele au referinta la numarul de masurari luate pe fiecare item. De exemplu , un rand ar putea sa fie o tranzactie cu case si coloanele ar include : informatii despre client, numerele din catalog ale articolelor comandate, pretul lor, cartea de credit utilizata , daca clientul doreste livrare la domiciliu samd.
Randurile si coloanele sunt un indicator foarte bun al timpului ce va fi pierdut pentru a construi un model. Cand numarul de randuri al unei baze de date este foarte mare , ori toate randurile trebuiesc procesate ori o parte random din ele vor trebui luate in considerare. In oricare mod, timpul necesar construirii modelului va fi mai mare decat daca ar fi un numar de randuri mai mic de procesat.
Atributele coloanelor pot fi adaugate de asemenea la marime. De exemplu, o variabila cum ar fi sexul are doar 2 valori, dar una cum ar fi judetul poate avea 40 de valori. Unii algoritmi cum ar cei neuronali prefera sa aiba variabile ( cum e sex- de categorisire) care sa fie impartite in mai multe coloane in asa fel incat fiecare valoare a coloanei sa fie una dintre DA sau NU. Astfel variabila judet ar putea fi impartita in 40 de coloane, urmand ca numai una dintre ele sa aiba setata valoarea DA. In felul asta nu numai marimea bazei de date creste enorm, dar si cautarea pe care o face algoritmul respectiv creste enorm.
Procesul de “Data Warehousing” sau depozitare a datelor, permite sprijinirea procesului de luare de decizii cu ajutorul datelor de nivel detaliat pe care foarte multe companii le-au acumulat in volum considerabil de la inceputul procesului de informatizare. Procesul de “data warehousing” se foloseste in principal in urmatoarele categorii generale:
• cresterea vitezei si flexibilitatii procesului de analiza;
• permiterea unei integrari ale sistemelor de date la nivel de companie si deci un acces la date de la orice nivel al companiei;
• imbunatatirea sau remodelarea proceselor de afaceri ;
• intelegerea comportamentului clientilor.
2. Despre identificarea modelelor frecvente
Progresul in tehnologia de achizitie, distributie, recuperare si stocare a datelor in format digital a dus la dezvoltarea bazelor de date mari. Una dintre marile provocari la care au fost supusi organizatiile si cercetatorii de specialitate a fost modalitatea prin care sa transforme colectiile mari de date in informatie utila si accesibila.
Aceste incercari au beneficiat de aportul unor cercetatori din diferite domenii cum ar fi statistica, masini de invatat, baze de date si multe altele, fapt ce dus la nasterea unui nou domeniu numit „Data Mining”.
Data Mining este cunoscuta si sub prescurtarea KDD (Knowledge discovery in databases – descoperirea de informatie din bazele de date). Unii traducatori au incercat „mineritul datelor”, dar cei mai multi specialisti au ramas la denumirea de „data mining”.
dezvoltarea unei aplicatii dintr-un domeniu cunoscut.
selectarea unui set de date tinta pe care se va executa identificarea datelor si o filtrare a datelor daca este necesar.
alegerea task-ului de data mining, a algoritmului si specificarea exacta a modelului si parametrilor specifici.
executia pe datele de intrare,identificarea si extragerea sabloanelor si a modelelor.
vizualizarea, interpretarea si consolidarea informatiilor descoperite.
Procesul este iterativ in sensul ca fiecare pas poate inspira rectificari pasilor anteriori. Este interactiv in sensul ca un user trebuie sa stie si sa poata limita efortul sistemului doar la ceea ce il intereseaza. Pasul de data mining este luat in considerare impreuna cu task-ul de extragere de informatie din datele ce ar putea fi importante pentru posesorul datelor stocate.
Data mining este analiza (deseori mare) a seturilor datelor pentru a gasi relatii nebanuite si a a le aranja intr-un mod usor accesibil si inteligibil utilizatorului.
Exista cateva task-uri corespunzatoare obiectivelor a ceea ce trebuie analizat si mai ales cum ar trebui sa arate rezultatele. Aceste task-uri pot fi impartite dupa cum urmeaza
Explorarea datelor analizate. Scopul principal este de a explora datele fara a avea vreo idee clara a ce se doreste a fi descoperit. Tehnici specifice includ metode grafice de afisare, tehinici de proiectare si metode de a prezenta reultatele( a face un rezumat al rezultatelor in contextul problemei initiale).
Recuperarea dupa continut. Utilizatorul are un sablon specific si doreste gasirea unor modele similare in seturile de date. Acest task este cel mai folosit pentru extragerea de informatie din colectiile mari si foarte mari de texte si imagini. Principala provocare este definirea asemanarilor si cum se face gasirea si identificarea sabloanelor care respecta definitia respectiva. Un exemplu cunoscut este motorul de cautare Google, care gaseste pagini web ce contin informatii similare cu un set de cuvinte transmise de utilizator.
Modelul descriptiv. Incearca o descriere fidela si cat mai explicita a datelor colectate. De asemenea include modele statistice, clustere si modele ce definesc dependentele.
Modelul predictiv. Tehnicile predictive cum ar fi clasificarea si revenirea la starea anterioara incearca sa raspunda la intrebari examinand in prealabil informatia si raspunsurile pentru a le generaliza pentru oportunitatile viitoare. Un exemplu de clasificare este sistemul SKICAT, care poate clasifica stele si galaxii ca expertii umani. Sistemul este folosit in mod curent de NASA pentru a cataloga milioanele de stele si galaxii din imaginile digitale ce surprind bolt cereasca.
Identificare sabloanelor. Scopul este de a gasi sabloane locale ce apar frecvent in interiorul bazei de date. Exista foarte multi algoritmi ce au fost studiati pentru diferite tipuri de sabloane, cum ar fi seturile, structurile de tip arbore, graf sau o structura relationala arbitrara si regulile de asociere ce actioneaza peste aceste structuri. Cele mai studiate tipuri de sabloane sunt seturile de articole(item-uri) care apar impreuna , frecvent in tranzactiile din bazele de date cum ar fi inregistrarile de vanzari de tip cos ale unui magazin.
In aceasta lucrare ne vom axa pe descoperirea de sabloane frecvente si cum pot fi rezolvate intr-un mod eficient in contextul specific al seturilor de articole (item-uri) si a regulilor de asociere.
Motivatia originala pentru a cauta reguli de asociere a aparut din nevoia de a analiza asa numita tranzactie a unui mare magazin universal („supermarket”).
In ultimul timp multi algoritmi au fost propusi pentru a rezolva problema „frequent itemset mining”, adica sa gaseasca toate seturile de item-uri care apar impreuna frecvent intr-o baza de date cu tranzactii oarecare. Desi tehnici foarte eficiente au fost prezentate, ele sufera in continuare de aceeasi problema. Adica, toate sunt inerent dependente de dimensiunea memoriei principale disponibila. Mai mult, daca aceasta cantitate nu este indeajuns, tehnicile prezentate pur si simplu nu mai sunt aplicabile sau au o nevoie stringenta sa creasca in performante. In aceasta lucrare, facem o comparatie riguroasa intre tehnicile curente cele mai importante si prezentam o tehnica noua si simpla bazata pe sortarea bazei de date ce contine tranzactii, rezultand un algoritm uneori mai eficient si datorita faptului ca foloseste mai putina memorie.
De la introducerea sa in 1993 de catre Argawal si altii, problema de cautare a item-urilor frecvente a primit multa atentie. In ultima decada, sute de lucrari de cercetare au fost publicate prezentand noi algoritmi sau imbunatatiri ale algoritmilor existenti pentru a rezlova mai eficient aceste probleme de itemset mining.
Seturile de articole (itemset-urile) joaca un rol esential in multe probleme de data mining care incearca sa gaseasca sabloane(modele) importante in bazele de date, cum ar fi regulile de asociere, corelatiile, secventele, episoadele, clasificarile si multe altele pentru care descoperirea regulilor asociative este una dintre principalele scopuri. Motivatia initiala pentru cautarea regulilor de asociere a venit din nevoia de a analiza asa-numita tranzactie de tip „supermarket”, adica de a examina comportamentul clientului in functie de produsele cumparate. Regulile de asociere descriu cat de des sunt cumaparate impreuna unele articole (item). De exemplu, o regula de asociere „bere => chips-uri (80%)” specifica faptul ca patru din cinci clienti care au cumparat bere au cumparat si chips-uri. Astfel de reguli pot fi folositoare pentru luarea deciziilor cu privire la pretul produselor, promotiilor, managementul stocurilor si multor altor aspecte.
Conceptele de seturi de articole frecvente( frequent itemset) si reguli de asociere au primit o atentie sporita din partea specialistilor inca de la introducerea conceptului de catre Argawal, in 1993. In ultimul deceniu, sute de lucrari de cercetare au fost publicate presentand noi algoritmi sau imbunatatind algoritmi existenti pentru a rezolva problemele de cautare( mining) mult mai eficient.
3. Descrierea problemei
Fie J un set de articole (item-uri). Un set X= {i1, . . . , ik} J este numit itemset, sau un k-itemset daca el contine k item-uri. O tranzactie peste J este un tuplu T=(tid,I) unde tid este identificatorul tranzactiei, iar I este un set de item-uri(itemset). O tranzactie T=(tid,I) se spune ca suporta un itemset XJ daca XI . O baza de date D ce contine tranzactii peste J este un set de tranzactii peste J. Acoperirea(cover) unui itemset X in D consta in setul de identificatori ai tranzactiilor din D ce suporta(acopera) pe X:
cover(X,D):={tid| (tid,I) D,XI}.
Suportul unui itemset X in D(baza de date ce contine tranzactiile) este numarul de tranzactii din acoperirea(cover-ul) lui X peste D:
support(X,D) = | cover(X,D) | .
Frecventa unui itemset X din D este probabilitatea ca X sa apara intr-o transactie TD:
frequency(X,D) = P(X) = support(X,D) / |D| . Am notat prin |D| = support({},D) .
Un itemset este frecvent daca suportul sau nu este mai mic decat un prag minimal absolut , unde 0≤≤|D|. Cand se lucreaza cu frecventele itemset-urile in locul folosirii suportului, vom utiliza un prag minimal relativ , unde 0≤≤1 si =[ * |D| ] . Mai departe vom folosi doar pragul minimal absolut si il vom nota cu σ .
Fie D o baza de date cu tranzactii peste un set de item-uri J, si σ pragul minimal. Colectia(multimea) de itemset-uri frecvente din D ce respecta σ este data de relatia:
F(D,σ) = {XJ| support(X,D) ≥σ}.
O prima problema care se ridica ar fi: avand un set de itemuri J, o baza de date cu tranzactii D cu item-uri din J si un prag minimal sa se construiasca F(D,σ).
In realitate nu ne intereseaza doar setul de itemuri F, dar si suportul acestor itemset-uri. O regula de asociere este o expresie de forma X=>Y, unde X si Y sunt itemset-uri si X∩Y={}. O astfel de regula exprima faptul ca ca daca o tranzactie contine toate item-urile din X atunci acea tranzactie contine ,deasemenea, toate item-urile lui Y. X este numit corp , iar Y cap al regulii. Suportul unei reguli X=>Y peste D este suportul lui XUY peste D si analog, frecventa unei reguli este frecventa lui XUY. O regula se numeste frecventa daca suportul sau sau frecventa sa depaseste un suport minimal absolut, respectiv relativ σ.
Increderea(confidence) unei reguli X=>Y peste D este probabilitatea de a avea Y in tranzactie, stiind ca X este continut de acea tranzactie:
confidence(X=>Y,D) = P(Y|X) = support(XUY,D) / support(X,D).
Regula este „de incredere” daca P(Y|X) depaseste un prag minimal al increderii (certitudinii) γ, unde 0≤ γ ≤1.
Fiind data o baza de date, D, ce contine tranzactii peste un set de item-uri J, σ un prag minimal(pentru suport) si γ un prag mininal al increderii, colectia de reguli frecvente si „de incredere” ce respecta σ si γ este data de expresia:
R(D, σ,γ) = {X=>Y | X,Y, X∩Y={}, XUYF(D,σ), confidence(X=>Y,D)≥ γ}.
A doua problema ce se ridica este: avand un set de item-uri J, o baza de date cu tranzactii D peste J, pragurile minimale σ si γ sa se construiasca R(D, σ,γ). Pe langa aflarea tuturor regulilor ne intereseaza de asemenea si calcularea suportului si al increderii pentru fiecare dintre aceste reguli.
Precizam ca problema de gasire a itemset-urile(frecvente) este un caz particular al problemei de identificare a regulilor de asociere. Intr-adevar, daca avem date cele doua praguri σ si γ, atunci fiecare itemset frecvent X reprezinta o regula X=>{}, care este evident ca are increderea de 100%. Este evident ca suportul ca suportul regulii este egal cu cel al lui X. De asemenea pentru fiecare itemset frecvent I, toate regulile X=>Y , unde XUY=I , sunt pastrate cu o incredere relativa de cel putin σ. De aici inainte trebuie ca pragul minimal al increderii sa fie mai mare decat pragul minimal al frecventei pentru a mai avea vreun efect.
Exemplu: Consideram setul de item-uri(articole) J ={bere,chips,pizza,vin} si o baza de date cu tranzactii,D :
Tabelul 1. Un exemplu de baza de date cu tranzactii, D
In tabelul urmator se pot vedea itemset-urile frecvente din D ce respecta pragul minimal al suportului de 1. Tabelul 3 prezinta toate regulile frecvente si de incredere ce respecta pragul minimal (al suportului) 1 si pragul minimal al increderii de 50%.
Tabelul 2. Itemset-urile si suportul lor peste D
Tabelul 3. Regulile de asociere cu suportul si increderea lor peste D
Primul algoritm propus pentru a rezolva problema gasirii regulilor de asociere este impartit in doua parti . In prima faza , toate itemset-urile sunt generate(sau toate regulile frecvente de forma X=>{} ). Faza a doua consta in generarea tuturor regulilor frecvente si de incredere. Aproape toti algoritmi de gasire a regulilor de asociere respecta aceasta strategie a celor doua faze. Cu toate acestea exista un algoritm, MagnumOpus, care foloseste alta strategie pentru a genera imediat un larg subset al tuturor regulilor de asociere .
4. Baze de date ce contin tranzactii
Pentru a calcula suporturile unei colectii de itemseturi, trebuie sa accesam baza de date. De vreme ce asemenea baze de date tind sa fie foarte mari, nu este intotdeauna posibil sa fie stocate in memoria principala.
Un aspect important la cei mai multi algoritmi este reprezentarea bazei de date ce contine tranzactii. Conceptual, o asemenea baza de date poate fi reprezentata de o matrice binara bidimensionala in care fiecare rand reprezinta o tranzactie individuala, iar coloanele reprezinta item-urile din I. O asemenea matrice poate fi implementata in mai multe modalitati. Cel mai comun utilizat layout este layout-ul orizontal de date. Adica, fiecare tranzactie are un identificator de tranzactie si o lista de itemuri ce apar in acea tranzactie. Un alt layout des utilizat este layout-ul vertical de date, unde baza de date consta intr-un set de itemuri, fiecare urmat de acoperirea sa(cover-ul sau). Tabelul urmator arata ambele layout-uri pentru baza de date din exemplul de mai sus. De remarcat ca pentru ambele layout-uri este de asemenea posibil de a folosi bit-string-urile exacte din matrice binara. De asemenea, pote fi folosita si o combinatie a ambelor layout-uri.
Tabel 4a. Layout-ul orizontal pentru baza de date cu tranzactii,D
Tabel 4b. Layout-ul veritcal pentru baza de date cu tranzactii,D
Pentru a calcula suportul unui itemset X folosind layout-ul orizontal al bazei de date, trebuie sa scanam baza de date complet si sa testam pentru fiecare tranzactie T daca XT. Desigur, acest lucru poate fi realizat pentru o colectie mare de itemseturi imediat. O greseala importanta in “frequent pattern mining” este ca scanarea bazei de date este o operatie I/O foarte intensa. Totusi, in cele mai multe cazuri, acesta nu este costul principal al pasilor de numarare. In schimb, actualizarea suporturilor tuturor itemset-urilor candidate continute intr-o tranzactie consuma in mod considerabil mai mult timp decit citirea acelei tranzactii dintr-un document sau dintr-o baza de date. Intr-adevar, pentru fiecare tranzactie trebuie sa verificam daca fiecare itemset candidat este inclus in acea tranzactie, sau similar, trebuie sa verificam fiecare subset al acelei tranzactii daca este in setul de itemseturi candidate. Pe de alta parte, numarul de tranzactii dintr-o baza de date este adesea corelat cu marimea maxima a unei tranzactii din baza de date respectiva. Ca urmare, numarul de tranzactii are o influenta asupra timpului necesar pentru calcularea suportului, dar nu este in nici un caz principalul factor. Layout-ul vertical al unei baze de date are avantajul major ca suportul unui itemset X poate fi usor calculat: intersectand cover-urile a oricaror doua subseturi Y,ZX, astfel incat YUZ = X. Totusi, dat fiind un set de item-uri candidate, aceasta tehnica presupune existenta cover-urile(acoperirerea) unui numar mare de seturi in memori principala, lucru care desigur nu este intotdeauna posibil. Intr-adevar, cover-urile tuturor itemset-urilor simple deja reprezinta intreaga baza de date.
5. Spatiul de cautare
Sarcina de a descoperi toate itemset-urile frecvente este destul de antrenanta. Spatiul de cautare este proportional cu numarul de item-uri ce apar in baza de date( este exponential cu numarul total de item-uri simple). De asemenea, aceste baze de date pot avea dimensiuni foarte mari, continand milioane de tranzactii si facand din contorizarea suportului o problema dificila.
Spatiul de cautare al tuturor itemset-urilor contine exact itemset-uri diferite. Daca J este suficient de mare, atunci o abordare naiva de a genera si contoriza suportul tuturor itemset-urilor dintr-o baza de date nu poate fi realizat (finalizat) intr-o timp rezonabil. De exemplu, in multe aplicatii J contine mii de item-uri si apoi numarul total de itemset-uri ce poate fi generat poate depasi usor .
In schimb, putem genera numai acele itemset-uri ce apar cel putin o data in baza de date cu tranzactii. In mod special, vom genera toate subseturile tuturor tranzactiilor ce apar in baza de date. Bineinteles , pentru tranzactii mari, acest numar ar putea fi totusi prea mare. De aceea, ca o optimizare, putem genera doar acele subseturi ce nu dapasesc o anumita dimensiune maxima. Aceasta tehnica a fost studiata de Amir si a reusit in cazul unei baze de date rasfirate. Cu toate aceste, pentru o baza de date foarte mare sau densa, acest algoritm nu merge foarte bine datorita faptului ca necesita memorie multa. De aceea , cateva solutii au fost propuse pentru a executa o cautare mai directa prin spatiul de cautare.
In timpul unei asemenea cautari, cateva multimi de itemset-uri candidate sunt generate si suportul lor calculat pana cand toate itemset-urile frecvente sunt generate.
Dandu-se o baza de date cu tranzactii D, un prag minimal al suportului σ, si un algoritm ce calculeaza F(D,σ) (adica multimea itemset-urilor frecvente), un itemset I este numit candidat daca acel algoritm calculeaza daca I este frecvent sau nu.
Marimea unei colectii de itemset-uri candidate nu trebuie sa depaseasca dimensiunea memoriei principale. Mai mult, este important sa fie generati cat mai putini candidati posibil, din moment calcularea suportului unei multimi de itemset-uri este o mare consumatoare de timp. In cel mai bun caz doar itemset-urile frecvente sunt generate si contorizate. Din pacate, acest lucru este imposibil.Ce mai exploatata proprietate de cei mai multi algoritmi este faptul ca suportul este monoton descrescator privitor la extinderea unui itemset.Fiind data o baza de date cu tranzactii D peste J si X,YJ ,doua itemseturi atunci daca XY => support(Y) ≤ support(X) . Aceasta reiese imediat din : cover(Y) cover (X)
Daca un itemset nu este frecvent atunci toate superseturile sunt nefrecvente. Aceasta proprietate de monotonie este denumita si proprietate de inchidere in jos ( downward closure property).Spatiul de cautare al tuturor itemset-urilor poate fi reprezentat printr-o retea , ce seamana cu un graf orientat, cu itemset-ul vid in varf si setul continand restul de itemset-uri jos. Colectia de itemset-uri frecvente F(D,σ) poate fi reprezentata de multimea maxima a itemset-urilor frecvente sau de colectia minima a itemset-urilor nefrecvente. Mannila a introdus notiunea de frontiera (border). Fie F o colectie de subseturi ale lui J. Frontiera Bd(F) consta in acele itemset-uri XJ astfel incat toate subseturile lui X sunt in F si nici un superset al lui X nu este in F
Bd(F) = {XJ| VY X : Y F ^ V ZX : Z F}
Acele itemset-uri din Bd(F) care sunt in F fac parte din frontiera pozitiva Bd+(F):
BD+(F) = {XJ| VY X : Y F ^ V ZX : Z F},
iar acele itemset-uri din Bd(F) care nu sunt in F fac parte din frontiera negativa Bd-(F):
BD-(F) = {XJ| VY X : Y F ^ V ZX : Z F},
6. Structuri de date
Generarea candidatilor si procesul de calcul al suportului necesita o structura de date eficienta in care toate itemset-urile candidate sunt stocate de vreme ce este important sa se gaseasca eficient itemset-urile care sunt continute intr-o tranzactie sau intr-un alt itemset.
6.1 Hash-tree
Pentru a gasi eficient toate subseturile k ( k-subset) ale unui itemset potential candidat, toate itemset-urile frecvente in Fk sunt stocate intr-un hash-table. Itemseturile candidate sunt stocate intr-un hash-tree. Un nod al arborelui fie contine o lista de itemseturi (nod frunza) sau un alt hash-table(nod interior). Intr-un nod interior, fiecare celula (bucket) indica spre alt nod. Radacina hash-tree-ului este definita ca fiind de adancime 1. Un nod interior la adancime d indica spre noduri la adancimea d+1. Itemset-urile sunt stocate in frunze. Cand adaugam un k-itemset X in timpul procesului de generare a candidatilor, incepem de la radacina si ajungem in jos pe arbore la o frunza. La un nod interior de adancime d, decidem ce ramura sa urmam aplicand o functie hash item-ului X[d] a itemsetului si urmand pointerul intr-o celula corespunzatoare. Toate nodurile sunt initial create ca noduri frunze. Cand numarul itemset-urilor intr-un nod de frunze la adancime d depaseste un prag specific, nodul de frunze este convertit intr-un nod interior numai daca k>d. Pentru a gasi itemset-urile candidate care sunt continute in tranzactia T, incepem de la nodul radacina. Daca suntem la o frunza, aflam care dintre itemset-uri sunt continute in T si le incrementam suportul. Daca suntem la un nod interior si l-am atins folosind functia de hash pentru itemul i, atunci apelam functia pentru fiecare item care vine dupa i in T si aplicam recursiv aceasta procedura nodului din celula corespunzatoare. Pentru nodul radacina, procesam fiecare item din T.
6.2 Trie
O alta structura de date care este larg folosita este un trie (sau prefix-tree). Intr-un trie, fiecare k-itemset are un nod asociat, asa cum are si k-1-itemeset-ul la randul sau. Itemset-ul vid reprezinta nodul radacina. Toate 1-itemset-urile(itemset-urile simple,ce contin doar item-uri simple) sunt atasate de nodul radacina si ramurile sale sunt etichetate de itemset-ul pe care il reprezinta. Fiecare k-itemset este atasat la prefixul k-1 corespunzator. Fiecare nod stocheaza ultimul item in itemsetul pe care il reprezinta, suportul sau si ramurile sale. Ramurile unui nod pot fi implementate utilizand cateva structuri de date cum ar fi: un hash-table, un arbore de cautare binara sau un vector. La o anumita iteratie k, toate itemset-urile candidate sunt stocate la o adancime k in trie. Pentru a gasi itemseturile-candidate ce sunt continute intr-o tranzactie T, incepem cu nodul radacina. Pentru a procesa o tranzactie pentru un nod din trie, (1) se urmeaza ramura corespunzatoare primului item in tranzactie si se aplica recursiv pe restul tranzactiei pentru acea ramura si (2) se abandoneaza primul item al tranzactiei si se proceseaza recursiv pentru nodul insusi. Aceasta procedura mai poate fi optimizata asa cum este descris in [11].
De asemenea, pasul de join procedurii de generare a candidatilor devine foarte simplu folosind un trie, de vreme ce toate itemseturile de marime k cu acelasi k-1-prefix sunt reprezentate de ramurile aceluiasi nod (acel nod reprezinta prefixul k-1). Intr-adevar pentru a genera toate itemseturile candidate cu prefix k-1 ,X, copiem toti fratii nodului ce reprezinta X drept ramuri ale acelui nod.
Mai mult, putem incerca sa minimalizam numarul acestor generari reordonand itemurile din baza de date in ordinea crescatoare a suportului. Folosind aceasta euristica, putem reduce numarul itemset-urilor generat in timpul pasului de join, si, astfel, implicit putem micsora numarul de ori de care pasul de stergere (prune step) are nevoie sa fie realizat. De asemenea, pentru a gasi nodul reprezentand un k-itemset specific in trie, trebuie sa realizam k cautari intr-un set de ramuri. Evident, realizarea unei asemenea cautari poate fi imbunatatita cand aceste seturi sunt tinute la dimensiuni cat mai mici.
In figura se poate observa cum arata un trie realizat pentru 4 item-uri : A, B, C, D . Este un trie complet. Cu linia mai groasa este arat itemset-ul ABD. In functie de contorul fiecarui item trie-ul poate suferi modificari, in sensul de a fi sterse item-urile ce se dovedesc nefrecvente. Fiecare algoritm realizeaza si o stocare in fiecare item al trie-ului diferite detalii , cum ar fi suportul , numarul tranzactiei in care apare item-ul respectiv. Initial la o prima trecere prin baza de date ce contine tranzactii se creeaza item-urile simple si se introduc in root. La terminarea scanarii se vor elimina acele item-uri simplece nu sunt frecvente
Urmand ca fiecare algoritm sa adauge sau sa stearga noduri in sau din trie in functie de executia sa specifica. Exceptie face o varianta a algoritmului DIC (Dynamic Itemset Counting) ce adauga dinamic item-urile la nodul principal(root). Varianta initiala a algoritmului prevedea ca trie-ul sa fie deja generat inainte de executia algoritmului. Dar cum sunt 2 la n noduri pentru o baza de date cu mii de tranzactii memoria nu ar ajunge pentru a retine trie-ul total.
7. APRIORI
Primul algoritm realizat pentru a genera toate itemset-urile frecvente si regulile de asociere de incredere a fost algoritmul AIS al lui Agrawal, care a fost prezentat impreuna cu o introducere in problema cautarii si identificarii sabloanelor frecvente. La putin timp algoritmul a fost imbunatatit si redenumit „Apriori” tot de catre Agrawal, exploatand proprietatea de monotonie a suportului itemset-urilor si a increderii regulilor de asociere. Aceeasi tehnica a fost propusa independent de catre Mannila. Ulterior cei doi au reusit sa-si cumuleze cunostintele si descoperirile de pana atunci si au propus „ R. Agrawal, T. Imielinski, and A.N. Swami. Mining association rules between sets of items in large databases. In P. Buneman and S. Jajodia, editors, Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, volume 22(2) of SIGMOD Record, pages 207–216. ACM Press, 1993”
7.1 ITEMSET MINING
Se presupune ca item-urile din tranzactii sunt pastrate in ordine crescatoare. Daca nu, se poate face o mica adaugare in care pentru mai multa siguranta dupa citirea tranzactiei se prelucreaza ,adica se pot elimina itemset-urile nefrecvente si ordonarea lor lexicografic(de ex crescator daca avem item-uri numerice) sau dupa un alt criteriu.
Etapa de gasire a itemset-urile din algoritmul Apriori este dat mai jos. Vom folosi notatia X[i] pentru a reprezenta item-ul numarul i din itemset-ul X. Prin k-prefix itelegem ca item-urile
{ X[1], X[2], … , X[k] }.
Algoritmul realizeaza o cautare in latime prin spatiul de cautare(search space) a tuturor itemset-urilor generand iterativ itemset-uri candidate Ck+1 de dimensiune k+1, incepand cu k=0 (linia 1). Un itemset este candidat daca toate subseturile sale sunt cunoscute ca fiind frecvente. In mod special, C1 consta in multimea completa a item-urile(simple) din J, si la un anumit nivel k toate itemset-urile de dimensiune k+1 sunt generate. Acest lucru e realizat in 2 pasi. Primul,numit si pasul de join (join step), Fk este unificat cu el insusi (Fk reprezinta multimea itemset-urilor frecvente). Reuniunea itemset-urilor X,Y Fk , XUY este realizata doar daca cele doua itemset-uri au acelasi prefix k-1(liniile 20-21). In pasul de eliminare (prune step), XUY este inserat in Ck+1 doar daca toate subseturile de dimensiune k apar in Fk , adica sunt frecvente.
Pentru a contoriza suportul tuturor itemset-urilor de dimensiune k, baza de date ,dupa modelul orizontal, este scanat tranzactie cu tranzactie si suportul tuturor itemset-urilor candidate ce sunt incluse in acea tranzactie sunt incrementate(liniile 6-12). Toate itemset-urile care se transforma in itemset-uri frecvente sunt inserate in Fk (liniile 14-18). In implementare, itemset-ul nefrecvent impreuna cu copiii sai este sters fiind pastrate doar item-urile frecvente.
Daca numarul candidatilor de marime k+1 este prea mare pentru a fi retinut in memoria principala, procedura de generare se opreste si suportul candidatilor generati este calculat ca si cum nimic nu s-ar fi intamplat. Dar , la iteratia urmatoare, in loc de generarea candidatilor de marime k+2, restul candidatilor de ordin k+1 este generat si contorizat pana cand toate itemset-urile frecvente de ordin k+1 sunt generate.
7.2 Identificare regulilor de asociere
Avand obtinute toate itemset-urile frecvente, putem genera acum toate regulile de asociere frecvente si de incredere. Acest algoritm este foarte asemanator cu cel aratat putin mai sus.
La inceput, toate itemset-urile frecvente sunt generate folosind algoritmul de mai sus. Apoi, fiecare itemset I este impartit in cap, Y, si corp , X=I \ Y.Acest proces incepe cu Y={}, rezultand o regula I=>{}, care intotdeauna are nivelul de incredere de 100% (linia 4). Dupa aceasta, algoritmul genereaza iterativ candidati de tipul „cap” (head) de marime k+1, Ck+1 incepand cu k=0 (linia 5). O parte „head” este un posibil candidat daca toate subseturile sale sunt cunoscute ca fiind reguli de incredere. Acest proces de generare a candidatilor de tip „head” este exact ca generarea itemset-urilor din algortimul de mai sus(liniile 11-16). Pentru a calcula increderea unui candidat Y, suportul lui I si al lui X este extras din F. Toate „head”-urile ce creeaza reguli de incredere sunt introduse in Hk (linia 9). La sfarsit toate regulile de incredere sunt introduse in R (linia 20)
Se observa ca dandu-se un itemset I si un „head” candidat Y, astfel incat I\Y=>Y, algoritmul verifica pentru toate Y’ Y daca regula I \ Y’ => Y este de incredere , dar nu si daca regula I \ Y => Y’ este de incredere. Cu toate acestea, este foarte posibil daca toate regulile sunt generate dintr-un itemset I, doar daca toate regulile sunt deja generate pentru toate itemset-urile I’ I
7.3 Optimizari
O multime de alti algoritmi propusi dupa introducerea lui Apriori au aceeasi structura generala, adaugand cateva tehnici pentru a optimiza anumiti pasi din cadrul algoritmului.De vreme ce performanta algoritmului Apriori este aproape in totalitate dictata de procedura sa de calcul al suportului, cele mai multe cercetari s-au concentrat asupra acelui aspect al algoritmului Apriori. Asa cum s-a mentionat inainte, performanta acestei proceduri este in principal dependenta de numarul de itemset-uri candidate ce apar in fiecare tranzactie.
7.3.1 AprioriTid, AprioriHybrid
Odata cu propunerea algoritmului Apriori, Agrawal si altii au propus doi alti algoritmi, AprioriTid si AprioriHybrid. Algoritmul AprioriTid reduce timpul necesar pentru procedura de calcul al suportului inlocuind fiecare tranzactie din baza de date cu setul de itemset-uri candidate ce apar in tranzactii. Aceasta este realizat repetat la fiecare iteratie k. Baza de date cu tranzactii adaptata este denumita de Ck.
Desi algoritmul AprioriTid este mult mai rapid in iteratiile tarzii, se comporta mult mai incet decat Apriori in iteratiile initiale. Aceasta mai ales din cauza overhead-ului aditional ce este creat atunci cand Ck este mai mare decat memoria principala si trebuie scris pe disc. Daca o tranzactie nu contine nici un itemset-k candidat, atunci Ck nu va avea intrare(entry) pentru aceasta tranzactie. Astfel, numarul de intrari in Ck poate fi mai mic decat numarul de tranzactii din baza de date, mai ales la iteratiile tarzii din algoritm. Aditional, la iteratiile tarzii, fiecare intrare poate fi mai mica decat tranzactia corespunzatoare deoarece foarte putine item-uri candidate pot fi continute in tranzactie. Totusi, in iteratiile initiale, fiecare intrare poate fi mai larga decat tranzactia sa corespunzatoare. Ca urmare, un alt algoritm, AprioriHybrid, a fost propus ce combina algoritmii Apriori si AprioriTid intr-un singur hibrid. Acest algoritm hibrid foloseste Apriori pentru iterarile initiale si se transforma in AprioriTid cand se asteapta ca setul Ck sa aiba loc in memoria principala. De vreme ce marimea lui Ck este proportionala cu numarul de itemset-uri candidate, o euristica este folosita pentru a estima marimea pe care Ck ar avea-o in iteratia curenta. Daca aceasta marime este indeajuns de mica si sunt mai putine sabloane(pattern-uri) candidate in iteratia curenta decat in iteratia anterioara, algoritmul decide sa mute in AprioriTid.Totusi aceasta euristica nu este foarte riguroasa.
7.3.2 DHP
La putin timp dupa propunerea algoritmilor Apriori, Park si altii. au propus o alta optimizare, numita DHP (Direct Hashing and Pruning) pentru a reduce numarul de itemset-uri candidate. In timpul celei de-a k iteratii, cand suporturile tuturor k-itemset-urilor candidate sunt numarate scanand baza de date, DHP deja aduna informatii despre itemset-urile candidate de marime k+1 de o asemenea maniera incat toate subseturile (k+1) ale fiecarei tranzactii dupa o curatare sunt introduse intr-un hash table. Fiecare celula din tabela hash consta intr-un contor pentru a reprezenta cate itemset-uri au fost integrate in acea celula pana atunci. Apoi, daca un itemset candidat de marime k+1 este generat, functia de hash este aplicata acelui itemset. Daca acel contor din celula corespunzatoare a tabelei hash este sub pragul minim de suport, itemset-ul generat nu este adaugat la multimea de itemset-uri adaugate. De asemenea, in timpul fazei de calcul al suportului iteratiei k, fiecare tranzactie s-a aranjat dupa cum urmeaza. Daca o tranzactie contine un itemset frecvent de marime k+1, orice item continut in acel itemset k+1 va aparea in cel putin k din itemseturile-k candidate in Ck. Ca rezultat, un item din tranzactia T poate fi taiat (trimmed) daca nu apare in cel putin k din itemseturile-k in Ck. Aceste tehnici, dau o descrestere semnificativa a numarului de itemseturi candidate ce trebuie numarate, mai ales in a doua iteratie. Totusi, crearea tabelelor hash si scrierea bazei de date adaptate pe disc la fiecare ieteratie cauzeaza o incarcare (overhead) semnificativa.
Desi DHP a fost acceptat de unii cercetatori ca avand performante mai bune decat Apriori si AprioriHybrid, aceasta teorie a fost repinsa de Ramakrishnan daca urmatoare optimizare este adaugata la Apriori. In loc de a folosi arborele-hash pentru a stoca si numara toate 2-itemseturile candidate, un array triunghiular C este creat in care contorul suportului unui 2-itemset candidat
{i, j}este stocat in locatia C[i][j]. Folosind acest array, procedura de calcul al suportului se reduce la o simpla bucla pe doua niveluri pentru fiecare tranzactie.
De vreme ce numarul 2-itemseturilor candidate este exact (2 la puterea F1), inca este posibil ca acest numar sa fie prea mare, asfel incat numai o parte a structurii sa fie generata si sa fie necesare mai multe scanari ale bazei de date. Totusi, din experienta, am descoperit ca o multime de 2-itemset-uri candidate nici nu apar deloc in baza de date si de aici, suportul lor ramane 0. Astfel, propunem urmatoarea optimizare. Cand toate item-urile simple sunt numarate, rezultand setul de itemseturi F1, nu generam nici un 2-itemset candidat. In schimb, incepem sa scanam baza de date si sa eliminam din fiecare tranzactie toate itemurile care nu sunt frecvente. Apoi, pentru fiecare tranzactie aranjata crestem suportul tuturor itemset-urilor candidate continute in acea tranzactie. Totusi, daca 2-itemset-ul candidat nu exista inca, generam itemset-ul candidat si ii initializam suportul la 1. Astfel, numai acele 2-itemset-uri candidate care apar cel putin o data in baza de date sunt generate. De exemplu, aceasta tehnica a fost in special folositoare pentru setul de date de tip cos (basket) folosite in experimental nostrum, de vreme ce in acel set date exista 8051 de item-uri frecvente si astfel, Apriori ar genera 2-itemset-uri candidate. Folosind aceasta tehnica, acest numar a fost redus drastic la 1 708 203.
8. DIC(Dynamic Itemset Counting)
Algoritmul DIC(Dynamic Itemset Counting) a fost propus ca o alternativa a algoritmului Apriori cu scopul de a genera itemset-uri frecvente , item-uri ce sunt citite dintr-o baza de date ce contine tranzactii. Itemset-urile sunt adaugate si sterse dinamic pe masura ce tranzactiile sunt citite. Si acest algoritm se bazeaza pe faptul pentru a fi frecentu un itemset trebuie ca toate subseturile sale sa fie frecvente. Deci se vor examina doar acele itemset-uri ale caror subseturi sunt frecvente. Cercetatorii au facut o analogie intre acest algoritm si un mersul unui tren.
Algoritmul se opreste dupa ce a citit M tranzactii pentru a adauga no itemset-uri.
Exista cate o statie la fiecare M tranzactii(dupa ce trenul parcurge cei M km se va opri intr-o statie). Pasagerii sunt itemset-urile. Itemset-urile se pot urca la orice oprire,dar se vor da jos la aceeasi statie la care s-au urcat. Doar itemset-urile din tren vor fi numarate cand se regasesc intr-o tranzactie. La inceput se pot contoriza 1-itemset-urile, iar la prima statie putem numara cateva dintre 2-itemset-uri. La a doua statie putem numara 3-itemset-urile si alte 2-itemseturi care pot aparea si vor fi de asemenea numarate.
Exista patru flag-uri pentru itemset-uri:
– patrat solid – – itemset frecvent si confirmat: un itemset care a trecut prin toate tranzactiile si a depasit pragul minimal al suportului (minsupp)
– cerc solid – – itemset nefrecvent si confirmat: un itemset care a trecut prin toate tranzactiile si nu a depasit pragul minimal al suportului(minsupp)
– patrat punctat – – itemset suspectat a fi frecvent- un itemset al carui suport se contorizeaza in continuare(dar a depasit deja minsupp)
– cerc punctat – – itemset suspectat a fi infrecvent- un itemset ce nu a trecut prin toate tranzactiile ,dar al carui suport se incrementeaza ori de cate ori apare intr-o tranzactie.
Pseudocod (algoritm static):
Marcheaza itemset-ul vid cu cerc solid. Marcheaza toate 1-itemset-urile cu cerc punctat. Lasa toate celelalte itemset-uri nemarcate.
Cat timp mai sunt itemset-uri punctate
Citeste M tranzactii(daca ajungem la sfarsitul fisierului cu tranzactii vom continua cu inceputul).Pentru fiecare tranzactie incrementeaza contorul fiecarui itemset ce apare in tranzactie si este marcat ca fiind cerc punctat.
Daca suportul unui itemset marcat cu cerc punctat depaseste minsupp atunci transforma-l in patrat punctat. Daca un superset imediat are toate subseturile sale patrate solide sau punctate atunci adauga un nou contor pentru el si transforma-l in cerc punctat.
Daca un itemset punctat a fost contorizat prin toate tranzactiile atunci el se va marca solid si nu se va mai contoriza.
Exemplu:
Se da fisierul cu urmatoare baza de date cu tranzactii:
, iar minsupp=25% si M=2.
Trie-ul pentru tranzactiile de mai sus este(initial):
Contoare: A = 0, B = 0, C = 0 ; setul vid este marcat cu patrat solid,iar 1-itemset-urile sunt marcate cu cerc punctat.
Contoare: A = 2, B = 1, C = 0, AB = 0 ; schimbam A si B in patrate punctate deoarece contoarele lor au depasit minsupp(=1) si adaugam un contor pentru AB datorita faptului ca subseturile sale sunt patrate.
Contoare: A = 2, B = 2, C = 1, AB = 0, AC = 0, BC = 0 . C se transforma in patrat deoarece contorul sau a depasit minsupp. A,B,C au fost contorizate prin toate tranzactiile si le transformam in patrate solide si nu vor mai fi numarate. Se adauga un contor pentru AC si BC deoarece subseturile lor sunt patrate.
Contoare: A = 2, B = 2, C = 1, AB = 1, AC = 0, BC = 0 . AB a fost contorizat prin toate tranzactiile si suportul sau depaseste minsupp si astfel se va transforma in patrat solid. BC se va transforma si el in patrat punctat.
Contoare: A = 2, B = 2, C = 1, AB = 1, AC = 0, BC = 1 . AC si BC au fost contorizate prin toate tranzactiile. Nu vom contoriza ABC pentru ca unul dintre subseturile sale este cerc. Nu mai sunt itemset-uri punctate si algoritmul se va opri.
PSEUDOCOD
SS = {} ; // solid square (frequent)
SC = {} ; // solid circle (infrequent)
DS = {} ; // dashed square (suspected frequent)
DC = { all 1-itemsets } ; // dashed circle (suspected infrequent)
while (DS != 0) or (DC != 0) do begin
read M transactions from database into T
forall transactions tT do begin
//increment the respective counters of the itemsets marked with dash
for each itemset c in DS or DC do begin
if ( c t ) then
c.counter++ ;
for each itemset c in DC
if ( c.counter ≥ threshold ) then
move c from DC to DS ;
if ( any immediate superset sc of c has all of its subsets in SS or DS ) then
add a new itemset sc in DC ;
end
for each itemset c in DS
if ( c has been counted through all transactions ) then
move it into SS ;
for each itemset c in DC
if ( c has been counted through all transactions ) then
move it into SC ;
end
end
Answer = { c SS } ;
9. O comparatie intre algoritmii Eclat si FP-growth
9.1 Definirea problemei
Problema poate fi formulata astfel. Fie J un set de articole (item-uri). Un set X= {i1, . . . , ik} J este numit itemset, sau un k-itemset daca el contine k item-uri. O tranzactie peste J este un tuplu T=(tid,I) unde tid este identificatorul tranzactiei, iar I este un set de item-uri(itemset). O tranzactie T=(tid,I) se spune ca suporta un itemset XJ daca XI . O baza de date D ce contine tranzactii peste J este un set de tranzactii peste J. Acoperirea(cover) unui itemset X in D consta in setul de identificatori ai tranzactiilor din D ce suporta(acopera) pe X:
cover(X,D):={tid| (tid,I) D,XI}.
Suportul unui itemset X in D(baza de date ce contine tranzactiile) este numarul de tranzactii din acoperirea(cover-ul) lui X peste D:
support(X,D) = | cover(X,D) | .
Frecventa unui itemset X din D este probabilitatea ca X sa apara intr-o transactie TD:
frequency(X,D) = P(X) = support(X,D) / |D| . Am notat prin |D| = support({},D) .
Scopul este acum sa gasim toate itemset-urile frecvente, data fiind o baza de date si un prag minim de suport.
Spatiul de cautare a acestei probleme, toate subseturile lui I, este evident urias. In loc de a numara si genera deodata suporturile tuturor acestor itemset-uri, care evident nu este fezabil, cateva solutii au fost propuse pentru a realiza o cautare mai directa generand si numarand iterativ itemset-urile candidate.
Aceste solutii pot fi divizate in doua clase majore, cele care traverseaza acest spatiu de cautare prima data pe latime si cele care o fac prima data in adancime. Principala provocare pe care acesti algoritmi o infrunta este cum sa determine eficient suportul tuturor itemset-urilor candidate atinse in timpul cautarii. Principala proprietate exploatata de toti acesti algoritmi este asa-numita proprietate de monotonie, adica toate subseturile unui itemset frecvent trebuie sa fie frecvente. Astfel, daca un itemset nu e frecvent, atunci toate superseturile sale pot fi eliminate din spatiul de cautare. Insa, acesti algoritmi isi au limitarile lor, iar o „cea mai buna” solutie generala inca nu a fost identificata. Totusi, studii recente au aratat ca dintr-un punct de vedere al performantei, alegerea algoritmului dintre cei disponibili in mod curent este irelevanta pentru o arie larga de alegeri ale unui prag minim de suport. Numai daca bazele de date sunt foarte mari, cei mai multi dintre acesti algoritmi sufera in continuare de problema lipsei de memorie principala/de baza.
Mai departe va fi prezentata o comparatie foarte riguroasa a doi elgoritmi excelenti, Eclat si FP-growth, amandoi adoptand o traversare prima data pe adancime in spatiul de cautare. Aceasta comparatie va releva cateva proprietati interesante ale ambilor algoritmi. Dezavantajul major al ambilor algoritmi este acela ca cer ca baza de date sa fie stocata in memoria de baza. Daca acest lucru nu este posibil, cateva tehnici au fost propuse pentru a reduce cantitatea de memorie necesara.
Din nefericire, toate reduc in mod semnificativ performanta ambilor algoritmi. Pentru a rezolva aceasta problema, aratam ca sortand prima data lexicografic baza de date cu tranzactii, este posibil sa prezentam o adaptare a algoritmului Eclat, numit Medic(Medic este corespondentul lui Memory Effcient Discovery of Itemsets – Descoperirea de Itemset-uri cu Memorie Eficienta – iar “C” este pentru rezonanta), care foloseste mult mai putina memorie si se comporta in cea mai mare parte a timpului chiar mai bine decat predecesorul sau.
Recent rezultatele in “frequent itemset mining” sunt in principal concentrate pe gasirea numai a itemset-urilor frecvente . In mod esential, algoritmul cel mai eficient cunoscut in prezent care sa gaseasca toate itemset-urile inchise CHARM, este bazat pe corespondentul sau complet ECLAT.
9.2 ECLAT VERSUS FP-GROWTH
Primul algoritm de success propus pentru a genera toate itemset-urile frecvente de tipul adancime este algoritmul Eclat al lui Zaki. Urmatorul cel mai cunoscut algoritm de tip adancime este FP-growth propus de Han si altii. In aceasta sectiune vom explica ambii algoritmi si vom arata ca in mare parte sunt asemanatori.
Data fiind o baza de date de tranzactie D si un prag minim al suportului σ, prin F[I](D;σ) intelegem setul tuturor itemset-urilor frecvente cu acelasi prefix IJ. Principala idee folosita atat de Eclat cat si de FP-growth este ca toate itemset-urile frecvente continand item i J, dar necontinand vreun item inainte de i, (presupunand aceeasi ordine pe J), pot fi gasite asa numita i-projected database, denumita Di. Astfel, Di consta in acele tranzactii din D care contin i si din care toate item-urile dinainte de i si insusi i sunt eliminate. Intr-adevar, daca generam toate itemset-urile frecvente in Di si adaugam i tuturor, atunci gasim toate itemset-urile frecvente continand item i, dar nici un item inainte de i, in baza de date originala, D. Atat Eclat cat si FP-growth genereaza recursiv pentru fiecare item frecvent iI setul F[{i}](Di; σ ). (A se nota ca F[{}](D; σ) = F[{i}](Di; σ) contine toate itemset-urile frecvente.)
Ambii algoritmi difera unul de celalalt prin felul in care creaza recursiv si reprezinta Di. Principalul lor avantaj consta intr-o strategie foarte eficienta de calcul al suportului, comparata cu mecanismul laborios iterativ al celor mai multi algoritmi de tip latime cum este Apriori.
De dragul simplicitatii si prezentarii vom presupune ca toate item-urile care apar in baza de date ce contine tranzactiile sunt frecvente. In practica toate itemurile frecvente pot fi calculate in timpul unei scanari initiale a bazei de date, dupa care toate itemurile nefrecvente vor fi ignorate.
9.3 Eclat
Eclat transforma baza de date in formatul sau vertical. Astfel, in loc de a lista explicit toate tranzactiile, fiecare item este stocat impreuna cu cover-ul sau(adica tranzactiile in care apare item-ul respectiv). In acest fel, suportul unui itemset X poate fi usor calculat pur si simplu intersectand cover-urile a oricare dintre doua subseturi Y;ZX, astfel incat YU Z = X.
Pe linia 3, fiecare item frecvent este adaugat in setul de output. Dupa aceasta,pe liniile 4-8, pentru fiecare astfel de item frecvent i, baza de date i-projected Di este creata. Aceasta se realizeaza prima data prin gasirea fiecarui item frecvent j care apare in mod frecvent impreuna cu i.
Suportul acestui set {i; j} este calculat intersectand cover-urile ambilor itemi (linia76). Daca {i;j} este frecvent atunci j este inserat in Di impreuna cu cover-ul sau (linia 8,9). Pe linia 13, algoritmului ii este cerut recursiv sa gaseasca toate itemset-urile frecvente intr-o noua baza de date Di. A se nota ca un itemset candidat este reprezentat de fiecare set I U{i; j} la care suportul este calculat la linia 7 a algoritmului. De vreme ce algoritmul nu exploateaza din plin proprietatea de monotonie, dar genereaza un itemset candidat bazat numai pe doua dintre subseturile sale, numarul itemset-urilor candidate care sunt generate este mult mai mare comparativ cu abordarea de tip latime din Apriori. Ca o comparatie, Eclat genereaza in special itemset-uri candidate folosind numai pasul de join din Apriori, de vreme ce itemset-urile necesare pentru pasul de eliminare nu sunt disponibile.
O tehnica folosita de obicei este de a reordona itemurile in ordine de suport crescatoare pentru a reduce numarul de item-uri candidate ce sunt generate. In Eclat, o asemenea reordonare poate fi realizata la fiecare pas al recursivitatii inainte de linia 13 in algoritm. De asemenea a se nota ca la o anume adancime d, cover-urile celor mai multe k-itemseturi cu acelasi k- 1-prefix sunt stocate in memoria de baza, cu k≤ d. Datorita reordonarii item-urilor, acest numar este mic.
Recent Zaki a propus o noua abordare pentru a calcula in mod eficient suportul unui itemset folosind folosind layout-ul vertical al bazei de date. In loc de a stoca cover-ul unui k-itemset I, diferenta dintre cover-ul lui I si cover-ul lui k-1-prefix lui I este stocat, marcat de diffset lui I. Aceasta tehnica a aratat experimental ca rezulta imbunatatiri relevante ale performantei si necesita mult mai putina memorie. Totusi, algoritmul inca mai cere ca baza de date originala sa fie stocata in memoria principala.
9.4 FP-growth
FP-growth foloseste o combinatie de layout orizontal si vertical al bazei de date pentru a stoca tranzactiile in memoria principala. In loc de a stoca cover-ul pentru fiecare item in baza de date, stocheaza adevarata tranzactie din baza de date intr-o structura trie si fiecare item are o lista cu toate tranzactiile ce contin acel item. Aceasta structura noua de date este denumita FP-tree (Frequent-Pattern tree). In mod esential, toate structurile sunt stocate intr-o structura de date de tip trie. Fiecare nod stocheaza aditional un contor care retine numarul de tranzactii ce impart aceeasi ramura prin acel nod. De asemenea, un link este stocat, ducand pana la urmatoarea aparitie a respectivului item in arborele-FP, astfel incat toate aparitiile unui item in arborele-FP sunt legate impreuna. Aditional, un tabel header (header table) este folosit. Acesta contine fiecare item separat impreuna cu suportul sau si un link la prima aparitie a itemului in arborele FP.
In arborele FP, toate item-urile sunt ordonate in ordinea descrescatoarea suportului, deoarece, in acest fel, se spera ca aceasta reprezentare a bazei de date este tinuta la cele mai mici dimensiuni posibile de vreme ce toate item-urile ce apar mai frecvent sunt aranjate mai aproape de radacina arborelui FP si astfel este mai probabil sa fie impartite. De exemplu, presupunem ca se da o baza de date ce contine tranzactiile si un prag minim al suportului de 2. Prima data, suporturile tuturor item-urilor este calculat, toate item-urile nefrecvente sunt eliminate din baza de date si toate tranzactiile sunt reordonate in functie de ordinea de suport descrescatoare (de exemplu baza de date de tranzactie din tabelul de mai jos).
Arborele-FP pentru aceasta baza de date este aratat mai jos:
Dat fiind un astfel de arbore-FP, suporturile tuturor itemurilor frecvente pot fi gasite in tabelul header. Evident, arborele-FP este o reprezentare mai comprimata a bazei de date cu toate tranzactiile folosite pentru generarea itemset-urilor frecvente. Intr-adevar, fiecare lista legata ce pleaca de la un item din tabelul header de fapt reprezinta o forma comprimata a acoperirii acelui item. Pe de alta parte, fiecare ramura ce pleaca din nodul radacina reprezinta o forma comprimata a unui set de tranzactii. In afara de acest arbore FP algoritmul FP-growth este similar cu Eclat dar mai foloseste cativa pasi in plus pentru a mentine structura arborelui FP in timpul pasilor de recursivitate, in timp ce Eclat are doar nevoie sa mentina acoperirea tuturor itemset-urilor generate.
La liniile 5-7, toate item-urile frecvente sunt calculate si stocate in tabelul header pentru arborele Fp reprezentand Di. Aceasta poate fi realizata eficient urmand simplu lista legata ce pleaca de la intrarea lui i in tabelul header. Apoi, la fiecare nod, in arborele-FP isi urmeaza calea pana la nodul din radacina si creste suportul fiecarui item pe langa care trece la numarare. Apoi, la liniile 8,9, arborele-FP pentru baza de date i-projected este construit pentru acele tranzactii in care i apare, intersectat cu setul tuturor j>i, astfel incat {i;j} este frecvent. Aceste tranzactii pot fi gasite eficient urmand legaturile-nod ce pleaca de la intrarea itemului i in tabelul header si urmarind calea din fiecare astfel de nod pana la radacina arborelui-FP si ignorand toate item-urile care nu sunt in H. Daca acest nod a numarat n, atunci tranzactia este adaugata de n ori.
Desigur aceasta se implementeaza pur si simplu incrementand numararile pe calea acestei tranzactii in noul arbore-FP de n. Totusi, aceasta tehnica cere ca fiecare nod in arborele-FP sa stocheze un link la sursa sa.
Singurul avantaj principal pe care FP-growth il are fata de Eclat este ca fiecare lista , ce incepe de la un item in tabelul header reprezentand cover-ul acelui item, este stocata intr-o forma comprimata. Din nefericire, pentru a se realiza acest castig este nevoie sa se mentina o structura de date complexa si sa se realizeze multa dereferentiere, in timp ce Eclat trebuie sa realizeze intersectii scurte si rapide. De asemenea, castigul intentionat cu aceasta compresie poate fi mai mic decat s-a sperat. In Eclat cover-ul unui item poate fi implementat folosind o arie de identificatori de tranzactie. Pe de cealalta parte, in FP-growth, cover-ul unui item este comprimat folosind lista de legaturi ce pleaca din nodul sau link din tabelul header, dar fiecare nod din lista de legaturi trebuie sa-si stocheze numele, un contor, un pointer la urmatorul nod, un drum la ramurile sale si un drum la sursa sa. Prin urmare, marimea unui arbore-Fp ar trebui sa fie cel mult 20% din marimea cover-urilor din Eclat pentru a profita de comprimarea sa.
Pentru a sustine aceste observatii, am realizat cateva experimente pe o larga varietate de seturi de date.Vom prezenta rezultatele pe un set de date sintetice generat de programul pus la dispozitie de grupul de cercetare Quest la IBM Almaden, care este un set de date dens ce contine 100 000 de tranzactii a mai mult de 1000 de itemuri. De asemenea, ne raportam rezultatele la setul de date BMS-WebView-1 ce contine cateva luni de date click-stream de la un web site de e-commerce. Acesta este un set de date rasfirat ce contine 59 602 tranzactii asupra a 498 itemuri.
Tabelul urmator arata pentru aceste seturi de date lungimea totala a tuturor ariilor in Eclat (jjDjj), numarul total de noduri in FP-growth (jFP-treej) si rata de compresie corespunzatoare pe arborele-FP. Aditional, pentru fiecare intrare, aratam marimea structurilor de date in bytes si compresia corespunzatoare pe arborele-FP.
Numarul de noduri in arborele-FP, este semnificativ mai mic decat marimea bazei de date, dar cand marimea exacta a bazei de date este luata in considerare, reprezentarea arborelui-FP este adesea mai mare decat reprezentare bazata doar pe array. Mai mult, algoritmul Eclat se comporta in cea mai mare parte a timpului mai bine decat algoritmul FP-growth.
9.5 MEDIC
Daca cantitatea de memorie de baza disponibila nu este suficienta pentru a stoca o baza de date de tranzactie completa, atunci algoritmii eficienti de tip adancime nu sunt capabili de initializare . Abordarea propusa pentru rezolva aceasta problema pentru algoritmul Fp-growth este de a crea o baza de date i-projected database pe disc pentru orice item i 2 I si apoi de a mina separat fiecre baza de date proiectata. Desigur, aceasta abordare poate fi folosita pentru orice algoritm de frequent itemset mining, dar din nefericire nu este fezabila pentru baze de date mari de vreme ce marimea cumulata a tuturor bazelor de date i-projected este mai mare in ceea ce priveste magnitudinea. A se nota ca aceasta strategie sorteaza inerent intreaga baza de date. Totusi cand baza de date este sortata lexicografic folosind ordinea impusa pe itemuri, o tehnica de optimizare foarte simpla poate fi folosita pentru a reduce uzajul de memorie a algoritmului Eclat, resultand un algoritm si mai eficient pe care il numim Medic.
Fie I = { i1, i2, … ,in } toate itemurile ce apar frecvent in D in ordine de suport ascendenta. Fie T[0] ce denumeste cel mai mic item intr-o tranzactie data T tinundu-se cont de ordinea impusa
Pentru corectitudinea algoritmului, adaugam o tranzactie la sfarsitul bazei de date ce contine un nou item, denotand capatul bazei de date. In acest fel, cercul exterior mai este executat pentru ultima oara.
Esential, algoritmul genereaza toate itemseturile continand item iimediat ce nu mai sunt tranzactii ce contin i. Mai specific, algoritmul proceseaza tranzactiile pe rand, in ordine lexicografica. Pentru fiecare item ice este ordonaat inaintea celui mai mic item in tranzactia curenta, stim ca nu mai poate apare in baza de date si, de aici, putem genera deja toate itemseturile frecvente continand i. Aste este exact ceea ce se intampla pe liniile 5-13. Aditional, dupa generarea tuturor acestor itemseturi, cover-ul lui i poate fi eliminat din memoria de baza, de vreme ce nu mai este cerut de algoritm (linia 14). Dupa aceasta, identificatorul de tranzactie a tranzactiei curente este adaugat la cover-urile tuturor itemurilor ce apar in tranzactie.
Evident acest algoritm foloseste mult mai putina memorie decat Eclat deoarece baza de date nu este niciodata incarcata in intregime in memoria de baza. Intr-adevar, in timp ce Eclat stocheaza initial toate cover-urile tuturor itemurilor in memoria de baza, Medic stocheaza numai cover-urile tuturor itemurilor de pana la tranzactia curenta si ii sterge imediat ce itemul nu mai poate apare intr-o tranzactie viitoare.
Reordonand initial toate itemurile in ordine crescatoare de suport, ne asiguram ca aceasta stergere a cover-urilor se petrece rapid, dar de asemenea ne asiguram ca cover-urile itemurilor foarte frecvente sunt folosite in timp ce cele mai multe cover-uri au fost deja sterse.
A se nota ca algoritmul se comporta in general mult mai bine, cand sortarea bazei de date nu este luata in considerare, de vreme ce intersectiile de care are nevoie pentru a realiza numararea suportului itemseturilor sunt aplicate la tidlist-uri mai scurte (sau diffset-uri).
10. IMPLEMENTAREA ALGORITMULUI APRIORI
Implementarea algoritmului Apriori s-a realizat in C++ folosindu-se ,ca si in cazul celorlalti algoritmi , o clasa pentru citirea din fisier a tranzactiilor, o clasa ce defineste item-ul si proprietatile sale, una pentru algoritmul insusi si un fisier de test a algoritmului.
Fisierul data.h
Contine doua clase. Prima este clasa “Transaction” ce defineste o tranzactie. O tranzactie este caracterizata(pe langa constructorul specific) de o lungime si bineinteles de un vector de intregi in care vor fi salvate item-urile tranzactiei citite din fisier. Forma unei tranzactii citite din fisier va fi de forma: “100 121 238 456 245 143 87 “.
A doua clasa este clasa “Data” cu ajutorul careia se citesc din baza de date una cate una tranzactiile. Clasa contine patru membri:
– in si fn sunt doi pointeri unul FILE si unul char ca puncteaza catre fisierul ce se doreste a fi deschis pentru citirea tranzactiilor,respectiv retine numele lui.
– current ce este folosit pentru a numara tranzactiile
– type ce retine tipul fisierului din care se face citire. Reamintim ca cele patru tipuri sunt: format binar si ASCII generat de generatorul QUEST, enumerativ si o alta versiune ASCII generat cu QUEST.
Fisierul data.cpp
Implementeaza functiile ale caror antete se gasesc in data.h . Realizeaza ,daca se poate, deschiderea fisierului cu tranzactii in vederea citirii lor. Si in functie de tipul fisierului realizeaza citirea tranzactiilor ,cate una, si returneaza tranzactia citita. Daca s-a ajuns la sfarsitul fisierului se va relua citirea.Controlul numarului de tranzactii citite nu se face de aici ci din fisierul caracteristic fiecarui algoritm( in cazul nostru dic.cpp).
Fisierul item.h
Incearca sa reprezinte cat mai fidel, minim,dar strict necesar caracteristicile unui item. Contine urmatorii membrii:
id : identificatorul item-ului.
support : suportul item-ului,cel care contorizeaza de cate
ori apare item-ul in tranzactii.
– children : container-ul ce va contine copiii item-ului(in fond este un container de alte item-uri)
Functii:
– int getId(): returneaza id-ul item-ului
– int Increment : incremeneteaza support-ul cu o valoare (default 1)
– set<Item> *makeChildren() – creeaza container-ul children al item-ului daca acesta nu exista sau il returneaza daca exista
– set<Item> *getChildren() – returneaza ‘children’ .
– int deleteChildren() – sterge recursiv copiii item-ului
-int getSupport() – returneaza support-ul
– bool operator<(const Item &i) : rescrierea operatorului ‘<’ folosit pentru comparatia item-urile in functie de id.
Fisierul item.cpp
Implementeaza functiile makeChildren si deleteChildren. Prima daca nu exista container-ul ‘children’ il creeaza ,iar daca exista il returneaza pe cel existent. A doua functie(deleteChildren) sterge recursiv copiii item-ului si seteaza pointerul ‘children’ la null.
Fisierul apriori.h
Incearca sa confere utilizatorului o cat mai fidela si eficienta implementare a trie-ului. Contine urmatorii membrii:
– trie : este trie-ul folosit de algoritm;
– minsup : suportul minim ce trebuie depasit de item-uri pentru a fi considerate
frecvente ;
– setsout : buffer ce ajuta la scrierea in fisier a rezultatelor;
– data : membru de tip ‘Data’ folosit la citirea tranzactiilor din fisier;
– verbose : flagul ce da aproba sau nu afisarii
– remap : vector folosit pentru ordonarea si renumerotarea item-urilor
– relist : container folosit la fel ca si remap
– countType : tipul de numarare a candidatilor
Functiile din acest fisier vor fi comentate in descrierea fisierului apriori.cpp
Fisierul apriori.cpp
Acest fisier este caracteristic fiecarui algoritm si incearca o implementare eficienta a algoritmului apriori.
int generateSets() – este functia declansatoare a algoritmului.
Cat timp mai exista item-uri au fost generate
pas++
daca pas > 2 atunci
generateCandidates()
pruneNodes(pas)
countCandidates(pas)
prundeCandidates(pas)
Daca pas == 1 atunci
ReOrder()
gata
int countCandidates(pas) – creeaza item-urile simple si incrementeaza suportul item-urile ca se contorizeaza;
daca pas == 1 atunci
pentru fiecare tranzactie citita din fisier
incremeneteaza suportul trie-ului
daca un item simplu nu exista atunci insereaza item-ul in trie
altfel incrementeaza suportul lui
altfel
pentru fiecare tranzactie citita din fisier
Reordoneaza tranzactia eliminand item-urile ce nu exista
daca pas<=2 atunci processTransaction(pas,children of trie,tranz,0,1))
altfel processTransaction2(pas,children of trie,tranz,0,1)
returneaza numarul de tranzactii procesate
int processTransaction(pas,itemset,tranzactie,poz,depth) – incrementeaza suportul item-urilor ce apar intr-o tranzactie;
(creata pentru item-urile de pe nivelul 2, realizand si constructia trie-ului pentru acest nivel)
daca items==null return 0
pentru fiecare item al tranzactiei
daca item-ul tranzactiei exista printre item-urile simple ale trie-ului atunci
daca depth==pas atunci incrementeaza suportul item-ului
altfel
daca depth==1 si level==2 atunci makeChildren()
processTranzaction(pas,children,t,poz+1,depth+1)
altfel daca depth==2 si pas==2 atunci
daca item-ul din tranzactie este si item simplu in trie atunci
insereaza-l la copii item-ului curent
int processTransaction2(pas,t,items,poz,depth) incrementeaza suportul item-urilor ce apar intr-o tranzactie;
daca items==null return 0
pentru fiecare item i din items
daca un item din tranzactie == i atunci
daca depth==pas atunci incrementeaza suportul item-ului
altfel processTranzaction2(pas,t,children of i,poz+1,depth+1)
return numarul de item-uri carora le-a fost incrementat suportul
int generateCandidates() – apeleaza generateCandidates cu parametrii
seteaza ca trie-ul sa nu mai fie contorizat dupa prima
parcurgere a fisierului cu tranzactii;
int generateCandidates(pas,items,depth,current) – genereaza posibili candidati pe baza unor item-uri din trie si a unor criterii(daca un item are toti copiii,subseturile sale, item-uri frecvente atunci devine si el un potential item nefrecvent ce va fi contorizat.
daca items==null return 0
daca depth==level-1 atunci
pentru fiecare item i din container-ul curent items
pentru fiecare item j!=i din items
salveaza calea in current
daca checkSubsets(pas,current,children of trie ,0,1) atunci
insereaza in copiii lui i pe j
altfel pentru fiecare item i din items
salveaza calea in current
generateCandidates(pas, children of i,depth+1,current)
returneaza numarul de candidati generati
bool checkSubsets(current) – verifica daca subseturile unui itemset sunt frecvente.
parcurge recursiv trie-ul pe baza lui ‘current’ ce contine o anumita cale.
daca toate caile ce se pot forma sunt exista(sunt frecvente) atunci returneaza true
altfel return false
int pruneNodes(pas) – apel pentru pruneNodes(pas,children of trie,1)
int pruneNodes(pas,items,depth) – elimina recursic nodurile ce nu au copiii .
daca items==null atunci return 0
nodes = 0
daca pas==depth atunci nodes = numarul de copii ai lui items
altfel pentru fiecare item i din items
nr_nodes=pruneNodes(pas, children of i, depth+1)
daca nr_nodes >0 atunci nodes++
else deleteChildren( i )
return nodes
int pruneCandidates(pas) – apel pruneCandidiates(pas,items,depth,current)
int pruneCandidiates(pas,items,depth,current)
daca items==null atunci return 0
nodes=0; nr_nodes=0
pentru fiecare item i din items
salveaza calea in current
daca pas=depth atunci
daca support of i < minsup atunci
deleteChildren ( i )
altfel
printSet( i ,current,depth)
nodes++
altfel
nr_nodes=pruneNodes(pas, children of i, depth+1)
daca nr_nodes >0 atunci nodes++
else deleteChildren( i )
return nodes
void ReOrder() – realizeaza o rearanjare a item-urilor simple. Este apelata doar o singura data la inceput si renumeroteaza id-urile item-urile in ordinea descrescatoare a suportului. Acest fapt mareste viteza de executie ulterior
trie-ul va avea alte id-uri renumerotate. Se foloseste relist si remap.
remap[i] <- id-ul vechi
relist . oldid <- id-ul vechi
relist. id <- noul id i
trie vor fi inserate item-uri cu noile id-uri consecutive i si suport-ul corespunzator id-urilor vechi.
void printSet(itemset,current,depth) – functia care scrie in fisierul cu rezultate detaliile despre item-uri(id-uri si suport)
11. IMPLEMENTAREA ALGORITMULUI DIC
(Dynamic Itemset Counting)
Implementarea algoritmului DIC(Dynamic Itemset Counting) s-a realizat in C++ folosindu-se ,ca si in cazul celorlalti algoritmi , o clasa pentru citirea din fisier a tranzactiilor, o clasa ce defineste item-ul si proprietatile sale, una pentru algoritmul insusi si un fisier de test a algoritmului.
Fisierul data.h
Contine doua clase. Prima este clasa “Transaction” ce defineste o tranzactie. O tranzactie este caracterizata(pe langa constructorul specific) de o lungime si bineinteles de un vector de intregi in care vor fi salvate item-urile tranzactiei citite din fisier. Forma unei tranzactii citite din fisier va fi de forma: “100 121 238 456 245 143 87 “.
A doua clasa este clasa “Data” cu ajutorul careia se citesc din baza de date una cate una tranzactiile. Clasa contine patru membri:
– in si fn sunt doi pointeri unul FILE si unul char ca puncteaza catre fisierul ce se doreste a fi deschis pentru citirea tranzactiilor,respectiv retine numele lui.
– current ce este folosit pentru a numara tranzactiile
– type ce retine tipul fisierului din care se face citire. Reamintim ca cele patru tipuri sunt: format binar si ASCII generat de generatorul QUEST, enumerativ si o alta versiune ASCII generat cu QUEST.
Fisierul data.cpp
Implementeaza functiile ale caror antete se gasesc in data.h . Realizeaza ,daca se poate, deschiderea fisierului cu tranzactii in vederea citirii lor. Si in functie de tipul fisierului realizeaza citirea tranzactiilor ,cate una, si returneaza tranzactia citita. Daca s-a ajuns la sfarsitul fisierului se va relua citirea.Controlul numarului de tranzactii citite nu se face de aici ci din fisierul caracteristic fiecarui algoritm( in cazul nostru dic.cpp).
Fisierul item.h
Incearca sa reprezinte cat mai fidel, minim,dar strict necesar caracteristicile unui item. Contine urmatorii membrii:
id : identificatorul item-ului.
support : suportul item-ului,cel care contorizeaza de cate
ori apare item-ul in tranzactii.
flag : seteaza starea unui item.
‘a’ – nefrecvent,dar se contorizeaza(cerc punctat)
‘b’ – frecvent si se contorizeaza(patrat punctat)
‘c’ – nefrevent si nu se mai contorizeaza(cerc solid)
‘d’ – frecvent si nu se mai contorizeaza(patrat solid)
start : seteaza numarul tranzactiei in care a aparut prima
data item-ul(pentru a cunoaste si momentul la care sa oprim
contorizarea item-ului)
– children : container-ul ce va contine copiii item-ului(in fond este un container de alte item-uri)
Functii:
– int getId(): returneaza id-ul item-ului
– bool Counting(): indica daca item-ul se contorizeaza sau nu (flag e ‘a’ sau ‘b’)
– bool Frequent() : indica daca item-ul este frecvent sau nu (flag e ‘b’ sau ‘d’)
– void setFlag(char c) : seteaza flag-ul la o valoare dorita
– int getStart() : returneaza valoarea membrului ‘start’
– int Increment : incremeneteaza support-ul cu o valoare (default 1)
– set<Item> *makeChildren() – creeaza container-ul children al item-ului daca acesta nu exista sau il returneaza daca exista
– set<Item> *getChildren() – returneaza ‘children’ .
– int deleteChildren() – sterge recursiv copiii item-ului
-int getSupport() – returneaza support-ul
– bool operator<(const Item &i) : rescrierea operatorului ‘<’ folosit pentru comparatia item-urile in functie de id.
Fisierul item.cpp
Implementeaza functiile makeChildren si deleteChildren. Prima daca nu exista container-ul ‘children’ il creeaza ,iar daca exista il returneaza pe cel existent. A doua functie(deleteChildren) sterge recursiv copiii item-ului si seteaza pointerul ‘children’ la null.
Fisierul DIC.h
Incearca sa confere utilizatorului o cat mai fidela si eficienta implementare a trie-ului. Contine urmatorii membrii:
– trie : este trie-ul folosit de algoritm;
– minsup : suportul minim ce trebuie depasit de item-uri pentru a fi considerate
frecvente ;
– setsout : buffer ce ajuta la scrierea in fisier a rezultatelor;
– data : membru de tip ‘Data’ folosit la citirea tranzactiilor din fisier;
– tnr : numara tranzactii;
– counting : cate item-uri se contorizeaza la un moment dat
– frequent : numara cate item-uri sunt frecvente (la fiecare pas)
Functiile din acest fisier vor fi comentate in descrierea fisierului DIC.cpp
Fisierul DIC.CPP
Acest fisier este caracteristic fiecarui algoritm si incearca o implementare eficienta a algoritmului DIC.
int generateSets() – este functia declansatoare a algoritmului.
Cat timp mai exista item-uri ce pot fi contorizate executa
countCandidates()
generateCandidates()
afisari specifice fiecarui pas(item-uri generate la acest pas, item-uri generate in total si numarul de item-uri frecvente dupa fiecare pas)
gata
int countCandidates() – creeaza item-urile simple si incrementeaza suportul item-urile ca se contorizeaza;
cat timp mai pot citi din fisier si nu am citit M tranzactii
citeste tranzactia si incrementeaza nr de tranzactii
daca trie-ul este cerc sau patrat punctat
daca gasesc in tranzactie vreun item ce nu exista in trie
atunci adauga item simplu la trie
incrementeaza nr de item-uri contorizate
incrementeaza nr de item-uri generate
processTransaction()
daca tnr%M == 0 atunci break
daca tnr%M != 0 atunci tnr=0
return numarul de item-uri generate(cele simple)
int processTransaction() – incrementeaza suportul item-urilor ce apar intr-o tranzactie;
pentru fiecare item de pe un nivel(copiii unui alt item)
daca un item coincide cu un item al tranzactiei
atunci incrementeaza suportul item-ului respectiv
apeleaza recursiv fctia pentru urmatorul item din tranzactie si copiii item-ului gasit.
int generateCandidates() – apeleaza generateCandidates cu parametrii
seteaza ca trie-ul sa nu mai fie contorizat dupa prima
parcurgere a fisierului cu tranzactii;
int generateCandidates(trie,current,pos) – genereaza posibili candidati pe baza unor item-uri din trie si a unor criterii(daca un item are toti copiii,subseturile sale, item-uri frecvente atunci devine si el un potential item nefrecvent ce va fi contorizat.
pentru fiecare item simplu(copiii root-ului ) din trie executa
salveaza id-ul pe o pozitia curenta in vectorul ’ current’
daca item-ul se contorizeaza(este cerc/patrat punctat -> a/b) atunci
daca a fost contorizat prin toate tranzactiile atunci
daca are suport > minsup atunci
daca nu era frecvent atunci incrementeaza contorul de item-uri frecvente
scrie in fisier itemset-ul frecvent
seteaza flag-ul itemset-ului ca fiind ‘d’ (patrat solid)
altfel seteaza flagul itemset-ului la ‘c’ (cerc solid)
decrementeaza contorul pt item-uri frecvente
altfel daca suport > minsup atunci
incrementeaza contorul de item-uri frecvente
seteaza flag-ul itemset-ului la ‘b’ (patrat punctat)
daca item-ul este frecvent (patrat – > ‘b’ sau ‘d’) atunci
generateCandidates(item->allChildren(),current,pos+1)
checkSubsets pentru toti fratii item-ului curent
returneaza numarul de itemset-uri generate
bool checkSubsets(current) – verifica daca subseturile unui itemset sunt frecvente.
parcurge recursiv trie-ul pe baza lui ‘current’ ce contine o anumita cale.
daca fiecare cale este frecventa atunci returneaza true
altfel false
void printSet() – functia care scrie in fisierul cu rezultate detaliile despre item-uri(id-uri si suport)
12. Implementarea Algoritmului Eclat
item.h
Contine doua clase Item si fItem .
Clasa Item:
transactions – container de tip int pentru a retine identificarii tranzactiilor in care apare un item ;
id – id-ul item-ului
Clasa fItem – reprezinta clasa nodului central (al trie-ului)
transactions – container de tip int pentru a retine identificarii tranzactiilor in care apare un item ;
id – id-ul item-ului
operatorul < este rescris facandu-se o comparare intre id-urile item-urilor.
eclat.h
Contine membrii
minsup – pragul minim al suportului
data – pentru citirea tranzactiilor din fisier
out – de tipul FILE – fisierul ce contine rezultatele
eclat.cpp
mine() – citeste tranzactiile din fisier , creeaza item-urile simple si lanseaza in executie creearea trie-ului
pentru fiecare tranzactie citita din fisier
pentru fiecare item al tranzactiei
daca nu exista item-ul in trie atunci adauga item
altfel introdu in vectorul de tranzactii al item-ului id-ul tranzactiei curente
pentru fiecare nod (item simplu) al trie-ului
daca numarul de tranzactii al nodului > minsup
atunci adauga item in noul trie (= allitems)
start_clock()
grow(allitems, nr_tranzactii)
grow ( items, supp ) – afla itemset-urile frecvente pentru nivelul 2 si declanseaza formarea trie-ului in adancime
cat timp mai sunt item-uri in items
salveaza in itemset[0] id-ul item-ului curent si in itsupp numarul de tranzactii
afisarea itemset-ului frecvent
daca itsupp<supp atunci
pentru fiecare item j din items cu j>i
realizeaza intersectia celor doua liste de tranzactii (i si j)
daca perechea (i,j) este frecventa atunci adaug-o in children
grow(children, itsupp, itemset, 2)
sterge item curent din items
grow ( items, supp,itemset,depth ) – realizeaza creearea trie-ului in adancime pentru fiecare item.
cat timp mai sunt item-uri in items
salveaza in itemset[depth-1] id-ul item-ului curent si in itsupp supp – numarul de tranzactii al item-ului curent
afisarea itemset-ului frecvent
daca itsupp<supp atunci
pentru fiecare item j din items cu j>i
realizeaza intersectia celor doua liste de tranzactii (i si j)
daca perechea (i,j) este frecventa atunci adaug-o in children
grow(children, itsupp, itemset,depth+1)
sterge item curent din items
print(itemset,current) – afisarea unui set de item-uri pana la o anumita adancime
13. Rularea aplicatiei
Cum se ruleaza: apriori | fpgrowth | eclat | dic datafile datatype minsup [M pentru DIC] [fis_out]
datatype = 1 pentru fisier binar de date de tipul Quest
datatype = 2 pentru fisier ascii de date de tipul Quest
datatype = 3 pentru fisier de tip „flat” (toate item-urile tranzactiilor sunt pe o singura linie)
datatype = 4 pentru versiunea ascii a fisierului binar de date de tipul Quest
Minsup nu este oun prag relativ,ci un numar natural cuprins intre 1 si numarul de tranzactii.
Ex: daca nr de tranzactii=8900, minsup=381.
Toate item-urile ce apar in fisierul de date trebuie sa fie numere naturale.
Cele patru posibile formate ale fisierelor de date de intrare:
Quest datagenerator binary
(http://www.almaden.ibm.com/software/quest/Resources/index.shtml)
Fiecare linie contine: <CustID, TransID, NumItems,List-Of-Items> , unde
CustID – customer id
TransID – transaction id
NumItems – numarul de item-uri
List-Of-Items – lista de item-uri, toti fiind intregi pe 4 octeti
Quest datagenerator ascii
(http://www.almaden.ibm.com/software/quest/Resources/index.shtml)
Fiecare linie contine: <CustID, TransID, Item> , intregi separati de spatii
Flat
Fiecare linie contine o lista de intregi separate prin spatii si terminate cu ‘\n’
O linie goala terminata cu ‘\n’ este considerata o tranzactie vida
versiunea ascii a fisierului binar de date de tipul Quest
Fiecare linie contine: <CustID, TransID, NumItems,List-Of-Items> , intregi separati de
spatii
14. Fisierul cu rezultate
Itemset-urile frecvente pot fi scrise intr-un fisier de iesire(posibilitate optionala) introdus la linia de comanda. Daca se doreste acest lucru, toate itemset-urile vor fi afisate in fisier (lista de item-uri ce formeaza itemset-ul) impreuna cu suportul lor.
De exemplu: 1 2 3 (100) inseamnca ca itemset-ul format din item-urile 1,2,3 apare in 100 tranzactii ale bazei de date
In timpul executiei algoritmului Apriori pe ecran vor fi afisate cateva statistici.
Exemplu
1 497 59603 [0.09s] 343 [0s] // 497 item-uri candidate, 59603 tranzactii si 343 item-uri frecvente
2 26362 [0.29s] 1573 [0.01s] // 26362 tranzactii and 1573 2-itemset-uri frecvente
3 9793 [0s] 8956 [0.22s] 1492 [0s] // 9793 candidati 3-itemset-uri, 8956 tranzactii and 1492
3-itemset-uri frecvente
…
3991 0.97 //totalul itemset-urilor frecvente si timpul de executie
(9219)
13 (suport=377)
12 (suport=177)
11 (suport=349)
10 (suport=354)
9 (suport=416)
7 (suport=126)
6 (suport=108)
5 (suport=206)
4 (suport=203)
3 (suport=107)
2 (suport=126)
1 (suport=250)
873 936 (suport=148)
852 883 (suport=146)
781 986 (suport=106)
751 897 (suport=130)
726 950 (suport=138)
721 986 (suport=153)
700 950 (suport=219)
689 913 (suport=109)
674 970 (suport=109)
666 950 (suport=136)
…………
568 930 (suport=138)
562 803 (suport=101)
562 695 (suport=102)
560 724 (suport=130)
551 725 (suport=109)
549 948 (suport=137)
549 844 (suport=182)
549 759 (suport=140)
549 735 (suport=137)
549 727 (suport=133)
549 621 (suport=142)
546 751 (suport=102)
542 950 (suport=205)
542 793 (suport=109)
542 704 (suport=178)
In timpul executiei algoritmului Eclat pe ecran vor fi afisate cateva statistici.
Exemplu:
reading 59603 transactions [0.1s] // se citesc un numar de tranzactii
removing infrequent items [0s] //eliminare item-urilor nefrecvente
generating frequent sets [0.78s] //generarea set-urile frecvente
3991 0.88 //totalul itemset-urilor frecvente si timpul de executie
Iata cum arata un fisier cu rezultate dupa executia algoritmului Eclat:
(9219)
237 (100)
739 (100)
352 (101)
439 (102)
676 (102)
167 (103)
299 (103)
497 (104)
625 (105)
212 (106)
977 (106)
3 (107)
555 (107)
584 (107)
143 584 (100)
584 920 (100)
584 840 (101)
584 886 (101)
788 (107)
832 (107)
6 (108)
68 (108)
741 (108)
470 (111)
88 (113)
…….
36 223 398 621 735 816 (108)
36 398 735 816 948 (108)
36 398 621 735 816 948 (108)
36 398 621 735 816 (111)
36 223 398 816 (111)
36 223 398 816 948 (109)
36 223 398 621 816 948 (109)
36 223 398 621 816 (111)
36 398 816 948 (111)
36 398 621 816 948 (111)
36 398 621 816 (114)
398 735 816 (116)
398 735 816 844 (112)
398 549 735 816 844 (108)
223 398 549 735 816 844 (105)
223 398 549 735 816 844 948 (104)
223 398 549 621 735 816 844 948 (104)
223 398 549 621 735 816 844 (105)
398 549 735 816 844 948 (106)
398 549 621 735 816 844 948 (106)
398 549 621 735 816 844 (108)
223 398 735 816 844 (109)
223 398 735 816 844 948 (107)
223 398 621 735 816 844 948 (107)
……..
150 873 (134)
150 531 873 (120)
150 531 (210)
107 (478)
107 296 (182)
107 172 296 (162)
107 172 296 700 (149)
107 172 296 700 950 (142)
107 172 296 313 700 950 (136)
107 172 296 313 700 (143)
107 172 296 950 (153)
107 172 296 313 950 (146)
107 172 296 313 (155)
107 296 700 (163)
107 296 700 950 (153)
107 296 313 700 950 (146)
107 296 313 700 (155)
107 296 950 (167)
107 296 313 950 (159)
107 296 313 (170)
107 172 (200)
In timpul executiei algoritmului FP-growth pe ecran vor fi afisate cateva statistici.
Exemplu
items read [0.12s] //citirea item-urilor
items reordered and pruned [0s] // reordonarea si eliminarea item-urile
FPtree constructed [0.3s] //Se construieste FP-growth
Frequent sets generated [0.57s] // seturile frecvente sunt generate
3991 0.99 //totalul itemset-urilor frecvente si timpul de executie
15. Aspecte Experimentale
Am implementat algoritmul Apriori folosind optimizarea generarii 2-itemset-urilor candidate dinamic. Aditional , am implementat algoritmii Eclat și Fp-growth așa cum a fost prezentat in sectiunea anterioara. Toti acești algoritmi au fost implementati in C++ folosind diferite structuri de date puse la dispozitie de C++ Standard Template Library.
Primul comportament interesant poate fi observat in experimentele pentru datele de tip coș. Intr-adevar, Eclat se comporta mai rau decat ceilalti algoritmi. Totuși, acest comportament a fost prevazut de vreme ce numarul item-urilor frecvente din datele din coș este foarte mare și, de aceea, o cantitate imensa de 2-itemseturi candidat este generata. Ceilalti algoritmi folosesc generarea dinamica a 2-itemseturi candidate rezultand performante mult mai bune. Un rezultat remarcabil este ca Apriori se comporta mai bine decat Fp-growth pentru setul de date de tip basket. Acest rezultat este datorat depașirii (overhead-ului) creat de mentinerea structurii FP-tree, in timp ce updatarea suporturilor tuturor itemseturilor candidate continute in fiecare transformare este realizata foarte rapid datorita rasfirarii acestui set de date.
Pentru toate pragurile minime de suport mai mari de 40, diferentele in performante sunt neglijabile și sunt in principal datorate initializarii și distrugerii rutinelor structurilor de date folosite. Pentru praguri de suport foarte joase, Eclat in mod evident depașește in performante ceilalti algoritmi. Motivul acestei performante scazute a lui Apriori este datorat unor tranzactii foarte largi pentru care procedura genratiei de subseturi pentru numararea suporturilor tuturor itemseturilor candidate consuma cea mai mare parte a timpului. Pentru a sustine aceasta afirmatie am realizat experimente editionale care au aratat ca numai 34 de tranzactii continand mai mult de 100 de itemuri frecvente a consumat cea mai mare parte a timpului in timpul numararii suporturilor tuturor itemseturilor candidat cu marimi intre 5 și 10. De exemplu, numararea tuturor suporturilor itemseturilor-7 dureaza 10 secunde din care 9 au fost folosite pentru aceste 34 de tranzactii.
Date de tip „basket”
Date : T40I10D100K.data
Date de tip “mushroom”
De asemenea, datele ciuperca arata niște rezultate interesante. Diferentele de performanta ale lui Eclat și Fp-growthsunt neglijabile și din nou sunt rezultate in principal din cauza diferentelor in initializare și distrugere. Evident, din cauza dimensiunilor reduse a bazei de date, amandoua ruleaza foarte repede. Pe de cealalta parte, Apriori ruleaza extrem de incet deoarece fiecare tranzactie contine exact 23 de itemuri din care multe au suporturi foarte mari.
16. Bibliografie
Bart Goethals – PhD, post-doctoral researcher Helsinki Institute for Information Technology (HIIT) Basic Research Unit (BRU)
R. Agrawal, H. Mannila, R. Srikant, H. Toivonen, and A.I. Verkamo –
“Fast discovery of association rules.Advances in Knowledge Discovery and Data Mining”;
R. Agrawal and R. Srikant. Quest Synthetic Data Generator. IBM Almaden Research Center, San Jose, California, http://www.almaden.ibm.com/cs/quest/syndata.html.
R. Agrawal and R. Srikant. "Fast Algorithms for Mining Association Rules". Proc. of the 20th Int'l Conference on Very Large Databases, Santiago, Chile, September 1994 ,
http://www.almaden.ibm.com/software/quest/Publications/papers/vldb94.pdf
R. Agrawal, A. Arning, T. Bollinger, M. Mehta, J. Shafer and R. Srikant. "The Quest Data Mining System". Proc. of the 2nd Int'l Conference on Knowledge Discovery in Databases and Data Mining, Portland, Oregon, August 1996.
http://fimi.cs.helsinki.fi/data/ – bazele de date cu tranzactii
Anexa A Surse program
Toate implementarile au in comun un fisier (clasa) ce realizeaza citirea din fisier a tranzactiilor. Va fi prezentat o singura data la inceput.
data.h
#include <stdio.h>
class Transaction
{
public:
Transaction(int l) : length(l) {t = new int[l];}
Transaction(const Transaction &tr);
~Transaction(){delete [] t;}
int length;
int *t;
};
class Data
{
public:
Data(char *filename, int t=0);
~Data();
Transaction *getNext();
private:
Transaction *getNextAs();
Transaction *getNextAsFlat();
Transaction *getNextAsQuest();
Transaction *getNextBin();
FILE *in;
char *fn;
int current;
int type;
};
data.cpp
#include <vector>
using namespace std;
#include "data.h"
Transaction::Transaction(const Transaction &tr)
{
length = tr.length;
t = new int[tr.length];
for(int i=0; i< length; i++) t[i] = tr.t[i];
}
Data::Data(char *filename, int t)
{
fn = filename;
type = t;
current=0;
if(type>1) in = fopen(fn,"rt");
else in = fopen(fn,"rb");
}
Data::~Data()
{
if(in) fclose(in);
}
Transaction *Data::getNext()
{
Transaction *t=0;
switch(type){
case 1: t= getNextBin(); break;
case 2: t= getNextAs(); break;
case 3: t= getNextAsFlat(); break;
case 4: t= getNextAsQuest(); break;
}
if(t) current++;
else {
rewind(in);
current=0;
}
return t;
}
Transaction *Data::getNextAs()
{
Transaction *t;
int tid, item, i, dummy;
vector<int> list;
static int cur=0,prev=-1;
static bool begin=true;
if(feof(in)) {
begin=true;
prev=-1;
return 0;
}
if(!begin) list.push_back(cur);
else begin=false;
while(true) {
fscanf(in, "%d %d %d",&dummy, &tid, &item);
if(feof(in)) {
int size=list.size();
t = new Transaction(size);
for(i=0; i<size; i++) t->t[i] = list[i];
list.clear();
return t;
}
else if(prev<0) prev=tid;
else if(tid != prev){
prev = tid;
cur = item;
int size=list.size();
t = new Transaction(size);
for(i=0; i<size; i++) t->t[i] = list[i];
list.clear();
return t;
}
list.push_back(item);
}
}
Transaction *Data::getNextAsFlat()
{
vector<int> list;
char c;
// read list of items
do {
int item=0, pos=0;
c = getc(in);
while((c >= '0') && (c <= '9')) {
item *=10;
item += int(c)-int('0');
c = getc(in);
pos++;
}
if(pos) list.push_back(item);
}while(c != '\n' && !feof(in));
// if end of file is reached, rewind to beginning for next pass
if(feof(in)){
rewind(in);
return 0;
}
// Note, also last transaction must end with newline,
// else, it will be ignored
// sort list of items
// sort(list.begin(),list.end());
// put items in Transaction structure
Transaction *t = new Transaction(list.size());
for(int i=0; i<int(list.size()); i++)
t->t[i] = list[i];
return t;
}
Transaction *Data::getNextAsQuest()
{
int tmptid, tid,l,i;
Transaction *t;
fscanf(in,"%d %d %d",&tmptid,&tid,&l);
if(feof(in)) return 0;
t = new Transaction(l);
for(i=0; i<l; i++) fscanf(in,"%d",&t->t[i]);
return t;
}
Transaction *Data::getNextBin()
{
int tmptid, tid,l,i;
Transaction *t;
fread(&tmptid,4, 1,in);
if(feof(in)) return 0;
fread(&tid,4, 1,in);
fread(&l,4, 1,in);
t = new Transaction(l);
for(i=0; i<l; i++) fread(&t->t[i],4, 1,in);
return t;
}
Algoritmul FP-growth
item.h
#include <set>
using namespace std;
class Item;
class Item_
{
public:
Item_();
~Item_();
int id;
int supp;
set<Item> *children;
Item_ *parent;
Item_ *nodelink;
};
class Item
{
public:
Item(int s, Item_ *p);
Item::Item(const Item& i);
~Item();
int getId() const {return item->id;}
int getSupport() const {return item->supp;}
set<Item> *getChildren() const {return item->children;}
set<Item> *makeChildren() const;
Item_ *getItem() const {return item;}
Item_ *getNext() const {return item->nodelink;}
void setNext(Item_ *i) const {item->nodelink = i;}
bool isFrequent(int ms) const {return item->supp >= ms;}
void Increment(int i=1) const {item->supp += i;}
void removeChildren() const;
bool operator< (const Item &i) const {return getId() < i.getId();}
private:
Item_ *item;
};
item.cpp
#include <stdio.h>
#include "item.h"
Item_::Item_()
{
supp = 0;
parent = 0;
nodelink = 0;
id = 0;
children = 0;
}
Item_::~Item_()
{}
Item::Item(int s, Item_ *p)
{
item = new Item_();
item->id = s;
item->parent = p;
}
Item::Item(const Item& i)
{
Item_ *tmp = i.getItem();
item = new Item_();
item->id = tmp->id;
item->parent = tmp->parent;
item->children = tmp->children;
item->nodelink = tmp->nodelink;
item->supp = tmp->supp;
}
Item::~Item()
{
delete item;
}
set<Item> *Item::makeChildren() const
{
if(item->children==0) item->children = new set<Item>;
return item->children;
}
void Item::removeChildren() const
{
set<Item> *items = item->children;
for(set<Item>::iterator it = items->begin();it != items->end(); it++) it->removeChildren();
delete item->children;
item->children = 0;
}
fptree.h
#include <set>
using namespace std;
class Element
{
public:
Element(int s, int i) : support(s), id(i){}
int support;
int id;
bool operator< (const Element &e) const {return support > e.support;}
};
class FPtree
{
public:
FPtree();
~FPtree();
int processTransaction(Transaction *t, int times=1);
int processItems(Transaction *t, int times=1);
void setMinsup(int ms) {minsup = ms;}
int grow(int *current, int depth);
void ReOrder();
int Prune();
void setOutput(FILE *of) {out =of;}
void print(int *itemset, int il, int *comb, int cl, int support, int spos=0, int depth=0, int *current=0);
static int *remap;
static set<Element> *relist;
private:
set<Item> header;
set<Item> *root;
int minsup;
unsigned nodes;
bool singlepath;
FILE *out;
};
fptree.cpp
#include <iostream>
#include <stdio.h>
#include <set>
using namespace std;
#include "data.h"
#include "item.h"
#include "fptree.h"
int *FPtree::remap = 0;
set<Element> *FPtree::relist = 0;
FPtree::FPtree()
{
root = new set<Item>;
nodes = 0;
singlepath=true;
}
FPtree::~FPtree()
{
set<Item>::iterator it;
for(it = root->begin(); it != root->end(); it++)
it->removeChildren();
delete root;
}
int FPtree::processItems(Transaction *t, int times)
{
set<Item>::iterator head;
int added=0;
for(int depth=0; depth < t->length; depth++) {
head = header.find(Item(t->t[depth], 0));
if(head == header.end()) {
head = header.insert(Item(t->t[depth], 0)).first;
added++;
}
head->Increment(times);
}
return added;
}
int FPtree::processTransaction(Transaction *t, int times)
{
set<Item>::iterator it, head;
set<Item>* items = root;
Item_ *current = 0;
int added=0;
for(int depth=0; depth < t->length; depth++) {
head = header.find(Item(t->t[depth], 0));
if(head != header.end()) {
it = items->find(Item(t->t[depth], 0));
if(it == items->end()) {
it = items->insert(Item(t->t[depth], current)).first;
it->setNext(head->getNext());
head->setNext(it->getItem());
nodes++;
added++;
if(singlepath && (items->size()>1)) singlepath=false;
}
it->Increment(times);
current = it->getItem();
items = it->makeChildren();
}
}
return added;
}
int FPtree::grow(int *current, int depth)
{
int added=0, factor=1;
if(header.size() == 0) return 0;
if(singlepath) {
int *comb = new int[header.size()];
int cl=0;
for(set<Item>::iterator it=header.begin(); it != header.end(); it++) {
current[depth-1] = it->getId();
print(current,depth,comb,cl,it->getSupport());
comb[cl++] = it->getId();
added += factor;
factor *= 2;
}
delete [] comb;
}
else {
for(set<Item>::iterator it=header.begin(); it != header.end(); it++) {
Item_ *i;
current[depth-1] = it->getId();
FPtree *cfpt = new FPtree();
cfpt->setMinsup(minsup);
cfpt->setOutput(out);
int *tmp = new int[header.size()];
for(i = it->getNext(); i; i = i->nodelink) {
int l=0;
for(Item_ *p=i->parent; p; p = p->parent) tmp[l++] = p->id;
Transaction *t = new Transaction(l);
for(int j=0; j<l; j++) t->t[j] = tmp[l-j-1];
cfpt->processItems(t,i->supp);
delete t;
}
cfpt->Prune();
for(i = it->getNext(); i; i = i->nodelink) {
int l=0;
for(Item_ *p=i->parent; p; p = p->parent) tmp[l++] = p->id;
Transaction *t = new Transaction(l);
for(int j=0; j<l; j++) t->t[j] = tmp[l-j-1];
cfpt->processTransaction(t,i->supp);
delete t;
}
delete [] tmp;
print(current,depth,0,0,it->getSupport());
added ++;
added += cfpt->grow(current,depth+1);
delete cfpt;
}
}
return added;
}
int FPtree::Prune()
{
int left=0;
for(set<Item>::iterator it = header.begin();it != header.end(); ) {
if(it->getSupport() < minsup) {
set<Item>::iterator tmp = it++;
header.erase(tmp);
}
else {
left++;
it++;
}
}
return left;
}
void FPtree::ReOrder()
{
set<Item>::iterator itI;
multiset<Element>::iterator itE;
multiset<Element> list;
for(itI = header.begin(); itI != header.end(); itI++)
list.insert(Element(itI->getSupport(), itI->getId()));
remap = new int[list.size()+1];
relist = new set<Element>;
header.clear();
int i=1;
for(itE=list.begin(); itE!=list.end(); itE++) {
if(itE->support >= minsup) {
remap[i] = itE->id;
relist->insert(Element(itE->id,i));
Item a(i,0);
itI = header.insert(a).first;
itI->Increment(itE->support);
i++;
}
}
}
void FPtree::print(int *itemset, int il, int *comb, int cl, int support, int spos, int depth, int *current)
{
if(current==0) {
if(out) {
set<int> outset;
for(int j=0; j<il; j++) outset.insert(remap[itemset[j]]);
for(set<int>::iterator k=outset.begin(); k!=outset.end(); k++) fprintf(out, "%d ", *k);
fprintf(out, "(%d)\n", support);
if(cl) {
current = new int[cl];
print(itemset,il,comb,cl,support,0,1,current);
delete [] current;
}
}
}
else {
int loper = spos;
spos = cl;
while(–spos >= loper) {
set<int> outset;
current[depth-1] = comb[spos];
for(int i=0; i<depth; i++) outset.insert(remap[current[i]]);
for(int j=0; j<il; j++) outset.insert(remap[itemset[j]]);
for(set<int>::iterator k=outset.begin(); k!=outset.end(); k++) fprintf(out, "%d ", *k);
fprintf(out, "(%d)\n", support);
print(itemset, il, comb, cl, support, spos+1, depth+1, current);
}
}
}
fpgrowth.h
class FPgrowth
{
public:
FPgrowth();
~FPgrowth();
void setData(char *file, int type){data = new Data(file,type);}
void setMinsup(unsigned ms){minsup = ms;}
void setOutput(char *of);
int mine();
private:
unsigned minsup;
Data *data;
FPtree *fpt;
FILE *out;
};
fpgrowth.cpp
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#include <time.h>
#include "data.h"
#include "item.h"
#include "fptree.h"
#include "fpgrowth.h"
FPgrowth::FPgrowth() : data(0), out(0)
{
fpt = new FPtree();
}
FPgrowth::~FPgrowth()
{
if(data) delete data;
if(fpt) delete fpt;
}
void FPgrowth::setOutput(char *of)
{
out = fopen(of, "wt");
}
int FPgrowth::mine()
{
int added=0;
clock_t start;
fpt->setMinsup(minsup);
fpt->setOutput(out);
start = clock();
int tmin=1000000, tmax=0, ttotal=0, tnr=0;
while(Transaction *t = data->getNext()) {
if(t->length) {
fpt->processItems(t);
ttotal += t->length;
if(t->length < tmin) tmin = t->length;
if(t->length > tmax) tmax = t->length;
}
delete t;
tnr++;
}
cout << "items read [" << (clock()-start)/double(CLOCKS_PER_SEC) << "s]" << endl;
start = clock();
fpt->ReOrder();
fpt->Prune();
cout << "items reordered and pruned [" << (clock()-start)/double(CLOCKS_PER_SEC) << "s]" << endl;
start = clock();
while(Transaction *t = data->getNext()) {
int i;
vector<int> list;
for(i=0; i<t->length; i++) {
set<Element>::iterator it = fpt->relist->find(Element(t->t[i],0));
if(it!=fpt->relist->end()) list.push_back(it->id);
}
int size=list.size();
sort(list.begin(), list.end());
delete t;
t = new Transaction(size);
for(i=0; i<size; i++) t->t[i] = list[i];
if(t->length) fpt->processTransaction(t);
delete t;
}
cout << "FPtree constructed [" << (clock()-start)/double(CLOCKS_PER_SEC) << "s]" << endl;
if(out) fprintf(out,"(%d)\n", tnr);
start = clock();
int *tmp = new int[100];
added = fpt->grow(tmp,1);
delete [] tmp;
delete [] FPtree::remap;
delete FPtree::relist;
cout << "Frequent sets generated [" << (clock()-start)/double(CLOCKS_PER_SEC) << "s]" << endl;
return added;
}
testfpgrowth.cpp
#include <iostream>
using namespace std;
#include <stdlib.h>
#include <time.h>
#include "data.h"
#include "item.h"
#include "fptree.h"
#include "fpgrowth.h"
int main(int argc, char *argv[])
{
if(argc < 4){
cerr << "usage: " << argv[0] << " datafile datatype minsup [output]" << endl;
cerr << "datatype = 1 for Quest datagenerator binary" << endl;
cerr << "datatype = 2 for Quest datagenerator ascii" << endl;
cerr << "datatype = 3 for flat, i.e. all items per transaction on a single line" << endl;
cerr << "datatype = 4 for ascii version of Quest datagenerator binary" << endl;
}
else{
FPgrowth *fpgrowth = new FPgrowth();
fpgrowth->setData(argv[1],atoi(argv[2]));
fpgrowth->setMinsup(atoi(argv[3]));
if(argc==5) fpgrowth->setOutput(argv[4]);
clock_t start = clock();
int added = fpgrowth->mine();
cout << added << "\t[" << (clock()-start)/double(CLOCKS_PER_SEC) << "s]" << endl;
if(argc==5) cout << "Frequent sets written to " << argv[4] << endl;
delete fpgrowth;
}
return 0;
}
ECLAT
item.h
#include <vector>
#include <set>
using namespace std;
class Item
{
public:
Item(int i) : id(i) {}
vector<int> transactions;
int id;
};
class fItem
{
public:
fItem(int i) : id(i) {}
bool operator< (const fItem &i) const {return id < i.id;}
mutable vector<int> transactions;
int id;
};
eclat.h
class Ascending
{
public:
bool operator()(const Item &i1, const Item &i2) const {return i1.transactions.size() < i2.transactions.size();}
};
class Descending
{
public:
bool operator()(const Item &i1, const Item &i2) const {return i1.transactions.size() > i2.transactions.size();}
};
class Eclat
{
public:
Eclat();
~Eclat();
void setData(char *file, int type){data = new Data(file,type);}
void setMinsup(unsigned ms){minsup = ms;}
void setOutput(char *of){out = fopen(of, "wt");}
int mine();
void print(int *itemset, int il, int *comb, int cl, int support, int spos=0, int depth=0, int *current=0);
protected:
int grow(multiset<Item, Ascending> *items, unsigned supp);
int grow(multiset<Item, Descending> *items, unsigned supp, int *itemset, int depth, int *comb, int cl);
unsigned minsup;
Data *data;
FILE *out;
};
eclat.cpp
#include <iostream>
#include <algorithm>
using namespace std;
#include <stdio.h>
#include <time.h>
#include "data.h"
#include "item.h"
#include "eclat.h"
Eclat::Eclat() : data(0), out(0) {}
Eclat::~Eclat()
{
if(data) delete data;
if(out) fclose(out);
}
int Eclat::mine()
{
int tnr = 0;
set<fItem> root;
clock_t start;
set<fItem>::iterator it;
// citeste toate tranzactiile din fisier
//inserez item-urile simple in root daca nu exista
//si completeaza campul tranzactii al fiecarui item cu id-ul tranzactiei respective
cout << "citire tranzactii " << flush;
start = clock();
while(Transaction *t = data->getNext()) {
tnr++;
for(int i=0; i<t->length;i++) {
it = root.find(fItem(t->t[i]));
if(it == root.end()) it = root.insert(fItem(t->t[i])).first;
it->transactions.push_back(tnr);
}
delete t;
}
cout << tnr << " transactions [" << (clock()-start)/double(CLOCKS_PER_SEC) << "s]" << endl << flush;
//eliminarea item-urilor nefrecvente
//daca un item nu apare de cel putin minsup ori el este eliminat
//in allitems se afla item-urile frecvente
//in root toate item-urile (cele de la inceput)
cout << "eliminare item-uri nefrecvente " << flush;
start = clock();
multiset<Item,Ascending> *allitems = new multiset<Item,Ascending>;
while((it = root.begin()) != root.end()) {
if(it->transactions.size() >= minsup) {
Item item(it->id);
item.transactions = it->transactions;
allitems->insert(item);
}
root.erase(it);
}
cout << " [" << (clock()-start)/double(CLOCKS_PER_SEC) << "s]" << endl << flush;
//afisare numar de tranzactii
if(out) fprintf(out,"(%d)\n",tnr);
// find all frequent sets depth-first
//gaseste toate seturile frecvente
cout << "generarea seturilor frecvente " << flush;
start = clock();
int added = grow(allitems, tnr);
delete allitems;
cout << " [" << (clock()-start)/double(CLOCKS_PER_SEC) << "s]" << endl << flush;
return added;
}
int Eclat::grow(multiset<Item,Ascending> *items, unsigned supp)
{
int *itemset = new int[items->size()];
int *comb = new int[items->size()];
int factor = 1, added = 0, cl=0;
multiset<Item, Ascending>::iterator it, it2;
unsigned itsupp;
while((it = items->begin()) != items->end()) {
itemset[0] = it->id;
itsupp = it->transactions.size();
//afisarea setului frecvent
print(itemset, 1, comb, cl, itsupp);
if(itsupp<supp) {
multiset<Item, Descending> *children = new multiset<Item, Descending>;
for(it2=it, it2++;it2 != items->end(); it2++) {
vector<int> inter;
unsigned r1=0, r2=0;
unsigned it2supp=0;//nr de tranzactii comune
//realizarea intersectiei ambelor liste de tranzactii
while((r1 < it->transactions.size()) && (r2 < it2->transactions.size())) {
if(it->transactions[r1] < it2->transactions[r2]){
inter.push_back(it->transactions[r1]);
r1++;
}
else if(it->transactions[r1] > it2->transactions[r2]) r2++;
else{
r1++;
r2++;
it2supp++;
}
}
if(it2supp>=minsup){
while(r1 < it->transactions.size())
{
inter.push_back(it->transactions[r1]);
r1++;
}
}
// if frequent then add child
if(it2supp >= minsup) {
Item item(it2->id);
item.transactions = inter;
children->insert(item);
}
}
// gasirea superset-urilor frecvente
added += factor + factor * grow(children, itsupp, itemset, 2, comb, cl);
//nu ne mai trebuie children
delete children;
}
else {
comb[cl++] = it->id;
added += factor;
factor *= 2;
}
items->erase(it);
}
delete [] itemset;
delete [] comb;
return added;
}
int Eclat::grow(multiset<Item, Descending> *items, unsigned supp, int *itemset, int depth, int *comb, int cl)
{
multiset<Item, Descending>::iterator it, it2;
unsigned itsupp;
int factor = 1, added = 0;
while((it = items->begin()) != items->end()) {
itemset[depth-1] = it->id;
itsupp = supp – it->transactions.size();
// send frequent itemset to output
print(itemset, depth, comb, cl, itsupp);
if(itsupp<supp) {
multiset<Item, Descending> *children = new multiset<Item, Descending>;
for(it2=it, it2++;it2 != items->end(); it2++) {
vector<int> inter;
unsigned r1=0, r2=0, it2supp=0;
// make intersection of both transactions lists
it2supp = itsupp;
while((r1 < it->transactions.size()) && (r2 < it2->transactions.size()) && it2supp>=minsup) {
if(it->transactions[r1] < it2->transactions[r2]) r1++;
else if(it->transactions[r1] > it2->transactions[r2]) {
inter.push_back(it2->transactions[r2]);
r2++;
it2supp–;
}
else {
r1++;
r2++;
}
}
while(r2 < it2->transactions.size() && it2supp>=minsup) {
inter.push_back(it2->transactions[r2]);
r2++;
it2supp–;
}
// if frequent then add child
if(it2supp >= minsup) {
Item item(it2->id);
item.transactions = inter;
children->insert(item);
}
}
// find frequent supersets
added += factor + factor * grow(children, itsupp, itemset, depth+1, comb, cl);
// children are no longer necessary
delete children;
}
else {
comb[cl++] = it->id;
added += factor;
factor *= 2;
}
items->erase(it);
}
return added;
}
void Eclat::print(int *itemset, int il, int *comb, int cl, int support, int spos, int depth, int *current)
{
if(current==0) {
if(out) {
set<int> outset;
for(int j=0; j<il; j++) outset.insert(itemset[j]);
for(set<int>::iterator k=outset.begin(); k!=outset.end(); k++) fprintf(out, "%d ", *k);
fprintf(out, "(%d)\n", support);
if(cl) {
current = new int[cl];
print(itemset,il,comb,cl,support,0,1,current);
delete [] current;
}
}
}
else {
int loper = spos;
spos = cl;
while(–spos >= loper) {
set<int> outset;
current[depth-1] = comb[spos];
for(int i=0; i<depth; i++) outset.insert(current[i]);
for(int j=0; j<il; j++) outset.insert(itemset[j]);
for(set<int>::iterator k=outset.begin(); k!=outset.end(); k++) fprintf(out, "%d ", *k);
fprintf(out, "(%d)\n", support);
print(itemset, il, comb, cl, support, spos+1, depth+1, current);
}
}
}
testeclat.cpp
#include <iostream>
using namespace std;
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include "data.h"
#include "item.h"
#include "eclat.h"
int main(int argc, char *argv[])
{
if(argc < 4) {
cerr << "usage: " << argv[0] << " datafile datatype minsup [output]" << endl;
cerr << "datatype = 1 for Quest datagenerator binary" << endl;
cerr << "datatype = 2 for Quest datagenerator ascii" << endl;
cerr << "datatype = 3 for flat, i.e. all items per transaction on a single line" << endl;
cerr << "datatype = 4 for ascii version of Quest datagenerator binary" << endl;
}
else {
Eclat eclat;
eclat.setData(argv[1],atoi(argv[2]));
eclat.setMinsup(atoi(argv[3]));
if(argc==5) eclat.setOutput(argv[4]);
clock_t start = clock();
int added = eclat.mine();
cout << added << "\t[" << (clock()-start)/double(CLOCKS_PER_SEC) << "s]" << endl;
if(argc==5) cout << "Frequent sets written to " << argv[4] << endl;
}
return 0;
}
DIC
item.h
#include <set>
using namespace std;
class Item
{
public:
Item(int i, int t=0) : id(i), support(0), children(0), flag('a'), start(t) {}
Item(const Item &i) : id(i.id), support(i.support), children(i.children), flag(i.flag), start(i.start) {}
~Item(){}
int getId() const {return id;}
bool Counting() const {return ((flag=='a') || (flag=='b'));}
bool Frequent() const {return ((flag=='b') || (flag=='d'));}
void setFlag(char c) const {flag = c;}
int getStart() const {return start;}
int Increment(int inc = 1) const {return support+=inc;}
set<Item> *makeChildren() const;
set<Item> *getChildren() const {return children;}
int deleteChildren() const;
int getSupport() const {return support;}
bool operator<(const Item &i) const{return id < i.id;}
private:
const int id;
mutable int support;
mutable set<Item> *children;
mutable char flag;
// 'a' means infrequent and counting
// 'b' means frequent and counting
// 'c' means infrequent and counted
// 'd' means frequent and counted
mutable int start;
};
item.cpp
#include "Item.h"
set<Item> *Item::makeChildren() const
{
if(children) return children;
return children = new set<Item>;
}
int Item::deleteChildren() const
{
int deleted=0;
if(children){
for(set<Item>::iterator it = children->begin(); it != children->end(); it++)
deleted += it->deleteChildren();
delete children;
children = 0;
deleted++;
}
return deleted;
}
dic.h
#include <set>
#include <fstream>
using namespace std;
#include "Data.h"
#include "Item.h"
class DIC
{
public:
DIC();
~DIC();
void setData(char *fn, int type);
int setOutputSets(char *fn);
void setMinSup(int ms){minsup=ms;}
void setInterval(int m){M = m;}
int generateSets();
protected:
int generateCandidates();
int generateCandidates(set<Item> *items, int depth, int *current);
bool checkSubsets(int sl, int *iset, set<Item> *items, int spos, int depth);
int countCandidates();
int processTransaction(Transaction *t, set<Item> *items, int spos);
void printSet(const Item& item, int *itemset, int length);
private:
Item *trie;
int minsup;
ofstream setsout;
Data *data;
int tnr;
int M;
int counting;
int frequent;
};
dic.cpp
#include <time.h>
#include <algorithm>
#include <iostream>
#include <time.h>
using namespace std;
#include "DIC.h"
DIC::DIC()
{
data=0;
minsup=0;
trie = new Item(0);
M=0;
}
DIC::~DIC()
{
if(data) delete data;
if(trie) {
trie->deleteChildren();
delete trie;
}
}
void DIC::setData(char *fn, int type)
{
data = new Data(fn, type);
}
int DIC::setOutputSets(char *fn)
{
setsout.open(fn);
if(!setsout.is_open()) {
cerr << "error: could not open " << fn << endl;
return -1;
}
return 0;
}
int DIC::generateSets()
{
int total=0, pass=0, generated=0;
tnr=0;
trie->makeChildren();
counting=1;
frequent=0;
clock_t start = clock();
while(counting) {
generated += countCandidates();
generated += generateCandidates();
if(tnr==0 || counting==0) {
total += generated;
cout << ++pass;
if(tnr != 0) cout << "(" << tnr << ")";
cout << ": " << " " << generated << " " << total << " " << frequent
<< " [" << (clock()-start)/double(CLOCKS_PER_SEC) << "s] " << endl << flush;
start = clock();
generated=0;
}
}
cout << endl;
return frequent;
}
int DIC::generateCandidates()
{
if(trie->Counting() && tnr==0) {
trie->setFlag('d');
counting–;
}
int *tmp = new int[trie->getChildren()->size()];
int generated = generateCandidates(trie->getChildren(), 1, tmp);
delete [] tmp;
return generated;
}
int DIC::generateCandidates(set<Item> *items, int depth, int *current)
{
if(items == 0) return 0;
int generated = 0;
set<Item>::reverse_iterator runner;
for(runner = items->rbegin(); runner != items->rend(); runner++) {
current[depth-1] = runner->getId();
if(runner->Counting()) {
if(runner->getStart() == tnr) {
if(runner->getSupport() >= minsup) {
if(!runner->Frequent()) frequent++;
if(setsout.is_open()) printSet(*runner, current, depth);
runner->setFlag('d');
}
else runner->setFlag('c');
counting–;
}
else {
if(runner->getSupport() >= minsup) {
if(!runner->Frequent()) frequent++;
runner->setFlag('b');
}
}
}
if(runner->Frequent()) {
generated += generateCandidates(runner->getChildren(), depth+1, current);
set<Item> *children = runner->makeChildren();
for(set<Item>::reverse_iterator it = items->rbegin(); it != runner; it++) {
current[depth] = it->getId();
if(it->Frequent() && children->find(Item(current[depth])) == children->end()) {
if(depth==1 || checkSubsets(depth+1, current, trie->getChildren(), 0, 1)) {
if(children->insert(Item(it->getId(),tnr)).second) {
counting++;
generated++;
}
}
}
}
}
}
return generated;
}
bool DIC::checkSubsets(int sl, int *iset, set<Item> *items, int spos, int depth)
{
if(items==0) return 0;
bool ok = true;
set<Item>::iterator runner;
int loper = spos;
spos = depth+1;
while(ok && (–spos >= loper)) {
runner = items->find(Item(iset[spos]));
if(runner != items->end() && runner->Frequent()) {
if(depth<sl-1) ok = checkSubsets(sl, iset, runner->getChildren(), spos+1, depth+1);
}
else ok=false;
}
return ok;
}
int DIC::countCandidates()
{
int generated=0;
Transaction *t=0;
while((t = data->getNext())) {
tnr++;
if(trie->Counting()) {
trie->Increment();
set<Item> *children = trie->getChildren();
for(int i=0; i<t->length; i++) {
set<Item>::iterator it = children->find(Item(t->t[i]));
if(it == children->end()) {
it = children->insert(Item(t->t[i])).first;
counting++;
generated++;
}
}
}
processTransaction(t, trie->getChildren(), 0);
delete t;
if(tnr%M == 0) break;
}
if(tnr%M != 0) tnr = 0;
return generated;
}
int DIC::processTransaction(Transaction *t, set<Item> *items, int spos)
{
if(items == 0) return 0;
for(set<Item>::iterator it = items->begin(); it!=items->end(); it++) {
while((spos<t->length) && t->t[spos] < it->getId()) spos++;
if((spos<t->length) && t->t[spos]==it->getId()) {
if(it->Counting()) it->Increment();
if(spos+1<t->length) processTransaction(t,it->getChildren(),spos+1);
}
}
return 0;
}
void DIC::printSet(const Item& item, int *itemset, int length)
{
set<int> outset;
for(int j=0; j<length; j++) outset.insert(itemset[j]);
for(set<int>::iterator k=outset.begin(); k!=outset.end(); k++) setsout << *k << " ";
setsout << "(" << item.getSupport() << ")" << endl << flush;
}
dictest.cpp
#include "DIC.h"
#include <iostream>
#include <time.h>
int main(int argc, char *argv[])
{
if(argc < 5) {
cerr << "usage: " << argv[0] << " datafile datatype minsup interval [output]" << endl;
cerr << "datatype = 1 for Quest datagenerator binary" << endl;
cerr << "datatype = 2 for Quest datagenerator ascii" << endl;
cerr << "datatype = 3 for flat, i.e. all items per transaction on a single line" << endl;
cerr << "datatype = 4 for ascii version of Quest datagenerator binary" << endl;
}
else {
DIC a;
a.setData(argv[1],atoi(argv[2]));
a.setMinSup(atoi(argv[3]));
a.setInterval(atoi(argv[4]));
if(argc==6) a.setOutputSets(argv[5]);
clock_t start = clock();
int sets = a.generateSets();
cout << sets << "\t[" << (clock()-start)/double(CLOCKS_PER_SEC) << "s]" << endl;
if(argc==6) cout << "Frequent sets written to " << argv[5] << endl;
}
return 0;
}
APRIORI
item.h
#include <set>
using namespace std;
class Item
{
public:
Item(int i) : id(i), support(0), children(0) {}
Item(const Item &i) : id(i.id), support(i.support), children(i.children) {}
~Item(){}
int getId() const {return id;}
int Increment(int inc = 1) const {return support+=inc;}
set<Item> *makeChildren() const;
int deleteChildren() const;
int getSupport() const {return support;}
set<Item> *getChildren() const {return children;}
bool operator<(const Item &i) const{return id < i.id;}
private:
const int id;
mutable int support;
mutable set<Item> *children;
};
item.cpp
#include "Item.h"
set<Item> *Item::makeChildren() const
{
if(children) return children;
return children = new set<Item>;
}
int Item::deleteChildren() const
{
int deleted=0;
if(children)
{
for(set<Item>::iterator it = children->begin(); it != children->end(); it++)
{
deleted += it->deleteChildren();
}
delete children;
children = 0;
deleted++;
}
return deleted;
}
aprioriSets.h
#include <set>
#include <vector>
#include <fstream>
using namespace std;
#include "Data.h"
#include "Item.h"
class Element
{
public:
Element(int iold, int inew=0) : oldid(iold), id(inew){}
int oldid;
int id;
bool operator< (const Element &e) const {return oldid < e.oldid;}
};
class AprioriSets
{
public:
AprioriSets();
~AprioriSets();
void setData(char *fn, int type);
int setOutputSets(char *fn);
void setMinSup(int ms){minsup=ms;}
int generateSets();
void setVerbose(){verbose=true;}
void setCountType(int t){countType=t;}
protected:
int generateCandidates(int level);
int generateCandidates(int level, set<Item> *items, int depth, int *current);
bool checkSubsets(int sl, int *iset, set<Item> *items, int spos, int depth);
int countCandidates(int level);
// test k-subsets of transaction that are candidate itemsets
int processTransaction(int level, Transaction *t, set<Item> *items, int spos, int depth);
// test all candidates whether contained in transaction
int processTransaction2(int level, Transaction *t, set<Item> *items, int spos, int depth);
void ReOrder();
int pruneNodes(int level);
int pruneNodes(int level, set<Item> *items, int depth);
int pruneCandidates(int level);
int pruneCandidates(int level, set<Item> *items, int depth, int *itemset);
void printSet(const Item& item, int *itemset, int length);
private:
Item *trie;
int minsup;
ofstream setsout;
Data *data;
int *remap;
set<Element> *relist;
bool verbose;
int countType;
};
AprioriSets.cpp
#include <time.h>
#include <algorithm>
#include <iostream>
#include <time.h>
using namespace std;
#include "AprioriSets.h"
AprioriSets::AprioriSets()
{
data=0;
minsup=0;
remap=0;
relist=0;
trie = new Item(0);
verbose = false;
countType = 1;
}
AprioriSets::~AprioriSets()
{
if(data) delete data;
if(trie) {
trie->deleteChildren();
delete trie;
}
if(remap) delete remap;
if(relist) delete relist;
}
void AprioriSets::setData(char *fn, int type)
{
data = new Data(fn, type);
}
int AprioriSets::setOutputSets(char *fn)
{
setsout.open(fn);
if(!setsout.is_open()) {
cerr << "error: could not open " << fn << endl;
return -1;
}
return 0;
}
int AprioriSets::generateSets()
{
int total=0, pass=0;
bool running = true;
while(running) {
clock_t start;
int generated=0, nodes=0, tnr=0, pruned;
pass++;
cout << pass << " " << flush;
if(pass>2) {
start = clock();
generated = generateCandidates(pass);
nodes = pruneNodes(pass);
if(verbose) cout << generated << " [" << (clock()-start)/double(CLOCKS_PER_SEC) << "s] " << flush;
}
start = clock();
tnr = countCandidates(pass);
if(verbose) {
if(pass == 1) cout << trie->getChildren()->size() << " ";
cout << tnr << " [" << (clock()-start)/double(CLOCKS_PER_SEC) << "s] " << flush;
}
if(pass==1 && setsout.is_open()) printSet(*trie,0,0);
start = clock();
pruned = pruneCandidates(pass);
if(verbose) cout << pruned << " [" << (clock()-start)/double(CLOCKS_PER_SEC) << "s]\n" << flush;
if(pass==1) ReOrder(); // Reorder all items
total += pruned;
if(pruned <= pass) running = false;
}
cout << endl;
return total;
}
int AprioriSets::generateCandidates(int level)
{
int *tmp = new int[level];
int generated = generateCandidates(level, trie->getChildren(), 1, tmp);
delete [] tmp;
return generated;
}
int AprioriSets::generateCandidates(int level, set<Item> *items, int depth, int *current)
{
if(items == 0) return 0;
int generated = 0;
set<Item>::reverse_iterator runner;
if(depth == level-1) {
for(runner = items->rbegin(); runner != items->rend(); runner++) {
current[depth-1] = runner->getId();
set<Item> *children = runner->makeChildren();
for(set<Item>::reverse_iterator it = items->rbegin(); it != runner; it++) {
current[depth] = it->getId();
if(level<=2 || checkSubsets(level,current, trie->getChildren(), 0, 1)) {
children->insert(Item(it->getId()));
generated++;
}
}
}
}
else {
for(runner = items->rbegin(); runner != items->rend(); runner++) {
current[depth-1] = runner->getId();
generated += generateCandidates(level, runner->getChildren(), depth+1, current);
}
}
return generated;
}
bool AprioriSets::checkSubsets(int sl, int *iset, set<Item> *items, int spos, int depth)
{
if(items==0) return 0;
bool ok = true;
set<Item>::iterator runner;
int loper = spos;
spos = depth+1;
while(ok && (–spos >= loper)) {
runner = items->find(Item(iset[spos]));
if(runner != items->end()) {
if(depth<sl-1) ok = checkSubsets(sl, iset, runner->getChildren(), spos+1, depth+1);
}
else ok=false;
}
return ok;
}
int AprioriSets::pruneNodes(int level)
{
return pruneNodes(level,trie->getChildren(),1);
}
int AprioriSets::pruneNodes(int level, set<Item> *items, int depth)
{
if(items == 0) return 0;
int nodes = 0;
if(depth==level) nodes = items->size();
else {
for(set<Item>::iterator runner = items->begin(); runner != items->end(); ) {
int now = pruneNodes(level, runner->getChildren(), depth+1);
if(now) {
nodes += now;
nodes++;
runner++;
}
else {
runner->deleteChildren();
set<Item>::iterator tmp = runner++;
items->erase(tmp);
}
}
}
return nodes;
}
int AprioriSets::countCandidates(int level)
{
int trans=0;
// count all single items
if(level==1) {
while(Transaction *t = data->getNext()) {
trie->Increment();
int *iset = t->t, sl = t->length;
set<Item> *items = trie->makeChildren();
for(int i=0; i<sl; i++) {
Item item(iset[i]);
set<Item>::iterator runner = items->find(item);
if(runner == items->end()) runner = (items->insert(item)).first;
runner->Increment();
}
trans++;
delete t;
}
}
else {
while(Transaction *t = data->getNext()) {
if(t->length >= level) {
// Reorder transaction
int i;
vector<int> list;
for(i=0; i<t->length; i++) {
set<Element>::iterator it = relist->find(Element(t->t[i]));
if(it != relist->end()) list.push_back(it->id);
}
int size=list.size();
sort(list.begin(), list.end());
delete t;
t = new Transaction(size);
for(i=0; i<size; i++) t->t[i] = list[i];
if(countType==1 || level<=2)
{
if(processTransaction(level, t, trie->getChildren(), 0, 1)) trans++;
}
else
{
if(processTransaction2(level, t, trie->getChildren(), 0, 1)) trans++;
}
delete t;
}
}
}
return trans;
}
int AprioriSets::processTransaction2(int level, Transaction *t, set<Item> *items, int spos, int depth)
{
if(items == 0) return 0;
int used=0, max = t->length-level+depth;
for(set<Item>::iterator it = items->begin(); spos<max && it!=items->end(); it++)
{
while(spos<max && t->t[spos] < it->getId()) spos++;
if(spos<max && (t->t[spos]==it->getId()) )
{
if(depth==level)
{
it->Increment();
used++;
}
else used += processTransaction2(level,t,it->getChildren(),spos+1,depth+1);
}
}
return used;
}
int AprioriSets::processTransaction(int level, Transaction *t, set<Item> *items, int spos, int depth)
{
if(items == 0) return 0;
int used=0, *iset = t->t, sl = t->length, loper = spos;
set<Item>::iterator runner;
spos = sl-(level-depth);
while(–spos >= loper) {
runner = items->find(Item(iset[spos]));
if(runner != items->end()) {
if(depth == level) {
runner->Increment();
used++;
}
else {
if(depth==1 && level==2) runner->makeChildren();
used += processTransaction(level, t, runner->getChildren(), spos+1, depth+1);
}
}
else if(depth==2 && level==2) {
set<Item> *singles = trie->getChildren();
if(singles->find(Item(iset[spos])) != singles->end()) {
runner = items->insert(Item(iset[spos])).first;
runner->Increment();
used++;
}
}
}
return used;
}
int AprioriSets::pruneCandidates(int level)
{
int pruned;
int *tmp = new int[level];
pruned = pruneCandidates(level,trie->getChildren(),1,tmp);
delete [] tmp;
return pruned;
}
int AprioriSets::pruneCandidates(int level, set<Item> *items, int depth, int *itemset)
{
if(items == 0) return 0;
int left = 0;
for(set<Item>::iterator runner = items->begin(); runner != items->end(); ) {
itemset[depth-1] = runner->getId();
if(depth == level) {
if(runner->getSupport() < minsup) {
runner->deleteChildren();
set<Item>::iterator tmp = runner++;
items->erase(tmp);
}
else {
if(setsout.is_open()) printSet(*runner, itemset, depth);
left++;
runner++;
}
}
else {
int now = pruneCandidates(level, runner->getChildren(), depth+1, itemset);
if(now) {
left += now;
runner++;
}
else {
runner->deleteChildren();
set<Item>::iterator tmp = runner++;
items->erase(tmp);
}
}
}
return left;
}
void AprioriSets::printSet(const Item& item, int *itemset, int length)
{
set<int> outset;
for(int j=0; j<length; j++)
if(remap) outset.insert(remap[itemset[j]]);
else outset.insert(itemset[j]);
for(set<int>::iterator k=outset.begin(); k!=outset.end(); k++) setsout << *k << " ";
setsout << "(" << item.getSupport() << ")" << endl;
}
void AprioriSets::ReOrder()
{
set<Item> *src = trie->getChildren();
set<Item>::iterator itI;
multiset<Element>::iterator itE;
multiset<Element> list;
for(itI = src->begin();itI != src->end(); itI++)
list.insert(Element(itI->getSupport(), itI->getId()));
remap = new int[list.size()+1];
relist = new set<Element>;
src->clear();
int i=1;
for(itE=list.begin(); itE!=list.end();itE++) {
if(itE->oldid >= minsup) {
remap[i] = itE->id;
relist->insert(Element(itE->id,i));
Item a(i);
a.Increment(itE->oldid);
src->insert(a);
i++;
}
}
}
aprioritest.cpp
#include "AprioriSets.h"
#include <iostream>
#include <time.h>
int main(int argc, char *argv[])
{
if(argc < 4) {
cerr << "usage: " << argv[0] << " datafile datatype minsup [output]" << endl;
cerr << "datatype = 1 for Quest datagenerator binary" << endl;
cerr << "datatype = 2 for Quest datagenerator ascii" << endl;
cerr << "datatype = 3 for flat, i.e. all items per transaction on a single line" << endl;
cerr << "datatype = 4 for ascii version of Quest datagenerator binary" << endl;
}
else {
AprioriSets a;
a.setVerbose(); // print information on nr of candidate itemsets etc
a.setData(argv[1],atoi(argv[2]));
a.setCountType(2);
// 1: to check k-subsets of transaction in set of candidates
// 2: to check all candidates in transaction (default – best performance)
a.setMinSup(atoi(argv[3]));
if(argc==5) a.setOutputSets(argv[4]);
clock_t start = clock();
int sets = a.generateSets();
cout << sets << "\t[" << (clock()-start)/double(CLOCKS_PER_SEC) << "s]" << endl;
if(argc==5) cout << "Frequent sets written to " << argv[4] << endl;
}
return 0;
}
O alta implementarea (statica) a algoritmului DIC
item.h
#include <iostream>
#include <set>
using namespace std;
class Item
{
public:
Item(int i) : id(i),flag(0), support(0), age(0), children(0) {}
Item(const Item &i) : id(i.id),flag(i.flag), support(i.support), age(0), children(i.children){}
~Item(){}
int getId() const {return id;}
bool isCircle() const {return (flag%2)==1;}//ret 1 daca e circle
bool isSolid() const {return flag>2;}//ret 1 daca e solid
bool isSquare() const {return flag==2||flag==4;}
bool isDashed() const {return flag==1||flag==2;}
bool hasExpired(int ntr) const {if (age>=ntr) {age=ntr;return true;}return false;}
void incAge() const {age++;}
int Increment(int inc = 1) const {return support+=inc;}
set<Item> *makeChildren() const;
int deleteChildren() const;
void setFlag(int f) const {flag=f;}
int getFlag() const {return flag;}
int getSupport() const {return support;}
set<Item> *getChildren() const {return children;}
void setParent(Item* p) const { parent=p;}
Item *getParent() const {return parent;}
void setThis(Item* thi) const { th=thi;}
Item *getThis() const {return th;}
bool operator<(const Item &i) const{return id < i.id;}
private:
const int id;
mutable int flag; //1-2 dashed circle/square; 3-4 solid circles/square;0-default
mutable int support,age;
mutable bool deleted;
mutable set<Item> *children;
mutable Item *parent,*th;
};
item.cpp
#include "Item.h"
set<Item> *Item::makeChildren() const
{
if(children) return children;
return children = new set<Item>;
}
int Item::deleteChildren() const
{
int erased=0;
if(children)
{
for(set<Item>::iterator it = children->begin(); it != children->end(); it++)
erased += it->deleteChildren();
erased++;
}
flag=3;//solid circles
return erased;
}
dicSets.h
#include <set>
#include <vector>
#include <fstream>
using namespace std;
#include "Data.h"
#include "Item.h"
class Element
{
public:
Element(int iold, int inew=0) : oldid(iold), id(inew){}
int oldid;
int id;
bool operator< (const Element &e) const {return oldid < e.oldid;}
//bool operator< (const Element &e) const {return id < e.id;}
};
class ItemPointer
{
public:
ItemPointer(Item *p) : address(p) {}
Item* getItem() const {return address;}
bool operator< (const ItemPointer &e) const {return address < e.address;}
Item *address;
};
class dicSets
{
public:
dicSets();
~dicSets();
void setData(char *fn, int type);
int setOutputSets(char *fn);
void setMinSup(int ms){minsup=ms;}
void generateSets();
void setNrTrans(){nrTrans=0;}
void setM(){M=100;}
void setVerbose(){verbose=true;}
void setCountType(int t){countType=t;}
void cItems(int i);
int hasDashedCircles(set<Item> *items);
protected:
void generateTrie();
void printSet(const Item& item, int *itemset, int length);
void combineItems(set<Item> *items);
int pruneCandidates(int level);
int pruneCandidates(int level, set<Item> *items, int depth, int *items);
void ReOrder();
void findDashedCircle(set<Item> *items,int*,int);
void incrementSupport(set<Item> *items,Transaction *t,int pos);
void incrementAge(set<Item> *items);
void toSolid(set<Item> *items);
bool checkSubsets(int sl, int *iset, set<Item> *items, int spos, int depth);
//void combine(Item *a);
private:
Item *trie;
set<ItemPointer> *dashedCircle, *dashedSquare;
int minsup,ntr;
ofstream setsout;
Data *data;
int *remap;
set<Element> *relist;
bool verbose;
int countType;
int nrTrans;
int level;
int M;
};
dicSets.cpp
#include <time.h>
#include <algorithm>
#include <iostream>
#include <time.h>
using namespace std;
#include "dicSets.h"
dicSets::dicSets()
{
ntr=0;
data=0;
minsup=0;
remap=0;
relist=0;
trie = new Item(0);
trie->setThis(trie);
trie->setParent(0);
dashedCircle = new set<ItemPointer>;
dashedSquare = new set<ItemPointer>;
verbose = false;
countType = 1;
level=0;
}
dicSets::~dicSets()
{
if(data) delete data;
if(remap) delete remap;
if(relist) delete relist;
if(dashedCircle) delete dashedCircle;
}
void dicSets::setData(char *fn, int type)
{
data = new Data(fn, type);
}
int dicSets::setOutputSets(char *fn)
{
setsout.open(fn);
if(!setsout.is_open())
{
cerr << "error: could not open " << fn << endl;
return -1;
}
return 0;
}
void dicSets::generateSets()
{
clock_t start;
start = clock();
generateTrie();
if(verbose)
{
cout << trie->getChildren()->size() << " ";
cout << " [nr tranz " << (clock()-start)/double(CLOCKS_PER_SEC) << "s] " << flush;
}
if(setsout.is_open()) printSet(*trie,0,0);
start = clock();
// for(set<ItemPointer>::iterator it = dashedCircle->begin(); it != dashedCircle->end(); it++)
// {
// cout << ":" << it->getItem()->getId();
// }
cout << endl;
}
void sortare(vector<int> &l)
{
}
int dicSets::hasDashedCircles(set<Item> *items)
{
// return l->begin()==l->end();
if (items==0) return 0;
set<Item>::iterator runner;
for(runner = items->begin(); runner != items->end(); runner++)
{
if(runner->isDashed() && !runner->hasExpired(ntr)) return 1;
if(hasDashedCircles(runner->getChildren())==1) return 1;
}
return 0;
}
void dicSets::generateTrie()
{
trie->setFlag(4);
while(Transaction *t = data->getNext())
{
ntr++;
int *iset = t->t, sl = t->length;
set<Item> *items = trie->makeChildren();
for(int i=0; i<sl; i++)
{
Item *item=new Item(iset[i]);
item->setParent(trie);
item->setThis(item);
set<Item>::iterator runner = items->find(*item);
if(runner == items->end())
{
runner = (items->insert(*item)).first;
ItemPointer *pointer=new ItemPointer(item->getThis());
dashedCircle->insert(*pointer);
}
runner->Increment();
}
delete t;
trie->Increment();
}
level++;
ReOrder(); // Reorder all items
combineItems(trie->getChildren());
for (set<Item>::iterator runner=trie->getChildren()->begin();runner!=trie->getChildren()->end();runner++)
{
runner->setFlag(1);
}
//int *tmp = new int[level];
// findDashedCircle(trie->getChildren());//,tmp);
int contor=0;
// while(!empty(dashedCircle))
int *vector_cale=new int[level];
while(1)
{
cout<<contor<<endl;Transaction *t;
if(!(t = data->getNext())) t = data->getNext();
int i;
vector<int> list;
for(i=0; i<t->length; i++)
{
set<Element>::iterator it = relist->find(Element(t->t[i]));
if(it != relist->end()) list.push_back(it->id);
}
int size=list.size();
sort(list.begin(), list.end());
delete t;
t = new Transaction(size);
for(i=0; i<size; i++) {t->t[i] = list[i];}
incrementSupport(trie->getChildren(),t,0);
incrementAge(trie->getChildren());
contor++;
if (contor%3==0)
{
findDashedCircle(trie->getChildren(),vector_cale,0);
if (!hasDashedCircles(trie->getChildren())) break;
}
}
toSolid(trie->getChildren());
pruneCandidates(0);
for(int i=1;i<=level;i++)
pruneCandidates(i);
printf("\nlevel=%d\n",level);
}
void print(const Item& item)
{
cout <<"(item:" << item.getId();
Item *i=item.getParent();
if (i!=NULL) print(*i);
else cout << ")" << endl;
}
void dicSets::incrementAge(set<Item> *items)
{
if (items==0) return;
set<Item>::iterator runner;
for(runner = items->begin(); runner != items->end(); runner++)
{
if (runner->isDashed()) runner->incAge();
incrementAge(runner->getChildren());
}
}
void dicSets::toSolid(set<Item> *items)
{
if (items==0) return;
set<Item>::iterator runner;
for(runner = items->begin(); runner != items->end(); runner++)
{
if (runner->isDashed()) runner->setFlag(runner->getFlag()+2);
toSolid(runner->getChildren());
}
}
void dicSets::incrementSupport(set<Item> *items,Transaction *t,int pos)
{
if (items==0) return;
for (int i=pos;i<t->length;i++)
{
set<Item>::iterator runner = items->find(Item(t->t[i]));
if (runner!=items->end())
{
if (items!=trie->getChildren())
{
if(runner->isDashed() && !runner->hasExpired(ntr))
runner->Increment();
}
incrementSupport(runner->getChildren(),t,pos+1);
}
}
}
void dicSets::findDashedCircle(set<Item> *items, int *current, int lev)
{
if (items==0) return;
set<Item>::reverse_iterator runner;
for(runner = items->rbegin(); runner != items->rend(); runner++)
{
current[lev]=runner->getId();
// cout << "findDashedCircle(level="<< lev << ") id=" << runner->getId() << " support=" << runner->getSupport() << " flag=" << runner->getFlag() << endl;
if(runner->getFlag()==1 && runner->getSupport()>minsup)
{
runner->setFlag(2);
set<Item>::iterator runner2;
for(runner2 = runner->getChildren()->begin(); runner2 != runner->getChildren()->end(); runner2++)
{
if (checkSubsets(lev+1,current, trie->getChildren(), 0, 0))
{
runner2->setFlag(1);
}
}
}
findDashedCircle(runner->getChildren(),current,lev+1);
}
}
bool dicSets::checkSubsets(int sl, int *iset, set<Item> *items, int loper, int depth)
{
if(items==0) return 0;
bool ok = true;
set<Item>::iterator runner;
int spos = depth+1;
while(ok && (–spos >= loper))
{
runner = items->find(Item(iset[spos]));
if (runner == items->end())
cout << "checkSubsets: runner not found" << endl;
if(runner != items->end()&&runner->isSquare())
{
cout << "am intrat cu runner si mai e si square pe deasupra…" << runner->getId() << endl;
if(depth<sl-1)
ok = checkSubsets(sl, iset, runner->getChildren(), spos+1, depth+1);
}
else ok=false;
}
return ok;
}
void dicSets::combineItems(set<Item> *items)
{
// if(items==0) return;
int l=0;
set<Item>::reverse_iterator runner ;
for(runner = items->rbegin(); runner != items->rend(); runner++)
{
set<Item> *children = runner->makeChildren();
for(set<Item>::reverse_iterator it = items->rbegin(); it != runner; it++)
{
Item *p=runner->getThis();
Item *a=new Item(it->getId());
a->setThis(a);
a->setParent(p);
children->insert(*a);
}
combineItems(runner->getChildren());
l++;
}
if(l>level) level=l;
}
int dicSets::pruneCandidates(int lev)
{
int pruned;
int *tmp = new int[lev];
pruned = pruneCandidates(lev,trie->getChildren(),1,tmp);
delete [] tmp;
return pruned;
}
int dicSets::pruneCandidates(int lev, set<Item> *items, int depth, int *itemset)
{
//ret cati candidati sunt
//sterge candidatii care nu au suportul peste minsup
//afiseaza candidatul care acopera o cale din trie
if(items == 0) return 0;
int left = 0;
for(set<Item>::iterator runner = items->begin(); runner != items->end(); runner++ )
{
//if (runner->isDeleted()) continue;
itemset[depth-1] = runner->getId();
if(depth == lev)
{
if(runner->getSupport() < minsup)
{
// runner->deleteChildren();
//runner->setFlag(1);
printSet(*runner, itemset, depth);
}
else
{
if(setsout.is_open()) printSet(*runner, itemset, depth);
left++;
}
}
else {
int now = pruneCandidates(lev, runner->getChildren(), depth+1, itemset);
if(now)
{
left += now;
}
else
{//runner->deleteChildren();
//runner->setFlag(1);
;}
}
}
return left;
}
void dicSets::ReOrder()
{
set<Item> *src = trie->getChildren();
set<Item>::iterator itI;
multiset<Element>::iterator itE;
multiset<Element> list;
for(itI = src->begin();itI != src->end(); itI++)
list.insert(Element(itI->getSupport(), itI->getId()));
remap = new int[list.size()+1];
relist = new set<Element>;
src->clear();
int i=1;
for(itE=list.begin(); itE!=list.end();itE++) {
if(itE->oldid >= minsup) {
remap[i] = itE->id;
relist->insert(Element(itE->id,i));
Item *a=new Item(i);
a->setThis(a);
a->setParent(trie);
a->Increment(itE->oldid);
src->insert(*a);
i++;
//cout<< a.getId()<<" ";
}
}
}
void dicSets::printSet(const Item& item, int *itemset, int length)
{
//afiseaza dintr-un itemset toate itemurile si suportul itemsetului
set<int> outset;
for(int j=0; j<length; j++)
if(remap) outset.insert(remap[itemset[j]]);
else outset.insert(itemset[j]);
for(set<int>::iterator k=outset.begin(); k!=outset.end(); k++)
setsout << *k << " ";
setsout << "(" << item.getSupport() << ")" <<item.getFlag() << endl;
}
dictest.cpp
#include "dicSets.h"
#include <iostream>
#include <time.h>
int main(int argc, char *argv[])
{
if(argc < 4) {
cerr << "usage: " << argv[0] << " datafile datatype minsup [output]" << endl;
cerr << "datatype = 1 for Quest datagenerator binary" << endl;
cerr << "datatype = 2 for Quest datagenerator ascii" << endl;
cerr << "datatype = 3 for flat, i.e. all items per transaction on a single line" << endl;
cerr << "datatype = 4 for ascii version of Quest datagenerator binary" << endl;
}
else {
dicSets a;
a.setVerbose(); // print information on nr of candidate itemsets etc
a.setData(argv[1],atoi(argv[2]));
a.setCountType(2);
// 1: to check k-subsets of transaction in set of candidates
// 2: to check all candidates in transaction (default – best performance)
a.setMinSup(atoi(argv[3]));
if(argc==5) a.setOutputSets(argv[4]);
clock_t start = clock();
a.setNrTrans();
a.setM();
a.generateSets();
cout <<"\t[" << (clock()-start)/double(CLOCKS_PER_SEC) << "s]" << endl;
if(argc==5) cout << "Frequent sets written to " << argv[4] << endl;
}
return 0;
}
Copyright Notice
© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.
Acest articol: Identificarea Sabloanelor Frecvente Automatica (ID: 161202)
Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.