手機(jī)基站定位數(shù)據(jù)可視分析

李海生，黃媛潔，宋璇，杜軍平，陳國潤，丁富強(qiáng)

1. 北京工商大學(xué)計(jì)算機(jī)與信息工程學(xué)院，北京 100048；2. 食品安全大數(shù)據(jù)技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室，北京 100048；3. 北京郵電大學(xué)計(jì)算機(jī)學(xué)院，北京 100876；4. 上海理想信息產(chǎn)業(yè)（集團(tuán)）有限公司，上海 201315

手機(jī)基站定位數(shù)據(jù)可視分析

李海生1,2，黃媛潔1,2，宋璇1,2，杜軍平3，陳國潤4，丁富強(qiáng)4

1. 北京工商大學(xué)計(jì)算機(jī)與信息工程學(xué)院，北京 100048；2. 食品安全大數(shù)據(jù)技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室，北京 100048；3. 北京郵電大學(xué)計(jì)算機(jī)學(xué)院，北京 100876；4. 上海理想信息產(chǎn)業(yè)（集團(tuán)）有限公司，上海 201315

手機(jī)基站定位數(shù)據(jù)蘊(yùn)含豐富的時(shí)空信息。設(shè)計(jì)了一種基于電信每次呼叫測(cè)量數(shù)據(jù)的可視分析方法，給出了基于每次呼叫測(cè)量數(shù)據(jù)的基站定位方法，提取手機(jī)用戶的出行軌跡，對(duì)凝聚層次聚類算法進(jìn)行改進(jìn)，可以高效率地對(duì)軌跡進(jìn)行聚類，利用流向圖和熱力圖表示軌跡聚類結(jié)果和手機(jī)用戶在某時(shí)刻的整體分布。將該方法應(yīng)用于上海電信手機(jī)基站定位數(shù)據(jù)，取得了良好的效果。

手機(jī)基站定位數(shù)據(jù)；軌跡聚類；流向圖；可視分析

1 引言

隨著手機(jī)等移動(dòng)終端的普及，在城市中2G/3G/4G網(wǎng)絡(luò)已經(jīng)基本實(shí)現(xiàn)全區(qū)域覆蓋。根據(jù)國家工業(yè)和信息化部統(tǒng)計(jì)，截至2015年，移動(dòng)電話用戶已達(dá)到13億戶，移動(dòng)電話用戶普及率達(dá)95.5部/百人，人們開始更加關(guān)注如何利用從移動(dòng)通信網(wǎng)絡(luò)中獲取的數(shù)據(jù)進(jìn)行可視化研究。其中，手機(jī)定位數(shù)據(jù)作為移動(dòng)通信網(wǎng)絡(luò)數(shù)據(jù)中的一類，在分析人群移動(dòng)模式[1,2]、城市功能區(qū)識(shí)別[3]以及交通網(wǎng)絡(luò)規(guī)劃[4]中都提供了很大的幫助。

通常，手機(jī)等移動(dòng)終端收集到的定位數(shù)據(jù)可以來自移動(dòng)通信網(wǎng)絡(luò)、Wi-Fi接入點(diǎn)位置信息、移動(dòng)終端的GPS定位信息等，記錄了移動(dòng)對(duì)象的位置、時(shí)間、速度和方向等行為特征。GPS定位數(shù)據(jù)最為精確，多由志愿者提供[5]，因此樣本數(shù)量很少并且難以獲取。Wi-Fi接入點(diǎn)數(shù)據(jù)也較為精確，但多用于室內(nèi)定位[6]。移動(dòng)通信網(wǎng)絡(luò)能夠定期或不定期地主動(dòng)或被動(dòng)地記錄手機(jī)用戶時(shí)間序列的基站編號(hào)，該種定位方式精確度低，數(shù)據(jù)粒度不均勻，往往需要配合其他類型數(shù)據(jù)來分析[7]，但在樣本量、覆蓋范圍以及實(shí)施成本和周期上更具有優(yōu)勢(shì)[4]。本文使用的手機(jī)基站定位數(shù)據(jù)即每次呼叫測(cè)量數(shù)據(jù)（per call measurement data，PCMD）是上海電信系統(tǒng)用來記錄每個(gè)呼叫的相關(guān)信息的數(shù)據(jù)，主要包括主叫通話、基站扇區(qū)和信號(hào)質(zhì)量等信息數(shù)據(jù)。

