公共自行車系統的租賃點聚類與功能識別

,

(杭州電子科技大學 計算機應用技術研究所,杭州 310018)

0 概述

公共自行車系統(Public Bicycle System,PBS)具有便捷、可達性高、收費低廉、低碳環保等特征,是公共交通系統中的重要組成部分。隨著公共自行車系統的普及和發展,現已積累了越來越多的使用數據。公共自行車系統的使用記錄數據蘊含了豐富的人群移動信息,但這些數據具有規模龐大、多維度等特征,對其進行特征提取和知識獲取非常困難。在系統中,租賃點所具有的功能和城市的區域功能具有相似性,都是用戶為滿足某個目的在空間和時間上進行聚集。

開展城市區域功能發現是一項繁重的任務,而公共自行車系統的使用用戶只是城市中的小部分居民,通過這些數據進行城市功能區域發現準確率較低。為此,本文構建一種公共自行車系統的租賃點聚類模型,根據系統所積累的歷史使用數據對租賃點進行功能聚類,識別租賃點的使用模式,以便于系統管理者進行車站平衡調度和新租賃點部署等操作。首先使用潛在狄利克雷分布(Latent Dirichlet Allocation,LDA)模型對公共自行車系統進行租賃點功能特征挖掘,然后通過K-means算法進行特征聚類,最后采用興趣點(Point of Interest,POI)數據和租賃點名稱信息對結果進行驗證。

1 相關工作

城市土地利用分析作為交通規劃的重要組成部分,可以幫助交通規劃者了解交通移動在使用空間上的影響[1],可用來定義城市中的居民對土地的使用,例如把城市分為住宅區、商業區和休閑區等。傳統的城市區域功能發現方法是通過實地調查、問卷、檢查建筑物數據的方式,這樣不僅浪費時間和金錢,而且所得到的結果是粗粒度的[2-4]。

近年來,隨著感知技術和計算環境的成熟,各種大數據在城市里悄然而生,如交通流、氣象數據、道路網、興趣點、移動軌跡和社交媒體等[5],越來越多的研究通過人群移動和活動模式實現城市區域功能發現:文獻[6]采用地圖分割算法把城市分割成若干區域,使用LDA算法分析城市中不同的功能區域以及每種功能的核心所在;文獻[7]采用具有噪聲的基于密度的聚類(Density-Based Spatial Clustering of Applications with Noise,DBSCAN)方法識別城市的功能區域。

隨著公共自行車需求的日益增加,越來越多的研究從不同角度來提高公共自行車系統的性能:文獻[8]和文獻[9]分別從靜態重分配和動態重分配2種調度類型出發進行系統自行車調度的最優化策略研究;文獻[10]提出一種基于統計模型對公共自行車系統租賃點進行分析的方法;文獻[11]對北愛爾蘭的公共自行車系統進行分析,發現租賃點有工作日通勤模式和以休閑區域為中心的非工作日休閑旅行模式;文獻[12]將出租車數據、天氣信息和空間變量作為協變量,使用回歸模型對公共自行車的使用量進行預測分析;文獻[13]通過泊松分布模型、神經網絡模型和馬爾科夫鏈模型分別進行預測分析并比較結果。

2 華盛頓公共自行車租賃系統及數據

本文所研究的對象為華盛頓哥倫比亞特區的公共自行車租賃系統,所采用的數據均可以在華盛頓公共自行車網站上獲取。

2.1 租賃點數據

華盛頓公共自行車租賃系統在美國迅速地發展,2008年有120輛公共自行車和10個租賃點,2014年達到3 171輛公共自行車和341個租賃點。租賃點的詳細數據包含租賃點編號、經緯度、自行車容量、停車槽數。

2.2 使用記錄數據

用戶通過刷卡來使用公共自行車,卡片記錄了用戶的移動信息:借車站點,還車站點,使用時長,借車時刻,還車時刻,用戶類型。經過數據清洗的歷史使用數據信息如表1所示。

表1 歷史使用數據信息

3 本文方法

本文首先利用車站位置信息,采用泰森多邊形算法對城市進行區域劃分,然后將公共自行車系統的使用歷史記錄轉換為區域的組成“單詞”,分別使用LDA算法[14]和K-means算法[15]對公共自行車系統進行租賃點聚類與功能識別,最后對每個聚類結果進行時空特征分析,采用POI數據和租賃點名稱信息,通過TF-IDF(Term Frequency-Inverse Document Frequency)[16]方法進行結果驗證。

