K-înseamnă

Algoritmul K- înseamnă un algoritm de analiză a grupului de partiții care vă permite să împărțiți un set de obiecte în k grupuri pe baza atributelor lor. Este o variantă a algoritmului de așteptare-maximizare (EM) al cărui scop este de a determina k grupurile de date generate de distribuțiile Gaussiene . Se presupune că atributele obiectelor pot fi reprezentate ca vectori și astfel pot forma un spațiu vectorial .

Descriere generala

Scopul pe care algoritmul îl stabilește este acela de a minimiza varianța totală în interiorul grupului; fiecare grup este identificat printr-un centroid sau punct mediu. Algoritmul urmează o procedură iterativă: inițial creează k partiții și atribuie puncte de intrare fiecărei partiții fie aleatoriu, fie folosind unele informații euristice; apoi calculați centroidul fiecărui grup; apoi construiește o nouă partiție prin asocierea fiecărui punct de intrare grupului al cărui centroid este cel mai apropiat de acesta; în cele din urmă, centroizii sunt recalculați pentru noile grupuri și așa mai departe, până când algoritmul converge.

Descriere formală

Date N obiecte cu $the$ ${\ displaystyle i}$ $the$ atribute, modelate ca vectori într-un spațiu vectorial $the$ ${\ displaystyle i}$ $the$ -dimensional, definim $X={X_{1},X_{2},\ldots ,X_{N}}$ ${\ displaystyle X = {X_ {1}, X_ {2}, \ ldots, X_ {N}}}$ $X = {X_ {1}, X_ {2}, \ ldots, X_ {N}}$ ca un set de obiecte. Amintiți-vă că partiția obiect este definită ca grupul de seturi $P={P_{1},P_{2},\ldots ,P_{K}}$ ${\ displaystyle P = {P_ {1}, P_ {2}, \ ldots, P_ {K}}}$ $P = {P_ {1}, P_ {2}, \ ldots, P_ {K}}$ care îndeplinesc următoarele proprietăți:

$\bigcup _{1}^{K}P_{i}=X$ ${\ displaystyle \ bigcup _ {1} ^ {K} P_ {i} = X}$ $\ bigcup _ {1} ^ {{K}} P_ {i} = X$ : unirea tuturor clusterelor trebuie să conțină toate obiectele de pornire;
$P_{i}\cap P_{j}=\varnothing ,i\neq j$ ${\ displaystyle P_ {i} \ cap P_ {j} = \ varnothing, i \ neq j}$ ${\ displaystyle P_ {i} \ cap P_ {j} = \ varnothing, i \ neq j}$ : fiecare obiect poate aparține unui singur cluster;
$\varnothing \subset P_{i}\subset X$ ${\ displaystyle \ varnothing \ subset P_ {i} \ subset X}$ $\ varnothing \ subset P_ {i} \ subset X$ : cel puțin un obiect trebuie să aparțină unui cluster și niciun cluster nu poate conține toate obiectele.

Evident, trebuie să fie și adevărat că $1<K<N$ ${\ displaystyle 1 <K <N}$ $1 <K <N$ ; de fapt, nu ar avea sens nici să căutăm un singur cluster, nici să avem un număr de clustere egal cu numărul de obiecte. O partiție este reprezentată de o matrice $U\in \mathbb {N} ^{K\times N}$ ${\ displaystyle U \ in \ mathbb {N} ^ {K \ times N}}$ $U \ in {\ mathbb {N}} ^ {{K \ times N}}$ , al cărui element generic $u_{ij}=\{0,1\}$ ${\ displaystyle u_ {ij} = \ {0,1 \}}$ ${\ displaystyle u_ {ij} = \ {0,1 \}}$ indică apartenența obiectului $j$ ${\ displaystyle j}$ $j$ la cluster $the$ ${\ displaystyle i}$ $the$ . Prin urmare, indicăm cu $C={C_{1},C_{2},\ldots ,C_{K}}$ ${\ displaystyle C = {C_ {1}, C_ {2}, \ ldots, C_ {K}}}$ $C = {C_ {1}, C_ {2}, \ ldots, C_ {K}}$ setul de $K.$ ${\ displaystyle K}$ $K.$ centroizi. În acest moment, definim funcția obiectivă ca:

