k- înseamnă grupare - k-means clustering

k- înseamnă clustering este o metodă de cuantificare vectorială , inițial din procesarea semnalului , care are ca scop împărțirea n observații în k clustere în care fiecare observație aparține clusterului cu cea mai apropiată medie (centre de cluster sau centroid de cluster), servind ca prototip de grupul. Acest lucru are ca rezultat o partiționare a spațiului de date în celule Voronoi . k- înseamnă grupare minimizează variațiile din interiorul clusterului ( distanțe euclidiene pătrate ), dar nu distanțe euclidiene regulate, ceea ce ar fi problema Weber mai dificilă: media optimizează erorile pătrate, în timp ce doar mediana geometrică minimizează distanțele euclidiene. De exemplu, soluții euclidiene mai bune pot fi găsite folosind k-mediane și k-medoide .

Problema este dificilă din punct de vedere al calculului ( NP-hard ); totuși, algoritmii euristici eficienți converg rapid către un optim local . Acestea sunt de obicei similare algoritmului de maximizare așteptărilor pentru amestecuri de distribuții gaussiene printr-o abordare iterativă de rafinament folosită atât de mijloacele k, cât și de modelarea amestecului gaussian . Ambii folosesc centre de cluster pentru modelarea datelor; cu toate acestea, gruparea k- înseamnă tinde să găsească clustere cu o extensie spațială comparabilă, în timp ce modelul de amestec gaussian permite clustere să aibă forme diferite.

Algoritmul k-înseamnă nesupravegheat are o relație slabă cu clasificatorul de vecini k- cel mai apropiat , o tehnică populară de învățare automată supravegheată pentru clasificare, care este adesea confundată cu k- mijloace datorită numelui. Aplicarea celui mai apropiat clasificator de vecin la centrele de cluster obținute prin k- mijloace clasifică datele noi în clusterele existente. Acest lucru este cunoscut ca cel mai apropiat clasificator de centroid sau algoritm Rocchio .

Descriere

Având în vedere un set de observații ( x ₁ , x ₂ , ..., x _n ), unde fiecare observație este un vector real d- dimensional, k- înseamnă grupare are ca scop împărțirea observațiilor n în k (≤ n ) seturi S = { S ₁ , S ₂ , ..., S _k } astfel încât să se minimizeze suma de pătrate din interiorul clusterului (WCSS) (adică varianța ). În mod formal, obiectivul este de a găsi:

{\ displaystyle {\ underset {\ mathbf {S}} {\ operatorname {arg \, min}}} \ sum _ {i = 1} ^ {k} \ sum _ {\ mathbf {x} \ in S_ {i }} \ left \ | \ mathbf {x} - {\ boldsymbol {\ mu}} _ {i} \ right \ | ^ {2} = {\ underset {\ mathbf {S}} {\ operatorname {arg \, min}}} \ sum _ {i = 1} ^ {k} | S_ {i} | \ operatorname {Var} S_ {i}}

unde μ _i este media punctelor din S _i . Acest lucru este echivalent cu minimizarea abaterilor pătrate în perechi ale punctelor din același cluster:

{\ displaystyle {\ underset {\ mathbf {S}} {\ operatorname {arg \, min}}} \ sum _ {i = 1} ^ {k} \, {\ frac {1} {2 | S_ {i } |}} \, \ sum _ {\ mathbf {x}, \ mathbf {y} \ în S_ {i}} \ left \ | \ mathbf {x} - \ mathbf {y} \ right \ | ^ {2 }}

Echivalența poate fi dedusă din identitate . Deoarece varianța totală este constantă, aceasta este echivalentă cu maximizarea sumei deviațiilor pătrate între puncte din diferite clustere (suma între pătrate a pătratelor, BCSS), care rezultă din legea varianței totale . ${\ displaystyle \ sum _ {\ mathbf {x} \ în S_ {i}} \ left \ | \ mathbf {x} - {\ boldsymbol {\ mu}} _ {i} \ right \ | ^ {2} = \ sum _ {\ mathbf {x} \ neq \ mathbf {y} \ în S_ {i}} (\ mathbf {x} - {\ boldsymbol {\ mu}} _ {i}) ^ {T} ({\ boldsymbol {\ mu}} _ {i} - \ mathbf {y})}$

Istorie

