User Tools

Site Tools


dehau:solution_homework3

Note: 3/5

Bonne implémentation, code lisible. Vous abordez la recherche du meilleur k possible, vous donnez une piste pour étendre le k-means au grpahe sans toutefois développer …

Guy Melançon 2012/04/19 22:01


Nous allons implémenter l'algorithme du kmean sur un ensemble de points/noeuds munits de poids(weights). Des fonctions seront ajoutées pour calculer l'inertie du graphe/DataSet afin de déterminer la meilleure valeur de k parmis (1..10)

1) On peut utiliser le code ainsi :

              kmean=kMean(graph,k,[viewLayout])#k : nombre de clusters, []tableau des propriétés à tester
	kmean.firstStep()	
	kmean.secondStep()

#Ici c'est la distance euclidienne sur le viewLayout qui est utilisée #On peut mettre n'importe quelles propriétés en entrée et elles seront utilisées pour le calcul de la distance(Si elles sont de type double ou size) #Par contre il ne faut pas mettre viewLayout ET les propriétés qui ont été utilisées comme axes pour le rendu, sinon l'information est prise en compte deux fois

L'algorithme a été testé sur une gridApproximation car l'import des données de voitures faisait planter mon tulip. Voici une image du résultat avec k=10

2) Pour trouver le meilleur k, on compare l'inertie pour différentes valeurs de k et on prend la plus grande :

Quelle inertie calculez-vous ? En principe l'inertie totale reste invariante, c'est la ratio inertie inter/inertie intra qui varie.

results=list()
for i in range(1,10):
	kmean=kMean(graph,i,[viewLayout])
	kmean.firstStep()	
	kmean.secondStep()
	results.append(kmean.calculateInertie())
print results

Ce qui donne dans le cas de la gridApproximation : [8.01480474999999, 6.665532191400003, 8.976555891575003, 14.429901374506255, 12.652839498843754, 13.534848676537509, 13.753423135465635, 12.771869744368756, 13.113310768012505] Le meilleur k est donc de 4 clusters.

1)Il faudrait pour cela remplacer la fonction distance(noeud1,noeud2) par une fonction qui calcul la distance entre les deux noeuds en terme de nombre minimal d'arrêtes à traverser.

2) On pourrait utiliser par exemple le degré et changer la fonction setWeight(noeud) pour qu'elle renvoi le degré du noeud.

