游麗平,陳德旺,陳 文,劉 林

1(福州大學(xué) 數(shù)學(xué)與計算機科學(xué)學(xué)院,福州 350108)2(福州大學(xué) 智慧地鐵福建省高校重點實驗室,福州 350108)3(福州地鐵公司運營分公司,福州 350012)

1 引 言

隨著地鐵建設(shè)事業(yè)的蓬勃發(fā)展,地鐵線路不斷增加,地鐵站點的管理變得更加艱難.合理的地鐵站點分類可以對站點管理提供參考,對其他交通方式的規(guī)劃提供借鑒意義,同時對廣告投放的地點提供參照.

國內(nèi)外現(xiàn)有的站點類型的相關(guān)研究中均采用單一的聚類方法對站點進行分類,如Chabchoub Y等人以巴黎自行車共享系統(tǒng)的工作日的數(shù)據(jù)為例,采用聚類分析方法k-means,將自行車站點分為3類[1],李向楠采用k-means將成都地鐵1號線分為6種類型的站點[2];岳真宏等采用高斯混合模型將北京地鐵分為4 類[3];尹芹等采用時間序列聚類方法將北京地鐵站點分為8類[4].

但是,對同一數(shù)據(jù)集不同的聚類算法產(chǎn)生的結(jié)果具有差異性,沒有一種聚類算法能準(zhǔn)確揭示各種數(shù)據(jù)集所呈現(xiàn)出來的多種多樣的簇結(jié)構(gòu)[5].基于此前提下本文提出將聚類集成方法應(yīng)用于站點類型研究,與單一聚類算法相比,聚類集成可以提高聚類結(jié)果的質(zhì)域和聚類的健壯性,不同的聚類結(jié)果,從不同方面反映了數(shù)據(jù)集合的結(jié)構(gòu)和多個聚類算法的綜合特性[6].本文將使用不同的算法對同一個數(shù)據(jù)集產(chǎn)生多個聚類結(jié)果構(gòu)成一個聚類集體,結(jié)合聚類集成方法,以期望取得更好的效果和更強的魯棒性[7].

2 數(shù)據(jù)來源及處理

本文研究對象為福州地鐵1號線客流數(shù)據(jù),文章選取2月13日至17日一周工作日的數(shù)據(jù)進行實驗分析.福州地鐵1號線一期全程24.89公里,設(shè)立21個地鐵站點,站點名稱及相應(yīng)的編號如表1所示.

表1 站點名稱及編號
Table 1 Station name and number

編號名稱編號名稱編號名稱編號名稱1象峰6樹兜11達道16黃山2秀山7屏山12上藤17排下3羅漢山8東街口13三叉街18城門4火車站9南門兜14白湖亭19三角埕5斗門10茶亭15葫蘆陣20臚雷21火車南

地鐵站點客流數(shù)據(jù)可以反映站點自身的特性,依據(jù)這個特性,我們對其進行分類,可以對站點管理提供幫助.但是這種分類并沒有明確的界限,屬于無監(jiān)督學(xué)習(xí)部分,在無先驗知識的情況下,我們并不能判斷對錯.而目前解決這一類問題時均采用單一聚類方法,并不能保證高準(zhǔn)確性.因而文章選用站點進、出站客流數(shù)據(jù)作為聚類分析的變量,結(jié)合聚類集成技術(shù)來研究站點的類型.

地鐵原始客流數(shù)據(jù)一條記錄包含53個信息,最后提取目標(biāo)信息、刷卡日期、卡編號、設(shè)備編號、進出站編號等5個信息.借助PyCharm編輯器編寫數(shù)據(jù)處理程序,計算出每個站點每天的進、出站數(shù)據(jù).

3 聚類集成技術(shù)

在現(xiàn)有研究基礎(chǔ)上,本文提出基于聚類集成的地鐵站點類型研究,其過程如圖1所示.

