Curs 7 Data Mining

72
Introducere ˆ ın Data Mining Analiza asocierilor: concepte avansate Lucian Sasu, Ph.D. Universitatea Transilvania din Bra¸ sov, Facultatea de Matematic˘ si Informatic˘ a April 12, 2012 [email protected] (UNITBV) Curs 7 April 12, 2012 1 / 72

Transcript of Curs 7 Data Mining

Introducere ın Data MiningAnaliza asocierilor: concepte avansate

Lucian Sasu, Ph.D.

Universitatea Transilvania din Brasov, Facultatea de Matematica si Informatica

April 12, 2012

[email protected] (UNITBV) Curs 7 April 12, 2012 1 / 72

Motivatie

Cursul precedent a prezentat tranzactii codificate sub forma binara:un obiect face sau nu parte din cosul curent

Valorile binare folosite sunt asimetrice: prezenta unui obiect este maiimportanta decat absenta lui

Doar obiectele cu aparitie frecventa ın cosul de cumparaturi apar si ınreguli

Cursul prezent: extinderea problemei detectarii asocierilor pentruvalori binare simetrice, categoriale, continue, secvente si grafuri

[email protected] (UNITBV) Curs 7 April 12, 2012 2 / 72

Motivatie

Exemplu de set de date pentru care se poate cere determinarea dereguli de asociere:

Figure: Exemplu de date ce nu sunt binare asimetrice

Exemplu de regula de asociere:

{Nr de pagini ∈ [5, 10]∧(Browser = Mozilla)} ⇒ {Cumpara = nu}

[email protected] (UNITBV) Curs 7 April 12, 2012 3 / 72

Outline

1 Manipularea atributelor categoriale

2 Manipularea atributelor continue

3 Manipularea unei ierarhii de concepte

4 Pattern-uri secventiale

5 Pattern-uri subgraf

[email protected] (UNITBV) Curs 7 April 12, 2012 4 / 72

Manipularea atributelor categoriale

De multe ori avem variabile binare simetrice: prezenta unuiobiect/trasaturi are aceeasi importanta cu absenta sa

Exemplu de date binare simetrice: gen (masculin/feminin), arecalculator acasa (da/nu)

Varianta de lucru: se transforma toate variabilele categoriale ın binareasimetrice

Se introduce cate un obiect artificial pentru fiecare perecheatribut–valoareExemplu: gen = masculin/feminin ⇒ gen = masculin cu valori posibile0 sau 1, gen = feminin cu aceleasi valori, deci transformam variabilainitiala gen ın alte doua variabileTip de browser: Internet Explorer (0/1), Mozilla Firefox (0/1) etc

[email protected] (UNITBV) Curs 7 April 12, 2012 5 / 72

Manipularea atributelor categoriale

Coloanele “gen” si “browser” devin:

Figure: Datele originale

Figure: Transformare din date categoriale in date binare [email protected] (UNITBV) Curs 7 April 12, 2012 6 / 72

Manipularea atributelor categoriale

Probleme pentru abordarea anterioara:1 Un atribut poate avea multe valori potentiale

Atributul tara poate avea sute de valori distinctePseudo-solutie: se procedeaza ca mai sus, cu micsorarea lui minsupProblema: multe multimi generate, unele cu asocieri ıntamplatoareSolutie: gruparea datelor ın categorii mai mari (e.g. pe continente);agregarea valorilor putin frecvente ıntr–o grupare “altele”

2 Unele valori de atribute pot fi foarte frecvente comparativ cu altele;spre exemplu, majoritatea utilizatorilor pot avea Cumpara = nu

Solutie: deoarece variabilitatea pentru acest atribut e mica, el poate fiignorat cu totulSolutie: aplicarea tehnicilor pentru distributii oblice din cursul precedent

3 Cresterea artificiala a numarului de atribute duce la cresterea timpuluide calcul

[email protected] (UNITBV) Curs 7 April 12, 2012 7 / 72

Outline

1 Manipularea atributelor categoriale

2 Manipularea atributelor continue

3 Manipularea unei ierarhii de concepte

4 Pattern-uri secventiale

5 Pattern-uri subgraf

[email protected] (UNITBV) Curs 7 April 12, 2012 8 / 72

Manipularea atributelor continue

Datele pot contine date continue

Exemplu:

Gen Ani Venit Numar de Conturi Preocupat deanual ore online de email intim. pe Internet

F 26 90K 20 4 DaM 51 135K 10 2 NuM 29 80K 10 3 DaF 45 120K 15 3 Da. . . . . . . . . . . . . . . . . .

