焦君

（廣州杰賽科技股份有限公司，廣東 廣州 510310）

1 引言

出租車或者浮動(dòng)車的GPS數(shù)據(jù)是當(dāng)前城市熱點(diǎn)挖掘的主要數(shù)據(jù)源，基于出租車或者浮動(dòng)車GPS數(shù)據(jù)對(duì)城市熱點(diǎn)進(jìn)行研究，目前已經(jīng)取得一定的成果：秦昆[1]等人利用出租車的GPS數(shù)據(jù)構(gòu)建城市區(qū)域的空間交互網(wǎng)絡(luò)，在此基礎(chǔ)上實(shí)現(xiàn)城市熱點(diǎn)的社團(tuán)探測(cè)，從而識(shí)別城市熱點(diǎn)；李婷[2]等人通過分析傳感器的位置數(shù)據(jù)提取城市熱點(diǎn)區(qū)域，為城市居民的出行提供參考；楊格格[3]等人采用出租車的GPS數(shù)據(jù)，提取北京對(duì)外交通樞紐的乘客OD時(shí)空分布特征；趙鵬祥[4]通過研究城市出租車軌跡的時(shí)空特性，構(gòu)建多模式的城市道路網(wǎng)絡(luò)模型，實(shí)現(xiàn)基于軌跡聚類的城市熱點(diǎn)提??；Zou[5]等人采用浮動(dòng)車的數(shù)據(jù)分析城市道路的熱點(diǎn)區(qū)域和冷點(diǎn)區(qū)域，為城市規(guī)劃和交通控制等領(lǐng)域提供數(shù)據(jù)支撐。但是出租車、浮動(dòng)車等交通工具采集的數(shù)據(jù)量有限，且基于GPS方式產(chǎn)生的數(shù)據(jù)計(jì)算復(fù)雜度過高，不利用大面積推廣應(yīng)用。針對(duì)上述問題，本文嘗試采用移動(dòng)用戶出行數(shù)據(jù)進(jìn)行城市熱點(diǎn)提取。移動(dòng)用戶出行的數(shù)據(jù)具有廣域、海量、實(shí)時(shí)性強(qiáng)、提取方便等優(yōu)點(diǎn)，實(shí)驗(yàn)表明，能夠比較真實(shí)地反映一個(gè)城市的熱點(diǎn)分布以及人口駐留現(xiàn)象。

2 移動(dòng)用戶出行數(shù)據(jù)研究

2.1 移動(dòng)用戶出行規(guī)律

移動(dòng)用戶的出行規(guī)律是指通過提取移動(dòng)用戶發(fā)生業(yè)務(wù)的時(shí)間與位置信息而得到的移動(dòng)用戶出行行為特征。胡永凱[6]通過提取移動(dòng)通信網(wǎng)絡(luò)的信令數(shù)據(jù)，并將原始信令數(shù)據(jù)的位置劃分到預(yù)先定義好的交通小區(qū)里，克服由于基站覆蓋范圍的變化而導(dǎo)致用戶軌跡與實(shí)際軌跡出入太大的情況，從而提升移動(dòng)用戶出行出發(fā)地和出行目的地（OD, Origin and Destination）匹配的方法精度，實(shí)現(xiàn)移動(dòng)用戶出行規(guī)律的研究。Schlaich J采用時(shí)間序列方法對(duì)移動(dòng)用戶的手機(jī)信令數(shù)據(jù)進(jìn)行處理并獲取移動(dòng)用戶的出行軌跡，通過對(duì)移動(dòng)用戶軌跡的疊加獲得整個(gè)城市范圍內(nèi)的用戶出行信息點(diǎn)（POI, Point of Information），為交通規(guī)劃領(lǐng)域提供數(shù)據(jù)支撐。李耀輝[8]利用移動(dòng)用戶的信令數(shù)據(jù)提取移動(dòng)用戶的軌跡，并通過交通小區(qū)語(yǔ)義化以及DBSCAN聚類的方法識(shí)別用戶聚集區(qū)域，實(shí)現(xiàn)居民出行目的的判斷。本文借鑒相關(guān)學(xué)者的研究成果，對(duì)移動(dòng)用戶出行規(guī)律進(jìn)行定義：根據(jù)移動(dòng)用戶的信令數(shù)據(jù)，對(duì)移動(dòng)用戶的時(shí)間-位置序列進(jìn)行提取并排序，形成動(dòng)態(tài)移動(dòng)用戶軌跡OD向量，根據(jù)上述的用戶的OD向量獲取移動(dòng)用戶的駐留區(qū)、移動(dòng)區(qū)，從而為城市熱點(diǎn)提供基礎(chǔ)數(shù)據(jù)。