Termenul " k- mijloace" a fost folosit pentru prima dată de James MacQueen în 1967, deși ideea se întoarce la Hugo Steinhaus în 1956. Algoritmul standard a fost propus pentru prima dată de Stuart Lloyd de la Bell Labs în 1957 ca tehnică pentru modularea codului pulsului , deși nu a fost publicat ca articol de revistă până în 1982. În 1965, Edward W. Forgy a publicat în esență aceeași metodă, motiv pentru care este uneori denumit algoritm Lloyd – Forgy.

Algoritmi

Algoritm standard (k-mijloace naive)

Convergența k- înseamnă

Cel mai comun algoritm folosește o tehnică de rafinare iterativă. Datorită omniprezenței sale, este adesea numit „ algoritmul k- înseamnă”; este denumit și algoritmul lui Lloyd , în special în comunitatea informatică. Uneori este denumit și „mijloace k naive”, deoarece există alternative mult mai rapide.

Având în vedere un set inițial de k înseamnă m ₁⁽¹⁾ , ..., m _k⁽¹⁾ (vezi mai jos), algoritmul continuă alternând între doi pași:

Etapa de atribuire : Atribuiți fiecare observație grupului cu cea mai apropiată medie: cea cu distanța euclidiană cel mai puțin pătrată . (Matematic, aceasta înseamnă partiționarea observațiilor în conformitate cu diagrama Voronoi generată de mijloace.)

{\ displaystyle S_ {i} ^ {(t)} = \ left \ {x_ {p}: \ left \ | x_ {p} -m_ {i} ^ {(t)} \ right \ | ^ {2} \ leq \ left \ | x_ {p} -m_ {j} ^ {(t)} \ right \ | ^ {2} \ \ forall j, 1 \ leq j \ leq k \ right \},}

unde fiecare este atribuit exact unuia , chiar dacă ar putea fi atribuit a două sau mai multe dintre ele.

{\ displaystyle x_ {p}}

{\ displaystyle S ^ {(t)}}

Pas de actualizare : Recalculați mijloacele ( centroide ) pentru observațiile atribuite fiecărui cluster.

{\ displaystyle m_ {i} ^ {(t + 1)} = {\ frac {1} {\ left | S_ {i} ^ {(t)} \ right |}} \ sum _ {x_ {j} \ în S_ {i} ^ {(t)}} x_ {j}}

Algoritmul a convergut atunci când atribuțiile nu se mai schimbă. Algoritmul nu este garantat pentru a găsi optimul.

Algoritmul este adesea prezentat ca atribuirea obiectelor celui mai apropiat cluster după distanță. Utilizarea unei funcții de distanță diferită de distanța euclidiană (pătrată) poate împiedica convergerea algoritmului. S- au propus diferite modificări ale k- mijloacelor, cum ar fi k- mijloace sferice și k- medoizi, pentru a permite utilizarea altor măsuri de distanță.

Metode de inițializare

Metodele de inițializare utilizate în mod obișnuit sunt Forgy și Random Partition. Metoda Forgy alege în mod aleatoriu k observații din setul de date și le folosește ca mijloace inițiale. Metoda partiției aleatorii atribuie mai întâi aleatoriu un cluster fiecărei observații și apoi trece la etapa de actualizare, calculând astfel media inițială pentru a fi centroidul punctelor alocate aleatoriu ale clusterului. Metoda Forgy tinde să răspândească mijloacele inițiale, în timp ce partiția aleatorie le plasează pe toate aproape de centrul setului de date. Potrivit Hamerly et al., Metoda aleatorie Partition este în general preferabil algoritmi cum ar fi k mijloace -harmonic și fuzzy , k -means. Pentru maximizarea așteptărilor și algoritmii standard k- înseamnă, este preferabilă metoda Forgy de inițializare. Un studiu cuprinzător realizat de Celebi și colab., Cu toate acestea, a constatat că metodele de inițializare populare, cum ar fi Forgy, Random Partition și Maximin, de multe ori au performanțe slabe, în timp ce abordarea lui Bradley și Fayyad are o performanță „constantă” în „cel mai bun grup” și k -means ++ performează ” în general bine ”.

Demonstrarea algoritmului standard
1. k „înseamnă” inițial (în acest caz k = 3) sunt generate aleatoriu în domeniul de date (afișat în culori).
2. k grupurile sunt create prin asocierea fiecărei observații cu cea mai apropiată medie. Partițiile de aici reprezintă diagrama Voronoi generată de mijloace.
3. Centroidul fiecăruia dintre k grupuri devine noua medie.
4. Pașii 2 și 3 se repetă până când se ajunge la convergență.

