User Tools

Site Tools


el_hilali_sami:solution_homework2

Correction

Critères & points attribués (/10)
Rappel du contexte 9
Résultats 9
Qualité du code (commentaires, structures utilisées, …) 9
Animation et visualisation 8
Explication en dehors du code 8
Total (/50) 43

B.P. : Très bien !!

Compte-rendu

Application de l'algorithme CURE aux données 04cars_data.csv


Implémentation


Ce projet a été effectué en binôme avec Maeva Veyssiere.

L'implémentation de l'algorithme de Cure réalisée, permet de clusteriser des données en fonction de deux paramètres. Le critère de rapprochement de deux clusters est la distance euclidienne entre leurs points représentatifs. Deux structures de données ont dues être implémentées. Une liste contenant tous les clusters ordonnées en ordre croissant de distance avec le cluster le plus proche. Un kd-tree organisant les points représentatifs de tous les clusters (il permet de limiter le nombre de comparaisons faites pour obtenir le représentant le plus proche). L'implémentation du KD-tree s'est appuyée sur la publication scientifique “An algorithm for Finding best Matches in Logarithmic expected Time” de J.H.Friedman, J.L.Bentley, R.A.Finkel.

Cet algorithme a été utilisé afin d'étudier les données de 04cars_data en fonction des paramètres : prix de la voiture (Price_Retail) et autonomie en ville (City_MPG). Pour cet exemple, la procédure de clustering donnant le résultat le plus cohérent (clusters bien distincts et peu d'outlayers) prenait en paramètre c=10 (nombre de représentants par cluster) et k=10 (nombre de clusters attendus).

Visualisation du processus de clusterisation


Pour observer la phase de construction des clusters, ceux-ci sont initialement alignés aléatoirement sur un axe horizontal [figure 1A]. Lorsqu'un cluster u fusionne avec son cluster le plus proche v, v est positionné sur le même axe vertical que u [figure 1B]. Le résultat obtenu à la fin de l'execution du script est présenté figure 1C.



Analyse du résultat


Afin d'analyser le contenu des clusters obtenus, une autre représentation a été retenue, un scatter plot. Celui ci prend en compte les deux dimensions utilisées pour la clusterisation, soit « City_MPG » sur la première dimension (en abscisse) et « Price_Retail » sur la seconde (en ordonnée). Le processus est maintenant observé grâce à la couleur des clusters. En effet, lorsque les clusters u et v fusionnent, la couleur de u est affectée à v.


Cette clusterisation permet d'identifier des gammes de véhicules sur la base du rapport entre le prix de vente et l'autonomie en ville. La majorité des voitures sont classées dans deux classes pour lesquels le prix varie entre 1028 et 6000 mais qui sont différentiables par leur autonomie. La classe de droite (rose) consommant moins que la classe de gauche (bleu foncé). Trois autres classes peuvent être différenciées selon le critère de l'autonomie. Des voitures de très faible prix permettant de faire entre 30 et 38 kilomètres avec un litre de carburant (violet foncé), une voiture dans le même ordre de prix mais pouvant faire 10 kilomètres de plus et enfin deux voitures, en bas à droite, peu chères qui ont la plus grande autonomie de toutes les voitures. Ces deux dernières (bleu ciel) ont été identifiées comme étant des voitures hybrides. Un véhicule de la marque Porsche est le véhicule le plus cher de la population et un véhicule de la marque Hummer est le véhicule ayant la plus petite autonomie soit la plus grosse consommation de carburant.

Code

Cure_Veyssiere_EL_HILALI.py
######################################################
######### VEYSSIERE Maeva, EL HILALI Sami ############
######################################################
from tulip import *
import numpy as np
import math
import random
import copy

###################Declaration des objets:	
class Cluster :
	def __init__(self,point=None):	
		if point :
			self.points=[point]
			self.mean=point
			self.rep=[]
			self.closest=None
		else :
			self.points=[]
			self.mean1=None
			self.mean2=None
			self.rep=[]
			self.closest=None
			self.dist_closest=None	
	#pour ajouter tous les points de u et v
	def setCluster(self,listPoint):
		for i in listPoint :
			self.points.append(i)
	
class Rep :
	def __init__(self,point,cluster):
		self.point=point
		self.parametre1=0
		self.parametre2=0
		self.filsgauche=None
		self.filsdroit=None
		self.pere=None
		self.depth=None
		self.cluster=cluster
	
