如何将N个2D对象划分为K大小组 实现组内平均距离最小化

是否可以不借助特殊库实现 #

完全可以。该需求的核心逻辑仅涉及基础的数值计算、遍历、排序操作，不需要依赖任何第三方聚类、数值计算类的特殊库，用编程语言自带的基础语法即可实现。

优化小提示：组内平均距离最小等价于组内所有点两两距离之和最小，优化过程中可以直接计算总距离省略除法步骤；如果只需要做距离比较，可直接使用平方欧氏距离省略开方操作，计算效率更高。

可行实现思路 #

根据你可接受的运行时间和效果要求，可以选择以下三种方案：

方案1：贪心启发式（最快，代码量最小） #

适合对运行速度要求极高、能接受局部最优结果的场景，N=150时毫秒级即可完成计算，代码逻辑如下：

• 预计算所有2D点两两之间的距离，存储为距离矩阵
• 初始化所有点为未分配状态
• 循环执行直到所有点分配完成：
  1. 从所有未分配点中，选出和其他未分配点平均距离最小的点作为当前分组的核心
  2. 从剩余未分配点中选出和该核心距离最近的 K-1 个点，和核心共同组成一个大小为K的分组
  3. 将该组所有点标记为已分配

方案2：约束版K-medoids（效果和速度平衡） #

适合想要更好的分组效果、能接受几秒内运行时间的场景，分组效果远好于纯贪心逻辑：

• 先计算总分组数 M = ceil(N / K)（如果要求所有分组严格为K，可提前对N做截断或者补虚拟点）
• 随机选M个未重复的2D点作为初始的簇中心（medoid，必须是现有样本点）
• 循环执行直到簇中心不再变化，或者达到预设的最大迭代次数（通常20-50次即可收敛）：
  1. 分配阶段：给每个未分配点计算到所有M个簇中心的距离，优先将距离最近的点分配到对应簇，直到每个簇满K个为止，剩余未分配的点补到不满的簇中
  2. 更新阶段：遍历每个簇的所有点，选出该簇内「作为中心时，簇内所有点到它的总距离最小」的点，替换为该簇的新中心

方案3：排序+动态规划（全局最优，运行时间稍长） #

如果要求尽可能得到全局最优结果、对运行时间要求宽松，可以选择该方案：

• 先对所有2D点做空间排序：比如先按x坐标升序排序，x相同的按y坐标升序排序，保证空间位置接近的点在排序后的序列中也相邻
• 定义DP数组 dp[i] 表示排序后的前i个点完成分组后的最小总组内距离，cost(a,b) 表示将排序后第a到第b个点分为一组的组内总距离
• 初始化 dp[0] = 0，其余dp值设为无穷大
• 遍历i从1到N，遍历j从max(0, i-K)到i-1，更新 dp[i] = min(dp[i], dp[j] + cost(j+1, i))
• 计算完成后回溯dp数组即可得到最优分组结果

内容的提问来源于stack exchange，提问作者Zooly92