基于SimRank的公共自行車站點聚類算法

朱金山,,,

(1.浙江大學寧波理工學院 圖書信息中心,浙江 寧波 315100; 2.寧波工程學院 電子與信息工程學院,浙江 寧波 315211)

0 概述

城市公共自行車概念最早起源于歐洲[1-3]。隨著20世紀90年代末期以來信息科學技術的發展,不斷涌現的新興信息技術促進了國內外城市公共自行車系統的發展[4-5]。公共自行車相對其他公共交通方式以其方便、符合健康生活的優點逐漸為眾人所歡迎。為積極響應綠色生活的號召,我國城市公共自行車系統近年來也在不斷發展改進。城市公共自行車系統在迅猛發展的同時,其面臨的問題開始逐漸顯現:公共自行車分布不均衡,經常會出現“潮汐問題”,即站點容量小而導致“上下班高峰的無法借車,車無法歸還”。現有針對潮汐問題的主流解決方案是對整個城市進行區域劃分,然后使用部分調度車輛進行區域間調度,最后對其他調度車輛進行區域內的小范圍調度[5]。但是這種方法存在以下問題:如何劃分區域,如何確定區域間調度的關鍵站點。

很多學者從站點聚類[6-8]、動態調度[9-10]、站點布局[11]等角度對公共自行車借還數據進行挖掘。由于研究目標不同,這些文獻的聚類結果并不能很好地體現城市內自行車的流動趨勢。因為這些聚類都是基于站點的靜態特征(如站點容量、借還統計數)進行研究,沒有考慮站點間聯系。一些學者從網絡拓撲關系角度出發分析站點之間的相似度,例如:文獻[12]使用加權相關網絡模擬自行車間關系,若站間地理位置靠近,則構成鏈路,根據鏈路權重得到相似值,提出的聚類算法則利用自行車站點狀態下的自行車數量計算相似值;文獻[13]將公共自行車系統看作Petri網,以Petri網思想去訓練,其缺點是缺乏完整的訓練數據集。

文獻[14]根據歐式距離劃定相似站點,并按一定時間區間的出(或入)度數據進行統計,將出(或入)度大的n個站點構成聚類。這個聚類在一定程度上代表了當時自行車從哪些站點流出。受該文獻啟發,本文基于站點間聯系研究城市公共自行車系統的站點聚類問題,提出一種基于SimRank原理的站點聚類算法SCSR。該算法將具有相似來源(或目的地)的站點聚成一類,從而使每個聚類代表一個或幾個自行車流的來源(或目標)區域。

1 基本概念

SimRank[15]是一種用于計算拓撲結構中任意2個節點之間相似值的算法,其主要被用于互聯網廣告、學術論文等相似值計算領域[16-18]。從結構上看,城市公共自行車系統是一個以站點為節點的網絡拓撲。但是,站點之間的相似值更多地取決于站點之間的借還記錄,而不是站點的位置、自行車樁位數等固定特征。因此,本文以“目標站點借走的自行車到達哪些站點”問題為研究對象,分析站點之間的相似值,并結合SimRank算法思想對站點進行聚類。為簡化和更好地描述算法,下面給出城市公共自行車系統的相關概念。

定義1(公共自行車站點拓撲網絡) 公共自行車站點拓撲網絡G=(V,E)(本文簡稱站點網絡)。站點α、β表示V的2個站點,三元組(α,β,r)表示站點α、β之間有向連接關系。其中,r表示在指定時間內從站點α到站點β的自行車數目,O(α)表示與站點α存在關聯的站點集合,Oi(α)表示O(α)的任一元素。

在SimRank算法中,相似值是2個節點連接邊之間相似值的平均值。但是由于站點網絡的借還數據不是簡單的引用關系,而是帶有標量的關聯關系,同時站點之間的關系也不像文獻引用或互聯網廣告那樣所有與其關聯的站點就是同類型的,因此本文取目標站點α的每個關聯站點Oi(α)與比較站點β的最相近關聯站點Oi(β)之間相似度的平均值作為2個站點的相似度。下面給出站點相似值定義。

定義2(站點相似度) 給定2個站點α、β,基于定義1的站點相似度定義如下:

(1)

式(1)用于計算站點網絡中任意2個站點α、β之間相似值,對于一個包含n個站點的站點網絡,需要計算一個n×n的矩陣。因此,將式(1)寫為如下的迭代公式:

(2)

