ANALIZA SECVENȚELOR DE EVENIMENTE Student: Mirela -Cristina URSE1 Coordonator: Prof.dr.ing. Florin Rădulescu Dinamica evoluției tehnologiei… [623571]

1
ANALIZA SECVENȚELOR DE EVENIMENTE
Student: [anonimizat]1
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
impl ementate în sectorul data mini ng, prin detectarea secvențelor frecvente dintr –
un set de date .

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

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

Analiza secvențelor de evenimente

2
Cuprins

1. Introducere
2. Scopul lucrării
3. Data Mining
4. Exploatarea structurată a datelor
5. Exploatarea secvențelor
6. Exploatarea șirurilor
7. Exploatarea seturilor de itemi
8. Avantajele exploatării datelor
9. Procesul Standard Cross -Industry pentru Data Mining (CRISP -DM)
10. Algoritmi de Data Mining
11. Alegerea algoritmului potrivit
12. Algoritmi utiliz ați
12.1. Spade
12.2. PrefixSpan (Prefixed -projected Sequencial Pattern Mining)
13. Compar area algoritmilor SPADE și P refix Span
14. Aplicații
15. Studiu de caz
16. Concluzii
Bibliografie

Analiza secvențelor de evenimente

3
1. Introducere

De-a lungul istoriei, omul a fost supus schimbării ș i adaptării indiferent că ne referim la
aspectele personale sau profesionale ale vieții sociale. Personajele cotidianului au fost martori
ai schimbărilor aduse de tehnologie, de -a lungul istoriei. În permanență prezent pe scena
socială, omul, este principa lul factor ce a determinat trecerea de la calculatoare de dimensiuni
impresionante și capacități infime la calculatoare de dimensiuni infime și capacități
impresionante. Cu timpul, nevoia de a cunoaște cât mai mult, cât mai repede și într -un mod
cât mai co mod a dus la o digitalizare a informației din toate domeniile vieții sociale.
În zilele noastre sistemele informatizate ocupă un loc esențial în viața oamenilor, ceea
ce a determinat o creștere continuă a utilizării acestora la scară largă. Conform unui st udiu
realizat de IBM, zilnic sunt create aproximativ 2,5 quintilioane byte 2, ceea ce va duce la un
volum de 40 zettabyte 3 de date create până în anul 2020 însemnând o creștere de 300 de ori
mai mare decât în anul 2005. Motivul principal al acestei creșteri îl reprezintă, printre altele,
ușurința cu care se pot efectua task -urile cotidiene, administrative sau nu.
Aceste volume încorporează date ce alcătuiesc o gamă diversificată de informații: de la
300 miliarde de unități de conținut distribuite lunar pe F acebook și 400 milioane de tweet -uri
trimise zilnic, la 4 miliarde de ore de video vizionate pe lunar pe YouTube. Studii similare
acestuia, i -au determinat pe cercetători să catalogheze generațiile contemporane drept
generația Z, personajele responsabile c u evoluția tehnologiei, mai ales în ceea ce privește
domeniul IT.
Cererea de tehnologii moderne pentru schimbul de informații este în continuă creștere
în întreaga lume. Indiferent de sfera sa de activitate, formatul digital a demonstrat că poate
înlocui cu succes, în orice moment clasica hârtie, înregistrându -se un progres în domeniul
securității datelor și informațiilor de interes atât pentru individ, cât și pentru societate. Actele
clasice se pot deteriora, rupe sau pierde, situații generatoare de haos în rândul activităților
de zi cu zi. Activități a căror bună desfășurare este oricum amenințată de dinamica acțiunilor
uzuale ce trebuie întreprinse pentru a urma cursul firesc al vieții. Astfel, lucruri firești precum
serviciul sau întreținerea unui cămin cauzează un stres suficient ce nu mai necesită a fi
amplificat de alte variabile ale cotidianului. Pentru a diminua acest stres care reprezintă boala
secolului XXI, tehnologia pune stăpânire pe toate ariile societății. Putem afirma cu tărie că
unul dintre domeniile critice ale vieții sociale, pe care digitalizarea și -a pus pregnant
amprenta, este domeniul comerțului electronic.
Proiectarea și crearea de sisteme informaționale necesită rezolvarea unui număr mare
de probleme atât din punct de vedere inginere sc cât și din punct de vedere economic.
Dezvoltarea domeniului IT a făcut ca această trecere să fie la doar un click distanță,
punând astfel bazele apariției sistemelor de gestiune a bazelor de date.