在對(duì)軌跡進(jìn)行可視化時(shí)，傳統(tǒng)的可視化方法直接將軌跡數(shù)據(jù)一一繪制在地圖上，由于相互遮擋等原因，不適用于大量數(shù)據(jù)的可視化[8]。采用聚集可視化的方法，將對(duì)象個(gè)體數(shù)據(jù)轉(zhuǎn)換為聚集值，能夠觀察移動(dòng)對(duì)象的群體特征，同時(shí)也能減少刻畫群體特征的數(shù)據(jù)量[9]。

本文設(shè)計(jì)了一種基于電信PCMD的人群流動(dòng)可視分析方法。首先，對(duì)PCMD進(jìn)行處理，提取用戶的出行數(shù)據(jù)以得到用戶的軌跡。然后根據(jù)用戶選擇的時(shí)間段和區(qū)域，使用軌跡層次聚類算法對(duì)用戶出行軌跡進(jìn)行聚類。最后，將聚類結(jié)果映射到地圖中，使用基于流向圖的多地圖縮放級(jí)別的層次可視化方法進(jìn)行可視分析。

2 相關(guān)工作

2.1 基于基站的手機(jī)定位數(shù)據(jù)可視分析

手機(jī)定位數(shù)據(jù)被廣泛用于發(fā)現(xiàn)人群的移動(dòng)模式，Zhang Y[1]使用用戶上網(wǎng)時(shí)產(chǎn)生的蜂窩數(shù)據(jù)信息進(jìn)行人群移動(dòng)模式建模，并且能夠預(yù)測(cè)出某個(gè)特定用戶在給定位置可能用到的應(yīng)用軟件。Xiong H等人[2]發(fā)現(xiàn)特定的某一類人的位置信息有很強(qiáng)的關(guān)聯(lián)性和相關(guān)性，并提出基于集體行為模式（collective behavioral patterns，CPB）的方法來預(yù)測(cè)人的軌跡，這種方法能夠很好地預(yù)測(cè)某個(gè)人接下來6 h之內(nèi)的位置。

除了移動(dòng)模式，手機(jī)定位數(shù)據(jù)還可以用于發(fā)現(xiàn)人類生活中重要的位置信息，比如居住地點(diǎn)和工作地點(diǎn)等。Isaacman S等人[3]提出一種基于聚集和回歸的方法，分析蜂窩網(wǎng)絡(luò)數(shù)據(jù)，發(fā)現(xiàn)有意義的位置信息，計(jì)算出通勤距離，并且通過幾十萬匿名用戶的碳排放量分析，證明了該算法可以作為有效的政策和基礎(chǔ)設(shè)施研究的支撐。

對(duì)手機(jī)定位數(shù)據(jù)的挖掘和分析可以幫助調(diào)整交通政策以及基礎(chǔ)設(shè)施的建設(shè)，使得城市的居民能獲得更好的出行體驗(yàn)。冉斌[4]提出了手機(jī)數(shù)據(jù)在交通調(diào)查以及交通規(guī)劃中的應(yīng)用，通過手機(jī)話單定位數(shù)據(jù)和手機(jī)信令定位數(shù)據(jù)進(jìn)行去噪、擴(kuò)樣等預(yù)處理，最終能夠獲得居民出行特征數(shù)據(jù)。根據(jù)這些特征數(shù)據(jù)，可以分析人口就業(yè)分布、通勤出行特征，還可以進(jìn)一步分析城市人口的時(shí)空動(dòng)態(tài)分布等。

2.2 基于流向圖的時(shí)空軌跡數(shù)據(jù)可視分析

當(dāng)軌跡數(shù)據(jù)量非常大時(shí)，在地圖上顯示軌跡會(huì)出現(xiàn)嚴(yán)重的視覺混亂和不清晰的問題。一種解決方法是使用邊捆綁技術(shù)[10]，通過彎曲邊使相似的邊相互靠近形成一束，以減少相互遮擋。

Guo D等人[11]提出了一種可以從大量流數(shù)據(jù)中提取主要流模式的方法，通過一個(gè)基于向量密度的模型為每一對(duì)位置估計(jì)流密度，然后選擇光滑路徑的子集在流向圖中表示主要的流，但是這種方法的計(jì)算復(fù)雜度非常高。

Andrienko N等人[12]提出了一種對(duì)移動(dòng)數(shù)據(jù)進(jìn)行空間泛化和聚集的方法，將數(shù)據(jù)覆蓋的版圖劃分成適當(dāng)?shù)男^(qū)域。Von L T等人[13]使用了上述劃分版圖的方法，先對(duì)區(qū)域進(jìn)行了劃分，然后對(duì)移動(dòng)數(shù)據(jù)線進(jìn)行空間上的聚類，再進(jìn)行時(shí)間上的聚類，用于展示長時(shí)間段的移動(dòng)數(shù)據(jù)的時(shí)空變化情況。

3 可視分析算法描述

