基于KMeans 的鐵路電務設備布放輔助設計軟件研究

吳紹華，趙 耀，張妍君

（中國鐵路設計集團有限公司 電化電信工程設計研究院，天津 300251）

在設計階段通過科學手段提高設計精度，從源頭合理規(guī)劃工程方案，對于提高工程質(zhì)量、節(jié)約建設投資、降低運營成本、推動鐵路高質(zhì)量發(fā)展具有重要意義[1]。在電務設備（簡稱：設備）布放設計過程中，設計人員需要在圖紙中布放設備，再布放連接設備與機房設備間的線纜，滿足設備的供電、通信和連通需求，形成可行的技術方案，最后繪制設備連接系統(tǒng)圖并編制工程量表。傳統(tǒng)的設計方法需要設計人員手動布置設備，人為確認線纜路徑，統(tǒng)計線纜的工程量，效率低且易出錯。

當前，BFS （ Breadth First Search） 算法、Dijkstra 算法和A*算法等路徑規(guī)劃算法可實現(xiàn)線纜路徑的自動規(guī)劃及工程量計算[2-3]。但其主要針對點對點連接的場景，無法滿足多設備復雜連接場景的需求。在鐵路設備布放設計過程中，存在將終端設備分組，共用一路電纜供電的場景，此時設計人員需要對設備進行聚類處理，以組為單位進行線纜路徑規(guī)劃。傳統(tǒng)的手動聚類方式效率低，難以得到最優(yōu)方案。考慮到電纜的載流量標準，亟需研究適合鐵路設備布放的聚類算法，基于設備位置數(shù)據(jù)實現(xiàn)自動聚類，并對聚類結(jié)果中每個簇的規(guī)模進行限制。

KMeans 是一種常用的無監(jiān)督聚類算法。該算法通過指定聚類數(shù)K，可根據(jù)輸入數(shù)據(jù)間的相似度，自動將數(shù)據(jù)劃分為K個簇，并得到每個簇的簇心。KMeans 算法實現(xiàn)簡單，適合輸入數(shù)據(jù)沒有標記且預先沒有確定結(jié)果的情形，可用于根據(jù)設備位置坐標將設備分組。但其在應用過程中存在初始簇心隨機選取導致聚類結(jié)果易陷入最優(yōu)局部解等問題。由此，誕生了KMeans++和BiKmeans 等改進算法[4-5]，其可在一定程度上避免算法陷入局部最優(yōu)解。為確定最佳聚類數(shù)，文獻[6] 采用手肘法，計算不同K值時的SSE（Sum of Squares due to Error）指標并繪制分布折線圖，選擇折線拐點對應的K值作為最佳聚類數(shù)；文獻[7]提出基于加權(quán)二分圖的算法，通過定義評價數(shù)L，計算不同K值下的L值來確定最佳聚類值。上述方法可在一定程度上得到最佳聚類數(shù)，但需要計算不同K值時的聚類結(jié)果，步驟繁瑣且自動化程度低。針對KMeans 算法無法限制聚類結(jié)果規(guī)模的問題，文獻[8]提出的改進算法在將樣本分配到每個簇前，先檢查簇的規(guī)模，保證每個簇的樣本總數(shù)不超過最大值，但依然需要事先指定聚類數(shù)；文獻[9]使用了基于正交分解的收縮聚類算法，通過迭代處理可在聚類數(shù)未知時，實現(xiàn)帶有最小規(guī)模限制的自動聚類，但無法限制最大規(guī)模。

綜上所述，目前相關聚類算法的研究均無法較好地滿足鐵路設備布放設計的需求，而不同的分組結(jié)果導致配電設施設置、線纜敷設的數(shù)量有較大差異，直接影響工程投資。因此，將設備根據(jù)空間位置等特征進行聚類處理，進而依據(jù)聚類結(jié)果自動進行線纜路徑規(guī)劃，是研發(fā)設備布放輔助設計軟件中需要深入研究的問題。

1 鐵路設備布放聚類算法研究

1.1 BiKMeans_SC 算法概述

Kmeans++算法通過計算每個樣本被選為初始簇心的概率，實現(xiàn)對簇心的科學選擇；BiKMeans 算法通過對每次迭代過程中SSE 較大的簇進行二分處理，在一定程度上避免了直接隨機初始化K個簇心給聚類結(jié)果帶來的影響。在上述算法基礎上，本文結(jié)合鐵路設備布放設計的特殊聚類需求，提出了BiKMeans_SC 算法，通過給定規(guī)模限制最大值M和重復次數(shù)p，可自動完成對輸入數(shù)據(jù)集X={x1,···,xn}的聚類處理，算法流程如圖1 所示。

圖1 BiKMeans_SC 算法流程