2 2,5 quintilioane byte = 23 trilioane de gigabyte
3 40 zettabyte = 43 trilioane gigabyte

Analiza secvențelor de evenimente

4
O bază de date secvențială constă în elemente sau eveni mente ordonate. Secvențele
de evenimente au aplicații în domenii variate, precum medicină, ADN, cumpărături, etc.

2. Scopul lucrării

Scopul lucrării de față este de a analiza secvențele de evenimente, în vederea facilitării
alegerii unor algoritmi ce pot fi implementați pentru optimizarea sistemelor de recomandare
pe baza unor similitudini între anumite produse sau evenimente.

3. Data Mining

Data mining este un subdomeniu interdisciplinar al informaticii. Este procesul de calcul
de descoperire a patter n-urilor în seturi mari de date ("big data"), implicând metode care
intersectează inteligența artificială, statistica, precum și sistemele de baze de date. Scopul
general al procesului de data mining este de a extrage informații dintr -un set de date și de a
le transforma într -o structură ușor de înțeles pentru o utilizare ulterioară. În afară de etapa
de analiză brută, aceasta implică și aspecte manageriale ale bazei de date și a datelor, de pre –
procesare a datelor, considerații de complexitate, de post -procesare a structurilor
descoperite, de vizualizare și actualizare on -line. Extragerea de date este etapa de analiză a
procesului de "descoperire de cunoștințe în baze de date.
Termenul este un termen impropriu, deoarece scopul este extracția de pattern -uri și
cunoștințe din cantități mari de date, nu extracția datelor în sine. Este frecvent aplicat la orice
formă de date pe scară largă sau la procesarea informației (colectare, extracție, depozitare,
analiză, statistici), precum și orice aplicare a sistemul ui de suport decizional de către
calculator, inclusiv inteligența artificială și inteligența business.

Fig. 1 – Data mining process

Analiza secvențelor de evenimente

5
Scopul real al exploatării datelor este analiza automată sau semi -automată a unor
cantități ma ri de date, pentru a extrage pattern -uri necunoscute anterior, interesante, cum
ar fi grupuri de înregistrări de date (analiza de cluster), înregistrări neobișnuite (detectarea
anomaliilor) și dependențele. Aceasta implică, de obicei, folosirea tehnici de baze de date,
cum ar fi indici spațiali. Aceste modele pot fi apoi văzută ca un fel de rezumat al datelor de
intrare, și poate fi utilizată în analiza ulterioară sau, de exemplu, în procesul de învățare al
mașinilor și în analiza predictivă. De exemplu, et apa de extragere a datelor ar putea identifica
mai multe grupuri în date, care pot fi apoi utilizate pentru a obține rezultate mai exacte de
predicție de la un sistem de suport decizional. Nici colectarea de date, pregătirea datelor sau
interpretarea rezul tatelor și raportarea nu fac parte din etapa de exploatare a datelor, dar fac
parte din procesul general KDD ca pași suplimentari. [1]

4. Exploatarea structurată a datelor

Exploatarea structurată a datelor este procesul de găsire și extragere a informați ilor
utile din seturi de date semi -structurate. Exploatarea grafurilor este un caz special de
exploatare a datelor structurate.
Creșterea utilizării datelor semi -structurate a creat noi oportunități pentru
exploatarea datelor, care, în mod tradițional, se ocupă cu seturi de date tabelare, reflectând
asocierea puternică între exploatarea datelor și bazele de date relaționale. O mare parte din
datele interesante și exploatabile din lume nu se pliază cu ușurință în bazele de date
relaționale, deși o generație de ingineri software a fost instruită să creadă că aceasta era
singura modalitate de a trata datele, și, în general, s -au dezvoltat algoritmi de exploatare a
datelor doar pentru a face față datelor tabelare.

Fig. 2 – Exploatarea structurată a datelor

Analiza secvențelor de evenimente

