基于改進模糊聚類算法的地鐵站點重要性分析

張 玲， 郭進利

(上海理工大學 管理學院， 上海 200093)

地鐵是城市公共交通中最重要的一環，與其他交通方式相比有著快速便捷、載客量大、準時等優越性，成為可以解決大城市區域交通需求的關鍵方案[1]。隨著城市地鐵的發展，世界上的許多城市對地鐵系統的依賴日益增長。截至2019年6月，上海已有17路線、415座車站、累計705 km地鐵運營線投入使用，運營線網規模位居世界前列(含磁懸浮)。

城市地鐵網絡中的節點因其重要度不同，遭受攻擊后失效導致的網絡運行效率的降低程度有所不同。已有研究表明，交通網絡的網絡抗毀性是由關鍵節點決定的[2]。因此識別地鐵網絡中對網絡運行效率起著重要作用的關鍵節點，加強對關鍵節點的保護和管控，增強其抗風險能力，對于提高地鐵網絡的抗風險能力有重要意義。目前，已有許多學者對地鐵網絡和復雜網絡節點重要度評價進行了深入研究。在對波士頓地鐵網初步的研究中，Latora等[3]發現其具有小世界特性。Sienkiewicz等[4]研究了22個所在波蘭的城市軌道交通的網絡特性，從而分析得出波蘭軌道交通網絡呈現出小世界特性和分層組織的結論。Meng等[5]用Space-L和Space-P兩種模型建立深圳市地鐵網絡，構建兩種模型的節點重要度評價模型，對兩種模型的抗毀性進行對比，結果表明P模型比L模型具有更強的整體抗攻擊能力，更有利于網絡的彈性。郭曉玲等[6]運用二次約束二次規劃模型，針對賦權網絡，綜合考慮節點移除后對網絡的整體結構和功能的影響，給出了計算網絡連通性的新測度，即一步連續和兩步連續。韓紀彬等[7]采用了空間 L 方法系統分析其網絡特征參量，從最大連通子圖的相對大小、網絡全局效率和網絡局部效率等指標分析網絡的可靠性。許海霖等[8]結合垂面距離和灰色關聯度綜合評價方案，用局部熵代替整體熵改進TOPSIS算法，測算了地鐵網絡的節點重要度。王梓行等[9]創新性地重新定義了復雜網絡的冗余度，并重新定義的冗余度量化了網絡抗毀性，利用節點刪除法對節點重要度進行了評估。

目前對地鐵網絡節點重要程度的評價主要依賴于刪除節點，考察節點失效對網絡整體效率的影響，且在評價節點時多采用重要度排序，但是在交通網絡中，對一個節點的評價大多為“關鍵”“重要”“一般”等表達，研究者難以確定關鍵節點的數量，選擇重要度排序前K個節點作為關鍵節點，導致關鍵節點判別不準確。為準確判斷軌道交通的關鍵節點，本文選取節點介數、接近中心性和特征向量中心性作為重要性評價指標，研究一種基于特征加權的模糊聚算法的節點重要性評價方法，適用于地鐵網絡。

1 城市地鐵網絡構建及指標選取

1.1 城市地鐵網絡構建

城市地鐵網絡建模是指將地鐵按照一定方法抽象為復雜網絡拓撲結構，從而方便對復雜網絡的各個統計指標進行分析和計算，為節點重要性分析提供模型基礎[10]。為直接反映站點之間的連接關系，采用Space-L方法來構建城市地鐵網絡拓撲結構：將站點抽象為節點，相鄰站點之間的軌道線路抽象為邊，構建城市地鐵網絡的自然拓撲結構，如圖1所示。

圖1 Space-L法構建網絡拓撲圖

1.2 指標選取

從網絡拓撲結構出發，綜合考慮了節點自身的性質及其鄰居節點的性質，最終選取了節點的介數、接近中心性和特征向量中心性作為評價節點重要性的依據。在描述網絡中某一個節點時，節點介數描述了該節點進行最短路徑傳輸信息的控制能力，接近中心性描述了網絡中所有節點到該節點的效率，特征向量中心性反映了與該節點相鄰節點的重要性。

1)介數：以經過節點i的最短路徑數目來刻畫節點重要性的指標稱為介數，它描述了節點i對于網絡中節點對之間沿著最短路徑傳輸信息的控制能力，即

(1)

式中：σst(i)表示節點s和節點t經過節點i的最短路徑數；σst表示節點s和節點t之間的最短路徑數。在現實出行中，人們往往選擇最短路徑。因此，通過節點的最短路徑越多，節點越重要。

2)接近中心性：對于網絡中的任意節點i，可以計算該節點到網絡中所有節點的距離的平均值，平均距離越小，代表節點i更接近其他節點，將平均距離的倒數定義為節點的接近中心性，即

(2)

3)特征向量中心性：特征向量中心性的基本思想是一個節點的重要性既取決于其鄰居節點的數量，也取決于其鄰居節點的重要性。本文將特征向量中心性定義為節點的鄰居節點的度值累加，即