Table: Date obtinute pe baza unor chestionare

Reguli ce se pot obtine: “Utilizatorii cu venit anual > 120K apartingrupului de varsta de 45-60 de ani”, “cei care au mai mult de 3casute de email si petrec mai mult de 15 ore online pe saptamanasunt preocupati de intimitatea pe Internet”

[email protected] (UNITBV) Curs 7 April 12, 2012 9 / 72

Manipularea atributelor continue

Moduri de abordare:1 Discretizare2 Metode statistice3 Metode fara discretizare

[email protected] (UNITBV) Curs 7 April 12, 2012 10 / 72

Discretizare

Cea mai comuna metoda

Se grupeaza valori adiacente ın intervale

Exemplu: atributul “varsta” se poate diviza ın:

varsta ∈ [12, 16), varsta ∈ [16, 20), . . . , varsta ∈ [55, 60)

Discretizare prin:

intervale de lungime egalaintervale cu frecventa egala a valorilor continuteentropieclustering

Valorile discrete sunt apoi transformate ın valori binare nesimetrice camai ınainte si se aplica algoritmii de analiza a asocierilor

[email protected] (UNITBV) Curs 7 April 12, 2012 11 / 72

Discretizare

Exemplu: datele din chestionarul de mai jos

Gen Ani Venit Numar de Conturi Preocupat deanual ore online de email intim. pe Internet

F 26 90K 20 4 DaM 51 135K 10 2 NuM 29 80K 10 3 DaF 45 120K 15 3 Da

se transforma ın:

M. F. Ani Ani Ani . . . Intim. Intim.< 13 ∈ [13, 21) ∈ [21, 30) . . . = da = nu

0 1 0 0 1 . . . 1 0

1 0 0 0 0 . . . 0 1

1 0 0 0 1 . . . 1 0

0 1 0 0 0 . . . 1 0

[email protected] (UNITBV) Curs 7 April 12, 2012 12 / 72

Discretizare

Element esential ın discretizare: numarul de intervale (la clustering)/lungimea lor/ frecventa asociataDeterminarea unui numar adecvat este o problema dificilaExemplu:

Grup de varsta Chat = da Chat = nu[12, 16) 12 13[16, 20) 11 2[20, 24) 11 3[24, 28) 12 13[28, 32) 14 12[32, 36) 15 12[36, 40) 16 14[40, 44) 16 14[44, 48) 4 10[48, 52) 5 11[52, 56) 5 10[56, 60) 4 11

Table: Sumar al datelor dintr-un chestionar

Reguli ce se pot extrage:

R1 : varsta ∈ [16, 24) −→ Chat = da (s = 8.8%, c = 81.5%)

R2 : varsta ∈ [44, 60) −→ Chat = nu (s = 16.8%, c = 70%)[email protected] (UNITBV) Curs 7 April 12, 2012 13 / 72

Discretizare: probleme

Pentru setul de date precedent: o regula este interesanta daca aresuportul s ≥ 5% si confidenta c ≥ 65%

Cum se determina o lungime buna a intervalului?

Probleme:1 Interval prea mare: scade confidenta regulilor generate

R ′

1 : varsta ∈ [12, 36) −→ Chat = da (s = 30%, c = 57.7%)

R ′

2 : varsta ∈ [36, 60) −→ Chat = da (s = 28%, c = 58.3%)

ambele reguli ar fi rejectate din cauza confidentei minime impuse2 Interval prea mic: suportul poate scadea sub minsup; pentru un

interval de 4 ani regula R1 se sparge ın

R(4)11 : varsta ∈ [16, 20) −→ Chat = da (s = 4.4%, c = 84.6%)

R(4)12 : varsta ∈ [20, 24) −→ Chat = da (s = 4.4%, c = 78.6%)

Regula R1 de pe slide-ul anterior se pierde

[email protected] (UNITBV) Curs 7 April 12, 2012 14 / 72

Discretizare: probleme

Probleme (cont):3 Daca latimea intervalului este 8 ani, atunci regula R2 se rescrie ca:

R(8)21 : varsta ∈ [44, 52) −→ Chat = nu (s = 8.4%, c = 70%)

R(8)22 : varsta ∈ [52, 60) −→ Chat = nu (s = 8.4%, c = 70%)

Deoarece s si c depasesc pragurile impuse, R2 se reconstituie. In locullui R1 ınsa vor rezulta:

R(8)11 : varsta ∈ [12, 20) −→ Chat = da (s = 9.2%, c = 50.5%)

R(8)12 : varsta ∈ [20, 28) −→ Chat = da (s = 9.2%, c = 60.0%)