#########################################
def normalisation(colonne):
	paramN=[]
	param=[]
	for n in graph.getNodes():
		param.append(colonne[n])
	std=np.std(param)	
 	mean=np.mean(param)
 	for n in graph.getNodes():
 		paramN.append((colonne[n]-mean)/std)
 	return paramN
 	
############################## Methodes de calcul des distance:
def distance_representants(rep1,rep2):
	d=abs(math.sqrt(((rep1.parametre1-rep2.parametre1)**2)+((rep1.parametre2-rep2.parametre2)**2)))
	return d
	
#renvoie la distance minimum entre le point observe et les points du cluster etudie
def distance(u,v):
	#calcul de la distance entre les cluster u et v qui est la distance minimum entre 1 des representants de chaque cluster
	distance_clusters=1000000
	for point1 in u.rep:		
		for point2 in v.rep:
			distance_points=distance_representants(point1,point2)		
		if distance_points<distance_clusters:
			distance_clusters=distance_points
	return distance_clusters

#cherche le point moyen : le plus proche du point theorique
def distance2(point,param1,param2,liste):
	pMean=0
	distance_clusters=10000	
	for p in liste:
		distance_points=abs(math.sqrt(((param1[point]-param1[p])**2)+((param2[point]-param2[p])**2)))
		if distance_points<distance_clusters:
			distance_clusters=distance_points
			pMean=p
	return pMean
	
def minDist(cluster,cluster2,param1,param2,clusterF,dRef):
	if cluster.mean!=cluster2.mean:
		d=abs(math.sqrt(((param1[cluster.mean]-param1[cluster2.mean])**2)+((param2[cluster.mean]-param2[cluster2.mean])**2)))
		if d < dRef :
			clusterF=cluster2
			dRef=d
	return [dRef,clusterF]
	
############################################ Definition de HEAP:
def build_heap(listeCluster,param1,param2,Q):
	clusterF=None #cluster le plus proche de celui etudie
	dF=0#distance entre les deux clusters
	
	for cluster in listeCluster:
		dRef=1000000 #distance a laquelle est comparee la distance calculee
		for cluster2 in listeCluster:
			if cluster2!=cluster:
				[dRef,clusterF]=minDist(cluster,cluster2,param1,param2,clusterF,dRef)
				cluster.closest=clusterF
				cluster.dist_closest=dRef
		Q.append([dRef,cluster])
	
	for i in range(len(Q)):
		for j in range((i+1),len(Q)):
			if Q[i][0]>Q[j][0]:
				item=Q.pop(j)
				Q.insert(i,item)
		
	for i in range(len(Q)):
		item=Q.pop(i)
		clust=item.pop(1)
		Q.insert(i,clust)

############################################ Definition du KDTREE:	
def tri_a_bulles_kdtree(S,variable):
	liste=S
	for i in range(len(S)):
		rep1=liste[i]
		for j in range((i+1),len(S)):
			rep2=liste[j]
			if variable=='param1':
				if (rep1.parametre1>rep2.parametre1):
					rep_tri=liste.pop(j)
					liste.insert(i,rep_tri)
			if variable=='param2':
				if (rep1.parametre2>rep2.parametre2):
					rep_tri=liste.pop(j)
					liste.insert(i,rep_tri)
	return liste

def extract_mediane(liste):
	indice=len(liste)//2
	return indice,liste.pop(indice)

def build_kdtree(liste,depth):
	liste=tri_a_bulles_kdtree(liste,'param1')
	indice,racine=extract_mediane(liste)
	racine.depth=depth
	racine.pere=None
	racine.filsgauche=build(racine,liste[:indice],depth+1)
	racine.filsdroit=build(racine,liste[indice:],depth+1)
	return racine
	
def build(pere,liste,depth):
	if len(liste)>=1:
		if depth%2==0:
			liste=tri_a_bulles_kdtree(liste,'param1')
		else:
			liste=tri_a_bulles_kdtree(liste,'param2')
		indice,racine=extract_mediane(liste)
		racine.depth=depth
		racine.pere=pere
		racine.filsgauche=build(racine,liste[:indice],depth+1)
		racine.filsdroit=build(racine,liste[indice:],depth+1)
		return racine

#################################################### Operations sur KDTREE
#################suppression
def parcours_recursif_suppression(rep,liste):
	if rep!=None:
		liste.append(rep)
		parcours_recursif_suppression(rep.filsgauche,liste)
		parcours_recursif_suppression(rep.filsdroit,liste)

