PythonRobotics 中的 k-means 二维对象聚类：原理、源码解析与动态仿真

本篇文章聚焦 PythonRobotics 仓库 Mapping（建图）模块下的 k-means 对象聚类实现，讲解如何用 k-means 算法对二维点云进行对象聚类，并剖析其完整源码、收敛判据与动态目标追踪仿真流程。读完本文，你将掌握该实现的调用方式、核心类结构、参数调优要点，以及如何运行和验证这一经典聚类算法在机器人建图场景中的应用。

一、功能定位：Mapping 模块中的对象聚类

在机器人系统中，Mapping（建图）指机器人借助 LIDAR、相机等外部传感器理解周围环境、识别障碍物位置与形状的能力。本仓库的 Mapping 模块总览 明确指出，grid mapping 与机器学习算法在 Mapping 中被广泛使用，其中就包括「使用 k-means 算法的二维对象聚类（2D object clustering）」这一经典方案。

关联文档 k_means_object_clustering_main.rst 对它的定位非常简洁清晰：

This is a 2D object clustering with k-means algorithm.

即：这是一个基于 k-means 算法的二维对象聚类实现。它的典型应用场景是：传感器（如激光雷达）扫描得到一片散乱点云后，通过 k-means 将点云划分成若干个簇，从而把「一个物体」和「另一个物体」区分开，为后续的障碍物识别、目标追踪提供基础。本文档对应的可运行示例位于 Mapping/kmeans_clustering/kmeans_clustering.py，且该实现被 Mapping 模块的 toctree 正式收录为独立章节。

二、算法原理：k-means 聚类核心流程

k-means 是经典的划分式聚类算法，本实现的核心思想是：通过迭代调整簇中心（centroid），使每个数据点到其所属簇中心的距离总和（代价函数 cost）最小化。其工作流程如下：

1. 初始化簇标签：为每个数据点随机分配一个簇标签（label），取值范围为 0 ~ nc-1。
2. 计算初始簇中心：对每个簇内的数据点坐标求平均，得到初始质心。
3. 分配阶段（update_clusters）：对每个数据点，计算它到所有簇中心的欧氏距离，将其重新分配到距离最近的簇，并累计代价。
4. 更新阶段（calc_centroid）：根据新一轮的簇成员重新计算各簇中心。
5. 收敛判断：若本轮代价与上一轮代价之差小于阈值 DCOST_TH，或迭代次数达到上限 MAX_LOOP，则停止迭代。

其中欧氏距离使用 math.hypot 计算，对应源码 update_clusters 方法：

def update_clusters(self):
    cost = 0.0
    for ip in range(self.n_data):
        px = self.x[ip]
        py = self.y[ip]
        dx = [icx - px for icx in self.center_x]
        dy = [icy - py for icy in self.center_y]
        dist_list = [math.hypot(idx, idy) for (idx, idy) in zip(dx, dy)]
        min_dist = min(dist_list)
        min_id = dist_list.index(min_dist)
        self.labels[ip] = min_id
        cost += min_dist
    return cost

可以看到，每个点被归属到距离最近的簇中心，同时将最小距离累加到代价 cost 上返回，供外层判断收敛。

三、源码级解析：kmeans_clustering 函数与 Clusters 类

3.1 入口函数 kmeans_clustering(rx, ry, nc)

文档中通过 autofunction 自动引用了 Mapping.kmeans_clustering.kmeans_clustering.kmeans_clustering，这是本实现的核心入口。其签名与语义如下：

参数	类型	含义
rx	List[float]	待聚类数据点的 x 坐标列表
ry	List[float]	待聚类数据点的 y 坐标列表
nc	int	期望划分的簇数量（k 值）

返回值：Clusters 实例，包含最终的簇分配结果（labels）与各簇中心（center_x、center_y）。

其内部实现直接体现了「初始化 → 迭代优化」两段式流程：

def kmeans_clustering(rx, ry, nc):
    clusters = Clusters(rx, ry, nc)
    clusters.calc_centroid()

    pre_cost = float("inf")
    for loop in range(MAX_LOOP):
        cost = clusters.update_clusters()
        clusters.calc_centroid()

        d_cost = abs(cost - pre_cost)
        if d_cost < DCOST_TH:
            break
        pre_cost = cost

    return clusters

这里有几个值得注意的设计点：

• 随机初始化：初始标签由 random.randint 随机生成，因此同一次数据在不同次运行时可能得到不同的初始划分，这是 k-means 的固有特性，也是它可能收敛到局部最优的原因。
• 收敛判据：MAX_LOOP = 10 与 DCOST_TH = 0.1 定义在文件顶部的「k means parameters」区块（源码第 13-16 行），前者限制最大迭代轮数防止死循环，后者是代价变化量的收敛阈值。
• 代价单调下降：pre_cost 初始为 float("inf")，保证首轮迭代必然继续，之后每轮比较相邻两次迭代的代价差。

3.2 数据结构 Clusters 类

Clusters 类封装了聚类所需的所有状态与操作，其成员包括：

• x、y：原始数据点坐标（构造时传入）。
• n_data：数据点总数，等于 len(x)。
• n_label：簇数量（即 k 值）。
• labels：每个数据点的簇标签列表，初始为随机值。
• center_x、center_y：每个簇中心的坐标，初始为全 0。

类中定义了四个核心方法：