dar cele 2 nu recompun regula R1 deoarece c este sub prag.

[email protected] (UNITBV) Curs 7 April 12, 2012 15 / 72

Discretizare: posibile solutii

Se considera fiecare grupare posibila de intervale

Se porneste cu interval de 4 ani si se reunesc intervale adiacente:varsta ∈ [12, 16), varsta ∈ [12, 20), . . . , varsta ∈ [12, 64) etc.

Astfel se detecteaza atat R1 si R2

Probleme:

calculele devin costisitoare; pentru k intervale avem k(k − 1)/2 variantedaca intervalul [a, b) este frecvent, atunci orice interval ce include pe[a, b) este frecvent deci putem avea inflatie de multiumi candidatpot rezulta multe reguli redundante:

{R3 : varsta ∈ [16, 20), gen = M} −→ {Chat = da}

{R4 : varsta ∈ [16, 24), gen = M} −→ {Chat = da}

R4 este mai generala decat R3

[email protected] (UNITBV) Curs 7 April 12, 2012 16 / 72

Metode statistice

Prin metode statistice se pot extrage reguli de forma:

{Venit anual > 100K , Cump. online = da} → Varsta : medie = 38

Generarea de reguli: atributul care se doreste ın consecvent este scosdin setul de date

Restul de atribute se binarizeaza

Se aplica algoritmul Apriori si se extrag multimile frecvente (partea deantecedent), determinand segmentele interesante ale populatiei

Se calculeaza distributia atributului tinta

Numarul de reguli este egal cu numarul de multimi frecventedescoperite

Deoarece consecventul este un numar calculat si nu o valoare preluatadin setul de date, notiunea de confidenta nu mai este aplicabila

Validarea regulilor se face prin metode statistice

[email protected] (UNITBV) Curs 7 April 12, 2012 17 / 72

Metode statistice

O regula este interesanta daca statistica determinata din tranzactiileacoperite de regula este diferita de cea calculata de restul tranzactiilor

Exemplu: regula

{Venit anual > 100K , Cump. online = da} → Varsta : medie = 38

e interesanta daca pentru tranzactiile care nu respecta antecedentul,media varstei este mult diferita de 38 de ani

Mod de a stabili daca diferenta este semnificativa dpdv statistic sefoloseste testarea ipotezelor statistice (vezi anexa lucrarii“Introduction to Data Mining”)

[email protected] (UNITBV) Curs 7 April 12, 2012 18 / 72

Metode fara discretizare

In multe cazuri se doreste determinare de asocieri ıntre valori si nuıntre intervale rezultate prin discretizare

Exemplu: asocieri ıntre cuvinte ın documente text

Pentru fiecare cuvant se calculeaza frecventa normalizata: frecventadin fiecare document ımpartita la numarul total de aparitii din toatedocumentele

Document cuv1 cuv2 cuv3 cuv4 cuv5 cuv6d1 0.3 0.6 0 0 0 0.2d2 0.1 0.2 0 0 0 0.2d3 0.4 0 0.3 0 0 0.2d4 0.2 0 0.3 0 0 0.1d5 0 0 0 1.0 1.0 0.3

Table: Matrice cu frecvente normalizate pentru documente si cuvinte

[email protected] (UNITBV) Curs 7 April 12, 2012 19 / 72

Metode fara discretizare

Matricea de frecvente normalizate se poate transforma ın matrice cuvalori binare asimetrice prin compararea fiecarei valori cu un pragconstant t

Problema: determinarea valorii potrivite pentru t este dificil de facut

t prea mare ⇒ se pot pierde asocieri interesantet prea mic ⇒ se pot genera prea multe asocieri ıntamplatoare

Varianta propusa: algoritmul min-Apriori

Suportul unei multimi de cuvinte este dat de suma minimelorsuporturilor cuvintelor din multime pentru fiecare document ın parte:

s({cuv1, cuv2}) = min(0.3, 0.6) + min(0.1, 0.2) + min(0.4, 0)

+ min(0.2, 0) + min(0, 0) (1)

[email protected] (UNITBV) Curs 7 April 12, 2012 20 / 72

Metode fara discretizare

Proprietati ale functiei de suport din ecuatia (1):

Suportul creste monoton cu frecventa normalizata a cuvantuluiSuportul creste monoton cu numarul de documente ce contin cuvantuldatSuportul are proprietate de antimonotonie: pentru multimile {A,B ,C}si {A,B} avem ca min({A,B ,C}) ≤ min({A,B}) decis({A,B ,C}) ≤ s({A,B})

