User Tools

Site Tools


chicoutimi_2016:biparti_cereals

Visual Analytics Course

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

Chicoutimi Summer 2016 roadmap / Session by session cutdown

Projection des graphes biparti, homogénéité et fouille visuelle

Cette séance revient sur le calcul de graphes bipartis, leur projection (pondérée),

et sur la navigation proposée par Renoust mettant en jeu les deux partitions d'un graphe biparti.

Pour prendre en main les données:

Cereals.py
from tulip import *
import json
import numpy
import math
 
class Cereals(object):
	"""docstring for Cereals"""
	def __init__(self, graph, property_list):
		super(Cereals, self).__init__()
		self.graph = graph
		self.property_list = property_list
 
	def normalize(self):
		self.all_ave = []
		for p in self.property_list:
			ave = 0.0
			for n in self.graph.getNodes():
				ave += p[n]
			ave /= self.graph.numberOfNodes()
			self.all_ave.append(ave)
 
		self.all_std_dev = []
		for i, p in enumerate(self.property_list):
			std = 0.0
			for n in self.graph.getNodes():
				std += (p[n] - self.all_ave[i])**2
			std /= self.graph.numberOfNodes()
			self.all_std_dev.append(math.sqrt(std))
 
		self.all_norm_prop = map(lambda x: self.graph.getDoubleProperty(x.getName() + '_norm'), self.property_list)
		for i, p in enumerate(self.property_list):
			p_norm = self.all_norm_prop[i]
			for n in self.graph.getNodes():
				p_norm[n] = (p[n] - self.all_ave[i])/self.all_std_dev[i]
 
	def make_complete_graph(self):
		nodes = [n for n in self.graph.getNodes()]
		for i, ni in enumerate(nodes):
			for j, nj in enumerate(nodes):
				if j > i:
					e = self.graph.addEdge(ni, nj)
 
	def compute_distances(self):
		nodes = [n for n in self.graph.getNodes()]
 
		diss_euclidean = self.graph.getDoubleProperty('dissimilarity_euclidean')
		mat_diss_euclidean = numpy.matrix([[0.0 for n in self.graph.getNodes()] for n in self.graph.getNodes()])
		for i, ni in enumerate(nodes):
			vi = map(lambda x: x[ni], self.property_list)
			for j, nj in enumerate(nodes):
				if j > i:
					vj = map(lambda x: x[nj], self.property_list)
					mat_diss_euclidean[i,j] = math.sqrt(sum(map(lambda x: (x[0]-x[1])**2, zip(vi, vj))))
 
		diss_euclidean_norm = self.graph.getDoubleProperty('dissimilarity_euclidean_norm')
		mat_diss_euclidean_norm = numpy.matrix([[0.0 for n in self.graph.getNodes()] for n in self.graph.getNodes()])
		for i, ni in enumerate(nodes):
			vi = map(lambda x: x[ni], self.all_norm_prop)
			for j, nj in enumerate(nodes):
				if j > i:
					vj = map(lambda x: x[nj], self.all_norm_prop)
					mat_diss_euclidean_norm[i,j] = math.sqrt(sum(map(lambda x: (x[0]-x[1])**2, zip(vi, vj))))
 
		diss_cos = self.graph.getDoubleProperty('dissimilarity_cosinus')
		mat_diss_cos = numpy.matrix([[0.0 for n in self.graph.getNodes()] for n in self.graph.getNodes()])
		for i, ni in enumerate(nodes):
			vi = map(lambda x: x[ni], self.property_list)
			for j, nj in enumerate(nodes):
				if j > i:
					vj = map(lambda x: x[nj], self.property_list)
					scal_prod = sum(map(lambda x: x[0]*x[1], zip(vi, vj)))
					norm_vi = math.sqrt(sum(map(lambda x: x**2, vi)))
					norm_vj = math.sqrt(sum(map(lambda x: x**2, vj)))
					mat_diss_cos[i,j] = 1.0 - scal_prod / (norm_vi * norm_vj)
 
		for i, ni in enumerate(nodes):
			vi = map(lambda x: x[ni], self.property_list)
			for j, nj in enumerate(nodes):
				if j > i:
					#e = self.graph.addEdge(ni, nj)
					e = self.graph.existEdge(ni, nj, False)
					diss_euclidean[e] =mat_diss_euclidean[i,j]
					diss_euclidean_norm[e] = mat_diss_euclidean_norm[i,j]
					diss_cos[e] = mat_diss_cos[i,j]
 
