k-meansを、重心が動くところから理解する

def kmeans(points, k, iterations=20):
    """A compact teaching implementation for 2D points."""
    centroids = [list(point) for point in points[:k]]

    for _ in range(iterations):
        groups = [[] for _ in range(k)]

        for point in points:
            label = min(
                range(k),
                key=lambda i: squared_distance(point, centroids[i]),
            )
            groups[label].append(point)

        updated = []
        for i, group in enumerate(groups):
            if not group:
                updated.append(centroids[i])
                continue
            updated.append([
                sum(p[0] for p in group) / len(group),
                sum(p[1] for p in group) / len(group),
            ])

        if all(squared_distance(a, b) < 1e-10
               for a, b in zip(centroids, updated)):
            break
        centroids = updated

    return centroids, groups

def squared_distance(a, b):
    return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2