def initialisation_suppression_kdtree(rep,racine,T):
	liste=[]
	parcours_recursif_suppression(rep,liste)
	liste.pop(0)
	aux=rep.pere
	#si rep est une feuille
	if len(liste)==0:
		if aux.filsgauche==rep:
			aux.filsgauche=None
		else:
			aux.filsdroit=None
		T.remove(rep)
		return racine,T
	#sinon
	else:
		if rep.depth%2==0:
			liste=tri_a_bulles_kdtree(liste,'param1')
		else:
			liste=tri_a_bulles_kdtree(liste,'param2')
		indice,racine_sous_arbre=extract_mediane(liste)
		racine_sous_arbre.depth=rep.depth
		racine_sous_arbre.filsgauche=build(racine_sous_arbre,liste[:indice],racine_sous_arbre.depth+1)
		racine_sous_arbre.filsdroit=build(racine_sous_arbre,liste[indice:],racine_sous_arbre.depth+1)
		
		#sous arbre construit, on le branche maintenant au reste de l'arbre
		#si rep n'est pas la racine de l'arbre	
		if aux!=None:
			#alors la racine de T a pas change
			if aux.filsgauche==rep:
				aux.filsgauche=racine_sous_arbre
			else:
				aux.filsdroit=racine_sous_arbre
			racine_sous_arbre.pere=aux
			T.remove(rep)
			return racine,T
		#sinon
		else:
			#alors la nouvelle racine est la racine du sous arbre
			racine_sous_arbre.pere=None
			T.remove(racine_sous_arbre)
			return racine_sous_arbre,T

def delete_rep(racine_kd,T,u):
	for rep in u.rep:
		racine_kd,T=initialisation_suppression_kdtree(rep,racine_kd,T)
	return racine_kd,T
#################### neirest neighbour:	
def bounds_overlap_ball(noeud_explore,closest,current_node):
	distance_frontiere=distance_representants(noeud_explore,current_node)
	rayon_cercle=distance_representants(noeud_explore,closest)
	if distance_frontiere<rayon_cercle:
		return True
	else:
		return False

def closest_rep(noeud_explore,closest,node,depth):		
	if (node in noeud_explore.cluster.rep)==False and (distance_representants(noeud_explore,node)<=distance_representants(noeud_explore,closest))and noeud_explore!=node:
		closest=node
	if depth%2==0:
		if noeud_explore.parametre1<node.parametre1:
			if node.filsgauche!=None:
				closest=closest_rep(noeud_explore,closest,node.filsgauche,depth+1)
			if node.filsdroit!=None:
				if bounds_overlap_ball(noeud_explore,closest,node.filsdroit):
					closest=closest_rep(noeud_explore,closest,node.filsdroit,depth+1)
		else:
			if node.filsdroit!=None:
				closest=closest_rep(noeud_explore,closest,node.filsdroit,depth+1)
			if node.filsgauche!=None:
				if bounds_overlap_ball(noeud_explore,closest,node.filsgauche):
					#si la distance entre noeud_explore et closest > distance entre noeud_explore et node.filsgauche
					#on explore les feuilles de node.filsgauche
					closest=closest_rep(noeud_explore,closest,node.filsgauche,depth+1)
	else:
		if noeud_explore.parametre2<node.parametre2:
			if node.filsgauche!=None:
				closest=closest_rep(noeud_explore,closest,node.filsgauche,depth+1)
			if node.filsdroit!=None:
				if bounds_overlap_ball(noeud_explore,closest,node.filsdroit):
					closest=closest_rep(noeud_explore,closest,node.filsdroit,depth+1)
		else:
			if node.filsdroit!=None:
				closest=closest_rep(noeud_explore,closest,node.filsdroit,depth+1)
			if node.filsgauche!=None:
				if bounds_overlap_ball(noeud_explore,closest,node.filsgauche):
					closest=closest_rep(noeud_explore,closest,node.filsgauche,depth+1)
	return closest
			
def search_closest(cluster,racine_kd,w):
	closest=None
	dist=1000000
	for p in cluster.rep:
		p1=closest_rep(p,w.rep[0],racine_kd,0)
		d=distance_representants(p,p1)
		if dist>=d:
			closest=p1.cluster
			dist=d
	return closest

