User Tools

Site Tools


chicoutimi_2016:k-means

Visual Analytics Course

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

Chicoutimi Summer 2016 roadmap / May 3, 3pm course

Algorithme k-means

Cette version de l'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).

KMeans.py
'''
Created on 7 dec. 2010
 
@author: melancon
'''
 
from tulip import *
from random import *
import time
 
class KMeans:
 
    def __init__(self, graph, k):
        self.graph = graph
        self.k = k
        self.gravitors = []
        self.colors = []
 
        self.red = tlp.Color(255, 50, 25, 255)
        self.blue = tlp.Color(50, 100, 255, 255)
        self.green = tlp.Color(75, 255, 75, 255)
        self.yellow = tlp.Color(255, 255, 50, 255)
        self.orange = tlp.Color(255, 125, 75, 255)
        self.purple = tlp.Color(120, 0, 180, 255)
        self.cyan = tlp.Color(255, 85, 255, 255)
        self.fullColorSet = [self.blue, self.green, self.cyan, self.yellow, self.orange, self.red, self.purple]
        self.epsilon = -1
        ''' used as stopping criterion, will be initialized when calling run() '''
 
    def run(self, stop = 0.01):
        viewColor = self.graph.getColorProperty("viewColor")
        layout = self.graph.getLayoutProperty("viewLayout")
        nodes = self.graph.getNodes()    
 
        self.randomPick(layout)
        for g in self.gravitors:
            self.epsilon += g.norm()
        while self.epsilon > stop: # should be changed to use a stopping criterion
            nodes = self.graph.getNodes()
            while nodes.hasNext():
                node = nodes.next()
                viewColor.setNodeValue(node, self.colors[self.selectGravitor(layout.getNodeValue(node))])
                time.sleep(0.01)
                updateVisualization()
            self.epsilon = self.updateGravitors(self.graph, viewColor, layout)
 
 
    def randomPick(self, layout):
        # pick k nodes at random and use them as gravitors
        pick = [-1] * self.k
        pick[0] = randint(0, self.graph.numberOfNodes() - 1)
        for i in range(1, self.k):
            r = randint(0, self.graph.numberOfNodes() - 1)
            while r in pick:
                r = randint(0, self.graph.numberOfNodes() - 1)
            pick[i] = r
        pick = sorted(pick)
        i = 0
        g = 0
        nodes = self.graph.getNodes()
        while i <= pick[self.k - 1]:
            node = nodes.next()
            if i in pick:
                self.gravitors.append(layout.getNodeValue(node))
                self.colors.append(self.fullColorSet[g])
                g += 1
            i += 1
 
    def selectGravitor(self, coord):
        closest = self.gravitors[0]
        closestIndex = 0
        dist2closest = coord.dist(closest)
        for i in range(1, len(self.gravitors)):
            if coord.dist(self.gravitors[i]) < dist2closest:
                dist2closest = coord.dist(self.gravitors[i])
                closest = self.gravitors[i]
                closestIndex = i
        return closestIndex
 
    def computeGravitor(self, coordList):
        x = 0
        y = 0
        z = 0
        nbCoords = len(coordList) + 0.0
        for i in range(len(coordList)):
            x += coordList[i].getX()
            y += coordList[i].getY()
            z += coordList[i].getZ()
        return tlp.Coord(x / nbCoords, y / nbCoords, z / nbCoords)
 
    def sameColor(self, c1, c2):
        if c1.getR() != c2.getR():
            return False
        elif c1.getG() != c2.getG():
            return False
        elif c1.getB() != c2.getB():
            return False
        else:
            return True
 
    def updateGravitors(self, graph, nodeColors, layout):
        epsilon = 0.0
        for i in range(self.k):
            selectedCoords = []
            nodes = graph.getNodes()
            while nodes.hasNext():
                node = nodes.next()
                if self.sameColor(nodeColors.getNodeValue(node), self.colors[i]):
                    selectedCoords.append(layout.getNodeValue(node))
            newGravitor = self.computeGravitor(selectedCoords)
            epsilon += newGravitor.dist(self.gravitors[i])
            self.gravitors[i] = newGravitor
        return epsilon
 
    def inertia_intra(self):
        layout = self.graph.getLayoutProperty("viewLayout")
        tot_inertia = 0.0
        for i in range(len(self.gravitors)):
            inertia_i = 0.0
            for n in self.graph.getNodes():
                coord = layout[n]
                if self.selectGravitor(coord) == i:
                    inertia_i += coord.dist(self.gravitors[i])**2
            tot_inertia += inertia_i
        return tot_inertia
 
def main(graph):
    k = 3
    km = KMeans(graph, k)
    km.run()
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/chicoutimi_2016/k-means.txt · Last modified: 2016/05/26 14:04 by melancon