User Tools

Site Tools


k-means

Table of Contents

Visual Analytics Course

k-Means

Here is a piece of python code that implements the k-Means algorithm in a very simple form. You would typically use it as:

km = KMeans(graph, k) # where k is an integer
km.run(epsilon) # where epsilon is a small real number (corresponding to how much barycenters move after iterating the main loop of the algorithm) 

KMeans.py
from random import *
 
class KMeansEuclidean:
 
    '''
    Computes k clusters based on the classical K-means algorithm
    Because nodes are colored using predefined colors,
    a maximal number of clusters is imposed
    '''
 
    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(170, 0, 255)
        self.pink = tlp.Color(255, 0, 255)
        self.brown = tlp.Color(170, 85, 0)
        self.fullColorSet = [self.red, self.blue, self.green, self.yellow, self.orange, self.purple, self.pink, self.brown]
        self.epsilon = -1
        ''' used as stopping criterion, will be initialized when calling run() '''
 
    def run(self, stop = 0.01):
        if self.k > len(self.fullColorSet):
            print "A maximum of ", len(self.fullColorSet), " clusters may be specified"
            return False
        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))])
            self.epsilon = self.updateGravitors(self.graph, viewColor, layout)
            updateVisualization()
 
 
    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
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/k-means.txt · Last modified: 2012/11/16 10:23 by melancon