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

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

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

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

1 引言

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

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

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

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

2 相關(guān)工作

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

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

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

對手機(jī)定位數(shù)據(jù)的挖掘和分析可以幫助調(diào)整交通政策以及基礎(chǔ)設(shè)施的建設(shè)，使得城市的居民能獲得更好的出行體驗。冉斌[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)一步分析城市人口的時空動態(tài)分布等。

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

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

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

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

3 可視分析算法描述

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

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

3.1 基于PCMD的基站定位方法

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

（1）單基站定位

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

圖2 單基站定位

圖3 找到符合時延條件的一個點

圖4 找到符合時延條件的兩個點

（2）兩點定位

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

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

（3）3點及多點定位方法

當(dāng)一條PCMD中包含3個或更多基站的數(shù)據(jù)，則可以進(jìn)行較為準(zhǔn)確的定位?；驹蕉啵ㄎ痪仍礁摺１疚氖褂玫竭_(dá)時間差（time difference of arrival，TDOA）/到達(dá)角度測距（angle of arrival，AOA）混合定位算法[14]。

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

通過上述基站定位方法，可以得到每條PCMD對應(yīng)的用戶的位置和時間信息。然后將一天的時間劃分為長度相等的時間片段，得到每個用戶在每個時間段對應(yīng)的起始位置和結(jié)束位置。時間段的長度基于PCMD的獲取頻率和用戶的需求來選擇。由于空間數(shù)據(jù)具有空間位置、非結(jié)構(gòu)化、空間關(guān)系、分類編碼、海量數(shù)據(jù)等特征[15]，為了有效地進(jìn)行空間查詢，使用PostgreSQL數(shù)據(jù)庫中的PostGIS①http://www. postgis.org/來存儲數(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的起點和終點；ps和pe分別表示sj和ej在軌跡Li上的投影；l⊥1、l⊥2、l||1、l||2則分別表示圖7中對應(yīng)端點間的歐氏距離，||Lj||表示軌跡Lj的長度；θ表示兩條子軌跡的夾角（0°≤θ≤180°）。

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

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

圖5 找不到符合延時條件的點

圖6 同基站整合

圖7 軌跡間的3種距離

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

定義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é)束位置。

計算所有軌跡間的距離會十分耗時并且效率低，因此，只計算給定時間段下的每條軌跡和它的kNN鄰近軌跡的距離。為了能夠快速找到每條軌跡的起始位置的kNN鄰近點和結(jié)束位置的kNN鄰近點，對所有起始位置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。

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

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

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

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

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

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

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

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

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

算法2 類間距離計算算法。

輸入：聚類Cx和聚類Cy。

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

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

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

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

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

圖8 計算聚類Cx和Cy距離示意

3.4 軌跡可視化

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

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

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

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

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

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

圖10 熱力圖

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

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

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

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

表1 聚類算法運行時間對比

4 結(jié)束語

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

圖13 聚類算法運行時間對比

[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ī)研究與發(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ī)輔助設(shè)計與圖形學(xué)學(xué)報, 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ī)輔助設(shè)計與圖形學(xué)學(xué)報, 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ī)模移動對象時空聚集分析原型系統(tǒng)[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é)報, 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]. 測繪科學(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ù)北京市重點實驗室、北京工商大學(xué)計算機(jī)與信息工程學(xué)院教授、研究生導(dǎo)師，主要研究方向為數(shù)據(jù)可視化與可視分析、計算機(jī)圖形學(xué)、科學(xué)可視化、三維模型檢索等。

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

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

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

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

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

2016-11-25

國家自然科學(xué)基金資助項目(No.61532006)；北京市自然科學(xué)基金資助項目(No.4162019)；北京市科技計劃課題資助項目(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)