En mineria de dades, k-means++ és un algorisme per triar els valors/centroides inicials (o "llavors") per a l'algorisme de clústering de k-means. Va ser proposat el 2007 per David Arthur i Sergei Vassilvitskii, com un algorisme d'aproximació per al problema de k-means NP-hard — una manera d'evitar els clústers de vegades deficients que troba l'algorisme estàndard de k-means. És similar al primer dels tres mètodes de sembra proposats, en un treball independent, el 2006 per Rafail Ostrovsky, Yuval Rabani, Leonard Schulman i Chaitanya Swamy. (La distribució de la primera llavor és diferent).
Rerefons El problema de les k-means consisteix a trobar centres de clúster que minimitzin la variància intraclasse, és a dir, la suma de les distàncies al quadrat des de cada punt de dades que s'agrupa fins al seu centre de clúster (el centre que hi és més proper). Tot i que trobar una solució exacta al problema de les k-means per a una entrada arbitrària és NP-hard, l'enfocament estàndard per trobar una solució aproximada (sovint anomenat algorisme de Lloyd o algorisme de les k-means) s'utilitza àmpliament i sovint troba solucions raonables ràpidament.
Tanmateix, l'algoritme de k-means té almenys dues deficiències teòriques importants:
Primer, s'ha demostrat que el pitjor temps d'execució de l'algoritme és superpolinòmic en la mida d'entrada. En segon lloc, l'aproximació trobada pot ser arbitràriament dolenta respecte a la funció objectiu en comparació amb l'agrupació òptima.
L'algoritme k-means++ aborda el segon d'aquests obstacles especificant un procediment per inicialitzar els centres del clúster abans de continuar amb les iteracions estàndard d'optimització k-means. Amb la inicialització k-means++, es garanteix que l'algoritme trobi una solució que sigui O(log k) competitiu amb la solució òptima de k-mitjanes.
Exemple d'un agrupament subòptim alt=Bad clustering of a rectangle|miniatura|Aquesta és una mala agrupació on els punts A i D es troben al clúster vermell del centroide E i els punts B i C es troben al clúster blau del centroide F, ja que la distància intraclúster no és mínima. Per il·lustrar el potencial de l'algoritme k-means per tenir un rendiment arbitràriament deficient respecte a la funció objectiu de minimitzar la suma de les distàncies al quadrat dels punts del clúster al centroide dels seus clústers assignats, considerem l'exemple de quatre punts a que formen un rectangle alineat amb l'eix l'amplada del qual és més gran que l'alçada. miniatura|Agrupació òptima per al problema. Si i els dos centres de clúster inicials es troben als punts mitjans dels segments de línia superior i inferior del rectangle format pels quatre punts de dades, l'algoritme de k-means convergeix immediatament, sense moure aquests centres de clúster. En conseqüència, els dos punts de dades inferiors s'agrupen junts i els dos punts de dades que formen la part superior del rectangle s'agrupen junts — una agrupació subòptima perquè l'amplada del rectangle és més gran que la seva alçada.
Considerem ara estendre el rectangle en direcció horitzontal a qualsevol amplada desitjada. L'algoritme estàndard de k-means continuarà agrupant els punts de manera subòptima i, augmentant la distància horitzontal entre els dos punts de dades de cada clúster, podem fer que l'algoritme tingui un rendiment arbitràriament deficient respecte a la funció objectiu de k-means.
Algoritme d'inicialització millorat La intuïció darrere d'aquest plantejament és que distribuir els k centres de clúster inicials és una bona cosa: el primer centre de clúster es tria uniformement a l'atzar entre els punts de dades que s'estan agrupant, després dels quals cada centre de clúster posterior es tria entre els punts de dades restants amb una probabilitat proporcional a la seva distància al quadrat des del centre de clúster existent més proper del punt.
L'algoritme exacte és el següent:
Trieu un centre uniformement a l'atzar entre els punts de dades. Per a cada punt de dades encara no s'ha triat, calcula D(), la distància entre i el centre més proper que ja s'ha triat. Trieu un nou punt de dades a l'atzar com a nou centre, utilitzant una distribució de probabilitat ponderada on es tria un punt amb una probabilitat proporcional a D( ) ². Això garanteix que es seleccioni un punt molt diferent del centroide seleccionat anteriorment com a següent centroide. Repetiu els passos 2 i 3 fins que s'hagin triat centres. Ara que s'han escollit els centres inicials, procediu utilitzant l'agrupació estàndard de k-means
Pseudocodi
El pseudocodi següent descriu una implementació de k-means++. La funció kmeans() realitza el procediment estàndard d'agrupació en clústers de k-means.
function kmeans++ (k, points) is
// Initialize list of centroids with one randomly
selected point
centroids ← empty list
firstIndex ← random integer from 0 to length(points) - 1
centroids.append(points[firstIndex])
Aquest mètode de sembra produeix una millora considerable en l'error final de -mitjanes. Tot i que la selecció inicial de l'algoritme requereix temps addicional, la part de -mitjanes convergeix molt ràpidament després d'aquesta sembra i, per tant, l'algoritme redueix el temps de càlcul. Els autors van provar el seu mètode amb conjunts de dades reals i sintètics i van obtenir millores de velocitat típicament del doble, i per a certs conjunts de dades, millores d'error de prop de 1000 vegades. En aquestes simulacions, el nou mètode gairebé sempre va tenir un rendiment almenys tan bo com -mitjanes estàndard tant en velocitat com en error.
A més, els autors calculen una relació d'aproximació per al seu algorisme. L'algorisme -means++ garanteix una relació d'aproximació O(log k) en expectativa (sobre l'aleatorietat de l'algoritme), on és el nombre de clústers utilitzats. Això contrasta amb -mitges estàndard, que poden generar agrupacions arbitràriament pitjors que l'òptim. Una generalització del rendiment de les k-mitges++ respecte a qualsevol distància arbitrària es proporciona a.
Aplicacions L'enfocament k-means++ s'ha aplicat des de la seva proposta inicial. En una revisió de Shindler, que inclou molts tipus d'algoritmes de clústering, es diu que el mètode supera amb èxit alguns dels problemes associats amb altres maneres de definir centres de clúster inicials per a la clústering de k-means. Lee et al. informen d'una aplicació de k-means++ per crear un clúster geogràfic de fotografies basat en la informació de latitud i longitud adjunta a les fotos. Howard i Johansen informen d'una aplicació a la diversificació financera. També hi ha disponibles en línia altres suports per al mètode i una discussió en curs. Com que la inicialització de k-means++ necessita que k passi les dades, no s'escala gaire bé a grans conjunts de dades. Bahmani et al. han proposat una variant escalable de k-means++ anomenada k-means|| (que s'ha de llegir com a "k-means paral·lel") que proporciona les mateixes garanties teòriques i, tanmateix, és altament escalable.
Programari Accord.NET conté implementacions de C# per a k-means, k-means++ i k -modes. ALGLIB conté implementacions paral·lelitzades de C++ i C# per a k-means i k-means++. Apache Commons Math conté k-means++ El marc de treball de mineria de dades ELKI conté múltiples variacions de k-means, incloent-hi k-means++ per a la sembra. MATLAB té una implementació de K-Means que utilitza k-means++ per defecte per a la sembra. OpenCV conté la implementació de K-means en C++ i Python (amb inicialització opcional de la llavor de k-means). Orange inclou el widget d'IU de k-means++ i la compatibilitat amb l'API R inclou k-means, i el paquet "flexclust" pot fer k-means++ scikit-learn té una implementació de K-Means que utilitza k-means++ per defecte. Weka conté clústers de k-means (amb k-means++ opcional) i x-means.
Referències
Categoria:Algorismes