Algoritmul nu garantează convergența către optimul global. Rezultatul poate depinde de grupurile inițiale. Deoarece algoritmul este de obicei rapid, este obișnuit să îl rulați de mai multe ori cu condiții de pornire diferite. Cu toate acestea, cel mai rău caz de performanță poate fi lent: în special anumite seturi de puncte, chiar și în două dimensiuni, converg în timp exponențial, adică $2 Ω (n)$ . Aceste seturi de puncte nu par să apară în practică: aceasta este confirmată de faptul că netezită timpul de rulare al k -means este polinom.

Pasul „atribuire” este denumit „pasul de așteptare”, în timp ce „pasul de actualizare” este un pas de maximizare, făcând din acest algoritm o variantă a algoritmului generalizat de așteptare-maximizare .

Complexitate

Găsirea soluției optime la problema de grupare k- înseamnă pentru observații în dimensiuni d este:

NP-hard în general spațiul euclidian (de dimensiuni d ) chiar și pentru două clustere,
NP-hard pentru un număr general de clustere k chiar și în plan,
dacă k și d (dimensiunea) sunt fixate, problema poate fi rezolvată exact în timp , unde n este numărul de entități care trebuie grupate. ${\ displaystyle O (n ^ {dk + 1})}$

Astfel, se utilizează în general o varietate de algoritmi euristici precum algoritmul lui Lloyd dat mai sus.

Durata de funcționare a algoritmului Lloyd (și a majorității variantelor) este , unde: ${\ displaystyle O (nkdi)}$

n este numărul de vectori d- dimensionali (care trebuie grupați)
k numărul de clustere
i numărul de iterații necesare până la convergență.

Pe datele care au o structură de grupare, numărul de iterații până la convergență este adesea mic și rezultatele se îmbunătățesc ușor doar după prima duzină de iterații. Prin urmare, algoritmul lui Lloyd este adesea considerat a avea o complexitate „liniară” în practică, deși este în cel mai rău caz superpolinomial atunci când este realizat până la convergență.

În cel mai rău caz, algoritmul lui Lloyd are nevoie de iterații, astfel încât complexitatea în cel mai rău caz al algoritmului lui Lloyd este superpolinomială . ${\ displaystyle i = 2 ^ {\ Omega ({\ sqrt {n}})}}$
Algoritmul lui Lloyd k- înseamnă un timp de rulare netezit polinomial. Se arată că pentru un set arbitrar de n puncte în , dacă fiecare punct este perturbat independent de o distribuție normală cu media $0$ și varianță , atunci timpul de funcționare așteptat al algoritmului $k-$ înseamnă este delimitat de , care este un polinom în $n$ , $k$ , $d$ și . ${\ displaystyle [0,1] ^ {d}}$ ${\ displaystyle \ sigma ^ {2}}$ ${\ displaystyle O (n ^ {34} k ^ {34} d ^ {8} \ log ^ {4} (n) / \ sigma ^ {6})}$ ${\ displaystyle 1 / \ sigma}$
Limitele mai bune sunt dovedite pentru cazurile simple. De exemplu, se arată că timpul de rulare al algoritmului k- înseamnă este mărginit de pentru $n$ puncte într-o rețea întreagă . ${\ displaystyle O (dn ^ {4} M ^ {2})}$ ${\ displaystyle \ {1, \ dots, M \} ^ {d}}$

Algoritmul lui Lloyd este abordarea standard pentru această problemă. Cu toate acestea, petrece mult timp de procesare calculând distanțele dintre fiecare dintre k centrele cluster și cele n puncte de date. Deoarece punctele rămân de obicei în aceleași clustere după câteva iterații, o mare parte din această lucrare nu este necesară, ceea ce face ca implementarea naivă să fie foarte ineficientă. Unele implementări folosesc cache-ul și inegalitatea triunghiului pentru a crea limite și a accelera algoritmul lui Lloyd.

Variații