6
Sequence mining este o problemă de exploatare a datelor strâns legată de cea a
exploatării regulilor de asociere. Diferența esențială dintre exploatarea secvențelor și cea a
regulilor de asociere o reprezintă setul de date de intrare. În cazul regulilor de asociere,
fiecare rând din tabelul de intrare reprezintă o singură intrare, ceea ce înseamnă că fiecare
rând este întreaga tranzacție. În cazul exploatării secvențiale, situația este mai complicată.
Aici, o secvență este împărțită pe mai multe rânduri consecutive în tabelul de intrare. Fiecare
rând reprezintă un singur eveniment al secvenței, identificat cu un atribut special. Fiecare
eveniment reprezintă o tranzacție. [3]

5. Exploatarea secvențelor

Exploatarea secven țelor este un s ubiect de exploatare a datelor ce vizează găsirea
unor modele relevante din punct de vedere statistic între exemple de date, în care valorile
sunt livrate într -o secvență. Se presupune, de obicei, că valorile sunt discrete, și, astfel,
exploatarea seriilor temporale este strâns legată, dar considerată, de obicei, o activitate
diferită. Exploatarea secvențială este un caz special de exploatare a datelor structurate.
Există mai multe probleme cheie de calcul tradițional abordate în acest domeniu.
Acestea incl ud construirea de baze de date eficiente și indecși pentru secvențele de
informații, extragerea modelelor care apar frecvent, compararea secvențelor după similarități
și recuperarea membrilor lipsă din secvență. În general, problemele de exploatare secvenț ială
pot fi clasificate în exploatarea șirurilor – care se bazează, de obicei, pe algoritmi de procesare
a șirurilor – și exploatarea seturilor de itemi – care se bazează, de obicei, pe învățarea regulilor
de asociere.
Exploatarea secvențială este un term en care caracterizează un câmp întreg din cadrul
exploatării datelor, cu identificarea automată a sub -secvențelor ce apar frecvent ca modele
din seturi mari de date secvențiale. Chiar dacă frecvența nu este întotdeauna cel mai
interesant atribut, în studiu l secvențelor este adesea cel folosit în căutări automate datorită
faptului că acesta poate fi măsurat cu ușurință.

Fig. 3 – Exploatarea secvenț elor

Analiza secvențelor de evenimente

7
Mai multe concepte sunt necesare pentru a înțelege un proces de exploatare a
secvențelor . Un set secvențial de date, așa cum a fost menționat anterior, este compus dintr –
o colecție de secvențe. O secvență este definită ca o listă ordonată de elemente sau
evenimente din care fiecare poate avea un reper temporal și o durată asociate cu aceasta.
Modelele de căutare în exploatarea secvențială sunt numite modele secvențiale sau secvențe
frecvente. Un model secvențial este o subsecvență frecventă dintr -un set de date. O secvență
b este o sub -secvență a unei secvențe a dacă fiecare element di n b este un subset al unui
element din a, dacă b este conținuta în a. O sub -secvență reprezintă un model secvențial (sau
secvența frecventă) în cazul în care este satisfacerea un prag minim de sprijin care este o
constrângere minimă frecventă stabilită de către un utilizator. Așa că, atunci când se
efectuează exploatarea secvențială, se dorește să se descopere toate sub -secvențe care
satisfac pragul minim al setului, ceea ce înseamnă toate modelele secvențiale existente.
Modul banal de a identifica astfel d e secvențe frecvente ar fi de a crea toate posibilele
combinații ale sub -secvenței și de a le testa împotriva pragul minim de sprijin. Totuși, aceasta
este în mod evident o metodă mai ineficient, atât în funcție de timp, cât și încărcarea
memoriei, având în vedere numărul mare de combinații posibile. In schimb, conform
principiului Apriori, fiecare sub -secvență a unui model secvențial este, de asemenea, un
model secvențial, cu alte cuvinte, o secvență poate fi frecventă doar în cazul în care toate sub –
secvențe sunt, de asemenea, frecvente. Folosind această proprietate inerentă observată de
secvențe implică faptul că, dacă o sub -secvență nu este frecventă, atunci toate secvențele
care o conțin nu pot fi frecvente și, prin urmare secvența poate fi ignorată . Acest lucru poate
reduce dramatic spațiul de căutare și poate face descoperirea de modele posibile în timpuri
realiste.
În afară de frecvență, alte atribute ale secvențelor solicitate pot fi constrânse de către
utilizator în scopul de a reduce și mai mul t spațiul de căutare. Acestea sunt legate de timp și
de modul în care o sub -secvență sau un potențial model secvențial este identificat în setul de
date. [4]

