Raport de cercetare pe semestrul 2, an universitar 2016 -2017 [623572]

ANALIZA SECVENȚELOR DE EVENIMENTE
Raport de cercetare pe semestrul 2, an universitar 2016 -2017

Student: [anonimizat]: Mirela -Cristina URSE1, anul 2 , master ABD
Coordonator: Prof.dr.ing. Florin Rădulescu

Dinamica evoluției tehnologiei reprezintă factorul motivațional care m -a făcut sa aleg ca
domeniu de studiu pentru lucrarea de cercetare domeniul Data Mining.
Prezenta lucrare are ca scop cercetarea unor algoritmi care ar putea duce la optimizarea
sistemelor de recomandare a produselor/evenimentelor în aplicațiile implementate în sectorul data
mining. Lucrarea de față prezintă, pe scurt, exploatarea secvențială a datelor și are ca scop
analizarea acestora.

Cuvinte cheie : data mining, sequence mining, algoritm, spade, prefix span

1Facultatea de Automatică și Calculatoare, Master ABD anul 2, Universitatea POLITEHNICA din București,
România, e -mail: [anonimizat]

1. Algoritmi de Data Mining

Un algoritm d e exploatare a datelor este un set de euristice și calcule care creează un
model de exploatare a datelor din date. Pentru a crea un model, algoritmul analizează mai
întâi datele furnizate, în căutarea anumitor tipuri de modele sau tendințe. Algoritmul folo sește
rezultatele acestei analize pentru a defini parametrii optimi pentru crearea modelului de
exploatare. Acești parametri sunt apoi aplicați la nivelul întregului set de date, pentru a
extrage modele concrete și statistici detaliate.

Fig. 1 – Algori tmi de Data Mining

Modelul de exploatare pe care un algoritm îl creează din datele introduse poate lua
diverse forme, incluzând:
– un set de clustere care descriu modul în care căsuțele dintr -un set de date sunt legate;
– un arbore de decizie care prezice un rezultat și descrie modul în care diferite criterii afectează
acest rezultat;
– un model matematic care prognozează vânzările;
– un set de reguli care descriu modul în care produsele sunt grupate împreună într -o tranzacție
și probabilitățile ca produse le să fie achiziționate împreună.

2. Alegerea algoritmului potrivit

Alegerea celui mai bun algoritm de utilizat pentru o sarcină analitică specifică poate fi
o provocare. În timp ce se pot folosi diferiți algoritmi pentru a îndeplini aceeași sarcină, f iecare
algoritm produce un rezultat diferit, iar unii algoritmi pot produce mai mult de un tip de
rezultat.
Alegerea unui algoritm după tip. Serviciul de analiză include următoarele tipuri de
algoritmi:
– algor itmi de clasificare – anticipează una sau mai multe variabile discrete, bazate pe celelalte
atribute din setul de date;
– algoritmi de regresie – anticipează una sau mai multe variabile continue, cum ar fi profit sau
pierdere, pe baza altor atribute din se tul de date;
– algoritmi de segmentare – împart datele în grupuri sau clustere de elemente care au aceleași
proprietăți;
– algoritmi de asociere – găsesc corelații între diferite atribute dintr -un set de date; cea mai
comună aplicație a acestui tip de algo ritm este pentru crearea de reguli de asociere, care pot
fi utilizate într -o analiză a unui coș de cumpărături;
– algoritmi de analiză secvențială – rezumă secvențe frecvente sau episoade în date, cum ar fi
un flux web path.
Cu toate acestea, nu există nic i un motiv pentru care ar trebui să fim limitați la un
singur algoritm în soluțiile noastre. Analiștii cu experiență vor folosi, uneori, un algoritm
pentru a determina cele mai eficiente intrări (variabile) și, apoi, vor aplica un algoritm diferit
pentru a prezice un rezultat anume pe baza acestor date. S -ar putea folosi, de asemenea, mai
mulți algoritmi într -o singură soluție pentru a efectua sarcini diferite: de exemplu, se poate
folosi regresia pentru a obține previziuni financiare sau un algoritm de reț ea neuronală pentru
a efectua o analiză a factorilor care influențează vânzările.
Alegerea unui algoritm după sarcină. Un algoritm poate fi utilizat pentru o anumită
sarcină, iar în cazul analizei secvențelor de date, se pot găsi grupuri formate din elemen te
similare.

3. Algoritmi utilizați

3.1. Spade