Optimizarea pauzelor naturale Jenks : k- mijloace aplicate datelor univariate
Clusterul k -medians utilizează mediana în fiecare dimensiune în loc de medie, și în acest mod minimizeazănorma ( geometria Taxicab ). ${\ displaystyle L_ {1}}$
k -medoids (de asemenea: Partitioning Around Medoids, PAM) folosește medoidul în loc de medie, iar acest mod minimizează suma distanțelor pentrufuncții de distanță arbitrare .
Fuzzy C-Means Clustering este o versiune soft a k -means, în care fiecare punct de date are un grad de apartenență la fiecare cluster.
Modelele de amestec gaussian antrenate cu algoritmul de maximizare a așteptărilor ( algoritmul EM) mențin atribuții probabilistice către clustere, în loc de atribuții deterministe, și distribuții Gauss multivariate în locul mijloacelor.
k -means ++ alege centrele inițiale într-un mod care oferă o limită superioară demonstrabilă asupra obiectivului WCSS.
Algoritmul de filtrare folosește kd-copaci pentru a accelera fiecare pas k- înseamnă.
Unele metode încearcă să accelereze fiecare pas k- înseamnă folosind inegalitatea triunghiului .
Evitați optima locală schimbând punctele între clustere.
Algoritmul de grupare sferic k- înseamnă că este potrivit pentru date textuale.
Variante ierarhice, cum ar fi bisectarea k -înseamnă , X-înseamnă clustering și G-înseamnă clustering împarte în mod repetat clustere pentru a construi o ierarhie și pot încerca, de asemenea, să determine automat numărul optim de clustere dintr-un set de date.
Măsurile interne de evaluare a clusterelor , cum ar fi silueta clusterelor, pot fi utile la determinarea numărului de clustere .
Minkowski ponderat k- mijloace calculează automat greutățile caracteristice specifice clusterului, susținând ideea intuitivă că o caracteristică poate avea diferite grade de relevanță la diferite caracteristici. Aceste greutăți pot fi, de asemenea, utilizate pentru a re-scala un anumit set de date, crescând probabilitatea ca un indice de validitate a clusterului să fie optimizat la numărul așteptat de clustere.
Mini-batch k- înseamnă: variație k- înseamnă folosind eșantioane „mini-batch” pentru seturi de date care nu se încadrează în memorie.
Metoda lui Otsu

Metoda Hartigan – Wong

Metoda lui Hartigan și Wong oferă o variație a algoritmului k- mijloace care progresează către un minim local al problemei sumelor minime a pătratelor cu diferite actualizări de soluții. Metoda este o căutare locală care încearcă în mod iterativ să mute un eșantion într-un cluster diferit, atâta timp cât acest proces îmbunătățește funcția obiectivă. Atunci când niciun eșantion nu poate fi mutat într-un cluster diferit cu o îmbunătățire a obiectivului, metoda se oprește (într-un minim local). În mod similar cu mijloacele k clasice , abordarea rămâne o euristică, deoarece nu garantează neapărat că soluția finală este optimă la nivel global.

Fie costul individual al definit de , cu centrul clusterului. ${\ displaystyle \ varphi (S_ {j})}$ ${\ displaystyle S_ {j}}$ ${\ displaystyle \ sum _ {x \ în S_ {j}} (x- \ mu _ {j}) ^ {2}}$ ${\ displaystyle \ mu _ {j}}$

Pasul de atribuire: metoda lui Hartigan și Wong începe prin partiționarea punctelor în clustere aleatorii . ${\ displaystyle \ {S_ {j} \} _ {j \ in \ {1, \ cdots k \}}}$

Pasul de actualizare : În continuare determină și pentru care următoarea funcție atinge un maxim ${\ displaystyle n, m \ in \ {1, \ ldots, k \}}$ ${\ displaystyle x \ în S_ {n}}$

{\ displaystyle \ Delta (m, n, x) = \ varphi (S_ {n}) + \ varphi (S_ {m}) - \ varphi (S_ {n} \ smallsetminus \ {x \}) - \ varphi ( S_ {m} \ cup \ {x \}).}

Pentru cei care ating acest maxim, se mută din cluster în cluster . ${\ displaystyle x, n, m}$ ${\ displaystyle x}$ ${\ displaystyle S_ {n}}$ ${\ displaystyle S_ {m}}$

Încheiere : algoritmul se încheie o dată este mai mic decât zero pentru toate . ${\ displaystyle \ Delta (m, n, x)}$ ${\ displaystyle x, n, m}$

