###################################################### ######### 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_pointsQ[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 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=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=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_clusterdistW_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)