Algoritmul Apriori standard poate fi modificat pentru a gasi asociatiiıntre cuvinte folosind noua definitie a suportului.

[email protected] (UNITBV) Curs 7 April 12, 2012 21 / 72

Outline

1 Manipularea atributelor categoriale

2 Manipularea atributelor continue

3 Manipularea unei ierarhii de concepte

4 Pattern-uri secventiale

5 Pattern-uri subgraf

[email protected] (UNITBV) Curs 7 April 12, 2012 22 / 72

Ierarhie de concepte

Figure: Ierarhii de concepte

[email protected] (UNITBV) Curs 7 April 12, 2012 23 / 72

Ierarhie de concepte - utilitate

Regulile formate cu elemente departe de radacina ierarhiei pot aveasuport prea mic pentru a trece de pragul minsup impus; se pot pierdereguli interesante

Altfel spus, regulile continand elemente departe de radacina pot fiprea specifice si neinteresante

putem obtine: lapte degresat → paine neagra, lapte 2% → paineneagra, lapte degresat → paine albase poate sumariza cu: lapte → paine

A nu se cadea ın extrema cealalta: daca se considera numai reguli cuconcepte aflate aproape de radacina, atunci ele devin prea generale:electronice → mancare si s–ar putea sa nu se poata exploata

[email protected] (UNITBV) Curs 7 April 12, 2012 24 / 72

Utilizarea ierarhiei ın extragerea de reguli

Fiecare tranzactie t se ınlocuieste cu tranzactia extinsa t ′, compusadin toate elementele stramos ale elementelor din t

t = {DVD, paine neagra} se rescriet ′ = {DVD, paine neagra, electrocasnice,mancare, electronice}

Se aplica algoritmi de extragere a regulilor pentru multimea detranzactii extinse

[email protected] (UNITBV) Curs 7 April 12, 2012 25 / 72

Probleme induse de folosirea ierarhiei

Creste timpul de calcul deoarece creste dimensiunea unei tranzactii

Valori neadecvate ale lui minsup:

prea mare → se vor folosi doar concepte superioare, cu riscul de a fiprea generaleprea mic → pot rezulta reguli prea specifice

Se pot produce reguli redundante: doua reguli X → Y si X → Y suntredundante daca X este stramos al lui X , Y este stramos al lui Y sicele doua reguli au confidenta similara

[email protected] (UNITBV) Curs 7 April 12, 2012 26 / 72

Alta modalitate de folosire a ierarhiei

Se genereaza pattern-urile frecvente de la primul nivel al arborelui

Se continua cu generarea de pattern-uri frecvente de la urmatorulnivel etc

Probleme:

operatii multiple de I/O, deoarece se fac generari de multimi la fiecarenivelse pot rata niste reguli potential interesante cu elemente ce apar penivele diferite

[email protected] (UNITBV) Curs 7 April 12, 2012 27 / 72

Outline

1 Manipularea atributelor categoriale

2 Manipularea atributelor continue

3 Manipularea unei ierarhii de concepte

4 Pattern-uri secventiale

5 Pattern-uri subgraf

[email protected] (UNITBV) Curs 7 April 12, 2012 28 / 72

Pattern-uri secventiale

Deseori tranzactiile contin date legate de timpul unui eveniment

datele achizitiilor facute de cumparaturi, ımpreuna cu obiectelerespectiveexperimente stiintifice care ınregistreaza evenimente si timpul sau loculde aparitiedate ınregistrate de senzori sau aparute ın retele (sociale, decalculatoare, senzoriale)

Ce s–a discutat pana acum este legat doar de co-ocurenta unorevenimente, nu si de localizarea spatiala sau temporala a datelor

Elementele recurente ale unor fenomene dinamice ar putea fidetectate daca se considera timpul sau locul de aparitie

[email protected] (UNITBV) Curs 7 April 12, 2012 29 / 72

Pattern-uri secventiale

[email protected] (UNITBV) Curs 7 April 12, 2012 30 / 72

Exemple de secvente

Figure: Exemple de secvente

[email protected] (UNITBV) Curs 7 April 12, 2012 31 / 72

Pattern-uri secventiale - definitii

O secventa este o lista ordonata de elemente

s =< e1e2 . . . en >

Un element ej este o colectie de unul sau mai multe evenimente

ej = {i1, i2, . . . , ik}

si este asociat unui moment sau pozitii cunoscute

Lungimea unei secvente |s| este numarul de elemente din s

O k-secventa este o secventa cu k evenimente

[email protected] (UNITBV) Curs 7 April 12, 2012 32 / 72

Pattern-uri secventiale - exemplei

