reorganise folders

[imago.git] / src / k_means.py

diff --git a/src/k_means.py b/src/k_means.py
new file mode 100644 (file)
index 0000000..f429824
--- /dev/null
+++ b/src/k_means.py
@@ -0,0 +1,51 @@
+"""K-means module."""
+
+import random
+
+def cluster(k, d, data, i_centers=None):
+    """Find *k* clusters on *d* dimensional *data*."""
+    borders = [(min(p[0][i] for p in data), max(p[0][i] for p in data))
+               for i in range(d) ]
+    if i_centers:
+        old_centers = i_centers
+    else:
+        old_centers = [[(h - l) * random.random() + l for (l, h) in borders]
+               for _ in range(k)]
+    clusters, centers = next_step(old_centers, data)
+    while delta(old_centers, centers) > 0:
+        old_centers = centers
+        clusters, centers = next_step(old_centers, data)
+
+    return clusters
+
+def next_step(centers, data):
+    """Compute new clusters and centers."""
+    clusters = [[] for _ in centers]
+    for point in data:
+        clusters[nearest(centers, point)].append(point)
+    centers = [centroid(c) for c in clusters]
+    return clusters, centers
+
+def nearest(centers, point):
+    """Find the nearest cluster *center* for *point*."""
+    d, i = min(((sum((p - c) ** 2 for (p, c) in zip(point[0], center)) ** 0.5 ,
+                index) if center else (float('inf'), len(centers)))
+               for (index, center) in enumerate(centers))
+    return i
+
+def centroid(cluster):
+    """Find the centroid of the *cluster*."""
+    # TODO is this just a mean of coordinates?
+    # TODO should we try different definitions?
+    l = float(len(cluster))
+    try:
+        d = len(cluster[0][0]) #TODO empty cluster error
+    except IndexError:
+        return None
+    return [sum(c[0][i] for c in cluster) / l for i in range(d)]
+
+def delta(c1, c2):
+    """Find the absolute distance between two lists of points."""
+    # TODO rewrite this to a sane form
+    return sum((sum(abs(cc1 - cc2) for (cc1, cc2) in zip (ccc1, ccc2)) if ccc2
+               else 0.) for (ccc1, ccc2) in zip(c1, c2))