SPADE este un algoritm pentru descoperirea rapidă a modelelor secvențiale. Acesta
utilizează proprietăți combinatorice pentru a descompune problema originală în sub –
probleme mai mici, care pot fi rezo lvate în mod independent în memoria principală folosind
tehnici de căutare mai eficiente și operații de join. Experimentele au demonstrat că SPADE
este de două ori mai eficient decât algoritmul co nsiderat următorul în clasament până la
momentul apariției s ale.
Sarcina descoperirii tuturor secvențelor frecvente în bazele de date mari este destul
de dificilă. Spațiul de căutare este extrem de mare. De exemplu, cu m atribute există O (mk)
secvențe posibile frecvente de lungime k. Cu milioane de obiecte din ba za de date, problema
minimizării I/O devine primordială. Cu toate acestea, majoritatea algoritmilor curenți sunt
iterativi în natură, necesitând cât mai multe parcurgeri complete ale baze i de date ca și cea
mai lungă secvență frecventă; este în mod clar un proces foarte costisitor. Unele dintre
metode, în special cele care folosesc o anumită formă de eșantionare, pot fi sensibile la data –
skew, ceea ce poate afecta negativ performanța. În plus, majoritatea abordărilor utilizează
structuri de date interne foa rte complic ate, care adaugă cheltuieli suplimentare de spaț iu și
de calcul. Algoritmul denumit SPADE (Sequential PAttern Discovery folosind clase de
Echivalență) are scopul algoritm este de a depăși toate aceste limitări , în vederea descoperi rii
setului tuturor secvențelor frecvente. Caracteristicile cheie ale acestei abordări sunt
următoarele:
• Este folosit un format de baze de date vertical , în care este asociată cu fiecare secvență o
listă de obie cte în care apare, împreună cu timestamp -ul. Se arată că toate secvențele
frecvente pot fi enumerate prin legături temporale simple de tip join (sau intersecții) pe listele
id.
• Este folosită o abordare teoretică pentru a descompu ne spațiul de căutare original în bucăți
mai mici care pot fi procesate independ ent în memoria principală. Această abordare necesită,
de obicei, trei parcurgeri ale baze i de date sau o singură parcurgere cu unele informații pre –
procesate, reducând astfel costurile I/O.
• Deconectează descompunerea problemei de la căutarea modelului. Astfel, sunt propuse
două strategii de căutare diferite pentru a enumera secvențe le frecvente din cadrul fiecărei
componente : căutare în lățime și în adâncime.
SPADE nu numai că minimizează costurile I/O prin reducerea parcurgerii bazei de date,
ci și co sturile de calcul prin utilizarea schemelor eficiente de căutare. Abordarea bazată pe
lista verticală pe bază de id -uri este, de asemenea, insensibilă la data -skew. Un set extins de
experimente arată că SPADE depășește abordările a nterioare cu un factor de doi. În plus,
SPADE scalează liniar în dimensiunea bazei de date și un număr de alți parametri ai bazei de
date. De asemenea, este prezentat pe scurt modul în care poate fi pusă în practică exploatarea
secvențelor. Astfel, se arată că, în aplicații compli cate din lumea reală, sequence mining poate
produce un număr covârșitor de modele frecvente. Se mai arată și modul în care se pot

identifica cele mai interesante modele care utilizează strategii de pruning într -o etapă de
postprocesare.
Cifrele indică în mod clar că diferența de performanță dintre cei doi algoritmi crește
odată cu scăderea suportului minim. SPADE este de aproximativ două ori mai rapid decât GSP
la valori mai scăzute ale suportului. În plus, se poate observa că SPADE -F2 depășește în
majori tatea cazurilor GSP -F2 cu un ordin de mărime. Există mai multe motive pentru care
SPADE depășește performanța GSP: SPADE folosește doar operațiunea de îmbinare temporală
simplă pe listele de id -uri. Pe măsură ce lungimea unei secvențe frecvente crește, dim ensiunea
numelui său de identificare scade, rezultând intrări foarte rapide ; nu este utilizată nicio
structură complicată de hash -tree și nu se generează cheltuieli generale de generare și căutare
a subsecvențelor. Aceste structuri au o poziț ie foarte slab ă. Pe de altă parte, SPADE are o
poziție excelentă, deoarece o unitate necesită doar o scanare liniară a două liste ; pe măsură
ce suportul minim este redus, se găsesc secvențe frecvente mai multe și mai mari. GSP
realizează o scanare completă de date pentr u fiecare iterație. SPADE, pe de altă parte, se
limitează, de obicei, la numai trei sca nări. Reduce astfel costurile I /O.

3.2. PrefixSpan (Prefixed -projected Sequencial Pattern Mining)