tp3.py
from tulip import *
 
 
def main(graph) : 
	viewBorderColor =  graph.getColorProperty("viewBorderColor")
	viewBorderWidth =  graph.getDoubleProperty("viewBorderWidth")
	viewColor =  graph.getColorProperty("viewColor")
	viewFont =  graph.getStringProperty("viewFont")
	viewFontSize =  graph.getIntegerProperty("viewFontSize")
	viewLabel =  graph.getStringProperty("viewLabel")
	viewLabelColor =  graph.getColorProperty("viewLabelColor")
	viewLabelPosition =  graph.getIntegerProperty("viewLabelPosition")
	viewLayout =  graph.getLayoutProperty("viewLayout")
	viewMetaGraph =  graph.getGraphProperty("viewMetaGraph")
	viewRotation =  graph.getDoubleProperty("viewRotation")
	viewSelection =  graph.getBooleanProperty("viewSelection")
	viewShape =  graph.getIntegerProperty("viewShape")
	viewSize =  graph.getSizeProperty("viewSize")
	viewSrcAnchorShape =  graph.getIntegerProperty("viewSrcAnchorShape")
	viewSrcAnchorSize =  graph.getSizeProperty("viewSrcAnchorSize")
	viewTexture =  graph.getStringProperty("viewTexture")
	viewTgtAnchorShape =  graph.getIntegerProperty("viewTgtAnchorShape")
	viewTgtAnchorSize =  graph.getSizeProperty("viewTgtAnchorSize")
 
 
	class Min:
		def __init__(self,defaultAttachedValue=""):
			self.attachedValue=defaultAttachedValue
			self.value=float('inf')
		def min(self,value,attachedValue):
			if(value<self.value):
				self.value=value
				self.attachedValue=attachedValue
	#/class Min/
 
	class NodeElem:
		def __init__(self,tlpNode,properties,weight):
			self.values=list()
			self.ref2tlpNode=tlpNode
			self.weight=weight
			for i in properties:
				values2Add=list()
				if(isinstance(i,tlp.LayoutProperty)):
					size=i.getNodeValue(self.ref2tlpNode)
					values2Add.append(size.getX())
					values2Add.append(size.getY())
					values2Add.append(size.getZ())
				else:
					values2Add.append(i.getNodeValue(self.ref2tlpNode))
				for j in values2Add:
					self.values.append(j)
 
 
	class kMean:
		def __init__(self,graph,k,properties,weightNodeMetric='default'):
			"""
				self.k : nombre de groupes
				self.groups : tableau de k groups(ensemble de noeuds/points)
				self.barycenters : tableau de k barycentres
				self.properties : proprietes utilisées comme "values"
 
			"""
			self.groups=[list() for i in range(k)]
			self.properties=properties
			self.weightNodeMetric=weightNodeMetric
			self.barycenters=list()
			self.colors=[tlp.Color(227,41,81),tlp.Color(227,41,168),tlp.Color(137,41,227),tlp.Color(50,41,227),tlp.Color(47,224,27),tlp.Color(208,224,27),tlp.Color(224,171,27),tlp.Color(224,40,27),tlp.Color(28,28,28),tlp.Color(153,129,127)]
			self.allNodes=list()
			self.N=graph.numberOfNodes()
			for i in graph.getNodes():
				self.allNodes.append(NodeElem(i,self.properties,self.calculateWeight(i,self.weightNodeMetric)))
			self.baryCenter=self.searchBaryCenter(self.allNodes)
			self.k=k
			self.graph=graph
 
 
 
		def calculateWeight(self,node,metric='default'):
			#pourra être étendu à des metrics de noeuds
				if(metric=='default'):
					return 1.0/self.N
				else:
					return 1.0/self.N
 
 
 
		def firstStep(self):
			for i in range(self.k):				
					self.barycenters.append(self.allNodes[i])
			self.fitNodesIntoGroups()
			self.renderView()
		def secondStep(self):
			tmp=0
			criteria=float('inf')
			while(criteria>9):
				criteria=self.searchBaryCenters()
				self.fitNodesIntoGroups()
				self.renderView()
				tmp+=1
 
		def renderView(self):
			for i in range(len(self.groups)):
				for j in self.groups[i]:
					viewColor.setNodeValue(j.ref2tlpNode,self.colors[i])
			updateVisualization()
 
		def fitNodesIntoGroups(self):
			#Réinitialise
			for i in range(self.k):
				self.groups[i]=list()
 
			#Pour chaque noeud regarder le barycentre le plus proche
			for node in self.allNodes:
				distanceMin=Min()
				for i in range(self.k):
					distanceMin.min(self.distance(node,self.barycenters[i]),i)
				self.groups[distanceMin.attachedValue].append(node)
 
 
 
 
		def distance(self,noeud1,noeud2):
			distance=0
			for w1,w2 in zip(noeud1.values,noeud2.values):
				distance+=((noeud2.weight*w2-noeud1.weight*w1)**2)
			return distance
 
 
			return retour
		def searchBaryCenter(self,group):
			distances=[0 for i in range(self.N)]
			distanceMin=Min()
			NGroup=len(group)
			#Pour chaque noeud
			for i2 in range(NGroup):
				for i3 in range(i2,NGroup):
					distance=self.distance(group[i2],group[i3])
					distances[i2]+=distance
					distances[i3]+=distance
 
				distanceMin.min(distances[i2],group[i2])
			return distanceMin.attachedValue
 
 
		def searchBaryCenters(self):
			stopCriteria=0
			for i1 in range(self.k):
				group=self.groups[i1]
				bary=self.searchBaryCenter(group)				
				stopCriteria+=self.distance(self.barycenters[i1],bary)
				self.barycenters[i1]=bary
			return stopCriteria
 
		def calculateClusterWeight(self,group):
			NGroup=len(group)
			retour=0
			#Pour chaque noeud
			for i in range(NGroup):
				retour+=group[i].weight
			return retour
 
		def calculateClusterInertie(self,groupIndice,groupWeight):
			group=self.groups[groupIndice]
			bary=self.barycenters[groupIndice]
 
			retour=0
			#Pour chaque noeud
			for i in group:
				retour+=((i.weight/groupWeight)*self.distance(i,bary))
			retour*=2
			return retour
		def calculateInertie(self):
			semisum1=0
			semisum2=0
			#pour chaque cluster
			for i in range(self.k):
				wci=self.calculateClusterWeight(self.groups[i])
				ICi=self.calculateClusterInertie(i,wci)
				dInterBary=self.distance(self.barycenters[i],self.baryCenter)
				semisum1+=(wci*ICi)
				semisum2+=(wci*(dInterBary**2))
			return semisum1+semisum2
 
 
 
 
 
 
	#Code pour trouver le meilleur k
	results=list()
	for i in range(1,10):
		kmean=kMean(graph,i,[viewLayout])
		kmean.firstStep()	
		kmean.secondStep()
		results.append(kmean.calculateInertie())
 
	print results			
 
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/dehau/solution_homework3.txt · Last modified: 2012/04/19 22:10 by melancon