Function k_means

pattern/vector/__init__.py:1462–1510

Returns a list of k clusters, where each cluster is a list of vectors (Lloyd's algorithm). Vectors are assigned to k random centers using a distance metric (EUCLIDEAN, COSINE, ...). Since the initial centers are chosen randomly (by default, seed=RANDOM), there is no guarante

(vectors, k=None, iterations=10, distance=COSINE, seed=RANDOM, **kwargs)

RANDOM, KMPP = "random", "kmeans++"

def k_means(vectors, k=None, iterations=10, distance=COSINE, seed=RANDOM, **kwargs):
    """ Returns a list of k clusters, where each cluster is a list of vectors (Lloyd's algorithm).
        Vectors are assigned to k random centers using a distance metric (EUCLIDEAN, COSINE, ...).
        Since the initial centers are chosen randomly (by default, seed=RANDOM),
        there is no guarantee of convergence or of finding an optimal solution.
        A more efficient way is to use seed=KMPP (k-means++ initialization algorithm).
    """
    features = kwargs.get("features") or _features(vectors)
    if k is None:
        k = sqrt(len(vectors) / 2)
    if k < 2: 
        return [[v for v in vectors]]
    if seed == KMPP:
        clusters = kmpp(vectors, k, distance)
    else:
        clusters = [[] for i in xrange(int(k))]
        for i, v in enumerate(sorted(vectors, key=lambda x: random())):
            # Randomly partition the vectors across k clusters.
            clusters[i % int(k)].append(v)
    # Cache the distance calculations between vectors (up to 4x faster).
    map = DistanceMap(method=distance); distance = map.distance
    converged = False
    while not converged and iterations > 0 and k > 0:
        # Calculate the center of each cluster.
        centroids = [centroid(cluster, features) for cluster in clusters]
        # Triangle inequality: one side is shorter than the sum of the two other sides.
        # We can exploit this to avoid costly distance() calls (up to 3x faster).
        p = 0.5 * kwargs.get("p", 0.8) # "Relaxed" triangle inequality (cosine distance is a semimetric) 0.25-0.5.
        D = {}
        for i in range(len(centroids)):
            for j in range(i, len(centroids)): # center1–center2 < center1–vector + vector–center2 ?
                D[(i,j)] = D[(j,i)] = p * distance(centroids[i], centroids[j])
        # For every vector in every cluster,
        # check if it is nearer to the center of another cluster.
        # If so, assign it. When visualized, this produces a Voronoi diagram.
        converged = True
        for i in xrange(len(clusters)):
            for v in clusters[i]:
                nearest, d1 = i, distance(v, centroids[i])
                for j in xrange(len(clusters)):
                    if D[(i,j)] < d1: # Triangle inequality (Elkan, 2003).
                        d2 = distance(v, centroids[j])
                        if d2 < d1:
                            nearest = j
                if nearest != i: # Other cluster is nearer.
                    clusters[nearest].append(clusters[i].pop(clusters[i].index(v)))
                    converged = False
        iterations -= 1; #print iterations
    return clusters
    
kmeans = k_means