Klaszterezés

A klaszterezés egy olyan eljárás, mellyel adatokat tudunk csoportosítani valamilyen hasonlóság alapján. Ezeket a csoportokat klasztereknek nevezzük. 

Először a statisztikában kezdtek foglalkozni vele, majd az adatbányászatban került előtérbe keretében nagy méretű adathalmazok klaszterezése. Így a klaszterezés az adatbányászat egyik legrégebbi és talán leggyakrabban alkalmazott része.

A klaszterezés során az adatpontokat diszjunkt csoportokba, klaszterekbe soroljuk. Célja, hogy az elemeknek egy olyan partícióját adjuk meg, melyben a közös csoportban lévő elempárok hasonlóbbak egymáshoz, mint azok az elempárok, amelyek különböző csoportba kerültek.

Klaszterezés során a megfelelõ csoportok kialakítása nem egyértelmű feladat, hiszen a különböző adatok eltérő jelentése és felhasználása miatt adathalmazonként más és más szempontok szerint kell csoportosítanunk. További nehézséget jelent, hogy egy n darab adatpontot tartalmazó adathalmaznak Bell-számnyi, O((e^(n lg n))) darab klaszterezése lehet.

Az olyan adatpontokat, amelyek lényegesen különböznek szinte minden más adatponttól, kívülállóknak nevezzük. Megjelenésük lehet mérési hiba, zaj következménye, de ha pontosak az adatok, akkor fontos információ. Mindkét esetben célszerű elhagyni a kívülálló pontokat.

Algoritmusok:
Particionáló klaszterező algoritmus: 
Az elemek egy tetszőleges klaszterezéséből indul ki, és minden lépésben az előző klasztert pontosítja. Akkor ér véget, ha már nem változik az eredményül kapott klaszter. A kiindulási partíció meghatározza a klaszterek számát, ami az eljárás során nem változik.
Hierarchikus algoritmusok:
A hierarchikus klaszterezés lehet felhalmozó és lebontó. A felhalmozó eljárás először minden egyes elemet külön klaszternek tekint és összekapcsolja őket egyre nagyobb klaszterekbe. Így a végén egyetlen, az összes elemet tartalmazó klasztert kapunk. A lebontó algoritmus ezzel szemben először az egész adattömböt egyetlen klaszternek tekinti és egyre kisebb klaszterekre osztja, míg a végén minden elem külön klasztert képez. Az eredményt általában fa formájában szokták ábrázolni. Az adatpontok a fa leveleiben találhatók. A fa minden belső pontja egy klaszternek felel meg, amely azokat a pontokat tartalmazza, melyek a fában alatta találhatók. A gyökér az összes adatpontot tartalmazza. A felhalmozó algoritmus a fa tetején kezdi az elemzést, a lebontó pedig a gyökereknél.

Alkalmazási területei:
	Társadalomtudomány: szociális hálózatok elemzése
	Marketing: vevők csoportosítása vásárlási szokásaik szerint
	Biológia: növény- és állatközösségek csoportosítására
	Orvostudomány: betegségek csoportosítása tüneteik szerint, képalkotás (PET)
	Várostervezés: csoportosíthatjuk az ingatlanokat típus, érték és geológiai elhelyezkedésük alapján
	Informatika: weboldalak csoportosítása látogatók szerint, mintázat-felismerés
	
Gráfok klaszterezése: egy klaszteren belül sok él fut, a különböző klaszterek között viszont kevés. A legkisebb klaszter, klaszterek kitörlésével a kívülállókat hagyjuk el.

1 sajátvektorral