圖1 聚類集成過程示意圖Fig.1 Schematic diagram of clustering integration process

3.1 聚類合理性判別指標(biāo)

在聚類分析中,我們希望聚類結(jié)果擁有高內(nèi)聚、低耦合的性質(zhì),也就是簇內(nèi)的點相似性盡可能的大,簇與簇間的點盡相

似性盡可能小.而輪廓系數(shù)(Silhouette Coefficient)就是通過這兩種特性來定義的,以此來實現(xiàn)對聚類結(jié)果合理性的評價,它的目的是尋找簇內(nèi)高內(nèi)聚且簇間高分離的聚類結(jié)果.

(1)

對于一次聚類的輪廓系數(shù)T則定義為式(2):

(2)

其中n為所有樣本個數(shù),輪廓系數(shù)T越接近1代表此時的內(nèi)聚度和分離度相對較優(yōu),說明該樣本聚類越合理,可用于聚類數(shù)目的確定[8].

3.2 生成基聚類

聚類集成是指關(guān)于一個對象集合的多個劃分(partitioning)組合成為一個統(tǒng)一聚類結(jié)果的方法[9].而一個對象的多個劃分就稱為基聚類,使用不同的方法來產(chǎn)生基聚類,可以從不同的角度挖掘出模式間的關(guān)系[10].本文將用以下三種方法來產(chǎn)生基聚類:

首先,使用層次聚類方法來對數(shù)據(jù)集進行實驗得到一個聚類結(jié)果.在層次聚類中采用歐式距離作為數(shù)據(jù)相似度的度量;在對兩個類進行合并時,計算類與類之間距離的算法有多種,通過實驗,對不同時間數(shù)據(jù)集不同算法情況下產(chǎn)生的二叉聚類樹和實際情況的相符程度進行計算,結(jié)果如表2所示,發(fā)現(xiàn)在當(dāng)前數(shù)據(jù)集情況下未加權(quán)平均距離法(average)表現(xiàn)的最優(yōu),故本文采用未加權(quán)平均距離法,也就是AL(average-linkage)層次聚類.其次,選用的是K-means聚類算法,它通過迭代算法,逐次更新各類的中心值,直至得到最好的聚類結(jié)果,即實現(xiàn)目標(biāo)函數(shù)的最小化,其目標(biāo)函數(shù)定義如公式(3)所示:

(3)

表2 不同算法情況下產(chǎn)生的二叉聚類樹和實際情況的相符程度值
Table 2 Coincidence degree between the binary clustering tree generated by different algorithms and the actual situation

日期|方法'average''centroid''complete'median''single''ward''weighted'2.130.75280.75270.7390———0.72510.73260.74422.140.83250.83240.68690.69330.74210.65450.69332.150.78430.78430.73420.70980.65280.72450.73882.160.74720.74710.73740.70340.65340.73120.74042.170.75470.75470.74800.74920.75490.74190.7494

其中K為聚類的類數(shù);Ci為第i個簇;p為簇內(nèi)的各點;μi為第i個簇的簇中心.由于每次選取的中心值不同,聚類結(jié)果可能不盡相同,因此本文進行了多次重復(fù)實驗.

最后,采用的是fuzzy c-means(FCM)算法,它是一種基于劃分的聚類算法,它的思想就是使得被劃分到同一簇的對象之間相似度最大,而不同簇之間的相似度最小,其目的同kmeans一樣也是實現(xiàn)目標(biāo)函數(shù)最小化,其目標(biāo)函數(shù)如式及約束條件定義為式(4):

(4)

其中K為聚類的類數(shù);n為樣本個數(shù);μij為每個樣本j屬于某一類i的隸屬度;Ci為模糊組的聚類中心;Xj為第j個樣本.

3.3 設(shè)計一致性集成函數(shù)

一致性集成函數(shù),顧名思義就是將基聚類進行合并集成,得到一個統(tǒng)一的聚類結(jié)果的函數(shù).本文將采用投票法來實現(xiàn)對基聚類的集成.

