Википедија

K-means++

U analizi podataka, k-means++[1][2] predstavlja algoritam koji vrši odabir početnih vrednosti (ili "semena") za k-means clustering algoritam. David Arthur i Sergei Vassilvitskii su ga predstavili 2007. godine, kao približni algoritam za NP-težak k-means problem - način na koji se izbegava loše grupisanje kod standardnih k-means algoritama. U samostalnom radu, 2006.[3] Rafail Ostrovsky, Yuval Rabani, Leonard Schulman iChaitanya Swamy, su predstavili tri metoda značenja, od kojih je prvom sličan ovaj algoritam. (Distribucija prvog značenja je drugačija.)

Razvoj уреди

K-means problem jeste pronaći centar grupisanja koji smanjuje odstupanje unutar klase, tj. zbir kvadrata rastojanja od svake tačke grupisanog podatka do njegovog centra grupisanja (njemu najbližem centru). Iako je pronalaženje tačnog rešenja za k-means problem za proizvoljani ulaz NP-težak[4], standardni pristup pronalaženja približnog rešenja (često nazvan Lojdov algoritam ili k-means algoritam) je u širokoj upotrebi i često brzo nađe razumljiva rešenja.

Međutim, k-means algoritam ima najmanje dva glavna teorijska nedostatka:

  • Prvo, pokazano se da je najgori slučaj rada algoritma super-polinomijalno vreme u početnom stanju.[5]
  • Drugo, pronađena tačnost može biti proizvoljno loša u odnosu na objektivne funkcije u poređenju sa optimalnim grupisanjem.

K-means++ algoritam prevazili drugu prepreku tako što određuje proceduru za inicijalizaciju centra grupisanja pre nego što nastavi sa standardnim k-means optimizovanim interacijama.

Sa k-means++ inicijalizacijom, algoritam garantuje da će pronaći rešenje koje je složenosti O(log k) i koje je konkurentno optimalnom k-means rešenju.

Primer lošeg slučaja уреди

Da bi ilustrovali potencijal k-means algoritma za proizvoljno slabo izvršavanje u odnosu na objektivne funkcije minimizovanja, zbira kvadrata rastojanja klastera (grupa) ukazuje na centroid dodeljenih klastera. Primer su 4 tačke iz R2 koje formiraju osno poravnat pravougaonik čija je širina veća od visine.

Ako je k = 2 i dva početna centra klastera leže na središtima gornje i donje stranice pravougaonika formirane od četiri tačke podataka,k-means kovergira odmah, bez pomeranja ovih cenatara klastera. Shodno tome, dve donje tačke podataka su grupisane zajedno i dve tačke podataka koje čine vrh pravougaonika su grupisane – što je manje od optimalnog grupisanja, jer je širina pravougaonika veća od njegove visine.

Zatim, uzmimo horizontalno istezanje pravougaonika na proizvoljnu širinu. Standardni k-means će nastaviti da grupiše tačke suboptimalno i povećanjem horizontalnog rastojanja između dve tačke podataka u svakom klasteru se može napraviti da se algoritam izvršava proizvoljno slabo u odnosu na objektivne funkcije k-means algoritma.

Algoritam inicijalizacije уреди

Intuicija da je širenje k polaznog skupa centara dobra stvar je iza ovog pristupa: prvi centar grupe se bira ravnomerno i nasumice iz tačaka podataka koje su grupisane, nakon čega je svaki sledeći klaster centar izabran od preostalih tačaka podataka sa verovatnoćom proporcionalnom sa svojom kvadratom udaljenosti od najbliže tačke za postojeće centre klastera.

Precizno, algoritam ide ovako:

  1. Ravnomerno i nasumično se bira jedan centar među tačakama podataka.
  2. Za svaku tačku podataka x, izračunava se D(x), rastojanje između x i najbližeg centra koji je prethodno izabran.
  3. Bira se nasumično jedna nova tačka koja ukazuju na novi centar, pomoću distribucije težinske verovatnoće, gde je tačka x izabrana sa verovatnoćom porporcionalnom sa D(x)2.
  4. Koraci 2 i 3 se ponavljaju dok se ne izabere k centara.
  5. Sada, kada su početni centri izabrani, u nastakvu se koristi k-means clustering algoritam.

