基于K-means的上海地鐵站點分級研究

趙 源

（1同濟大學 道路與交通工程教育部重點實驗室，上海201804；2上海軌道交通運營管理中心，上海200070）

0 引 言

目前，對于軌道交通站點的分級研究主要依據是車站的位置、用地情況以及客流量等因素，結果往往只是單一特征下的幾類車站，不能反映一個車站同時屬于多種類型的情況［1］。隨著上海地鐵網絡的快速發展，線網網絡的拓撲結構越來越復雜，需要更加科學合理的分級體系，來對站點進行分級研究［2］。本文應用圖論的方法，將上海地鐵復雜的線網用數學模型方法［3］進行描述。通過研究模型準確地發現線網的規律和特點后，引入簡單高效的kmeans聚類方法，綜合各指標對上海現有站點進行分類研究。

1 基于圖論的地鐵車站重要度研究

現實中復雜的地鐵線網可以通過圖論進行簡化描述，將現實中的站點擬化成圖論中的節點，站點之間的線路可擬化成邊。不同的線路利用不同的顏色進行區分，然后通過復雜線網的3個重要指標（節點度值、接近中心性和介數中心性）的值，對線網節點進行描述［4］，從而了解上海各站站點在線網網絡中的重要度。

1.1 上海地鐵線網模型建立

在圖論中，一般設圖G＝（V，E），V和E的值分別代表圖G的頂點數和邊數。若圖G的頂點數和邊數都是有限集，則稱G為有限圖，反之為無限圖。若圖G中，節點之間的邊有方向，則稱圖G為有向圖，否則稱為無向圖。有向圖中節點的度有出度和入度之分。

在研究上海地鐵全網的拓撲模型特性時，需要選擇合適的網絡拓撲抽象方法。常見構建線網拓撲的方法是Space L和Space P方法。對比兩種建模方法：Space L方法所建的模型能夠很好的重現線網的實際拓撲結構，但對一些交通特性如換乘次數、最短路徑等體現的不夠明顯。Space P方法能夠很好的將換乘特性、出行距離等乘客重點關注的特征參數表示出來，但由于模型的過度抽象，無法較好的體現線網的具體拓撲結構。由于本文的研究目的主要為分析站點的拓撲特性，因此選擇使用Space L方法來進行實際地鐵線網的建模。

為了研究圖論角度下，上海地鐵線網的一般拓撲結構規律及特征，需對線網進行如下簡化：

（1）將各站距離都假定為1。

（2）共線線路合并為一條線路。

（3）線網網絡為無向網絡，不分上下行。

（4）換乘站當做一個站，忽略換乘通道。

1.2 線網重要度評價指標

運用Space L法建立的上海地鐵線網拓撲網絡是復雜網絡。目前，復雜網絡中最主要的統計指標有：節點度值、接近中心性以及介數中心值。運用這些指標對線網中某個節點進行描述，從而反映這個節點在網絡中的基本特性。

（1）節點度值。節點度的值是指和該節點相關聯的邊的條數，又稱關聯度。無向網絡中，節點i的度k i定義為與該節點相連接邊的數目，網絡中所有節點i的度k i的平均值，即網絡的平均度公式為：

依據公式，如果某個節點的度越大，表明與該節點形成連邊的數目越多，該節點在網絡中的重要性也相對較大。

（2）接近中心性。對于網絡中的每一節v i，可以計算該節點到其它節點最短距離的平均長度L i。L i的倒數即為節點v i的接近中心性，二者的表達式如下：

依據公式，L i值是線網中某個節點至網絡中其它節點距離之和。其值越小，說明到網絡中其它節點距離較小，節點接近中心性的值就越大，節點vi在網絡中空間位置上就相對重要。

（3）介數中心值。介數中心值定義為網絡中起始點到終點路徑中，所有經過節點vi的最短路徑的數目。介數中心性的值，定義為網絡中所有節點對之間的最短路徑中，經過節點v i的比例之和。其中，g st為節點vs和節點vt之間的最短路徑數目，n vs t為連接節點s、t之間最短路徑中經過節點v i的最短路數目。如果兩節點間不存在路徑，此時介數值就為0。當節點vs和節點v t存在路徑時則公式為：

介數中心性的值從“流量”的角度刻畫了該節點在網絡中的相對重要程度，值越大說明節點在網絡中作為樞紐作用就較大，車站站點在地鐵網絡中的重要性就越高。

由公式計算出來的部分站點指標數值見表1。

表1 部分站點指標數值表Tab.1 Numerical table of partial site indicators

2 K-means聚類算法

基于圖論建立地鐵網絡拓撲網絡后，可以引入K-means算法模型。根據表征地鐵線網中車站和區間的局部拓撲重要性指標（度）和全局拓撲重要性指標（節點接近中心性和介數），再結合客流量指標以及上海大型城市中心點站對各站點的輻射影響指標，用K-means聚類算法對站點進行聚類分析。

2.1 K-means算法模型

K-means聚類是無監督學習的一種聚類方法。聚類算法是針對觀測到的數據，根據給定的準則發現它們的共同點，在數據集中尋找“群”［5］。Kmeans算法以距離作為數據對象間相似性度量的標準，通常采用歐氏距離來計算數據對象間的距離，歐氏距離的計算公式如下所示：

其中，D表示數據對象的屬性個數。

基于K-means的車站站點重要度聚類分析基本步驟：

（1）確定分類數K。從所有樣本中，隨機選取K個對象作為初始的簇中心。