相對于監(jiān)督式學(xué)習(xí)而言,在聚類中使用投票法進行集成更加困難,因為聚類中存在類標(biāo)簽對應(yīng)的問題[11].例如,在數(shù)據(jù)集D中有{a,b,c,d,e}5個對象,對于該數(shù)據(jù)集有結(jié)果劃分C1={1,1,2,2,3}和C2={2,2,1,1,3},這兩個看似劃分不同的結(jié)果實際上卻是等價的,劃分的聚類數(shù)目相同且都劃分為{a,b},{c,d},{e}.為了解決這種類標(biāo)簽對應(yīng)的問題,本文采用了基于共協(xié)關(guān)系矩陣(Co-association matrix)的集成方法[12].

基于共協(xié)關(guān)系矩陣的集成方法是通過計算兩個數(shù)據(jù)點被基聚類劃分在同一個簇中的次數(shù)來實現(xiàn)的,如果兩個數(shù)據(jù)點被聚在同一個簇中的次數(shù)占基聚類總數(shù)的一半以上,也就是說有一半以上的聚類成員認為它們屬于同一個簇,則它們被歸為同一個簇.共協(xié)關(guān)系矩陣定義如下:

co_ass(i,j)=Sij/N

(5)

其中Sij表示在所有基聚類結(jié)果中樣本i與樣本j被劃分到同一個簇的基聚類的個數(shù);N為基聚類的總數(shù).在共協(xié)關(guān)系矩陣的基礎(chǔ)上利用投票法設(shè)定閾值α=0.5,當(dāng)co_ass(i,j)>α?xí)r認為樣本i與樣本j屬于同一個簇,然后利用傳遞性原則確定最終的聚類結(jié)果.傳遞性原則定義為:

{a,b}∩{b,c}?{a,b,c}

(6)

即若有樣本a和樣本b屬于同一簇且樣本b和樣本c也屬于同一簇,則可以推出樣本a、b、c屬于同一簇.

3.4 評價指標(biāo)

本文定義了一個聚類劃分的穩(wěn)定性指標(biāo)(Stability Indicator),該標(biāo)準(zhǔn)同一致性集成函數(shù)類似,也是通過共協(xié)關(guān)系矩陣實現(xiàn),其關(guān)系矩陣定義為:

(7)

(8)

其中n表示站點總數(shù);m為(i,j)所有組合情況即n2;num()表示符合條件的數(shù)量.Sta值越接近1則表示該算法越穩(wěn)定.

4 實驗結(jié)果分析

4.1 聚類數(shù)目分析

表3 層次聚類輪廓系數(shù)
Table 3 Silhouette coefficient of hierarchical clustering

日期|類數(shù)23452.130.77790.67470.78400.75932.140.63440.73430.82000.76202.150.75470.61790.75560.70702.160.75670.70560.79730.79742.170.78280.69740.77170.7549

表4 Kmeans聚類輪廓系數(shù)值
Table 4 Silhouette coefficient of kmeans clustering

日期|類數(shù)23452.130.77790.68310.78400.71772.140.74610.78700.82000.74312.150.77500.72210.80270.70702.160.76340.70560.79730.79742.170.77100.71000.77170.6952

表5 FCM聚類輪廓系數(shù)
Table 5 Silhouette coefficient of FCM clustering

日期|類數(shù)23452.130.73860.65850.78400.75932.140.72000.62030.82000.73972.150.75470.70130.75560.70702.160.76340.70560.79730.73662.170.77700.71000.77170.6716

4.2 站點聚類分析

每種算法分別計算了從2月13日至17日數(shù)據(jù),對于一個工作日數(shù)據(jù)集的基聚類結(jié)果將使用一致性集成函數(shù)進行第一次集成,之后為消除偶然因素的影響,將這5日每日的結(jié)果作為一個基聚類進行第二次集成,以得到最終的結(jié)果.

