基于LightGBM和TOPSIS法的城市軌道交通關鍵節點識別

李坤,劉杰*,郭建民,申永生,王喆

1.山東交通學院交通與物流工程學院,山東 濟南 250357;2.濟南軌道交通集團有限公司,山東 濟南 250014;3.杭州城市大腦有限公司,浙江 杭州 310020;4.濟南市規劃設計研究院,山東 濟南 250101

0 引言

截至2022年底,中國大陸地區共開通軌道交通線路308條,運營里程達10 287.45 km[1]。城市軌道交通是公共交通的重要組成部分,在居民日常出行與通勤中承擔著重要作用[2]。城市軌道線網中某節點發生故障,將嚴重危害整個網絡的安全運行[3]。為盡可能降低關鍵節點故障對軌道交通網絡的影響,快速、精確地識別城市軌道交通線網中的關鍵節點成為當前研究的熱點問題。

目前,國內外對關鍵節點識別的主要研究方法分為2類。第1類主要基于復雜網絡理論,考慮節點在網絡中的度、中心性與特征向量等指標,識別網絡中的關鍵節點:張晉等[4]基于復雜網絡理論,分析北京軌道交通網絡結構模型,識別其關鍵節點;陳錦渠等[5]分別基于站點度、站點介數及改進LeaderRank算法識別高鐵網絡中的關鍵節點;王德龍等[6]采用度表征各節點在機場網絡中的重要程度并進行排名,采用復雜網絡理論構建機場網絡級聯失效抗毀性評估模型;秦孝敏[7]采用復雜網絡理論及熵權法分析重慶軌道交通網絡的度、直徑和平均路徑長度等特性,尋找脆弱站點并加強防護;Wang等[8]采用信息熵模型構建多式聯運復合運輸網絡,通過改進的加權k殼模型識別關鍵節點;Yang等[9]提出結合人口密度的加權綜合指數,評估節點重要性,并用于定位軌道交通網絡中的樞紐站點;Zhang等[10]基于度中心性與接近中心性等復雜網絡特性指標,提出基于邊緣中介的節點收縮算法;Lai等[11]對比分析節點度、k殼層度與加權k殼層度鄰域識別法等,發現綜合考慮元素的加權k殼層度鄰域識別法效果最好。第2類是基于交通網絡特性,綜合探究交通網絡中的客流量、出行效率等建立關鍵節點識別模型:Sun等[12]基于節點度和介數考慮節點的客流強度,識別軌道交通網絡中的關鍵站點;胡映月等[13]綜合考慮網絡中的客流特性和線路的運輸承載結構,提出評估節點重要度的指標;徐敏[14]將軌道交通線路客流數據分別抽象為物理網絡和客流網絡,提出基于客流的軌道交通網絡節點重要度的定義和評價方法;李宗平等[15]提出結合進、出站客流與換乘客流的關鍵節點識別方法。上述研究均從復雜網絡理論和交通網絡運行性能方面識別交通網絡關鍵節點,未考慮軌道交通與城市空間布局、城市活力間的耦合關系。軌道交通站點在城市空間結構中的分布及站點周邊的城市活力信息在一定程度上表征該站點在軌道交通網絡中的重要性,如中央商務區(central business district,CBD)是城市經濟發展中樞,客流高度集聚,該區域的軌道交通站點一旦受到影響,將直接影響城市交通的正常運營[16]。現有研究多采用熵權法對指標賦權,但熵權法難以橫向考慮各指標間的關系,易受樣本影響導致權重失真。一些研究采用傳統的逼近理想解排序(technique for order preference by similarity to ideal solution,TOPSIS)法,但未考慮各評價指標對方案的不同貢獻程度。

本文通過引入站點的城市活力信息,結合機器學習算法,提出從橫向與縱向角度考慮各指標間關系、避免權重失真的綜合評價方法。構建考慮復雜網絡理論、交通網絡運行性能與城市活力信息的評價指標體系,基于輕量級梯度提升決策樹(light gradient boosting machine,LightGBM)機器學習算法改進TOPSIS法構建關鍵節點識別模型,以杭州軌道交通為例進行分析,驗證基于LightGBM和TOPSIS法的城市軌道交通關鍵節點識別模型的識別精度,為城市軌道交通安全有序運營提供良好支撐。

1 評價指標分析與量化

