K-means算法的变体，具有等大小簇的特点。

Question

K-means算法的变体，具有等大小簇的特点。

algorithmdictionarycluster-analysisk-means

59

我正在寻找一种最快的算法，将地图上的点按距离平均分组。k-means clustering algorithm 看起来直接且有前途，但无法产生大小相等的组。

是否有这个算法的变体或其他算法可实现所有聚类中成员数量相等？

参见：Group n points in k clusters of equal size

- pixelistik

1

k-means聚类本身是NP难问题。也许你可以开始改变距离函数，直到所有点都落入大小相等的组中，但我担心这不是一个凸优化问题，所以你需要进行一些严肃的计算。 - Alexei Polkhanov

谢谢大家给出的好答案。我已经采用了完全不同的方法来解决我的初始问题，不再涉及聚类。因此，我无法判断哪个答案应该被接受，我将把它保持开放状态，希望你们不介意。 - pixelistik

@pixelistik 你好，能否请您介绍一下您解决这个问题的方法？我也在尝试解决同样的问题。任何提示/建议都可以。先谢谢了。 - Atendra Gautam

抱歉，我恐怕无法提供帮助。我的方法已经不再涉及聚类了。 - pixelistik

@Atendra，下面的很多回答中都有实现。有些似乎已经过时（Python），其他一些据说还可以使用（ELKI），还有一些需要自己编写代码（我的回答）。你试过其中任何一个吗？ - Has QUIT--Anony-Mousse

18个回答

11

如果有人想要复制和粘贴短函数，这里有一个 - 基本上运行KMeans，然后在最大分配点的约束下找到点与聚类之间的最小匹配（聚类大小）。

from sklearn.cluster import KMeans
from scipy.spatial.distance import cdist
from scipy.optimize import linear_sum_assignment
import numpy as np


def get_even_clusters(X, cluster_size):
    n_clusters = int(np.ceil(len(X)/cluster_size))
    kmeans = KMeans(n_clusters)
    kmeans.fit(X)
    centers = kmeans.cluster_centers_
    centers = centers.reshape(-1, 1, X.shape[-1]).repeat(cluster_size, 1).reshape(-1, X.shape[-1])
    distance_matrix = cdist(X, centers)
    clusters = linear_sum_assignment(distance_matrix)[1]//cluster_size
    return clusters

- Eyal Shulman

1

我猜这里的X是一个(x,y)值或坐标的列表。有没有办法输入一个距离/权重矩阵呢？ - tcokyasar

一个解释。Centers被重复，以便每个中心出现cluster_size次。因此，distance_matrix具有每个点到每个中心的距离重复cluster_size次。linear_sum_assignment将每个点与最近可用的中心（记住中心是重复的）进行1-1映射。[1]的输出显示哪个重复的中心匹配到输入的[0]（[0]已排序，所以它只是arange）。因此，//删除重复项，为每个输入提供正确的聚类。 - thepenguin77

如果您的X不能完全适配cluster_size，您可以进行以下更改：

who_is = np.tile(np.arange(n_clusters),(cluster_size+1))[:len(X)]
centers_repeated = centers[who_is]
distance_matrix = cdist(X, centers_repeated)
X_assignments = linear_sum_assignment(distance_matrix)[1]
clusters = who_is[X_assignments]

- thepenguin77

这段代码似乎不太适合扩展。我使用了8GB的RAM，但在尝试对10000个点进行聚类时无法得到结果。 - asmaier

7

ELKI数据挖掘框架有一个等大小k-means教程。

这不是一个特别好的算法，但它是一种足够简单的k-means变体，可以编写教程并教人们如何实现自己的聚类算法变体。显然，有些人确实需要他们的簇具有相同的大小，尽管SSQ质量将比常规k-means差。

在ELKI 0.7.5中，您可以选择此算法作为tutorial.clustering.SameSizeKMeansAlgorithm。