本文設(shè)計(jì)了一種基于PCMD的基站定位方法得到用戶的出行軌跡，然后計(jì)算軌跡間的相似度，接下來采用改進(jìn)的層次聚類算法對(duì)所有軌跡進(jìn)行聚類，最后對(duì)聚類結(jié)果進(jìn)行可視分析，算法技術(shù)框架如圖1所示。

圖1 算法技術(shù)框架

3.1 基于PCMD的基站定位方法

一條PCMD中包含兩個(gè)關(guān)鍵時(shí)間信息，分別為初始時(shí)刻和終止時(shí)刻的時(shí)間戳，這反映了手機(jī)接入和斷開網(wǎng)絡(luò)的時(shí)間。PCMD每次獲取一組信息，其中與定位相關(guān)的信息有基站號(hào)、扇區(qū)號(hào)、時(shí)延、電磁輻射場強(qiáng)等。定位的關(guān)鍵信息是場強(qiáng)和時(shí)延。但是場強(qiáng)更容易受到環(huán)境、建筑、天氣、電網(wǎng)、屏蔽體、設(shè)備等的影響，在城市內(nèi)尤甚，定位的準(zhǔn)確度難以保證。與場強(qiáng)相比，時(shí)延所受的干擾更少，所以這里使用時(shí)延信息進(jìn)行定位。每組信息可以由一個(gè)或多個(gè)基站產(chǎn)生，這些基站分為參考基站和非參考基站。本文設(shè)計(jì)了以下3種方法進(jìn)行定位。

（1）單基站定位

如果一條PCMD中僅包含1個(gè)基站的數(shù)據(jù)，則只能使用單個(gè)基站進(jìn)行定位。由于1個(gè)基站有3個(gè)扇區(qū)，有時(shí)電波到達(dá)這3個(gè)扇區(qū)的時(shí)間是不相同的，這種情況是由于多徑效應(yīng)造成的。當(dāng)發(fā)生這種情況時(shí)，取時(shí)延最短的扇區(qū)對(duì)應(yīng)的弧，由于沒有其他補(bǔ)充信息，無法將用戶定位到弧的具體點(diǎn)上，因此取弧的中點(diǎn)作為用戶的期望位置，如圖2（a）所示；當(dāng)兩個(gè)扇區(qū)的時(shí)延相同時(shí)，不能判定用戶在哪段弧上，這時(shí)以兩弧的臨界點(diǎn)作為期望位置，如圖2（b）所示；當(dāng)3個(gè)扇區(qū)的時(shí)延相同時(shí)，用戶可能位于一個(gè)圓周的任意位置，這時(shí)以基站的位置作為期望位置，如圖2（c）所示。

圖2 單基站定位

圖3 找到符合時(shí)延條件的一個(gè)點(diǎn)

圖4 找到符合時(shí)延條件的兩個(gè)點(diǎn)

（2）兩點(diǎn)定位

當(dāng)一條PCMD時(shí)，使用兩點(diǎn)定位情形相似，用戶到時(shí)延可能不完全相影響，仍使用到達(dá)為計(jì)算依據(jù)。當(dāng)找點(diǎn)時(shí)，該點(diǎn)作為用戶示。圖4表示找到符情況，如果兩點(diǎn)中只如圖4（a）所示，則

中包含2個(gè)基站的數(shù)據(jù)方法。與單基站定位的達(dá)某個(gè)基站不同扇區(qū)的同，為減少多徑效應(yīng)的各個(gè)基站的最小時(shí)延作到符合時(shí)延條件的一個(gè)的期望位置，如圖3所合時(shí)延條件的兩個(gè)點(diǎn)的有一點(diǎn)滿足扇區(qū)條件，取該點(diǎn)為用戶的期望位置；如果兩點(diǎn)都滿足或都不滿足扇區(qū)條件，如圖4（b）所示，則取與兩個(gè)基站有效扇區(qū)正方向的總誤差更小的點(diǎn)的位置。如果找不到符合時(shí)延條件的點(diǎn)，如圖5所示，則取時(shí)延總誤差最小的點(diǎn)作為用戶的期望位置。

（3）3點(diǎn)及多點(diǎn)定位方法

當(dāng)一條PCMD中包含3個(gè)或更多基站的數(shù)據(jù)，則可以進(jìn)行較為準(zhǔn)確的定位?；驹蕉?，定位精度越高。本文使用到達(dá)時(shí)間差（time difference of arrival，TDOA）/到達(dá)角度測(cè)距（angle of arrival，AOA）混合定位算法[14]。