城市軌道交通網絡結構復雜、覆蓋范圍廣,與城市空間布局及其他系統密切相關,應綜合考慮各因素,建立科學、高精度的城市軌道交通網絡關鍵節點識別模型[17-20]。根據評價指標表征的網絡信息范圍分為全局指標與局部指標,全局指標包括介數中心性、接近中心性和客流量;局部指標包括度中心性、特征向量中心性和城市活力信息。

1.1 全局指標

介數中心性B11是網絡中通過某節點的最短路徑數,穿過節點的最短路徑越多,節點越重要,節點i的介數中心性

(1)

接近中心性B12是指通過計算網絡中某節點與其余節點的平均距離達到去特殊值的影響,節點i的接近中心性

(2)

式中dij為節點i、j間的最短路徑長度。

1.2 局部指標

節點度ki是指與某節點i的相鄰節點數[21],ki越大,在網絡中的影響力越高,度中心性越大,節點i的度中心性

B21(i)=ki/(N-1)。

(3)

節點重要性既與其相鄰的節點數有關,也與相鄰節點的重要性有關,通過特征向量中心性體現節點重要性,節點i的特征向量中心性

(4)

式中:E為N×N矩陣,λ為E的最大特征向量,aij為構成網絡的鄰接矩陣變量,CE(j)為節點j的度中心性。

用商業與商務辦公設施數表征城市活力信息。不同類型站點周邊的商業與商務辦公設施數不同,位于CBD的樞紐站點與換乘站點周邊的商業與商務辦公設施較多,而郊區或中心城外圍區域的普通站點周邊的商業與商務辦公設施較少。站點周圍的商業和商務辦公設施越多,客流量越大,站點在軌道交通網絡中的重要性較大。統計站點周邊的商業與商務辦公設施興趣點(point of interest,POI),篩選各站點周圍1 km范圍內的商業與商務辦公設施數,記為B23。

2 關鍵節點識別算法

根據評價指標的維度,將關鍵節點的評價方法分為單維和多維2類方法,前者指標體系較單一,識別精度較低,后者能綜合考慮指標特征,識別精度較高。樣本分類也會影響關鍵節點的識別精度,應均衡處理樣本數據,提高分類算法準確率。

2.1 Borderline-SMOTE算法

圖1 Borderline-SMOTE算法對樣本的分類示意圖

在人工少數類過采樣法(synthetic minority oversampling technique,SMOTE)基礎上改進的Borderline-SMOTE算法,將樣本分為A、B和C3類,A類為安全,近鄰樣本超過一半為少數類,B類為邊界,近鄰樣本超過一半為多數類,C類為噪聲,近鄰樣本全部為多數類。選擇最具代表性的邊界樣本合成新樣本,改善樣本的類別分布,有效避免過度擬合及類內混淆問題。Borderline-SMOTE算法對樣本的分類過程如圖1所示,主要包括4個步驟。

步驟1:計算某樣本ei與所有訓練樣本的歐氏距離,即n個近鄰。

步驟2:設在n個近鄰中有n′個屬于多數類樣本,0≤n′≤n。若n=n′,ei為噪聲樣本;若0≤n′

步驟3:計算ei′與ei的k近鄰,選擇l個近鄰與ei′進行線性插值得到新樣本

enew=ei+rjdj,j=1,2,…,l,

式中:dj為ei′與其l個近鄰的距離;rj為隨機數,rj∈[0,1]。

步驟4:新樣本與原樣本合并,得到新的訓練樣本T′。

2.2 LightGBM算法

LightGBM算法具有訓練速度快、內存消耗低和準確率高等優點[22]。采用LightGBM法改進TOPSIS法,可解決其忽略評價過程中各指標貢獻度不同的問題。

樣本數據集

D={(Xi,yi)|Xi={xi1,xi2,…,xis};yi={1,2,…,i}},

式中:Xi={xi1,xi2,…,xis}為第i個樣本的特征參數,其中s為參數個數;yi為第i個樣本的標簽。

第i個樣本的預測站點類型

式中:fk為獨立樹結構q中葉節點權重z組成的集合;K為樹的總數;Г為回歸樹數據空間,Γ={f(X)=wq(x)}(q:Rm→L,z∈RT),能將樣本映射到相應的葉節點L,m為特征數,T為葉子節點的數。

為分析預測準確度,計算LightGBM算法在地鐵站點類型預測的平均絕對百分比誤差

EA=(TP+TN)/(TP+TN+FP+FN)×100%,

式中:TP為實際為正類且預測結果為正類的站點,TN為實際為負類而預測結果為負類的站點,FP為實際為負類而預測結果為正類的站點,FN為實際為正類而預測結果為負類的站點。