Ovaj metod donosi značajno poboljšanje kod konačne greške k-means-a. Iako početna selekcija u algoritmu zahteva dodatno vreme, deo k-means-a konvergira vrlo brzo, s toga, algoritam zaista smanjuje vreme izračunavanja. . Autori su testirali svoj metod sa realnim i sintetičkim skupovima podataka i dobili 2 puta poboljšanje u brzini, a za određene skupove podataka, blizu 1000 puta poboljšanje kod grešaka. U ovim simulacijama nova metoda se gotovo uvek izvršavala dobro barem kao vanilla k-means i u brzini i što se tiče grešaka.

Pored toga, autori su izračunali približnu složenost za svoj algoritam. K-means++ algoritam garantuje složenost O(log k) gde je   broj klastera koji se koriste. To je u suprotnosti sa vanilla k-means, koji može da generiše klastere proizvoljno lošije od optimuma.[6]

Primena уреди

K-means++ + pristup se koristi od kad je prvi put predstavljen. U pregledu,[7] koji uključuje mnoge vrste algoritama grupisanja, ovaj metod je uspešno prevazišao neke od problema u vezi sa drugim načinima definisanja početnih centara klastera za k-means clustering. Mnogi drugi koriste mogućnost k-means++ da stvori geografski klaster fotografija na osnovu informacije o geografskoj širini i dužini priključene fotografiji. Finansijsku diversifikacije su zahtevali Howard and Johansen.[8] Druga podrška za metod i tekuće diskusije su takođe dostupni online.[9] Pošto k-means++ inicijalizaciji treba k prelaza podacima, nije dobra razmera nad velikim skupovima podataka. Bahman Bahmani i dr. su predložili prilagodljivu varijantu k-means++ nazvanu k-means|| koja obezbeđuje iste teorijske garancije, a takođe je veoma skalabilna.[10]

Softver уреди

 
Викикњиге имају више информација о K-means++

Reference уреди

  1. ^ Arthur, D. & Vassilvitskii, S. (2007). „k-means++: the advantages of careful seeding”. Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics Philadelphia, PA, USA. стр. 1027—1035. 
  2. ^ Arthur, D.; Vassilvitskii, S. „Slides for presentation of method” (PDF). 
  3. ^ Ostrovsky, R.; et al. (2006). „The Effectiveness of Lloyd-Type Methods for the k-Means Problem”. Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06). IEEE. стр. 165—174. 
  4. ^ Drineas, P.; et al. (2004). „Clustering Large Graphs via the Singular Value Decomposition”. Machine Learning. Kluwer Academic Publishers Hingham, MA, USA. 56 (1–3): 9—33. doi:10.1023/B:MACH.0000033113.59016.96. 
  5. ^ Arthur, D. & Vassilvitskii, S. (2006), How slow is the k-means method?, ACM New York, NY, USA, стр. 144—153 
  6. ^ T. Kanungo, D. Mount, N. Netanyahux, C. Piatko, R. Silverman, A. Wu "A Local Search Approximation Algorithm for k-Means Clustering" Архивирано на сајту Wayback Machine (9. фебруар 2006) 2004 Computational Geometry: Theory and Applications.
  7. ^ „Approximation Algorithms for the Metric k-Median Problem” (PDF). Архивирано из оригинала 05. 06. 2011. г. Приступљено 31. 05. 2013. 
  8. ^ http://www.cse.ohio-state.edu/~johansek/clustering.pdf[мртва веза] Clustering Techniques for Financial Diversification, March 2009
  9. ^ http://lingpipe-blog.com/2009/03/23/arthur-vassilvitskii-2007-kmeans-the-advantages-of-careful-seeding/ Архивирано на сајту Wayback Machine (15. јун 2013) Lingpipe Blog
  10. ^ B. Bahmani, B. Moseley, A. Vattani, R. Kumar, S. Vassilvitskii "Scalable K-means++" 2012 Proceedings of the VLDB Endowment.
Преузето из „https://sr.wikipedia.org/w/index.php?title=K-means%2B%2B&oldid=27055570”