Studiile au arătat că PrefixSpan analizează toate seturile de date repetitive și este mai
eficient, mai rapid, și mai scalabil decât algoritmii FreeSpan și GSP.
Prefix -projected pattern growth este mult mai elegantă decât frequent pattern -guided
projection. În comparație cu aceasta, utilizată în FreeSpan, Prefix -projected pattern growth
este mai progresivă. Chiar și în cel mai rău caz, PrefixSpan garantează că bazele de date
proiectate continuă să se micșoreze.
Ideea sa de bază este că, în loc să proiecteze secvențe din baza de date luând în
considerare toate aparițiile po sibile ale subsecvențelor frecvente, proiecția se bazează doar
pe prefixurile frecvente, pentru că orice subsecvență frecventă poate fi găsită dezvoltând un
prefix frecvent.

De ce PrefixSpan are o performanță atât de ridicată – avem următoarea analiză:
• Ritmul de creștere fără generarea de candidați. PrefixSpan este o abordare bazată pe
creșterea modelului, similară cu cea a creșterii FP. Spre deosebire de abordarea tradițională
apriori care efectuează generarea și testarea candidaților, PrefixSpan nu gener ează niciun
candidat inutil și ia în calcul d oar frecvența grupurilor locale cu un element. Astfel, se arată că,
atunci când min_support scade, numărul de secvențe frecvente crește exponențial. Ca
metodă de generare și testare a candidatului, cum ar fi GSP , manipularea unui număr atât de
exponențial de candidați este o necesitate, independentă de trucurile de optimizare. Nu este
de mirare că GSP presupune o creștere exponențială de timp pentru a procesa o bază de date
destul de mică (de exemplu, doar secven țe de 10K), deoarece trebuie să dureze mult timp să
generezi și să testezi un număr foarte mare de posibile șablo ane secvențial e.

• Proiecția bazată pe divide et impera ca mijloc eficient de reducere a datelor. PrefixSpan
generează modele mai lungi din cele mai scurte, împărțind spațiul de căutare și concentrându –
se doar pe subspațiu, care poate susține o creștere suplimentară a modelului. Spațiul de
căutare al PrefixSpan este concentrat și este limitat la un set de baze de date proiectate. Dat
fiind faptul c ă o bază de date proiectată pentru un model secvențial conține toate informațiile
necesare pentru extracția șabloanelor secvențiale care pot crește, dimensiunea bazelor de
date proiectate se reduce, de regulă, rapid, pe măsură ce procesul de mining continu ă cu
modele secvențiale mai lungi. În schimb, abordarea apriori caută întotdeauna baza de date
originală la fiecare iterație. Multe secvențe irelevante trebuie să fie scanate și verificate, ceea
ce se adaugă la cheltuielile generale.
• PrefixSpan consumă un spațiu de memorie relativ stabil, deoarece nu generează niciun
candidat și utiliează metodologia divide et impera . Pe de altă parte, metodele de generare și
testare a candidatului, inclusiv GSP și SPADE, necesită o cantitate substanțială de memorie
atunci când pragul de suport scade, deoarece trebuie să susțină un număr enorm de seturi
candidate .
• PrefixSpan aplică prefix -projected pattern growth , fiind mai eficientă decât FreeSpan,
care utilizează frequent pattern -guided projection . Comparând cu frequent p attern -guided
projection , folosită în FreeSpan, prefix -projected pattern growth (PrefixSpan) economisește
mult timp și spațiu, deoarece PrefixSpan proiectează numai elementele frecvente din sufixe,
iar secvențele proiectate se micșorează rapid. Când sunt e xploatate baze de date dense, acolo
unde FreeSpan nu poate obține mult din proiecții, PrefixSpan poate încă reduce în mod
substanțial atât lungimea secvențelor, cât și numărul de secvențe din bazele de date
proiectate.

