基于K-means的上海地鐵站點(diǎn)分級(jí)研究

趙 源

（1同濟(jì)大學(xué) 道路與交通工程教育部重點(diǎn)實(shí)驗(yàn)室，上海201804；2上海軌道交通運(yùn)營(yíng)管理中心，上海200070）

0 引 言

目前，對(duì)于軌道交通站點(diǎn)的分級(jí)研究主要依據(jù)是車(chē)站的位置、用地情況以及客流量等因素，結(jié)果往往只是單一特征下的幾類(lèi)車(chē)站，不能反映一個(gè)車(chē)站同時(shí)屬于多種類(lèi)型的情況［1］。隨著上海地鐵網(wǎng)絡(luò)的快速發(fā)展，線網(wǎng)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)越來(lái)越復(fù)雜，需要更加科學(xué)合理的分級(jí)體系，來(lái)對(duì)站點(diǎn)進(jìn)行分級(jí)研究［2］。本文應(yīng)用圖論的方法，將上海地鐵復(fù)雜的線網(wǎng)用數(shù)學(xué)模型方法［3］進(jìn)行描述。通過(guò)研究模型準(zhǔn)確地發(fā)現(xiàn)線網(wǎng)的規(guī)律和特點(diǎn)后，引入簡(jiǎn)單高效的kmeans聚類(lèi)方法，綜合各指標(biāo)對(duì)上海現(xiàn)有站點(diǎn)進(jìn)行分類(lèi)研究。

1 基于圖論的地鐵車(chē)站重要度研究

現(xiàn)實(shí)中復(fù)雜的地鐵線網(wǎng)可以通過(guò)圖論進(jìn)行簡(jiǎn)化描述，將現(xiàn)實(shí)中的站點(diǎn)擬化成圖論中的節(jié)點(diǎn)，站點(diǎn)之間的線路可擬化成邊。不同的線路利用不同的顏色進(jìn)行區(qū)分，然后通過(guò)復(fù)雜線網(wǎng)的3個(gè)重要指標(biāo)（節(jié)點(diǎn)度值、接近中心性和介數(shù)中心性）的值，對(duì)線網(wǎng)節(jié)點(diǎn)進(jìn)行描述［4］，從而了解上海各站站點(diǎn)在線網(wǎng)網(wǎng)絡(luò)中的重要度。

1.1 上海地鐵線網(wǎng)模型建立

在圖論中，一般設(shè)圖G＝（V，E），V和E的值分別代表圖G的頂點(diǎn)數(shù)和邊數(shù)。若圖G的頂點(diǎn)數(shù)和邊數(shù)都是有限集，則稱G為有限圖，反之為無(wú)限圖。若圖G中，節(jié)點(diǎn)之間的邊有方向，則稱圖G為有向圖，否則稱為無(wú)向圖。有向圖中節(jié)點(diǎn)的度有出度和入度之分。

在研究上海地鐵全網(wǎng)的拓?fù)淠Ｐ吞匦詴r(shí)，需要選擇合適的網(wǎng)絡(luò)拓?fù)涑橄蠓椒ā３Ｒ?jiàn)構(gòu)建線網(wǎng)拓?fù)涞姆椒ㄊ荢pace L和Space P方法。對(duì)比兩種建模方法：Space L方法所建的模型能夠很好的重現(xiàn)線網(wǎng)的實(shí)際拓?fù)浣Y(jié)構(gòu)，但對(duì)一些交通特性如換乘次數(shù)、最短路徑等體現(xiàn)的不夠明顯。Space P方法能夠很好的將換乘特性、出行距離等乘客重點(diǎn)關(guān)注的特征參數(shù)表示出來(lái)，但由于模型的過(guò)度抽象，無(wú)法較好的體現(xiàn)線網(wǎng)的具體拓?fù)浣Y(jié)構(gòu)。由于本文的研究目的主要為分析站點(diǎn)的拓?fù)涮匦裕虼诉x擇使用Space L方法來(lái)進(jìn)行實(shí)際地鐵線網(wǎng)的建模。

為了研究圖論角度下，上海地鐵線網(wǎng)的一般拓?fù)浣Y(jié)構(gòu)規(guī)律及特征，需對(duì)線網(wǎng)進(jìn)行如下簡(jiǎn)化：

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

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