6. Exploatarea șirurilor

Exploatarea șirurilor folosește, în mod obișnuit, un alfabet limitat pe ntru elementele
care apar într -o secvență, dar secvența în sine poate fi, de obicei, foarte lungă. Exemple de un
alfabet pot fi cele din setul de caractere ASCII, folosit în textul limbajului natural, bazele
nucleotidice "A", "G", "C" și "T", în secvențe d e ADN, sau aminoacizii pentru secvențele de
proteine. În aplicațiile de analiză biologică asupra dispunerii alfabetului în șiruri pot fi folosite
pentru examinare secvențe genetice și proteine pentru a li se determina proprietățile.
Cunoscând secvența de l itere ale unui ADN, o proteină nu este un scop final în sine. Mai
degrabă, scopul major este de a înțelege secvența, în ceea ce privește structura și funcția
biologică. Acest lucru se realizează în mod obișnuit în primul rând prin identificarea regiunilor
individuale sau unităților structurale din cadrul fiecărei secvențe și apoi atribuirea unei funcții
la fiecare unitate structurală. În multe cazuri, acest lucru necesită compararea unei secvențe

Analiza secvențelor de evenimente

8
de date cu cele studiate anterior. Comparația dintre șiruri d evine complicată atunci când
ștergeri și mutații apar într -un șir.
Un studiu asupra algoritmilor cheie pentru compararea secvențelor pentru
bioinformatică este prezentat de Abouelhoda și Ghanem (Abouelhoda, M.; Ghanem, M.
(2010). "String Mining in Bioinfor matics". In Gaber, M. M. Scientific Data Mining and
Knowledge Discovery.) și include:
– probleme legate de repetare: care se ocupă cu operațiunile asupra unei singure secvențe și
se pot baza pe metode de potrivire exactă sau aproximativa a șirurilor pentru găsirea
repetărilor de lungime fixă dispersate sau de lungime maximă, găsirea de repetiții în tandem
și găsirea de subsecvențe unice sau subsecvențe lipsă;
– probleme de aliniere: care se ocupă cu comparația între șiruri prin alinierea mai întâi a uneia
sau a mai multor secvențe; exemple de metode populare includ BLAST – pentru a compara o
singură secvență cu mai multe secvențe dintr -o bază de date – și ClustalW – pentru mai multe
aliniamente. Algoritmii de aliniere pot fi bazați pe metode exacte sau aprox imative și pot fi,
de asemenea, clasificați ca aliniamente globale, aliniamente semi -globale și aliniamente
locale.

7. Exploatarea seturilor de itemi

Unele probleme în exploatării secvențială se pretează la descoperirea seturilor de
itemi frecvente și ordinea în care apar, de exemplu, se caută reguli de forma "dacă un {client
cumpără o mașină}, cel mai probabil el sau ea urmează să {cumpere asigurare} în decurs de 1
săptămână". În mod tradițional, exploatarea seturilor de itemi este folosită în aplicați ile de
marketing pentru a descoperi regularități între elemente frecvente ce apar împreună în
tranzacții mari. De exemplu, prin analiza tranzacțiilor coșurilor de cumpărături ale clienților
dintr -un supermarket, se poate produce o regulă care spune "dacă u n client cumpără ceapă
și cartofi, împreună, cel mai probabil el sau ea urmează să cumpere, de asemenea, carne de
hamburger în aceeași tranzacție". [5]

8. Avantajele exploatării datelor

Sequence mining este una dintre tehnicile de data mining care au ca scop descoperirea
sau identificarea de modele similare, evenimente uzuale sau trend -uri în datele
tranzacționale.
De exemplu, în vânzări, folosind datele tranzacționale vechi, o companie poate
identifica seturile de elemente pe care cumpărătorii le cumpăr ă împreună în diferite perioade
ale anului. Astfel, companiile pot folosi informațiile pentru a recomanda cumpărătorilor ce să
cumpere, folosind un preț promoțional pe baza a ceea ce au cumpărat frecvent în trecut.

Analiza secvențelor de evenimente