(3)

式中：Vi為節點空間V的子空間，表示節點i的鄰居節點集合；kj為節點j的度值。由于特征向量中心性的計算方法既考慮到了節點i鄰居節點的數量，即度值，又考慮到了鄰居節點的質量，為了減少指標之間的相關性，本文不再引入度值作為評價指標。

2 基于k-means和熵權法加權的改進FCM算法

不同于聚類算法的硬化分，嚴格地將個體歸劃到某一類去，模糊聚類將個體以一定的隸屬度歸于某一類，實現軟化分。在交通網絡中，對節點的描述多是“關鍵”“重要”等模糊性表達，研究者難以對其進行明確的區分，因此模糊聚類更能客觀描述節點重要性程度。

基于上述結論，選擇采用模糊C-均值(FuzzyC-means)對節點進行模糊聚類。FCM算法是利用目標函數來反映聚類效果，利用約束條件解決非線性問題，目標函數進行不斷迭代，直到取得極小值。在模糊聚類的思想中，每一個樣本不是嚴格地歸為某一類，而是以一定的隸屬度屬于某一類。為了優化FCM算法，從而進一步提升FCM算法在地鐵網絡中的適用性，本文采用k-means和熵權法對FCM算法進行改進。

2.1 基于k-means的初始聚類中心確定方法

FCM算法對初始聚類中心十分敏感。初始聚類中心的選取直接影響算法迭代次數和計算時間，算法極容易因選擇了不恰當的初始聚類中心而陷入局部最優解[2]。

k-means作為動態聚類法，具有原理簡明、熟練快速、聚類效果較優等優勢[12]，是一種最為廣泛使用的聚類方法，且可以得到與FCM相似的聚類中心，因此在對數據進行模糊聚類之前，先使用k-means 聚類，確定初始聚類中心，不僅可以大大降低迭代次數，而且可以降低FCM陷入局部最優解的可能性。

2.2 特征加權的FCM算法

為了優化傳統FCM算法，除了通過k-means動態聚類法確定初始聚類中心，減少迭代步驟之外，也重新定義了樣本與聚類中心之間的距離。

考慮到節點介數、接近中心性和特征向量中心性3個指標在重要性評價上的權重有所不同，熵權法是一種客觀賦權方法，指標的變異程度越小，其反映的信息量就越少，所對應的權值應該就越低，因此在傳統FCM算法基礎上使用熵權法引入權重。

特征加權后的FCM算法與傳統FCM算法的區別體現在樣本xj與聚類中心ci之間的距離變為

(4)

式中：wq為相應指標的權重；xjq表示第j個樣本的第q項指標；ciq表示第i個聚類中心第q項指標；m為模糊加權指數，取值范圍為1.5～2.5。因此，改進FCM算法目標函數和約束條件為

(5)

式中：c為別個數；uji表示第j個樣本屬于第i類的隸屬度，滿足0≤uji≤1且uj1+uj2+…+ujc=1。

改進FCM算法的步驟如下：

步驟1l=0，通過k-means算法得到初始聚類中心C(0)，確定初始隸屬度矩陣U(0)，通過熵權法計算的指標權重為W。

步驟2l=l+1，更新第l步中的聚類中心C(l)，即

(6)

步驟3修正隸屬度矩陣U(l)，計算目標函數J(l)，即

(7)

(8)

步驟4對給定目標函數終止容限ε或最大迭代步長Lmax，當|J(l)-J(l-1)|<ε或l>Lmax時，終止迭代，否則l=l+1，轉步驟2。

2.3 算法檢驗

為了判斷FCM算法的準確性，采用誤差率交叉估計法進行結果驗證[12]。首先從N個數據中任意去掉一個，對其他數據進行FCM聚類，然后用所得的聚類中心對刪除的樣本進行判別。重復上述步驟，直到所有樣本均被檢驗，與原FCM聚類結果進行對比，求得誤判率。

3 實證分析

選取上海地鐵網絡作為研究對象，以截至2019年6月的地鐵站點及線路為例，驗證評價方法的有效性。

3.1 方法應用

將上海地鐵實際網絡抽象為以站點為節點、站點之間的軌道為連邊的Space-L網絡模型，由于地鐵相鄰兩站之間的出行時間多為2～3 min，故不考慮站點之間的距離，建立無向無權復雜網絡模型，如圖2所示。

圖2 上海地鐵Space-L模型

由Gephi軟件的結果可知，節點度最大的點為世紀大道，度值為8，上海地鐵網絡平均度為2.329，大多數站點的度值為2，即與同一條線路上的相鄰兩站構成鄰居關系，網絡直徑為44。平均路徑長度為15.893，網絡平均聚類系數為0.026，上海地鐵Space-L網絡不構成小世界網絡。

通過MATLAB計算出節點介數、接近中心性和特征向量中心性3個指標，并對所有的數據進行標準化處理。

