具有相等簇大小的K均值算法变化

Question

我正在寻找最快的算法,通过距离将地图上的点分组为相同大小的组.在K-均值聚类算法看起来简单的和有希望的,但不会产生同样大小的组.

是否存在此算法的变体或不同的算法,允许所有群集的成员数相等？

另请参见:对具有相同大小的k个簇中的n个点进行分组

Answer 1

以防万一有人想在这里复制并粘贴一个简短的函数 - 基本上运行 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

Answer 2

这可能会成功:应用Lloyd的算法来获得k质心.通过降低数组中关联簇的大小来对质心进行排序.对于我 = 1〜ķ -1,推数据点簇我以最小的距离,以任何其他形心Ĵ(我 < Ĵ ≤ ķ)关闭以Ĵ和重新计算质心我(但不重新计算群集),直到簇大小是n/k.

在这个后处理步骤的复杂度为O(ķ ² ñ LG Ñ).

Answer 3

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

看这个情节：

有四点：

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)。因此不能同时满足集群和同等大小组的要求。

Answer 4

您可以将距离视为定义加权图.相当多的图分区算法明确地基于尝试将图顶点分割成两组相等的大小.例如,这出现在Kernighan-Lin算法和使用拉普拉斯算子的谱图分割中.要获得多个集群,您可以递归地应用分区算法; 在频谱图分区的链接上有一个很好的讨论.

Answer 5

试试这个 k 均值变体：

初始化：

• 从数据集中随机选择k中心，或者使用 kmeans++ 策略更好
• 对于每个点，计算到其最近的聚类中心的距离，并为此构建一个堆
• 从堆中提取点，并将它们分配给最近的簇，除非簇已经满了。如果是，则计算下一个最近的簇中心并重新插入堆中

最后，您的分区应该满足每个集群 +-1 相同数量的对象的要求（确保最后几个集群也有正确的数量。第一个集群m应该有ceil对象，其余的正是floor对象。）

迭代步骤：

必备条件：每个集群的列表，其中包含“交换建议”（希望位于不同集群中的对象）。

E步骤：按照常规 k 均值计算更新的聚类中心

M步骤：迭代所有点（可以仅迭代一个点，也可以批量迭代所有点）

计算距离对象最近的聚类中心/比当前聚类更接近的所有聚类中心。如果是不同的集群：

• 如果其他簇比当前簇小，则将其移动到新簇
• 如果有来自其他簇（或任何距离较小的簇）的交换提议，则交换两个元素簇分配（如果有多个提议，则选择改进最大的一个）
• 否则，指示另一个集群的交换提案

簇大小保持不变（+- ceil/floor 差异），只要导致估计的改进，对象只会从一个簇移动到另一个簇。因此它应该像 k 均值那样在某个点收敛。但它可能会慢一些（即更多迭代）。

我不知道这是否已经发布或实施过。这正是我会尝试的（如果我会尝试 k-means。有更好的聚类算法。）

Answer 6

所述ELKI数据挖掘框架具有上大小相等的k均值教程.

这不是一个特别好的算法,但它是一个足够简单的k-means变体来编写教程并教人们如何实现他们自己的聚类算法变化; 并且显然有些人确实需要他们的集群具有相同的大小,尽管SSQ质量将比常规k均值更差.

在ELKI 0.7.5中,您可以选择此算法tutorial.clustering.SameSizeKMeansAlgorithm.