Természet | Adat particionáló algoritmus ( d ) |
---|
A k -means (vagy angolul k -means ) particionálás az adatok particionálásának módszere és kombinatorikus optimalizálási probléma . Adott pontok és egy k egész szám , a probléma az, hogy a pontokat k csoportokra osztjuk , amelyeket gyakran klasztereknek nevezünk , egy bizonyos függvény minimalizálása érdekében. Figyelembe vesszük egy pont távolságát a klaszterének pontjainak átlagától; a minimalizálandó függvény e távolságok négyzetének összege.
Van egy klasszikus heurisztikus ezt a problémát, gyakran nevezik k- átlagok módszereket használt a legtöbb esetben. A problémát klasszikus optimalizálási problémaként is tanulmányozzák, például közelítő algoritmusokkal .
A k- átlagokat különösen a felügyelet nélküli tanulásban használják, ahol a megfigyelések k partíciókra vannak felosztva . A dinamikus klaszterek általánosítják azt az elvet, amelynél az egyes partíciókat egy gyűrű képviseli, az átlagosnál összetettebbek lehetnek. A klasszikus k- jelentése algoritmus megegyezik a Lloyd-Max kvantálási algoritmussal .
Adva egy sor halmazt ( x 1 , x 2 ,…, x n ), megpróbáljuk felosztani az n pontot k S S = { S 1 , S 2 ,…, S k } ( k ≤ n ) halmazokba a az egyes partíciókon belüli pontok közötti távolság:
ahol μ i az S i pontjainak baricentruma .
A " k -means" kifejezést először James MacQueen használta 1967-ben, bár az eredeti ötletet Hugo Steinhaus javasolta 1957-ben. A klasszikus algoritmust Stuart Lloyd javasolta 1957-ben pulzus kód moduláció céljából , de nem adták ki a Bell Labs-on kívül, 1982 előtt. 1965-ben az EW Forgy lényegében hasonló módszert tett közzé, ezért néha "Lloyd Forgy módszerének" is nevezik. Hatékonyabb, Fortran kódolású verziót Hartigan és Wong tettek közzé 1975/1979-ben.
Van egy klasszikus algoritmus a problémára, amelyet néha k-mean módszernek is neveznek , amelyet a gyakorlatban széles körben használnak és hatékonynak tartanak, bár nem garantálja sem az optimalitást, sem a polinom számítási időt .
Az inicializálás meghatározó tényező az eredmények minőségében (helyi minimum). Sok mű foglalkozik ezzel a ponttal. Két szokásos inicializálási módszer létezik: egyrészt Forgy módszere, másrészt véletlenszerű particionálás. Forgy módszere a kezdeti középérték k pontját hozzárendeli k véletlenszerűen kiválasztott bemeneti adatokhoz. A véletlenszerű particionálás véletlenszerűen hozzárendel egy fürtöt minden egyes adatelemhez, majd folytatja a kezdeti átlagos pontok (első előtti) kiszámítását.
A K-mean ++ egy k pont inicializáló algoritmus, amely javasolja az inicializálást, amely javítja az optimális megoldás (globális minimum) elérésének valószínűségét. Ennek a megközelítésnek az az intuíciója, hogy elosztja a kezdeti középérték k pontját. Az első klaszter kezdeti átlagos pontját véletlenszerűen választják ki az adatokból. Ezután minden kezdeti átlagos pontot megválasztunk a megmaradt pontok közül, a valószínűség arányos a pont és a legközelebbi klaszter közötti távolság négyzetével.
Véges számú lehetséges partíció található k osztállyal. Ezenkívül az algoritmus minden egyes lépése szigorúan csökkenti a költségfüggvényt, pozitív és jobb partíciót mutat. Ez lehetővé teszi annak megerősítését, hogy az algoritmus mindig véges idő alatt konvergál, vagyis véget ér.
A végső particionálás nem mindig optimális. Ezenkívül a számítási idő exponenciális lehet a pontok számában, még a síkban is. A gyakorlatban lehetőség van az iterációk számának korlátozására vagy az iterációk közötti javulás kritériumának meghatározására.
Abban fix k , a sima bonyolultsága polinomiális egyes konfigurációk, beleértve pontok euklideszi térben , és az ügy a Kullback-Leibler divergencia . Ha k a bemenet része, akkor a sima komplexitás továbbra is polinom az euklideszi esetnél. Ezek az eredmények részben magyarázzák az algoritmus gyakorlati hatékonyságát.
A k- átlagok problémája általában NP-nehéz . Euklideszi esetben létezik egy polinomiális közelítés algoritmus, amelynek aránya 9, helyi kereséssel .
A particionálás k-eszközeinek egyik lehetséges hátránya, hogy a klaszterek az inicializálástól és a választott távolságtól függenek .
A k a priori paraméter kiválasztásának tényét hátrányként vagy előnyként lehet felfogni. Például számoló zsák kiszámítása esetén ez lehetővé teszi a kívánt szótár méretének pontos rögzítését. Éppen ellenkezőleg, az adatok bizonyos felosztásakor előnyösebb lesz eltekinteni egy ilyen korlátozástól.