9
În cadrul lucrării de față, voi prezenta un studiu de caz pentru sequence mining,
folosind o bază de date cu cărți și un instrument pentru data mining. Scopul este obținerea
de secvențe frecvente de cărți citite de către utilizatori, cu scopul de a obține recomandări
pentru cititorii cu gusturi s imilare.
Exploatarea datelor ajută companiile de marketing să construiască modele bazate pe
date istorice, pentru a anticipa cine va răspunde la noile campanii de marketing, cum ar fi
direct mail, campanii de marketing online, etc. În urma rezultatelor, co mercianții vor avea o
abordare adecvată pentru vânzarea de produse profitabile clienților vizați. Explorarea datelor
aduce multe beneficii companiilor de retail, la fel ca și marketingul. Prin analiza coșului de pe
piață, un magazin poate avea un aranjamen t de producție adecvat, astfel încât clienții să
poată cumpăra produse cumpărate frecvent împreună. În plus, ajută companiile de vânzare
cu amănuntul să ofere anumite reduceri pentru anumite produse, care să atragă mai mulți
clienți.
Avantajele și dezavant ajele exploatării datelor aduce o mulțime de beneficii
întreprinderilor, societății, guvernelor, dar și individului. Cu toate acestea, confidențialitatea,
securitatea și utilizarea necorespunzătoare a informațiilor pot crea mari probleme, dacă nu
sunt abor date și rezolvate în mod corespunzător.

9. Procesul Standard Cross -Industry pentru Data Mining (CRISP -DM)

CRISP -DM constă în șase etape, destinate unui proces ciclic, după cum urmează:

Fig. 6 – Cross -Industry Standard Process pentru Data Mining (CRIS P-DM)

Analiza secvențelor de evenimente

10

Procesul standard pentru industria extinsă pentru procesarea datelor (CRISP -DM)
Înțelegerea contextului
În faza de înțelegere:
• În primul rând, este necesar să înțelegem în mod clar obiectivele afacerii și să aflăm
care sunt nevoile afacerii.
• În continuare, trebuie să evaluăm situația actuală prin găsirea resurselor, ipotezelor,
constrângerilor și a altor factori importanți care ar trebui luați în considerare.
• Apoi, din obiectivele de afaceri și situațiile curente, trebuie să creăm obiective de
data mining, pentru a atinge obiectivele de afaceri în contextul actual.
• În cele din urmă, trebuie stabilit un bun plan de exploatare a datelor, pentru a atinge
atât obiectivele de afaceri, cât și cele privind valorificarea datelor. Planul trebuie să fi e cât mai
detaliat posibil.

Înțelegerea datelor
• În primul rând, faza de înțelegere a datelor începe cu colectarea datelor inițiale, pe
care le colectăm din sursele de date disponibile, pentru a ne ajuta să ne familiarizăm cu datele.
Trebuie efectuate câ teva activități importante, inclusiv încărcarea datelor și integrarea
datelor, pentru a face cu succes colectarea datelor.
• În continuare, proprietățile "brute" sau "superficiale" ale datelor colectate trebuie
examinate cu atenție și raportate.
• Apoi, da tele trebuie explorate prin abordarea problemelor legate de extragerea
datelor, care pot fi abordate prin interogări, raportare și vizualizare.
• În final, calitatea datelor trebuie examinată prin răspunderea unor întrebări
importante cum ar fi "Sunt compl ete datele colectate?", "Există valori lipsă în datele
colectate?"
Pregătirea datelor
Pregătirea datelor consumă, de obicei, aproximativ 90% din timpul proiectului.
Rezultatul fazei de pregătire a datelor este setul final de date. Odată identificate sursel e de
date disponibile, ele trebuie selectate, curățate, construite și formatate în forma dorită.
Sarcina de explorare a datelor la o adâncime mai mare poate fi efectuată în această fază.
Modelare
• În primul rând, trebuie selectate tehnicile de modelare pe ntru a fi utilizate pentru
setul de date pregătit.

Analiza secvențelor de evenimente

