Tehnica k-means (k-medii) pentru probleme de grupare [617567]

Tema 1

Învă
ț
are Automată

Tehnica k-means (k-medii) pentru probleme de grupare

Tehnica Expectation-Maximization pentru probleme de grupare

Student: [anonimizat]-Iosif MERKA

Anul 4 gr. 4.1

Exerci
ț
ii propuse:

1) Realiza
ț
i o documenta
ț
ie a func
ț
iilor kmeans
ș
i fitgmdist din Matlab care să cuprindă o

descriere a func
ț
ionalită
ț
ilor, prezentarea argumentelor de intrare
ș
i de ie
ș
ire, informa
ț
ii

despre algoritmul care stă la baza implementării, precum
ș
i diverse exemple de rulare
ș
i

afi
ș
are a datelor, pe alte seturi de date, chiar de dimensiuni mai mari.

Rezolvare:

Func
ț
ia K-MEANS

IDX = kmeans(X,K)
​
împarte punctele în matricea de date X cu N rânduri
ș
i P coloane

în clustere (grupuri) K. Această parti
ț
ie minimizează suma, pe toate grupurile, de sumele în

interiorul grupului de distan
ț
e punct-grup-centru. Rândurile din matricea X corespund

punctelo, iar coloanele corespund variabilelor. Când X este un vector, k-means îl tratează ca

o matrice de date de N rânduri
ș
i o coloană, adică un vector coloană, indifferent de

orientarea acestuia. Kmeans returnează un vector coloană (IDX) cu N rânduri care con
ț
ine

indicii clusterului pentru fiecare punct. Implicit, k-means folose
ș
te pătratul distan
ț
ei

Euclidiene.

K-means tratează NaN-urile ca date lipsă
ș
i ignoră rândurile de X care con
ț
in NaNs.

[IDX,C] = kmeans(X,K) returnează loca
ț
iile centrului grupului în matricea C cu K linii
ș
i P

coloane.

[IDX,C,SUMD] = kmeans(X,K) returnează sumele dista
ț
elor punct-centru din interiorul

clusterului în vectorul coloană SUMD care are K rânduri.

[IDX,C,SUMD,D] = kmeans(X,K) returnează de la fiecare punct la fiecare centru în matricea

D care are N rânduri
ș
i K coloane.

[ … ] = kmeans(…, 'PARAM1',val1, 'PARAM2',val2, …) specifică op
ț
ional perechi parametru

nume/valoare pentru a controla algoritmul iterative folosit de tehnica k-means.

Parametrii sunt:

Distance
​
– măsurarea distan
ț
ei în spa
ț
iul P-dimensional pe care această tehnică ar

trebui să o reducă la valoarea minima.

Start
​
– metodă folosită pentru a culege ini
ț
ial pozi
ț
iile centrale pentru clustere,

cunoscute sub numele de ‘semin
ț
e’.

Replicates
​
– numărul de repetări a grupării, fiecare cu un nou set de centrii ini
ț
iali.

Un număr întreg pozitiv, valoarea implicită fiind 1.

EmptyAction
​
– ac
ț
iune luată în cazul în care un grup pierde toate observa
ț
iile

membrilor.

Options
​
– op
ț
iuni pentru algoritmul iterative utilizat pentru a minimiza criteriul de

potrivire, a
ș
a cum a fost creat de STATSET.

UseSubstreams
​
– setat pe TRUE pentru a calcula în parallel într-un mid

reproductibil. Implicit este pe FALSE. Pentru a calcula reproductibil, fluxurile trebuie setate la

un tip care să permit subre
ț
elele mlfg6331_64 sau mrg32k3a.

OnlinePhase
​
– Flag-ul care indică dacă k-means ar trebui să efectueze o fază de

actualizare on-line în plus fa
ț
ă de o fază de actualizare tot. Faza on-line poate fi

consumatoare de timp pentru seturi mari de data, dar garantează o solu
ț
ie care este un

minim local al criteriului distan
ț
ei, adică o împăr
ț
ire a datelor în cazul în care deplasarea

oricărui punct într-un al grup cre
ș
te suma totală a distan
ț
elor.

Exemplul 1:

Exemplul 2:

Exemplul 3:

Exemplul 4:

Func
ț
ia
​
FITGMDIST
​
:

Cu ajutorul acesteia se aplică o distribu
ț
ie de amestec Gaussian a datelor.

GM = fitgmdist(X,K)
​
se potrive
ș
te cu o distribu
ț
ie a amestecului Gaussian cu

componentele K la datele din X. X este o matrice cu N linii
ș
i D coloane. Liniile din X

corespund observa
ț
iilor. Coloanele corespund variabilelor. Fitgmdist se potrive
ș
te modelului

cu proababilitate maxima, folosind algoritmul Expectation-Maximization (EM).

Această func
ț
ie tratează NaN-urile ca date lipsă. Rândurile de X cu NaN-uri sunt excluse din