定義3(p-站點相似) 給定相似值閾值p,根據定義2,給定2個站點α、β之相似值滿足s(α,β)>p,s(β,α)>p,則稱站點α、β是p-站點相似。

定義4(站點聚類) 給定相似值矩陣M(n×n),如果M矩陣元素站點α、β滿足p-站點相似,且不存在一個站點γ同時滿足以下2個條件:1)站點α、γ屬于p-站點相似;2)s(α,β)

2 算法實現

基于上一節站點之間相似值的定義,本文給出基于連接關系的公共自行車站點聚類算法的實現過程。整個算法分成2個階段:首先,根據定義2和定義3計算站點之間的相似值矩陣M,該功能通過函數computeSimilarMatrix實現;然后,根據相似值矩陣M和用戶指定的相似值概率閾值p,并結合定義4,將站點歸類為不同的聚類,由函數Cluster實現。算法的偽代碼如下:

算法1StationMiningByLinkRelation(G,k,c,p)

輸入站點網絡G,迭代次數k,抑制因子c,概率p

輸出站點聚類集合

1.M=computeSimilarMatrix(G,k,c);

//M表示相似值矩陣

2.return Cluster(M,p);

2.1 基于連接關系的站點相似度矩陣

站點相似度矩陣M可以通過式(2)和式(3)迭代計算得到。假設n表示站點個數,k表示迭代次數,R(α,β)是相似值矩陣M的元素,存儲每次迭代過程中每對節點(α,β)之間的相似值。每次迭代結束時,將其拷貝到相似值矩陣M。算法2給出了站點相似值矩陣的計算過程。首先按式(9)初始化相似值矩陣M(第1行),由函數Initiaze實現;然后對于每兩個站點α、β,循環執行如下迭代過程k次:1)針對站點α的連接站點集合O(α)的每個元素Oi(α),從站點α的連接站點集合O(β)找出與其最相似的站點Oj(β),將這兩個站點之間的相似值作為O(α)與O(β)的相似值(第7行～第9行);2)計算α的所有連接站點對應值的平均值作為2個站點之間的相似值(第10行和第11行);3)將中間矩陣M*復制到矩陣M以備下一次迭代,迭代結束。函數返回的是迭代計算得到的相似值矩陣M。

算法2computeSimilarMatrix(G,k,c)

輸入G、k、c同算法1

輸出相似值矩陣M

1.M*=Initiaze(G);

2.i=0;

3.while(i

4. for α,β∈V(α≠β)

5. for each entry Oi(α)∈O(α) do

6. temp←0;

7. for each entry Oj(β)∈O(β) do

8. if(temp

9. temp=R(Oi(α),Oj(β));

10. R*(α,β)← R*(α,β)+temp;

11. R*(α,β)← R*(α,β)/|O(α)|;

12. CopyMatrix(M*,M);

13.return M;

2.2 聚類過程

典型的聚類算法很多,如K-means、CHEMALOEN、DBSCAN等,由于本文聚類問題具有以下約束:1)聚類個數不定;2)個體特征更多是以個體間聯系,而不是空間特征;3)事先已經得到每2個站點間的相似值矩陣。因此本文采用CHEMALOEN算法作為本文聚類算法的原型,并根據具體要求做相應修正。站點聚類思想如下:按照站點之間相似值,判斷所有p-站點相似的站點集合,并按大者優先原則將站點分成不同聚類。為方便描述,先說明一些關鍵數據結構設定:數組c[i]表示站點i屬于哪個站點的聚類(c[i]==j表示站點i是屬于站點j所在聚類,max[i]表示站點i屬于站點j所在聚類的最大相似值)。本文聚類算法實現過程如下:

1)針對每個相似值矩陣M的每一列i,執行如下操作:(1)判斷相似值矩陣的當前行i是否存在滿足定義3的2個條件的站點,如果不存在,則直接跳轉到下一次循環;否則跳轉到下一步;(2)如果存在多個站點,則將具有最大相似值的站點j設置為站點i的控制站點;(3)判斷矩陣元素mij>max[i](站點i、j的相似值大于先前最大相似值),如果是,則將站點i的控制站點更新為站點j;否則直接跳過本次循環。

2)按數組c[i]合并聚類,如果c[i]==j(j!=0),則判斷站點i、j是否屬于聚類:(1)如果站點i和j不屬于任何聚類,那么站點i和站點j組成一個新聚類,聚類控制站點為站點j;(2)如果站點i(或站點j)屬于某個聚類,那么站點j(或站點i)加入站點i(或站點j)的聚類;(3)如果站點i、j都屬于不同聚類,則將其合并。

