基于變色龍算法的共享單車站點(diǎn)聚類研究

管博,江圍,周超蘭,王廟文,姚杰

（寧波工程學(xué)院 電子與信息工程學(xué)院,浙江 寧波 315211）

0 引言

隨著城市共享單車在全國(guó)范圍內(nèi)的不斷推廣，共享單車亂停亂放現(xiàn)象逐漸成為城市管理的一大難題。城市居民每天的流動(dòng)規(guī)律（工作日早上由居住性質(zhì)的區(qū)域流向商業(yè)辦公區(qū)域，晚上又從商業(yè)辦公區(qū)域流向居住區(qū)域）導(dǎo)致共享單車在不同時(shí)刻會(huì)從某個(gè)區(qū)域流向另外一個(gè)區(qū)域，為了解決單車的過(guò)度聚集問(wèn)題，哈羅單車、青桔單車、小溜等多個(gè)共享單車運(yùn)營(yíng)商都開始通過(guò)采取設(shè)定禁停區(qū)域等一系列措施來(lái)限制借車居民對(duì)單車的亂停亂放，但效果并不明顯。很多學(xué)者對(duì)共享單車占地聚類進(jìn)行了研究。例如，陳艷艷等[1]利用K-Means聚類分析算法，呈現(xiàn)北京市7類自行車站點(diǎn)特點(diǎn)，用于運(yùn)營(yíng)商或規(guī)劃人員調(diào)整自行車站周邊交通布局。董紅召等[2]旨在對(duì)集合的租賃點(diǎn)進(jìn)行空間聚類劃分，生成調(diào)度區(qū)域劃分方案。周素靜等[3]分析了用車高峰時(shí)段的借、還車頻次，利用spss的交叉聯(lián)表和K-Means聚類分析法建立聚類分析模型。陸朕等[4]同樣采用K-Means的聚類思想，提出了基于自行車使用規(guī)模的共享單車租賃點(diǎn)的聚類方法，通過(guò)不同天氣、季節(jié)、日期類型對(duì)不同租賃點(diǎn)進(jìn)行聚類分析，使用特征曲線的描繪，分割、量化分析數(shù)據(jù)。而城市內(nèi)共享單車系統(tǒng)就是一個(gè)以站點(diǎn)為節(jié)點(diǎn)、節(jié)點(diǎn)間聯(lián)系為借還記錄的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。由于共享單車屬于短途交通工具，其移動(dòng)特征應(yīng)該有明顯的城市交通小世界特征，即在某個(gè)區(qū)域內(nèi)，大多數(shù)共享單車在局部區(qū)域內(nèi)移動(dòng)，只有少部分單車在區(qū)域之間移動(dòng)。但現(xiàn)有大多研究成果都是基于站點(diǎn)特征進(jìn)行聚類，忽略了站點(diǎn)之間的聯(lián)系，無(wú)法將城市內(nèi)共享單車移動(dòng)的小世界內(nèi)站點(diǎn)聚成一類。

本文主要是以城市共享單車借還數(shù)據(jù)為基礎(chǔ)，按照城市內(nèi)共享單車移動(dòng)的小世界特征，將站點(diǎn)單車的借還次數(shù)、借還記錄來(lái)源站點(diǎn)和借還記錄目的站點(diǎn)等作為站點(diǎn)特征，并利用變色龍聚類算法（Chameleon）思想將具有小世界特征區(qū)域內(nèi)的站點(diǎn)作為聚類目標(biāo)（這些區(qū)域內(nèi)大多共享單車在本區(qū)域內(nèi)移動(dòng)）。顯然，這些大小不同的、具有小世界特征的聚類結(jié)果可以用于城市內(nèi)共享單車調(diào)度策略優(yōu)化、站點(diǎn)選點(diǎn)等相關(guān)場(chǎng)景。

1 算法框架

城市內(nèi)的共享單車運(yùn)營(yíng)系統(tǒng)是一個(gè)以借還站點(diǎn)為節(jié)點(diǎn)，共享單車借還記錄為邊的圖結(jié)構(gòu)。為了更好的描述本算法的實(shí)現(xiàn)思想，下面先給出一些基于城市共享單車系統(tǒng)的定義。

定義1(站點(diǎn)的關(guān)聯(lián)集合)：給定時(shí)間區(qū)間t和目標(biāo)站點(diǎn)si，站點(diǎn)si在時(shí)間區(qū)間t內(nèi)的關(guān)聯(lián)集合是在t時(shí)間區(qū)間內(nèi)，站點(diǎn)si歸還和借走單車的來(lái)源站點(diǎn)和目標(biāo)站點(diǎn)的集合，表示為Rt（si）。