通過熵權法對網絡節點重要性指標進行加權，得到3個指標(節點介數、接近中心性、特征向量中心性)的權重矩陣為W={0.425 7 0.165 8 0.408 5}。

3.2 改進FCM算法的應用結果

將節點重要性分為5個級別，分別為“關鍵”“次關鍵”“重要”“較為重要”“一般”。在應用算法的過程中，取聚類類別數c=5，終止容限ε=0.001，模糊聚類指數m=2，最大迭代次數Lmax=1 000，通過改進FCM算法得出的聚類結果如圖3所示。

圖3 改進FCM聚類結果可視化

由于節點介數、接近中心性和特征向量中心性均為正向指標，即指標數值越大，節點越重要，因此將最終聚類中心的3項指標加權和進行降序排列，將類別依次記為“關鍵”“次關鍵”“重要”“較為重要”“一般”，改進FCM算法結果統計如圖4所示。

圖4 上海地鐵站點重要性匯總

由圖4可知，用改進FCM算法得出了上海地鐵的24個關鍵節點、52個次關鍵節點、62個重要節點、167個較為重要節點和41個一般節點。對比站點信息得出關鍵節點分別為上海體育館、徐家匯、常熟路、陜西南路、人民廣場、漢中路、江蘇路、靜安寺、南京西路、世紀大道、宜山路、金沙江路、曹楊路、大木橋路、東安路、肇嘉浜路、成山路、陸家浜路、曲阜路、嘉善路、馬當路、交通大學、新天地、隆德路。由站點信息可知，關鍵節點均為換乘站點，且地理位置集中于市區中心區域。

表1所示為改進FCM算法各個聚類中心在3個評價指標上的得分。從表1可知，關鍵節點在介數、接近中心性和特征向量中心性上的評分均為最高，其中特征向量中心性的得分為2.705 6，說明相鄰節點的重要性對節點自身的重要性有一定影響。次關鍵節點的聚類中心在3個評價指標上的得分僅次于關鍵節點，且依然是在特征向量中心性這一指標上得分最高。重要節點在接近中心性上的得分較高，說明此類節點與網絡中節點的距離較小。圖4 表明，較為重要站點個數為167個，這些站點大多居于線路的中間部分，且不為換乘站，經過此類站點的最短路線較多。

表1 聚類中心

而在重要性為一般的節點中，大多數節點為地鐵線路的首末站點或與首末站點相鄰的站點。在地鐵網絡拓撲結構中，這些站點一般不與其他站點相鄰，度值較小；通過它們的最短路線較少，因此介數較小；而其他站點到它們的距離較大，因此接近中心性較小；由于在模型中考慮到了一個節點的重要性也取決于其鄰居節點的重要性，因此與首末站點相鄰的站點在評價體系中重要性也相對較小。

3.3 改進FCM算法評價

3.3.1 目標函數及迭代次數

與傳統FCM算法相比，由于改進FCM算法在迭代之前通過k-means確定了初始聚類中心，故初次計算的目標函數值和迭代次數均遠低于傳統FCM算法。傳統FCM算法迭代次數為62次，改進后迭代了26次，迭代次數降低了58.06%，縮短了運行時間。傳統FCM的目標函數值為5.554 9，改進FCM算法最終得出的目標函數值為5.259 1，目標函數值降低了5.33%，如圖5所示。

圖5 目標函數和迭代次數對比

3.3.2 誤判率評價

采用誤判率交叉估計法，分別驗證傳統FCM算法與改進FCM算法的誤判率。觀察表2可知，使用傳統FCM算法進行模糊聚類，在“重要”“較為重要”“一般”3種類別中出現分別出現了6、9、4個誤判，整體誤判率為5.49%。而使用k-means和熵權法對FCM算法進行改進后，誤判率為0，大大提高了FCM算法的準確性。

表2 改進FCM算法與傳統FCM算法誤判率對比

4 結語

研究了城市地鐵網絡節點重要性：選取節點介數、接近中心性和特征向量中心性3個指標，通過基于k-means和熵權法改進的FCM算法進行模糊聚類分析，并由模糊聚類中心3項指標的加權和將地鐵網絡節點分類為“關鍵”“次關鍵”“重要”“較為重要”“一般”5個重量級類別。以上海地鐵網絡為例，通過模糊聚類得出了24個關鍵節點，均在4號線環線及以內區域，因此在以后的站點維護中，要加強對城市中心區域地鐵站的維護，增強其抗干擾能力。對比改進FCM算法和傳統FCM算法的聚類效果，發現改進后的FCM算法降低了目標函數值、減少了迭代次數、降低了誤判率，更能客觀刻畫地鐵網絡的節點重要性，適用于城市地鐵網絡。

提出了一種改進的FCM模型，但仍存在許多方面期待進一步研究，例如本文僅從網絡拓撲結構上綜合考慮了節點本身及其相鄰節點的重要性指標，但并未考慮實際交通需求量，以后的研究可以將實際客流量考慮進去，建立帶有權重的網絡模型，計算各個節點的強度作為指標之一。