單基站定位方法不可能定位到準(zhǔn)確位置。一條PCMD包括兩個(gè)時(shí)刻的信息，因此對(duì)一條PCMD中兩個(gè)時(shí)刻的信息交叉使用，某些情況下可以提高定位的準(zhǔn)確度。當(dāng)兩個(gè)時(shí)刻的信息來自于同一基站時(shí)，定位的兩點(diǎn)位于以基站為圓心的兩個(gè)同心圓弧上，如圖6所示。將這兩個(gè)圓弧的中心連線的中點(diǎn)作為在這個(gè)時(shí)段內(nèi)用戶位置的估算；當(dāng)兩個(gè)時(shí)刻的信息來自于不同基站時(shí)，使用前面敘述的兩點(diǎn)定位方法對(duì)用戶的位置進(jìn)行估算，并選擇其中一點(diǎn)作為這個(gè)時(shí)段內(nèi)位置的估算。

通過上述基站定位方法，可以得到每條PCMD對(duì)應(yīng)的用戶的位置和時(shí)間信息。然后將一天的時(shí)間劃分為長度相等的時(shí)間片段，得到每個(gè)用戶在每個(gè)時(shí)間段對(duì)應(yīng)的起始位置和結(jié)束位置。時(shí)間段的長度基于PCMD的獲取頻率和用戶的需求來選擇。由于空間數(shù)據(jù)具有空間位置、非結(jié)構(gòu)化、空間關(guān)系、分類編碼、海量數(shù)據(jù)等特征[15]，為了有效地進(jìn)行空間查詢，使用PostgreSQL數(shù)據(jù)庫中的PostGIS①http://www. postgis.org/來存儲(chǔ)數(shù)據(jù)。將用戶的出行數(shù)據(jù)按照每天進(jìn)行分區(qū)，保證數(shù)據(jù)的訪問效率。

3.2 軌跡間相似性度量方法

本文使用Lee J G等人[16]提出的軌跡間的相似性度量方法，該距離是3種距離的加權(quán)和表示，分別是其垂直距離d⊥、平行距離d||和角度距離dθ。給3種距離賦予相同的權(quán)重，即軌跡間的距離d=d⊥+d||+dθ。軌跡Li和Lj間的3種距離如圖7所示，其中，si、sj、ei、ej分別表示軌跡Li和Lj的起點(diǎn)和終點(diǎn)；ps和pe分別表示sj和ej在軌跡Li上的投影；l⊥1、l⊥2、l||1、l||2則分別表示圖7中對(duì)應(yīng)端點(diǎn)間的歐氏距離，||Lj||表示軌跡Lj的長度；θ表示兩條子軌跡的夾角（0°≤θ≤180°）。

3.3 改進(jìn)的層次聚類算法

給定時(shí)間段[to,td]，定義手機(jī)用戶i在該時(shí)間段的軌跡為Ti={Oi,Di}，其中to為起始時(shí)刻，td為結(jié)束時(shí)刻，Oi為用戶i在該時(shí)間段有最早記錄的位置，Di為用戶i在該時(shí)間段有最晚記錄的位置。定義T={Ti}為在給定時(shí)間段下，所有捕獲到的手機(jī)用戶軌跡的集合。定義O={Oi}為所有在T中用戶軌跡的起始位置的集合，D={Di}為所有在T中用戶軌跡的結(jié)束位置的集合。

圖5 找不到符合延時(shí)條件的點(diǎn)

圖6 同基站整合

圖7 軌跡間的3種距離

定義kNN(Oi，k)為屬于集合O并且距離點(diǎn)Oi最近的k個(gè)點(diǎn)。同理，kNN(Di，k)為屬于集合D并且距離點(diǎn)Di最近的k個(gè)點(diǎn)。

定義1 軌跡的kNN鄰近軌跡。一條軌跡Tp的kNN鄰近軌跡FN(Tp，k)={Tq∈T |Oq∈kNN(Op，k)∧Dq∈kNN(Dq，k)}，其中Op、Dp分別是軌跡Tp的起始位置和結(jié)束位置，Oq、Dq分別是軌跡Tq的起始位置和結(jié)束位置。

計(jì)算所有軌跡間的距離會(huì)十分耗時(shí)并且效率低，因此，只計(jì)算給定時(shí)間段下的每條軌跡和它的kNN鄰近軌跡的距離。為了能夠快速找到每條軌跡的起始位置的kNN鄰近點(diǎn)和結(jié)束位置的kNN鄰近點(diǎn)，對(duì)所有起始位置O和所有結(jié)束位置D分別建立k-d樹。k-d樹是一種分割k維數(shù)據(jù)空間的數(shù)據(jù)結(jié)構(gòu)，主要應(yīng)用于多維空間關(guān)鍵數(shù)據(jù)的搜索，如范圍搜索和最近鄰搜索。在本文中，位置信息為經(jīng)緯度坐標(biāo)，因此為二維空間，k為2。