#######################insertion
def insertion_kdtree(rep,racine,liste):
	depth=0
	#si l'arbre est vide
	aux=racine
	aux_pere=aux

	while(aux!=None):
		if depth%2==0:
			if aux.parametre1>rep.parametre1:
				aux_pere=aux
				aux=aux.filsgauche
			else:
				aux_pere=aux
				aux=aux.filsdroit
		else:
			if aux.parametre2>rep.parametre2:
				aux_pere=aux
				aux=aux.filsgauche
			else:
				aux_pere=aux
				aux=aux.filsdroit
		depth+=1

	if depth%2==0:
		if aux_pere.parametre1>rep.parametre1:
			aux_pere.filsgauche=rep
		else:
			aux_pere.filsdroit=rep
	else:
		if aux_pere.parametre2>rep.parametre2:
			aux_pere.filsgauche=rep
		else:
			aux_pere.filsdroit=rep
	rep.depth=aux_pere.depth+1
	rep.pere=aux_pere
	liste.append(rep)
	
def insert_rep(racine_kd,T,w):
	for rep in w.rep:
		insertion_kdtree(rep,racine_kd,T)
		rep.cluster=w


########Calcul de mean
def mean(cluster,param1,param2): 
	# calcul des coordonnes du point mean ideal
	sum1 = 0
	sum2 = 0
	for point in cluster.points :
	 	sum1 = sum1+param1[point]
	 	sum2 = sum2+param2[point]
	mean1 = sum1/len(cluster.points)
	mean2 = sum2/len(cluster.points)
	return [mean1,mean2]	
	
################################################## Fonction sur heap
#insertion d'un cluster dans le heap
def insert(heap,cluster,d):
	cluster.dist_closest=d
	i=0
	while (heap[i].dist_closest<d) and (i<len(heap)-1):
		i=i+1
	heap.insert(i,cluster)
	
#change la position du cluster en fonction de sa distance avec le cluster le plus proche
def relocate(heap,cluster):
	d=distance(cluster,cluster.closest)
	cluster.dist_closest=d
	heap.remove(cluster)
	insert(heap,cluster,d)	
	
def delete(heap,v):
	for item in heap :
		if item[1]==v :
			heap.remove(item)
			

#########" Methodes d'affichage
# Mouvement des cluster
def clustering(lPoints, point, viewLayout, viewColor,i):
	#x =viewLayout[lPoints[len(lPoints)-1]][0]
	#y =viewLayout[lPoints[len(lPoints)-1]][1]
	#viewLayout[point]=tlp.Coord(x,y+(20*i),0)
	viewColor[point]=viewColor[lPoints[len(lPoints)-1]]

####################################### Fonction pour associer deux clusters
def merge(u,v,c,param1,param2,viewLayout,viewColor):
	w=Cluster() #creation du nouveau cluster
	w.setCluster(u.points)
	w.setCluster(v.points)
	[w.mean1,w.mean2]=mean(w,param1,param2)
	tmpSet=[]
	maxPoint=None
	for i in range(c) :
		maxDist=0
		if i<len(w.points):
			for point in w.points :
				if (point in tmpSet)==False:
					if i==0:
						minDist=math.sqrt(((param1[point]-w.mean1)**2)+((param2[point]-w.mean2)**2))
					else :
						minDist=distance2(point,param1,param2,tmpSet)
					if minDist>=maxDist:
						maxDist=minDist
						maxPoint=point
			tmpSet.append(maxPoint)
	
	for i in tmpSet:
		maxrep=Rep(i,w)
		maxrep.parametre1=param1[i]
		maxrep.parametre2=param2[i]
		w.rep.append(maxrep)	
	
	i=1	
	for point in v.points:
		lPoints=u.points
		clustering(lPoints, point, viewLayout, viewColor,i)
		i+=1
		updateVisualization(centerViews=False)
	return w
	
#################################################### Fonction pour trier dans les clusters
def CURE(listeCluster,listeRep,param1,param2,k,viewLayout,viewColor):
	c = 10
	Q=[]
	T=listeRep
	build_heap(listeCluster,param1,param2,Q)
	racine_kd=build_kdtree(T,0)
	while len(Q)>k :
		u = Q.pop(0) #extrait la tete de Q
		v = u.closest #recupere le cluster le plus proche
		Q.remove(v) #supprime v du heap	
		w=merge(u,v,c,param1,param2,viewLayout,viewColor) #cree un nouveau cluster compose de u et v
		racine_kd,T=delete_rep(racine_kd,T,u)
		racine_kd,T=delete_rep(racine_kd,T,v)
		w.closest=Q[0] #defini un cluster du heap (choisi au hasard) comme etant le plus proche de w
		copie = copy.copy(Q)
		for cluster in copie :
			distW_cluster=distance(w,cluster)
			distW_closest=distance(w,w.closest)
			distC_closest=distance(cluster,cluster.closest)
			if distW_cluster<distW_closest: 
				w.closest=cluster				
			if (cluster.closest==u) or (cluster.closest==v):
				if distC_closest<distW_cluster:
					cluster.closest = search_closest(cluster,racine_kd,w)	
				else :
					cluster.closest = w
				relocate(Q,cluster)
					
			elif distC_closest>distW_cluster :
				cluster.closest=w
				relocate(Q,cluster)
		insert_rep(racine_kd,T,w)
		distW_closest=distance(w,w.closest)
		insert(Q,w,distW_closest)
			 
	return Q
	