Pot fi folosite diferite strategii de acceptare a mișcării. Într-o strategie de primă îmbunătățire , se poate aplica orice relocare îmbunătățită, în timp ce într-o strategie de îmbunătățire optimă , toate relocările posibile sunt testate iterativ și numai cele mai bune sunt aplicate la fiecare iterație. Prima abordare favorizează viteza, indiferent dacă cea din urmă abordează în general calitatea soluției în detrimentul timpului de calcul suplimentar. Funcția utilizată pentru a calcula rezultatul unei relocări poate fi, de asemenea, evaluată eficient utilizând egalitatea ${\ displaystyle \ Delta}$

{\ displaystyle \ Delta (x, n, m) = {\ frac {\ mid S_ {n} \ mid} {\ mid S_ {n} \ mid -1}} \ cdot \ lVert \ mu _ {n} - x \ rVert ^ {2} - {\ frac {\ mid S_ {m} \ mid} {\ mid S_ {m} \ mid +1}} \ cdot \ lVert \ mu _ {m} -x \ rVert ^ { 2}.}

Optimizare globală și metaheuristică

Se știe că algoritmul clasic al mijloacelor k și variațiile sale converg doar la minimele locale ale problemei de grupare a sumelor minime de pătrate definite ca

{\ displaystyle {\ underset {\ mathbf {S}} {\ operatorname {arg \, min}}} \ sum _ {i = 1} ^ {k} \ sum _ {\ mathbf {x} \ in S_ {i }} \ left \ | \ mathbf {x} - {\ boldsymbol {\ mu}} _ {i} \ right \ | ^ {2}.}

Multe studii au încercat să îmbunătățească comportamentul de convergență al algoritmului și să maximizeze șansele de a atinge optimul global (sau cel puțin, minimele locale de o calitate mai bună). Tehnicile de inițializare și repornire discutate în secțiunile anterioare reprezintă o alternativă pentru a găsi soluții mai bune. Mai recent, algoritmii de programare matematică bazate pe generarea ramurilor și legăturilor și a coloanei au produs soluții „dovedite optime” pentru seturi de date cu până la 2.300 de entități. Așa cum era de așteptat, datorită durității NP a problemei de optimizare subiacentă, timpul de calcul al algoritmilor optimi pentru mijloacele K crește rapid dincolo de această dimensiune. Soluțiile optime pentru scară mică și medie rămân în continuare valoroase ca instrument de referință, pentru a evalua calitatea altor euristici. Pentru a găsi minime locale de înaltă calitate într-un timp de calcul controlat, dar fără garanții de optimitate, alte lucrări au explorat metaheuristica și alte tehnici de optimizare globală , de exemplu, bazate pe abordări incrementale și optimizare convexă, swap-uri aleatorii (adică căutare locală iterată ), vecinătate variabilă algoritmi de căutare și genetici . Se știe într-adevăr că găsirea unor minime locale mai bune ale problemei de grupare a sumelor minime de pătrate poate face diferența dintre eșec și succes în recuperarea structurilor de cluster în spații caracteristice de dimensiuni ridicate.

Discuţie

Un exemplu tipic de convergență k- înseamnă la un minim local. În acest exemplu, rezultatul grupării k- înseamnă (figura corectă) contrazice structura evidentă a clusterului setului de date. Cercurile mici sunt punctele de date, cele patru stele cu raze sunt centroizii (mijloace). Configurația inițială este în figura din stânga. Algoritmul converge după cinci iterații prezentate pe figuri, de la stânga la dreapta. Ilustrația a fost pregătită cu applet-ul Java Mirkes.

k- înseamnă rezultatul grupării pentru setul de date de flori de Iris și speciile reale vizualizate folosind ELKI . Mijloacele cluster sunt marcate folosind simboluri mai mari, semitransparente.

k- înseamnă clustering vs. EM clustering pe un set de date artificial („mouse”). Tendința k- mijloacelor de a produce clustere de dimensiuni egale duce la rezultate proaste aici, în timp ce EM beneficiază de distribuțiile Gaussiene cu rază diferită prezentă în setul de date.

Trei caracteristici cheie ale k- mijloacelor care îl fac eficient sunt adesea considerate drept cele mai mari dezavantaje:

Distanța euclidiană este utilizată ca metrică și varianța este utilizată ca măsură a dispersiei clusterului.
Numărul de clustere k este un parametru de intrare: o alegere inadecvată a lui k poate produce rezultate slabe. De aceea, atunci când efectuați k- mijloace, este important să efectuați verificări de diagnostic pentru determinarea numărului de clustere din setul de date .
Convergența la un minim local poate produce rezultate contraintuitive („greșite”) (a se vedea exemplul din Fig.).