（3）線網(wǎng)網(wǎng)絡(luò)為無(wú)向網(wǎng)絡(luò)，不分上下行。

（4）換乘站當(dāng)做一個(gè)站，忽略換乘通道。

1.2 線網(wǎng)重要度評(píng)價(jià)指標(biāo)

運(yùn)用Space L法建立的上海地鐵線網(wǎng)拓?fù)渚W(wǎng)絡(luò)是復(fù)雜網(wǎng)絡(luò)。目前，復(fù)雜網(wǎng)絡(luò)中最主要的統(tǒng)計(jì)指標(biāo)有：節(jié)點(diǎn)度值、接近中心性以及介數(shù)中心值。運(yùn)用這些指標(biāo)對(duì)線網(wǎng)中某個(gè)節(jié)點(diǎn)進(jìn)行描述，從而反映這個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中的基本特性。

（1）節(jié)點(diǎn)度值。節(jié)點(diǎn)度的值是指和該節(jié)點(diǎn)相關(guān)聯(lián)的邊的條數(shù)，又稱關(guān)聯(lián)度。無(wú)向網(wǎng)絡(luò)中，節(jié)點(diǎn)i的度k i定義為與該節(jié)點(diǎn)相連接邊的數(shù)目，網(wǎng)絡(luò)中所有節(jié)點(diǎn)i的度k i的平均值，即網(wǎng)絡(luò)的平均度公式為：

依據(jù)公式，如果某個(gè)節(jié)點(diǎn)的度越大，表明與該節(jié)點(diǎn)形成連邊的數(shù)目越多，該節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性也相對(duì)較大。

（2）接近中心性。對(duì)于網(wǎng)絡(luò)中的每一節(jié)v i，可以計(jì)算該節(jié)點(diǎn)到其它節(jié)點(diǎn)最短距離的平均長(zhǎng)度L i。L i的倒數(shù)即為節(jié)點(diǎn)v i的接近中心性，二者的表達(dá)式如下：

依據(jù)公式，L i值是線網(wǎng)中某個(gè)節(jié)點(diǎn)至網(wǎng)絡(luò)中其它節(jié)點(diǎn)距離之和。其值越小，說(shuō)明到網(wǎng)絡(luò)中其它節(jié)點(diǎn)距離較小，節(jié)點(diǎn)接近中心性的值就越大，節(jié)點(diǎn)vi在網(wǎng)絡(luò)中空間位置上就相對(duì)重要。

（3）介數(shù)中心值。介數(shù)中心值定義為網(wǎng)絡(luò)中起始點(diǎn)到終點(diǎn)路徑中，所有經(jīng)過(guò)節(jié)點(diǎn)vi的最短路徑的數(shù)目。介數(shù)中心性的值，定義為網(wǎng)絡(luò)中所有節(jié)點(diǎn)對(duì)之間的最短路徑中，經(jīng)過(guò)節(jié)點(diǎn)v i的比例之和。其中，g st為節(jié)點(diǎn)vs和節(jié)點(diǎn)vt之間的最短路徑數(shù)目，n vs t為連接節(jié)點(diǎn)s、t之間最短路徑中經(jīng)過(guò)節(jié)點(diǎn)v i的最短路數(shù)目。如果兩節(jié)點(diǎn)間不存在路徑，此時(shí)介數(shù)值就為0。當(dāng)節(jié)點(diǎn)vs和節(jié)點(diǎn)v t存在路徑時(shí)則公式為：

介數(shù)中心性的值從“流量”的角度刻畫(huà)了該節(jié)點(diǎn)在網(wǎng)絡(luò)中的相對(duì)重要程度，值越大說(shuō)明節(jié)點(diǎn)在網(wǎng)絡(luò)中作為樞紐作用就較大，車(chē)站站點(diǎn)在地鐵網(wǎng)絡(luò)中的重要性就越高。

由公式計(jì)算出來(lái)的部分站點(diǎn)指標(biāo)數(shù)值見(jiàn)表1。

表1 部分站點(diǎn)指標(biāo)數(shù)值表Tab.1 Numerical table of partial site indicators

2 K-means聚類(lèi)算法