Corectitudinea și caracterul com plet al algoritmului pot fi justificate. Aici, eficiența
algoritmului este analizată după cum urmează. Nu trebuie gener ată nicio secvență de
candidați prin PrefixSpan. Spre deosebire de algoritmii de tip apriori, PrefixSpan generează
numai șiruri secvenția le mai lungi din cele mai scurte și mai frecvente. Nu generează și nu
testează nicio secvență candidată inexistentă într -o bază de date proiectată. În comparație cu
GSP, care generează și testează un număr substanțial de secvențe candidate, PrefixSpan caut ă
un spațiu mult mai mic. Baza de date proiectată continuă să scadă. O bază de date proiectată
este mai mică decât cea originală, deoarece doar subsecțiunile postfix ale unui prefix frecvent
sunt proiectate într -o bază de date proiectată. În practică, fact orii de micșorar e pot fi
semnificativi deoarece, de obicei, doar un mic set de modele secvențiale crește destul de mult
într-o bază de date secvențială și astfel numărul de secvențe dintr -o bază de date proiectată
va deveni destul de mic când prefixul creș te; și proiecția ia doar partea postfix în raport cu un
prefix. Se poate observa că FreeSpan utilizează și ideea de baze de date proiectate. Cu toate
acestea, proiecția de acolo ia adesea întregul șir (nu doar postfix) și, prin urmare, factorul de
micșorar e este mult mai mic decât cel al lui PrefixSpan. Costul major al PrefixSpan este
construirea bazelor de date proiectate. În cel mai rău caz, PrefixSpan construiește o bază de
date proiectată pentru fiecare model secvențial. Dacă există un număr bun de mode le
secvențiale, costul este non -trivial.
Așa cum susține un studiu de analiză și de performanță, atât PrefixSpan cât și FreeSpan
sunt mai rapide decât GSP, iar PrefixSpan este și mai rapid decât FreeSpan. Aici rezumăm
factorii care contribuie la eficiența PrefixSpan, FreeSpan și GSP după cum urmează.
Atât PrefixSpan cât și FreeSpan sunt metode de pattern -growth , căutările lor sunt mai
concentrate și astfel eficiente. Metodele de pattern -growth încearcă să crească modele mai
lungi din cele mai scurte. În consecință, ele împart spațiul de căutare și se concentrează numai
asupra subspațiului care poate susține o creștere suplimentară a modelului la un moment dat.
Astfel, spațiile lor de căutare sunt focalizate și sunt limitate de bazele de date proiectate. O
bază de date proiectată pentru un model secvențial) conține toate și doar informațiile
necesare pentru modelele de sequence mining ca re pot fi cultivate din aceasta . Pe măsură ce
procesul de extracție continuă cu modele secvențiale lungi, bazele de date p roiectate devin
din ce în ce mai mici. În schimb, GSP caută mereu în baza de date originală. Multe secvențe
irelevante trebuie scanate și verificate, ceea ce duce la creșterea costurilor inutile.
Prefix -projected pattern growth este mai elegant decât frequent pattern -guided
projection . În comparație cu frequent pattern -guided projection , utilizată în FreeSpan, Prefix –
projected pattern growth este mai progresiv . Chiar și în cel mai rău caz, PrefixSpan garantează
că bazele de date proiectate continuă să se micșoreze și realizează doar postfixe. Când sunt
exploatate baze de date dense, FreeSpan nu poate câștiga prea mult de la proiecții, în timp ce
PrefixSpan poate tăia dramatic atât lungimea, cât și numărul de secvențe din bazele de date
proiectate.
Propri etatea Apriori este integrată în prefixul bi -nivel de proiecție. Proprietatea Apriori
este esența metodelor Apriori. Proiecția pe două niveluri în PrefixSpan utilizează proprietatea
Apriori în pruning -ul bazelor de date proiectate. Pe baza acestei propriet ăți, proiecția pe două
niveluri analizează verificarea în trei direcții pentru a determina dacă un model secvențial
poate duce la un model mai lung și elementele care ar trebui folosite pentru a asambla modele
mai lungi. Numai porțiuni prolifice ale secven țelor sunt proiectate în noile baze de date. Mai
mult, verificarea în 3 direcții este eficientă, deoarece sunt verificate numai celulele

corespunzătoare din matricile de ordin 6, în timp ce nu este necesară o asamblare
suplimentară.
PrefixSpan este o me todă inedită, scalabilă, eficientă și minuțioasă, a cărei i dee
generală este de a examina numai subsecțiunile prefixelor și de a proiecta numai
subsecvențele lor postfix corespunzătoare în bazele de date proiectate. În fiecare bază de date
proiectată, mode lele secvențiale sunt cultivate prin explorarea numai a mod elelor locale
frecvente. Pentru a îmbunătăți în continuare eficiența mining -ului, sunt explorate două tipuri
de proiecții de baze de date: proiecția level -by-level și proiectarea bi -nivel, dar și o tehnică de
optimizare care explorează psuedo -proiecția. St udiul sistematic de performanță arată că
PrefixSpan minează întregul set de modele, fiind eficient și rulând considerabil mai rapid decât
algoritmul GSP bazat pe ambele baze de date și FreeSpan. Printre variațiile diferite ale
PrefixSpan, proiecția bi -nive l are performanțe mai bune la procesarea pe disc, iar pse udo-
proiecția are cea mai bună performanță atunci când baza de date a secvențelor proiectate
încape în memoria principală. PrefixSpan reprezintă o metodologie nouă și promițătoare
pentru extracția e ficientă a modelelor secvențiale în bazele de date mari. Este interesant de
extins spre modele secvențiale de mining cu constrângeri de timp, ferestre de timp și/sau
taxonomie și alte tipuri de cunoștințe legate de timp.