定義2(站點(diǎn)狀態(tài))：給定時(shí)間區(qū)間t和目標(biāo)站點(diǎn)si，時(shí)間區(qū)間t內(nèi)站點(diǎn)si的狀態(tài)是si的所有關(guān)聯(lián)集合中站點(diǎn)sk和關(guān)聯(lián)數(shù)nk的組合，如公式1所示。

其中nk其實(shí)就是在時(shí)間區(qū)間t內(nèi)兩個(gè)站點(diǎn)之間的單車來(lái)往數(shù)量之和。

定義3(站點(diǎn)的度)：給定時(shí)間區(qū)間t和目標(biāo)站點(diǎn)si，該站點(diǎn)的度deg（Si）就是在時(shí)間區(qū)間內(nèi)從該站點(diǎn)借走和歸還的共享單車數(shù)量，即deg（Si）=|St（Si）|

由于共享單車是短途交通工具，大多數(shù)單車是在某個(gè)局部區(qū)域內(nèi)移動(dòng)。也就是說(shuō)，共享單車的移動(dòng)具有城市小世界特征。如果可以將各個(gè)城市小世界內(nèi)的站點(diǎn)聚成1個(gè)子簇，那么這些子簇可以作為當(dāng)前流行的共享單車調(diào)度策略中區(qū)域劃分的依據(jù)。按照變色龍算法的思想，給出子簇相關(guān)定義。

定義4(子簇狀態(tài))：給定時(shí)間區(qū)間t和由n個(gè)站點(diǎn)組成的子簇C={s1，s2，…，sn}，那么子簇C在t區(qū)間內(nèi)的狀態(tài)就是與子簇有關(guān)聯(lián)的子簇以及關(guān)聯(lián)數(shù)的集合，如公式2所示。

定義5(子簇的度)：給定時(shí)間區(qū)間t和目標(biāo)站點(diǎn)si，該子簇的度deg（si）就是在時(shí)間區(qū)間內(nèi)從該子簇借走和歸還的、不在子簇內(nèi)站點(diǎn)歸還和借走的共享單車數(shù)量，即deg（C）=|St（C）|。

定義6(子簇的相對(duì)互連性)：給定時(shí)間區(qū)間t和由n個(gè)站點(diǎn)組成的子簇C={s1，s2，…，sn},那么2個(gè)子簇的相對(duì)互聯(lián)性RI（Ci，Cj）定義如下：

其中|St（Ci）|表示1個(gè)子簇Ci做最小截?cái)鄷r(shí)需要去掉的邊的權(quán)重之和，EC（Ci，Cj）表示的是連接2個(gè)聚簇的邊的權(quán)重和。公式（3）表示子簇Ci和子簇Cj之間內(nèi)部互連性。

定義7(子簇的相對(duì)近似性)：給定2個(gè)子簇Ci、Cj，子簇間相對(duì)近似性RC（Ci，Cj）的定義如下：

其中|Ci|、|Cj|分別表示Ci，Cj子簇中站點(diǎn)個(gè)數(shù)，是連接子簇Ci、Cj之間的平均權(quán)重，是最小截?cái)鄷r(shí)需要去掉的邊的平均權(quán)重。公式（4）表示子簇Ci和子簇Cj之間內(nèi)部近似度。

相對(duì)互連性描述的是2個(gè)子簇的關(guān)聯(lián)程度。其值越大，表示不同子簇之間的站點(diǎn)關(guān)聯(lián)性就越高，相對(duì)近似性描述的是2個(gè)子簇的相似程度，其值越高，表示2個(gè)子簇之間平均關(guān)聯(lián)度與每個(gè)子簇內(nèi)站點(diǎn)間的關(guān)聯(lián)度具有很高的相似性。

按照上述的定義，基于變色龍算法的共享單車站點(diǎn)聚類分析實(shí)現(xiàn)框架分成3個(gè)步驟：

第一步，按照k-近鄰思想將共享單車站點(diǎn)連接圖縮減成k-近鄰站點(diǎn)連接圖，（僅保留每個(gè)站點(diǎn)權(quán)值大的k條邊），最近鄰思想的依據(jù)不是按照物理位置，而是按照2個(gè)站點(diǎn)間共享單車借還的總數(shù)（邊的權(quán)重是2個(gè)站點(diǎn)之間的借出和歸還數(shù)量之和）。

第二步，按照最小邊割劃分代價(jià)思想，將k-近鄰圖分割成數(shù)量眾多的子簇，構(gòu)成初始子簇集。