SetDirectory[NotebookDirectory[]];
ClearAll[program];
program[s_String]:= Module[{adj,m,dd,skalazott,ddd,cc},
adj=Import[s,"AdjacencyMatrix"];
m=(adj/(Total[adj,2]));
dd=DiagonalMatrix[1/(Sqrt[m.ConstantArray[1.,Import[s,"VertexCount"]]])];
skalazott=dd.m.dd;
ddd=dd.Eigenvectors[skalazott][[2]];
cc=ClusteringComponents[ddd,2];
GraphPlot[AdjacencyGraph[adj],VertexRenderingFunction->({If[cc[[#2]]==1,Red,Blue],EdgeForm[Black],Disk[#,.15]}&),ImageSize->800]]

program["karate.gml"]

program["dolphins.gml"]

2 sajátvektorral

SetDirectory[NotebookDirectory[]];
ClearAll[program2];
program2[s_String]:= Module[{adj,m,dd,skalazott,ddd2,ddd3,t,ddd,cc,v},
adj=Import[s,"AdjacencyMatrix"];
v=Import[s,"VertexCount"];
m=(adj/(Total[adj,2]));
dd=DiagonalMatrix[1/(Sqrt[m.ConstantArray[1.,v]])];
skalazott=dd.m.dd;
t=Table[ {Eigenvectors[skalazott][[2]][[i]] , Eigenvectors[skalazott][[3]][[i]]},{i,v}];
ddd=dd.t;
cc=ClusteringComponents[ddd,3,1];
GraphPlot[AdjacencyGraph[adj],VertexRenderingFunction->({If[cc[[#2]]==1,Green,If[cc[[#3]]==2,Blue,Red]],EdgeForm[Black],Disk[#,.15]}&),ImageSize->800]]

program2["karate.gml"]

program2["dolphins.gml"]

k sajátvektorral

SetDirectory[NotebookDirectory[]];
ClearAll[programk];
programk[s_String, k_Integer]:= Module[{adj,m,dd,skalazott,ddd2,ddd3,t,ddd,cc,v},
adj=Import[s,"AdjacencyMatrix"];
v=Import[s,"VertexCount"];
m=(adj/(Total[adj,2]));
dd=DiagonalMatrix[1/(Sqrt[m.ConstantArray[1.,v]])];
skalazott=dd.m.dd;
t=Table[Flatten[Take [Table[Eigenvectors[skalazott][[i]],{i,2,k+1}],All, {j,j}]],{j,v}];
ddd=dd.t;
cc=ClusteringComponents[ddd,k+1,1];
GraphPlot[AdjacencyGraph[adj],VertexRenderingFunction->({Hue[cc[[#2]]/(k+1)],EdgeForm[Black],Disk[#,.15]}&),ImageSize->800]]

programk["karate.gml",5]

programk["dolphins.gml",5]

Manipulate[programk["karate.gml", x],{x,Range[33]}]

Manipulate[programk["dolphins.gml", x],{x,Range[10]}]

SetDirectory[NotebookDirectory[]];
ClearAll[pfok];
pfok[s_String, k_Integer]:= Module[{adj,m,dd,skalazott,ddd2,ddd3,t,ddd,cc,v},
adj=Import[s,"AdjacencyMatrix"];
v=Import[s,"VertexCount"];
m=(adj/(Total[adj,2]));
dd=DiagonalMatrix[1/(Sqrt[m.ConstantArray[1.,v]])];
skalazott=dd.m.dd;
t=Table[Flatten[Take [Table[Eigenvectors[skalazott][[i]],{i,2,k+1}],All, {j,j}]],{j,v}];
ddd=dd.t;
cc=ClusteringComponents[ddd,k+1,1];
GraphPlot[AdjacencyGraph[adj],VertexRenderingFunction->({Hue[cc[[#2]]/(k+1)],EdgeForm[Black],Disk[#,0.1Sqrt[Total[adj][[#2]]]], Text[Style[#2,Black,20], #]}&),ImageSize->800]]

pfok["karate.gml",2]

pfok["dolphins.gml",2]

Ellenőrzés

program, program2 a programk-beli színezéssel

SetDirectory[NotebookDirectory[]];
ClearAll[s1];
s1[s_String]:= Module[{adj,m,dd,skalazott,ddd,cc},
adj=Import[s,"AdjacencyMatrix"];
m=(adj/(Total[adj,2]));
dd=DiagonalMatrix[1/(Sqrt[m.ConstantArray[1.,Import[s,"VertexCount"]]])];
skalazott=dd.m.dd;
ddd=dd.Eigenvectors[skalazott][[2]];
cc=ClusteringComponents[ddd,2];
GraphPlot[AdjacencyGraph[adj],VertexRenderingFunction->({Hue[cc[[#2]]/2],EdgeForm[Black],Disk[#,.15]}&),ImageSize->800]]

SetDirectory[NotebookDirectory[]];
ClearAll[s2];
s2[s_String]:= Module[{adj,m,dd,skalazott,ddd2,ddd3,t,ddd,cc,v},
adj=Import[s,"AdjacencyMatrix"];
v=Import[s,"VertexCount"];
m=(adj/(Total[adj,2]));
dd=DiagonalMatrix[1/(Sqrt[m.ConstantArray[1.,v]])];
skalazott=dd.m.dd;
t=Table[ {Eigenvectors[skalazott][[2]][[i]] , Eigenvectors[skalazott][[3]][[i]]},{i,v}];
ddd=dd.t;
cc=ClusteringComponents[ddd,3,1];
GraphPlot[AdjacencyGraph[adj],VertexRenderingFunction->({Hue[cc[[#2]]/3],EdgeForm[Black],Disk[#,.15]}&),ImageSize->800]]

programk["karate.gml",1]== s1["karate.gml"]

programk["karate.gml",2]== s2["karate.gml"]

Legkisebb klaszter törlése

SetDirectory[NotebookDirectory[]];
ClearAll[p];
p[s_String, k_Integer]:= Module[{adj,m,dd,skalazott,ddd2,ddd3,t,ddd,cc,v},
adj=Import[s,"AdjacencyMatrix"];
v=Import[s,"VertexCount"];
m=(adj/(Total[adj,2]));
dd=DiagonalMatrix[1/(Sqrt[m.ConstantArray[1.,v]])];
skalazott=dd.m.dd;
t=Table[Flatten[Take [Table[Eigenvectors[skalazott][[i]],{i,2,k+1}],All, {j,j}]],{j,v}];
ddd=dd.t;
cc=ClusteringComponents[ddd,k+1,1]]

SetDirectory[NotebookDirectory[]];
ClearAll[tr];
tr[s_String, k_Integer]:= Module[{adj,m,dd,skalazott,t,ddd,cc,v,e,l,r,q,adj2,a,cc2},
adj=Import[s,"AdjacencyMatrix"];
v=Import[s,"VertexCount"];
cc=p[s, k];

e=Table[Count[cc,j],{j,k+1}];
r=Flatten[Position[cc,Flatten[Position[e,Min[e]]][[1]]]];(*azok a helyek,amiket törölni kell *)
f=Reverse[r] ;
a=Last[Table[adj=Drop[adj,{f[[i]]}],{i,Length[f]}]];  (*sorok törlése*)
adj2=Table[Last[Table[a[[j]]=Drop[a[[j]],{f[[i]]}],{i,Length[f]}]],{j,Length[a]}];(*oszlopok törlése-új szomszédossági mátrix *)
cc2=Last[Table[cc=Drop[cc,{f[[i]]}],{i,Length[f]}]]; (*csúcsok régi színei*)

GraphPlot[AdjacencyGraph[adj2],VertexRenderingFunction->({Hue[cc2[[#2]]/(k+1)],EdgeForm[Black],Disk[#,.15]}&),ImageSize->800]]

tr["karate.gml",4]

Ellenőrzés:

Grid[{{programk["karate.gml",4],tr["karate.gml",4]}},Frame->All]

x legkisebb klaszter törlése

SetDirectory[NotebookDirectory[]];
ClearAll[xtr];
xtr[s_String, k_Integer, x_Integer]:= Module[{adj,m,dd,skalazott,t,ddd,cc,v,e,l,r,q,adj2,a,cc2},
adj=Import[s,"AdjacencyMatrix"];
v=Import[s,"VertexCount"];
cc=p[s, k];

e=Table[Count[cc,j],{j,k+1}];
r=Sort[Flatten[Table[Position[cc,Flatten[Table[Position[e,RankedMin[e,i]],{i,x}]][[j]]],{j,x}]]];(*azok a      helyek, amiket törölni kell *)
f=Reverse[r] ;
a=Last[Table[adj=Drop[adj,{f[[i]]}],{i,Length[f]}]];  (*sorok törlése*)
adj2=Table[Last[Table[a[[j]]=Drop[a[[j]],{f[[i]]}],{i,Length[f]}]],{j,Length[a]}];(*oszlopok törlése-új szomszédossági mátrix *)
cc2=Last[Table[cc=Drop[cc,{f[[i]]}],{i,Length[f]}]]; (*csúcsok régi színei*)

GraphPlot[AdjacencyGraph[adj2],VertexRenderingFunction->({Hue[cc2[[#2]]/(k+1)],EdgeForm[Black],Disk[#,.15]}&),ImageSize->800]]

xtr["karate.gml",4,2]

Ellenőrzés:

xtr["karate.gml",4,1]== tr["karate.gml",4]

Grid[{{programk["karate.gml",4],xtr["karate.gml",4,2]}},Frame->All]

Felhasznált irodalom:

www.sztaki.hu/~alukacs/Papers/klaszterezes.pdf

http://hu.wikipedia.org/wiki/Klaszter-analízis

http://home.dei.polimi.it/matteucc/Clustering/tutorial_html