4. Compar area algoritmilor SPADE și Prefix Span

SPADE este un algoritm folosit pentru descoperirea rapidă a șabloanelor de secvențiale
(sequential pattern). Majoritatea algoritmilor din ace astă categorie presupun utilizarea unor
baze de date orizontale. SPADE folosește baze de date în f ormat vertical, unde este stocată o
listă bazată pe id -urile fiecărui element. Baza de date este descrisă în figura următoare:

Fig. 7 – Datele stocate în baza de date

Pentru a determina elementele frecvente folosind algoritmul SPADE, vom considera
suportul minim = 2. Considerăm baza de date din figura de mai sus. Pentru a genera o secvență
(1-sequence), apariția fiecărui element este numărată , ceea ce înseamnă că acele elemente
care îndeplinesc suportul minim aparțin lui L1.
Pasul 1: Elementele și num ărătoarea fiecărei apariții sunt date în tabelul de mai jos:

Tabel 1 – C1: numărul de apariții al fiecărui element
Elementul Nr. de apariții al fiecărui element
A 4
B 4
C 1
D 2
E 1
F 4
G 1
H 1

Tabel 2 – L1: elemente care îndeplinesc suportul minim
Elementul Nr. de apariții al fiecărui element
A 4
B 4
D 2
F 4

Pasul 2: În următoarele etape , vom arăta modalitatea de identificare a elementelor frecvente
folosind temporal join. În prima fază , ne pr opunem să calculăm suportul pentru secvența
AB, având setul J={A,B,D,F}. Vom efectua un temporal join pentru a obține o listă finală a
id-urilor. Relația între AB este non -temporală, pe care o numim equality join, iar din
moment ce toate trebuie sa aibă lo c în același timp, reiese că toate aparițiile lui A și B au
același e -id și le stocăm în următoarea listă de id -uri.

Tabel 3 – Lista ID -urilor pentru AB (non -temporal join)
AB
SID EID A EID B
1 15 15
1 20 20
2 15 15
3 10 10

În tabelul de mai sus , SID este același, ceea ce înseamnă că secvența a apărut de 2 ori,
dar aparține aceluiași client, ceea ce ne face să ignorăm numărătoarea pentru SID=1, așadar
numărul total de apariții este 3. Ceea ce înseamnă că este îndepli nit suportul minim. Nu se
poate spune însă același lucru despre secvența AD, unde numărul de apariții este 1 și nu
îndeplinește suportul minim. Pe de altă parte, la fel ca în cazul lui AB, numărul de apariții
pentru AF este 3, ceea ce conduce la îndeplini rea suportului minim:

Tabel 4 – Lista ID -urilor pentru AF (non -temporal join)
AF
SID EID A EID F
1 20 20
1 25 25
2 15 15
3 10 10

Pentru secvența BD, însă, numărul aparițiilor este egal cu zero iar suportul minim nu
este îndeplinit, aceeași afirmație fiind valabilă și pentru secvențele DF și AA, cu un număr de
apariții egal cu 1. Contrar acestora, secvența BF îndeplinește suportul minim, numărul
aparițiilor pentru aceasta fiind egal cu 4.

Tabel 5 – Lista ID -urilor pentru BF (non -temporal join)
BF
SID EID B EID F
1 20 20
2 15 15
3 10 10
4 20 20

Pentru o relație temporală, secvența AB are un număr de apariții egal cu 1, ceea ce nu
satisface suportul minim, alături de secvențele AD, AF, BB, BD, BF, DD, FF, FD, FB. Singurele
care satisfac condiția de suport minim sunt secvențele:

Tabel 6 – Lista ID -urilor care îndeplinesc suportul minim (temporal join)
B->A
SID EID B EID A
1 15 15
4 20 20
D->A
SID EID D EID A
1 10 20
1 10 25
4 10 25
D->B
SID EID D EID B
1 10 15
1 10 20
4 10 20
D->F
SID EID D EID F
1 10 20
1 10 25
4 10 20
F->A
SID EID F EID A
4 20 25

În urma calculului anterior, r ezultă un C2= {(AB,3); (AD,1); (AF,3); (BD,0); (BF,4); (DF,1);
(A->A,1); (A ->B,1); (A ->D,1); (A ->F,1); (B ->A,2); (B ->B,1); (B ->D,1); (B ->F,1); (D ->A,1); (D ->B,2);
(D->D,2); (D ->F,2); (F ->A,1); (F ->B,1); (F ->D,1); (F ->F,1) }, ceea ce conduce la obținerea un ui L2
(secvențe care satisfac condiția impusă de suportul minim) ilustrat în tabelul următor:

