User Tools

Site Tools


chicoutimi_2016:clustering_hierarchique_ascendant

Visual Analytics Course

Instructor: Guy Melançon (email: Guy dot Melancon at labri dot fr)

Chicoutimi Summer 2016 roadmap / May 3, 3pm course

Clustering hiérarchique ascendant

Cet exemple s'appuie sur les notions vu en cours sur le clustering hiérarchique de graphes, et implémente l'algorithme de hiérarchique ascendant.

Cet algorithme calcule la distance entre les points à partir de leur position à l'écran. Mais on peut penser calculer la distance euclidienne entre ces points à partir de leurs attributs (ceux qui s'y prêtent).

L'algorithme fabrique un clone du graphe de départ , et crée un arbre (un autre graphe) qui décrit la structure du clustering et dont les feuilles sont les éléments de .

HierarchicalClustering.py
from tulip import *
import time
import numpy
 
class HierarchicalClustering(object):
	'''
	computes a hierarchical clustering of a muldim dataset
	a cluster tree is built as a side graph
	'''
	def __init__(self, arg):
		super(HierarchicalClustering, self).__init__()
		self.graph = graph
		self.original_graph = self.graph.addCloneSubGraph('original_graph')
		selNodes = self.graph.getBooleanProperty('viewSelection')
		selNodes.setAllNodeValue(True)
		selNodes.setAllEdgeValue(False)
		self.layout = self.original_graph.getLayoutProperty('viewLayout')
 
		self.cluster_tree = graph.addSubGraph(selNodes)
		self.cluster_tree.setName('cluster_tree')
		self.cluster_distance_prop = self.cluster_tree.getDoubleProperty('cluster_distance')
 
		# stores total inertia within (intra) cluster
		self.intra = self.cluster_tree.getDoubleProperty('raw_inertia')
		# stores between cluster inertia by subtracting
		self.inter = self.cluster_tree.getDoubleProperty('inter_inertia')
		# stores intertia between barycenter of child clusters
		#self.inter_from_barycenter = self.cluster_tree.getDoubleProperty('inter_inertia_from_barycenter')
		self.clusters = {}
		for n in self.cluster_tree.getNodes():
			self.clusters[n] = set([n])
			self.intra[n] = 0.0
			self.inter[n] = 0.0
		self.cluster_barycenters = self.cluster_tree.getLayoutProperty('barycenter')
		orig_graph_layout = self.original_graph.getLayoutProperty('viewLayout')
		for n in self.original_graph.getNodes():
			self.cluster_barycenters[n] = orig_graph_layout[n]
 
	def merge(self, cluster_node1, cluster_node2, cluster_dist):
		'''
		merges subgraphs 1, 2 in the cluster tree
		by adding a new node in the tree instanciating the merge
		'''
		new_cluster_node = self.cluster_tree.addNode()
		self.cluster_distance_prop[new_cluster_node] = cluster_dist
		e1 = self.cluster_tree.addEdge(new_cluster_node, cluster_node1)
		e2 = self.cluster_tree.addEdge(new_cluster_node, cluster_node2)
		self.clusters[new_cluster_node] = self.clusters[cluster_node1].union(self.clusters[cluster_node2])
		b1 = self.barycenter(cluster_node1)
		b2 = self.barycenter(cluster_node2)
		size_c1 = float(len(self.clusters[cluster_node1]))
		size_c2 = float(len(self.clusters[cluster_node2]))
		b = self.barycenter(new_cluster_node)
		self.cluster_barycenters[new_cluster_node] = b
		size_c = len(self.clusters[new_cluster_node])
		self.inter[e1] = b1.dist(b)**2
		self.inter[e2] = b2.dist(b)**2
 
		self.intra[new_cluster_node] = self.raw_inertia(new_cluster_node)
		self.clusters.pop(cluster_node1)
		self.clusters.pop(cluster_node2)
 
	def cluster_distance(self, cluster_node1, cluster_node2, distance_function):
		'''
		distance between clusters is the average distance between pairs of nodes selected form cluster 1 and 2
		other approaches are possible
		'''
		ave_dist = 0.0
		size_c1 = len(self.clusters[cluster_node1])
		size_c2 = len(self.clusters[cluster_node2])
		for n1 in self.clusters[cluster_node1]:
			for n2 in self.clusters[cluster_node2]:
				ave_dist += distance_function(n1, n2)
		return ave_dist / (size_c1 * size_c2)
 
	def distance_function(self, n1, n2):
		'''
		let's use for now the euclidean distance between nodes in the plane
		'''
		return self.layout[n1].dist(self.layout[n2])
 
	def connected(self, cluster1, cluster2):
		'''
		to do -- better to only merge clusters that are connected,
		not only that they sit close to each other
		'''
		return True
 
	def min_distance_clusters(self):
		'''
		loops over all pairs of subgraphs of original graph
		returns pair of distinct subgraphs with minimal cluster distance
		'''
		min_dist = numpy.inf
		for i, clusteri in enumerate(self.clusters.keys()):
			for j, clusterj in enumerate(self.clusters.keys()):
				if j > i and self.connected(clusteri, clusterj):
					c_dist = self.cluster_distance(clusteri, clusterj, self.distance_function)
					if c_dist < min_dist:
						min_dist = c_dist
						min_sg1 = clusteri
						min_sg2 = clusterj
		return min_dist, min_sg1, min_sg2
 
	def Ward_clustering(self):
		while len(self.clusters.keys()) > 1:
			print('Dealing with ', len(self.clusters.keys()), ' clusters')
			min_dist, min_sg1, min_sg2 = self.min_distance_clusters()
			self.merge(min_sg1, min_sg2, min_dist)
 
	def raw_inertia(self, cluster_node):
		inertia = 0.0
		barycenter = self.barycenter(cluster_node)
		for n in self.clusters[cluster_node]:
			inertia += self.layout[n].dist(barycenter)**2
		return inertia
 
	def barycenter(self, cluster_node):
		barycenter = tlp.Coord(0.0,0.0,0.0)
		for n in self.clusters[cluster_node]:
			barycenter += self.layout[n]
		barycenter /= len(self.clusters[cluster_node])
		return barycenter
 
	def inter_inertia(self, father_cluster_node, cluster_node1, cluster_node2):
		b = self.barycenter(father_cluster_node)
		b1 = self.barycenter(cluster_node1)
		b2 = self.barycenter(cluster_node2)
 
		return b1.dist(b)**2 + b2.dist(b)**2
 
def main(graph):
 
	hc = HierarchicalClustering(graph)
	hc.Ward_clustering()
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/chicoutimi_2016/clustering_hierarchique_ascendant.txt · Last modified: 2016/05/26 21:54 by melancon