基于KMeans 的铁路电务设备布放辅助设计软件研究

吴绍华，赵 耀，张妍君

（中国铁路设计集团有限公司 电化电信工程设计研究院，天津 300251）

在设计阶段通过科学手段提高设计精度，从源头合理规划工程方案，对于提高工程质量、节约建设投资、降低运营成本、推动铁路高质量发展具有重要意义[1]。在电务设备（简称：设备）布放设计过程中，设计人员需要在图纸中布放设备，再布放连接设备与机房设备间的线缆，满足设备的供电、通信和连通需求，形成可行的技术方案，最后绘制设备连接系统图并编制工程量表。传统的设计方法需要设计人员手动布置设备，人为确认线缆路径，统计线缆的工程量，效率低且易出错。

当前，BFS （ Breadth First Search） 算法、Dijkstra 算法和A*算法等路径规划算法可实现线缆路径的自动规划及工程量计算[2-3]。但其主要针对点对点连接的场景，无法满足多设备复杂连接场景的需求。在铁路设备布放设计过程中，存在将终端设备分组，共用一路电缆供电的场景，此时设计人员需要对设备进行聚类处理，以组为单位进行线缆路径规划。传统的手动聚类方式效率低，难以得到最优方案。考虑到电缆的载流量标准，亟需研究适合铁路设备布放的聚类算法，基于设备位置数据实现自动聚类，并对聚类结果中每个簇的规模进行限制。

KMeans 是一种常用的无监督聚类算法。该算法通过指定聚类数K，可根据输入数据间的相似度，自动将数据划分为K个簇，并得到每个簇的簇心。KMeans 算法实现简单，适合输入数据没有标记且预先没有确定结果的情形，可用于根据设备位置坐标将设备分组。但其在应用过程中存在初始簇心随机选取导致聚类结果易陷入最优局部解等问题。由此，诞生了KMeans++和BiKmeans 等改进算法[4-5]，其可在一定程度上避免算法陷入局部最优解。为确定最佳聚类数，文献[6] 采用手肘法，计算不同K值时的SSE（Sum of Squares due to Error）指标并绘制分布折线图，选择折线拐点对应的K值作为最佳聚类数；文献[7]提出基于加权二分图的算法，通过定义评价数L，计算不同K值下的L值来确定最佳聚类值。上述方法可在一定程度上得到最佳聚类数，但需要计算不同K值时的聚类结果，步骤繁琐且自动化程度低。针对KMeans 算法无法限制聚类结果规模的问题，文献[8]提出的改进算法在将样本分配到每个簇前，先检查簇的规模，保证每个簇的样本总数不超过最大值，但依然需要事先指定聚类数；文献[9]使用了基于正交分解的收缩聚类算法，通过迭代处理可在聚类数未知时，实现带有最小规模限制的自动聚类，但无法限制最大规模。

综上所述，目前相关聚类算法的研究均无法较好地满足铁路设备布放设计的需求，而不同的分组结果导致配电设施设置、线缆敷设的数量有较大差异，直接影响工程投资。因此，将设备根据空间位置等特征进行聚类处理，进而依据聚类结果自动进行线缆路径规划，是研发设备布放辅助设计软件中需要深入研究的问题。

1 铁路设备布放聚类算法研究

1.1 BiKMeans_SC 算法概述

Kmeans++算法通过计算每个样本被选为初始簇心的概率，实现对簇心的科学选择；BiKMeans 算法通过对每次迭代过程中SSE 较大的簇进行二分处理，在一定程度上避免了直接随机初始化K个簇心给聚类结果带来的影响。在上述算法基础上，本文结合铁路设备布放设计的特殊聚类需求，提出了BiKMeans_SC 算法，通过给定规模限制最大值M和重复次数p，可自动完成对输入数据集X={x1,···,xn}的聚类处理，算法流程如图1 所示。

图1 BiKMeans_SC 算法流程

（1）给定输入值：待聚类数据集X、聚类结果的最大规模限制M和重复次数p。

（2）初始化空集合Xc，用来存储X中已经完成聚类的样本。

（3）对于待聚类数据集X，使用KMeans++方法初始化2 个簇心C={c1,c2}，具体方法为：

