k-means clustering
Clustering is unsupervised learning: the data have no labels, and the goal is to find groups of similar points. k-means, in the form known as Lloyd's algorithm, is the standard method. You choose the number of clusters k and some initial centroids, and then repeat two steps. In the assignment step, every point joins the cluster of its nearest centroid. In the update step, each centroid moves to the mean of the points assigned to it. The algorithm stops when the centroids no longer change.
Python
points = [(1.0, 1.0), (1.5, 2.0), (3.0, 4.0), (5.0, 7.0), (3.5, 5.0), (4.5, 5.0), (3.5, 4.5)]
def distance2(a, b):
return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2
def kmeans(points, centroids):
iterations = 0
while True:
iterations += 1
clusters = [[] for _ in centroids]
for point in points:
nearest = min(range(len(centroids)), key=lambda i: distance2(point, centroids[i]))
clusters[nearest].append(point)
updated = [(sum(p[0] for p in c) / len(c), sum(p[1] for p in c) / len(c)) for c in clusters]
if updated == centroids:
return centroids, clusters, iterations
centroids = updated
centroids, clusters, iterations = kmeans(points, [points[0], points[3]])
print([tuple(round(value, 2) for value in c) for c in centroids])
print([len(c) for c in clusters], iterations)