3.1 數據定義

3.1.1 用戶使用數據定義及處理

每個乘客的一次出行產生一條記錄,這些記錄構成了用戶使用記錄數據集,本文定義記錄格式如式(1)所示。

U=(U.sO,U.tO,U.sD,U.tD)

(1)

其中:U.sO表示借車站點;U.tO表示借車時刻;U.sD表示還車站點;U.tD表示還車時刻。每條這樣的OD(Origin-Destination)記錄由空間屬性和時間屬性組成。

3.1.2 用戶出行模式

由BSS的用戶使用數據可以得出用戶的出行模式,共有2種客流模式:租借模式和歸還模式,本文分別定義為MO和MD。

MO=(U.sO,U.sD,U.tO)

(2)

MD=(U.sO,U.sD,U.tD)

(3)

3.1.3 租賃點使用模式

租賃點的使用模式不僅反映了用戶在不同時間段內的使用規律,而且還反映了其和其他租賃點的移動關系。與用戶出行模式類似,租賃點的使用模式也有2種,分別為租借模式和歸還模式,本文分別定義為XSO和XSD:

XSO=(CO1,CO2,…,COs,…,COS)

(4)

XSD=(CD1,CD2,…,CDs,…,CDS)

(5)

其中,COs為在編號為s的租賃點發生租借行為的所有記錄,它是一個S×T矩陣。

COs=‖{MO=(x,y,z)|x=s,y=i,z=k}‖

(6)

COs表示在時間點(1,2,…,k,…,T),從編號為s的租賃點借車,到編號為(1,2,…,i,…,S)的租賃點還車發生的記錄統計量;同理,CDs為在編號為s的租賃點發生還車行為的所有記錄,它是一個S×T矩陣。

CDs=‖{MD=(x,y,z)|x=s,y=i,z=k}‖

(7)

3.2 公共自行車系統在LDA模型中的類比

本文對公共自行車的使用記錄數據和文檔主題模型使用的文檔數據做類比,如圖1所示。具體而言:可以將每一個租賃點看作一個文檔,租賃點對應的區域功能視作文檔的主題,租賃點的使用模式相當于組成每篇文檔的單詞。如同每篇文檔一篇文章的每個詞都是通過“以一定概率選擇了某個主題,并從這個主題中以一定概率選擇某個詞語”這樣一個過程得到,租賃點的用戶出行模式也可以推導出租賃點所在區域的功能。

圖1 租賃點區域-功能與文檔-主題的類比圖

公共自行車系統共有S個租賃點,因此,本文研究的文檔個數也為S篇。根據租賃點的使用模式向量XSO和XSD,可以得出任意一個租賃點的組成內容為Cs=(WOs,WDs)。

以編號為i的租賃點為例來說明一篇文檔的單詞的計算過程:定義單詞為WOi=COi和WDi=CDi。單詞的生成示意圖如圖2所示。其中,橫軸為時間,縱軸為租賃點編號。在時刻t(1,2,…,t,…,T)時,從編號為i的租賃點借車去到租賃點編號為s(1,2,…,s…,S)的租賃點還車的記錄有M條,表示租賃點有M個這樣的單詞,同時“還車”類型單詞也是相同計算方法。

圖2 用戶出行模式轉化為“單詞”的過程

3.3 算法實現

本文使用LDA模型對租賃點所在區域進行功能挖掘,圖3為得到的概率圖模型,其中:α為每個租賃點的主題分布的先驗分布Dirichlet分布的參數;β為每個主題的詞分布的先驗分布Dirichlet分布的參數;S為租賃點的總數;K為租賃點所具有的功能數;θs是一個s×k矩陣,代表第s個租賃點的主題分布;Ns表示租賃點s有Ns個單詞;zs,n表示該單詞(租賃點s第n個單詞)被賦予的租賃點功能;φk是一個s×k矩陣,代表編號為k的主題上的詞分布;w是通過人群移動轉化的單詞。

圖3 主題模型概率圖模型

LDA算法具體過程如下:

1)對于所有的功能數k∈[1,k]:生成φk,φk～Dir(β)。

2)對于所有的租賃點s∈[1,S]:生成租賃點-功能分布θs,θs～Dir(α);生成租賃點的長度Ns,Ns～poiss(ξ)。

