1 引言

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

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

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

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

2 相關(guān)工作

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

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

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

對(duì)手機(jī)定位數(shù)據(jù)的挖掘和分析可以幫助調(diào)整交通政策以及基礎(chǔ)設(shè)施的建設(shè)，使得城市的居民能獲得更好的出行體驗(yàn)。冉斌提出了手機(jī)數(shù)據(jù)在交通調(diào)查以及交通規(guī)劃中的應(yīng)用，通過(guò)手機(jī)話(huà)單定位數(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)重的視覺(jué)混亂和不清晰的問(wèn)題。一種解決方法是使用邊捆綁技術(shù)，通過(guò)彎曲邊使相似的邊相互靠近形成一束，以減少相互遮擋。

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

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

3 可視分析算法描述

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

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

3.1 基于PCMD的基站定位方法

一條PCMD中包含兩個(gè)關(guān)鍵時(shí)間信息，分別為初始時(shí)刻和終止時(shí)刻的時(shí)間戳，這反映了手機(jī)接入和斷開(kāi)網(wǎng)絡(luò)的時(shí)間。PCMD每次獲取一組信息，其中與定位相關(guān)的信息有基站號(hào)、扇區(qū)號(hào)、時(shí)延、電磁輻射場(chǎng)強(qiáng)等。定位的關(guān)鍵信息是場(chǎng)強(qiáng)和時(shí)延。但是場(chǎng)強(qiáng)更容易受到環(huán)境、建筑、天氣、電網(wǎng)、屏蔽體、設(shè)備等的影響，在城市內(nèi)尤甚，定位的準(zhǔn)確度難以保證。與場(chǎng)強(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)的弧，由于沒(méi)有其他補(bǔ)充信息，無(wú)法將用戶(hù)定位到弧的具體點(diǎn)上，因此取弧的中點(diǎn)作為用戶(hù)的期望位置，如圖2(a)所示;當(dāng)兩個(gè)扇區(qū)的時(shí)延相同時(shí)，不能判定用戶(hù)在哪段弧上，這時(shí)以?xún)苫〉呐R界點(diǎn)作為期望位置，如圖2(b)所示;當(dāng)3個(gè)扇區(qū)的時(shí)延相同時(shí)，用戶(hù)可能位于一個(gè)圓周的任意位置，這時(shí)以基站的位置作為期望位置，如圖2(c)所示。

圖2 單基站定位

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

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

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

圖4 找到符合時(shí)延條件的兩個(gè)點(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)混合定位算法。

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

圖6 同基站整合

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

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的長(zhǎng)度;θ表示兩條子軌跡的夾角(0°≤θ≤180°)。

圖7 軌跡間的3種距離

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

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

定義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樹(shù)。k-d樹(shù)是一種分割k維數(shù)據(jù)空間的數(shù)據(jù)結(jié)構(gòu)，主要應(yīng)用于多維空間關(guān)鍵數(shù)據(jù)的搜索，如范圍搜索和最近鄰搜索。在本文中，位置信息為經(jīng)緯度坐標(biāo)，因此為二維空間，k為2。

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

算法1 凝聚軌跡聚類(lèi)算法。

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

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

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

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

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

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

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

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

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

輸入：聚類(lèi)Cx和聚類(lèi)Cy。

輸出：聚類(lèi)Cx和聚類(lèi)Cy之間的距離。

步驟1 分別計(jì)算聚類(lèi)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’>表示聚類(lèi)Cx和Cy。

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

3.4 軌跡可視化

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

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

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

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

圖10 熱力圖

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

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

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

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

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

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

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

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

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

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