def main(graph):
	Calories = graph.getIntegerProperty("Calories")
	Complex_carbohydrates = graph.getIntegerProperty("Complex_carbohydrates")
	Cups = graph.getIntegerProperty("Cups")
	Dietary_fiber = graph.getIntegerProperty("Dietary_fiber")
	Display_shelf = graph.getIntegerProperty("Display_shelf")
	Fat = graph.getIntegerProperty("Fat")
	Manufacturer = graph.getStringProperty("Manufacturer")
	Name = graph.getStringProperty("Name")
	Potassium = graph.getIntegerProperty("Potassium")
	Protein = graph.getIntegerProperty("Protein")
	Sodium = graph.getIntegerProperty("Sodium")
	Sugars = graph.getIntegerProperty("Sugars")
	Type = graph.getStringProperty("Type")
	Vitamins_and_minerals = graph.getIntegerProperty("Vitamins_and_minerals")
	Weight = graph.getIntegerProperty("Weight")
 
	property_list = [Calories, Complex_carbohydrates, Cups, Dietary_fiber, \
					Fat, Potassium, Protein, Sodium, Sugars, Vitamins_and_minerals, Weight]
 
	cereals = Cereals(graph, property_list)
	cereals.make_complete_graph()
	cereals.normalize()
	cereals.compute_distances()
Céréales et graphe biparti
  • En examinant les valeurs des attributs des céréales, on est tenté de penser qu'il s'agit là plutôt de données nominales ou ordinales – plutôt que de valeurs données sur une échelle numériques.
    • C'est le cas pour l'attribut Protein dont les valeurs s'étendent sur une échelle de 1 à 6
    • C'est le cas pour l'attribut Vitamins_and_minerals dont les valeurs varient dans
  • Ecrivez un script qui à partir des données sur les céréales construit un graphe biparti
  • Dont les sommets sont:
    • les sommets correspondant aux céréales (les lignes du tableau de données de départ)
    • les sommets (attributs) correspondant aux valeurs nominales ou ordinales
      • Ainsi, les valeurs de l'attribut Vitamins_and_minerals donnera lieu à trois sommets Vitamins_and_minerals_0, Vitamins_and_minerals_25, Vitamins_and_minerals_100
  • Dont les arêtes connectent les sommets aux sommets
    • Ainsi, si la céréale a la valeur 0 pour l'attribut Vitamins_and_minerals, on créera un lien entre le sommet et le sommet Vitamins_and_minerals_0.
nodes = [n for n in graph.getNodes()]
pour n dans nodes
    type de n = cereale

On cree d'abord les sommets 'modalite'
pour chaque propriete p (dans la liste des proprietes qui nous interessent)
    on calcule l'ensemble des valeurs prises sur les sommets
    value_set = set([p[n] for n in nodes])
    pour chaque valeur dans cet ensemble
        on cree un nouveau sommet
        m_node = graph.addNode()
        nom de m_node = nom propriete + valeur 
        type de m_node = modalite

pour chaque propriete p (dans la liste des proprietes qui nous interessent)
    pour chaque sommet cereale c
        on cree une arete entre c et le sommet dont le nom est nom de p + valeur p[n]

Reculer pour mieux avancer ?
  • Sur ce graphe biparti, on peut calculer une projection et revenir au graphe de départ.
    • Le procédé de projection permet d'inférer un poids sur les arêtes du graphe de départ.
    • Comment ce poids se compare t-il aux distances euclidiennes calculées à partir des attributs (considérés alors comme attributs numériques) ?

Un script pour calculer la projection (et le poids induit sur les arêtes):

OneModeProjection.py
from tulip import *
 
