Curs 7 Data Mining
-
Upload
lucian-sasu -
Category
Education
-
view
521 -
download
1
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
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
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
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