層次聚類算法需要一個(gè)類間最大距離閾值來判斷兩個(gè)聚類是否合并。在判斷聚類Cx和Cy是否合并時(shí)，使用基于共享近鄰（shared nearest neighbor，SNN）的個(gè)數(shù)的方法計(jì)算SNN(Cx,Cy)[17]。與第3.2節(jié)提出的軌跡間距離計(jì)算方法不同，SNN(Cx,Cy)只用于判斷兩個(gè)聚類是否合并。改進(jìn)的凝聚層次聚類算法步驟如下。

算法1 凝聚軌跡聚類算法。

輸入：指定時(shí)間段的軌跡數(shù)據(jù)集T={Ti|1≤i≤n}，計(jì)算距離時(shí)鄰近軌跡的個(gè)數(shù)k。

輸出：聚類結(jié)果C={Cm|1＜m＜＜n}。

步驟1 為T的所有起始位置O和所有結(jié)束位置D分別建立k-d樹, 并得到每條軌跡的kNN鄰近軌跡。

步驟2 按照第3.2節(jié)計(jì)算距離的方法計(jì)算每條軌跡和它的kNN鄰近軌跡之間的距離,并根據(jù)距離升序排列。

步驟3 將每一條軌跡初始化為一個(gè)聚類。

步驟4 對(duì)按距離排序過后的每一個(gè)軌跡和它的鄰近軌跡(p,q)。首先找到p和q分別所在的聚類Cx、Cy，然后計(jì)算Cx和Cy之間的距離,如果x≠y，并且SNN(Cx,Cy)＜1，則Cx=Cx∪Cy，C=C-Cy。

在計(jì)算兩個(gè)聚類Cx和Cy之間的距離時(shí)，按照平均連接（average-linkage）算法聚類法，應(yīng)該計(jì)算Cx和Cy的軌跡之間的平均距離，但是這樣十分耗時(shí)。因此，使用近似但是效率高的方法計(jì)算聚類Cx和Cy之間的距離，計(jì)算過程如圖8所示，計(jì)算步驟如下。

算法2 類間距離計(jì)算算法。

輸入：聚類Cx和聚類Cy。

輸出：聚類Cx和聚類Cy之間的距離。

步驟1 分別計(jì)算聚類Cx和Cy的起始位置的質(zhì)心Ocx和Ocy以及結(jié)束位置的質(zhì)心Dcx和Dcy。

步驟2 從起始位置集O中找到最接近Ocx和Ocy的點(diǎn)Ocx’和Ocy’，從結(jié)束位置集D中找到最接近Dcx和Dcy的點(diǎn)Dcx’和Dcy’。

步驟3 生成兩個(gè)中間軌跡＜Ocx’，Dcx’＞和＜Ocy’，Dcy’＞表示聚類Cx和Cy。

步驟4 使用SNN(Ccx’,Ccy’)計(jì)算軌跡＜Ocx’，Dcx’＞和＜Ocy’，Dcy’＞之間的距離，用來近似表示聚類Cx和Cy之間的距離。

圖8 計(jì)算聚類Cx和Cy距離示意

3.4 軌跡可視化

通過上述軌跡聚類算法對(duì)用戶給定時(shí)間段下的手機(jī)用戶軌跡進(jìn)行聚類，得到了一組聚類結(jié)果。每個(gè)類用中間軌跡來代替該類，使用流向圖的方法將每個(gè)類的代表軌跡畫在地圖中，如圖9所示，顯示至少包含70條軌跡以上的類。其中，原始數(shù)據(jù)為上海電信手機(jī)用戶在顧村公園和歡樂谷兩個(gè)區(qū)域某天全天的24 278條軌跡數(shù)據(jù)，如圖9（a）所示。設(shè)置k=150，使用聚類算法聚成了2 917個(gè)類，最大的類包含了355條軌跡。其中90%以上的軌跡可以至少找到一條鄰近軌跡，每個(gè)軌跡平均有7條鄰近軌跡。有1 321條軌跡無法找到任何鄰近軌跡，會(huì)自己形成一個(gè)類，在軌跡可視化時(shí)會(huì)去除這些單獨(dú)的類。