（1）給定輸入值：待聚類數(shù)據(jù)集X、聚類結(jié)果的最大規(guī)模限制M和重復次數(shù)p。

（2）初始化空集合Xc，用來存儲X中已經(jīng)完成聚類的樣本。

（3）對于待聚類數(shù)據(jù)集X，使用KMeans++方法初始化2 個簇心C={c1,c2}，具體方法為：

①隨機選中數(shù)據(jù)集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中樣本總數(shù)n，若如n≤M，則 λj滿足規(guī)模限制，將 λj中的每個樣本添加到Xc中；若n＞M，則計算簇 λj的SSE 指標

式中，xi為 λj中的第i個樣本；cj為 λj的簇心。選擇SSE 指標最大的簇作為待聚類數(shù)據(jù)集，重復步驟（3），直至Xc包括X的所有元素。

（6）重復步驟（2）～（5）達到p次，則計算每次聚類結(jié)果所有簇的SSE 指標之和，選擇值最小一次的聚類結(jié)果作為最終結(jié)果輸出。

BiKMeans_SC 算法使用了與BiKMeans 同樣的二分迭代方法，通過在每次迭代過程中檢查每個簇的樣本總數(shù)，將滿足規(guī)模限制的簇提取出來，添加到聚類結(jié)果中，直至結(jié)果包含所有的輸入數(shù)據(jù)。該算法無需事先指定聚類數(shù)，亦無需進行不同K值下聚類結(jié)果的計算，利用簇的規(guī)模限制條件實現(xiàn)了聚類數(shù)未知的情況下數(shù)據(jù)集的自動聚類。

BiKMeans_SC 算法參考KMeans++完成初始簇心的選取，并設置了重復次數(shù)p，對數(shù)據(jù)集多次處理，以每次聚類結(jié)果的SSE 為指標，選擇最小的一次作為最終結(jié)果，最大程度避免了算法的隨機性。

1.2 仿真驗證

floor(t)表示不超過變量t的最大整數(shù)值，且是隨機數(shù)，表示疊加在第i行輸入數(shù)據(jù)上的噪聲，σ為0.2。分別使用KMeans、KMeans++、BiKMeans、BiKMeans_SC 算法對矩陣A60×2進行聚類處理。其中，使用KMeans、KMeans++、BiKMeans 算法時，設定聚類數(shù)為20，使用BiKMeans_SC 算法時，設定M為3，p為10。以A60×2中第1 列值作為x，第2 列值作為y，不同算法得到的聚類結(jié)果及簇心分布如圖2所示，圖2 中每個圓代表一個簇。

圖2 各算法聚類結(jié)果

由公式（3）可知，A中每行元素ai是行標i除以3 的整數(shù)商，疊加上擾動噪聲r。A中共有60 行，可知理想結(jié)果為，將A分為20 個簇，每個簇中均含有3 個樣本，得到的各算法的聚類結(jié)果如表1 所示。

表1 各算法聚類結(jié)果

由表1 可知，在指定劃分為20 個簇的前提下，相對于經(jīng)典KMeans 算法，KMeans++、BiKMeans 算法得到的簇的樣本總數(shù)分布更貼近理想情況，SSE 指標值更低，比KMeans 算法聚類效果更優(yōu)。BiKMeans_SC 算法在沒有預先指定聚類數(shù)的情況下，自動將數(shù)據(jù)集劃分為21 個簇，每個簇的樣本總數(shù)均不超過3，接近理想情況，解決了聚類數(shù)未知時帶有規(guī)模限制的聚類問題，且綜合了KMeans++和BiKMeans 算法的優(yōu)勢，得到了更小的SSE 指標值。

2 輔助設計軟件設計

2.1 數(shù)據(jù)集提取

設計人員通常在CAD 圖紙中布放設備、標注線纜，完成設計工作。設備在圖紙中的位置坐標即為真實環(huán)境位置的等比例映射，設備間相對位置關系與實際關系一致。本文使用ObjectARX 工具，提取所有待聚類設備在圖紙中的平面坐標，形成一個二維數(shù)組。為方便數(shù)據(jù)處理及結(jié)果展示，需要對數(shù)據(jù)進行歸一化處理，使所有設備坐標均處于[0,1]區(qū)間，將其作為輸入數(shù)據(jù)集，同時，輸入每個簇的規(guī)模最大值，基于BiKMeans_SC 算法，實現(xiàn)K值未知條件下的設備聚類。

2.2 線纜路徑規(guī)劃

