我正在寻找最快的算法，将地图上的点按距离分成大小相等的组。k-means 聚类算法看起来简单而有前途，但不会产生同样大小的组。
该算法是否有变体或允许所有集群的成员数量相等的不同算法？
问问题
46638 次
18 回答
17
这可能会奏效：应用劳埃德算法来获得k个质心。按数组中相关簇的降序大小对质心进行排序。对于i = 1 到k -1，将簇i中与任何其他质心j ( i < j ≤ k ) 距离最小的数据点推到j并重新计算质心i（但不要重新计算簇），直到集群大小为n / k。
此后处理步骤的复杂度为 O( k ² n lg n )。
于 2011-03-27T21:49:36.350 回答
6
ELKI数据挖掘框架有一个关于等大小 k-means的教程。
这不是一个特别好的算法，但它是一个足够简单的 k-means 变体，可以编写教程并教人们如何实现自己的聚类算法变体；显然有些人确实需要他们的集群具有相同的大小，尽管 SSQ 的质量会比常规的 k-means 更差。
在 ELKI 0.7.5 中，您可以选择此算法为tutorial.clustering.SameSizeKMeansAlgorithm.
于 2013-02-16T23:14:59.240 回答
5
您可以将距离视为定义加权图。相当多的图划分算法明确地基于尝试将图顶点划分为两组相等大小。例如，这出现在Kernighan-Lin 算法和使用拉普拉斯算子的谱图分区中。要获得多个集群，可以递归应用分区算法；在关于谱图分区的链接上有一个很好的讨论。
于 2011-03-28T10:02:18.570 回答
5
试试这个 k-means 变体：
初始化：
- 从数据集中随机选择
k中心，甚至更好地使用 kmeans++ 策略 - 对于每个点，计算到其最近的聚类中心的距离，并为此建立一个堆
- 从堆中提取点，并将它们分配给最近的集群，除非集群已经满了。如果是这样，计算下一个最近的集群中心并重新插入到堆中
最后，您应该有一个满足您对每个集群 +-1 相同数量的对象的要求的分区（确保最后几个集群也有正确的数量。第一个m集群应该有ceil对象，其余的正是floor对象。）
迭代步骤：
必要条件：每个集群的列表，其中包含“交换建议”（希望位于不同集群中的对象）。
E步：计算更新后的聚类中心，就像在常规 k-means 中一样
M步：遍历所有点（要么只有一个，要么全部在一批中）
计算离对象最近的集群中心/所有比当前集群更近的集群中心。如果是不同的集群：
- 如果其他集群小于当前集群，只需将其移动到新集群
- 如果有来自另一个集群（或任何距离更短的集群）的交换提议，则交换两个元素集群分配（如果有多个提议，则选择改进最大的一个）
- 否则，指示另一个集群的交换提议
集群大小保持不变（+- ceil/floor 差异），一个对象只从一个集群移动到另一个集群，只要它导致估计的改进。因此，它应该像 k-means 一样在某个点收敛。不过，它可能会慢一些（即更多的迭代）。
我不知道这是否已经发布或实施过。这正是我要尝试的（如果我要尝试 k-means。有更好的聚类算法。）
于 2012-01-10T20:42:31.200 回答
5
以防万一有人想在这里复制和粘贴一个简短的功能-基本上运行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
于 2020-09-14T14:23:39.100 回答
4
在阅读了这个问题和几个类似的问题之后，我使用https://elki-project.github.io/tutorial/same-size_k_means上的 Elki 教程创建了一个相同大小的 k-means 的 python 实现， 它利用了 scikit-learn 的 K - 表示大多数常用方法和熟悉的 API 的实现。
我的实现在这里找到： https ://github.com/ndanielsen/Same-Size-K-Means
在这个函数中可以找到聚类逻辑：_labels_inertia_precompute_dense()
于 2017-09-18T14:24:28.527 回答
4
一般来说，按距离将地图上的点分成大小相等的组在理论上是不可能完成的任务。因为将点分组为大小相等的组与按距离对集群中的点进行分组是冲突的。
看到这个情节：
有四点：
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)。因此不能同时满足集群和同等规模组的要求。
于 2015-11-17T09:51:08.620 回答
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 解决方案相当的结果，并且更容易实现。在伪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
于 2015-08-14T22:10:45.047 回答
2
考虑某种形式的递归贪心合并——每个点都从一个单例集群开始，并重复合并最近的两个，这样这样的合并不会超过最大值。尺寸。如果您别无选择，只能超过最大大小，则在本地重新集群。这是回溯层次聚类的一种形式：http ://en.wikipedia.org/wiki/Hierarchical_clustering
于 2011-03-27T22:12:15.880 回答
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)
于 2013-11-23T16:26:50.167 回答
1
2012 年 1 月添加：比后处理更好的是保持集群大小与它们的增长大致相同。
例如，为每个 X 找到 3 个最近的中心，然后将 X 添加到距离最佳的中心 - λ clustersize。
如果您的 k-means 聚类大小大致相等，则 k-means 之后的简单贪婪后处理可能就足够了。
（这近似于来自 k-means 的 Npt 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
于 2011-03-28T09:29:16.330 回答
0
还要查看对数据进行分区的 Kd 树，直到每个分区的成员小于作为算法输入的 BUCKET_SIZE。
这不会强制存储桶/分区的大小完全相同，但它们都将小于 BUCKET_SIZE。
于 2015-03-19T01:14:57.807 回答
0
我也一直在努力解决这个问题。但是，我意识到我一直使用错误的关键字。如果您希望点结果成员的数量相同，则您正在进行分组，而不是再进行聚类。我终于能够使用简单的 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
);
那么你需要做的是：
- 找到将成为您的起点的第一个坐标
- 查找距起点最近的坐标，按距离升序排列，按您首选成员的数量限制结果（在本例中为 400）
- 通过更新 group_id 列来更新结果
- 对其余数据执行 10 次以上 3 步，其中 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()
希望能帮助到你
于 2017-09-27T09:07:35.000 回答
0
我在存储库https://github.com/brand17/clusters_equal_size的答案中添加了大部分算法。
最有效的是投票最多的答案。
我开发了一些其他算法（投票最多的仍然是最好的）：
我修改了迭代交换建议——通过识别和消除直接循环而不仅仅是交换（它提高了一点效率）
我还开发了以下算法：通过有效地移动 Voronoi 图边界，迭代最近的质心对并在它们之间交换点，使点的数量相差不超过一个。
于 2021-09-29T14:57:08.353 回答
0
在聚类分配期间，还可以在距离上添加“频率惩罚”，这使得高频聚类更难获得额外的分数。这在“Frequency Sensitive Competitive Learning for Balanced Clustering on High-dimensional Hyperspheres - Arindam Banerjee 和 Joydeep Ghosh - IEEE Transactions on Neural Networks”中有所描述
http://www.ideal.ece.utexas.edu/papers/arindam04tnn.pdf
他们还有一个在线/流媒体版本。
于 2021-07-22T11:08:45.293 回答
-1
您想查看空间填充曲线，例如 z 曲线或希尔伯特曲线。您可以考虑使用空间填充曲线将 2 维问题简化为 1 维问题。尽管 sfc 索引只是二维数据的重新排序，而不是数据的完美聚类，但当解决方案不能满足完美聚类并且必须相当快地计算时，它可能很有用。
于 2011-03-27T21:51:12.707 回答