3)對于任意一個租賃點的單詞n∈[1,Ns]:生成單詞所對應的功能Zs,n～Mult(θs);生成該功能對應的單詞Ws,n～Mult(φZs,n)。

本文使用Java編寫LDA算法,工程的核心文件為LdaModel.java和LdaGibbsSampling.java。算法運行結束后,將LDA主題模型得到的文檔在每一主題上的概率分布作為文檔的特征值,采用K-means聚類算法對不同的文檔進行聚類。

4 聚類結果分析及驗證

表2是主題發現產生的結果統計,圖4則展示了所有租賃點在地圖上的分布,其中,C1～C7區域表示公共自行車系統各租賃點的聚類結果。由表2和圖4可以看出,C3、C4、C5每個租賃點的使用頻次比較多,并且3個集群位于城市的中心地帶,因此,這3個集群站點可能是將所有租賃點聯系起來的核心租賃點,對于一個城市來說,商業區、住宅區、文化區構成了城市的必要組成部分,很有可能這3個聚類屬于這幾個功能;C1、C2則處于城市的邊緣地帶,同時根據表2得到平均每個租賃點的使用頻次也相對較低;C6與C3和C4相鄰,C6集群里面包含較多的站點,并且總共使用的頻次較高。每個分為相同類的租賃點的地理位置也比較接近,這種現象也說明了公共自行車租賃點的使用受到空間影響。

表2 聚類站點信息

圖4 聚類結果分布

4.1 整體聚類特點分析

圖5為不同聚類集群中的移動頻次統計圖,橫軸為借車聚類編號(C1～C7),縱軸為還車聚類編號(C1～C7)。從圖5可以得出每個聚類集群的客流主要來自于其本身集群,這是因為公共自行車系統是公共交通系統中的毛細血管,它提供“門到門”服務,有效滿足短距離出行的需求,所以在自身集群中發生的使用頻次較多;C1、C2、C7僅在本區域中的用戶移動頻率較明顯,而其余幾個聚類集群則相互頻繁流通。本文根據各個聚類在不同用戶和不同時刻的使用特征對7類聚類進行命名,如表3所示。

圖5 不同聚類集群中的移動頻次

聚類編號命名C1Cityoutskirts1C2Cityoutskirts2C3Housing1C4Memorials/Park/MuseumsC5CBD/BusinessC6Housing2C7Mixed

4.2 不同集群特點分析

將C4命名為Memorials/Park/Museums,是因為本文對其1 d客流模式進行分析,由圖6所示的C4不同時段借車客流模式圖,發現其呈現出“單峰”狀態,并且非工作日的使用量要多于工作日的使用量,這說明C4租賃點所在區域呈現的功能是景區。

圖6 C4不同時段借車客流模式圖

本文同時分析C4車站的不同用戶類型在92 d內的使用特征,如圖7所示,可以發現該集群內的非注冊用戶的使用量要大于注冊用戶的使用量,這也進一步說明C4中的租賃點所呈現的功能是風景區。通過圖5所示的流動圖,可以得出C4在本身區域發生的租借行為較多,這是因為公共自行車在景區有著很大的便利性,大多數用戶借到自行車之后,在各個景點之間進行騎行,這樣不僅可以節省時間和體力,也能更好地進行游玩,同時C4、C5、C6聯系比較緊密。

對C3 1 d客流模式進行分析,結果如圖8所示。其中工作日呈現出明顯的“雙峰”現象,借車和還車的客流模式則呈現相反現象,這種現象非常符合人們的日常行為:早上從生活區到工作區上班,晚上則從工作區返回生活區;而在非工作日時,則沒有這樣的客流模式,并且可以看出,在非工作日用戶的夜間活動明顯增加。

圖8 C3不同時段客流模式圖

C6的借還特征和C3很相似,但又有所不同,如圖5所示,由于C6其他幾個集群的的聯系性比較大,因此,筆者猜測C6可能是居住和商業混合區。圖9所示為C6不同時段客流模式圖(圖9(a)為借車模式,圖9(b)為還車模式),其中工作日呈現出和C3相似的特性,不同之處在于早晚高峰C3還車頻次和借車頻次差距比C6較大。

圖9 C6不同時段客流模式圖

