Shlukování a velké soubory dat Hana Řezanková Vysoká škola ekonomická v Praze
Osnova
Cíle shlukování Problematika velkých souborů Zdokonalení tradičních metod Speciální metody pro velký počet objektů Shlukování podprostorů (vhodné pro velký počet proměnných)
2
Cíle klasifikace a shlukové analýzy
Cílem klasifikace je zařadit buď některé z objektů nebo všechny objekty do skupin. Shlukování: nemáme žádné informace o existenci skupin a chceme klasifikovat všechny sledované objekty (chceme vytvořit shluky). Shluková analýza je postup formulovaný jako procedura, pomocí níž objektivně seskupujeme jedince do skupin na základě jejich podobnosti a odlišnosti (zkráceně R. C. Tryon, 1939). 3
Problematika velkých souborů Dvě základní skupiny shlukovacích metod:
metody založené na vzdálenostech, tj. na
analýze matice vzdáleností mezi objekty (hierarchická shluková analýza, vícerozměrné škálování), metody vektorového prostoru – vycházejí přímo z původní zdrojové matice objekty x proměnné, každý řádek představuje vektor charakterizující určitý objekt (metoda k-průměrů). 4
Problémy velkých souborů
Nelze použít metody založené na vzdálenostech (kapacitně a výpočetně) Grafické znázornění postrádá smysl Bez grafu je obtížné navrhnout počet shluků (absence procedur pro určení počtu) Při existenci odlehlých objektů tvoří tyto objekty samostatné shluky
5
Problematika velkých souborů Základní požadavky kladené na shlukovací techniky pro velké soubory dat:
přiměřená náročnost (požadavky na strojový čas
a na paměť),
nezávislost na pořadí vstupu (tj. pořadí, v němž
jsou objekty zařazovány do analýzy) a
schopnost ohodnotit platnost vytvořených shluků. 6
Problematika velkých souborů Požadavky na robustnost metod zejména v následujících oblastech:
dimenzionalita (rozdílnost mezi objekty by měla být
zjistitelná i v případě velkého počtu proměnných), šum a odlehlá pozorování (algoritmus musí být schopen odhalit šum a odlehlá pozorování a eliminovat jejich negativní vlivy), statistické rozdělení, tvar shluků, velikost shluků, hustota shluků, oddělení shluků (algoritmus musí být schopen zjistit překrývající se shluky), typy proměnných (algoritmus by měl být určen pro různé typy proměnných, tj. kvantitativní spojité i kategoriální). 7
Řešení pro velké soubory
Iterativní postupy k-průměrů, k-medoidů,…
+ Kohonenova mapa (typ neuronové sítě) Algoritmy rychlého rozdělování (Hartigan):
algoritmus hlavního objektu (Leader Algorithm), třídící algoritmus (Sorting Algorithm).
Hybridní přístup (Gordon):
výběr objektů + shlukování ve výběru, zbylé objekty přiřazovány k vytvořeným shlukům.
8
Řešení pro velké soubory
Algoritmy rychlého rozdělování: algoritmus hlavního objektu:
množinu objektů prochází pouze jednou, míra vzdálenosti D a prahová hodnota T .
třídící algoritmus:
pro každou (j-tou) proměnnou stanovena prahová hodnota T(j), algoritmus prochází množinou objektů tolikrát, kolik je proměnných, shluky tvoří políčka vícerozměrné kontingenční tabulky. 9
Řešení nedostatku vnitřní paměti
Přístup „rozděl a panuj“:
data rozdělena do p bloků, v každém objekty shlukovány do k shluků, získáme pk reprezentativních objektů, reprezentanti shlukováni do k shluků, zbývající objekty přiřazeny k vytvořeným shlukům .
Postupné shlukování:
shlukovací algoritmus hlavního objektu (viz výše), nejkratší cesta typu SSP (shortest spanning path), „pavučinový“ (cobweb) systém (postupný konceptuální shlukovací algoritmus), postupný shlukovací algoritmus pro dynamické zpracování informací. 10
Metody pro rozsáhlé databáze (Berkhin: Survey of Clustering Data Mining Techniques. Inet)
Postupné „dobývání“ (mining) – viz výše „Drcení“ (squashing) dat – postačující statistiky
(souhrny) za skupiny objektů, např. CF (cluster feature) charakteristika (BIRCH):
počet objektů ve shluku, součet hodnot pro každou proměnnou, součet druhých mocnin těchto hodnot.
Spolehlivé vzorkování (CLARANS) 11
Problematika velkého počtu proměnných Více než 16 proměnných – data s vysokou dimenzí
Řešení – redukce dimenze:
transformace proměnných (agregování
proměnných, analýza hlavních komponent, singular value decomposition – SVD), doménová dekompozice (data rozdělena do podsouborů – canopies), metody založené na shlukování podprostorů (subspace clustering). 12
Shlukování pro velké datové soubory (Mercer: Clustering Large Datasets. Inet)
Postupy vycházející z tradičních metod:
nehierarchické metody, hierarchické algoritmy a metody založené na modelu,
Metody speciálně vytvořené pro velké soubory:
metody založené na hustotě, metody založené na mřížce, metody založené na modelu, smíšené (hybridní) metody. 13
Zdokonalení tradičních metod – nehierarchický přístup
CLARA (Clustering LARge Applications): 1990, Kaufman a Rousseeuw (z metody PAM), S-PLUS.
CLARANS (Clustering Large Applications based on a RANdomized Search):
1994, Ng a Han.
Hybridní klasifikace (dvoufázová):
např. 1986, Gordon (sborník z COMPSTATu). 14
Řešení pro velké soubory CLARA (S-PLUS):
základem metoda k-medoidů (shluk je charakterizován jedním jeho objektem), nejdříve je proveden náhodný výběr objektů, ty jsou rozděleny do k skupin, každý zbylý objekt přiřazen k nejbližší skupině, proces je opakován, vybráno shlukování s nejmenší průměrnou vzdáleností. 15
Zdokonalení tradičních metod – hierarchický přístup
Frakcionování – 1992, Cutting a kolektiv Refrakcionování – 2002, Tantrum a kolektiv BIRCH (Balanced Iterative Reducing using Cluster Hierarchies) – 1996, Zhang a kolektiv Dvoukroková shluková analýza (procedura TwoStep Cluster analysis v SPSS) CURE (Clustering Using REpresentatives) – 1998, ROCK (RObust Clustering using linKs) – 1999, Guha a kol., Chameleon – 1999, Karypis a kol. 16
Řešení pro velké soubory Dvoukroková shluková analýza (SPSS 11.5)
Vytvoření pomocných shluků (sekvenčně) + shlukování pomocných shluků (hierarchicky) Analýza spojitých i kategoriálních proměnných Stanovení počtu shluků Identifikace odlehlých objektů Klasifikační proměnná v datovém editoru Charakteristika shluků ve výstupní sestavě 17
Dvoukroková shluková analýza Sekvenční vytváření pomocných shluků:
modifikovaná CF charakteristika:
počet objektů vstupu, střední hodnota a rozptyl každé spojité proměnné, četnosti každé kategorie každé kategoriální proměnné,
algoritmus vytváří tzv. strom:
strom se skládá z několika úrovní uzlů, rozlišovány listové a nelistové uzly, každý uzel obsahuje určitý počet vstupů,
vstupy do listových uzlů reprezentují konečné podshluky.
18
Dvoukroková shluková analýza Sekvenční vytváření pomocných shluků:
přepočítání CF charakteristiky:
po zařazení nového objektu do poshluku na základě nového objektu a původní CF charakteristiky, bez znalostí individuálních objektů v podshluku, což snižuje nároky na operační paměť,
zjišťování odlehlých objektů:
pokud počet objektů ve vstupu je menší než stanovený podíl (např. 25 %) velikosti největšího vstupu listového uzlu v CF stromu, jsou objekty považovány za odlehlé. 19
Dvoukroková shluková analýza V obou krocích 2 míry nepodobnosti:
Euklidovská vzdálenost, míra typu věrohodnostní poměr (log-likelihood): d ( h , h ' ) = ξ h + ξ h ' − ξ h ,h ' p ⎛p 1 ⎞ 2 2 ξ v = −nv ⎜⎜ ∑ log(s j + svj ) + ∑ H vj ⎟⎟ j =1 ⎝ j =1 2 ⎠ A
B
Lj
H vj = − ∑ l =1
nvjl nv
log
nvjl nv
20
Dvoukroková shluková analýza Předpoklady pro použití míry nepodobnosti typu věrohodnostní poměr:
proměnné spojité (z normálního rozdělení) i kategoriální (z multinomického rozdělení), nezávislost proměnných, spojité proměnné jsou standardizovány.
21
Dvoukroková shluková analýza Stanovení vhodného počtu shluků:
BIC (Bayesian Information Criterion): k
BIC ( k ) = −2∑ ξ v + mk log(n ) v =1
AIC (Akaike Information Criterion): ⎛ A p ⎞ mk = k ⎜⎜ 2 p + ∑ (L j − 1)⎟⎟ j =1 ⎝ ⎠ B
k
AIC ( k ) = −2∑ ξ v + 2mk v =1
22
Aplikace – charakteristika dat Ozeki, T. et al. Environ. Sci. Technol. 29 (1995).
391 vzorků deště z Japonska z let 1991 až 1992 9 proměnných – koncentrace látek: aniontů chloridových (Cl ( -), dusičnanových (NO3-), síranových (SO ( 42-) a kationtů sodných (Na ( +), draselných (K ( +), vápenatých (Ca ( 2+), hořečnatých (Mg ( 2+), amonných (NH ( +) ( 4+), a vodíkových (H 23
Aplikace – analýza vzorků deště
Dvoukroková shluková analýza – 2 shluky, míra typu věrohodnostní poměr (likelihood): nadprůměrné hodnoty u všech sledovaných látek (194 vzorků) – znečištěný déšť, podprůměrné hodnoty u všech sledovaných látek (197 vzorků) – neznečištěný déšť.
24
Aplikace – analýza vzorků deště Dvoukroková shluková analýza – 4 shluky Shluk (četnost) Složení
1 (82)
2 (84)
3 (175)
4 (50)
[Cl-]
0,61
1,97
0,32
2,4
[NO3-]
1,82
0,87
0,35
2,14
[SO42-]
1,57
1,02
0,4
2,15
[Na+]
0,71
1,93
0,38
2,06
[K+]
1,13
1,1
0,34
2,92
[Ca2+]
1,26
1,22
0,3
2,68
[Mg2+]
0,86
1,6
0,29
2,68
[NH4+]
1,65
1,02
0,25
2,53
[H+]
2,41
0,62
0,65
0,54
Průměrné hodnoty
25
Krabičkové grafy pro proměnné podle shluků Déšť z průmyslových oblastí
Déšť s mořskou vodou 4
7
87 93
105 151
6
109
3
5
154 155
52 115 127 166
4
2 62
3
91
49 75 54 33 79
47
2
70 71
76 70
1
2 8
1 0
0 -1
-1
N=
82
82
82
[Cl]
82
82
[SO4] [NO3]
82
82
[K] [Na]
82
[Mg] [Ca]
82
N=
[H]
84
84
[SO4] [NO3]
84
84
84
[K] [Na]
84
84
[Mg] [Ca]
[H] [NH4]
Déšť ze zemědělských oblastí 12
3,0 311
2,5
301 302
2,0
285 336 244 198 329 182 332 335 191
282 284 283 306 281 300 287 321
244 336 311 301 182
329 203 335 332 198 325
267 287 208 325 231 254 256 180 200 332 215
10
378
375
8
205 288
1,5
6
306 182 185
284 184 306 266
346 391 371
4
2
0,0
0
359 373
384 379 378 380
184 186 191 183 281 204 187 282 197 194 190 317
285 283 189 329
,5
384 346 381
390 346 344
380 346 379
351 379 378
360
388 379 380 389 365 349 390 347 356
-2
-,5 N=
84
[NH4]
Neznečištěný déšť
1,0
84
[Cl]
175
175
[Cl]
175
175
[SO4] [NO3]
175
175
[K] [Na]
175
175
[Mg] [Ca]
175
[H] [NH4]
N=
50
50
[Cl]
50
50
[SO4] [NO3]
50
50
[K] [Na]
50
50
[Mg] [Ca]
50
[H] [NH4]
26
Aplikace – analýza vzorků deště Metoda k-průměrů (SPSS) – 4 shluky Shluk (četnost) Složení
1 (53)
2 (33)
3 (106)
4 (199)
[Cl-]
0,69
2,76
1,81
0,36
[NO3-]
2,17
2,06
1,17
0,42
[SO42-]
2,04
2,10
1,16
0,45
[Na+]
0,79
2,23
1,78
0,43
[K+]
1,18
3,55
1,25
0,40
[Ca2+]
1,32
2,81
1,50
0,35
[Mg2+]
1,00
2,72
1,71
0,34
[NH4+]
2,24
2,76
1,17
0,29
[H+]
3,30
0,17
0,59
0,75
Průměrné hodnoty
27
Aplikace – analýza vzorků deště Metoda CLARA (S-PLUS) – 4 shluky Shluk (četnost) Složení
1 (86)
2 (189)
3 (55)
4 (61)
[Cl-]
1,83
0,31
2,42
0,68
[NO3-]
0,84
0,42
1,93
2,19
[SO42-]
0,98
0,45
1,92
1,9
[Na+]
1,85
0,39
2,07
0,74
[K+]
1,04
0,39
2,85
1,15
[Ca2+]
1,13
0,35
2,61
1,39
[Mg2+]
1,52
0,31
2,59
0,96
[NH4+]
0,92
0,26
2,29
2,23
[H+]
0,64
0,76
0,34
2,85
Průměrné hodnoty
28
Aplikace – charakteristika dat
Soubor Home sales (SPSS) Údaje o 2 440 nemovitostech Tři kvantitativní proměnné: odhadnutá cenu pozemku – nezařazeno odhadnuté zhodnocení majetku prodejní cena (závislost na ceně pozemku)
Kvalitativní proměnná – oblast nemovitosti (A-G) 29
Aplikace – analýza nemovitostí
30
Aplikace – analýza nemovitostí Dvoukroková shluková analýza – 3 shluky Cluster Distribution N Cluster
Total
1 2 3 Combined
967 620 853 2440 2440
% of Combined 39,6% 25,4% 35,0% 100,0%
% of Total 39,6% 25,4% 35,0% 100,0% 100,0%
31
Aplikace – analýza nemovitostí Dvoukroková shluková analýza – 3 shluky Centroids
Cluster
1 2 3 Combined
Appraised Value of Improvements Std. Mean Deviation 50901,61 17304,982 51307,10 28200,701 22227,85 10318,097 40980,58 23382,739
Sale Price Std. Mean Deviation 74567,07 27521,159 120858,2 65036,701 41410,98 18839,242 74738,54 49260,688
32
Aplikace – analýza nemovitostí Dvoukroková shluková analýza – 3 shluky
Dvourozměrná tabulka četností kategorií kvalitativní proměnné podle shluků: do prvního shluku patří všechny objekty z oblastí D a E, do druhého shluku objekty z oblastí A, B a C (a jeden objekt z oblasti F) a do třetího shluku objekty z oblastí F (kromě jednoho) a G. 33
Aplikace – analýza nemovitostí Auto-Clustering
Number of Clusters 1 2 3 4 5
Schwarz's Bayesian Criterion (BIC) 114169,813 110180,582 107880,244 106461,049 105345,775
BIC Change
Ratio of BIC Changesb
Ratio of Distance Measuresc
-3989,231 -2300,337 -1419,195 -1115,274
1,000 ,577 ,356 ,280
1,710 1,589 1,255 1,346
a
a. The changes are from the previous number of clusters in the table. b. The ratios of changes are with respect to the change at the two clusters. c. The ratios of distance measures are based on the current number of clusters against the previous number of clusters.
34
Aplikace – analýza nemovitostí Auto-Clustering
Number of Clusters 1 2 3 4 5
Akaike's Information Criterion (AIC) 110723,585 106767,607 104538,232 103055,744 101886,152
AIC Change
Ratio of AIC Changesb
Ratio of Distance Measuresc
-3955,978 -2229,375 -1482,489 -1169,592
1,000 ,564 ,375 ,296
1,771 1,500 1,265 1,410
a
a. The changes are from the previous number of clusters in the table. b. The ratios of changes are with respect to the change at the two clusters. c. The ratios of distance measures are based on the current number of clusters against the previous number of clusters.
35
Zdokonalení tradičních metod – metody založené na modelu
mrkd (multiple-resolution k-dimension) stromy jako implementace EM algoritmu, 1999, Moore, k je počet proměnných analyzovaného souboru
36
Speciální metody pro velké soubory – metody založené na hustotě
DBSCAN (Density Based Spatial Clustering of Application with Noise):
OPTICS (Ordering Points To Identify the Clustering Structure):
1996, Ester a kolektiv.
1999, Ankerst a kolektiv.
DENCLUE (DENsity-based CLUstEring):
1998, Hinneburg a Keim, shluky (atraktory hustoty) jsou definovány jako lokální maxima celkové funkce hustoty.
37
Speciální metody pro velké soubory – metody založené na mřížce
STING (STatistical INformation Grid): 1997, Wang a kolektiv, pro každou buňku uchovávány charakteristiky: počet objektů, průměr, směrodatná odchylka, minimální a maximální hodnota a typ statistického rozdělení (normální, rovnoměrné či žádné z uvedených).
38
Speciální metody pro velké soubory – metody založené na modelu
Particle filters (filtrovací metody): filtr je tvořen množinou částic a vah, komentář: 2002, Chopin, Fearnhead.
SOON (Self Organizing Oscillator Network): 2001, Frigui a Rhouma, vychází z algoritmu SOM (Self-Organizing Map).
39
Speciální metody pro velké soubory – smíšené metody
DBCLASD (Distribution-Based clustering algorithm for Clustering LArge Spatial Datasets): 1998, Xu a kolektiv, využity metody založené na všech třech principech, tj. na modelu, hustotě a mřížce, používá se chí-kvadrát test, shluky musí obsahovat minimálně 30 objektů.
40
Shlukování podprostorů
CLIQUE (CLustering In QUEst):
1998, Agrawal a kolektiv, přístupy založené na hustotě a na mřížce.
ENCLUS (ENntropy-based CLUStering): 1999, Cheng a kolektiv, rozdílné kritérium pro výběr podprostorů.
MAFIA (Merging of Adaptive Finite Intervals (And more than a CLIQUE)): 1999, Goil a kolektiv, 2001, Nagesh a kolektiv.
41
Shlukování podprostorů
OptiGrid: 1999 Hinneburg a Keim (autoři DENCLUE), odhady hustoty stejně jako v DENCLUE.
PROCLUS (PROjected CLUStering):
1999, Aggarwal a kolektiv.
ORCLUS (ORiented projected CLUSter generation):
2000, Aggarwal a Yu. 42
Využití principů shlukování pro velké soubory dat
Redukce počtu proměnných Identifikace odlehlých objektů Indexování objektů v datových souborech s vysokou dimenzí (hierarchické shlukování)
43
Literatura [1] Berkhin, P.: Survey of Clustering Data Mining Techniques. Accrue Software, Inc., San Jose. www.ee.ucr.edu/~barth/EE242/clustering_survey.pdf [2] Gordon, A.D.: Classification, 2nd Edition. Chapman & Hall/CRC, Boca Raton, 1999. [3] Han, J., Kamber, M.: Data Mining: Concepts and Techniques. Morgan Kaufman Publishers. San Francisco, 2001. [4] Hartigan, J.A.: Clustering Algorithms. John Wiley & Sons, New York, 1975 [5] Hinneburg, A., Keim, D.A.: Cluster Discovery Methods for Large Data Bases: From the Past to the Future. Halle, 1999. http://www.ece.northwestern.edu/~harsha/Clustering/keimslides.html [6] Jain, A.K., Murty, M.N., Flynn, P.J.: Data Clustering: A Review. IEEE Computer Society Press, 1996. 44
Literatura [7] Kusiak, A.: Cluster Analysis. Part I. University of Iowa, Iowa City. http://www.icaen.uiowa.edu/~comp/Public/Clustering1.pdf [8] Kusiak, A.: Cluster Analysis in Data Mining. Part II. University of Iowa, Iowa City. http://www.icaen.uiowa.edu/~comp/Public/Clustering2.pdf [9] Mercer, D.P.: Clustering Large Datasets. Linacre College, 2003. http://www.stats.ox.ac.uk/~mercer/documents/Transfer.pdf [10] Ozeki, T., Koide K., Kimoto, T.: Evaluation of Sources of Acidity in Rainwater Using a Constrained Oblique Rotational Factor Analysis. Environ. Sci. Technol. 29 (1995), 1638-1645. [11] Řezanková, H.: Klasifikace pomocí shlukové analýzy. In: Kupka, K. (ed.). Analýza dat 2003/II. TriloByte Statistical Software, Pardubice, 2004, 119–135. [12] Wang, W.: Clustering. University of North Carolina, Chapel Hill, 2004. http://www.cs.unc.edu/Courses/comp290-90f03/GNET214/clustering2.pdf 45
