具有相同簇大小的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() 

希望它能幫助