--- a/python/ml.py	Thu Nov 24 19:20:07 2011 -0500
+++ b/python/ml.py	Fri Nov 25 18:38:54 2011 -0500
@@ -3,23 +3,55 @@
 
 __metaclass__ = type
 
-def kMeansFixedDistance(data, sameCluster, centroid):
+class Centroid:
+    'Wrapper around instances to add a counter'
+
+    def __init__(self, instance, nInstances = 1):
+        self.instance = instance
+        self.nInstances = nInstances
+
+    # def similar(instance2):
+    #     return self.instance.similar(instance2)
+
+    def add(self, instance2):
+        self.instance = self.instance.multiply(self.nInstances)+instance2
+        self.nInstances += 1
+        self.instance = self.instance.multiply(1/float(self.nInstances))
+
+    def average(c):
+        inst = self.instance.multiply(self.nInstances)+c.instance.multiply(instance.nInstances)
+        inst.multiply(1/(self.nInstances+instance.nInstances))
+        return Centroid(inst, self.nInstances+instance.nInstances)
+
+    def draw(self, options = ''):
+        from matplotlib.pylab import text
+        self.instance.draw(options)
+        text(self.instance.position.x+1, self.instance.position.y+1, str(self.nInstances))
+
+
+def clustering(data, similar, initialCentroids = []):
     '''k-means algorithm with similarity function
-    Two instances should be in the same cluster if the sameCluster function returns true for two instances. It is supposed that the centroid of a set of instances can be computed, using the function. 
+    Two instances should be in the same cluster if the sameCluster function returns true for two instances. It is supposed that the average centroid of a set of instances can be computed, using the function. 
     The number of clusters will be determined accordingly
 
     data: list of instances
-    centroid: '''
+    averageCentroid: '''
 
-    # todo randomize input
-    centroids = [data[0]]
-    for instance in data:
+    from random import shuffle
+    from copy import copy, deepcopy
+    localdata = copy(data) # shallow copy to avoid modifying data
+    shuffle(localdata)
+    if initialCentroids:
+        centroids = deepcopy(initialCentroids)
+    else:
+        centroids = [Centroid(localdata[0])]
+    for instance in localdata[1:]:
         i = 0
-        while i<len(centroids) and not sameCluster(instance, centroids[i]):
+        while i<len(centroids) and not similar(centroids[i].instance, instance):
             i += 1
         if i == len(centroids):
-            centroids.append(instance)
+            centroids.append(Centroid(instance))
         else:
-            centroids[i] = centroid(centroids[i], instance)
+            centroids[i].add(instance)
 
     return centroids