11
• Apoi, scenariul de test trebuie generat pentru a valida calitatea și validitatea
modelului.
• Apoi, unul sau mai multe modele sunt create prin rularea instrumentului de
modelare pe setul de date pregătit .
• În cele din urmă, modelele trebuie evaluate cu atenție prin implicarea părților
interesate, pentru a se asigura că modelele create sunt conforme cu așteptările.
Evaluare
În faza de evaluare, rezultatele trebuie evaluate în contextul obiectivelor de afa ceri
din prima fază. În această fază, noi cerințele pot fi ridicate din cauza noilor modele care au
fost descoperite în rezultatele modelului sau de la alți factori. Obținerea înțelegerii în afaceri
este un proces iterativ în procesul de extragere a datelo r. Deciziile go -go sau non -go trebuie
făcute în acest pas pentru a trece la faza de desfășurare.
Implementare
Cunoștințele sau informațiile pe care le obținem prin procesul de extragere a datelor
trebuie să fie prezentate în așa fel încât părțile interesat e să le poată folosi atunci când o
doresc. Pe baza cerințelor afacerii, faza de implementare ar putea fi la fel de simplă ca și
crearea unui raport sau la fel de complexă ca un proces de extragere a datelor repetabil în
întreaga organizație. În faza de des fășurare, trebuie create planurile de implementare,
întreținere și monitorizare pentru punerea în aplicare și suportul viitor. Din punct de vedere
al proiectului, raportul final al proiectului trebuie să rezume experiențele proiectului și să
revizuiască pr oiectul pentru a vedea ce nevoie să îmbunătățească lecțiile învățate create.
CRISP -DM oferă un cadru uniform pentru documentarea experienței și pentru
instrucțiuni. În plus, CRISP -DM se poate aplica în diferite industrii, cu diferite tipuri de date.

Analiza secvențelor de evenimente

12
10. Algoritmi de Data Mining

Un algoritm de 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
foloseș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 s tatistici detaliate.

Fig. 4 – Algoritmi 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 produsele să fie achiziționate împreună.

Analiza secvențelor de evenimente

13
11. 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ă, fiecare
algoritm produce un rezultat diferit, iar unii algoritmi pot produce mai mult de un tip de
rezultat.

Fig. 5 – Alegerea algoritmului potrivit

Alegerea unui algoritm după tip. Serviciul de analiză include următoarele tipuri de
algoritmi:
– algoritmi de clasificare – anticipează una sau mai multe variabile discrete, bazate pe celelalte
atribute din setul de date;
– algoritmi de regresie – anticipează una sau ma i multe variabile continue, cum ar fi profit sau
pierdere, pe baza altor atribute din setul 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 într e diferite atribute dintr -un set de date; cea mai
comună aplicație a acestui tip de algoritm 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 fre cvente sau episoade în date, cum ar fi
un flux web path.
Cu toate acestea, nu există nici 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

Analiza secvențelor de evenimente

14
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 exempl u, 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 elemente
similare. [2]

12. Algoritmi utilizați

12.1. Spade

SPADE este un algoritm pentru descoperirea rapidă a modelelor secvențiale. Acesta
utilizează proprietăți combina torice pentru a descompune problema originală în sub –
probleme mai mici, care pot fi rezolva te î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 sale.
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 atribu te există O (mk)
secvențe posibile frecvente de lungime k. Cu milioane de obiecte din baza 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 parcurger i 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 negati v performanța. În plus, majoritatea abordărilor utilizează
structuri de date interne foarte complic ate, care adaugă cheltuieli suplimentare de spaț iu și
de calcul. Algoritmul denumit SPADE (Sequential PAttern Discovery folosind clase de
Echivalență) are sc opul 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 independent î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.

Analiza secvențelor de evenimente

15
• 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 costurile 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 poa te fi pusă în practică
exploatarea secvențelor. Astfel, se arată că, în aplicații complicate 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 de pășește în
majoritatea 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 frec vente crește,
dimensiunea 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 po ziț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 compl etă de date pentru fiecare iterație. SPADE, pe de
altă parte, se limitează, de obicei, la numai trei sca nări. Reduce astfel costurile I /O.

12.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 to ate aparițiile posibile 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.

Analiza secvențelor de evenimente

16

De ce PrefixSpan are o performanță atât de ridicată – avem următ oarea 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, Pr efixSpan nu generează 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 candidatul ui, 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 exe mplu, 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 ma i 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. D at 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 pattern -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ă r apid. Când sunt exploatate 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.

Analiza secvențelor de evenimente