Secventa Web — lista de pagini vizitate:< {Homepage} {Electronics} {Digital Cameras} {Canon DigitalCamera} {Shopping Cart} {Order Confirmation} {Return toShopping} >

Secventa de carti ımprumutate:<{Fellowship of the Ring} {The Two Towers} {Return of the King}>

[email protected] (UNITBV) Curs 7 April 12, 2012 33 / 72

Subsecvente

Definitie

O secventa a =< a1a2 . . . an > este inclusa ın secventab =< b1b2 . . . bm > (sau: este o subsecventa a lui b) daca exista ıntregii1 ≤ i1 < i2 < . . . in ≤ m a.ı. a1 ⊆ bi1 , a2 ⊆ bi2 , . . . , an ⊆ bin .

Suportul unei subsecvente este frecventa relativa a secventelor carecontin subsecventa data

Un pattern secvential este o subsecventa cu suportul cel putin minsup

[email protected] (UNITBV) Curs 7 April 12, 2012 34 / 72

Problema detectarii pattern-urilor secventiale

Se dau: o baza de secvente si un prag minim de suport, minsup

Se cere: care sunt toate subsecventele care au suportul ≥ minsup?

Problema este computational intensiva: pentru o secventa de nelemente se pot alege C k

n combinatii de k-subsecvente

Pentru o secventa de n evenimente, numarul total de subsecventeeste:

C 1n + C 2

n + · · ·+ C kn + · · ·+ Cn

n = 2n − 1

deci metoda fortei brute ajunge la complexitate cel putin exponentiala

[email protected] (UNITBV) Curs 7 April 12, 2012 35 / 72

Problema detectarii pattern-urilor secventiale – exemplu

[email protected] (UNITBV) Curs 7 April 12, 2012 36 / 72

Detectarea pattern-urilor secventiale – mod de lucru

Se dau n evenimente: i1, i2, . . . , inVarianta brute-force:

Se determina 1-subsecventele candidat:

< {i1} >,< {i2} >, . . . , < {in} >

Se determina 2-subsecventele candidat:

< {i1, i2} >,< {i1, i3} >, . . . , < {i1}{i1} >,< {i1}{i2} >, . . . ,

< {in−1}{in} >

Se determina 3-subsecventele candidat:

< {i1, i2, i3} >,< {i1, i2, i4} >, . . . , < {i1, i2}{i1} >,

< {i1, i2}{i2} >, . . . , < {i1}{i1, i2} >,< {i1}{i1, i3} >, . . . ,

< {i1}{i1}{i1} >,< {i1}{i1}{i2} >, . . .

etc; la final se pastreaza doar candidatii frecventi

Observam numarul mult mai mare de secvente care se pot forma cuun numar mic de simboluri, comparativ cu numarul de multimi dinalgoritmul Apriori clasic

[email protected] (UNITBV) Curs 7 April 12, 2012 37 / 72

Detectarea pattern-urilor secventiale – varianta Apriori

1 Determina toate 1-secventele frecvente2 Repeta pana nu se mai detecteaza secvente frecvente:

Generarea candidatilor: se unesc subsecvente frecvente gasite ınpasul anterior k − 1 pentru a determina care sunt k-secventele candidatRetezarea candidatilor: se elimina candidatii care contin (k − 1)secvente infrecventeCalculul suportului: se determina suportul candidatilor ramasiEliminarea candidatilor: se elimina k-subsecventele al caror suporteste mai mic decat minsup

[email protected] (UNITBV) Curs 7 April 12, 2012 38 / 72

Detectarea pattern-urilor secventiale – generareacandidatilor

O secventa a este unita cu o secventa b numai daca prin eliminareaprimului eveniment al lui a si a ultimului eveniment din b se ajunge laaceeasi subsecventa

Conditia e impusa pentru a evita generarea de duplicate

Secventa rezultata prin unire este a concatenata cu ultimul evenimentdin b

Ultimul eveniment din b poate fie sa se adauge ın acelasi element casi ultimul element din a, fie sa se adauge ca si element separat

Daca ultimele doua evenimente din b apartin aceluiasi element, atunciultimul element din b este o parte din ultimul element din a ın secventarezultata dupa unireDaca ultimele doua evenimente din b apartin unor elemente diferiteatunci ultimul eveniment din b devine element separat ın secventa unita

[email protected] (UNITBV) Curs 7 April 12, 2012 39 / 72

Generarea candidatilor – exemplu

Unificarea secventelor a =< {1}{2, 3}{4} > si b =< {2, 3}{4, 5} >produce secventa candidat < {1}{2, 3}{4, 5} > deoarece ultimele 2evenimente din b (4 si 5) apartin aceluiasi element