Tabel 7 – L2 (secvențe care satisfac suportul minim)
Secvențe Nr. de apariții ale fiecărei secvențe
AB 3
AF 3
BF 4
B->A 2
D->A 2
D->B 2
B->F 2
F->A 2

Pasul 3: Generarea 3 -sequence. În acest caz avem secvența AB ->A cu un număr de apariții egal
cu 2, însă ambele secvențe care o c ompun aparțin lui SID=1 , care nu satisface suportul minim.
În această situație se află și alte secvențe, însă în tabelul următor le vom include numai pe cele
care satisfac condiția impusă de suportul minim:
Tabel 8 – L3 (apariții care îndeplinesc suportul minim)
Secvențe Nr. de apariții ale fiecărei secvențe
ABF 3
BF->A 2
D->B ->A 2
D->F->A 2
D->BF 2

Pasul 4: În acest pas vom genera 4 -sequence. Considerând mai întâi secvența ABF ->A, numărul
de apariții este egal cu 1, ceea ce nu satisface suportul minim, conform tabelului următor:
Tabel 9 – Lista ID -urilor pentru ABF ->A (temporal join)
ABF->A
SID EID A EID B EID F EID A
1 20 20 20 25
2 15 15 15 –
3 10 10 10 –

Următoarea secvență analizată este D ->BF->A pentru care numărul de aparențe este egal cu
2, ceea ce duce la îndeplinirea condi ției impuse de suportul minim:
Tabel 10 – Lista ID -urilor pentru D ->BF->A (temporal join)
D->BF->A
SID EID d EID B EID F EID A
1 10 20 20 25
2 – 15 15 –
3 – 10 10 –
4 10 20 20 25

PrefixSpan este un algoritm d estinat explorării proiecțiilor prefixate în șabloanele
secvențiale de mining. PrefixSpan reduce simțitor efortul pentru generarea secvențelor
candidate. Totodată, acest algoritm reduce dimensiunile bazelor de date proiectate și conduce
la creșterea perfor manței în procesare.
În exemplificarea acestui algoritm , pornim de la aceleași premise ca și în exemplificarea
algoritmului SPADE.
Pasul 1: Având în vedere considerentele anterioare, vom obține , ca și în cazul algoritmului
SPADE, aceleași elemente care în deplinesc condiția impusă de suportul minim:
Tabel 11 – 1-sequence
Elementul Nr. de apariții al fiecărui
element
A 4
B 4
D 2
F 4

Pasul 2: Divizăm spațiul de căutare:
Tabel 12 – Divizarea spatiului de ca utare
<A> <B> <C> <D>
(_BC)(ABF)(ACDF) (_BC)(ABF)(ACDF) (ABC)(ABF)(ACDF) (ACDF)
(_BF)(E) (_F)(E) (E)
(_BF) (_F)
(_GH) (_F)(AGH) (_F)( BF)(AGH) (AGH)

Pasul 3: Găsirea subseturilor
Pasul 3.1.: Găsirea subseturilor pentru <A>

Tabel 13 – Subseturi pentru elementul A
<A>
(_BC)(ABF)(ACDF)
(_BF)(E)
(_BF)
(_GH)

Singurele elemente care satisfac suportul minim sunt _B și _F, pentru care elementul
A poate fi prefix, formând astfel secvențele AB și AF, pentru care putem găsi s ubseturi de la
care se pot forma noi secvențe pană la secvențe egale cu 4 -sequence. Subseturile care satisfac
condiția suportului minim sunt:

Tabel 14 – Subseturi prefixate cu elementul A
<AB> <AF> <ABF>
(_BC)(ABF)(ACDF) (ACDF) (ACDF)
(_BF)(E) E E
(_BF)
(_GH)

Pasul 3.2.: Găsirea subseturilor pentru <B>
Tabel 15 – Subseturi pentru elementul B
<B>
(_BC)(ABF)(ACDF)
(_F)(E)
(_F)
(_F)(AGH)

Singurele elemente care satisfac suportul minim sunt _A și _F, pentru care elementul
B poate fi prefix, formând astfel secvențele B ->A și BF, pentru care putem găsi subseturi de la
care se pot forma noi secvențe pană la secvențe egale cu 4 -sequence. Subseturile care satisfac
condiția suportului minim sunt:
Tabel 16 – Subseturi prefixate cu elementul B
B->A BF BF->A
(_CDF) (ACDF) (_CDF)
(_GH) E (_GH)
AGH

