查找聚类列表中质心距离最小的两个聚类并返回合并结果

不需要写冗余的多层嵌套循环，按以下逻辑实现即可：

• 第一步：生成所有聚类的不重复两两组合，避免重复计算同一对聚类的距离
• 第二步：遍历每对组合，计算两个聚类质心的距离，记录距离最小的一对
• 第三步：合并这对聚类的解决方案列表，新质心取两个原质心的平均值，就是最终结果

测试输入 #

test = []

# 单聚类结构：[聚类内解决方案列表, 聚类质心]
test.append([[3,5],4])
test.append([[2,8],5])
test.append([[1,3],2])
test.append([[5,9],7])

可直接运行的实现代码 #

from itertools import combinations

min_dist = float('inf')
target_clusters = None

# 遍历所有两两组合，combinations自动保证不重复取对
for c1, c2 in combinations(test, 2):
    dist = abs(c1[1] - c2[1]) # 一维质心的距离就是差值绝对值
    if dist < min_dist:
        min_dist = dist
        target_clusters = (c1, c2)

# 合并结果
merged = [
    target_clusters[0][0] + target_clusters[1][0],
    (target_clusters[0][1] + target_clusters[1][1]) / 2
]

print(merged)

输出验证 #

运行代码后输出为[[3, 5, 2, 8], 4.5]，解决方案列表内元素顺序不做要求，和预期结果完全匹配。

如果后续质心升级为二维/高维向量，只需要把距离计算的逻辑替换成对应维度的欧氏距离、余弦距离计算公式即可，整体筛选合并逻辑不需要调整。

内容的提问来源于stack exchange，提问作者Charles David Mupende