本文設(shè)計(jì)了一種多地圖縮放級(jí)別的層次可視化方法，根據(jù)地圖的縮放級(jí)別，顯示不同聚類大小的軌跡。當(dāng)?shù)貓D縮放級(jí)別較小時(shí)，只顯示包含軌跡數(shù)量較大的類，如圖9（b）所示。當(dāng)擴(kuò)大地圖縮放級(jí)別時(shí)，增加顯示其他包含軌跡數(shù)量較小的類，如圖9（b）方框所示區(qū)域相同。其中，顏色越深的線表示包含軌跡數(shù)量越多的類；反之，顏色越淺的線表示包含軌跡數(shù)量越少的類。

使用熱力圖的方法表示用戶選擇的時(shí)間段的結(jié)束時(shí)刻的手機(jī)用戶分布情況，如圖9（c）所示，該圖表示的區(qū)域與圖10所示，圖10為14:00—14:05用戶的移動(dòng)軌跡和用戶在14:05時(shí)所在位置的熱力圖。熱力圖可以顯示大規(guī)模個(gè)體的整體狀況，顏色越深表示數(shù)目越大。

圖9 軌跡聚類結(jié)果可視化

3.5 參數(shù)選擇與算法對(duì)比

在軌跡聚類時(shí)，若參數(shù)k設(shè)置過小，結(jié)果會(huì)產(chǎn)生許多很小的類；反之若k設(shè)置過大，結(jié)果則會(huì)產(chǎn)生較大的類，并且計(jì)算量也會(huì)非常大。給定一個(gè)合適的類簇指標(biāo)，只要假設(shè)的類簇的數(shù)目等于或者高于真實(shí)的類簇的數(shù)目時(shí)，該指標(biāo)上升會(huì)很緩慢，而一旦試圖得到少于真實(shí)數(shù)目的類簇時(shí)，該指標(biāo)會(huì)急劇上升。本文類簇指標(biāo)選擇類簇的軌跡數(shù)量加權(quán)平均值，圖11表示選擇不同k值對(duì)應(yīng)的類簇的軌跡數(shù)量加權(quán)平均值。可以看到，當(dāng)k值取150左右時(shí)，類簇指標(biāo)的上升趨勢(shì)開始加快，通過蟻群優(yōu)化算法可以自動(dòng)得到最優(yōu)k值。圖12（b）為k=200的聚類結(jié)果，k=150的結(jié)果在

圖10 熱力圖

圖12 （a）為k=100的聚類結(jié)果，圖9（c）中。對(duì)比這3張地圖可以發(fā)現(xiàn)，盡管最大的類包含的軌跡數(shù)量不同、顯示的聚類結(jié)果有些細(xì)微的不同，但是總體的模式是相似的。結(jié)果表明k值的設(shè)定對(duì)聚類結(jié)果的影響和整體的分析不是十分敏感，當(dāng)需要看整體的流動(dòng)情況時(shí)，用戶可以選擇較大的k；當(dāng)需要看局部區(qū)域的流動(dòng)情況時(shí)，用戶可以選擇較小的k。

為了驗(yàn)證改進(jìn)算法的效率，本文分別使用傳統(tǒng)的凝聚層次聚類算法（agglomerative nesting，AGNES）、使用代表點(diǎn)的層次聚類算法（clustering using representatives，CURE）[19]以及本文改進(jìn)的凝聚層次聚類算法對(duì)不同條數(shù)的軌跡進(jìn)行聚類，結(jié)果見表1和圖13。實(shí)驗(yàn)結(jié)果表明，當(dāng)軌跡數(shù)量較少時(shí)，AGNES聚類算法效率比較高，CURE和本文改進(jìn)的聚類算法效率相對(duì)較低；當(dāng)軌跡數(shù)量較多時(shí)，CURE聚類算法的效率略好于AGNES聚類算法，但相比之下本文改進(jìn)的聚類算法效率最高，并且運(yùn)行時(shí)間呈線性增長。

圖11 不同k值對(duì)應(yīng)的類簇的軌跡數(shù)量加權(quán)平均值

圖12 不同k值的聚類結(jié)果

表1 聚類算法運(yùn)行時(shí)間對(duì)比

4 結(jié)束語

本文設(shè)計(jì)了一個(gè)基于大規(guī)模PCMD的可視分析方法，使用基于PCMD的基站定位方法得到手機(jī)用戶的出行數(shù)據(jù)，對(duì)用戶的出行軌跡進(jìn)行聚類，將結(jié)果呈現(xiàn)在可視分析系統(tǒng)中。用戶可以從時(shí)間和空間上對(duì)手機(jī)用戶進(jìn)行分析，發(fā)現(xiàn)其中隱含的規(guī)律。流向圖因箭頭本身的指向性讓分析人員可以容易地判斷出手機(jī)用戶整體的移動(dòng)方向，線條顏色的深淺可以清楚地表達(dá)流量的大小。熱力圖可以清晰地表示手機(jī)用戶在某時(shí)刻整體的分布情況。本文提出的軌跡聚類算法適用于大規(guī)模數(shù)據(jù)，效率高，可以將本文算法應(yīng)用到實(shí)時(shí)在線數(shù)據(jù)分析中，下一步將圍繞軌跡聚類算法結(jié)果優(yōu)劣的評(píng)價(jià)方面展開進(jìn)一步的工作。

