基于移動用戶出行數(shù)據(jù)的城市熱點挖掘算法

焦君

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

1 引言

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

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

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

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

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

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

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

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

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

2.4 城市熱點挖掘的算法研究

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實驗結(jié)果及分析

本文以某地市運營商的2萬名移動用戶的移動出行數(shù)據(jù)為分析對象，并將數(shù)據(jù)分成兩個時間段進行分析，工作日在工作時間段（8點至20點）以及非工作時間段（20點至次日8點）。

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

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

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

圖1 標簽矩陣示意圖

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

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

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

圖3 第二次迭代示意圖

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

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

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

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

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

4 結(jié)束語

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