17
Corectitudinea și caracterul complet 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țiale 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ă, factorii 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, fac torul de
micșorare 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 modele
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 contri buie 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 cel e 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 d ate 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 proiectate 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 proiectat e 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 pro iectate.
Proprietatea 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

Analiza secvențelor de evenimente

18
poate duce la un model mai lung și elementele care ar trebui folosite pentru a asambla
modele mai lungi. Numai porțiuni pro lifice 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 metodă 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ă, modelele secvențiale sunt cultivate prin explorarea numai a modelelor 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 b i-nivel, dar și o tehnică de
optimizare care explorează psuedo -proiecția. Studiul 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 dat e și FreeSpan. Printre variațiile diferite ale
PrefixSpan, proiecția bi -nivel 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 eficientă 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 a lte tipuri de cunoștințe legate de timp.

13. Compar area algoritmilor SPADE și P refix Span

SPADE este un algoritm folosit pentru descoperirea rapidă a șabloanelor de
secvențiale (sequential pattern). Majoritatea algoritmilor din ace astă categorie presupu n
utilizarea unor baze de date orizontale. SPADE folosește baze de date în format 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

Analiza secvențelor de evenimente

19
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
element e 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 el ement
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 ident ificare a elementelor frecvente
folosind temporal join. În prima fază , ne propunem 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ă loc î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.

Analiza secvențelor de evenimente

20
Tabel 3 – Lista ID -urilor pentru AB (n on-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 îndeplinit 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 cazu l lui AB, numărul de apariții
pentru AF este 3, ceea ce conduce la îndeplinirea 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 sec venț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ăr ul
aparițiilor pentru aceasta fiind egal cu 4.

Analiza secvențelor de evenimente

21
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 apa riț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 mi nim (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

Analiza secvențelor de evenimente

22
1 10 25
4 10 20
F->A
SID EID F EID A
4 20 25

În urma calculului anterior, rezultă 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 unui 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:

Analiza secvențelor de evenimente

23
Tabel 8 – L3 (apariții care îndeplinesc suportul mi nim)
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 min im, 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

Analiza secvențelor de evenimente

24
PrefixSpan este un algoritm destinat explorării proiecțiilor prefixate în șabloanele
secvențiale de mining. PrefixSpan reduce simțitor efortul pentru generarea secvențelor
candidate. Totodată, acest algoritm r educe dimensiunile bazelor de date proiectate și
conduce la creșterea performanț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 anterioa re, vom obține , ca și în cazul algoritmului
SPADE, aceleași elemente care îndeplinesc 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 cautare
<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 subse turilor
Pasul 3.1.: Găsirea subseturilor pentru <A>

Analiza secvențelor de evenimente

25
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 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 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:

Analiza secvențelor de evenimente

26
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)(ACDF)
(_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, pe ntru 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)

Analiza secvențelor de evenimente

27
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 cr eșterea
șabloanelor orientate pe
prefixare.
Secvența candidată Generarea secvențelor –
candidate este obligatorie. Generarea secvențelor –
candidate nu este
obligatorie. Folosește
proiectarea prefixului.

Analiza secvențelor de evenimente

28
14. Aplicații

Cu o gamă largă de produse și comp ortamente de cumpărare ale utilizatorilor,
rafturile pe care sunt afișate produse 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]
Sarcina 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 descoperit e 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 mode le pentru promoții, plasări pe raft, etc. Să luăm
în considerare un alt exemplu 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 c el 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ă se quence
mining includ identificarea eșecurilor planului, găsirea tiparelor de alarmă de rețea ș.a.m.d.

Fig. 7 – Aplicații ale Data Mining

Analiza secvențelor de evenimente

29
15. Studiu de caz

Lucrarea de față își propune să analizeze înregistrările din baza de date, cu scopul de
a evid enția structurile care se repetă în aceste secvențe de evenimente. Aplicația analizează,
deci, comportamentul utilizatorului.
Există patru tipuri principale de factori 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 consumatorul. Cultura este esențială atunci când vine vorba de
înțelegerea nevoilor și comportament ului 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, deoarece 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țilo r 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 se 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.
SPFM es te un instrument open -source pentru data mining pentru a găsi secvențe
frecvente cu apariții unice ale elementelor. Adică, un element poate să apară o singură dată
în fiecare tranzacție (și astfel și în fiecare secvență frecventă găsită). Subsecvențele pot
conține goluri, adică pot exista elemente suplimentare în tranzacțiile intercalate cu
elementele din subsecvențele găsite. Cu ajutorul acestui program, am analizat setul de date
și am găsit secvențe de evaluări care se repetă, găsind astfel tipare în ceea ce privește
preferințele utilizatorilor și cărțile pe care aceștia le citesc.