O limitare cheie a k- mijloacelor este modelul său de cluster. Conceptul se bazează pe clustere sferice care pot fi separate astfel încât media converge către centrul clusterului. Clusterele sunt de așteptat să aibă o dimensiune similară, astfel încât atribuirea către cel mai apropiat centru de cluster este atribuirea corectă. De exemplu, când se aplică k- mijloace cu o valoare de pe binecunoscutul set de date de flori de Iris , rezultatul nu reușește adesea să separe cele trei specii de Iris conținute în setul de date. Cu , cele două clustere vizibile (una care conține două specii) vor fi descoperite, în timp ce una dintre cele două clustere va fi împărțită în două părți pare. De fapt, este mai potrivit pentru acest set de date, în ciuda setului de date care conține 3 clase . Ca și în cazul oricărui alt algoritm de grupare, rezultatul k- înseamnă presupune că datele îndeplinesc anumite criterii. Funcționează bine pe unele seturi de date și nu reușește pe altele. ${\ displaystyle k = 3}$ ${\ displaystyle k = 2}$ ${\ displaystyle k = 3}$ ${\ displaystyle k = 2}$

Rezultatul k- mijloacelor poate fi văzut ca celulele Voronoi ale grupului. Deoarece datele sunt împărțite la jumătatea distanței dintre mijloacele cluster, acest lucru poate duce la divizări suboptimale, așa cum se poate vedea în exemplul „mouse-ului”. Modelele gaussiene utilizate de algoritmul de maximizare așteptărilor (probabil o generalizare a k- mijloacelor) sunt mai flexibile, având atât varianțe, cât și covarianțe. Rezultatul EM este astfel capabil să acomodeze clustere de dimensiuni variabile mult mai bune decât k- mijloace, precum și clustere corelate (nu în acest exemplu). În contrapartidă, EM necesită optimizarea unui număr mai mare de parametri liberi și pune unele probleme metodologice din cauza dispariției clusterelor sau a matricelor de covarianță prost condiționate. K- mijloace este strâns legat de modelarea bayesiană neparametrică .

Aplicații

K- înseamnă că clusterizarea este destul de ușor de aplicat chiar și seturilor de date mari, în special atunci când se utilizează euristici, cum ar fi algoritmul lui Lloyd . A fost folosit cu succes în segmentarea pieței , viziunea computerizată și astronomie, printre multe alte domenii. Este adesea folosit ca etapă de preprocesare pentru alți algoritmi, de exemplu pentru a găsi o configurație de pornire.

Cuantizarea vectorială

Imagine color cu două canale (în scop ilustrativ - numai canale roșii și verzi).

Cuantificarea vectorială a culorilor prezente în imaginea de mai sus în celule Voronoi folosind k- mijloace.

k- mijloace provine din procesarea semnalului și încă își găsește utilizarea în acest domeniu. De exemplu, în grafica computerizată , cuantificarea culorilor este sarcina de a reduce paleta de culori a unei imagini la un număr fix de culori k . K Algoritmul -means poate fi ușor de utilizat pentru această sarcină și produce rezultate competitive. Un caz de utilizare pentru această abordare este segmentarea imaginii . Alte utilizări ale cuantificării vectoriale includ eșantionarea non-aleatorie , deoarece k- mijloace pot fi ușor utilizate pentru a alege k obiecte diferite, dar prototipice dintr-un set mare de date pentru o analiză ulterioară.

Analiza grupului

În analiza clusterelor, algoritmul k- înseamnă poate fi folosit pentru partiționarea setului de date de intrare în k partiții (clustere).

Cu toate acestea, algoritmul k- înseamnă pur nu este foarte flexibil și, ca atare, este de utilizare limitată (cu excepția cazului în care cuantizarea vectorială așa cum este mai sus este de fapt cazul de utilizare dorit). În special, se știe că parametrul k este greu de ales (așa cum s-a discutat mai sus) atunci când nu este dat de constrângeri externe. O altă limitare este că nu poate fi utilizat cu funcții de distanță arbitrare sau pe date nenumerice. Pentru aceste cazuri de utilizare, mulți alți algoritmi sunt superiori.

Învățarea caracteristicilor

