我在中有一些点，我想对这些点进行聚类，以便：
每个簇包含相同数量的元素。（假设集群的数量除以。）
每个集群在某种意义上都是“空间内聚的”，就像来自均值的集群一样。
很容易想到许多满足其中一个或另一个的聚类过程，但是有没有人知道同时获得两者的方法？
每个聚类具有相同数量的点的聚类过程？
机器算法验证
机器学习
聚类
k-均值
无监督学习
2022-01-27 04:19:38
4个回答
我建议分两步走：
获得对聚类中心的良好初始估计，例如使用硬或模糊 K 均值。
使用 Global Nearest Neighbor assignment 将点与聚类中心相关联：计算每个点与每个聚类中心之间的距离矩阵（只计算合理距离可以使问题更小），将每个聚类中心复制 X 次，求解线性分配问题。对于每个聚类中心，您将获得与数据点完全匹配的 X 个数据点，从而在全局范围内最小化数据点和聚类中心之间的距离。
请注意，您可以在第 2 步之后更新集群中心并重复第 2 步，以基本上运行每个集群具有固定点数的 K-means。尽管如此，首先获得一个好的初步猜测仍然是一个好主意。
试试这个 k-means 变体：
初始化：
- 从数据集中随机选择
k中心，甚至更好地使用 kmeans++ 策略 - 对于每个点，计算到其最近的聚类中心的距离，并为此建立一个堆
- 从堆中提取点，并将它们分配给最近的集群，除非集群已经满了。如果是这样，计算下一个最近的集群中心并重新插入到堆中
最后，您应该有一个满足您对每个集群 +-1 相同数量的对象的要求的分区（确保最后几个集群也有正确的数量。第一个m集群应该有ceil对象，其余的正是floor对象。）
迭代步骤：
必要条件：每个集群的列表，其中包含“交换建议”（希望位于不同集群中的对象）。
E步：计算更新后的聚类中心，就像在常规 k-means 中一样
M步：遍历所有点（要么只有一个，要么全部在一批中）
计算离对象最近的集群中心/所有比当前集群更近的集群中心。如果是不同的集群：
- 如果其他集群小于当前集群，只需将其移动到新集群
- 如果有来自另一个集群（或任何距离更短的集群）的交换提议，则交换两个元素集群分配（如果有多个提议，则选择改进最大的一个）
- 否则，指示另一个集群的交换提议
集群大小保持不变（+- ceil/floor 差异），一个对象只从一个集群移动到另一个集群，只要它导致估计的改进。因此，它应该像 k-means 一样在某个点收敛。不过，它可能会慢一些（即更多的迭代）。
我不知道这是否已经发布或实施过。这正是我要尝试的（如果我要尝试 k-means。有更好的聚类算法。）
一个好的起点可能是ELKI中的 k-means 实现，它似乎已经支持三种不同的初始化（包括 k-means++），作者说他们还希望有不同的迭代策略，以涵盖所有各种常见的模块化方式的变体（例如 Lloyd、MacQueen、...）。
最近我自己需要这个来处理一个不是很大的数据集。我的答案虽然运行时间相对较长，但可以保证收敛到局部最优值。
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)
这是一个优化问题。我们有一个开源 Java 库可以解决这个问题（集群中每个集群的数量必须在设定范围之间）。你需要你的总点数最多几千 - 不超过 5000 或可能 10000。
图书馆在这里：
https://github.com/PGWelch/territorium/tree/master/territorium.core
该库本身是针对地理/GIS 类型问题设置的 - 因此您将看到对 X 和 Y、纬度和经度、客户、距离和时间等的引用。您可以忽略“地理”元素并将其用作纯群集器。
您提供一组初始为空的输入集群，每个集群都有一个最小和最大目标数量。聚类器将使用基于启发式的优化算法（交换、移动等）将点分配给您的输入聚类。在优化中，它首先优先考虑将每个簇保持在其最小和最大数量范围内，然后最小化簇中所有点与簇中心点之间的距离，因此簇在空间上具有凝聚力。
您使用此接口为求解器提供点之间的度量函数（即距离函数）：
该指标实际上是为返回距离和“时间”而设计的，因为它是为基于旅行的地理问题而设计的，但对于任意聚类问题，只需将“时间”设置为零，将距离设置为您在之间使用的实际指标点。
你会在这个类中设置你的问题：
您的点将是“客户”，他们的数量将为 1。在客户类中，确保您设置 costPerUnitTime = 0 和 costPerUnitDistance=1，假设您在 TravelMatrix 返回的“距离”字段中返回您的公制距离。
有关运行求解器的示例，请参见此处：
其它你可能感兴趣的问题