從圖10不同時段客流模式圖可以得出C5在工作日呈現“雙峰”,并且C5的客流模式與C3和C6呈現相反的特征:早高峰借車數較少而晚高峰借車數較高。從圖5同樣可得出C5除了與自身區域發生的借還頻次較多外,與C3、C4、C6的關系也很緊密:在工作日的晚高峰時,多數用戶從C5借車還車到C3和C6,而在早高峰,多數用戶從C3和C6借車,還到C5。可以利用工作區和居住區這種相反使用特征去指導公共自行車系統的自行車重分配策略,使得公共自行車系統的使用率達到平衡,減少公共自行車系統出現“無車可借”“無樁可還”的情況。

從地圖上可以看出C1和C2分布在城市的外圍,將其命名為和City outskirts2,同樣對其進行不同時刻的使用特征分析。圖11(a)和圖11(b)分別為C1和C2不同時間借車的客流模式圖,從圖中可以得出這兩類的站點使用在工作日都呈現“雙峰”特性,非工作日則為“單峰”特性。

圖10 C5不同時段借車客流模式圖

圖11 C1和C2不同時段借車客流模式圖

最后對C7進行分析,類似地做出其不同時段客流模式圖和不同集群之間的客流模式圖(分別為圖12和圖13)。圖12表明,屬于C7的租賃點工作日和非工作日呈現出不同的特性,并且通過觀察圖13可以得出:C7和C3、C5之間關系較緊密,它們之間發生借還頻次較高的時間段為一天之中的早高峰和晚高峰,據此,判斷C7為一個混合區域,也就是說該區域為工業、商業、住宅混合在一起,下文會進一步對結果進行證明。

圖12 C7不同時段的客流模式圖

圖13 C7借車流動頻次

4.3 POI數據和租賃點名稱數據驗證

POI數據的分布在一定程度上可以反映某類地物的分布,因此,可以通過對POI數據的分析挖掘某類地物的分布規律和特點,為本文的聚類驗證進一步研究提供依據。本文共獲取51種POI數據,為了驗證方便,把這51種POI又劃分為6類。對于任意租賃點Si,都可以求出向量POI-Si(P1,P2,…,Pp,…,Pn),Pp為租賃點i的第p類POI的TF-IDF值:

(8)

其中,np為租賃點i的第p類POI的數量,Ni為租賃點i擁有的POI的數量,S為所有的租賃點總個數,‖Si|thep-thPOI∈Si‖為第p類POI出現在不同租賃點的數量。

進一步可求得集群的POI分布POI-Cc(P1,P2,…,Pp,…Pn),求解公式如下:

(9)

計算的結果如表4所示。C4區域內的文化類(包含景點、公園、博物館等)POI值較之其他集群為最大,說明C4集群內的車站大多數位于娛樂休閑中心和景點周邊。例如美國著名的景點:“白宮”“杰弗遜紀念堂”“肯尼迪中心”等;住宅區是城市最大、最基礎的功能區,其他功能區的布局多是圍繞其分布或延伸開來的,有成品住宅樓及配套的服務設備,與企業相鄰或成片規劃建設,從表4中可以看出C3和C6的住宅、商業、購物的值和其他集群比較而言,值較高而且分布均勻。C3和C6主要的區別在于:C3為比較成熟的住宅區;C6為住宅區與商業區的混合;C5的商業、停車場、出租屋、酒店以及通勤類型的POI較多;C1和C2的POI分布最多的為公寓,其次為車站和地鐵。城市混合功能區是指:在這個區域內,工業、商業、住宅混合在一起,是多用途功能區,在這個區域里面,既有辦公樓群,也有住宅、餐館、購物中心和文化設施等。觀察其POI分布,可以發現區域內分布較靠前的為房屋出租、公寓、商業、公司類型的POI,在C7里分布的居民房和停車場也比較多。

表4 POI分布

車站的記錄信息不僅包含車站的具體位置信息(經、緯度),還包含其名字,這個名字類似于上文所使用的POI名稱信息,所以,一個車站的名字也在某種程度上可以反映這個車站所具有的功能,例如,處于C4里面的租賃點名稱為Lincoln Memorial,它的使用頻次在所有租賃點為首位,其位于林肯紀念館附近,用戶使用該租賃點的目的很明顯,是為了更好地去欣賞風景和游玩。所以,采用相似的辦法對車站名稱進行處理分析,經過處理分析可以得出以下結果:C4中車站名字詞項頻次比重排名靠前的為Jefferson、Construction、Memorial、Lincoln;C3和C6中車站名字詞項頻次比重排名靠前的為Columbia、Station、Capitol、Market;C5中車站名字詞項頻次比重排名靠前的為DuPont、Pennsylvania、Georgetown;C1和C2中車站名字詞項頻次比重排名靠前的為Wilson、Metro、Memorial;C7中車站名字詞項頻次比重排名靠前的為Connecticut、Zoo、Metro,上述結果在一定程度上證明了本文結論。