①随机选中数据集X={x1,···,xn}中的某个样本作为第一个簇心c1；

②逐个计算各样本xi距c1的欧式距离di,1；

③计算xi的被选中为簇心的概率p(xi)

④选择xi=argmaxp(xi) 作为簇心c2，加入到C中。

（4）对X使用KMeans 法进行聚类，具体方法为：

①分别计算X中每个样本xi至每个簇心cj的欧式距离d(xi,cj)，j=1，2，标记xi隶属簇λj=argmind(xi,cj)；

②基于 λj的每个样本xi，求取它们的平均值作为簇心cj的新值；

③重复①～②，直至全部簇心不再变化。

（5）判断每个簇 λj中样本总数n，若如n≤M，则 λj满足规模限制，将 λj中的每个样本添加到Xc中；若n＞M，则计算簇 λj的SSE 指标

式中，xi为 λj中的第i个样本；cj为 λj的簇心。选择SSE 指标最大的簇作为待聚类数据集，重复步骤（3），直至Xc包括X的所有元素。

（6）重复步骤（2）～（5）达到p次，则计算每次聚类结果所有簇的SSE 指标之和，选择值最小一次的聚类结果作为最终结果输出。

BiKMeans_SC 算法使用了与BiKMeans 同样的二分迭代方法，通过在每次迭代过程中检查每个簇的样本总数，将满足规模限制的簇提取出来，添加到聚类结果中，直至结果包含所有的输入数据。该算法无需事先指定聚类数，亦无需进行不同K值下聚类结果的计算，利用簇的规模限制条件实现了聚类数未知的情况下数据集的自动聚类。

BiKMeans_SC 算法参考KMeans++完成初始簇心的选取，并设置了重复次数p，对数据集多次处理，以每次聚类结果的SSE 为指标，选择最小的一次作为最终结果，最大程度避免了算法的随机性。

1.2 仿真验证

floor(t)表示不超过变量t的最大整数值，且是随机数，表示叠加在第i行输入数据上的噪声，σ为0.2。分别使用KMeans、KMeans++、BiKMeans、BiKMeans_SC 算法对矩阵A60×2进行聚类处理。其中，使用KMeans、KMeans++、BiKMeans 算法时，设定聚类数为20，使用BiKMeans_SC 算法时，设定M为3，p为10。以A60×2中第1 列值作为x，第2 列值作为y，不同算法得到的聚类结果及簇心分布如图2所示，图2 中每个圆代表一个簇。

图2 各算法聚类结果

由公式（3）可知，A中每行元素ai是行标i除以3 的整数商，叠加上扰动噪声r。A中共有60 行，可知理想结果为，将A分为20 个簇，每个簇中均含有3 个样本，得到的各算法的聚类结果如表1 所示。

表1 各算法聚类结果

由表1 可知，在指定划分为20 个簇的前提下，相对于经典KMeans 算法，KMeans++、BiKMeans 算法得到的簇的样本总数分布更贴近理想情况，SSE 指标值更低，比KMeans 算法聚类效果更优。BiKMeans_SC 算法在没有预先指定聚类数的情况下，自动将数据集划分为21 个簇，每个簇的样本总数均不超过3，接近理想情况，解决了聚类数未知时带有规模限制的聚类问题，且综合了KMeans++和BiKMeans 算法的优势，得到了更小的SSE 指标值。

2 辅助设计软件设计

2.1 数据集提取

设计人员通常在CAD 图纸中布放设备、标注线缆，完成设计工作。设备在图纸中的位置坐标即为真实环境位置的等比例映射，设备间相对位置关系与实际关系一致。本文使用ObjectARX 工具，提取所有待聚类设备在图纸中的平面坐标，形成一个二维数组。为方便数据处理及结果展示，需要对数据进行归一化处理，使所有设备坐标均处于[0,1]区间，将其作为输入数据集，同时，输入每个簇的规模最大值，基于BiKMeans_SC 算法，实现K值未知条件下的设备聚类。

2.2 线缆路径规划

