algoritmi paraleli În recunoaşterea formelor_v1a

Algoritmi paraleli n

recunoaterea formelor

Cursul Metode avansate de

recunoasterea formelor

Masterat SIC, anul I

Algoritmul k - mediilor (k - means clustering)

Context nvare nesupravegheat

Intrri: N(E) i k numrul de clase

Ieire: Pk(E)

Observaie: pentru k n restul cursului se utilizeaz M. S-a

pstrat k deoarece istoric aa a fost numit algoritmul (k mediilor).

Algoritmul k - mediilor (k - means clustering)

Algoritmul k - mediilor (k - means clustering) - 1

procedura kMedii(N(E), k, Pk) este

*) se aleg aleatoriu k centroizi (gi=xi si Ci={gi} i=1,k)

*) iclas[i]=i cu i=1,k si iclas[i]=0, i=k+1,n

repet

gata = adevarat

pentru i=1,k execut

ci = gi

gij=0, pentru j=1,p

miu[i]=0

@

pentru i=1,n executa

dmin=1e+38

pentru j=1,k executa

d = dist(cj,xi)

dac d

Algoritmul k - mediilor (k - means clustering) - 2

dac jmin iclas[i] atunci gata =fals @

iclas[i] = jmin // Cjmin = Cjmin U {xj}

miu[jmin]=miu[jmin] + fi

pentru j=1,p execut

gjmin,j = gjmin,j + xij*fi

@

@ // sfarsit pentru i=1,n

pentru i=1,k execut

pentru j=1,p execut

gij = gij /miu[i]

@

@

pn cnd gata

sfrit

K-medii. Exemplu

Object weight pH

Medicine A 1 1

Medicine B 2 1

Medicine C 4 3

Medicine D 5 4

k-medii. Exemplu

gata=adevrat

g1=x1, g2=x2,

k-medii. Exemplu

g1=x1, g2=x2,

c1=g1

c2=g2,

k-medii. Exemplu

g1=x1, g2=x2,

c1=g1

c2=g2, iclas[ ]= {1,2,0,0}

k-medii. Exemplu

g1=x1, g2=x2,

c1=g1

c2=g2, iclas[ ]= {1,2,0,0}

d(x1,c1)=0

d(x1,c2)=1 => jmin=1

k-medii. Exemplu

g1=x1, g2=x2,

c1=g1

c2=g2, iclas[ ]= {1,2,0,0}

d(x1,c1)=0

d(x1,c2)=1 => jmin=1

d(x2,c1)=1

d(x2,c2)=0 => jmin=2

k-medii. Exemplu

g1=x1, g2=x2,

c1=g1

c2=g2, iclas[ ]= {1,2,0,0}

d(x1,c1)=0

d(x1,c2)=1 => jmin=1

d(x2,c1)=1

d(x2,c2)=0 => jmin=2

d(x3,c1)=3.61

d(x3,c2)=2.83 => jmin=2 , gata=fals

iclas[3]=2

k-medii. Exemplu

g1=x1, g2=x2,

c1=g1

c2=g2, iclas[ ]= {1,2,0,0}

d(x1,c1)=0

d(x1,c2)=1 => jmin=1

d(x2,c1)=1

d(x2,c2)=0 => jmin=2

d(x3,c1)=3.61


iclas[3]=2

d(x4,c1)=5


iclas[4]=2

K-medii. Exemplu

g1 = (1,1)

g2= (3.33, 2.66)

Deoarece gata=fals

Se reiau iteratiile

gata=adevrat

K-medii. Exemplu. Iteratia 2

c1=g1

c2=g2,


c1=g1

c2=g2, iclas[ ]= {1,2,2,2}


c1=g1

c2=g2, iclas[ ]= {1,2,2,2} d(x1,c1)=0

d(x1,c2)=3.14 => jmin=1


c1=g1

c2=g2, iclas[ ]= {1,2,2,2} d(x1,c1)=0

d(x1,c2)=3.14 => jmin=1

d(x2,c1)=1

d(x2,c2)=2.36 => jmin=1,gata=fals

iclas[2]=1


c1=g1

c2=g2, iclas[ ]= {1,2,2,2} d(x1,c1)=0

d(x1,c2)=3.14 => jmin=1

d(x2,c1)=1

d(x2,c2)=2.36 => jmin=1,

gata=fals

iclas[2]=1

d(x3,c1)=3.61

d(x3,c2)=0.47 => jmin=2


c1=g1

c2=g2, iclas[ ]= {1,2,2,2} d(x1,c1)=0