3 實驗

本節將以詳細的實驗結果分析和參數分析來驗證SCSR算法的有效性。由于基于關聯關系進行自行車站點聚類的算法鮮有報道,與本文算法并沒有直接可比性,因此實驗僅分析算法結果的現實意義和算法參數的影響。實驗數據是寧波公共自行車借還的5 d數據,抽取其中的(借車站點編號、借車時間、還車站點編號、還車時間)為實驗數據,同時結合站點信息數據(站點編號、站點名稱、站點經度、站點維度等)。實驗開發環境為Win7,Visual C++。

3.1 實驗結果與分析

與本文最為相關的研究成果是文獻[14]挖掘的自行車運動的時空模式。筆者將其作為對比算法。實驗數據為6∶00—10∶00借還車數據,以一個街區距離(250 m)為站點間閾值。圖1顯示了高出度的站點聚類(85號聚類是具有借車頻繁的站點集合)。圖2顯示了高入度的站點聚類(1號聚類是該時間區間內還車頻繁的站點集合)。從2個圖中可以發現:1號聚類站點是借出自行車較多的站點集合(85號聚類還的自行車較多)。由于這2個聚類并不表示這些自行車的去向(或來源),因此該算法的聚類結果并沒有描述城市自行車流,無法在公共自行車調度和自行車車流的小區域劃分等領域使用。

圖1 高出度聚類

圖2 高入度聚類

圖3顯示了SCSR算法計算得到的聚類結果(參數p為0.7,實驗數據為還車數據集合)。其中“水滴形狀”表示不屬于任何聚類的站點(異常點),不同聚類用不同顏色的形狀表示。相對于文獻[14]的聚類算法,SCSR算法的聚類結果具有以下特點:1)聚類站點具有更加一致的趨勢特征,SCSR算法將具有相同來源的站點聚成一類(聚類所有成員都擁有相同的來源),每個聚類表示一個或多個自行車流聚類的匯集區域;2)聚類具有更加明顯的區域特征,與文獻[14]算法中出現的聚類(遍布整個鬧市區)不同,SCSR算法挖掘出的聚類很少會包括較大區域。

圖3 SCSR算法的聚類結果