k -means gruparea a fost utilizată ca o învățare caracteristică (sau de învățare dicționar ) etapă, fie ( semi- ) supravegheat de învățare sau de învățare nesupravegheata . Abordarea de bază este mai întâi formarea unei reprezentări de grupare k- înseamnă, folosind datele de instruire de intrare (care nu trebuie etichetate). Apoi, pentru a proiecta orice referință de intrare în noul spațiu de caracteristici, o funcție de „codificare”, cum ar fi produsul matricial prag al referinței cu locațiile centrului, calculează distanța de la referință la fiecare centroid, sau pur și simplu o funcție indicator pentru cel mai apropiat centroid sau o transformare ușoară a distanței. Alternativ, transformând distanța eșantion-cluster printr-un RBF Gaussian , se obține stratul ascuns al unei rețele funcționale de bază radială .

Această utilizare a k- mijloacelor a fost combinată cu succes cu clasificatori simpli și liniari pentru învățarea semi-supravegheată în NLP (în special pentru recunoașterea entității denumite ) și în viziunea computerizată . Pe o sarcină de recunoaștere a obiectelor, s-a constatat că prezintă performanțe comparabile cu abordări mai sofisticate de învățare a caracteristicilor, cum ar fi autoencodere și mașini Boltzmann restricționate . Cu toate acestea, în general necesită mai multe date, pentru performanțe echivalente, deoarece fiecare punct de date contribuie doar la o „caracteristică”.

Relația cu alți algoritmi

Model de amestec gaussian

„Algoritmul standard” lent pentru gruparea k- înseamnă, și algoritmul său de așteptare-maximizare asociat , este un caz special al unui model de amestec gaussian, în mod specific, cazul limitativ la fixarea tuturor covarianțelor pentru a fi diagonale, egale și pentru a avea o variație infinitesimală mică. În loc de varianțe mici, o atribuire de cluster dur poate fi utilizată și pentru a arăta o altă echivalență a grupării k- mijloace la un caz special de modelare a amestecului Gauss „greu”. Aceasta nu înseamnă că este eficient să se utilizeze modelarea amestecului Gaussian pentru a calcula k- mijloace, ci doar că există o relație teoretică și că modelarea Gaussiană a amestecului poate fi interpretată ca o generalizare a k- mijloacelor; dimpotrivă, s-a sugerat utilizarea clusterizării k-mijloacelor pentru a găsi puncte de plecare pentru modelarea amestecului Gaussian pe date dificile.

K-SVD

O altă generalizare a algoritmului k- înseamnă este algoritmul K-SVD, care estimează punctele de date ca o combinație liniară rară de „vectori de coduri”. k -means corespunde cazului special al utilizării unui singur codbook vector, cu o greutate de 1.

Analiza componentelor principale

Soluția relaxată a grupării $k-$ înseamnă, specificată de indicatorii cluster, este dată de analiza componentelor principale (PCA). Intuiția este că k- mijloacele descriu grupuri de formă sferică (în formă de bilă). Dacă datele au 2 clustere, linia care leagă cei doi centroizi este cea mai bună direcție de proiecție 1-dimensională, care este și prima direcție PCA. Tăierea liniei în centrul masei separă clusterele (aceasta este relaxarea continuă a indicatorului de cluster discret). Dacă datele au trei clustere, planul bidimensional cuprins de trei centroizi de clustere este cea mai bună proiecție 2D. Acest plan este definit și de primele două dimensiuni PCA. Clusterele bine separate sunt modelate în mod eficient de clustere în formă de bilă și astfel descoperite de k- mijloace. Clusterele fără formă de bilă sunt greu de separat atunci când sunt aproape. De exemplu, două clustere în formă de jumătate de lună împletite în spațiu nu se separă bine atunci când sunt proiectate pe subspațiul PCA. k- mijloace nu ar trebui să se aștepte să funcționeze bine pe aceste date. Este simplu să se producă contraexemple pentru a afirma că subspaiul centroid cluster este întins pe direcțiile principale.

Grupare medie de schimbare