- Erich Schubert

6

总的来说，在理论上，将地图上的点按距离分组成相等大小的组是不可能的任务。因为将点分组成相等大小的组与按距离将点分组成簇是相互冲突的。

看这个图：

有四个点：

A.[1,1]
B.[1,2]
C.[2,2]
D.[5,5]

如果我们把这些点分成两个簇，显然 (A,B,C) 将成为簇 1，D 将成为簇 2。但是，如果我们需要等大小的组，(A,B) 将成为一个簇，(C,D) 将成为另一个簇。这违反了簇规则，因为 C 更靠近 (A,B) 的中心，但它属于簇 (C,D)。因此，簇要求和等大小分组的要求无法同时满足。

- BooksE

5

你可以将距离视为定义加权图的方式。相当多的图分割算法明确地基于尝试将图顶点划分为两个大小相等的集合。例如，在Kernighan-Lin算法和使用拉普拉斯的谱图分割中都有这种情况。要获取多个聚类，您可以递归应用分区算法；在谱图分割链接上有一个很好的讨论。

- Michael J. Barber

5

尝试这种k-means变体：

初始化：

- 从数据集中随机选择k个中心，或者更好的方法是使用kmeans ++策略。 - 对于每个点，计算到其最近簇中心的距离，并构建一个堆。 - 从堆中选取点，并将它们分配给最近的簇，除非该簇已经过满。如果是这样的话，计算下一个最近的簇心并重新插入堆中。

最后，你应该有一个符合要求的分区，即每个簇的物体数量+-1相同（确保最后几个簇也有正确的数量。前m个簇应有ceil个物体，剩余部分应该正好有floor个物体）。

迭代步骤：

先决条件：对于每个簇，有一个带有“交换提议”的列表（希望在不同簇中的对象）。

E步骤：像常规k-means一样计算更新的簇中心。

M步骤：遍历所有点（只有一个或者全部在一个批次中）

- 计算对象/所有比当前簇更接近的所有簇中心的最近簇中心。如果它是一个不同的簇： - 如果其他簇比当前簇小，就将它移动到新簇中。 - 如果来自其他簇（或任何距离更短的簇）有交换提议，则交换两个元素的簇分配（如果有多个提议，则选择改进最大的那一个）。 - 否则，标志着其他簇的交换提议。

簇的大小保持不变（+-ceil/floor差异），只有在估计有所改进时，物体才会从一个簇移动到另一个簇。因此，它应该像k-means一样收敛。但可能会慢一些（即需要更多的迭代）。我不知道这是否已被发布或实现。这只是我想尝试的方法（如果我想尝试k-means。还有更好的聚类算法）。

- Has QUIT--Anony-Mousse

4

阅读了这个问题和几个类似的问题后，我使用Elki教程上的python实现了相同大小的k-means https://elki-project.github.io/tutorial/same-size_k_means。该教程大多使用scikit-learn的K-Means实现常用方法和熟悉的API。

我的实现在这里： https://github.com/ndanielsen/Same-Size-K-Means 聚类逻辑在此函数中：_labels_inertia_precompute_dense()。

- Nate

3

有一种更加简洁的后处理方法，给定聚类中心。假设有N个项目，K个群集和最大群集大小S = ceil(N/K)。

创建一个元组列表(item_id, cluster_id, distance)
按距离排序元组
对于排序后的元组列表中的每个元素(item_id, cluster_id, distance)：
- 如果cluster_id中的元素数量超过了S，则不执行任何操作
- 否则，将item_id添加到群集cluster_id中。

这个运行时间为O(NK lg(N))，应该会产生与@larsmans解决方案相当的结果，并且更容易实现。伪代码如下：

dists = []
clusts = [None] * N
counts = [0] * K

for i, v in enumerate(items):
    dist = map( lambda x: dist(x, v), centroids )
    dd = map( lambda (k, v): (i, k, v), enumerate(dist) )
    dists.extend(dd)

