Data Mining: Clustering docent: dr. Toon Calders
Gebaseerd op slides van Tan, Steinbach, and Kumar. Introduction to Data Mining
Wat is clustering? Het onderverdelen van de objecten in een database in homogene groepen. Input: – Relatie R(A1, …, An)
• Output: – { C1, …, Cn} met C1, …, Cn ⊆ R
• Criterium: – Gelijkenis binnen 1 groep is groter dan gelijkenis tussen objecten van verschillende groepen.
Wat is clustering? Inter-cluster afstanden maximaliseren
Intra-cluster afstanden minimaliseren
Toepassingen van cluster analyse • Begrijpen – Groepeer gerelateerde documenten, genen, stocks, …
• Samenvatten –Reduceer de grootte van de dataset; individuele punten worden samengevat door hun cluster
Discovered Clusters
1 2 3 4
Applied-Matl-DOWN,Bay-Network-Down,3-COM-DOWN, Cabletron-Sys-DOWN,CISCO-DOWN,HP-DOWN, DSC-Comm-DOWN,INTEL-DOWN,LSI-Logic-DOWN, Micron-Tech-DOWN,Texas-Inst-Down,Tellabs-Inc-Down, Natl-Semiconduct-DOWN,Oracl-DOWN,SGI-DOWN, Sun-DOWN Apple-Comp-DOWN,Autodesk-DOWN,DEC-DOWN, ADV-Micro-Device-DOWN,Andrew-Corp-DOWN, Computer-Assoc-DOWN,Circuit-City-DOWN, Compaq-DOWN, EMC-Corp-DOWN, Gen-Inst-DOWN, Motorola-DOWN,Microsoft-DOWN,Scientific-Atl-DOWN Fannie-Mae-DOWN,Fed-Home-Loan-DOWN, MBNA-Corp-DOWN,Morgan-Stanley-DOWN Baker-Hughes-UP,Dresser-Inds-UP,Halliburton-HLD-UP, Louisiana-Land-UP,Phillips-Petro-UP,Unocal-UP, Schlumberger-UP
Clusters van neerslag in Australia
Industry Group
Technology1-DOWN
Technology2-DOWN
Financial-DOWN Oil-UP
Notie “Cluster” is vaak ambigu
Hoeveel clusters?
6?
Of 2?
Misschien 4?
Types van clusterings • Een clustering is een verzameling clusters • Hiërarchische en partitionele clusterings. { C1, …, Cn } is een – Partitional Clustering: Ci ∩ Cj = {} voor alle 1 ≤ i < j ≤n – Hiërarchische clustering: Ci ∩ Cj = {} of Ci ∩ Cj = Ci of Ci ∩ Cj = Cj voor alle 1 ≤ i < j ≤n
Partitionele Clustering
Originele punten
Partitionele clustering
Hiërarchische Clustering p1 p3
p4
p2
p1 p2 Traditionele Hiërarchische Clustering
p3 p4
Traditioneel Dendrogram
p1 p3
p4
p2
p1 p2 Niet-traditionele Hiërarchische Clustering
p3 p4
Niet-traditioneel Dendrogram
Clustering Algoritmes •K-means en varianten •Density-based clusterings •Hierarchische clusterings
K-means Clustering • • • •
Partitionele clustering benadering Elke cluster wordt geassocieerd met een centroid (centraal punt) Elk punt gaat naar de cluster met de dichtstbijzijnde centroid Aantal clusters K moet vooraf gespecifieerd worden
K-Means Clustering Veronderstelling: We hebben een afstandsmaat op D en we kunnen van een verzameling punten S het centrum bepalen centroid(S). Input: constante K, database D, afstandsmaat d Output: Partitie {C1, …, CK} van D zodanig dat: ∀i ∈ {1, …, K}: ∀x∈Ci: ∀j ∈ {1, …, K}: i≠j ⇒ d(x,centroid(Ci)) ≤ d(x, centroid(Cj)) (Elk punt is dichter bij z’n eigen centroid dan bij elke andere centroid)
K-Means Clustering
K-means: Voorbeeld Iteration 6 1 2 3 4 5 3
2.5
2
y
1.5
1
0.5 0
-2
-1.5
-1
-0.5
0
0.5
1
1.5
2
x
K-means: Voorbeeld Iteration 1
Iteration 2
Iteration 3
2.5
2.5
2.5
2
2
2
1.5
1.5
1.5
y
3
y
3
y
3
1
1
1
0.5
0.5
0.5
0
0
-2
-1.5
-1
-0.5
0
0.5
1
1.5
2
0
-2
-1.5
-1
-0.5
x
0
0.5
1
1.5
2
-2
Iteration 4
Iteration 5 2.5
2
2
1.5
1.5
1.5
1
1
1
0.5
0.5
0.5
0
0
-0.5
0
x
0.5
1
1.5
2
0
0.5
1
1.5
2
1
1.5
2
y
2.5
2
y
2.5
y
3
-1
-0.5
Iteration 6
3
-1.5
-1
x
3
-2
-1.5
x
0
-2
-1.5
-1
-0.5
0
x
0.5
1
1.5
2
-2
-1.5
-1
-0.5
0
x
0.5
Belang van een goede keuze van de initiële centroids … Originele Punten 3
2.5 2
y
1.5
1
0.5 0
-2
-1.5
-1
-0.5
0
0.5
1
1.5
2
x 3
3
2.5
2.5
2
2
1.5
y
y
1.5
1
1
0.5
0.5
0
0 -2
- 1.5
-1
-0 .5
0
0 .5
1
1 .5
2
-2
x
- 1.5
-1
-0.5
0
0.5
Iteration 5 1 2 3 4 3
2.5
2
y
1.5
1
0.5 0
-1.5
-1
1.5
2
Sub-optimale Clustering
Belang van een goede keuze van de initiële centroids …
-2
1
x
Optimale Clustering
-0.5
0
x
0.5
1
1.5
2
Belang van een goede keuze van de initiële centroids … Iteration 1
Iteration 2
3
3
2.5
2.5
y
2
1.5
y
2
1.5
1
1
0.5
0.5
0
0
-2
-1.5
-1
-0.5
0
0.5
1
1.5
2
-2
-1.5
-1
-0.5
x
0
0.5
2.5
2
2
1.5
1.5
1.5
y
2.5
2
y
2.5
y
3
1
1
1
0.5
0.5
0.5
0
0
-1
-0.5
0
x
0.5
2
Iteration 5
3
-1.5
1.5
Iteration 4
3
-2
1
x
Iteration 3
1
1.5
2
0
-2
-1.5
-1
-0.5
0
0.5
1
1.5
2
-2
-1.5
-1
-0.5
x
0
0.5
1
1.5
2
x
Problemen bij de selectie van initiële pntn •
Als er K echte clusters zijn, is de kans relatief klein dat we in elke echte cluster een punt hebben: –
Als alle “echte” clusters grootte n hebben:
–
Bijvoorbeeld, als K = 10, dan is de kans slechts = 10!/1010 = 0.00036 (!!) Soms komt dit nog goed tijdens het algoritme, soms ook niet.
–
Oplossingen voor dit probleem • Meerdere runs – Helpt, maar de kansen zijn erg laag …
• Gebruik ander algoritme om clusters te vinden en gebruik deze als input voor K-means • Selecteer meer dan K initiele centroids – Selecteer achteraf de verst van elkaar gelegen clusters
• Postprocessing
Beperkingen van K-means • K-means heeft problemen als – de clusters te erg verschillen qua grootte – de clusters te erg verschillen qua densiteit – De clusters geen bolvorm hebben – De data outliers bevat – De dimensionaliteit van de data hoog is
Beperkingen: verschillende groottes
Originele punten
K-means (3 Clusters)
Beperkingen: verschillende densiteit
Originele punten
K-means (3 Clusters)
Beperkingen: geen bolvorm
Originele punten
K-means (2 Clusters)
Oplossingen voor de beperkingen
Originele punten
K-means Clustering
Een oplossing is K veel groter nemen dan het veronderstelde aantal clusters Achteraf worden dicht bij elkaar gelegen clusters samengevoegd
Oplossingen voor de beperkingen
Originele punten
K-means Clustering
Oplossingen voor de beperkingen
Originele punten
K-means Clustering
Clustering Algoritmes • K-means en varianten • Density-based clusterings • Hiërarchische clusterings
Density-based clustering
Density-based clustering
DBSCAN • DBSCAN is hierop gebaseerd • Input: – een afstandsmaat d – een dataset D – Getallen µ en ε
• Output: – Een partitionering { C1, …, Cn } van D zodat: • Voor alle punten x,y die voldoen aan volgende voorwaarde geldt dat ze in dezelfde cluster zitten: | { z | d(x,z) ≤ ε } | ≥ µ en | { z | d(y,z) ≤ ε } | ≥ µ en d(x,y) ≤ ε
Density-based clustering: DBSCAN • ε -densiteit van een punt = aantal punten binnen straal ε • Een punt is een (ε, µ) -core punt indien er meer dan µ punten zijn binnen een straal ε • Een (ε, µ) -border punt heeft minder dan µ punten binnen straal ε, maar ligt binnen een straal ε van ten minste een core punt • Alle andere punten worden ruis punten genoemd.
Density-based clustering: DBSCAN • Een punt y is (ε, µ)-density-reachable vanuit punt x indien er een sequentie c1, …, ck van (ε,µ)-core punten bestaat zodanig dat: – d(x,c1) ≤ ε – ∀i∈{1, …, n-1} : d(ci,ci+1) ≤ ε – d(cn,y) ≤ ε
• Opmerking: berekening van alle paren (x,y) zodat y (ε, µ)-density-reachable vanuit een core punt x = berekenen van transitieve afsluiting.
DBSCAN: Core, Border, en Ruis Punten
DBSCAN Algorithm 1. Elimineer de ruis punten 2. i=1 3. Zolang er core punten zijn die nog niet aan een cluster zijn toegekend: •
Neem een willekeurig nog niet toegekend core point c
•
Ci = { y | y is (ε,µ)- density reachable vanuit c, y is nog niet toegekend} i := i+1
•
4. Return { C1, …, Ci-1 }
Voorbeeld: DBSCAN
Eerste punt wordt geselecteerd
Alle punten die densityreachable zijn worden aan de cluster toegevoegd
Tweede selectie
Tweede cluster wordt gevormd
Derde selectie en constructie van de cluster
DBSCAN: Core, Border and Noise Points
Punt types: core, border en noise
Originele punten
ε = 10, µ = 4
Waneer werkt DBSCAN goed?
Originele punten
Clustering
• Resistent voor ruis • Kan clusters met verschillende vormen en groottes aan
Wanneer werkt DBSCAN niet goed?
Originele punten
(µ =4, ε = 9.75)
• Variërende densiteit • Hoog dimensionele data
(µ =4, ε = 9.92)
DBSCAN: Bepalen van ε en µ • Voor punten binnen een cluster is de afstand tot hun k-de buur ongeveer gelijk • Ruis punten hebben hun k-de buur op veel grotere afstand • Dus, plot de cumulatieve distributie van de afstand tussen alle punten en hun k-de buur.
DBSCAN: Bepalen van ε en µ
Conclusies • Clustering is het onderverdelen van de objecten in een database in homogene groepen • Notie van een cluster is ambigu … • Twee partitieve algoritmes – K-Means – DBSCAN
Conclusies • K-Means – Aantal clusters K gegeven – Elk punt ligt dichter bij z’n eigen cluster center dan bij de centra van de andere clusters
• DBSCAN – Gebaseerd op dichtheid – Twee punten op korte afstand in dichtbevolkt gebied moeten tot dezelfde cluster behoren – Aantal clusters niet op voorhand bepaald
• Clustering-algoritmes scoren slecht in hoogdimensionele data