d(x1,c2)=3.14 => jmin=1

d(x2,c1)=1

d(x2,c2)=2.36 => jmin=1, gata=fals

iclas[2]=1

d(x3,c1)=3.61

d(x3,c2)=0.47 => jmin=2

d(x4,c1)=5

d(x4,c2)=1.89 => jmin=2


g1 = (1.5, 1)

g2 = (4.5, 3.5)

Deoarece gata=fals

Se reiau iteratiile

gata=adevrat


c1=g1

c2=g2,


c1=g1

c2=g2, iclas[ ]= {1,1,2,2}


c1=g1

c2=g2, iclas[ ]= {1,1,2,2} d(x1,c1)=0.5

d(x1,c2)=4.3 => jmin=1


c1=g1

c2=g2, iclas[ ]= {1,1,2,2} d(x1,c1)=0.5

d(x1,c2)=4.3 => jmin=1

d(x2,c1)=0.5

d(x2,c2)=3.54 => jmin=1


c1=g1

c2=g2, iclas[ ]= {1,1,2,2} d(x1,c1)=0.5

d(x1,c2)=4.3 => jmin=1

d(x2,c1)=0.5

d(x2,c2)=3.54 => jmin=1

d(x3,c1)=3.2

d(x3,c2)=0.71 => jmin=2


c1=g1

c2=g2, iclas[ ]= {1,1,2,2} d(x1,c1)=0.5

d(x1,c2)=4.3 => jmin=1

d(x2,c1)=0.5

d(x2,c2)=3.54 => jmin=1

d(x3,c1)=3.2

d(x3,c2)=0.71 => jmin=2

d(x4,c1)=4.61

d(x4,c2)=0.71 => jmin=2


Deoarece gata=adevarat

ciclul repet se oprete

REZULTAT: P2(E)= {C1 , C2}

iclas[ ]= {1,1,2,2}

C1={x1,x2},

C2={x3,x4}

Exemplul numeric, partea grafic au fost preluate de

pe pag. http://people.revoledu.com/kardi/tutorial/kMean/NumericalExample.htm si adaptate la algoritmul prezentat in pseudocod anterior.

k-means. Exemplul 2

k-means. Exemplul 2

Manasi N. Joshi, Parallel K - Means Algorithm on Distributed Memory Multiprocessors Spring 2003, Computer Science Department, University of Minnesota

Paralelizarea algoritmului de k-medii

Caracteristic pentru Algoritmul K-mediilor: paralelismul intrinsec

Efortul masiv de calcul: determinarea la fiecare iteratie a nxk distante dintre n forme si k centroizi

Ideea: impartirea sarcinilor de calcul pe mai multe procesoare

Observatie: exista comunicatie de date intre procesoare si Tcomunicatie >> Tcalcul

Pentru o eficienta mai mare este necesara minimizarea comunicatiei

Calculul paralel Procesul root

initializeaza lista celor k centroizi si apoi ii va transmite la celelalte procese

Fiecare proces care nu este root

primeste o parte din cele n forme (n/nproces) pe care le

memoreaza local

la fiecare iteratie va determina apartenenta lor la cele k clase pe

baza distantei minime fata de centroizi

pentru formele stocate calculeaza pentru i=1,k

miu_partial[i] = fj g_partial[i] = fj * xj daca iclasa[j] = i transmite catre procesul root valoarea variabilei locale gata si

tablourile miu_partial[i] si g_partial[i]

Calculul paralel Procesul root Verifica daca nu a fost primit vreun gata=fals de la celelalte procese Pe baza tablourilor miu_partial[i] si g_partial[i] primite calculeaza

pentru i=1,k nprocese

miu[i] = miu_partial[j] j=1

nprocese

g[i] = 1/ miu[i] g_partial[j] j=1

Transmite noii centroizi g[i] catre celelalt procese initiind o noua iteratie.

Daca s-a primit doar gata=adevarat de la toate celelalte procese, atunci cere de la procese iclasa_partial[] si reconstituie iclasa[i], i=1,n

Implementarea calculului paralel

Modelul Single Program Multiple Data (SPMD)

Se utilizeaz Message Passing Interface (MPI) pentru a programa calculul distribuit pe mai multe noduri de calcul

Resursa MPI: http://www.mcs.anl.gov/research/projects/mpich2/index.php

http://software.intel.com/en-us/intel-mpi-library/ - 30 zile evaluare

algoritmi paraleli În recunoaşterea formelor_v1a

Documents