dists = sorted(dists, key = lambda (x,y,z): z)

for (item_id, cluster_id, d) in dists:
    if counts[cluster_id] >= S:
        continue
    if clusts[item_id] == None:
        clusts[item_id] = cluster_id
        counts[cluster_id] = counts[cluster_id] + 1

- Łukasz Kidziński

2

最近我需要为一个不太大的数据集实现这个功能。我的答案虽然运行时间比较长，但是它保证会收敛到局部极值。

def eqsc(X, K=None, G=None):
    "equal-size clustering based on data exchanges between pairs of clusters"
    from scipy.spatial.distance import pdist, squareform
    from matplotlib import pyplot as plt
    from matplotlib import animation as ani    
    from matplotlib.patches import Polygon   
    from matplotlib.collections import PatchCollection
    def error(K, m, D):
        """return average distances between data in one cluster, averaged over all clusters"""
        E = 0
        for k in range(K):
            i = numpy.where(m == k)[0] # indeces of datapoints belonging to class k
            E += numpy.mean(D[numpy.meshgrid(i,i)])
        return E / K
    numpy.random.seed(0) # repeatability
    N, n = X.shape
    if G is None and K is not None:
        G = N // K # group size
    elif K is None and G is not None:
        K = N // G # number of clusters
    else:
        raise Exception('must specify either K or G')
    D = squareform(pdist(X)) # distance matrix
    m = numpy.random.permutation(N) % K # initial membership
    E = error(K, m, D)
    # visualization
    #FFMpegWriter = ani.writers['ffmpeg']
    #writer = FFMpegWriter(fps=15)
    #fig = plt.figure()
    #with writer.saving(fig, "ec.mp4", 100):
    t = 1
    while True:
        E_p = E
        for a in range(N): # systematically
            for b in range(a):
                m[a], m[b] = m[b], m[a] # exchange membership
                E_t = error(K, m, D)
                if E_t < E:
                    E = E_t
                    print("{}: {}<->{} E={}".format(t, a, b, E))
                    #plt.clf()
                    #for i in range(N):
                        #plt.text(X[i,0], X[i,1], m[i])
                    #writer.grab_frame()
                else:
                    m[a], m[b] = m[b], m[a] # put them back
        if E_p == E:
            break
        t += 1           
    fig, ax = plt.subplots()
    patches = []
    for k in range(K):
        i = numpy.where(m == k)[0] # indeces of datapoints belonging to class k
        x = X[i]        
        patches.append(Polygon(x[:,:2], True)) # how to draw this clock-wise?
        u = numpy.mean(x, 0)
        plt.text(u[0], u[1], k)
    p = PatchCollection(patches, alpha=0.5)        
    ax.add_collection(p)
    plt.show()

if __name__ == "__main__":
    N, n = 100, 2    
    X = numpy.random.rand(N, n)
    eqsc(X, G=3)

- user2341646

2

考虑使用一种递归贪心合并的方法——每个点开始作为一个单独的聚类，重复合并最接近的两个点，直到合并不超过最大大小。如果你别无选择，只能超过最大大小，则在本地重新进行聚类。这是一种回溯层次聚类的形式：http://en.wikipedia.org/wiki/Hierarchical_clustering

- sclv

1

看起来这是一个不错的开始。但是，你能定义一下“本地重新聚类”吗？谢谢。 - Pierre-David Belanger

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Fred Foo · Accepted Answer

这可能会有所帮助：使用 Lloyd's algorithm 获取 k 个聚类中心，并按其相关聚类的大小降序排列成数组。对于 i = 1 到 k-1，将属于聚类 i 中与任何其他聚类中心 j（i < j ≤ k）距离最小的数据点移动到 j 并重新计算聚类中心 i（但不重新计算聚类本身），直到聚类大小为 n / k。

此后处理步骤的复杂度为 O(k² n lg n)。