potrivire.

GM = fitgmdist(X,K,’PARAM1’,val1,’PARAM2’,val2,…)
​
ne permite să specificăm

perechi op
ț
ionale nume / valoare parametru pentru a specifica detaliile modelului
ș
i pentru a

controla algoritmul iterative EM modelul.

Parametrii sunt:

Start
​
– metoda folosită pentru a alege parametrii ini
ț
iali medii, covarian
ț
ă
ș
i amestec

proportional pentru componentele Gaussian. Replicates – un număr întreg pozitiv, care dă

numărul de repetări, fiecare având un nou set parametrii ini
ț
iali. Fitgmdist returnează

potrivirea cu cea mai mare probabilitate. Numărul prestabilit de replicări este 1. O valoare

mai mare de 1 necesită ca intrarea ‘Start’ să fie ‘randSample’ sau ‘plus’.

CovarianceType
​
– ‘diagonal’ dacă matricile de covarian
ț
ă sunt limitate să fie

diagonal. ‘full’ este similar, doar că se impune full. Aceasta este
ș
i valoarea implicită.

SharedCovariance
​
– este TRUE dacă toate matricile de covarian
ț
ă sunt limitate să

fie acelea
ș
i (estimare samara). Altfel este FALSE, ceea ce este
ș
i valoarea implicită.

RegularizationValue
​
– o valoare de regularizare non-negativă care trebuie adăugată

la diagonal fiecărei matrice de covarian
ț
ă pentru a se asigura că estimările sunt positive

definite. Implicit este 0.

Options
​
– structura de op
ț
iuni pentru algoritmul iterative EM, creat de STATSET.

Exemplul 1

Exemplul 2:

Exemplul3:

Exemplul 4:

2) Realiza
ț
i o func
ț
ie Matlab similară cu kmeans care să con
ț
ină o implementare proprie a

algoritmului k-means cu ini
ț
ializarea centrelor folosind algoritmul k-means++.

În vederea relizării acestei cerin
ț
e, am creat următoarele func
ț
ii:

RecalculareCentru(W, NrCentre, m, indici)
​
care returnează o matrice cu centrele

noi, cu un număr de rânduri egal cu numărul de centre
ș
i 2 coloane.

W
​
– o matrice care con
ț
ine centrele vechi

NrCentre
​
– numărul de centre existente

m
​
– numărul de puncte

indici
​
– o matrice coloană cu indicii centrelor existente

Cod (RecalculareCentru.m):

function [CentreNoi] = RecalculareCentru(W, NrCentre, m, indici)

suma = zeros(NrCentre,1);

CentreNoi = zeros(NrCentre,2);

for i=1 : m

for j=1 : NrCentre

if( indici(i) == j)

suma(j) = suma(j) + 1;

end

end

end

for i=1 : NrCentre

pozitia = find(indici==i);

CentreNoi(i,1) = 1/suma(i) * sum(W(pozitia,1));

CentreNoi(i,2) = 1/suma(i) * sum(W(pozitia,2));

end

end

AtribuireCentru(W, Centre, NrCentre, m)
​
– atribuie unui grup de puncte un centru.

W
​
– o matrice care con
ț
ine centrele vechi

Centre
​
– centrele existente

NrCentre
​
– numărul de centre existente

m
​
– numărul de puncte

Cod (AtribuireCentru.m):

function [indici] = AtribuireCentru(W,Centre, NrCentre ,m)

indici = zeros(size(W,1), 1);

for i = 1 : m %parcurgem fiecare punct

j=1;

aux = 1;

min_dist = norm(W(i,:)-Centre(j,:));

for j = 2 : NrCentre

dist = norm(W(i,:)-Centre(j,:));

if(dist < min_dist)

min_dist = dist;

aux = j;

end

end

indici(i) = aux;

end

end

KmeansPlusPlus()
​
– implementează pa
ș
ii algoritmului kmeans++, acela de ini
ț
ializare a

centrelor. În fi
ș
ierul main.m se cheamă celelalte func
ț
ii, ini
ț
ial cea care implementează

kmeans++ pentru a ini
ț
ializa centrele, iar apoi celelalte pentru a duce la implementarea

algoritmului kmeans.

X = rand(500,2);

Xk = X(:,[1 2]);

[NrCentre Centre] = KmeansPlusPlus()

plot(Xk(:,1),Xk(:,2),'o')

CentreNoi = zeros(NrCentre,2);

m = size(X,1);

x1 = X(:, 1);

x2 = X(:, 2);

W=[x1,x2];

indici = AtribuireCentru(W,Centre,NrCentre, m);

gscatter(x1,x2,indici);

hold on;

OldCentre = Centre;

while(Centre ~= CentreNoi)

Centre = CentreNoi;

CentreNoi = RecalculareCentru(W, NrCentre, m, indici);

indici = AtribuireCentru(W, CentreNoi, NrCentre, m);

end

figure;

gscatter(x1,x2,indici);