基于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 算法具有通用性，對鐵路站房設備分組、線路區間內的設備分組匯聚、區間房屋的選址等都有一定的輔助設計作用。