Unificarea secventelor a =< {1}{2, 3}{4} > si b =< {2, 3}{4}{5} >produce secventa candidat < {1}{2, 3}{4}{5} >

[email protected] (UNITBV) Curs 7 April 12, 2012 40 / 72

Alti pasi

Retezarea candidatilor: o k-secventa candidata este eliminata dacacel putin una din (k − 1)-subsecventele sale este infrecventa

Calculul suportului: algoritmul enumera toate k-secventele; valoareasuport a candidatilor descoperiti este incrementata

[email protected] (UNITBV) Curs 7 April 12, 2012 41 / 72

Constrangeri de timp

In cazul unor evenimente ordonate ın timp, distanta prea mare ıntreevenimente poate sa fie considerata inacceptabila

Desi secventele sunt ın continuare ordonate, nu mai sunt relevantepentru extragerea de pattern-uri frecvente

Problema: cum se includ diferite restrictii de timp ın algoritmul deextragere a pattern-urilor frecvente?

[email protected] (UNITBV) Curs 7 April 12, 2012 42 / 72

Constrangeri de timp

Constrangerea maxspan specifica diferenta de timp maxim admisaıntre evenimente

Valoare prea mare a lui maxspan poate duce la detectare depattern-uri ıntamplatoare din date ınvechite

Constrangerile maxgap, mingap: diferenta maxima / minima (ın timpsau spatiu) dintre doua elemente succesive din secventa

maxgap = 1 saptamana: evenimentele din doua elemente succesivetrebuie sa apara ın decurs de o saptamanamingap = 1 ora: doua evenimente din elemente succesive nu trebuie sasurvina la mai putin de 1 ora

[email protected] (UNITBV) Curs 7 April 12, 2012 43 / 72

Constrangeri de timp

Figure: Constrangeri de timp

[email protected] (UNITBV) Curs 7 April 12, 2012 44 / 72

Constrangeri de timp - strategii de lucru

Strategia 1:

se detecteaza pattern-urile secventiale fara a tine cont de restrictiile detimpse postproceseaza pattern-urile obtinute si se elimina cele ce nu satisfacconditiile

Strategia 2:

se modifica algoritmul de detectare a pattern-urilor frecvente a.ı. saıncorporeze restrictiile de timpıntrebare: se mai aplica principiul Apriori?

[email protected] (UNITBV) Curs 7 April 12, 2012 45 / 72

Constrangeri de timp - varianta Apriori

[email protected] (UNITBV) Curs 7 April 12, 2012 46 / 72

Constrangeri de timp - varianta Apriori

Definitie (Subsecventa continua)

O secventa s este o subsecventa continua a lui w =< e1e2 . . . ek > dacaare loc macar una din urmatoarele:

1 s se obtine din w prin stergerea unui eveniment fie din e1, fie din ek2 s se obtine din w prin stergerea unui eveniment din orice element ei

care contine macar 2 evenimente

3 s este o subsecventa continua a lui t iar t e subsecventa continua alui w

Exemple: s =< {1}{2} >

este o subsecventa continua a lui < {1}{2, 3} >, < {1, 2}{2}{3} > si< {3, 4}{1, 2}{2, 3}{4} >nu este o subsecventa continua a lui < {1}{3}{2} > sau< {2}{1}{3}{2} >

[email protected] (UNITBV) Curs 7 April 12, 2012 47 / 72

Constrangeri de timp - varianta Apriori

Definitie (Principiul Apriori modificat)

Daca o k-secventa este frecventa, atunci orice (k − 1)-subsecventacontinua a sa este de asemenea frecventa.

Principiul modificat este util la pasul de retezare a candidatilor:

exemplu: pentru maxgap = 1 si secventa candidat< {1}{2, 3}{4}{5} >, subsecventa < {1}{2, 3}{5} > nu trebuie sa fieverificata ca fiind frecventa deoarece diferenta ıntre evenimentele {2, 3}si {5} este > 1doar subsecventele continue trebuie sa fie verificate daca sunt frecvente

[email protected] (UNITBV) Curs 7 April 12, 2012 48 / 72

Constrangeri de timp – dimensiunea ferestrei

Nu e obligatoriu ca evenimentele din cadrul unei element sa apara laacelasi moment

Window size: distanta maxima care se admite ıntre doua evenimentedin cadrul aceluiasi element

ws = 0 ınseamna ca toate evenimentele din cadrul oricarui elementtrebuie sa apara simultan

Restrictia afecteaza calculul numarului de suport