2.2 基于移動(dòng)用戶信令數(shù)據(jù)的OD分析

目前基于移動(dòng)信令數(shù)據(jù)的OD分析研究主要集中在用戶的出行端點(diǎn)識(shí)別，也就是根據(jù)基站切換的位置來(lái)表示用戶的出行開始點(diǎn)和結(jié)束點(diǎn)，每一個(gè)OD的結(jié)束站點(diǎn)也是下一個(gè)OD的開始站點(diǎn)。目前，基站的覆蓋面積大多數(shù)假設(shè)是泰森多邊形假設(shè)、六邊形假設(shè)以及扇形假設(shè)。在處理移動(dòng)用戶的出行端點(diǎn)時(shí)，一般以多邊形的中心點(diǎn)表示用戶所處的位置。部分移動(dòng)用戶的OD出行表如表1所示。

在獲取移動(dòng)用戶出行OD位置點(diǎn)的基礎(chǔ)上，采用時(shí)間序列方式對(duì)上述OD位置點(diǎn)進(jìn)行排序，形成移動(dòng)用戶的出行軌跡。在獲取移動(dòng)用戶軌跡后，采用關(guān)聯(lián)規(guī)則的方法獲取移動(dòng)用戶關(guān)鍵的OD站點(diǎn)，以便找到移動(dòng)用戶頻繁出現(xiàn)的OD站點(diǎn)，剔除一些隨機(jī)發(fā)生的OD站點(diǎn)。本文采用Apriori算法挖掘移動(dòng)用戶關(guān)鍵OD站點(diǎn)，完成移動(dòng)用戶出行數(shù)據(jù)的預(yù)處理。

2.3 基于移動(dòng)用戶出行數(shù)據(jù)的空間交互網(wǎng)絡(luò)研究

在分析每一個(gè)移動(dòng)用戶的關(guān)鍵OD節(jié)點(diǎn)后，可以從個(gè)體和聚集兩方面進(jìn)行研究。在聚集層面上，可以根據(jù)眾多移動(dòng)用戶的OD數(shù)據(jù)反映每一個(gè)區(qū)域的交互特性。這個(gè)區(qū)域是以基站為節(jié)點(diǎn)的，以移動(dòng)用戶頻繁移動(dòng)產(chǎn)生的交互為邊，產(chǎn)生了一個(gè)無(wú)向帶權(quán)網(wǎng)絡(luò)G=(V,E,W)，其中V表示基站節(jié)點(diǎn)集合，E表示移動(dòng)用戶在移動(dòng)過程中產(chǎn)生的交互集合，W表示邊權(quán)重集合。本文以關(guān)鍵OD點(diǎn)構(gòu)造用戶出行的空間交互網(wǎng)絡(luò)。

2.4 城市熱點(diǎn)挖掘的算法研究

城市熱點(diǎn)挖掘?qū)嵸|(zhì)上是通過一些信息化的手段監(jiān)測(cè)不同地區(qū)的“準(zhǔn)實(shí)時(shí)”人流變化情況，并根據(jù)不同區(qū)域的特點(diǎn)給出人群的特征分布。從上述的定義可知，城市熱點(diǎn)具有動(dòng)態(tài)、實(shí)時(shí)的特點(diǎn)。因此，采用傳統(tǒng)的監(jiān)督分類的方法來(lái)識(shí)別不同時(shí)間段的熱點(diǎn)區(qū)域分布是不現(xiàn)實(shí)的。本文嘗試采用一種半監(jiān)督的方法，采用少量具有標(biāo)簽的熱點(diǎn)區(qū)域的特征去捕捉整個(gè)城市的“準(zhǔn)實(shí)時(shí)”的熱點(diǎn)區(qū)域分布。