Pasul 3.3.: Găsirea subseturilor pentru <D>
Tabel 17 – Subseturi pentru elementul D
<D>
(ABC)(ABF)(ACD F)
(_GH) (BF) (AGH)

Singurele elemente care satisfac suportul minim sunt A, B și F, pentru care elementul
B poate fi prefix, formând astfel secvențele D ->a, D ->B și D ->B->A, pentru care putem găsi
subseturi de la care se pot forma noi secvențe pană la secvențe egale cu 4 -sequence.
Subseturile care satisfac condiția suportului minim sunt:
Tabel 18 – Subseturi prefixate cu elementul D
D->A D->B D->B->A
(_BC)(ABF)(ACDF) (_C)(ABF)(ACDF) (_BF)(ACDF)
(_GH) (_F)(AGH) (_GH)

Tabel 19 – Compararea celor doi algoritmi

SPADE PrefixScan
Scopul algoritmului Este utilizat pentru
descoperirea rapidă a
șablonului secvențial. Este utilizat pentru
descoperirea șablonului
secvențial și pentru o
execuție mai bună pe
secvențe de mining de
dimensiuni mai mari.
Performanța Prezintă proprietăți de
scalare excelente cu privire
la un număr de parametri,
cum ar fi numărul de
secvențe de intrare, numărul
de evenimente pe secvența
de intrare, mărimea
evenimentului și mărimea
potențialelor evenimente
frecvente maxime și
secvențe. PrefixSpan minează un set
complet de modele, dar
reduce foarte mult eforturile
de generare a succesiunii
candidate.prefix -proiecție
reduce semnificativ
dimensiunea bazelor de date
proiectate și conduce la o
prelucrare eficientă.
Formatul bazei de date Folosește un format vertical
de bază de date. Folosește un format
orizontal de bază de date.
Abordare Apriori. Model bazat pe creșterea
șabloanelor orientate pe
prefixare.
Secvența candidată Generarea se cvențelor –
candidate este obligatorie. Generarea secvențelor –
candidate nu este
obligatorie. Folosește
proiectarea prefixului.

5. Aplicații

Cu o gamă largă de produse și comportamente de cumpărare ale utilizatorilor, rafturile
pe care sunt afișate pr oduse este una dintre cele mai importante resurse în mediul de vânzare
retail. Comercianții retail pot nu doar să își crească profitul, dar, de asemenea, să reducă costul
de printr -o gestionare adecvată a spațiului de pe rafturi și a produselor. [8]
Sarcin a de sequence mining este de a descoperi un set de atribute, partajate în timp între un
număr mare de obiecte într -o bază de date dată. De exemplu, putem să luăm în considerare
baza de date a împrumuturilor unei biblioteci, unde obiectele reprezintă clienț i, iar atributele
reprezintă autori sau cărți. Să presupunem că baza de date înregistrează cărțile citite de
fiecare abonat la bibliotecă pe o perioadă de timp. Modelele descoperite sunt secvențele
cărților cel mai frecvent citite de pasionații de lectură. Un exemplu ar putea fi faptul că "70%
dintre persoanele care citesc Pride and Prejudice a lui Jane Austen citesc, de asemenea, Emma
într-o lună." Magazinele pot folosi aceste modele pentru promoții, plasări pe raft, etc. Să luăm
în considerare un alt exem plu de bază de date de acces la un site popular, în care un obiect
este un utilizator web și un atribut este o pagină web. Modelele descoperite sunt secvențele
paginilor accesate cel mai frecvent de acel site. Aceste tipuri de informații pot fi utilizate
pentru a restructura site -ul web sau pentru a insera dinamic link -uri relevante în pagini web,
pe baza modelelor de acces ale utilizatorilor. Alte domenii în care a fost aplicată sequence
mining includ identificarea eșecurilor planului, găsirea tiparelor de alarmă de rețea ș.a.m.d.

6. Studiu de caz