通過LightGBM模型中的gain屬性和split屬性,從橫向與縱向2個角度綜合計算各特征的重要性。gain屬性G指每個分裂變量的信息增益,split屬性S指用特征劃分數據類型時所用特征次數,公式為:

式中:IL為節點I分裂后的左子樹,IR為I分裂后的右子樹,l(IL)為左子樹的個數,l(IR)為右子樹的個數,rm為第m個特征在訓練中被用的次數。

2.3 LightGBM-TOPSIS法

TOPSIS法可衡量評價方案與最優、最劣方案間的距離,最優方案是指方案的各屬性在所有方案中均最優;反之則為最劣方案,對所有方案進行排序可逼近理想解[23]。但TOPSIS法無法區分不同評價指標的貢獻度,熵權法難以橫向考慮各評價指標間的關系,二者均不適合分析具有多層次復合評價指標的城市軌道交通。本文將能從縱向與橫向為多層次評價指標客觀賦權的LightGBM算法與TOPSIS法結合識別城市軌道交通系統的關鍵節點。

正向化處理樣本數據,遵循數值越大越好的原則。假設某網絡的節點數為N,節點重要度指標有M個,各節點在該網絡中的指標值為xij(i=1,2,3,.…,N;j=1,2,3,…,M),構造初始決策矩陣

為消除量綱不同造成的影響,計算xij的標準化值

hij=(xij-minxij)/(maxxij-minxij),maxxij≠minxij。

采用網格調參函數尋找LightGBM模型最優參數,計算特征的gain屬性與split屬性,通過熵權法計算綜合權重ω,對標準化決策矩陣H進行加權,得到加權決策矩陣

R=(rij)N×M=(hijωj)N×M。

3 實例應用

3.1 算例建模

圖2 杭州城市規道交通網絡拓撲結構

以杭州城市軌道交通網絡為例,驗證基于LightGBM和TOPSIS法的城市軌道交通關鍵節點識別模型的識別精度。采用Space-L模型構建杭州城市軌道交通網絡拓撲結構,如圖2所示。站點代表網絡節點,邊代表線路區間[24],共有241個節點、261個區間。采集2022-06-13杭州城市軌道交通客流量數據,全天共計進站客流1 835 121人次,出站客流1 899 459人次,其中火車東站是進、出站客流最多的站點,分別為55 273、52 668人次;青西三路站是進、出站客流最少的站點,分別為50、54人次。部分站點的進、出站客流及商業與商務辦公設施如表1所示。

表1 部分站點客流量與商業與商務辦公設施

3.2 計算數據

表2部分站點評價指標標準化值

站點B11B12B113B213B21B22B23濱康路站0.240.660.080.070.600.270.14西興站 0.160.700.200.210.200.200濱和路站0.190.770.200.170.200.230.14建業路站0.000.350.160.1700.040誠業路站0.040.400.130.110.200.090.29偉業路站0.070.460.080.080.200.150.43

將杭州城市軌道交通站點根據通過的線路數分為普通站點(198個)、換乘站點(39個)和樞紐站點(4個)3類,普通站點只有1條線路通過,換乘站點有2條線路通過,樞紐站點有3條及以上線路通過。通過式(1)～(4)計算各站點的介數中心性、接近中心性、度中心性和特征向量中心性,與統計得到的客流量、商業與商務辦公設施數組成樣本數據,進行標準化處理,部分站點的評價指標標準化值如表2所示。由于樣本數據過少,易導致分類算法結果擬合性較差,在普通站點數據的最小值與最大值間震蕩,隨機產生新數據至600條,復制所有樞紐站點數據并隨機插入樣本數據集。采用Borderline-SMOTE算法均衡處理樣本數據集,過采樣率為100%,即平衡少數類樣本與多數類樣本的數量,設置近鄰個數為5,隨機種子為42。樣本均衡后數據分布如表3所示。

表3 樣本均衡前后對比

表4 LightGBM機器學習算法參數設置

將Borderline-SMOTE算法均衡后的樣本數據集按7：3比例劃分為訓練集與測試集,設置隨機種子為42,在訓練集訓練LightGBM機器學習算法,采用網格調參函數搜索最優參數,設置50個弱估計器。LightGBM機器學習算法參數設置如表4所示。

圖3 混淆矩陣

采用訓練后的LightGBM算法預測杭州城市規道交通各站點的類型,測試集的預測準確度為98.15%。通過混淆矩陣驗證算法的性能,基于LightGBM算法對樣本數據識別結果的混淆矩陣如圖3所示。

