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

PythonRobotics 中的 k-means 二维对象聚类原理、源码解析与动态仿真【免费下载链接】PythonRoboticsPython sample codes and textbook for robotics algorithms.项目地址: https://gitcode.com/GitHub_Trending/py/PythonRobotics本篇文章聚焦 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最小化。其工作流程如下初始化簇标签为每个数据点随机分配一个簇标签label取值范围为0 ~ nc-1。计算初始簇中心对每个簇内的数据点坐标求平均得到初始质心。分配阶段update_clusters对每个数据点计算它到所有簇中心的欧氏距离将其重新分配到距离最近的簇并累计代价。更新阶段calc_centroid根据新一轮的簇成员重新计算各簇中心。收敛判断若本轮代价与上一轮代价之差小于阈值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这是本实现的核心入口。其签名与语义如下参数类型含义rxList[float]待聚类数据点的 x 坐标列表ryList[float]待聚类数据点的 y 坐标列表ncint期望划分的簇数量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_points10每个物体周围生成的点数rand_d3.0点云散布半径噪声幅度n_cluster2聚类簇数量与物体数一致sim_time15.0总仿真时长dt1.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) ...每一帧的执行步骤为更新物体位置update_positions让两个物体沿固定速度移动——物体 1 每帧位移(DX10.4, DY10.5)物体 2 每帧位移(DX2-0.3, DY2-0.5)源码第 121-133 行。生成观测点云calc_raw_data在每个物体中心周围以rand_d为幅度随机撒点模拟传感器噪声源码第 110-118 行。执行聚类对当帧点云调用kmeans_clustering得到两簇划分。可视化可选若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 地图、圆形/矩形拟合等章节。【免费下载链接】PythonRoboticsPython sample codes and textbook for robotics algorithms.项目地址: https://gitcode.com/GitHub_Trending/py/PythonRobotics创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考