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