基于圖論建立地鐵網(wǎng)絡(luò)拓?fù)渚W(wǎng)絡(luò)后，可以引入K-means算法模型。根據(jù)表征地鐵線網(wǎng)中車(chē)站和區(qū)間的局部拓?fù)渲匾灾笜?biāo)（度）和全局拓?fù)渲匾灾笜?biāo)（節(jié)點(diǎn)接近中心性和介數(shù)），再結(jié)合客流量指標(biāo)以及上海大型城市中心點(diǎn)站對(duì)各站點(diǎn)的輻射影響指標(biāo)，用K-means聚類(lèi)算法對(duì)站點(diǎn)進(jìn)行聚類(lèi)分析。

2.1 K-means算法模型

K-means聚類(lèi)是無(wú)監(jiān)督學(xué)習(xí)的一種聚類(lèi)方法。聚類(lèi)算法是針對(duì)觀測(cè)到的數(shù)據(jù)，根據(jù)給定的準(zhǔn)則發(fā)現(xiàn)它們的共同點(diǎn)，在數(shù)據(jù)集中尋找“群”［5］。Kmeans算法以距離作為數(shù)據(jù)對(duì)象間相似性度量的標(biāo)準(zhǔn)，通常采用歐氏距離來(lái)計(jì)算數(shù)據(jù)對(duì)象間的距離，歐氏距離的計(jì)算公式如下所示：

其中，D表示數(shù)據(jù)對(duì)象的屬性個(gè)數(shù)。

基于K-means的車(chē)站站點(diǎn)重要度聚類(lèi)分析基本步驟：

（1）確定分類(lèi)數(shù)K。從所有樣本中，隨機(jī)選取K個(gè)對(duì)象作為初始的簇中心。

（2）將剩余的點(diǎn)保存到相應(yīng)的簇中，即計(jì)算該點(diǎn)與初始質(zhì)心間的距離，選取最近的那個(gè)質(zhì)心，并將其存儲(chǔ)于該質(zhì)心所在的簇中。

（3）每個(gè)簇的質(zhì)心進(jìn)行更新，選擇該簇所有點(diǎn)的平均值為新的k個(gè)質(zhì)心。

（4）將數(shù)據(jù)集中所有的點(diǎn)進(jìn)行新一輪分配。如果所有點(diǎn)的分配結(jié)果與上一次一致，即簇的質(zhì)心不會(huì)再發(fā)生改變，流程結(jié)束。否則，分配完所有的點(diǎn)之后重新更新每個(gè)簇的質(zhì)心，循環(huán)該流程直到所有簇的質(zhì)心穩(wěn)定下來(lái)為止。

2.2 聚類(lèi)變量選取

地鐵車(chē)站在線網(wǎng)中所處區(qū)位不同會(huì)導(dǎo)致重要度差異較大，聚類(lèi)指標(biāo)的選取需結(jié)合圖論中的指標(biāo)來(lái)反映節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要度。所以，變量可以選用復(fù)雜網(wǎng)絡(luò)的3個(gè)指標(biāo)：度、接近中心性以及介數(shù)值。除此之外，客流量因素也是影響車(chē)站重要度的主要因素［6］。從實(shí)際數(shù)據(jù)量上可知，上海地鐵客流量超過(guò)40萬(wàn)的站點(diǎn)數(shù)占比最少，可以歸為一類(lèi)，而日進(jìn)出站量在1萬(wàn)-10萬(wàn)人／天以下的站點(diǎn)數(shù)占比較大，應(yīng)該在此區(qū)間對(duì)客流量進(jìn)行細(xì)分（以1萬(wàn)人／天為單位劃分）。10萬(wàn)人／天-40萬(wàn)人／天的車(chē)站數(shù)隨著客流量上升占比變小，以5萬(wàn)人／天劃分，這樣可將全網(wǎng)站點(diǎn)的客流量分為16級(jí)，客流量分級(jí)見(jiàn)表2。

表2 客流分級(jí)Tab.2 Passenger flow classification

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

由于各指標(biāo)數(shù)據(jù)具有不同量綱及單位，為了使得分類(lèi)的結(jié)果更加合理有效，應(yīng)先將各項(xiàng)數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理。Z-score標(biāo)準(zhǔn)化方法是一個(gè)分?jǐn)?shù)與平均數(shù)的差再除以標(biāo)準(zhǔn)差的過(guò)程，可以用式（5）表示：

其中，Z值即為變量標(biāo)準(zhǔn)化后的數(shù)值；x為實(shí)際變量值；μ為同一類(lèi)變量的均值；σ為變量的標(biāo)準(zhǔn)差。