標(biāo)簽傳播算法（LPA, Label Propagation Algorithm）的核心思想非常簡(jiǎn)單：依靠節(jié)點(diǎn)自身的相似性，在傳播過程中，未標(biāo)記節(jié)點(diǎn)根據(jù)鄰居節(jié)點(diǎn)的標(biāo)簽情況來(lái)迭代更新自身的標(biāo)簽信息，如果鄰居節(jié)點(diǎn)與未標(biāo)記節(jié)點(diǎn)的相似性越高，那么對(duì)未標(biāo)記節(jié)點(diǎn)的影響權(quán)值越大，鄰居節(jié)點(diǎn)的標(biāo)簽更容易進(jìn)行傳播，并且相似的數(shù)據(jù)應(yīng)該具有相同的標(biāo)簽。LPA算法包括兩個(gè)流程：

（1）構(gòu)造相似矩陣。LPA算法是基于圖G=(V, E)，在對(duì)上述的移動(dòng)用戶出行數(shù)據(jù)構(gòu)建一個(gè)圖后，圖中的節(jié)點(diǎn)V代表基站個(gè)體，節(jié)點(diǎn)包含“標(biāo)簽”數(shù)據(jù)和“無(wú)標(biāo)簽數(shù)據(jù)”，具有“標(biāo)簽”的數(shù)據(jù)一般通過人工經(jīng)驗(yàn)設(shè)定。E代表節(jié)點(diǎn)所在的邊，表示基站之間的相似度。根據(jù)節(jié)點(diǎn)之間的相似度，構(gòu)造的相似性矩陣如下：

本文所描述的基站相似度是基于移動(dòng)用戶的簽到數(shù)據(jù)的交集進(jìn)行計(jì)算的，考慮了移動(dòng)用戶共同簽到的基站的特性，類似于一些網(wǎng)站采用Jaccard算法來(lái)挖掘博客相似瀏覽，因此，本文采用Jaccard算法來(lái)衡量基站之間的相似性：

F（u）表示在某個(gè)時(shí)間段內(nèi)與基站u具有切換關(guān)系的鄰居基站數(shù)量；F（v）表示在某個(gè)時(shí)間段內(nèi)與基站v具有切換關(guān)系的鄰居基站數(shù)量；F（u）∩F（v）表示在一段時(shí)間內(nèi)與基站u和基站v都具有切換關(guān)系的基站數(shù)量。同理，F(xiàn)（u）∩F（v）表示在一段時(shí)間內(nèi)與基站u或基站v具有切換關(guān)系的基站數(shù)量之和。上述的相似性僅僅考慮了某個(gè)區(qū)域領(lǐng)域的移動(dòng)用戶在某一個(gè)時(shí)間段內(nèi)共同簽到的基站與全部簽到的基站占比情況。上述情況是沒有考慮到基站的交互次數(shù)，也就是有多少比例的移動(dòng)用戶在兩個(gè)基站之間的切換關(guān)系。通過Jaccard相似度計(jì)算相似矩陣中兩兩基站的相似度，最終構(gòu)造LPA的相似矩陣。

（2）通過標(biāo)簽的傳播找到相同標(biāo)簽的數(shù)據(jù)，標(biāo)簽相同的標(biāo)簽歸為一組。每個(gè)節(jié)點(diǎn)都以一定的概率傳播給其他節(jié)點(diǎn)，如果兩個(gè)節(jié)點(diǎn)的相似度越高，那么對(duì)方的標(biāo)簽越容易被自己的標(biāo)簽賦予。由于事先確定的標(biāo)簽是具有不變性，因此，隨著具有標(biāo)簽數(shù)據(jù)不斷將自身的標(biāo)簽傳播出去，最后類邊界會(huì)穿越高密度區(qū)域，而停留點(diǎn)則會(huì)留在低密度區(qū)域中，相當(dāng)于每一個(gè)類別都隨著標(biāo)簽的傳播劃分自己的范圍，最終形成了一個(gè)類別。

（1）節(jié)點(diǎn)相似性度量