（2）將剩余的點保存到相應的簇中，即計算該點與初始質心間的距離，選取最近的那個質心，并將其存儲于該質心所在的簇中。

（3）每個簇的質心進行更新，選擇該簇所有點的平均值為新的k個質心。

（4）將數據集中所有的點進行新一輪分配。如果所有點的分配結果與上一次一致，即簇的質心不會再發生改變，流程結束。否則，分配完所有的點之后重新更新每個簇的質心，循環該流程直到所有簇的質心穩定下來為止。

2.2 聚類變量選取

地鐵車站在線網中所處區位不同會導致重要度差異較大，聚類指標的選取需結合圖論中的指標來反映節點在網絡中的重要度。所以，變量可以選用復雜網絡的3個指標：度、接近中心性以及介數值。除此之外，客流量因素也是影響車站重要度的主要因素［6］。從實際數據量上可知，上海地鐵客流量超過40萬的站點數占比最少，可以歸為一類，而日進出站量在1萬-10萬人／天以下的站點數占比較大，應該在此區間對客流量進行細分（以1萬人／天為單位劃分）。10萬人／天-40萬人／天的車站數隨著客流量上升占比變小，以5萬人／天劃分，這樣可將全網站點的客流量分為16級，客流量分級見表2。

表2 客流分級Tab.2 Passenger flow classification

以此分級標準對各站點劃分客流等級后，作為一項指標放入模型中。此外，上海是國內的一線大都市，城市中心站點本身的影響力很大，所以在進行站點重要度分級時應考慮城市中心站點是否會對市區段的其它站點產生客流的輻射影響，從而造成同類型站點間重要度的差異。因此，本研究選取上海市的4個城市中心站點。其中包括：一個城市主中心（人民廣場站），三個城市副中心（世紀大道站、徐家匯站、中央公園站）。利用Dijkstra算法求解出所有車站至4個城市中心站的最短距離（相鄰站間距為1），由于主中心影響比副中心的影響稍大，設受主中心影響的站點距離權重為0.4，受副中心影響的站點距離權重為0.2。例如，由Dijkstra算法求出大渡河站到人民廣場的距離為8，到世紀大道、徐家匯的距離分別是12和5。將該值乘以各自的權重后可以作為一項指標放入模型中。

由于各指標數據具有不同量綱及單位，為了使得分類的結果更加合理有效，應先將各項數據進行標準化處理。Z-score標準化方法是一個分數與平均數的差再除以標準差的過程，可以用式（5）表示：

其中，Z值即為變量標準化后的數值；x為實際變量值；μ為同一類變量的均值；σ為變量的標準差。

2.3 站點重要度分級

由于地鐵實際線網與純圖論下的網絡會存在較大的差異，單純利用求得的圖論指標進行計算時，會存在一定的異常點，需要結合實際情況進行處理。如，對一些對外接駁其它交通方式的終點樞紐站指標參數進行適當提高，從而保證站點分級的合理性。為了更加明確區分各類型車站的特征，需要經過多次迭代才能得到最優的車站等級聚類結果。將上海全網地鐵站點進行聚類分析后，可將現有站點重要度分為12個等級，即k＝12，各等級代表站點見表3。

表3 部分車站聚類結果Tab.3 Cluster results of some stations

對聚類結果進一步分析，并按照各站點實際情況對各類別進行特征歸納排序，可得如下結論：

（1）第一類站點：重要度等級為1。站點是各線的郊區站，位置比較偏僻，該類站點皆為非換乘站和終點站，吸引的客流量較低，因此重要度最低。

（2）第二類站點：重要度等級為2的站點。雖然是各線的郊區段站點且不是換乘站，但位置相對不太偏僻，圖論指標中度較小，客流量也偏低，因此重要度相對較低。

（3）第三類站點：重要等級為3級，站點為各條線路的終點站及郊區段接入市區段的前段站點。終點站吸引客流范圍較廣，且可能接駁公交或者其它交通方式，圖論指標較小，有少量的通勤客流，重要度比郊區段稍高。

（4）第四類站點：重要度等級是4級的站點，為各線郊區段接入市區段的樞紐站點及郊區的換乘站點。由于距市區較近所以受市區段的影響，有大量的通勤客流，因此重要度也略微有所提高。

（5）第五類站點：重要度等級是5-8級的站點，為各線市區段的站點。受是否為換乘站及到城市中心站點的遠近影響，客流也因是否為換乘站及受城市中心站點的輻射程度產生差異，因此對于重要度有所區分。

（6）第六類站點：重要度等級是9-11級的站點，為各線位于市中心附近的站點，因圖論指標和客流指標產生分級。圖論指標和客流指標都較大，因此站點非常重要。

（7）第七類站點：重要度等級是12級的站點，為市中心地標性的站點。除了換乘客流還有很多商業觀光客流，位于網絡中心，自身介數和接近中心性指標最大，級別也最高。

3 結束語

本文通過Space-L構建了上海地鐵線網模型，選取圖論中衡量節點重要度的3個指標，從自身的連通性、在線網中所處的位置和“流量”方面評價站點的重要性，結合現實中客流量因素和城市中心站的輻射影響，運用K-means聚類算法全面的對全網站點進行聚類研究和評估。根據聚類結果，站點的重要度等級被分為12級并將這12級歸結為7類站點。通過研究7類站點的特征，為今后新建車站的資源分配和管理模式的選擇提供決策依據。