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. 

Alkalmazási területei:
	biológia: növény- és állatközösségek csoportosítására
	orvostudomány: képalkotás (PET)
	társadalomtudomány: szociális hálózatok elemzése, piackutatás (fogyasztók csoportosítása)
	informatika: mintázat-felismerés
	
Gráfok klaszterezése: egy klaszteren belül sok él fut, a csoportok között kevés.

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[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];
GraphPlot[AdjacencyGraph[adj],VertexRenderingFunction->({Hue[cc[[#2]]/(k+1)],EdgeForm[Black],Disk[ #,Total[adj][[#2]]/(1.5v)], Text[Style[#2,Black,20], #]}&),ImageSize->800]]

p["karate.gml",2]

p["dolphins.gml",2]

Ellenőrzés

program2, program3 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"]