class Projection(object):
	def __init__(self, graph):
		self.graph = graph
		self.catalyst_map = {}
 
	def neighbor_sets(self):
		for s in self.substrates:
			self.catalyst_map[s] = frozenset([catalyst for catalyst in self.two_mode_graph.getInOutNodes(s)])
 
	def project(self, type_property, type_name):
		catalysts = [n for n in self.two_mode_graph.getNodes() if type_property[n] != type_name]
		for c in catalysts:
			try:
				c_weight = self.weight_function(c)
				substrates = [neigh for neigh in self.two_mode_graph.getInOutNodes(c)]
				for i, si in enumerate(substrates):
					for j, sj in enumerate(substrates):
						if i < j:
							e = self.substrate_graph.existEdge(si, sj, False)
							if not e.isValid():
								e = self.substrate_graph.addEdge(si, sj)
							self.edge_weight[e] += c_weight
			except ZeroDivisionError: # happens when c has degree 1, in which case there are no inferred edges
				pass
 
	def Giatsidis_weight_function(self, catalyst):
		return 1.0 / self.graph.deg(catalyst)
 
	def clique_weight_function(self, catalyst):
		return 2.0 / self.graph.deg(catalyst) / (self.graph.deg(catalyst) - 1)
 
	def uniform_weight(self, catalyst):
		return 1.0
 
	def run(self, type_property, type_name, weighting_scheme = 'Giatsidis'):
		# This method is the entry point of the algorithm when it is called
		# and must contain its implementation.
 
		# The graph on which the algorithm is applied can be accessed through
		# the "graph" class attribute (see documentation of class tlp.Graph).
 
		# The parameters provided by the user are stored in a Tulip DataSet
		# and can be accessed through the "dataSet" class attribute
		# (see documentation of class tlp.DataSet).
 
		# The method must return a boolean indicating if the algorithm
		# has been successfully applied on the input graph.
		self.two_mode_graph = self.graph.getSubGraph('Two_mode_graph')
		if self.two_mode_graph == None:
			self.two_mode_graph = self.graph.addCloneSubGraph('Two_mode_graph')
		self.substrates = [n for n in self.two_mode_graph.getNodes() if type_property[n] == type_name]
		self.substrate_graph = self.graph.addSubGraph()
		for s in self.substrates:
			self.substrate_graph.addNode(s)
		self.substrate_graph.setName(type_name + '_graph_' + weighting_scheme)
 
		self.edge_weight = self.substrate_graph.getDoubleProperty('edge_weight')
		if weighting_scheme == 'Giatsidis':
			self.weight_function = self.Giatsidis_weight_function
		elif weighting_scheme == 'Clique':
			self.weight_function = self.clique_weight_function
		else: # self.dataSet['Weighting scheme'] == 'Uniform 1.0'
			self.weight_function = self.uniform_weight
 
		self.neighbor_sets()
		self.project(type_property, type_name)
		return True
 
def main(graph):
	omp = Projection(graph)
	type_prop = graph.getStringProperty('bipartite_type')
	projected_entities = 'cereal'
	weighting_scheme = 'Giatsidis'
	omp.run(type_prop, projected_entities, weighting_scheme)

  • Cette section propose de naviguer le graphe biparti des céréales (et des modalités) selon la technique de Renoust
  • A partir du graphe biparti, construisez un fichier json sur le modèle du fichier toy_example.json
  • Pour éviter d'avoir à naviguer un graphe trop touffu, on peut en simplifier la structure
    • Parmi les sommets représentant les modalités, on peut éliminer les sommets de degrés 1 qui n'indexeront alors aucune arête
    • On peut aussi pousser et éliminer les sommets de degré 2 puisque ces descripteurs auront une interaction “périphérique” avec les autres descripteurs (de degré pus élevé).
  • Une fois le fichier de données produit, chargez les données sur le site de Detangler et explorez les données.
toy_example.json
{"nodes":[
	{
		"id":1,
		"label":"node1",
		"x":0,
		"y":0,
		"descriptors":"catalyst(-);catalyst(+);catalyst(~);catalyst(=)"
	},
	{
		"id":2,
		"label":"node2",
		"x":1,
		"y":1,
		"descriptors":"catalyst(-);catalyst(+);catalyst(~)"
	},
	{
		"id":3,
		"label":"node3",
		"x":2,
		"y":0,
		"descriptors":"catalyst(-);catalyst(=)"
	}],
"links":[
	{
		"id":1,
		"source":1,
		"target":2,
		"descriptors":"catalyst(-);catalyst(+);catalyst(~)"
	},
	{
		"id":2,
		"source":1,
		"target":3,
		"descriptors":"catalyst(-);catalyst(=)"
	},
	{
		"id":3,
		"source":2,
		"target":3,
		"descriptors":"catalyst(-)"
	}]
}
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/chicoutimi_2016/biparti_cereals.txt · Last modified: 2016/06/03 16:29 by melancon