在構(gòu)建空間社交網(wǎng)絡(luò)后，通過對(duì)空間交互網(wǎng)絡(luò)的交互指標(biāo)進(jìn)行分析，實(shí)現(xiàn)城市熱點(diǎn)的挖掘。當(dāng)前，城市熱點(diǎn)挖掘的相關(guān)研究有：通過軌跡聚類方式實(shí)現(xiàn)城市節(jié)點(diǎn)提取[4]；根據(jù)位置簽到數(shù)據(jù)的聚類方法提取城市熱點(diǎn)[9]；利用位置簽到數(shù)據(jù)實(shí)現(xiàn)POI顯著度計(jì)算，再利用鄰域分析和相關(guān)指標(biāo)的統(tǒng)計(jì)，實(shí)現(xiàn)提取城市特點(diǎn)的目的[10]。本文的城市熱點(diǎn)挖掘算法是基于空間交互網(wǎng)絡(luò)實(shí)現(xiàn)的，首先，通過分析每一個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的Jaccard相似度來(lái)衡量節(jié)點(diǎn)之間的關(guān)系，其次，采用重疊社團(tuán)劃分的方法來(lái)實(shí)現(xiàn)對(duì)社團(tuán)的探測(cè)。以空間交互網(wǎng)絡(luò)的內(nèi)聚子圖來(lái)反映城市的熱點(diǎn)區(qū)域，體現(xiàn)城市商圈的特性。

經(jīng)過歸一化處理之后，基站u和基站v的相似度為：

其中Wuv表示基站u和基站v之間的權(quán)重，表示基站之間的交互次數(shù)，等于某個(gè)時(shí)間段內(nèi)移動(dòng)用戶從基站u進(jìn)入基站v或者從基站v進(jìn)入基站u的人數(shù)除以基站u和基站v的移動(dòng)用戶數(shù)之和。

（2）基于節(jié)點(diǎn)相似性的社團(tuán)發(fā)現(xiàn)算法

經(jīng)過節(jié)點(diǎn)的相似性度量后，構(gòu)造空間交互網(wǎng)絡(luò)的相似性矩陣。通過標(biāo)簽傳播算法（LPA, Label Propagation Algorithm）來(lái)實(shí)現(xiàn)社團(tuán)探測(cè)，以網(wǎng)絡(luò)的內(nèi)聚子圖來(lái)構(gòu)成城市熱點(diǎn)區(qū)域。LPA的基本思想是依靠節(jié)點(diǎn)自身的相似性，在傳播過程中，未標(biāo)記節(jié)點(diǎn)根據(jù)鄰居節(jié)點(diǎn)的標(biāo)簽情況來(lái)迭代更新自身的標(biāo)簽信息，如果鄰居節(jié)點(diǎn)與未標(biāo)記節(jié)點(diǎn)的相似性越高，那么對(duì)未標(biāo)記節(jié)點(diǎn)的影響權(quán)值越大，鄰居節(jié)點(diǎn)的標(biāo)簽更容易進(jìn)行傳播。

第一步，基于節(jié)點(diǎn)相似性計(jì)算傳播概率，構(gòu)建節(jié)點(diǎn)之間的傳播概率傳播矩陣P：

Pij表示從節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j的概率。在標(biāo)簽重讀次數(shù)相同的情況下，節(jié)點(diǎn)i對(duì)節(jié)點(diǎn)j的傳播概率越大，那么節(jié)點(diǎn)j的標(biāo)簽越有可能被節(jié)點(diǎn)i選中。上述公式是第一次迭代的概率，隨著迭代次數(shù)的變化，節(jié)點(diǎn)之間的傳播概率是動(dòng)態(tài)變化的。

第二步，通過事先確定的標(biāo)簽，構(gòu)造標(biāo)簽矩陣。假設(shè)事先定義C個(gè)類別和L個(gè)具有標(biāo)簽的樣本，定義一個(gè)L×C的YL標(biāo)簽矩陣，第i行表示第i個(gè)樣本的標(biāo)簽指向量，如果該行的樣本類別為j，那么該行的第j個(gè)元素為1，其余元素為0。同理，給其余U個(gè)無(wú)標(biāo)簽的樣本構(gòu)造一個(gè)U×C的YU標(biāo)簽矩陣。將上述的兩個(gè)標(biāo)簽矩陣合并，形成一個(gè)N×C的標(biāo)簽矩陣F[YL; YU]。