第三步，按照定義4和定義5計(jì)算每2個(gè)子簇之間的相對(duì)互連性和相對(duì)近似性，并將所有子簇對(duì)按照子簇相似度公式S=RI（Ci，Cj）+σRC（Ci，Cj）進(jìn)行排序，合并相似度最大的2個(gè)子簇，然后將合并后子簇插入到隊(duì)列，將相似度最大的子簇進(jìn)行合并，……，一直到子簇個(gè)數(shù)達(dá)到指定數(shù)量。

2 實(shí)證分析

為了驗(yàn)證本算法的有效性，本節(jié)將對(duì)算法生成的站點(diǎn)聚類進(jìn)行分析和對(duì)比。本實(shí)驗(yàn)室采用的數(shù)據(jù)是中國(guó)某城市某一年的共享單車借還數(shù)據(jù)為實(shí)驗(yàn)數(shù)據(jù)，抽取其中的站點(diǎn)借還記錄和站點(diǎn)位置為研究數(shù)據(jù)。由于共享單車站點(diǎn)連接圖中站點(diǎn)數(shù)量并不龐大，算法第二步中的初始子簇直接是單個(gè)站點(diǎn)，σ的取值為1。

圖1顯示了本算法的聚類結(jié)果。從圖1可以發(fā)現(xiàn)：聚類結(jié)果具有明顯的小世界特征，整個(gè)城市的站點(diǎn)被劃分為3個(gè)大聚類，聚類1區(qū)域內(nèi)所有站點(diǎn)都是由住在該市老城區(qū)居民使用。聚類2區(qū)域內(nèi)的所有站點(diǎn)基本都是在城市在早期擴(kuò)展區(qū)域內(nèi)居民使用。而聚類4是由該市新城區(qū)內(nèi)居民使用。每個(gè)區(qū)域都具有一定的封閉性（即小世界特征）。如果在共享單車調(diào)度車輛有限情況下，采用局部和全局相結(jié)合的調(diào)度策略（每個(gè)子區(qū)域由專門調(diào)度車輛負(fù)責(zé)，區(qū)域之間再由全局調(diào)度車輛負(fù)責(zé)）在上下班高峰期要比憑經(jīng)驗(yàn)調(diào)度策略好，因?yàn)樯舷掳喔叻迤陂g，城市內(nèi)道路交通擁堵會(huì)大大限制車輛的調(diào)度速度。

圖1 聚類數(shù)為20的算法結(jié)果

圖2 聚類數(shù)為50的部分聚類結(jié)果圖

圖2顯示了當(dāng)聚類數(shù)為50的部分聚類結(jié)果圖。從圖中可以發(fā)現(xiàn)：同一個(gè)聚類的6個(gè)圓形站點(diǎn)從位置上來(lái)看并不封閉，西北方的2個(gè)站點(diǎn)與東南方的4個(gè)站點(diǎn)并不相鄰，中間還隔著4個(gè)站點(diǎn)。但從城市功能區(qū)角度來(lái)看，該聚類處在居住區(qū)A1的周邊，同樣具有一定的封閉性（小世界特征）。

綜上所述，算法不僅可以將共享單車移動(dòng)相對(duì)獨(dú)立的區(qū)域找出來(lái)。而且，隨著預(yù)設(shè)聚類個(gè)數(shù)的變大，原來(lái)的聚類逐漸變成多個(gè)小區(qū)域的聚類。顯然，這些小聚類展示著具有局部獨(dú)立性的小區(qū)域。這些聚類結(jié)果可以解決當(dāng)前共享單車調(diào)度策略中區(qū)域劃分困難的窘境，以這個(gè)聚類為依據(jù)對(duì)調(diào)度車輛進(jìn)行調(diào)度，針對(duì)每個(gè)區(qū)域的共享單車移動(dòng)特點(diǎn)，配置不同數(shù)量的調(diào)度車輛，只要保證區(qū)域內(nèi)移動(dòng)共享單車的循環(huán)閉環(huán)，那么該區(qū)域的共享單車就不會(huì)存在單車過(guò)度聚集問(wèn)題。

3 結(jié)語(yǔ)

基于變色龍算法的共享單車站點(diǎn)聚類算法可以很好地挖掘城市中共享單車移動(dòng)的小世界區(qū)域，使得共享單車調(diào)度可以按照這些小世界區(qū)域進(jìn)行車輛調(diào)度區(qū)域的劃分，方便實(shí)現(xiàn)小世界區(qū)域內(nèi)移動(dòng)共享單車的循環(huán)閉環(huán)，減少單車過(guò)度聚集，緩解調(diào)度壓力，提高共享單車調(diào)度效率。