Algoritmii de bază de grupare a deplasărilor medii mențin un set de puncte de date de aceeași dimensiune ca și setul de date de intrare. Inițial, acest set este copiat din setul de intrare. Apoi, acest set este înlocuit iterativ cu media acelor puncte din set care se află la o distanță dată de acel punct. Prin contrast, k- înseamnă restricționează acest set actualizat la k puncte de obicei mult mai puțin decât numărul de puncte din setul de date de intrare și înlocuiește fiecare punct din acest set cu media tuturor punctelor din setul de intrare care sunt mai aproape de acel punct decât oricare altul (de exemplu, în cadrul partiției Voronoi a fiecărui punct de actualizare). Un algoritm de deplasare medie care este similar atunci cu k- mijloace, numit deplasare medie de probabilitate , înlocuiește setul de puncte care urmează să fie înlocuite cu media tuturor punctelor din setul de intrare care se află la o distanță dată de setul de schimbare. Unul dintre avantajele deplasării medii față de k- mijloace este că numărul de clustere nu este pre-specificat, deoarece schimbarea medie este probabil să găsească doar câteva clustere dacă există doar un număr mic. Cu toate acestea, schimbarea medie poate fi mult mai lentă decât k- înseamnă și necesită totuși selectarea unui parametru de lățime de bandă. Deplasarea medie are variante moi.

Analiza componentelor independente

Sub ipotezele de raritate și atunci când datele de intrare sunt pre-procesate cu transformarea de albire , k- mijloace produce soluția sarcinii de analiză liniară independentă a componentelor (ICA). Acest lucru ajută la explicarea aplicării cu succes a k- mijloacelor de învățare a caracteristicilor .

Filtrare bilaterală

k- înseamnă presupune implicit că ordinea setului de date de intrare nu contează. Filtrul bilateral este similar cu k- mijloace și schimbare medie prin faptul că menține un set de puncte de date care sunt înlocuite iterativ cu mijloace. Cu toate acestea, filtrul bilateral restricționează calculul (kernel ponderat) pentru a include doar punctele care sunt apropiate în ordonarea datelor de intrare. Acest lucru îl face aplicabil la probleme precum dezagregarea imaginii, unde dispunerea spațială a pixelilor dintr-o imagine are o importanță critică.

Probleme similare

Setul de erori pătrate care minimizează funcțiile clusterului include, de asemenea, algoritmul k- medoid , o abordare care forțează punctul central al fiecărui cluster să fie unul dintre punctele reale, adică folosește medoizi în locul centroidelor .

Implementări software

Diferite implementări ale algoritmului prezintă diferențe de performanță, cea mai rapidă pe un set de date de testare terminând în 10 secunde, cea mai lentă durând 25 988 secunde (~ 7 ore). Diferențele pot fi atribuite calității implementării, diferențelor de limbă și compilator, diferitelor criterii de terminare și niveluri de precizie și utilizării indexurilor pentru accelerare.

Software gratuit / Open Source

Următoarele implementări sunt disponibile sub licențe software gratuit / open source , cu cod sursă disponibil public.

Accord.NET conține implementări C # pentru k -means, k -means ++ și k -modes.
ALGLIB conține implementări paralelizate C ++ și C # pentru k- mijloace și k- mijloace ++.
AOSP conține o implementare Java pentru k- mijloace.
CrimeStat implementează doi algoritmi k- înseamnă spațiali, dintre care unul permite utilizatorului să definească locațiile de pornire.
ELKI conține k -means (cu iterație Lloyd și MacQueen, împreună cu inițializări diferite, cum ar fi inițializarea k -means ++) și diverși algoritmi de clusterizare mai avansați.
Smile conține k- mijloace și mai mulți alți algoritmi și vizualizarea rezultatelor (pentru java, kotlin și scala).
Julia conține o implementare k- înseamnă în pachetul JuliaStats Clustering.
KNIME conține noduri pentru k- mijloace și k -medoide.
Mahout conține k- mijloace bazate pe MapReduce .
mlpack conține o implementare C ++ a k- mijloacelor.
Octave conține k- mijloace.
OpenCV conține o implementare k- înseamnă.
Orange include o componentă pentru k- înseamnă clustering cu selecție automată a punctării k și a siluetei cluster.
PSPP conține k- mijloace, comanda QUICK CLUSTER efectuează clustering k- mijloace pe setul de date.
R conține trei k- înseamnă variații.
SciPy și scikit-learn conțin mai multe implementări k- înseamnă.
Spark MLlib implementează un algoritm distribuit k- înseamnă.
Torch conține un pachet unsup care oferă clustering k- înseamnă.
Weka conține k- mijloace și x- mijloace.

Proprietate

Următoarele implementări sunt disponibile în condițiile licenței proprietare și este posibil să nu aibă cod sursă disponibil public.

Languages

In other projects