2.3 站點(diǎn)重要度分級(jí)

由于地鐵實(shí)際線網(wǎng)與純圖論下的網(wǎng)絡(luò)會(huì)存在較大的差異，單純利用求得的圖論指標(biāo)進(jìn)行計(jì)算時(shí)，會(huì)存在一定的異常點(diǎn)，需要結(jié)合實(shí)際情況進(jìn)行處理。如，對(duì)一些對(duì)外接駁其它交通方式的終點(diǎn)樞紐站指標(biāo)參數(shù)進(jìn)行適當(dāng)提高，從而保證站點(diǎn)分級(jí)的合理性。為了更加明確區(qū)分各類(lèi)型車(chē)站的特征，需要經(jīng)過(guò)多次迭代才能得到最優(yōu)的車(chē)站等級(jí)聚類(lèi)結(jié)果。將上海全網(wǎng)地鐵站點(diǎn)進(jìn)行聚類(lèi)分析后，可將現(xiàn)有站點(diǎn)重要度分為12個(gè)等級(jí)，即k＝12，各等級(jí)代表站點(diǎn)見(jiàn)表3。

表3 部分車(chē)站聚類(lèi)結(jié)果Tab.3 Cluster results of some stations

對(duì)聚類(lèi)結(jié)果進(jìn)一步分析，并按照各站點(diǎn)實(shí)際情況對(duì)各類(lèi)別進(jìn)行特征歸納排序，可得如下結(jié)論：

（1）第一類(lèi)站點(diǎn)：重要度等級(jí)為1。站點(diǎn)是各線的郊區(qū)站，位置比較偏僻，該類(lèi)站點(diǎn)皆為非換乘站和終點(diǎn)站，吸引的客流量較低，因此重要度最低。

（2）第二類(lèi)站點(diǎn)：重要度等級(jí)為2的站點(diǎn)。雖然是各線的郊區(qū)段站點(diǎn)且不是換乘站，但位置相對(duì)不太偏僻，圖論指標(biāo)中度較小，客流量也偏低，因此重要度相對(duì)較低。

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

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

（5）第五類(lèi)站點(diǎn)：重要度等級(jí)是5-8級(jí)的站點(diǎn)，為各線市區(qū)段的站點(diǎn)。受是否為換乘站及到城市中心站點(diǎn)的遠(yuǎn)近影響，客流也因是否為換乘站及受城市中心站點(diǎn)的輻射程度產(chǎn)生差異，因此對(duì)于重要度有所區(qū)分。

（6）第六類(lèi)站點(diǎn)：重要度等級(jí)是9-11級(jí)的站點(diǎn)，為各線位于市中心附近的站點(diǎn)，因圖論指標(biāo)和客流指標(biāo)產(chǎn)生分級(jí)。圖論指標(biāo)和客流指標(biāo)都較大，因此站點(diǎn)非常重要。

（7）第七類(lèi)站點(diǎn)：重要度等級(jí)是12級(jí)的站點(diǎn)，為市中心地標(biāo)性的站點(diǎn)。除了換乘客流還有很多商業(yè)觀光客流，位于網(wǎng)絡(luò)中心，自身介數(shù)和接近中心性指標(biāo)最大，級(jí)別也最高。

3 結(jié)束語(yǔ)

本文通過(guò)Space-L構(gòu)建了上海地鐵線網(wǎng)模型，選取圖論中衡量節(jié)點(diǎn)重要度的3個(gè)指標(biāo)，從自身的連通性、在線網(wǎng)中所處的位置和“流量”方面評(píng)價(jià)站點(diǎn)的重要性，結(jié)合現(xiàn)實(shí)中客流量因素和城市中心站的輻射影響，運(yùn)用K-means聚類(lèi)算法全面的對(duì)全網(wǎng)站點(diǎn)進(jìn)行聚類(lèi)研究和評(píng)估。根據(jù)聚類(lèi)結(jié)果，站點(diǎn)的重要度等級(jí)被分為12級(jí)并將這12級(jí)歸結(jié)為7類(lèi)站點(diǎn)。通過(guò)研究7類(lèi)站點(diǎn)的特征，為今后新建車(chē)站的資源分配和管理模式的選擇提供決策依據(jù)。