1 引言

隨著手機(jī)等移動終端的普及，在城市中2G/3G/4G網(wǎng)絡(luò)已經(jīng)基本實(shí)現(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ù)中的一類，在分析人群移動模式、城市功能區(qū)識別以及交通網(wǎng)絡(luò)規(guī)劃中都提供了很大的幫助。

通常，手機(jī)等移動終端收集到的定位數(shù)據(jù)可以來自移動通信網(wǎng)絡(luò)、Wi-Fi接入點(diǎn)位置信息、移動終端的GPS定位信息等，記錄了移動對象的位置、時間、速度和方向等行為特征。GPS定位數(shù)據(jù)最為精確，多由志愿者提供，因此樣本數(shù)量很少并且難以獲取。Wi-Fi接入點(diǎn)數(shù)據(jù)也較為精確，但多用于室內(nèi)定位。移動通信網(wǎng)絡(luò)能夠定期或不定期地主動或被動地記錄手機(jī)用戶時間序列的基站編號，該種定位方式精確度低，數(shù)據(jù)粒度不均勻，往往需要配合其他類型數(shù)據(jù)來分析，但在樣本量、覆蓋范圍以及實(shí)施成本和周期上更具有優(yōu)勢。本文使用的手機(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ù)的可視化。采用聚集可視化的方法，將對象個體數(shù)據(jù)轉(zhuǎn)換為聚集值，能夠觀察移動對象的群體特征，同時也能減少刻畫群體特征的數(shù)據(jù)量。

本文設(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使用用戶上網(wǎng)時產(chǎn)生的蜂窩數(shù)據(jù)信息進(jìn)行人群移動模式建模，并且能夠預(yù)測出某個特定用戶在給定位置可能用到的應(yīng)用軟件。Xiong H等人發(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)人類生活中重要的位置信息，比如居住地點(diǎn)和工作地點(diǎn)等。Isaacman S等人提出一種基于聚集和回歸的方法，分析蜂窩網(wǎng)絡(luò)數(shù)據(jù)，發(fā)現(xiàn)有意義的位置信息，計算出通勤距離，并且通過幾十萬匿名用戶的碳排放量分析，證明了該算法可以作為有效的政策和基礎(chǔ)設(shè)施研究的支撐。

對手機(jī)定位數(shù)據(jù)的挖掘和分析可以幫助調(diào)整交通政策以及基礎(chǔ)設(shè)施的建設(shè)，使得城市的居民能獲得更好的出行體驗(yàn)。冉斌提出了手機(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ù)，通過彎曲邊使相似的邊相互靠近形成一束，以減少相互遮擋。

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

Andrienko N等人提出了一種對移動數(shù)據(jù)進(jìn)行空間泛化和聚集的方法，將數(shù)據(jù)覆蓋的版圖劃分成適當(dāng)?shù)男^(qū)域。Von L T等人使用了上述劃分版圖的方法，先對區(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ǔ)充信息，無法將用戶定位到弧的具體點(diǎn)上，因此取弧的中點(diǎn)作為用戶的期望位置，如圖2(a)所示;當(dāng)兩個扇區(qū)的時延相同時，不能判定用戶在哪段弧上，這時以兩弧的臨界點(diǎn)作為期望位置，如圖2(b)所示;當(dāng)3個扇區(qū)的時延相同時，用戶可能位于一個圓周的任意位置，這時以基站的位置作為期望位置，如圖2(c)所示。

圖2 單基站定位

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

當(dāng)一條PCMD中包含2個基站的數(shù)據(jù)時，使用兩點(diǎn)定位方法。與單基站定位的情形相似，用戶到達(dá)某個基站不同扇區(qū)的時延可能不完全相同，為減少多徑效應(yīng)的影響，仍使用到達(dá)各個基站的最小時延作為計算依據(jù)。當(dāng)找到符合時延條件的一個點(diǎn)時，該點(diǎn)作為用戶的期望位置，如圖3所示。圖4表示找到符合時延條件的兩個點(diǎn)的情況，如果兩點(diǎn)中只有一點(diǎn)滿足扇區(qū)條件，如圖4(a)所示，則取該點(diǎn)為用戶的期望位置;如果兩點(diǎn)都滿足或都不滿足扇區(qū)條件，如圖4(b)所示，則取與兩個基站有效扇區(qū)正方向的總誤差更小的點(diǎn)的位置。如果找不到符合時延條件的點(diǎn)，如圖5所示，則取時延總誤差最小的點(diǎn)作為用戶的期望位置。

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

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

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

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

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

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

圖6 同基站整合

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

圖7 軌跡間的3種距離

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é)束位置的集合。

定義kNN(Oi，k)為屬于集合O并且距離點(diǎn)Oi最近的k個點(diǎn)。同理，kNN(Di，k)為屬于集合D并且距離點(diǎn)Di最近的k個點(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é)束位置。

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

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

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

輸入：聚類Cx和聚類Cy。

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

步驟1 分別計算聚類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 生成兩個中間軌跡<Ocx’，Dcx’>和<Ocy’，Dcy’>表示聚類Cx和Cy。

步驟4 使用SNN(Ccx’,Ccy’)計算軌跡<Ocx’，Dcx’>和<Ocy’，Dcy’>之間的距離，用來近似表示聚類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條軌跡無法找到任何鄰近軌跡，會自己形成一個類，在軌跡可視化時會去除這些單獨(dú)的類。

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

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

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

圖10 熱力圖

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

在軌跡聚類時，若參數(shù)k設(shè)置過小，結(jié)果會產(chǎn)生許多很小的類;反之若k設(shè)置過大，結(jié)果則會產(chǎn)生較大的類，并且計算量也會非常大。給定一個合適的類簇指標(biāo)，只要假設(shè)的類簇的數(shù)目等于或者高于真實(shí)的類簇的數(shù)目時，該指標(biāo)上升會很緩慢，而一旦試圖得到少于真實(shí)數(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值。

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

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

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

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

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

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

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í)時在線數(shù)據(jù)分析中，下一步將圍繞軌跡聚類算法結(jié)果優(yōu)劣的評價方面展開進(jìn)一步的工作。