[email protected] (UNITBV) Curs 7 April 12, 2012 49 / 72

Constrangeri de timp – dimensiunea ferestrei

Figure: Constrangerea “window size”

[email protected] (UNITBV) Curs 7 April 12, 2012 50 / 72

Outline

1 Manipularea atributelor categoriale

2 Manipularea atributelor continue

3 Manipularea unei ierarhii de concepte

4 Pattern-uri secventiale

5 Pattern-uri subgraf

[email protected] (UNITBV) Curs 7 April 12, 2012 51 / 72

Motivatie, utilitate

Datele pot fi uneori structurate ca grafuri

Exemple:

compusi chimicistructura 3D a proteinelortopologii de reteledocumente XML

Problema: determinarea subgrafurilor frecvente

Exemplu: ın chimia computationala se pune problema determinariisubstructurilor care sunt asociate cu anumite functionalitati

[email protected] (UNITBV) Curs 7 April 12, 2012 52 / 72

Motivatie, utilitate

Figure: Exemple de grafuri

[email protected] (UNITBV) Curs 7 April 12, 2012 53 / 72

Grafuri - notiuni

Graf: structura de date ce reprezinta legaturi ıntre entitati

G = (V ,E )

V - multime de varfuriE - multime de arce (graf orientat) sau muchii (graf neorientat)

muchie: (vi , vj), vi , vj ∈ V

Fiecare varf v poate avea o eticheta l(v)

Fiecarei muchii i se poate asocia o eticheta l(vi , vj)

Definitie (Subgraf)

Un graf G ′ = (V ′,E ′) este un subgraf al grafului G = (V ,E ) daca V ′ ⊆ Vsi E ′ ⊆ E; notam acest lucru cu G ′ ⊆S G.

[email protected] (UNITBV) Curs 7 April 12, 2012 54 / 72

Graf si subgraf

[email protected] (UNITBV) Curs 7 April 12, 2012 55 / 72

Grafuri - definitia problemei

Definitie (Suport)

Pentru o colectie de grafuri G, suportul pentru un subgraf g este definit cafrecventa relativa a tuturor grafurilor care contin pe g ca si subgraf:

s(g) =|{Gi |g ⊆S Gi , Gi ∈ G}|

|G|(2)

Definitie (Problema subgrafurilor frecvente)

Pentru o multime G si un prag minsup se cere determinarea tuturorsubgrafurilor g pentru care s(g) ≥ minsup.

Observatie: vom considera doar grafurile conexe si neorientate.

[email protected] (UNITBV) Curs 7 April 12, 2012 56 / 72

Grafuri - notiuni

Problema este intensiva computational: numarul maxim de subgrafuripentru un graf complet cu etichete unice este

d∑

i=1

C id2

C2i

C id este numarul de moduri ın care se pot alege i varfuri din cele d

2C2i este numarul maxim de variante de alegere a muchiilor ıntre cele i

varfuri

[email protected] (UNITBV) Curs 7 April 12, 2012 57 / 72

Metoda de tip Apriori - transformarea datelor

Fiecare graf se poate reprezenta sub forma de tranzactie

Un obiect din tranzactie: etichetele a doua varfuri si eticheta muchieice le leaga

Figure: Transformarea grafurilor ın tranzactii

[email protected] (UNITBV) Curs 7 April 12, 2012 58 / 72

Algoritmul de tip Apriori pentru grafuri

1 Gaseste 1-subgrafurile frecvente2 Repeta:

Genereaza candidatii

foloseste (k − 1)-grafurile frecvente pentru a genera k-grafuri candidat

Reteaza candidatii

elimina subgrafurile candidat care contin (k − 1) subgrafuri infrecvente

Calculeaza suportul pentru k grafurile frecvente ramaseElimina candidatii k-grafuri care sunt infrecventi

In practica apar probleme legate de complexitatea calculului

[email protected] (UNITBV) Curs 7 April 12, 2012 59 / 72

Algoritmul de tip Apriori - exemplu

Figure: Multime de grafuri G

Figure: Cativa pasi pentru algoritmul [email protected] (UNITBV) Curs 7 April 12, 2012 60 / 72

Generarea candidatilor

In Apriori cu tranzactii: unirea a doua k-multimi va produce doar o(k + 1)-multime candidat

In Apriori aplicat pe grafuri: unirea a doua k-subgrafuri frecventepoate produce mai mult de un (k + 1)-subgraf frecvent

Moduri de realizare a unirii de doua subgrafuri:1 prin adaugare de muchii; ın acest context, un k-subgraf este un graf cu

