# Visual Analytics Course

k-means

## 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