4.2.1 聚類結(jié)果展示

表6至表8為三種聚類方法多天的聚類結(jié)果,分類結(jié)果中的每一行為一個類,數(shù)字1-21代表站點的編號.通過對比可以發(fā)現(xiàn),對于同一天的數(shù)據(jù)不同的算法可能產(chǎn)生不一樣的劃分結(jié)果.而不同的聚類算法是從不同的角度對數(shù)據(jù)集進行劃分,因此聚類集成得到的結(jié)果可以結(jié)合多個算法的綜合特性.表9為每個工作日的多種方法的集成結(jié)果.

4.2.2 算法穩(wěn)定性分析

通過穩(wěn)定性評價指標(biāo)sta計算,表明聚類集成結(jié)果在該數(shù)據(jù)集情況下,穩(wěn)定性比FCM、kmeans及層次聚類更加穩(wěn)定.各方法指標(biāo)值如表10所示.

集成算法的穩(wěn)定性比最穩(wěn)定的層次聚類提升了5.96%,比最不穩(wěn)定的kmeans聚類提升了38.18%,在穩(wěn)定性表現(xiàn)方面集成算法具有明顯的優(yōu)勢.

此外,由于集成聚類結(jié)果是在幾個基聚類的基礎(chǔ)上產(chǎn)生的,它綜合了多種算法的特性,同時也帶來了相對于單個算法集成聚類計算量更大的問題.因此聚類集成比較適用于高維度的數(shù)據(jù)集,由于高維度的數(shù)據(jù)內(nèi)在特性總是比較復(fù)雜,而集成可以從多角度反映數(shù)據(jù)集的結(jié)構(gòu);還可以用于雖然數(shù)據(jù)是低維度,但是簇結(jié)構(gòu)比較難發(fā)現(xiàn)的數(shù)據(jù)集,這種時候使用集成就可以提高劃分的穩(wěn)定性和準(zhǔn)確性.

表6 層次聚類結(jié)果
Table 6 Clustering result of hierarchical

日期分類結(jié)果日期分類結(jié)果日期分類結(jié)果2月13日周一1、5、7、12、142、3、15、16、17、18、19、204、6、9、10、11、13、2182月14日周二1、7、12、142、3、5、15、16、17、18、19、204、6、9、10、11、13、2182月15日周三1、5、7、12、142、3、15、16、17、18、19、204、6、9、10、11、13、2182月16日周四1、5、7、12、142、3、15、16、17、18、19、204、6、9、10、11、13、2182月17日周五1、5、7、12、142、3、15、16、17、18、19、206、9、10、11、13、214、8

表7 kmeans聚類結(jié)果
Table 7 Clustering result of k-means

日期分類結(jié)果日期分類結(jié)果日期分類結(jié)果2月13日周一1、5、7、12、142、3、15、16、17、18、19、204、6、9、10、11、13、2182月14日周二1、5、7、12、142、3、15、16、17、18、19、204、6、9、10、11、13、2182月15日周三1、5、7、12、142、3、15、16、17、18、19、204、6、9、10、11、13、2182月16日周四1、5、7、12、142、3、15、16、194、6、8、9、10、11、13、2117、18、202月17日周五1、5、7、12、142、3、15、16、194、6、8、9、10、11、13、2117、18、20

表8 FCM聚類結(jié)果
Table 8 Clustering result of FCM

日期分類結(jié)果日期分類結(jié)果日期分類結(jié)果2月13日周一1、6、7、9、12、13、142、3、5、15、16、194、8、10、11、2117、18、202月14日周二1、5、7、12、142、3、15、16、17、18、19、204、6、9、10、11、13、2182月15日周三1、5、7、12、142、3、15、16、17、18、19、204、6、9、10、11、13、2182月16日周四1、5、7、12、142、3、15、16、17、18、19、204、6、9、10、11、13、2182月17日周五1、5、7、12、142、3、15、16、17、18、19、206、9、10、11、13、214、8