由圖3可知:有185個普通站點,2個被誤判為換乘站點;有166個換乘站點,2個被誤判為普通站點;有189個樞紐站點,2個被誤判的為換乘站點。采用熵權法分別求gain屬性和split屬性的權重,其中gain與split的信息熵與二者總信息熵的比分別為81%、19%。各評價指標的gain屬性、split屬性及權重如表5所示。

表5 各評價指標的權重

圖4 LightGBM-TOPSIS法識別的前15個關鍵節點

將各評價指標的權重代入TOPSIS法計算各節點的重要性并排序。目前研究多采用靜態識別方法,即僅按初始數據識別關鍵節點,忽略了某節點失效后剩余網絡結構、節點度等的變化。本文采用動態識別方法,每次識別僅取排序第1的節點,然后刪去此節點再重新計算節點度等更新樣本數據,重新進行節點重要性排序[25]。LightGBM-TOPSIS法識別的前15個關鍵節點如圖4所示。

3.3 結果分析

3.3.1 關鍵節點識別精度評價

采用刪除節點法衡量基于LightGBM-TOPSIS法的城市軌道交通關鍵節點識別模型的識別精度,若刪除關鍵節點后城市軌道交通網絡結構嚴重破環,性能急劇下降,說明關鍵節點的識別精度較高。采用最大連通子圖和網絡效率量化所識別的關鍵節點在網絡結構中的影響力,通過網絡結構變化趨勢衡量關鍵節點排序結果的準確性。

網絡效率是指網絡中信息的傳播速度,可評價網絡整體的通行能力及連通水平[27]。刪除節點后,節點間的路徑長度發生變化,網絡效率逐步減小,其減小的速度反映所刪除節點對網絡的破壞程度,網絡效率

式中V為節點集合。

3.3.2 情景分析

為驗證基于LightGBM-TOPSIS法的城市軌道交通關鍵節點識別模型的有效性,設置a、b 2組對照試驗:a組樣本數據僅采用B11、B12、B21、B224個單層次評價指標,分別采用熵權-TOPSIS法與LightGBM-TOPSIS法識別關鍵節點;b組樣本數據采用B11、B12、B13、B21、B22、B236個多層次評價指標,分別采用TOPSIS法、熵權-TOPSIS法與LightGBM-TOPSIS法識別關鍵節點。不同算法的關鍵節點識別結果如表6所示。由表6可知:a組試驗中2種算法識別出13個相同的關鍵節點,但僅前5個關鍵節點的排序一致;b組試驗中3種算法識別出11個相同的關鍵節點。

表6 不同算法的關鍵節點識別結果

圖5 蓄意攻擊后a組的與η變化結果

圖6 蓄意攻擊與隨機攻擊后b組的與η變化結果

根據網絡中節點動態失效過程可知:網絡攻擊首先瓦解城市中心的樞紐站,如錢江路站;其次切斷次中心與繞城環線的樞紐站,如鳳起路站與近江路站等;最后切斷次中心與郊區的換乘站,如中醫藥大學站與三壩站等。杭州軌道交通管理部門應加強對中心樞紐站與環線換乘站的保護。

4 結論

為提高城市軌道交通關鍵節點的識別精度,綜合考慮軌道交通站點的城市活力信息,結合復雜網絡理論與交通網絡運行性能,提出基于LightGBM改進TOPSIS法的城市軌道交通關鍵節點識別模型,以杭州城市軌道交通為例進行關鍵節點識別。采用蓄意攻擊與隨機攻擊,以動態方式刪除節點,通過網絡效率與最大連通子圖比例驗證基于LightGBM與TOPSIS法的城市軌道交通關鍵節點識別模型的有效性與識別精度。結果表明:在破壞網絡結構速度方面,基于LightGBM與TOPSIS法的城市軌道交通關鍵節點識別模型在刪除前5個關鍵節點時網絡效率與最大連通子圖比例下降約50%;在破壞網絡結構程度方面,刪除前15個關鍵節點時,網絡效率與最大連通子圖比例分別下降至25.61%、16.60%,軌道交通網絡基本完全破壞。

研究僅考慮城市軌道交通中的靜態客流,下一步應考慮城市軌道交通網絡在級聯失效的情況下,客流將會由于站點的失效轉而流向鄰近的其他站點,采用動態客流更能挖掘動態攻擊下的關鍵節點。