第三步，執(zhí)行傳播。將傳播矩陣和標(biāo)簽矩陣相乘，得到每一個(gè)節(jié)點(diǎn)的傳播概率。刷新所有節(jié)點(diǎn)的標(biāo)簽，在每次迭代中，將每個(gè)節(jié)點(diǎn)的標(biāo)簽更新為其最大數(shù)量的鄰居所具有的標(biāo)簽。如果該標(biāo)簽值有且僅有一個(gè)，那么就確定為該標(biāo)簽值；如果該標(biāo)簽值有多個(gè)，那么模型會(huì)隨機(jī)選取一個(gè)，得到新的標(biāo)簽矩陣。

第四步，重復(fù)上述的步驟，每個(gè)節(jié)點(diǎn)的標(biāo)簽與其鄰居節(jié)點(diǎn)出現(xiàn)次數(shù)最多的標(biāo)簽相同，那么算法達(dá)到結(jié)束的條件。

3 實(shí)驗(yàn)結(jié)果及分析

本文以某地市運(yùn)營(yíng)商的2萬(wàn)名移動(dòng)用戶的移動(dòng)出行數(shù)據(jù)為分析對(duì)象，并將數(shù)據(jù)分成兩個(gè)時(shí)間段進(jìn)行分析，工作日在工作時(shí)間段（8點(diǎn)至20點(diǎn)）以及非工作時(shí)間段（20點(diǎn)至次日8點(diǎn)）。

在提取移動(dòng)用戶出行數(shù)據(jù)的OD關(guān)鍵點(diǎn)后，構(gòu)建基于移動(dòng)用戶出行數(shù)據(jù)的空間交互網(wǎng)絡(luò)。在構(gòu)建移動(dòng)用戶出行空間交互網(wǎng)絡(luò)后，通過移動(dòng)用戶的出行數(shù)據(jù)構(gòu)建基站之間的Jaccard相似度，比如：某個(gè)區(qū)域有基站u和基站v，根據(jù)大量的移動(dòng)用戶出行數(shù)據(jù)的挖掘可知，用戶到達(dá)基站u后將會(huì)前往到基站1、基站2等20個(gè)基站，那么基站u的鄰居基站集合為F（u）=20；同理計(jì)算基站v的鄰居基站集合，F(xiàn)（v）=15。而F（u）與F（v）的共同基站數(shù)量為8。根據(jù)某段時(shí)間段內(nèi)逗留在基站u的移動(dòng)用戶數(shù)量1 002，逗留在基站v的移動(dòng)用戶數(shù)量580，以及在兩個(gè)基站上相互“進(jìn)出”用戶數(shù)量360，得到基站u和基站v的相似度為：

同理，計(jì)算所有基站之間的相似度，最后計(jì)算出基站之間的轉(zhuǎn)移概率Pij。節(jié)點(diǎn)之間的傳播概率越大，那么節(jié)點(diǎn)之間的標(biāo)簽越有可能相同。具有“熱點(diǎn)”標(biāo)簽的基站i與沒有標(biāo)簽的基站j的傳播概率越大，那么基站j越有可能被選中，最后都有可能成為“熱點(diǎn)”基站。

假如整個(gè)城市范圍內(nèi)定義“熱點(diǎn)”和“非熱點(diǎn)”兩類基站，其中“熱點(diǎn)”基站標(biāo)簽矩陣為L(zhǎng)，“非熱點(diǎn)”基站標(biāo)簽矩陣為U，那么形成標(biāo)簽矩陣如圖1所示：

圖1 標(biāo)簽矩陣示意圖

圖1 中紅色字體代表熱點(diǎn)基站的標(biāo)簽矩陣，黑色字體代表非熱點(diǎn)基站的標(biāo)簽矩陣。結(jié)合基站之間的相似度計(jì)算基站傳播概率，根據(jù)每一個(gè)傳播概率Pij刷新所有節(jié)點(diǎn)的標(biāo)簽，在每次迭代將每個(gè)節(jié)點(diǎn)的標(biāo)簽更新為其最大數(shù)量的鄰居所具有的標(biāo)簽，其示意圖如圖2、圖3所示。

上述圓形代表具有“標(biāo)簽”的基站，方形代表“無(wú)標(biāo)簽”的基站。給每一個(gè)基站添加標(biāo)簽以代表其所屬社區(qū)，并通過標(biāo)簽的傳播概率Pij“傳播”形成同一標(biāo)簽的“社區(qū)”結(jié)構(gòu)。