圖13 聚類算法運(yùn)行時(shí)間對(duì)比

[1] ZHANG Y. User mobility from the view of cellular data networks [C]//IEEE INFOCOM 2014-IEEE Conference on Computer Communications, April 27-May 2, 2014, Toronto, Canada. Piscataway: IEEE Computer Society Press, 2014: 1348-1356.

[2] XIONG H, ZHANG D, ZHANG D, et al. Predicting mobile phone user locations by exploiting collective behavioral patterns[C]//The 2012 9th International Conference on Ubiquitous Intelligence and Computing and 9th International Conference on Autonomic and Trusted Computing, September 4-7, 2012, Fukuoka, Japan. [S.l.:s.n.], 2012: 164-171.

[3] ISAACMAN S, BECKER R, CáCERES R, et al. Identifying important places in people’s lives from cellular network data[C]//The 9th International Conference on Pervasive Computing, June 12-15, 2011, San Francisco, USA. Berlin: Springer Press, 2011: 133-151.

[4] 冉斌. 手機(jī)數(shù)據(jù)在交通調(diào)查和交通規(guī)劃中的應(yīng)用[J]. 城市交通, 2013, 11(1): 72-81. RAN B. Use of cellphone data in travel survey and transportation planning[J]. Urban Transport of China, 2013, 11(1): 72-81.

[5] ZHENG Y, CHEN Y, XIE X, et al. GeoLife2.0: a location-based social networking service[C]//The 2009 10th International Conference on Mobile Data Management: Systems, Services and Middleware, May 18-20, 2009, Taipei, China. New Jersey: IEEE Press, 2009: 357-358.

[6] 王睿, 趙方, 彭金華, 等. 基于Wi-Fi和藍(lán)牙融合的室內(nèi)定位算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2011, 48(S2): 28-33. WANG R, ZHAO F, PENG J H, et al. Combination of WI-FI and bluetooth for indoor localization [J]. Journal of Computer Research and Development, 2011, 48（S2）: 28-33.