方法	作用
plot_cluster()	将每个簇的数据点用不同颜色绘制成散点图
calc_centroid()	计算每个簇内点的坐标均值作为新簇中心
update_clusters()	按最近距离重新分配标签并返回代价
_get_labeled_x_y(label)	取出指定标签对应的所有点坐标，供绘图与质心计算复用

其中 calc_centroid 的实现（源码第 79-84 行）体现了 k-means 中「簇中心 = 簇内点的均值」这一标准定义：

def calc_centroid(self):
    for label in set(self.labels):
        x, y = self._get_labeled_x_y(label)
        n_data = len(x)
        self.center_x[label] = sum(x) / n_data
        self.center_y[label] = sum(y) / n_data

注意这里使用 set(self.labels) 遍历实际存在的簇标签，即使某个簇在迭代中变为空簇，也能安全跳过。

四、动态对象聚类仿真：main() 完整流程

与静态聚类示例不同，本实现自带的 main() 构建了一个两个运动物体的动态聚类仿真场景，直观展示 k-means 在连续帧中持续追踪目标的能力。

4.1 仿真参数（源码第 139-146 行）

参数	默认值	含义
cx / cy	[0.0, 8.0]	两个物体中心的初始坐标
n_points	10	每个物体周围生成的点数
rand_d	3.0	点云散布半径（噪声幅度）
n_cluster	2	聚类簇数量，与物体数一致
sim_time	15.0	总仿真时长
dt	1.0	每帧时间步长

4.2 仿真循环

while time <= sim_time:
    print("Time:", time)
    time += dt

    # objects moving simulation
    cx, cy = update_positions(cx, cy)
    raw_x, raw_y = calc_raw_data(cx, cy, n_points, rand_d)

    clusters = kmeans_clustering(raw_x, raw_y, n_cluster)
    ...

每一帧的执行步骤为：

1. 更新物体位置：update_positions 让两个物体沿固定速度移动——物体 1 每帧位移 (DX1=0.4, DY1=0.5)，物体 2 每帧位移 (DX2=-0.3, DY2=-0.5)（源码第 121-133 行）。
2. 生成观测点云：calc_raw_data 在每个物体中心周围以 rand_d 为幅度随机撒点，模拟传感器噪声（源码第 110-118 行）。
3. 执行聚类：对当帧点云调用 kmeans_clustering，得到两簇划分。
4. 可视化（可选）：若 show_animation 为 True，则清空画布、绘制各簇散点与物体真实中心（红色圆点 "or"），并设置坐标范围 xlim(-2, 10)、ylim(-2, 10)；按下 Esc 键可随时退出仿真（源码第 159-168 行）。

这个仿真直观说明了 k-means 在动态场景中的价值：即使物体在运动、点云带噪声，聚类仍能逐帧正确区分两个目标，这正是其在机器人目标检测与追踪中的基础能力。

五、运行方式与单元测试验证

5.1 直接运行仿真

在仓库根目录执行以下命令即可启动动态聚类仿真（需要已按 requirements.txt 安装 matplotlib、numpy 等依赖）：

python Mapping/kmeans_clustering/kmeans_clustering.py

运行后会打印 start!!、逐帧的 Time: 信息，最后输出 Done。

5.2 单元测试

仓库为每个模块提供了对应的 pytest 测试。针对本模块的测试位于 tests/test_kmeans_clustering.py，其做法是关闭动画后完整跑一遍 main()，以验证聚类流程可正常执行：

import conftest
from Mapping.kmeans_clustering import kmeans_clustering as m


def test_1():
    m.show_animation = False
    m.main()

测试通过 tests/conftest.py 将仓库根目录加入 sys.path，从而能够以 Mapping.kmeans_clustering 的形式导入模块。运行方式：

pytest tests/test_kmeans_clustering.py

值得注意的是，测试中通过 m.show_animation = False 关闭了 GUI 动画，说明 show_animation 这一模块级开关是保证该实现可以在无图形环境（如 CI）中运行的关键设计。

六、参数调优指南

基于源码分析，可针对不同应用场景调整以下参数：

• nc（簇数量）：这是 k-means 最重要的超参数。本示例中与真实物体数一致设为 2。若传感器场景中物体数量未知，可能需要配合其他方法（如轮廓系数、肘部法则）预先估计 k 值。
• MAX_LOOP（最大迭代数）：默认 10。数据规模大、噪声强时可能需要增大，否则可能在未收敛时就停止；反之过大会增加每帧计算开销。
• DCOST_TH（收敛阈值）：默认 0.1。越小收敛判据越严格，聚类越精细但可能增加迭代次数。
• rand_d（点云散布幅度）：模拟传感器噪声水平。噪声越大，聚类边界越模糊；若两个物体间距小于 rand_d，聚类可能难以正确区分目标——这也是 k-means 基于距离划分的本质限制。
• n_points（每物体点数）：模拟点云密度，影响质心估计的稳定性。

七、小结

本文围绕 k-means object clustering 文档 展开，完整介绍了 PythonRobotics 中 k-means 二维对象聚类的算法原理、Clusters 类的源码实现、动态多目标仿真流程以及测试验证方式。该实现虽然代码精炼，却完整覆盖了 k-means 的核心环节——随机初始化、最近邻分配、质心更新与代价收敛判断，非常适合作为理解聚类算法在机器人建图/感知领域落地的入门示例。若需要进一步研究本仓库的建图相关内容，可继续阅读 Mapping 模块文档 中的射线投影栅格地图（ray casting grid map）、NDT 地图、圆形/矩形拟合等章节。