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

Question

我正在寻找最快的算法，将地图上的点按距离分组为相同大小的组。 k-means clustering algorithm看起来很直接，很有前途，但不会产生同样大小的团体。

这个算法还有一个变体，或者是一个允许所有簇的成员数相等的变体？

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

Answer 1

这可能做的伎俩：适用Lloyd's algorithm获得ķ重心。按照数组中相关联的簇的大小对质心进行排序。对于我 = 1〜ķ -1，以最小的距离推数据点簇我到任何其他形心Ĵ（我 < Ĵ≤ķ）关闭以Ĵ并重新计算质心i（但不要重新计算该簇），直到簇大小为n/k。

这个后处理步骤的复杂度为O（ķ²ÑLGÑ）。

Answer 2

您想查看空间填充曲线，例如z曲线或希尔伯特曲线。我想到了一个空间填充曲线来将二维问题简化为一维问题。虽然sfc索引只是二维数据的重新排序，并不是数据的完美聚类，但当解决方案未满足完美集群并且计算速度相当快时，sfc索引可能非常有用。

Answer 3

考虑某种形式的递归贪婪合并 - 每个点开始为单例聚类，并重复合并最近的两个，这样合并不超过最大值。尺寸。如果您没有选择余地，但超过最大尺寸，则会在本地重新进行。这是回溯层次聚类的一种形式：http://en.wikipedia.org/wiki/Hierarchical_clustering

Answer 4

新增Jan 2012： 优于后处理将保留簇大小 大致随着他们的成长一样。
例如，为每个X找到最近的3个中心，然后将 添加到距离最近的中心 - - ＆lambda;簇的大小。

---

一个简单的后k均值贪婪的后期处理可以是足够好的，如果从k均值群集的大致相同大小的。
（这近似于从k均值该条约X的距离c矩阵的分配算法。）

人们可以迭代

diffsizecentres = kmeans(X, centres, ...) 
X_centre_distances = scipy.spatial.distance.cdist(X, diffsizecentres) 
    # or just the nearest few centres 
xtoc = samesizeclusters(X_centre_distances) 
samesizecentres = [X[xtoc[c]].mean(axis=0) for c in range(k)] 
... 

我会感到惊讶如果迭代改变中心多， 但它将取决于™。

关于您的Npoint Ncluster和Ndim有多大？

#!/usr/bin/env python 
from __future__ import division 
from operator import itemgetter 
import numpy as np 

__date__ = "2011-03-28 Mar denis" 

def samesizecluster(D): 
    """ in: point-to-cluster-centre distances D, Npt x C 
      e.g. from scipy.spatial.distance.cdist 
     out: xtoc, X -> C, equal-size clusters 
     method: sort all D, greedy 
    """ 
     # could take only the nearest few x-to-C distances 
     # add constraints to real assignment algorithm ? 
    Npt, C = D.shape 
    clustersize = (Npt + C - 1) // C 
    xcd = list(np.ndenumerate(D)) # ((0,0), d00), ((0,1), d01) ... 
    xcd.sort(key=itemgetter(1)) 
    xtoc = np.ones(Npt, int) * -1 
    nincluster = np.zeros(C, int) 
    nall = 0 
    for (x,c), d in xcd: 
     if xtoc[x] < 0 and nincluster[c] < clustersize: 
      xtoc[x] = c 
      nincluster[c] += 1 
      nall += 1 
      if nall >= Npt: break 
    return xtoc 

#............................................................................... 
if __name__ == "__main__": 
    import random 
    import sys 
    from scipy.spatial import distance 
    # http://docs.scipy.org/doc/scipy/reference/spatial.distance.html 

    Npt = 100 
    C = 3 
    dim = 3 
    seed = 1 

    exec("\n".join(sys.argv[1:])) # run this.py N= ... 
    np.set_printoptions(2, threshold=200, edgeitems=5, suppress=True) # .2f 
    random.seed(seed) 
    np.random.seed(seed) 

    X = np.random.uniform(size=(Npt,dim)) 
    centres = random.sample(X, C) 
    D = distance.cdist(X, centres) 
    xtoc = samesizecluster(D) 
    print "samesizecluster sizes:", np.bincount(xtoc) 
     # Npt=100 C=3 -> 32 34 34 

Answer 5

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

Answer 6

试试这个k均值变化：

初始化：

• 选择从数据集k中心随机的，甚至更好的使用K均值++战略
• 每个点，计算距离到其最近的集群中心，并为此堆构建一个堆，并将它们分配给最近的集群，除非集群已经是o verfull。如果是这样，计算下一个最近的聚类中心和重新插入堆

最后，你应该有你满足了+ -1相同数量的每个群集对象的要求paritioning（确保最后几簇也有正确的数量的第一m簇应具有ceil目的，其余完全相同floor对象）

迭代步骤：。

要件：用于与“交换建议”（对象中的每个簇的列表那更喜欢在广告中不同的集群）。

Ê步骤：计算所述更新的集群中心，作为在常规的k-means

中号步骤：迭代通过所有的点（或者只是一个，或所有在一个批次中）

最近的计算集群中心对比比当前集群更近的所有集群中心。如果它是一个不同的集群：

• 如果其他集群比当前群小，只是将其移动到新的集群
• 如果有来自其他集群交换提案（或用任何集群较低的距离），交换两个元素集群分配（如果有一个以上的报价，选择具有最大的改进）
• 否则，指示其他集群

的簇大小仍然是一个交换的建议不变（+ - 细胞/楼层差异），一个物体是只是从一个集群移动到另一个集群，只要它能够改善估计。因此它应该像k-means一样在某个点汇合。虽然它可能会稍微慢一点（即更多的迭代）。

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

