Szigetek
A feladat alapötletét Oláh Gábortól kaptam, aki beszédfelismerés kapcsán találkozott a probléma egy magasabb dimenziós változatával.
Az egyszerűsített változat:
Adott véges sok pont a síkon, egész koordinátákkal. Csoportosítsuk a pontokat "szigetekre".
Példa
Az alábbi első ábrán látható ponthalmazt a legtöbb ember a második ábrán látható módon csoportosítaná.
A kérdés pontosítása
Nem definiáltuk, mit jelent a "sziget", és rövid gondolkozás után látható, hogy a definíció egyáltalán nem nyilvánvaló.
Küszöbszámokkal
Távolságarányokkal
Alkalmazások
Web-keresők találatainak csoportosítása
Az egyik érdekes alkalmazás a következő: a web-keresések rengeteg találatot ("pontot") adnak, jó lenne ezeket a találatokat csoportosítani, és a csoportokat megjeleníteni.
Ha definiálni tudunk a talált weblapok ("pontok") absztrakt terében egy jó távolság mértéket, akkor egy "sziget-kereső" (clustering) algoritmus segítségével csoportosíthatjuk a találatokat.
Beszédfelismerés
Szakirodalom
Tesztadat
91 36
43 92
401 136
182 72
361 241
420 238
120 293
57 337
110 349
185 358
