Curs 8 Data Mining

85
Introducere în Data Mining Analiza 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

Transcript of Curs 8 Data Mining

Page 1: 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

Page 2: Curs 8 Data Mining

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

Page 3: Curs 8 Data Mining

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

Page 4: Curs 8 Data Mining

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

Page 5: Curs 8 Data Mining

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

Page 6: Curs 8 Data Mining

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

Page 7: Curs 8 Data Mining

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

Page 8: Curs 8 Data Mining

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

Page 9: Curs 8 Data Mining

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

Page 10: Curs 8 Data Mining

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

Page 11: Curs 8 Data Mining

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

Page 12: Curs 8 Data Mining

Clustering partiţional

Figure: Clustering partiţional

[email protected] (UNITBV) Curs 8 May 3, 2012 12 / 85

Page 13: Curs 8 Data Mining

Clustering ierarhic

Figure: Clustering [email protected] (UNITBV) Curs 8 May 3, 2012 13 / 85

Page 14: Curs 8 Data Mining

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

Page 15: Curs 8 Data Mining

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

Page 16: Curs 8 Data Mining

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

Page 17: Curs 8 Data Mining

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

Page 18: Curs 8 Data Mining

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

Page 19: Curs 8 Data Mining

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

Page 20: Curs 8 Data Mining

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

Page 21: Curs 8 Data Mining

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

Page 22: Curs 8 Data Mining

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

Page 23: Curs 8 Data Mining

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

Page 24: Curs 8 Data Mining

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

Page 25: Curs 8 Data Mining

Algoritmul K-means: pseudocod

Figure: Algoritmul K-means

[email protected] (UNITBV) Curs 8 May 3, 2012 25 / 85

Page 26: Curs 8 Data Mining

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

Page 27: Curs 8 Data Mining

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

Page 28: Curs 8 Data Mining

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

Page 29: Curs 8 Data Mining

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

Page 30: Curs 8 Data Mining

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

Page 31: Curs 8 Data Mining

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

Page 32: Curs 8 Data Mining

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

Page 33: Curs 8 Data Mining

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

Page 34: Curs 8 Data Mining

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

Page 35: Curs 8 Data Mining

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

Page 36: Curs 8 Data Mining

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

Page 37: Curs 8 Data Mining

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

Page 38: Curs 8 Data Mining

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

Page 39: Curs 8 Data Mining

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

Page 40: Curs 8 Data Mining

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

Page 41: Curs 8 Data Mining

Bisecting K-means: exemplu

Figure: Exemplu de aplicare a algoritmului bisecting K-means.

[email protected] (UNITBV) Curs 8 May 3, 2012 41 / 85

Page 42: Curs 8 Data Mining

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

Page 43: Curs 8 Data Mining

Limitări ale K-means: clustere de dimensiuni diferite

[email protected] (UNITBV) Curs 8 May 3, 2012 43 / 85

Page 44: Curs 8 Data Mining

Limitări ale K-means: clustere de densităţi diferite

[email protected] (UNITBV) Curs 8 May 3, 2012 44 / 85

Page 45: Curs 8 Data Mining

Limitări ale K-means: clustere neglobulare

[email protected] (UNITBV) Curs 8 May 3, 2012 45 / 85

Page 46: Curs 8 Data Mining

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

Page 47: Curs 8 Data Mining

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

Page 48: Curs 8 Data Mining

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

Page 49: Curs 8 Data Mining

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

Page 50: Curs 8 Data Mining

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

Page 51: Curs 8 Data Mining

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

Page 52: Curs 8 Data Mining

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

Page 53: Curs 8 Data Mining

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

Page 54: Curs 8 Data Mining

Clustering ierarhic aglomerativ: starea intermediară

După câţia paşi avem câteva clustere

[email protected] (UNITBV) Curs 8 May 3, 2012 54 / 85

Page 55: Curs 8 Data Mining

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

Page 56: Curs 8 Data Mining

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

Page 57: Curs 8 Data Mining

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

Page 58: Curs 8 Data Mining

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

Page 59: Curs 8 Data Mining

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

Page 60: Curs 8 Data Mining

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

Page 61: Curs 8 Data Mining

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

Page 62: Curs 8 Data Mining

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

Page 63: Curs 8 Data Mining

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

Page 64: Curs 8 Data Mining

Clustering ierarhic aglomerativ: MIN

Aspect bun al algoritmului: poate manipula forme necirculare

[email protected] (UNITBV) Curs 8 May 3, 2012 64 / 85

Page 65: Curs 8 Data Mining

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

Page 66: Curs 8 Data Mining

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

Page 67: Curs 8 Data Mining

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

Page 68: Curs 8 Data Mining

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

Page 69: Curs 8 Data Mining

Clustering ierarhic aglomerativ: Group average

[email protected] (UNITBV) Curs 8 May 3, 2012 69 / 85

Page 70: Curs 8 Data Mining

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

Page 71: Curs 8 Data Mining

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

Page 72: Curs 8 Data Mining

Clustering ierarhic aglomerativ: comparaţie

Figure: Clusterele obţinute de cele 4 metode diferă

[email protected] (UNITBV) Curs 8 May 3, 2012 72 / 85

Page 73: Curs 8 Data Mining

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

Page 74: Curs 8 Data Mining

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

Page 75: Curs 8 Data Mining

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

Page 76: Curs 8 Data Mining

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

Page 77: Curs 8 Data Mining

DBSCAN: puncte nucleu, de frontieră, zgomot

[email protected] (UNITBV) Curs 8 May 3, 2012 77 / 85

Page 78: Curs 8 Data Mining

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

Page 79: Curs 8 Data Mining

DBSCAN: exemplu

[email protected] (UNITBV) Curs 8 May 3, 2012 79 / 85

Page 80: Curs 8 Data Mining

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

Page 81: Curs 8 Data Mining

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

Page 82: Curs 8 Data Mining

DBSCAN: părţi slabe

Densităţi neomogeneDate cu multe dimensiuni

[email protected] (UNITBV) Curs 8 May 3, 2012 82 / 85

Page 83: Curs 8 Data Mining

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

Page 84: Curs 8 Data Mining

Evaluarea clusterelor

[2], secţiunea 5.8

[email protected] (UNITBV) Curs 8 May 3, 2012 84 / 85

Page 85: Curs 8 Data Mining

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