,

(杭州電子科技大學(xué) 計算機應(yīng)用技術(shù)研究所,杭州 310018)

0 概述

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

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

1 相關(guān)工作

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

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

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

2 華盛頓公共自行車租賃系統(tǒng)及數(shù)據(jù)

本文所研究的對象為華盛頓哥倫比亞特區(qū)的公共自行車租賃系統(tǒng),所采用的數(shù)據(jù)均可以在華盛頓公共自行車網(wǎng)站上獲取。

2.1 租賃點數(shù)據(jù)

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

2.2 使用記錄數(shù)據(jù)

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

表1 歷史使用數(shù)據(jù)信息

3 本文方法

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

3.1 數(shù)據(jù)定義

3.1.1 用戶使用數(shù)據(jù)定義及處理

每個乘客的一次出行產(chǎn)生一條記錄,這些記錄構(gòu)成了用戶使用記錄數(shù)據(jù)集,本文定義記錄格式如式(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的用戶使用數(shù)據(jù)可以得出用戶的出行模式,共有2種客流模式:租借模式和歸還模式,本文分別定義為MO和MD。

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

(2)

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

(3)

3.1.3 租賃點使用模式

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

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

(4)

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

(5)

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

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

(6)

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

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

(7)

3.2 公共自行車系統(tǒng)在LDA模型中的類比

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

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

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

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

圖2 用戶出行模式轉(zhuǎn)化為“單詞”的過程

3.3 算法實現(xiàn)

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

圖3 主題模型概率圖模型

LDA算法具體過程如下:

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

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

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

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

4 聚類結(jié)果分析及驗證

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

表2 聚類站點信息

圖4 聚類結(jié)果分布

4.1 整體聚類特點分析

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

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

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

4.2 不同集群特點分析

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

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

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

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

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

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

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

從圖10不同時段客流模式圖可以得出C5在工作日呈現(xiàn)“雙峰”,并且C5的客流模式與C3和C6呈現(xiàn)相反的特征:早高峰借車數(shù)較少而晚高峰借車數(shù)較高。從圖5同樣可得出C5除了與自身區(qū)域發(fā)生的借還頻次較多外,與C3、C4、C6的關(guān)系也很緊密:在工作日的晚高峰時,多數(shù)用戶從C5借車還車到C3和C6,而在早高峰,多數(shù)用戶從C3和C6借車,還到C5?？梢岳霉ぷ鲄^(qū)和居住區(qū)這種相反使用特征去指導(dǎo)公共自行車系統(tǒng)的自行車重分配策略,使得公共自行車系統(tǒng)的使用率達到平衡,減少公共自行車系統(tǒng)出現(xiàn)“無車可借”“無樁可還”的情況。

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

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

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

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

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

圖13 C7借車流動頻次

4.3 POI數(shù)據(jù)和租賃點名稱數(shù)據(jù)驗證

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

(8)

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

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

(9)

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

表4 POI分布

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

5 結(jié)束語

本文以公共自行車的OD記錄數(shù)據(jù)為研究對象,使用LDA模型和K-means聚類算法對公共自行車系統(tǒng)進行租賃點聚類分析和功能識別,并將華盛頓哥倫比亞特區(qū)公共自行車系統(tǒng)作為實例進行實驗分析?；诩耗Ｊ教卣鞣治觥OI數(shù)據(jù)和租賃點名字數(shù)據(jù)的驗證結(jié)果表明,該模型可以實現(xiàn)城市公共自行車系統(tǒng)租賃點的功能識別。下一步將利用實驗結(jié)果對公共自行車系統(tǒng)進行自行車需求預(yù)測,同時解決聚類區(qū)域間的自行車調(diào)度問題。

[1] 王靜遠,李 超,熊 璋,等.以數(shù)據(jù)為中心的智慧城市研究綜述[J].計算機研究與發(fā)展,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].武漢大學(xué)學(xué)報(信息科學(xué)版),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.