Function kmpp

pattern/vector/__init__.py:1514–1556

The k-means++ initialization algorithm returns a set of initial clusers, with the advantage that: - it generates better clusters than k-means(seed=RANDOM) on most data sets, - it runs faster than standard k-means, - it has a theoretical approximation guarantee.

(vectors, k, distance=COSINE)

kmeans = k_means

def kmpp(vectors, k, distance=COSINE):
    """ The k-means++ initialization algorithm returns a set of initial clusers, 
        with the advantage that:
        - it generates better clusters than k-means(seed=RANDOM) on most data sets,
        - it runs faster than standard k-means,
        - it has a theoretical approximation guarantee.
    """
    # Cache the distance calculations between vectors (up to 4x faster).
    map = DistanceMap(method=distance); distance = map.distance
    # David Arthur, 2006, http://theory.stanford.edu/~sergei/slides/BATS-Means.pdf
    # Based on:
    # http://www.stanford.edu/~darthur/kmpp.zip
    # http://yongsun.me/2008/10/k-means-and-k-means-with-python
    # Choose one center at random.
    # Calculate the distance between each vector and the nearest center.
    centroids = [choice(vectors)]
    d = [distance(v, centroids[0]) for v in vectors]
    s = sum(d)
    for _ in range(int(k) - 1):
        # Choose a random number y between 0 and d1 + d2 + ... + dn.
        # Find vector i so that: d1 + d2 + ... + di >= y > d1 + d2 + ... + dj.
        # Perform a number of local tries so that y yields a small distance sum.
        i = 0
        for _ in range(int(2 + log(k))):
            y = random() * s
            for i1, v1 in enumerate(vectors):
                if y <= d[i1]: 
                    break
                y -= d[i1]
            s1 = sum(min(d[j], distance(v1, v2)) for j, v2 in enumerate(vectors))
            if s1 < s:
                s, i = s1, i1
        # Add vector i as a new center.
        # Repeat until we have chosen k centers.
        centroids.append(vectors[i])
        d = [min(d[i], distance(v, centroids[-1])) for i, v in enumerate(vectors)]
        s = sum(d)
    # Assign points to the nearest center.
    clusters = [[] for i in xrange(int(k))]
    for v1 in vectors:
        d = [distance(v1, v2) for v2 in centroids]
        clusters[d.index(min(d))].append(v1)
    return clusters

#--- HIERARCHICAL ----------------------------------------------------------------------------------
# Hierarchical clustering is slow but the optimal solution guaranteed in O(len(vectors) ** 3).