Algoritmi Paraleli În Recunoaşterea Formelor_v1a
-
Upload
georgeanton -
Category
Documents
-
view
30 -
download
2
description
Transcript of 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
d(x3,c2)=2.83 => jmin=2 , gata=fals
iclas[3]=2
d(x4,c1)=5
d(x4,c2)=4.24 => jmin=2 , gata=fals
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,
-
K-medii. Exemplu. Iteratia 2
c1=g1
c2=g2, iclas[ ]= {1,2,2,2}
-
K-medii. Exemplu. Iteratia 2
c1=g1
c2=g2, iclas[ ]= {1,2,2,2} d(x1,c1)=0
d(x1,c2)=3.14 => jmin=1
-
K-medii. Exemplu. Iteratia 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
-
K-medii. Exemplu. Iteratia 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
-
K-medii. Exemplu. Iteratia 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
-
K-medii. Exemplu. Iteratia 2
g1 = (1.5, 1)
g2 = (4.5, 3.5)
Deoarece gata=fals
Se reiau iteratiile
gata=adevrat
-
K-medii. Exemplu. Iteratia 3
c1=g1
c2=g2,
-
K-medii. Exemplu. Iteratia 3
c1=g1
c2=g2, iclas[ ]= {1,1,2,2}
-
K-medii. Exemplu. Iteratia 3
c1=g1
c2=g2, iclas[ ]= {1,1,2,2} d(x1,c1)=0.5
d(x1,c2)=4.3 => jmin=1
-
K-medii. Exemplu. Iteratia 3
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
-
K-medii. Exemplu. Iteratia 3
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
-
K-medii. Exemplu. Iteratia 3
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
-
K-medii. Exemplu. Iteratia 3
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
-
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