表9 5個工作日的多種方法的集成結(jié)果
Table 9 Integration result of multiple methods on 5 working days

日期分類結(jié)果日期分類結(jié)果日期分類結(jié)果2月13日周一1、5、7、12、142、3、15、16、17、18、19、204、6、9、10、11、13、2182月14日周二1、5、7、12、142、3、15、16、17、18、19、204、6、9、10、11、13、2182月15日周三1、5、7、12、142、3、15、16、17、18、19、204、6、9、10、11、13、2182月16日周四1、5、7、12、142、3、15、16、17、18、19、204、6、9、10、11、13、2182月17日周五1、5、7、12、142、3、15、16、17、18、19、206、9、10、11、13、214、8

4.2.3 集成結(jié)果分析

表11在5個工作日的多種方法的集成基礎(chǔ)上進行第二次集成得到多個工作日的綜合集成分類:該結(jié)果經(jīng)與福州地鐵集團工作人員確認,認為站點分類結(jié)果科學(xué)有效,對于合理安排人力非常有參考價值.

簇標(biāo)簽2為低流量站點包含8個站點,分別為葫蘆陣、黃山、排下、城門、三角埕、臚雷、秀山以及羅漢山.這類站點都是距離市中心比較遠,客流量明顯較少,主要是一些工廠、汽車銷售公司等比較多.此類站點交通方式的銜接和站點管理都比較輕松,適當(dāng)就好.

表10 穩(wěn)定性指標(biāo)值
Table 10 Stability index value

算法 Sta值FCM聚類0.7506層次聚類0.9138 kmeans聚類0.7007集成聚類0.9683

簇標(biāo)簽1為中流量站點包含5個站點,分別為象峰、斗門、屏山、上藤及白湖亭.這類站點客流量適中,地鐵壓力不大.

簇標(biāo)簽3為高流量站點包含7個站點,分別為火車站、樹兜、南門兜、茶亭、達道、三叉街及火車南站.這類站點是交通樞紐中心或是距離市中心近人口住宅密集的點,人口密集,客流量大.此類站點是除東街口外最高客流量點,客流壓力大,在站點管理和交通規(guī)劃時都要加強關(guān)注.

簇標(biāo)簽4為超高流量站點包含東街口站.東街口是一個福州市最繁華的商業(yè)街區(qū),人流量多,地鐵乘客流量大.這類站點需要重點關(guān)注、加強管理,多增加人手.在這些站點的周圍應(yīng)該多一些交通方式,可以減少地鐵高峰時期的壓力.此外,這類站點附近也是最優(yōu)的廣告投放點.

表11 多個工作日的綜合集成分類
Table 11 Integrated classification of multiple working days

站點編號123456789101112131415161718192021簇標(biāo)簽122313143331312222223

5 結(jié)束語

在現(xiàn)有站點聚類研究均采用單一聚類方法的基礎(chǔ)上,本文提出了基于聚類集成的站點類型研究,運用層次聚類,K均值聚類以及FCM聚類三種聚類方法產(chǎn)生的結(jié)果作為聚類集體,通過基于共協(xié)關(guān)系矩陣的集成方法以及傳遞性原則實現(xiàn)聚類集體的合并.

定義了聚類劃分穩(wěn)定性指標(biāo)sta,通過指標(biāo)計算表明在該數(shù)據(jù)情況下,聚類集成方法在幾種聚類方法中表現(xiàn)最為穩(wěn)定.通過實驗分析,將福州地鐵1號線分為了超高流量站點、高流量站點、中流量站點以及低流量站點4類.

本文只是針對工作日的站點類型進行研究,在之后的研究中將結(jié)合節(jié)假日的客流情況進行地鐵站點類型的探討,分析節(jié)假日與工作日的區(qū)別;此外,對影響站點類型因素的考慮也不夠全面,在今后的研究中也將要解決這個問題.