V(U,C)=\sum _{i=1}^{K}\sum _{X_{j}\in P_{i}}||X_{j}-C_{i}||^{2}

{\ displaystyle V (U, C) = \ sum _ {i = 1} ^ {K} \ sum _ {X_ {j} \ in P_ {i}} || X_ {j} -C_ {i} || ^ {2}}

V (U, C) = \ sum _ {{i = 1}} ^ {{K}} \ sum _ {{X_ {j} \ in P_ {i}}} || X_ {j} -C_ {i } || ^ {2}

și din aceasta calculăm minimul urmând procedura iterativă văzută mai sus:

Generează $U_{v}$ ${\ displaystyle U_ {v}}$ $U_ {v}$ Și $C_{v}$ ${\ displaystyle C_ {v}}$ $CV}$ Aleatoriu
calculati $U_{n}$ ${\ displaystyle U_ {n}}$ $A}$ care minimizează $V(U,C_{v})$ ${\ displaystyle V (U, C_ {v})}$ $V (U, C_ {v})$
calculati $C_{n}$ ${\ displaystyle C_ {n}}$ $C_n$ care minimizează $V(U_{v},C)$ ${\ displaystyle V (U_ {v}, C)}$ $V (U_ {v}, C)$
Dacă algoritmul converge, acesta se oprește, altfel $U_{v}=U_{n},C_{v}=C_{n}$ ${\ displaystyle U_ {v} = U_ {n}, C_ {v} = C_ {n}}$ $U_ {v} = U_ {n}, C_ {v} = C_ {n}$ și reveniți la pasul 2

Criteriile tipice de convergență sunt următoarele:

Nu există modificări în matrice $U$ ${\ displaystyle U}$ $U$ ;
diferența dintre valorile funcției obiective în două iterații succesive nu depășește un prag predeterminat.

Argumente pro şi contra

Algoritmul a dobândit notorietate deoarece converge foarte repede: s-a observat de fapt că, în general, numărul de iterații este mai mic decât numărul de puncte. Cu toate acestea, algoritmul poate fi foarte lent în cel mai rău caz: D. Arthur și S. Vassilvitskii au arătat că există anumite seturi de puncte pentru care algoritmul are un timp superpolinomial $2^{\Omega ({\sqrt {n}})}$ ${\ displaystyle 2 ^ {\ Omega ({\ sqrt {n}})}}$ $2 ^ {{\ Omega ({\ sqrt {n}})}}$ a converge. Mai recent, A. Vattani a îmbunătățit acest rezultat, arătând că algoritmul poate dura exponențial $2^{\Omega (n)}$ ${\ displaystyle 2 ^ {\ Omega (n)}}$ $2 ^ {{\ Omega (n)}}$ să convergă și pentru anumite seturi de puncte din plan. Pe de altă parte, D. Arthur, B. Manthey și H. Roeglin au arătat că complexitatea netezită a algoritmului este polinomială, ceea ce susține faptul că algoritmul este rapid în practică.

În ceea ce privește calitatea soluțiilor, algoritmul nu garantează realizarea optimului global: calitatea soluției finale depinde în mare măsură de setul inițial de grupuri și poate, în practică, să obțină o soluție mult mai proastă decât optimul global . Deoarece algoritmul este de obicei extrem de rapid, este posibil să-l aplicați de mai multe ori și să alegeți cea mai satisfăcătoare soluție dintre cele produse. Un alt dezavantaj al algoritmului este acela că necesită alegerea numărului de grupuri k de identificat; dacă datele nu sunt partiționate în mod natural, veți obține rezultate ciudate. Mai mult, algoritmul funcționează bine numai atunci când grupurile sferice sunt detectabile în date.

K- înseamnă în Matlab

Puteți aplica algoritmul K- means în Matlab folosind funcția kmeans (DATA, N_CLUSTER) , care găsește numerele de cluster N_CLUSTER printre datele DATA. Următorul fișier m arată o posibilă aplicație a algoritmului pentru gruparea datelor de imagine bazate pe culoare.

img_segm.m

 %Sintaxă:
% img_segm (nume de fișier, N_CLUSTER)
%
%Descriere:
% Având o imagine în tonuri de gri, o segmentează într-un
% dat număr de segmente, utilizând algoritmi de grupare. 
%
% Intrări:
% filename - Numele fișierului care conține imaginea
% N_CLUSTER - Număr de segmente
dacă nargin <2
    eroare („Număr insuficient de parametri”);
