Hierarchikus klaszterező algoritmusok tesztelése
paraméterek |
mintázat* |
 |
 |
 |
 |
 |
 |
 |
klaszterekszáma |
2 |
2 |
2 |
5 |
6 |
9 |
2 |
minta-pontokszáma |
40 |
1000 |
1000 |
1500 |
2000 |
2000 |
2000 |
zaj** |
- |
10% |
10% |
5% |
5% |
5% |
5% |
mintazaj 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 |
|
 |
 |
 |
 |
 |
 |
CUREc=5;15***alpha=0.7 |
nincs |
 |
 |
 |
 |
 |
 |
 |
van |
|
 |
 |
 |
 |
 |
 |
CUREc=5;15***alpha=0.95 |
nincs |
 |
 |
 |
 |
 |
 |
 |
van |
|
 |
 |
 |
 |
 |
 |
CUREc=10;30***alpha=0.7 |
nincs |
 |
 |
 |
 |
 |
 |
 |
van |
|
 |
 |
 |
 |
 |
 |
CUREc=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
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.
|