k muchii2 prin adaugare de varfuri; ın acest context, un k-subgraf este un graf cu

k varfuri

Evitarea generarii duplicatelor: doua k-subgrafuri trebuie sa aiba ıncomun un (k − 1)-subgraf (aka nucleu)

[email protected] (UNITBV) Curs 7 April 12, 2012 61 / 72

Generarea candidatilor prin adaugare de varfuri

k : numarul de varfuri

Se adauga un nou varf la fiecare din cele 2 k-subgrafuri frecvente

Manevra se aplica pentru k-subgrafuri care au un (k − 1)-subgraf ıncomun

Intre varfurile din noul (k + 1)-subgraf se poate considera sau numuchie ⇒ putem avea mai multe rezultate pentru o astfel de unire

[email protected] (UNITBV) Curs 7 April 12, 2012 62 / 72

Generarea candidatilor prin adaugare de varfuri

Figure: Strategia de unire prin adaugare de varfuri. Semnele de ıntrebare arata case poate ca ın graful rezultat se poate sau nu considera legatura ıntre varfuri(daca considerarea este valida).

[email protected] (UNITBV) Curs 7 April 12, 2012 63 / 72

Generarea candidatilor prin adaugare de muchii

k : numarul de muchii

Se adauga o noua muchie la fiecare din cele 2 k-subgrafuri frecvente

Manevra se aplica pentru k-subgrafuri care au un (k − 1)-subgraf ıncomun

Variante:

varfuri cu etichete identicenucleul contine etichete identicenucleul poate fi ales din mai multe posibilitati

[email protected] (UNITBV) Curs 7 April 12, 2012 64 / 72

Generarea candidatilor prin adaugare de muchii: varfuri cuetichete identice

Figure: Cazul varfurilor cu etichete identice

[email protected] (UNITBV) Curs 7 April 12, 2012 65 / 72

Generarea candidatilor prin adaugare de muchii: nucleulcontine etichete identice

Figure: Cazul nucleului cu etichete identice

[email protected] (UNITBV) Curs 7 April 12, 2012 66 / 72

Generarea candidatilor prin adaugare de muchii: alegerimultiple de nucleu

Figure: Cazul nucleului ce poate fi ales din mai multe variante

[email protected] (UNITBV) Curs 7 April 12, 2012 67 / 72

Retezarea candidatilor

Avem k-subgrafurile candidat de la pasul de generare

Candidatii care contin (k − 1)–subgrafuri infrecvente sunt eliminatiProblema (grea): cum faci cautarea ın multimea de (k − 1)-subgrafurifrecvente?

Problema grafurilor izomorfe: 2 grafuri sunt izomorfe daca printr-oreetichetare a nodurilor pentru unul din grafuri se ajunge la celalalt graf

Figure: Doua grafuri izomorfe

[email protected] (UNITBV) Curs 7 April 12, 2012 68 / 72

Retezarea candidatilor

Problema determinarii izomorfismului a doua grafuri e des ıntalnita ınaceasta sectiune

Pentru determinarea faptului ca un (k − 1)-graf este frecventPentru a evita generarea de duplicatePentru a face numararea candidatilor ın cadrul grafurilor care l-ar puteacontine

[email protected] (UNITBV) Curs 7 April 12, 2012 69 / 72

Detectarea grafurilor izomorfe

Determinarea faptului ca un graf este izomorf cu altul: se asociaza uncod pe baza matricei de adiacenta

Din cauza simetriei se ia ın considerare doar partea de deasupradiagonalei principale a matricei

Se alcatuieste un cod pentru fiecare matrice de adiacenta

Codul cel mai mare ın ordine lexicografica da forma canonica agrafului

Doua grafuri sunt izomorfe doar daca au aceeasi forma canonica

Se iau ın considerare si permutarile de varfuri!

[email protected] (UNITBV) Curs 7 April 12, 2012 70 / 72

Reprezentari pentru grafuri

Figure: Reprezentari pentru doua grafuri

[email protected] (UNITBV) Curs 7 April 12, 2012 71 / 72

Calculul numarului de suport

Operatie potential costisitoare: trebuie determinate toate subgrafurilefrecvente ce apar ın G

Solutie: se mentine pentru fiecare (k − 1)-grafuri frecvent care estelista grafurilor din G care ıl contin

Cand se genereaza un k-graf candidat din 2 (k − 1)-grafuri frecvente,se face intersectia listei de grafuri aferente celor doua (k − 1)-grafuri

Se face testarea izomorfismului de grafuri cu grafurile din intersectiaanterioara

[email protected] (UNITBV) Curs 7 April 12, 2012 72 / 72