[7] 汪飛, 張繁, 吳斐然, 等. 面向多源城市出行數(shù)據(jù)的可視化查詢模型[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2016, 28(1): 25-31. WANG F, ZHANG F, WU F R, et al. A visual query model for multi-source urban mobility data[J]. Journal of Computer-Aided Design & Computer Graphics, 2016, 28(1): 25-31.

[8] 王祖超, 袁曉如. 軌跡數(shù)據(jù)可視分析研究[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2015, 27(1): 9-25. WANG Z C, YUAN X R. Visual analysis of trajectory data[J]. Journal of Computer-Aided Design and Computer Graphics, 2015, 27(1): 9-25.

[9] 廖帥, 陳犖, 熊偉, 等. 面向位置服務(wù)的大規(guī)模移動(dòng)對(duì)象時(shí)空聚集分析原型系統(tǒng)[J]. 計(jì)算機(jī)研究與發(fā)展, 2015(S1): 107-111. LIAO S, CHEN L, XIONG W, et al. A LBS-oriented massive moving objects spatiotemporal aggregation analysis prototype system[J]. Journal of Computer Research and Development, 2015(S1): 107-111.

[10] ZHOU H, XU P, YUAN X, et al. Edgebundling in information visualization[J]. Tsinghua Science and Technology, 2013, 18(2): 145-156.

[11] GUO D, ZHU X. Origin-Destination flow data smoothing and mapping[J]. IEEE Trans on Visualization & Computer Graphics, 2014, 20(12): 2043-2052.

[12] ANDRIENKO N, ANDRIENKO G. Spatial generalization and aggregation of massive movement data[J]. IEEE Trans on Visualization & Computer Graphics, 2011, 17(2): 205-219.

[13] VON L T, BRODKORB F, ROSKOSCH P, et al. MobilityGraphs: visual analysis of mass mobility dynamics via spatio-temporal graphs and clustering[J]. IEEE Trans on Visualization & Computer Graphics, 2016, 22(1): 11-20.

[14] 鄧平, 李莉, 范平志. 一種TDOA/AOA混合定位算法及其性能分析[J]. 電波科學(xué)學(xué)報(bào), 2002, 17(6): 633-636. DENG P, LI L, FAN P Z. A hybrid TDOA/AOA location algorithm and its performance analysis[J]. Chinese Journal of Radio Science, 2002, 17(6): 633-636.

[15] 張大鵬, 張錦, 郭敏泰, 等. 開源WebGIS軟件應(yīng)用開發(fā)技術(shù)和方法研究[J]. 測(cè)繪科學(xué), 2011, 36(5): 193-196. ZHANG D P, ZHANG J, GUO M T. Application development technology and methods of open-source WebGIS software[J]. Science of Surveying & Mapping, 2011, 36(5): 193-196.

[16] LEE J G, HAN J, WHANG K Y. Trajectory clustering: a partition-and-group framework[C]//The 2007 ACM SIGMOD International Conference on Management of Data, June 11-14,2007, Beijing, China. New York : ACM Press, 2007: 593-604.

[17] ZHU X, GUO D. Mapping large spatial flow data with hierarchical clustering[J]. Transactions in Gis, 2014, 18(3): 421-435.

[18] RAJARAMAN A, ULLMAN J D. Mining of massive datasets[M].Cambridge: Cambridge University Press, 2012.

[19] MIN Y, LI Y. Vehicles recognition based on the size characteristics and the CURE clustering algorithm[C]// The 2015 IEEE International Conference on Signal Processing, Communications and Computing, September 19-22, 2015，Ningbo, China. New Jersey: IEEE Press, 2015: 7-11.

Visual analyses of mobile phone base station location data

LI Haisheng1,2, HUANG Yuanjie1,2, SONG Xuan1,2, DU Junping3, CHEN Guorun4, DING Fuqiang4
1.School of Computer and Information Engineering, Beijing Technology and Business University, Beijing 100048, China 2.Beijing Key Laboratory of Big Data Technology for Food Safety, Beijing 100048, China 3.School of Computer Science, Beijing University of Posts and Telecommunications, Beijing 100876, China 4.Shanghai Ideal Information Industry(Group) Co., Ltd., Shanghai 201315, China

Mobile phone base station location data contains rich spatio-temporal information. A visual analytic method based on per call measurement data (PCMD) was designed. A base station positioning method based on PCMD to extract mobile phone users’trajectories was designed. An agglomerate hierarchical clustering algorithm was improved to cluster trajectories efficiently. Flow map and heat map were employed to present the clustering result and the overall distribution of mobile phone users at a specific time. This method was applied to the dataset of Shanghai mobile phone base station data, which has achieved satisfied results.

mobile phone base station location data, trajectory clustering, flow map, visual analyses

TP399

A

10.11959/j.issn.2096-0271.2017008

李海生（1974-），男，博士，食品安全大數(shù)據(jù)技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室、北京工商大學(xué)計(jì)算機(jī)與信息工程學(xué)院教授、研究生導(dǎo)師，主要研究方向?yàn)閿?shù)據(jù)可視化與可視分析、計(jì)算機(jī)圖形學(xué)、科學(xué)可視化、三維模型檢索等。

黃媛潔（1992-），女，食品安全大數(shù)據(jù)技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室、北京工商大學(xué)計(jì)算機(jī)與信息工程學(xué)院碩士生，主要研究方向?yàn)閿?shù)據(jù)可視化與可視分析。

宋璇（1993-），女，食品安全大數(shù)據(jù)技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室、北京工商大學(xué)計(jì)算機(jī)與信息工程學(xué)院碩士生，主要研究方向?yàn)閿?shù)據(jù)可視化與可視分析。

杜軍平（1963-），女，博士，北京郵電大學(xué)計(jì)算機(jī)學(xué)院教授、博士生導(dǎo)師，主要研究方向?yàn)檫\(yùn)動(dòng)圖像處理、視覺與信息獲取等。

陳國潤（1978-），男，上海理想信息產(chǎn)業(yè)（集團(tuán)）有限公司電信支撐軟件部研發(fā)部經(jīng)理，主要研究方向?yàn)樵朴?jì)算管理、分布式數(shù)據(jù)處理。

丁富強(qiáng)（1973-），男，博士，上海理想信息產(chǎn)業(yè)（集團(tuán)）有限公司研發(fā)中心主任，主要研究方向?yàn)殡娦糯髷?shù)據(jù)應(yīng)用研究。

2016-11-25

國家自然科學(xué)基金資助項(xiàng)目(No.61532006)；北京市自然科學(xué)基金資助項(xiàng)目(No.4162019)；北京市科技計(jì)劃課題資助項(xiàng)目(No. Z161100001616004)

Foundation Items:The National Natural Science Foundation of China (No.61532006), The Beijing Municipal Natural Science Foundation (No.4162019), Beijing Science and Technology Project (No. Z161100001616004)