在进行路径规划时，常使用邻接矩阵表述路径图。基于给定的路径图，进行线缆路径规划时，常用的路径搜索算法有BFS、Dijkstra 和A*算法。BFS是一种盲目搜寻算法，能找到最短路径但计算量较大；Dijkstra 算法考虑了顶点间的移动距离，对比BFS 算法能更快找到最短路径，但会计算起点至所有顶点的最短路径，造成计算资源的浪费；A*算法在Dijkstra 算法基础上进行改进，通过定义启发函数，辅助进行路径选择，可比Dijkstra 更快找到最短路径。本文使用优势最突出的A*算法进行线缆路径规划的实现。

A*算法中启发函数F的表达式为

式中，G为从起点s至某一指定顶点q 的移动距离，由路径图给定；H为从q 到目标点 t 的估算距离，需自行确定。H值必须小于从q 到 t 间的实际距离，常用的H计算公式有曼哈顿距离计算和欧式距离计算，以2 个二维顶点X=(x1,x2)、Y=(y1,y2) 为例：

曼哈顿距离计算式为

欧式距离计算式为

考虑到实际中线缆并不总是水平或垂直敷设的，使用曼哈顿距离公式计算得到的数值可能会超过两点间敷设线缆所需的实际长度，因此，本文选用欧式距离作为估算距离H的计算公式。以设备聚类结果中每个簇的中心点为终点，以机房配线间等为起点进行路径规划，并根据规范和实际情况，考虑线缆的余长预留。

2.3 软件开发

本文基于C#语言在Visual Studio 平台进行软件的开发[10]，实现设备聚类及线缆路径规划，软件运行流程如图3 所示。

图3 软件运行流程

3 实验验证

以某车站视频监控系统的设计过程为例，采用本文辅助设计软件，以摄像机的空间位置为测试数据进行聚类处理，并对摄像机电源线缆的路径进行自动规划。该车站的站房共2 层，布置了73 台不同类型的摄像机，站房首层建筑平面及摄像机的分布位置如图4 所示，图4 中的粉色及蓝色直线分别代表了地面和吊顶的线缆槽道。

图4 站房首层摄像机布置

受电源线允许通过的最大电流限制，最多4 台摄像机共用一路电源线。使用BiKMeans_SC 算法对摄像机的空间位置进行聚类处理，将摄像机在图纸中的横纵坐标归一化，作为x、y值，该x、y值与聚类结果如图5 所示，图5 中每个圆圈代表一个簇。可看出BiKMeans_SC 算法将73 组测试数据分为26 个簇，每个簇的样本总数均不超过4，实现了预期目标。

图5 摄像机空间位置聚类结果

根据图5 所示的摄像机分组结果，使用A*算法自动生成每组摄像机电源线缆的路径和长度，部分摄像机的线缆信息标注如图6 所示。

图6 部分摄像机线缆信息标注

最终，辅助设计软件设计的电源线缆总长度为1 996 m，相对于设计人员手工分组、手动测量得到的线缆长度2 600 m，使用本辅助设计软件节省了23.2%的线缆。根据设备的分组信息和计算得到的线缆信息，软件能自动生成如图7 所示的视频监控系统线缆连接示意图。

图7 视频监控系统线缆连接示意

本文设计的辅助设计软件在铁路多个站房视频监控系统的设计阶段进行了测试，试验结果均证明该软件能有效减少设计人员的工作量，精准控制线缆工程量，提高施工图设计质量。

4 结束语

针对聚类数未知且带有最大规模限制的铁路电务设备布放聚类需求，本文设计了BiKMeans_SC 算法对数据集进行聚类，通过仿真实验证明了该算法能切实完成聚类任务。利用BiKMeans_SC 算法和A*算法开发辅助设计软件，实现了平面设备的自动分组、线缆路径的自动规划、设备与线缆连接图的生成。

相对于传统的手动设计方式，本文软件能自动生成精准科学的设备分组结果和线缆工程量，减少了设计人员的工作量，提高了设计质量和效率，节省了工程投资。本文设计的BiKMeans_SC 算法具有通用性，对铁路站房设备分组、线路区间内的设备分组汇聚、区间房屋的选址等都有一定的辅助设计作用。