Studiul de caz de față își propune să analizeze înregistrările din baza de date, cu scopul
de a evidenția structurile care se repetă în aceste secvențe de evenimente. Aplicația
analizează, deci, comportamentul utilizatorului, dar și eficacitatea celor doi algoritmi utilizați.
Există patru tipuri principale de facto ri care influențează comportamentul
consumatorului: factorii culturali, factorii sociali, factorii personali și factorii psihologici.
Factorii culturali provin din diferitele componente legate de cultură sau de mediul
cultural din care face parte consumato rul. Cultura este esențială atunci când vine vorba de
înțelegerea nevoilor și comportamentului unui individ. De -a lungul existenței sale, un individ
va fi influențat de familie, prieteni, mediul cultural sau societate, care îl vor învăța valori,
preferințe , dar și comportamente comune pentru cultura respectivă. Pentru un brand, este
important să înțeleagă și să ia în considerare factorii culturali inerenți fiecărei piețe sau fiecărei
situații, în scopul de a adapta produsul său și strategia de marketing, de oarece acestea joacă
un rol important în percepția, obiceiurile, comportamentul sau așteptările consumatorilor.
Lectura este unul dintre cele mai plăcute și educative hobby -uri și, în același timp,
foarte accesibil. Cărțile, putem spune, sunt buni prieteni și profesori. Așadar, lectura a devenit
din ce în ce mai populară, iar cumpărarea cărților a cunoscut o mare creștere.
Folosind un set de date ce cuprinde părerile cititorilor despre anumite cărți, scopul
lucrării este de a căuta secvențele de volume ce s e repetă, pentru a putea genera sugestii
pentru cei cu preferințe similare.
Setul de date este oferit de către Cai -Nicolas Ziegler și comunitatea Book -Crossing și
conține aproximativ 200.000 de cărți, cu peste 1 milion de evaluări. Acesta cuprinde 3 tabele :
Users – conține utilizatorii, cu câte un id unic. Opțional, vârstă și localitate, dar fără nume,
irelevante, oricum, pentru cercetarea de față.
Books – conține lista de cărți. Acestea sunt identificate cu ISBN, au titlu, autor, anul publicării
și editură .
BooksRatings – conține lista evaluărilor pentru cărți, pe o scară de la 1 la 10.

Folosind intrumentele Oracle SQL Developer, Oracle SQL Developer Data Modeler,
Oracle JDeveloper Studio, Oracle Database am modelat și implementat baza de date cu
tabelele d escrise anterior (Books, BooksRatings și Users), cu scopul de a testa cei doi algoritmi,
Spade și PrefixSpan pe aceste seturi de date.

Figura 2 – Diagrama relațională a bazei de date

Algoritmii au fost inițial descriși de SPMF, o librărie Open -Source pentru Dat a Mining.
Ulterior, au fost integrați într -un proiect realizat in O racle JDeveloper Studio, pentr u a fi rulați
pe setul de date descris anterior. Execuția algoritmilor a arătat că algoritmul PrefixSpan este
mult mai eficient decât SPADE, fiind mult mai rapid .

7. Concluzii

Secvențele de evenimente au aplicații în diverse domenii, iar interpretarea lor poate
duce la rezultate benefice în cadrul acestora. Din rezultatele studiului de caz reies se cvențele
de cărți citite cel mai frecvent de către cititori. Astfel, un cititor poate primi sugestii legate de
următoarele cărți pe care le -ar putea citi, în funcție de alegerile celorlalți cititori, cu gusturi
similare cu ale lui.
Algoritmul PrefixSpan este mai eficient decât SPADE, atât ca performanță, dar și din
punct de vedere al timpului, fiind mult mai rapid. De asemenea, memoria necesară
algoritmului PrefixSpan este mult mai mică decât cea necesară algoritmului SPADE.

B I B L I O G R A F I E

[1] https://msdn.microsoft.com/en -us/library/ms175595 .aspx
[2] https://en.wikipedia.org/wiki/Sequential_pattern_mining
[3] http://www2.informatik.uni -freiburg.de/~cziegler/BX/
[4] http://www.philippe -fournier -viger.com/spmf/
[5] J. Pei, J. Han, B. Mortazavi -Asi, H.P.Q. Chen, U. Dayal, M. Hsu, „PrefixSpan: Mining
Sequential Patterns Efficiently by Prefix -Projected Pattern Growth”
[6] J. Zaki Mohammed, “SPADE: An Efficient Algori thm for Mining Frequent Sequences”,
2001
[7] Fournier -Viger, P., Lin, C.W., Gomariz, A., Gueniche, T., Soltani, A., Deng, Z., Lam, H. T.
(2016). The SPMF Open -Source Data Mining Library Version 2. Proc. 19th European
Conference on Principles of Data Minin g and Knowledge Discovery (PKDD 2016) Part III,
Springer LNCS 9853, pp. 36 -40
[8] Manika, Verma, Devarshi, Mehta; „Sequential Pattern Mining: A Comparis on bet ween
GSP, SPADE and Prefix SPAN ”
[9] http://theconsumerfactor.com/en/4 -factors -influencing -consumer -behavior/
[10] http://www.philippe -fournier -viger.com/spmf/SPADE.pdf
[11] http://www.philippe -fournier -viger. com/spmf/prefixspan.pdf
[12] http://hanj.cs.illinois.edu/pdf/span01.pdf