K-means++
U analizi podataka, k-means++ 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. 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, 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.
 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:
 Ravnomerno i nasumično se bira jedan centar među tačakama podataka.
 Za svaku tačku podataka , izračunava se D(), rastojanje između  i najbližeg centra koji je prethodno izabran.
 Bira se nasumično jedna nova tačka koja ukazuju na novi centar, pomoću distribucije težinske verovatnoće, gde je tačka  izabrana sa verovatnoćom porporcionalnom sa D()2.
 Koraci 2 i 3 se ponavljaju dok se ne izabere  centara.
 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 -means-a. Iako početna selekcija u algoritmu zahteva dodatno vreme, deo -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 -means i u brzini i što se tiče grešaka.

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

Primena 
K-means++ + pristup se koristi od kad je prvi put predstavljen. U pregledu, 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. Druga podrška za metod i tekuće diskusije su takođe dostupni online. 
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.

Softver 

 ELKI data-mining okvir koji sadrži više k-means varijanti, uključujući k-means++ za brzinu
 GNU R uključuje k-means, a "flexclust" paketi mogu da urade k-means++
 OpenCV implementation
 Weka sadrži k-means (sa opcionim k-means++) i x-means clustering.
 Apache Commons Math Java implementation

Reference 

Алгоритми кластеризације података
Статистички алгоритми
U analizi podataka , k-means++ predstavlja algoritam koji vrši odabir početnih vrednosti ( ili " semena " ) za k-means clustering algoritam . David Arthur i Sergei Vassilvitskii su ga predstavili 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 , 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 , 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 . 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 sutač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 : Ravnomerno i nasumično se bira jedan centar među tačakama podataka . Za svaku tačku podataka , izračunava se D ( ) , rastojanje između i najbližeg centra koji je prethodno izabran . Bira se nasumično jedna nova tačka koja ukazuju na novi centar , pomoću distribucije težinske verovatnoće , gde je tačka izabrana sa verovatnoćom porporcionalnom sa D( ) 2. Koraciise ponavljaju dok se ne izabere centara . 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 -means-a . Iako početna selekcija u algoritmu zahteva dodatno vreme , deo -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 dobiliputa poboljšanje u brzini , a za određene skupove podataka , blizuputa poboljšanje kod grešaka . U ovim simulacijama nova metoda se gotovo uvek izvršavala dobro barem kao vanilla -means i u brzini i što se tiče grešaka . Pored toga , autori su izračunali približnu složenost za svoj algoritam . -means++ algoritam garantuje složenost O( log k ) gde je broj klastera koji se koriste . To je u suprotnosti sa vanilla -means , koji može da generiše klastere proizvoljno lošije od optimuma . Primena K-means++ + pristup se koristi od kad je prvi put predstavljen . U pregledu , 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 . Druga podrška za metod i tekuće diskusije su takođe dostupni online . 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 . Softver ELKI data-mining okvir koji sadrži više k-means varijanti , uključujući k-means++ za brzinu GNU R uključuje k-means , a " flexclust " paketi mogu da urade k-means++ OpenCV implementation Weka sadrži k-means ( sa opcionim k-means++ ) i x-means clustering . Apache Commons Math Java implementation Reference Алгоритми кластеризације података Статистички алгоритми