5 結束語

本文以公共自行車的OD記錄數據為研究對象,使用LDA模型和K-means聚類算法對公共自行車系統進行租賃點聚類分析和功能識別,并將華盛頓哥倫比亞特區公共自行車系統作為實例進行實驗分析。基于集群模式特征分析、POI數據和租賃點名字數據的驗證結果表明,該模型可以實現城市公共自行車系統租賃點的功能識別。下一步將利用實驗結果對公共自行車系統進行自行車需求預測,同時解決聚類區域間的自行車調度問題。

[1] 王靜遠,李 超,熊 璋,等.以數據為中心的智慧城市研究綜述[J].計算機研究與發展,2015,51(2):239-259.

[2] PUISSANT A,HIRSCH J,WEBER C.The Utility of Texture Analysis to Improve Per-pixel Classification for High to Very High Spatial Resolution Imagery[J].International Journal of Remote Sensing,2005,26(4):733-745.

[3] YANG X,LO C P.Using a Time Series of Satellite Imagery to Detect Land Use and Land Cover Changes in the Atlanta,Georgia Metropolitan Area[J].International Journal of Remote Sensing,2002,23(9):1775-1798.

[4] CARLEER A P,WOLFF E.Urban Land Cover Multi-level Region-based Classification of VHR Data by Selecting Relevant Features[J].International Journal of Remote Sensing,2006,27(6):1035-1051.

[5] 鄭 宇.城市計算概述[J].武漢大學學報(信息科學版),2015,40(1):1-13.

[6] YUAN J,ZHENG Y,XIE X.Discovering Regions of Different Functions in a City Using Human Mobility and POIs[C]//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2012:186-194.

[7] PAN G,QI G,WU Z,et al.Land-use Classification Using Taxi GPS Traces[J].IEEE Transactions on Intelligent Transportation Systems,2013,14(1):113-123.

[8] RAVIV T,TZUR M,FORMA I A.Static Repositioning in a Bike-sharing System:Models and Solution App-roaches[J].EURO Journal on Transportation and Logistics,2013,2(3):187-229.

[9] CAGGIANI L,OTTOMANELLI M.A Dynamic Simulation Based Model for Optimal Fleet Repositioning in Bike-sharing Systems[J].Procedia-Social and Behavioral Sciences,2013,87:203-210.

[10] COME E,OUKHELLOU L.Model-based Count Series Clustering for Bike Sharing System Usage Mining:A Case Study with the Velib’System of Paris[J].ACM Transactions on Intelligent Systems and Technology,2014,5(3):1-28.

[11] DAVIS A W,LEE J H,GOULIAS K G.Analyzing Bay Area Bikeshare Usage in Space and Time[C]//Proceedings of the 94th Annual Meeting of Transportation Research Board.Santa Barbara,USA:[s.n.],2015:1-19.

[12] SINGHVI D,SINGHVI S,FRAZIER P I,et al.Predicting Bike Usage for New York City’s Bike Sharing System[C]//Proceedings of the 29th AAAI Conference on Artificial Intelligence.[S.l.]:AAAI,2015:1-5.

[13] LEE C,WANG D,WONG A.Forecasting Utilization in City Bike-Share Program[EB/OL].[2016-10-30].http://cs229.stanford.edu/proj2014/Christina Lee,David Wang,Adeline Wong,Forecasting Utilization in City Bike-Share Program.pdf.

[14] BLEI D M,NG A Y,JORDAN M I.Latent Dirichlet Allocation[J].The Journal of Machine Learning Research,2003,3:993-1022.

[15] HARTIGAN J A,WONG M A.Algorithm AS 136:A k-means Clustering Algorithm[J].Journal of the Royal Statistical Society,Series C(Applied Statistics),1979,28(1):100-108.

[16] SALTON G,McGILL M J.Introduction to Modern Information Retrieval[M].New York,USA:McGraw-Hill,Inc.,1986.