Analiza secvențelor de evenimente

30
Lista de cărți citite de fiecare utilizator arăta, inițial, ca în figura 8. Pentru a putea
procesa datele folosind SPMF, aceasta trebuie să arate ca în figura 3. Se folosește “ -1” ca
separator pentru evenimente, iar “ -2” pentru a marca finalul liniei.

Figura 8. Tabelul inițial cu cărțile fiecărui utilizator

Figura 9. Modelul cerut de program pentru datele de intrare

Analiza secvențelor de evenimente

31
Pentru a ajunge la tiparul dorit, am urmat mai mulți pași. Am creat două noi coloane,
cărora le -am atribuit formulele din figura 10. Acestea au rolul de a pune pe aceeași linie toate
cărțile unui utilizator până la linia curentă, marcând și care este linia cu lista completă de cărți
a utilizatorului respectiv. La final, am sortat lista descrescător, după ultima coloană, pentru a
avea câte o linie pentru fiecare utilizator, și am înlăturat liniile care erau în plus (figura 13).

Figura 10. Formule utilizate

Figura 11. Rezultatul aplicării formulelor

Analiza secvențelor de evenimente

32

Figura 12 . Rezultatul aplicării formulelor, restrâns

Figura 13 . Rezultatul aplicării formulelor, adaptat cerințelor SPMF

Analiza secvențelor de evenimente

33
În varianta finală a documentului, se regăsesc, pe fiecare linie, cărțile aferente fiecărui
utilizator, separate de “ -1”, iar, la fina l, se încheie cu “ -2”, pentru a marca sfârșitul liniei (figura
14).

Figura 14. Documentul final pentru input

În figura 15, vedem rezultatul aplicării algoritmului PrefixSpan (pentru string -uri).
Acesta este un algoritm utilizat pentru descoperirea secv ențelor repetitive în bazele de date
cu secvențe, propus de către Jian Pei Jiawei Han în 2001.

Figura 15 . Rezultatul aplicării algoritmului PrefixSpan

Analiza secvențelor de evenimente

34
În figura 1 6, vedem rezultatul aplicării algoritmului SPADE.

Figura 1 6. Rezultatul aplicării algo ritmului SPADE

Analiza secvențelor de evenimente

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

Figura 1 7. 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 .

Analiza secvențelor de evenimente

36
16. 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 r eies secvenț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.

Analiza secvențelor de evenimente

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

[1] https://en.wikipedia.org/wiki/Data_mining
[2] https://msdn.microsoft.com/en -us/library/ms175595.aspx
[3] M. Zaki, L. Wong, „Data mining techniques”, 2003
[4] K. Vrotsou, "Everyday mining. Exploring sequences in eve nt-based data", 2010
[5] https://en.wikipedia.org/wiki/Sequential_pattern_mining
[6] http://www2.informatik.uni -freiburg.de/~cziegler/BX/
[7] http://www.philippe -fournier -viger.com/spmf/
[8] 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”
[9] J. Zaki Mohammed, “SPADE: An Efficient Algorithm for Mining Frequent Sequences”,
2001
[10] Fournier -Viger, P., Lin, C.W., Gomariz, A., Gueniche, T., Soltani, A., De ng, Z., Lam, H. T.
(2016). The SPMF Open -Source Data Mining Library Version 2. Proc. 19th European
Conference on Principles of Data Mining and Knowledge Discovery (PKDD 2016) Part III,
Springer LNCS 9853, pp. 36 -40
[11] Manika, Verma, Devarshi, Mehta; „Se quential Pattern Mining: A Comparison between
GSP, SPADE and Prefix SPAN”
[12] http://theconsumerfactor.com/en/4 -factors -influencing -consumer -behavior/
[13] http://www.philippe -fournier -viger.com/spmf/SPADE.pdf
[14] http://www.philippe -fournier -viger.com/s pmf/prefixspan.pdf
[15] http://hanj.cs.illinois.edu/pdf/span01.pdf