在第二次迭代中，原本沒有傳遞信息的標(biāo)簽開始傳播。在經(jīng)歷多次傳播后，標(biāo)簽的每個(gè)節(jié)點(diǎn)的標(biāo)簽與其鄰居節(jié)點(diǎn)出現(xiàn)次數(shù)最多的標(biāo)簽相同，那么算法達(dá)到結(jié)束的條件。最終采用LPA算法實(shí)現(xiàn)“熱點(diǎn)”基站識(shí)別，實(shí)現(xiàn)空間交互網(wǎng)絡(luò)的社團(tuán)劃分，得到不同時(shí)間段的城市熱點(diǎn)結(jié)果如圖4所示。

圖3 第二次迭代示意圖

圖4 非工作時(shí)間段的城市熱點(diǎn)挖掘結(jié)果

圖4 紅色及黃色部分表示非工作時(shí)間段的熱點(diǎn)區(qū)域，而綠色部分表述該時(shí)間段內(nèi)非熱點(diǎn)區(qū)域。從圖4可知，在非工作時(shí)間段，該城市的熱點(diǎn)區(qū)域集中在城市的東南角，主要是居民的住宅區(qū)、大型的商場(chǎng)、休閑區(qū)以及大型公園等。工作時(shí)間段的城市熱點(diǎn)挖掘結(jié)果如圖5所示：

圖5 工作時(shí)間段的城市熱點(diǎn)挖掘結(jié)果

圖5 紅色及黃色部分表示工作時(shí)間段的熱點(diǎn)區(qū)域，而綠色部分表述該時(shí)間段內(nèi)非熱點(diǎn)區(qū)域。從圖5可知，在工作時(shí)間段，該城市的熱點(diǎn)區(qū)域集中在城市的東南角、中部以及西南角。居民的住宅區(qū)、大型的商場(chǎng)、商圈、休閑區(qū)以及大型公園等主要分布在該城市的東北角，因此無(wú)論是工作時(shí)間段還是非工作時(shí)間段人群的密度相對(duì)較高。而中部以及西南角主要是一些高檔的辦公樓、銀行、工業(yè)園、IT企業(yè)以及政府機(jī)關(guān)的聚集區(qū)域，因此在工作時(shí)間段的人群密度相對(duì)較高，在非工作時(shí)間段的密度較低。

通過對(duì)比上述圖4和圖5的結(jié)果，本文挖掘的城市熱點(diǎn)能夠有效分析出城市不同功能區(qū)的分布，能夠通過移動(dòng)用戶的出行數(shù)據(jù)快速識(shí)別該城市中8 943個(gè)以居住和休閑為特性的城市熱點(diǎn)（以基站為單位）和38 394個(gè)以辦公為特性的城市熱點(diǎn)（以基站為單位）。城市熱點(diǎn)的發(fā)現(xiàn)有利于研究城市的變遷與發(fā)展，也能夠?yàn)槌歉蛘呦嚓P(guān)部門的城市的規(guī)劃工作提供數(shù)據(jù)支撐。

4 結(jié)束語(yǔ)

本文基于真實(shí)的移動(dòng)用戶出行數(shù)據(jù)提出了一種基于移動(dòng)用戶出行數(shù)據(jù)的城市熱點(diǎn)挖掘算法。首先，通過移動(dòng)用戶的出行端點(diǎn)識(shí)別關(guān)鍵的OD點(diǎn)；其次，基于關(guān)鍵OD點(diǎn)構(gòu)建整個(gè)城市范圍內(nèi)的空間交互網(wǎng)絡(luò)；再次，采用Jaccrad相似度度量空間交互網(wǎng)絡(luò)節(jié)點(diǎn)之間的相似度；最后，采用LPA來(lái)實(shí)現(xiàn)空間交互網(wǎng)絡(luò)內(nèi)聚子圖的劃分，實(shí)現(xiàn)了整個(gè)城市范圍內(nèi)熱點(diǎn)區(qū)域的識(shí)別。實(shí)驗(yàn)證明，上述算法識(shí)別的城市熱點(diǎn)區(qū)域比較符合現(xiàn)實(shí)情況。