從圖4可以發現聚類A(圓形站點50#,201#,209#)和聚類B(方形站點160#,478#,260#)分別為區域1中2個聚類。2個聚類具有一定的區域重疊性。但是,無論是從站點所在城市功能區來看(聚類B中的160#站點處在鼓樓步行街北面,應該與50#站點更具有相似特征),還是地圖位置來看(160#站點與站點50#站點和209#站點更接近),160#站點的特征更接近聚類A,而不是聚類B。筆者通過分析實際還車數據發現:160#站點的還車數據更接近于同聚類的478#站點和260#站點,原因是因為160#站點位于中山公園旁邊,每天早上都有很多從江東江北老區過來的市民進行早鍛煉,從而導致該站點數據與聚類B站點相似。

圖4 SCSR算法的聚類分析

上述分析顯示:聚類A是處在商業區和旅游區相結合區域的站點特征,而聚類B是處在天一鼓樓商業區北面邊緣站點特征。這個結果是文獻[14]算法無法解析出的運動模式。因此,本文提出的SCSR算法得到的聚類具有更加一致的趨勢特征和位置特征,能夠更好地應用到公共自行車系統的調度策略和城市區域劃分等領域。

3.2 參數影響

本文算法涉及到的參數包括阻尼系數C和相似值概率p2個參數,有關SimRank的阻尼系數C的討論已經有很多文獻進行了研究,這里不再進行討論,本文將其設定為固定值(0.65)。本節重點來分析相似值概率閾值p的變化對算法結果的影響。圖5～圖8分別顯示了不同相似值概率p值(0.68、0.69、0.70、0.71)的算法運行結果。從中可知,閾值p越大,聚類就越少,這是由于聚類算法中各站點關聯數據計算后滿足p條件的站點隨p變大而減少。如圖7中的聚類9和聚類29都逐漸消失。另一方面,聚類規模也在逐漸變小。例如:圖中47#聚類(圓圈圈出的站點聚類)隨著p值的不斷增大而聚類規模逐漸變小,57中47#聚類基本遍及江北區“新馬路”以南全部區域,而圖6中靠近出口的成員站點(處在連接海曙區和江東區的大橋附近,方框標注)不再屬于47#聚類的成員站點。而在圖7和圖8中,47#聚類只包含3個和2個站點,而這些成員基本都處在江北區“新馬路”以南人群最密集區域,尤其是圖8中2個站點:生寶路自行車租賃點位于寧波外灘附近,而江北行政中心自行車租賃點地處江北行政中心附近,顯然這兩處都是寧波江北區的人群密集區域。

圖6 閾值p為0.69時聚類47的分布情況

圖7 閾值p為0.70時聚類47的分布情況

圖8 閾值p為0.71時聚類47的分布情況

4 結束語

本文分析當前關于公共自行車站點聚類的研究成果,并針對其不足提出基于SimRank的站點聚類算法。實驗結果表明,本文算法得到的站點聚類結果具有準確的自行車流趨勢特征和區域特征,能作為站點區域劃分、公共自行車調度策略等研究的基礎。下一步將把本文算法應用在基于公共自行車軌跡數據的區域劃分和自行車調度策略等方面,同時收集更多的公共自行車實驗數據用于研究。

[1] BENCHIMOL M,BENCHIMOL P,CHAPPERT B,et al.Balancing the stations of a self-service bike hire system[J].RAIRO-Operations Research,2011,45(1):37-61.

[2] GASPERO L D,RENDL A,URLI T.Balancing bike sharing systems with constraint programming[J].Constraints,2016,21(2):318-348.

[3] NAIR R,MILLER-HOOKS E,HAMPSHIRE R C,et al.Large-scale vehicle sharing systems:analysis of Vélib’[J].International Journal of Sustainable Transportation,2012,7(1):85-106.

[4] LATHIA N,SANIUL A,CAPRA L.Measuring the impact of opening the London shared bicycle scheme to casual users[J].Transportation Research,Part C:Emerging Technologies,2012,22:88-102.

[5] 徐建閩,秦筱然,馬瑩瑩.公共自行車多層次分區調度方法研究[J].交通運輸系統工程與信息,2017,17(1):212-219.

[6] BORGNAT P,ABRY P,FLANDRIN P.Shared bicycles in a city:a signal processing and data analysis perspective[J].Advances in Complex Systems,2011,14(3):1-24.

[7] BORGNAT P,ROBARDET C,ABRY P,et al.A dynamical network view of Lyon’s Vélo’v shared bicycle system[M]//MUKHERJEE A,CHOUDHURY M,PERUANI F,et al.Dynamics on and of Complex Networks,Volume 2.Berlin,Germany:Springer,2013:267-284.

[8] VOGEL P,MATTFELD D C.Strategic and operational planning of bike-sharing systems by data mining-a case study[C]//Proceedings of ICCL’11.Berlin,Germany:Springer,2011:127-141.

[9] VOGEL P,GREISER T,MATTFELD D C.Understanding bike-sharing systems using data mining:exploring activity patterns[J].Procedia-Social and Behavioral Sciences,2011,20(6):514-523.

[10] ETIENNE C,OUKHELLOU L.Model-based count series clustering for bike sharing system usage mining:a case study with the Vélib’ system of Paris[J].ACM Transactions on Intelligent Systems and Technology,2014,5(3):1-21.

[11] CHARDON C M D,CARUSO G.Estimating bike-share trips using station level data[J].Transportation Research,Part B:Methodological,2015,78:260-279.

[12] CHEN L,JAKUBOWICZ J,ZHANG D,et al.Dynamic cluster-based over-demand prediction in bike sharing system[C]//Proceedings of 2016 ACM International Joint Conference.New York,USA:ACM Press,2016:841-852.

[13] KADRI A A,LABADI K,KACEM I.An integrated petri net and GA based approach for performance optimization of bicycle sharing systems[J].European Journal of Industrial Engineering,2015,9(5).

[14] ZHOU X L.Understanding spatiotemporal patterns of biking behavior by analyzing massive bike sharing data in Chicago[J].PLOS One,2015,10(10).

[15] JEH G,WIDOM J.SimRank:a measure of structural-context similarity[C]//Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2002:538-543.

[16] 周文樂,朱 明,陳天昊.一種基于網站聚合和語義知識的電影推薦方法[J].計算機工程,2014,40(8):277-281.

[17] 王 健,李志斌,林鴻飛.一種基于社會化標注的網頁檢索方法[J].計算機工程,2012,38(15):50-52.

[18] 田 玲,曾 濤,陳 蓉,等.基于SimRank的中藥“效-效”相似關系挖掘[J].計算機工程,2008,34(12):242-243.