Answer 7

我可以虚心地建议你试试这个项目ekmeans。

一个Java K-means聚类实现与在集群施加了相等的基数约束，而其余的尽可能空间凝聚力的一个可选的特殊等于选项。

它还没有实验性，所以请注意known bugs。

Answer 8

ELKI数据挖掘框架有一个tutorial on equal-size k-means。

这不是一个，特别是好的算法，但它是一个很容易的k-means变体，可以写一个教程，教人们如何实现自己的聚类算法的变体;显然有些人真的需要他们的群体具有相同的大小，虽然SSQ质量会比常规k均值差。

Answer 9

最近我自己需要一个不是很大的数据集。我的答案虽然运行时间相对较长，但能保证收敛到局部最优。

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) 

Answer 10

也期待在K-d树，直到每个分区的成员是小于BUCKET_SIZE其是输入到算法中的划分的数据。

这不会强制桶/分区的大小完全相同，但它们都会小于BUCKET_SIZE。

Answer 11

给定聚类质心有一个更清洁的后处理。设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溶液和更容易实现。在伪python

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 

Answer 12

在一般情况下，在地图上将点分成相同大小的组，按距离是理论上不可能的任务。因为将点分组到相同大小的组中与按距离按聚类分组点相冲突。

看到这样的情节： enter image description here

有四点：

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

如果我们这些点聚集为两个群集。显然，（A，B，C）将是第一类，D将是第二类。但是如果我们需要大小相同的组，（A，B）将会是一个集群，（C，D）将成为另一个集群。这违反了集群规则，因为C更靠近（A，B）的中心，但它属于集群（C，D）。因此集群和同等规模的团队的需求不能同时满足。

Answer 13

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

我实现这里找到： https://github.com/ndanielsen/Same-Size-K-Means

聚类逻辑在此功能中发现：_labels_inertia_precompute_dense()

Answer 14

我一直挣扎在如何解决过这个问题。但是，我意识到我这次使用了错误的关键字。如果你希望点结果成员的数量是相同的大小，你正在做一个分组，而不是集群了。我终于能够使用简单的python脚本和postgis查询来解决问题。

例如，我有一个名为tb_points的表，它具有4000个坐标点，并且您想将它分成10个相同大小的组，每个组将包含400个坐标点。下面是表结构的例子

CREATE TABLE tb_points (
    id SERIAL PRIMARY KEY, 
    outlet_id INTEGER, 
    longitude FLOAT, 
    latitide FLOAT, 
    group_id INTEGER 
); 

然后，你需要做的是：

1. 找到的第一个坐标，这将是你的出发点
2. 查询从您的出发点最近的坐标，按距离升序排序，将结果限制为您的首选成员的数量（在本例中为400）
3. 通过更新group_id列更新结果
4. 执行3个步骤的10倍以上为数据的其余部分，这GROUP_ID列仍然是NULL

这是在Python实现：

import psycopg2 

dbhost = '' 
dbuser = '' 
dbpass = '' 
dbname = '' 
dbport = 5432 

conn = psycopg2.connect(host = dbhost, 
     user = dbuser, 
     password = dbpass, 
     database = dbname, 
     port = dbport) 

def fetch(sql): 
    cursor = conn.cursor() 
    rs = None 
    try: 
     cursor.execute(sql) 
     rs = cursor.fetchall() 
    except psycopg2.Error as e: 
     print(e.pgerror) 
     rs = 'error' 
    cursor.close() 
    return rs 

def execScalar(sql): 
    cursor = conn.cursor() 
    try: 
     cursor.execute(sql) 
     conn.commit() 
     rowsaffected = cursor.rowcount 
    except psycopg2.Error as e: 
     print(e.pgerror) 
     rowsaffected = -1 
     conn.rollback() 
    cursor.close() 
    return rowsaffected 


def select_first_cluster_id(): 
    sql = """ SELECT a.outlet_id as ori_id, a.longitude as ori_lon, 
    a.latitude as ori_lat, b.outlet_id as dest_id, b.longitude as 
    dest_lon, b.latitude as dest_lat, 
    ST_Distance(CAST(ST_SetSRID(ST_Point(a.longitude,a.latitude),4326) 
    AS geography), 
    CAST(ST_SetSRID(ST_Point(b.longitude,b.latitude),4326) AS geography)) 
    AS air_distance FROM tb_points a CROSS JOIN tb_points b WHERE 
    a.outlet_id != b.outlet_id and a.group_id is NULL and b.group_id is 
    null order by air_distance desc limit 1 """ 
    return sql 

def update_group_id(group_id, ori_id, limit_constraint): 
    sql = """ UPDATE tb_points 
    set group_id = %s 
    where outlet_id in 
    (select b.outlet_id 
    from tb_points a, 
    tb_points b 
    where a.outlet_id = '%s' 
    and a.group_id is null 
    and b.group_id is null 
    order by ST_Distance(CAST(ST_SetSRID(ST_Point(a.longitude,a.latitude),4326) AS geography), 
    CAST(ST_SetSRID(ST_Point(b.longitude,b.latitude),4326) AS geography)) asc 
    limit %s) 
    """ % (group_id, ori_id, limit_constraint) 
    return sql 

def clustering(): 
    data_constraint = [100] 
    n = 1 
    while n <= 10: 
     sql = select_first_cluster_id() 
     res = fetch(sql) 
     ori_id = res[0][0] 

     sql = update_group_id(n, ori_id, data_constraint[0]) 
     print(sql) 
     execScalar(sql) 

     n += 1 

clustering() 

希望它能帮助