Sfârșit
imagine = imread (numele fișierului);
MO = [];
linii = dimensiune (imagine, 1);
coloane = dimensiune (imagine, 2);
pentru i = 1: linii
    pentru j = 1: coloane
        c = imagine (i, j, 3);
        MO = [MO; i, j, c];
    Sfârșit
Sfârșit
MO = dublu (MO);
U = kmeans (MO, N_CLUSTER);
pentru k = 1: N_CLUSTER
    ris = 255. * cele (rânduri, coloane);
    temp = find (U == k);
    pentru i = 1: lungime (temp)
        rând = etaj (temp (i) / coloane) + 1;
        coloană = mod (temp (i), coloane) + 1;
        ris (rând, coloană) = 0;
    Sfârșit
    figura ('nume', sprintf ('Cluster% d', k));
    imagine (ris);
    colormap (gri (256));
Sfârșit

Funcția citește imaginea utilizând funcția Matlab imread, care primește ca intrare numele fișierului care conține imaginea și returnează un tablou al cărui element $k_{ij}$ ${\ displaystyle k_ {ij}}$ $k _ {{ij}}$ conține codul de culoare al pixelilor i, j. Apoi, construiește matricea de observații cu două simple pentru bucle. În cele din urmă, matricea de observații este transmisă în intrarea algoritmului de grupare și, după ce a generat matricile utile pentru afișarea clusterelor produse într-o imagine, acestea sunt afișate pe ecran cu funcția de imagine.

De exemplu, executând comanda:
img_segm ('kmeans0.jpg', 2);
se obține următorul rezultat:

Imagine originală
Primul grup
Al doilea grup

Bibliografie

JB MacQueen (1967): „Câteva metode pentru clasificarea și analiza observațiilor multivariate”, Lucrările celui de-al cincilea simpozion Berkeley privind statistici și probabilități matematice, Berkeley, University of California Press, 1: 281-297
D. Arthur , S. Vassilvitskii (2006): „Cât de lentă este metoda k-means?”, Proceedings of the 2006 Simpozion on Computational Geometry (SoCG).
A. Vattani (2009): „k-înseamnă necesită exponențial multe iterații chiar și în plan”, Proceedings of the 2009 Symposium on Computational Geometry (SoCG).
D. Arthur , B. Manthey , H. Roeglin (2009): „k-means are polynomial smoothled complex”, Proceedings of the 50th Symposium on Foundations of Computer Science (FOCS).

Elemente conexe

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere pe k-means

linkuri externe

Exemple numerice de grupare cu K-means , pe people.revoledu.com .
Exemple de aplicații care utilizează K-înseamnă clustering pentru a reduce numărul de culori din imagini , pe leet.it.
(IT) Articol informativ despre Clustering și Mining de date , pe mathici.it .
Extensie PostgreSQL pentru k-means , pe pgxn.org .

Portal IT

Portalul de matematică

V · D · M Învățare automată
Probleme	Clasificarea · Regresie · asociere Reguli · Învățare nesupravegheați · Supravegheat de învățare · Reinforcement Learning · învățare profundă
Învățare nesupravegheată	Clustering · clustering Ierarhica · K mijloace · Așteptarea maximizare · DBSCAN · schimbare medie · antagonist generativă rețea (CGAN · cycleGAN VAE-GAN)
Învățare supravegheată	Arborele decizional · Pădure aleatorie · CRF · HMM · KNN · Clasificator bayesian · Rețea neuronală artificială · Regresie liniară · Regresie logistică · PGM · SVM
Consolidarea învățării	Q-learning · SARSA · TD
Reducerea dimensiunii	Analiza factorilor · CCA · ICA · LDA · PCA · Selecția caracteristicilor · Extragerea caracteristicilor · t-SNE
Rețele neuronale artificiale	Perceptron · RBF · N · FFN · Rețea Hopfield · MLP · RNN ( LSTM ) · RBM · SOM · CNN · TDNN · SNN
Software	Keras · Microsoft Cognitive Toolkit · scikit-learn · TensorFlow · Theano · Torch · Weka
Alte	Algoritm genetic · PSO · Caracteristic