Hierarchikus klaszterező algoritmusok tesztelése
Készítették: Förhécz András & Pilászy István
A Ward algoritmus tesztelését végezték: Németh Bottyán & Takács Gábor
paraméterek mintázat*
klaszterek
száma
2 2 2 5 6 9 2
minta-
pontok
száma
40 1000 1000 1500 2000 2000 2000
zaj** - 10% 10% 5% 5% 5% 5%
minta
zaj
nélkül
zajos
minta
 
algoritmus zaj teszt #1 teszt #2 teszt #3 teszt #4 teszt #5 teszt #6 teszt #7
single-link nincs
van  
average-link nincs
van  
complete-link nincs
van  
CURE
c=5;15***
alpha=0.7
nincs
van  
CURE
c=5;15***
alpha=0.95
nincs
van  
CURE
c=10;30***
alpha=0.7
nincs
van  
CURE
c=10;30***
alpha=0.95
nincs
van  
Ward nincs
van  
futási idő**** ~0mp ~10 - 13mp ~10 - 13mp ~30 - 35mp ~55mp - 1p 12mp ~55mp - 1p 12mp ~50mp - 1p
memória igény***** ~10Mb 40..60Mb 40..60Mb 85..130Mb 140..213Mb 140..213Mb 140..213Mb
* a piros terület kétszeres sűrűséget jelöl
** a mintapontok ezen része nem a megadott mintázat szerint készült, hanem véletlen egyenletes eloszlású
*** az első érték a #1, a második a #2-#6 tesztekre vonatkozik
**** a tesztelést AMD Athlon XP 1600+ (1,4Ghz) processzorral végeztük; a nagyobb értékek a CURE algoritmushoz tartoznak.
***** az alsó érték garbage collection folyamatos használatával, a felső bőséges szabad memóriával értendő
(a tesztekre kattintva azok megjelennek eredeti méretben)
Az itt látható teszteket
George Karypis, Eui-Hong (Sam) Han, Vipin Kumar — CHAMELEON: A Hierarchical Clustering Algorithm Using Dynamic Modeling
című 1999-es cikke alapján készítettük el. A cikk teszteket tartalmazó oldala itt található.
Eredmények:

  • a single-link eljárás nagyon pontos, ha a klaszterek jól elkülönülnek, de nem tud mit kezdeni a zajjal.
  • az average-link már jobban teljesít zajos esetekben, de a bonyolult formákkal nem tud mit kezdeni.
  • a complete-link hajlamos a nagy klasztereket szétszabdalni, és a zajtűrő képessége sem túl jó.
  • a CURE algoritmus jól kezeli a zajos eseteket, de nem tudja jól reprezentálni a bonyolult formákat.

A különböző méretű klaszterekkel (teszt #2) egyik eljárásnak sem volt problémája, viszont a befoglaló klasztert (teszt #6) csak a single-link eljárás képes helyesen elkülöníteni. A Gauss eloszlású, egymásba lógó mintahalmazok klaszterezése kemény dió volt mindegyik algoritmusnak (teszt #7), csak a feladathoz pont jó számú reprezentáns pontot használó CURE algoritmus oldotta meg kellő pontossággal a zajmentes esetben.