#####################################
############################### MAIN:
#####################################
def main(graph): 
	AWD =  graph.getIntegerProperty("AWD")
	City_MPG =  graph.getIntegerProperty("City MPG")
	Cyl =  graph.getIntegerProperty("Cyl")
	Dealer_Cost =  graph.getIntegerProperty("Dealer Cost")
	Engine_Size_l =  graph.getDoubleProperty("Engine Size (l)")
	HP =  graph.getIntegerProperty("HP")
	Hwy_MPG =  graph.getIntegerProperty("Hwy MPG")
	Len =  graph.getIntegerProperty("Len")
	Minivan =  graph.getIntegerProperty("Minivan")
	Pickup =  graph.getIntegerProperty("Pickup")
	RWD =  graph.getIntegerProperty("RWD")
	Retail_Price =  graph.getIntegerProperty("Retail Price")
	SUV =  graph.getIntegerProperty("SUV")
	SmallSporty_CompactLarge_Sedan =  graph.getIntegerProperty("Small/Sporty/ Compact/Large Sedan")
	Sports_Car =  graph.getIntegerProperty("Sports Car")
	Vehicle_Name =  graph.getStringProperty("Vehicle Name")
	Wagon =  graph.getIntegerProperty("Wagon")
	Weight =  graph.getIntegerProperty("Weight")
	Wheel_Base =  graph.getIntegerProperty("Wheel Base")
	Width =  graph.getIntegerProperty("Width")
	viewBorderColor =  graph.getColorProperty("viewBorderColor")
	viewBorderWidth =  graph.getDoubleProperty("viewBorderWidth")
	viewColor =  graph.getColorProperty("viewColor")
	viewFont =  graph.getStringProperty("viewFont")
	viewFontSize =  graph.getIntegerProperty("viewFontSize")
	viewLabel =  graph.getStringProperty("viewLabel")
	viewLabelBorderColor =  graph.getColorProperty("viewLabelBorderColor")
	viewLabelBorderWidth =  graph.getDoubleProperty("viewLabelBorderWidth")
	viewLabelColor =  graph.getColorProperty("viewLabelColor")
	viewLabelPosition =  graph.getIntegerProperty("viewLabelPosition")
	viewLayout =  graph.getLayoutProperty("viewLayout")
	viewMetaGraph =  graph.getGraphProperty("viewMetaGraph")
	viewMetric =  graph.getDoubleProperty("viewMetric")
	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")
	param1=graph.getDoubleProperty("param1_norm")	
	param2=graph.getDoubleProperty("param2_norm")
	
	############################
	listeCluster=[]	#liste contenant tous les clusters
	listeRep=[]#Liste contenant tous les rep qui sont les points representatifs des clusters ordonnes dans le kd tree
	
	#normalisation des donnees
	param2_norma=[]
	param1_norma=[]
	param1_norma=normalisation(City_MPG)
	param2_norma=normalisation(Retail_Price)
	
	#creation des objets clusters	
	i=0
	for n in graph.getNodes():	
		######## Afficher tous les points sur une meme ligne
		viewSize[n]=tlp.Size(25,25,25)
		viewLayout[n]=tlp.Coord(param1_norma[i]*300,param2_norma[i]*300,0)
		viewColor[n]=tlp.Color(random.randrange(255),random.randrange(255),random.randrange(255))
		
		#ajout des donnees normalisees comme propriete des noeuds du graphe	
		param1.setNodeValue(n,param1_norma[i])
		param2.setNodeValue(n,param2_norma[i])
		
		#cree un cluster et un rep par noeud
		cluster=Cluster(n)
		rep=Rep(n,cluster)
		rep.parametre1=param1_norma[i]
		rep.parametre2=param2_norma[i]
		cluster.rep.append(rep)
		#Ajoute a la liste des clusters et des reps
		listeCluster.append(cluster)	
		listeRep.append(rep)			
		i+=1		
	
	Q=CURE(listeCluster,listeRep,param1,param2,10,viewLayout,viewColor)
		
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/el_hilali_sami/solution_homework2.txt · Last modified: 2014/01/08 18:22 by bpinaud