k_means.py

   1 """K-means module"""
   2
   3 import random
   4
   5 def cluster(k, d, data, i_centers=None):
   6     borders = [(min(p[0][i] for p in data), max(p[0][i] for p in data))
   7                for i in range(d) ]
   8     if i_centers:
   9         old_centers = i_centers
  10     else:
  11         old_centers = [[(h - l) * random.random() + l for (l, h) in borders]
  12                for _ in range(k)]
  13     clusters, centers = next_step(old_centers, data)
  14     while delta(old_centers, centers) > 0:
  15         old_centers = centers
  16         clusters, centers = next_step(old_centers, data)
  17
  18     return clusters
  19
  20 def next_step(centers, data):
  21     clusters = [[] for _ in centers]
  22     for point in data:
  23         clusters[nearest(centers, point)].append(point)
  24     centers = [centroid(c) for c in clusters]
  25     return clusters, centers
  26
  27 def nearest(centers, point):
  28     d, i = min(((sum((p - c) ** 2 for (p, c) in zip(point[0], center)) ** 0.5 ,
  29                 index) if center else (float('inf'), len(centers)))
  30                for (index, center) in enumerate(centers))
  31     return i
  32
  33 def centroid(cluster):
  34     l = float(len(cluster))
  35     try:
  36         d = len(cluster[0][0]) #TODO empty cluster error
  37     except IndexError:
  38         return None
  39     return [sum(c[0][i] for c in cluster) / l for i in range(d)]
  40
  41 def delta(c1, c2):
  42     return sum( (sum(abs(cc1 - cc2) for (cc1, cc2) in zip (ccc1, ccc2)) if ccc2
  43                else 0.) for (ccc1, ccc2) in zip(c1, c2))