在進行路徑規(guī)劃時，常使用鄰接矩陣表述路徑圖?；诮o定的路徑圖，進行線纜路徑規(guī)劃時，常用的路徑搜索算法有BFS、Dijkstra 和A*算法。BFS是一種盲目搜尋算法，能找到最短路徑但計算量較大；Dijkstra 算法考慮了頂點間的移動距離，對比BFS 算法能更快找到最短路徑，但會計算起點至所有頂點的最短路徑，造成計算資源的浪費；A*算法在Dijkstra 算法基礎上進行改進，通過定義啟發(fā)函數(shù)，輔助進行路徑選擇，可比Dijkstra 更快找到最短路徑。本文使用優(yōu)勢最突出的A*算法進行線纜路徑規(guī)劃的實現(xiàn)。

A*算法中啟發(fā)函數(shù)F的表達式為

式中，G為從起點s至某一指定頂點q 的移動距離，由路徑圖給定；H為從q 到目標點 t 的估算距離，需自行確定。H值必須小于從q 到 t 間的實際距離，常用的H計算公式有曼哈頓距離計算和歐式距離計算，以2 個二維頂點X=(x1,x2)、Y=(y1,y2) 為例：

曼哈頓距離計算式為

歐式距離計算式為

考慮到實際中線纜并不總是水平或垂直敷設的，使用曼哈頓距離公式計算得到的數(shù)值可能會超過兩點間敷設線纜所需的實際長度，因此，本文選用歐式距離作為估算距離H的計算公式。以設備聚類結(jié)果中每個簇的中心點為終點，以機房配線間等為起點進行路徑規(guī)劃，并根據(jù)規(guī)范和實際情況，考慮線纜的余長預留。

2.3 軟件開發(fā)

本文基于C#語言在Visual Studio 平臺進行軟件的開發(fā)[10]，實現(xiàn)設備聚類及線纜路徑規(guī)劃，軟件運行流程如圖3 所示。

圖3 軟件運行流程

3 實驗驗證

以某車站視頻監(jiān)控系統(tǒng)的設計過程為例，采用本文輔助設計軟件，以攝像機的空間位置為測試數(shù)據(jù)進行聚類處理，并對攝像機電源線纜的路徑進行自動規(guī)劃。該車站的站房共2 層，布置了73 臺不同類型的攝像機，站房首層建筑平面及攝像機的分布位置如圖4 所示，圖4 中的粉色及藍色直線分別代表了地面和吊頂?shù)木€纜槽道。

圖4 站房首層攝像機布置

受電源線允許通過的最大電流限制，最多4 臺攝像機共用一路電源線。使用BiKMeans_SC 算法對攝像機的空間位置進行聚類處理，將攝像機在圖紙中的橫縱坐標歸一化，作為x、y值，該x、y值與聚類結(jié)果如圖5 所示，圖5 中每個圓圈代表一個簇?？煽闯鯞iKMeans_SC 算法將73 組測試數(shù)據(jù)分為26 個簇，每個簇的樣本總數(shù)均不超過4，實現(xiàn)了預期目標。

圖5 攝像機空間位置聚類結(jié)果

根據(jù)圖5 所示的攝像機分組結(jié)果，使用A*算法自動生成每組攝像機電源線纜的路徑和長度，部分攝像機的線纜信息標注如圖6 所示。

圖6 部分攝像機線纜信息標注

最終，輔助設計軟件設計的電源線纜總長度為1 996 m，相對于設計人員手工分組、手動測量得到的線纜長度2 600 m，使用本輔助設計軟件節(jié)省了23.2%的線纜。根據(jù)設備的分組信息和計算得到的線纜信息，軟件能自動生成如圖7 所示的視頻監(jiān)控系統(tǒng)線纜連接示意圖。

圖7 視頻監(jiān)控系統(tǒng)線纜連接示意

本文設計的輔助設計軟件在鐵路多個站房視頻監(jiān)控系統(tǒng)的設計階段進行了測試，試驗結(jié)果均證明該軟件能有效減少設計人員的工作量，精準控制線纜工程量，提高施工圖設計質(zhì)量。

4 結(jié)束語

針對聚類數(shù)未知且?guī)в凶畲笠?guī)模限制的鐵路電務設備布放聚類需求，本文設計了BiKMeans_SC 算法對數(shù)據(jù)集進行聚類，通過仿真實驗證明了該算法能切實完成聚類任務。利用BiKMeans_SC 算法和A*算法開發(fā)輔助設計軟件，實現(xiàn)了平面設備的自動分組、線纜路徑的自動規(guī)劃、設備與線纜連接圖的生成。

相對于傳統(tǒng)的手動設計方式，本文軟件能自動生成精準科學的設備分組結(jié)果和線纜工程量，減少了設計人員的工作量，提高了設計質(zhì)量和效率，節(jié)省了工程投資。本文設計的BiKMeans_SC 算法具有通用性，對鐵路站房設備分組、線路區(qū)間內(nèi)的設備分組匯聚、區(qū)間房屋的選址等都有一定的輔助設計作用。