Curs 8 Data Mining
-
Upload
lucian-sasu -
Category
Education
-
view
783 -
download
4
Transcript of Curs 8 Data Mining
Introducere în Data MiningAnaliza grupărilor: concepte de bază şi algoritmi
Lucian Sasu, Ph.D.
Universitatea Transilvania din Braşov, Facultatea de Matematică şi Informatică
May 3, 2012
[email protected] (UNITBV) Curs 8 May 3, 2012 1 / 85
Outline
1 Generalităţi
2 Algoritmul K-means
3 Clustering ierarhic aglomerativ
4 Algoritmul DBSCAN
5 Evaluarea clusterelor
[email protected] (UNITBV) Curs 8 May 3, 2012 2 / 85
Scop
Analiza grupărilor (eng: cluster analysis) divide datele în grupuri, pebaza similarităţilor sau a relaţiilor dintre ele
datele din acelaşi cluster sunt similare între eledatele din alte clustere ar trebui să aibă similaritate mică cu cele dinclusterul curent
[email protected] (UNITBV) Curs 8 May 3, 2012 3 / 85
Scop
Domenii de utilizare:
ştiinţe sociale
biologie
statistică
recunoaştere de şabloane (pattern recognition)
regăsirea informaţiei
analiza imaginilor
bioinformatică
[email protected] (UNITBV) Curs 8 May 3, 2012 4 / 85
Scopul analizei grupărilor
Prin clustering se încearcă obţinerea de grupări care sunt:semnificative: clusterele trebuie să surprindă natura structurală adatelorutile: sumarizarea unui volum mare de date, furnizare de explicaţii
sau ambele
[email protected] (UNITBV) Curs 8 May 3, 2012 5 / 85
Clustering pentru facilizarea înţelegerii
Scop: obţinerea de clase de elemente, utile în analizarea şi înţelegerealumii înconjurătoare.Exemple:
biologie: obţinerea de taxonomii: regn, încrengătură, clasă, ordin,familie, gen, specie;bioinformatică: gruparea genelor şi a proteinelor, presupuse a aveafuncţionalitate similarăpsihologie şi medicină: boli sau stări au diferenţe minore; gruparea lore folosită pentru descoperirea de subcategorii – e.g. diverse tipuri dedepresiiafaceri: gruparea clienţilor în funcţie de similarităţile de achiziţie şirealizarea de reclame particularizate pe grupuri de clienţi
[email protected] (UNITBV) Curs 8 May 3, 2012 6 / 85
Clustering pentru scopuri utilitare
Permite abstractizare faţă de datele care intră în cluster
Alternativ: clusterele se pot caracteriza deseori prin intermediulprototurilorDin acest punct de vedere clustering-ul este modalitatea dedeterminare a celor mai reprezentativi centri de cluster
sumarizare: în loc de a considera datele de plecare, se poate lucra cucentroizii clusterelor; rezultatele pot avea acurateţe comparabilăcompresie: pentru fiecare cluster se consideră centroidul lui; se obţineo aproximare bazată pe substituirea datei iniţiale cu centroidulclusterului de care aparţine; se mai numeşte şi vector quantizationgăsirea eficientă a celor mai apropiaţi vecini: în loc să se calculezedistanţe între toate perechile de obiecte, se poate restricţiona calcululla doar obiectele din acelaşi cluster, sau clustere apropiate
[email protected] (UNITBV) Curs 8 May 3, 2012 7 / 85
Ce nu este analiza clusterelor?
Clasificare supervizată: clustering–ul este de fapt învăţarenesupervizată
Segmentare simplă a datelor, precum gruparea studenţilor după primaliteră din nume
Partiţionarea de grafuri: există câteva elemente comune, darpartiţionarea de grafuri se face după specificaţii externe mai complexedecât pentru clustering, sau subgrafurile obţinute nu au o separareconsiderabilă
[email protected] (UNITBV) Curs 8 May 3, 2012 8 / 85
Ambiguitatea noţiunii de cluster
În multe domenii noţiunea de cluster nu e clar definită
Figure: Moduri de grupare
[email protected] (UNITBV) Curs 8 May 3, 2012 9 / 85
Tipuri de clustering
Trei atribute ale unui proces de clustering:1 ierarhic vs. partiţional2 exclusiv vs. cu suprapuneri vs. fuzzy3 complet vs. parţial
[email protected] (UNITBV) Curs 8 May 3, 2012 10 / 85
Clustering ierarhic vs. partiţional
Gruparea poate fi cu imbricări (ierarhică) sau nu (partiţională)
Clustering partiţional: datele sunt împărţite în subseturi fărăsuprapuneri; fiecare dată face parte din exact un clusterDacă permitem ca un cluster să aibă subclustere ⇒ clustering ierarhic
fiecare nod intern este reuniunea clusterelor reprezentate de nodurilecopilse poate ajunge ca nodurile frunză să conţină exact o înregistrareo partiţionare ierarhică poate fi văzută ca o secvenţă de partiţionăriaplicată pornind de la mulţimea originară a datelor şi grupând succesivfiecare partiţie în parte; partiţionarea poate fi făcută până când seajunge la noduri cu un singur element sau se poate face retezare
[email protected] (UNITBV) Curs 8 May 3, 2012 11 / 85
Clustering partiţional
Figure: Clustering partiţional
[email protected] (UNITBV) Curs 8 May 3, 2012 12 / 85
Clustering ierarhic
Figure: Clustering [email protected] (UNITBV) Curs 8 May 3, 2012 13 / 85
Clustering excluziv vs. cu suprapuneri vs. fuzzy
Excluziv vs non-excluziv:
excluziv: un punct aparţine unui singur clusternon-exclusiv (eng: overlapping): un punct poate fi asociat mai multorclustereutilitatea clusterelor ne–exclusive: pot reprezenta puncte ce aparţinsimultan mai multor clase sau puncte apropiate de zona de separare
Fuzzy clustering: fiecare obiect are o măsură fuzzy de apartenenţă lafiecare cluster
clusterele devin mulţimi fuzzyclustere fuzzy pot fi convertite la unele de tip exclusiv prin alegereapentru fiecare dată a acelui cluster pentru care măsura fuzzy este maimare
[email protected] (UNITBV) Curs 8 May 3, 2012 14 / 85
Clustering parţial vs. complet
Clustering complet: fiecare dată este asociată unui cluster
Clustering parţial: pentru un obiect se poate să nu avem asignare laun cluster
[email protected] (UNITBV) Curs 8 May 3, 2012 15 / 85
Tipuri de clustere
Bine separate
Bazate pe prototipuri
Bazate pe grafuri
Bazate pe densitate
Conceptuale
[email protected] (UNITBV) Curs 8 May 3, 2012 16 / 85
Clustere bine separate
În această viziune: un cluster este un set de puncte astfel încât oricepunct din cluster este mai aproape (sau mai similar) faţă de oricepunct din acel cluster decât de puncte din afara lui
Definiţia e respectată doar când datele sunt grupate grupate naturalîn clustere care sunt depărtate unele de altele
[email protected] (UNITBV) Curs 8 May 3, 2012 17 / 85
Clustere bazate pe prototipuri
În această viziune: un cluster e o mulţime cu proprietatea că unobiect din cluster este mai apropiat/similar de/cu prototipulclusterului decât cu alte prototipuriCa prototip: centroid sau medoid
medoid — punct din setul de date iniţial care e cel mai reprezentativpentru clustercentroid — e.g. centru de greutate; valoarea lui poate să nu coincidăcu niciunul din punctele din centroid
[email protected] (UNITBV) Curs 8 May 3, 2012 18 / 85
Clustere bazate pe grafuri
Util pentru date reprezentate ca graf; un cluster este un grup deobiecte conectate
Exemplu: clustere bazate pe contiguitate: două date sunt conectatedoar dacă se află la o distanţă mai mică decât un prag impus
Posibile probleme: zgomotul poate creşte clusterele în mod artificial -vezi clusterul cu albastru deschis
[email protected] (UNITBV) Curs 8 May 3, 2012 19 / 85
Clustere bazate pe densitate
În această viziune: un cluster este o zonă densă înconjurată de zonăde densitate mică
Zonele de densitate mică separă pe cele cu densitate mare
Utilizate când clusterele sunt neregulate sau se înconjoară unele pealtele sau când zgomotul şi datele outlier sunt prezente
[email protected] (UNITBV) Curs 8 May 3, 2012 20 / 85
Clustere conceptuale
Clusterul este văzut ca un set de obiecte care partajează o proprietatece reiese din mulţimea de puncte din clusterUn algoritm de clustering de acest tip ar trebui să detecteze concepte
[email protected] (UNITBV) Curs 8 May 3, 2012 21 / 85
Outline
1 Generalităţi
2 Algoritmul K-means
3 Clustering ierarhic aglomerativ
4 Algoritmul DBSCAN
5 Evaluarea clusterelor
[email protected] (UNITBV) Curs 8 May 3, 2012 22 / 85
Algoritmul K-means
Algoritm bazat pe prototipuri
Prototipul este un centroid
Tehnica se aplică pentru obiecte din spaţiul continuu n–dimensional
Cel mai popular algoritm de clustering
Variantă înrudită: K-medoid — centroidul este unul din punctele dincluster
[email protected] (UNITBV) Curs 8 May 3, 2012 23 / 85
Paşii algoritmului K-means
1 Se aleg K centroizi iniţiali; K e parametru de intrare2 Fiecare punct este asignat celui mai apropiat centroid3 Fiecare colecţie de puncte asignată unui centroid este un cluster4 Centroidul este modificat pe baza punctelor din clusterul pe care îl
reprezintă5 Se reia de la pasul 2 până când nu se mai schimbă poziţia celor K
centroizi
[email protected] (UNITBV) Curs 8 May 3, 2012 24 / 85
Algoritmul K-means: pseudocod
Figure: Algoritmul K-means
[email protected] (UNITBV) Curs 8 May 3, 2012 25 / 85
Algoritmul K-means: observaţii
Centroizii iniţiali sunt cel mai des aleşi aleator
Centroidul este de regulă media punctelor din clusterApropierea dintre punct şi centroid se consideră ca distanţă sausimilaritate
distanţă Euclidiană, similaritatea cosinus, coeficient de corelaţie etc.
K-Means va converge pentru măsurile de similaritate de mai sus
Convergenţa este rapidă, apare după relativ puţine operaţii
De multe ori condiţia de oprire se schimbă în: “până când relativpuţine puncte îşi schimbă clusterul”
Complexitatea este O(m · K · I · d), unde m = numărul de puncte, K
= numărul de clustere, I = numărul de iteraţii, d = dimensiuneaspaţiului de intrare
[email protected] (UNITBV) Curs 8 May 3, 2012 26 / 85
Algoritmul K-means: exemplificare
Figure: Exemplificare de iteraţii pentru K-means. Punctele marcate cu cruce suntcentroizii de la fiecare pas. La finalizare (pasul d) centroizii se stabilizează.
[email protected] (UNITBV) Curs 8 May 3, 2012 27 / 85
Algoritmul K-means: observaţii
Pasul 4 din algoritm este:Recompute the centroid of each cluster
deoarece centroidul se poate modifica
Modificarea poziţiei centroidului duce la modificarea distanţelor de lapunctele din cluster la centroid
Problema de clustering poate fi privită ca una în care funcţia obiectiveste de a minimiza suma pătratelor distanţelor de la puncte lacentroizii clusterului din care fac parte
Funcţia obiectiv este utilizată pentru măsurarea calităţii clusteringului
[email protected] (UNITBV) Curs 8 May 3, 2012 28 / 85
Algoritmul K-means: clusteringul ca problemă deoptimizare
Funcţia: suma pătratelor erorilor, orig: sum of squared error(SSE), scatterNotaţii:
Simbol Descrierex Un obiectCi Al i–lea clusterci Centroidul clusterului i
c Centroidul tuturor punctelormi Numărul de obiecte din al i–lea clusterm numărul de obiecte din setul de dateK numărul de clustere presupuse
Formula:
SSE =K∑
i=1
∑
x∈Ci
dist(ci , x)2 (1)
[email protected] (UNITBV) Curs 8 May 3, 2012 29 / 85
Algoritmul K-means: clusteringul ca problemă deoptimizare
Dacă se formează clustere diferite atunci valoarea SSE poate diferi dela caz la cazPutem avea deci clustering optimal şi suboptimal
Figure: Clustering optimal vs. suboptimal, relativ la funcţia [email protected] (UNITBV) Curs 8 May 3, 2012 30 / 85
Algoritmul K-means: clusteringul ca problemă deoptimizare
Paşii 3 şi 4 din algoritm încearcă să minimizeze în mod direct SSE
Optimul care se obţine poate fi unul local: se optimizează SSE pentru
anumite alegeri ale locaţiilor centroizilor, nu pentru toate variantele
[email protected] (UNITBV) Curs 8 May 3, 2012 31 / 85
K-means: importanţa alegerii centroizilor iniţiali
Centroizi iniţiali aleşi “inspirat”
Figure: Clustering în care poziţia centroizilor iniţiali este aleasă [email protected] (UNITBV) Curs 8 May 3, 2012 32 / 85
K-means: importanţa alegerii centroizilor iniţiali
Clustere iniţiale alese nefavorabil
Figure: Clustering în care poziţia centroizilor iniţiali este aleasă nefavorabil.
[email protected] (UNITBV) Curs 8 May 3, 2012 33 / 85
Algoritmul K-means: clusteringul ca problemă deoptimizare
K-means nu se reduce doar la date în spaţiul Euclidian
Pentru cazul în care datele se referă la documente: obiectivul estemaximizarea similarităţii între documentele din acelaşi cluster =maximizarea coeziunii clusterului:
Coeziunea totală =K∑
i=1
∑
x∈Ci
cos(x, ci) (2)
[email protected] (UNITBV) Curs 8 May 3, 2012 34 / 85
Algoritmul K-means: metode de reducere a impactuluinegativ de alegere nefavorabilă a centroizilor
Se ia un eşantion de puncte şi se aplică clustering ierarhic; centroiziirezultaţi sunt apoi folosiţi ca şi centroizi iniţiali pentru K-meansclustering
K–means++ [1]1 Se alege uniform un centru din datele iniţiale2 Pentru fiecare punct x se calculează distanţa D(x) de la x la cel mai
apropiat centroid care a fost deja ales3 Alege un punct aleator, cu probabilitatea proporţională cu D2(x)4 Repetă paşii 2 şi 3 până când s-au ales K centroizi
Bisecting K-means
Postprocesare
[email protected] (UNITBV) Curs 8 May 3, 2012 35 / 85
Algoritmul K-means: problema clusterelor goale
Algoritmul originar poate duce la crearea de clustere goale
Cluster gol: niciun punct nu este alocat acelui cluster
Dacă acest centroid este lăsat aşa, SSE creşte mai mult decât e cazulSoluţii:
se renunţă la acest centroid, se alege un altul (e.g. cel mai îndepărtatde oricare din ceilalţi centroizi)se alege un centroid din clusterul care contribuie cel mai mult lacreşterea valorii SSE
Dacă sunt mai multe clustere goale, se procedează în mod repetat camai sus
[email protected] (UNITBV) Curs 8 May 3, 2012 36 / 85
Algoritmul K-means: outliers
Datele de tip outlier influenţează calculul centroizilor; aceştia pot sănu mai fie reprezentativiDe regulă se preferă eliminarea lor înainte de clustering
totuşi: valorile outlier pot corespunde unor date de interes major
Alternativ: se pot detecta şi elimina outliers în faza de postprocesare:se determină acele date care contribuie cel mai mult la creşterea SSEse formează clustere mici constând în grupări de outliers
[email protected] (UNITBV) Curs 8 May 3, 2012 37 / 85
Algoritmul K-means: reducerea SSE prin postprocesare
Strategii:clusterul care are valoarea SSE cea mai mare poate fi împărţit în maimulte subclusterese introduce un nou centroid: cel mai depărtat punct faţă de oriceclusterdispersarea unui cluster: se ignoră centroidul unui cluster, punctele dinel sunt reasignate altor clustere; se alege clusterul care producecreşterea maximă de SSEunirea a două clustere: clusterele cu cel mai apropiat centroid se unescşi rezultă unul singur
[email protected] (UNITBV) Curs 8 May 3, 2012 38 / 85
Algoritmul K-means: modificarea incrementală a clusterelor
În varianta originară poziţia centroizilor este calculată doar după cepunctele sunt asignate celor mai aproppaiţi centri
Variantă: poziţia centroidului să se calculeze după fiecare asignare aunui punct la acel centroid
Avantaj: nu se ajunge la clustere vide
Se poate decide asignarea unui punct la un alt centroid doar dacămanevra duce la îmbunătăţirea funcţiei obiectiv
Dezavantaj: algoritmul devine dependent de ordinea de prezentare adatelor
[email protected] (UNITBV) Curs 8 May 3, 2012 39 / 85
Bisecting K-means
Se bazează pe împărţirea succesivă a unui cluster în două subclustereAlegerea clusterului care se împarte se poate face după mai multecriterii: cel mai larg clsuter, cel care contribuie cel mai mult la SSE,combinaţie de aceste două criteriiPas opţional: se aplică K-means cu centroizii obţinuţi prin bisectingK-means
[email protected] (UNITBV) Curs 8 May 3, 2012 40 / 85
Bisecting K-means: exemplu
Figure: Exemplu de aplicare a algoritmului bisecting K-means.
[email protected] (UNITBV) Curs 8 May 3, 2012 41 / 85
Limitări ale K-means
K-means întâmpină probleme când clusterele sunt de diferitedimensiunidensităţiforme, altceva decât cele circulare
K-means are probleme când datele prezintă outliers
[email protected] (UNITBV) Curs 8 May 3, 2012 42 / 85
Limitări ale K-means: clustere de dimensiuni diferite
[email protected] (UNITBV) Curs 8 May 3, 2012 43 / 85
Limitări ale K-means: clustere de densităţi diferite
[email protected] (UNITBV) Curs 8 May 3, 2012 44 / 85
Limitări ale K-means: clustere neglobulare
[email protected] (UNITBV) Curs 8 May 3, 2012 45 / 85
K-means: puncte tari şi slabe
Puncte tari:simplu de implementateficient: se opreşte după puţine iteraţiibisecting K-means, K-mean++: puţin sensibile la problema iniţializăriiclusterelor
Puncte slabe:nu poate manipula date ce prezintă grupuri non-globulare, dedimensiuni sau densităţi diferiteprobleme la datele care conţin outliersalgoritmul e restricţionat la datele pentru care noţiunea de centroid aresens
[email protected] (UNITBV) Curs 8 May 3, 2012 46 / 85
K-means ca problemă de optimizare
A se vedea [2], secţiunea 8.2.6
[email protected] (UNITBV) Curs 8 May 3, 2012 47 / 85
Outline
1 Generalităţi
2 Algoritmul K-means
3 Clustering ierarhic aglomerativ
4 Algoritmul DBSCAN
5 Evaluarea clusterelor
[email protected] (UNITBV) Curs 8 May 3, 2012 48 / 85
Clustering ierarhic
Produce un set de clustere imbricate organizate ca un arbore
Clusterele pot fi vizualizate sub forma unei dendrograme
[email protected] (UNITBV) Curs 8 May 3, 2012 49 / 85
Clustering ierarhic
Nu trebuie făcute presupuneri asupra numărului de clusterese poate obţine orice număr de clustere prin retezarea dendrogramei lanivelul dorit
Pot corespunde unei taxonomiiexemplu: taxonomia din ştiinţele biologice
[email protected] (UNITBV) Curs 8 May 3, 2012 50 / 85
Clustering ierarhic
Două tipuri de clustering ierarhic
Aglomerativ:
se porneşte cu fiecare punct ca şi cluster
la fiecare pas se uneşte cea mai apropiată pereche de clustere până
rămân k clustere
Diviziv:
se pleacă cu un cluster ce conţine toate punctele
la fiecare pas se divizează un cluster
se continuă procesul până când fiecare cluster conţine un punct, sau se
face retezare când se ajunge la k clustere
[email protected] (UNITBV) Curs 8 May 3, 2012 51 / 85
Clustering ierarhic aglomerativ
Tehnica este populară şi cu vechime
Operaţia esenţială este calculul proximităţii a două clustere
Diferenţele între algoritmii ierahici aglomerativi sunt date de modulde calcul al proximităţii
[email protected] (UNITBV) Curs 8 May 3, 2012 52 / 85
Clustering ierarhic aglomerativ: pornirea procesului
Se porneşte cu clustere formate din câte un punct
[email protected] (UNITBV) Curs 8 May 3, 2012 53 / 85
Clustering ierarhic aglomerativ: starea intermediară
După câţia paşi avem câteva clustere
[email protected] (UNITBV) Curs 8 May 3, 2012 54 / 85
Clustering ierarhic aglomerativ: unirea de 2 clustere
Unim cele mai apropiate două clustere C2 şi C5 şi modificămmatricea de proximitate
[email protected] (UNITBV) Curs 8 May 3, 2012 55 / 85
Clustering ierarhic aglomerativ: unirea de 2 clustere
Problemă: cum se modifică valorile din matricea de proximitate?
[email protected] (UNITBV) Curs 8 May 3, 2012 56 / 85
Clustering ierarhic aglomerativ: definirea similarităţii întreclustere
MINMAXGroup averageDistanţa dintre centroiziAlte metode bazate pe funcţie obiectiv: e.g. metoda lui Ward
[email protected] (UNITBV) Curs 8 May 3, 2012 57 / 85
Clustering ierarhic aglomerativ: MIN
Apropierea clusterelor este dată de distanţa minimă dintre 2 punctedin clustere
[email protected] (UNITBV) Curs 8 May 3, 2012 58 / 85
Clustering ierarhic aglomerativ: MAX
Apropierea clusterelor este dată de distanţa maximă dintre 2 punctedin clustere
[email protected] (UNITBV) Curs 8 May 3, 2012 59 / 85
Clustering ierarhic aglomerativ: group average
Apropierea clusterelor este dată de distanţa medie dintre toateperechile de puncte din clustere
[email protected] (UNITBV) Curs 8 May 3, 2012 60 / 85
Clustering ierarhic aglomerativ: complexitatea de timp şispaţiu
Complexitatea de memorie:
matricea de proximitate: simetrică, dar cu număr iniţial de elementeO(m2)lista de clustere şi apartenenţa punctelor la clustere: O(m), unde m enumărul de clustere
Complexitate de timp:Căutarea liniară a clusterelor proxime la iteraţia i : O((m − i + 1)2); întotal este complexitate de O(m3)Dacă pentru fiecare cluster se menţine o listă sortată (sau heap) aclusterelor în funcţie de proximitate, se reduce costul căutării celui maiapropiat cluster la O(m − i + 1); împreună cu costul menţinerii listelorsortate se ajunge la complexitate de timp O(m2 log m)
[email protected] (UNITBV) Curs 8 May 3, 2012 61 / 85
Clustering ierarhic aglomerativ: MIN
Numită şi single link
Similaritatea a două clustere este dată de distanţa celor mai apropiatepuncte din ele
[email protected] (UNITBV) Curs 8 May 3, 2012 62 / 85
Clustering ierarhic aglomerativ: MIN
Figure: In stânga: numerele de lângă clustere reprezintă ordinea de grupare.Dendrograma asociată este în dreapta; cu cât o unire de clustere este mai jos, cuatât s–a făcut mai devreme.
[email protected] (UNITBV) Curs 8 May 3, 2012 63 / 85
Clustering ierarhic aglomerativ: MIN
Aspect bun al algoritmului: poate manipula forme necirculare
[email protected] (UNITBV) Curs 8 May 3, 2012 64 / 85
Clustering ierarhic aglomerativ: MIN
Limitări ale clusteringului ierarhic prin MIN: senzitivitate la zgomot şioutliers
[email protected] (UNITBV) Curs 8 May 3, 2012 65 / 85
Clustering ierarhic aglomerativ: MAX
Similaritatea a două clustere este dată de cele mai distanţate douăpuncte din ele
[email protected] (UNITBV) Curs 8 May 3, 2012 66 / 85
Clustering ierarhic aglomerativ: MAX
Punct tare: puţin sensibil la zgomot şi outliersPuncte slabe:
tinde să evite crearea de clustere maritinde să creeze clustere circulare
[email protected] (UNITBV) Curs 8 May 3, 2012 67 / 85
Clustering ierarhic aglomerativ: Group average
Proximitatea a două clustere este dată de media proximităţilor dintrepunctele din ele
proximitate(clusteri , clusterj) =
∑pi ∈clusteri ,pj ∈clusterj
proximitate(pi , pj)
|clusteri | · |clusterj |
numitorul este necesar pentru că altfel s–ar defavoriza clusterele mari
[email protected] (UNITBV) Curs 8 May 3, 2012 68 / 85
Clustering ierarhic aglomerativ: Group average
[email protected] (UNITBV) Curs 8 May 3, 2012 69 / 85
Clustering ierarhic aglomerativ: Group average
Parte bună: mai puţin susceptibil la zgomot şi outliers
Limitare: tinde să producă clustere globulare
[email protected] (UNITBV) Curs 8 May 3, 2012 70 / 85
Clustering ierarhic aglomerativ: metoda lui Ward
Metoda lui Ward: proximitatea a două clustere e definită ca şicreşterea erorii pătratice atunci când două clustere sunt unite
Foarte similară cu metoda group average dacă distanţa consideratăîntre puncte este luată ca pătratul distanţei euclidiene
Mai puţin susceptibilă la zgomot şi outliers
Are tendinţa de a produce clustere globulare
Poate fi utilizată pentru iniţializarea centrilor de clustere în metodaK-means
[email protected] (UNITBV) Curs 8 May 3, 2012 71 / 85
Clustering ierarhic aglomerativ: comparaţie
Figure: Clusterele obţinute de cele 4 metode diferă
[email protected] (UNITBV) Curs 8 May 3, 2012 72 / 85
Clustering ierarhic aglomerativ: probleme şi limitări
Odată ce o decizie de unire de clustere este luată, nu se mai revine
Nu există o funcţie obiectiv care să fie optimizatăDiferite forme de clustering ierarhic aglomerativ suferă de variiprobleme:
senzitivitate la zgomot şi outliersdificultate în manipularea de clustere cu dimensiuni diferite sau cuforme neconvexetendinţa de spargere a clusterelor mari
[email protected] (UNITBV) Curs 8 May 3, 2012 73 / 85
Outline
1 Generalităţi
2 Algoritmul K-means
3 Clustering ierarhic aglomerativ
4 Algoritmul DBSCAN
5 Evaluarea clusterelor
[email protected] (UNITBV) Curs 8 May 3, 2012 74 / 85
DBSCAN
Denumirea completă: Density-Based Spatial Clustering ofApplications with Noise
Se localizează regiuni de densitate mare care sunt separate prin zonede densitate mică
Densitate: numărul de puncte de pe o rază specificată Eps, din jurulunui punct – inclusiv punctul respectiv
Valoarea Eps e critică: prea mult ⇒ orice punct are suficienţi vecini;valoare prea mică ⇒ densitatea în jurul majorităţii punctelor va fi 1
[email protected] (UNITBV) Curs 8 May 3, 2012 75 / 85
DBSCAN
Definiţie (Punct nucleu)
Un punct nucleua este un punct din setul iniţial care are cel puţin MinPts
vecini în jurul lui, la distanţă mai mică decât Eps
aEngl: core point.
Definiţie (Punct de frontieră)
Un punct de frontierăa este un punct din setul iniţial care nu are MinPts
vecini în jurul lui, la distanţă mai mică decât Eps, dar este în vecinătatea
unui punct nucleu.
aEngl: border point.
Definiţie (Punct zgomot)
Un punct zgomot e un punct care nu e nucleu sau de frontieră.
[email protected] (UNITBV) Curs 8 May 3, 2012 76 / 85
DBSCAN: puncte nucleu, de frontieră, zgomot
[email protected] (UNITBV) Curs 8 May 3, 2012 77 / 85
Algoritmul DBSCAN
Informal: oricare două puncte nucleu care sunt suficient de apropiate– la distanţă nu mai mare de Eps – sunt depuse în acelaşi cluster
Orice punct de frontieră care e suficient de apropiat de un punctnucleu este pus în acelaşi cluster ca punctul nucleu
Punctele zgomot sunt eliminate
[email protected] (UNITBV) Curs 8 May 3, 2012 78 / 85
DBSCAN: exemplu
[email protected] (UNITBV) Curs 8 May 3, 2012 79 / 85
DBSCAN: complexitate
Complexitatea de timp: pentru m puncte,O(m × timpul necesar pentru a contoriza puncte în raza Eps), deciîn cel mai rău caz O(m2)
Pentru spaţii cu puţine dimensiuni, dacă se foloseşte kd-tree, atunciO(m log2 m)
Complexitatea de memorie: O(m), deoarece pentru fiecare datătrebuie menţinut doar indicele clusterului şi tipul de punct
[email protected] (UNITBV) Curs 8 May 3, 2012 80 / 85
DBSCAN: părţi bune
Rezistent la zgomot
Poate obţine clustere de forme şi dimensiuni diferite
[email protected] (UNITBV) Curs 8 May 3, 2012 81 / 85
DBSCAN: părţi slabe
Densităţi neomogeneDate cu multe dimensiuni
[email protected] (UNITBV) Curs 8 May 3, 2012 82 / 85
Outline
1 Generalităţi
2 Algoritmul K-means
3 Clustering ierarhic aglomerativ
4 Algoritmul DBSCAN
5 Evaluarea clusterelor
[email protected] (UNITBV) Curs 8 May 3, 2012 83 / 85
Bibliografie
Arthur, D. and Vassilvitskii, S., “k-means++: the advantages of
careful seeding” 2007, Proceedings of the eighteenth annualACM-SIAM symposium on Discrete algorithms, pp. 1027Ű1035
Pang-Ning Tan, Michael Steinbach, and Vipin Kumar: Introduction to
Data Mining, 2006, Addison-Wesley
[email protected] (UNITBV) Curs 8 May 3, 2012 85 / 85