Here is my personal implementation of the clustering k-means algorithm.
from scipy.spatial import distance import numpy as np import random # (x,y) coordinates of a point X = 0 Y = 1 def get_first(k, points): return points[0:k] def cost(cetroids, clusters): cost = 0 for i in range(len(centroids)): centroid = centroids[i] cluster = clusters[i] for point in cluster: cost += (distance.euclidean(centroid, point))**2 return cost def compute_centroids(clusters): centroids =  for cluster in clusters: centroids.append(np.mean(cluster, axis=0)) return centroids def kmeans(k, centroids, points, method, iter): clusters = [ for i in range(k)] for i in range(len(points)): point = points[i] belongs_to_cluster = closest_centroid(point, centroids) clusters[belongs_to_cluster].append(point) new_centroids = compute_centroids(clusters) if not equals(centroids, new_centroids): print "Iteration " + str(iter) + ". Cost [k=" + str(k) + ", " + method + "] = " + str(cost(new_centroids, clusters)) clusters = kmeans(k, new_centroids, points, method, iter+1) return clusters def closest_centroid(point, centroids): min_distance = float('inf') belongs_to_cluster = None for j in range(len(centroids)): centroid = centroids[j] dist = distance.euclidean(point, centroid) if dist < min_distance: min_distance = dist belongs_to_cluster = j return belongs_to_cluster def contains(point1, points): for point2 in points: if point1[X] == point2[X] and point1[Y] == point2[Y]: return True return False def equals(points1, points2): if len(points1) != len(points2): return False for i in range (len(points1)): point1 = points1[i] point2 = points2[i] if point1[X] != point2[X] or point1[Y] != point2[Y]: return False return True if __name__ == "__main__": data = [[-19.0748, -8.536 ], [ 22.0108, -10.9737 ], [ 12.6597, 19.2601 ], [ 11.26884087, 19.90132146 ], [ 15.44640731, 21.13121676 ], [-20.03865146, -8.820872829], [-19.65417726, -8.211477352], [-15.97295894, -9.648002534], [-18.74359696, -5.383551586], [-19.453215, -8.146120006], [-16.43074088, -7.524968005], [-19.75512437, -8.533215751], [-19.56237082, -8.798668569], [-19.47135573, -8.057217004], [-18.60946986, -4.475888949], [-21.59368337, -10.38712463], [-15.39158057, -3.8336522 ], [-40.0, 40.0 ]] k = 4 # k-means picking the first k points as centroids centroids = get_first(k, data) clusters = kmeans(k, centroids, data, "first", 1)
I understood and followed the theory of the algorithm, but as you can see, when running the code, the cost on each iteration of the algorithm increases. I am new to python and I think the problem relies in some misunderstanding from my side regarding list manipulation. Any ideas?