吳子嘯

(中國(guó)城市規(guī)劃設(shè)計(jì)研究院，北京 100037)

1 研究概述

1.1 手機(jī)數(shù)據(jù)類(lèi)型及特征

與其他類(lèi)型大數(shù)據(jù)類(lèi)似，手機(jī)數(shù)據(jù)也是一種被動(dòng)產(chǎn)生的痕跡數(shù)據(jù)，即用戶(hù)使用手機(jī)進(jìn)行通訊活動(dòng)(通話(huà)、短信等)和運(yùn)營(yíng)商提供通訊服務(wù)的痕跡數(shù)據(jù)。由于手機(jī)痕跡數(shù)據(jù)包含位置和時(shí)間信息，從而提供了人們出行和活動(dòng)的線(xiàn)索。與傳統(tǒng)交通調(diào)查數(shù)據(jù)相比，手機(jī)數(shù)據(jù)具有大樣本、可持續(xù)、成本低等優(yōu)點(diǎn)，為未來(lái)交通研究和交通建模提供了全新的數(shù)據(jù)資源。

相關(guān)研究中通常將手機(jī)數(shù)據(jù)分為兩類(lèi)：一類(lèi)是通話(huà)詳單數(shù)據(jù)(Call Detail Record Data, CDR)，另一類(lèi)是信令數(shù)據(jù)(Sightings Data)。CDR 數(shù)據(jù)是由用戶(hù)使用手機(jī)進(jìn)行通訊活動(dòng)產(chǎn)生的痕跡數(shù)據(jù)，通常包含通訊活動(dòng)的用戶(hù)ID、起始時(shí)間、時(shí)長(zhǎng)信息以及服務(wù)基站信息；信令數(shù)據(jù)是運(yùn)營(yíng)商提供通訊服務(wù)的痕跡數(shù)據(jù)，除了由用戶(hù)進(jìn)行通訊活動(dòng)觸發(fā)外，還可以由服務(wù)區(qū)切換等網(wǎng)絡(luò)活動(dòng)觸發(fā)。與CDR 數(shù)據(jù)不同，信令數(shù)據(jù)中的位置信息通常為幾個(gè)基站間通過(guò)三角算法計(jì)算的結(jié)果。因此，信令數(shù)據(jù)的時(shí)間密度和位置信息精度均高于CDR數(shù)據(jù)[1]。

手機(jī)數(shù)據(jù)的時(shí)間密度因用戶(hù)而異，并且非常不規(guī)則。通常在某一小段時(shí)間內(nèi)，手機(jī)數(shù)據(jù)密集出現(xiàn)，在較長(zhǎng)且不規(guī)律的時(shí)間后，手機(jī)數(shù)據(jù)再次密集發(fā)生。為了表示手機(jī)數(shù)據(jù)的時(shí)間密度，通常將一天劃分為以0.5 h 為單位的時(shí)段，在一個(gè)時(shí)段內(nèi)有一個(gè)或多個(gè)手機(jī)數(shù)據(jù)即表示該時(shí)段出現(xiàn)手機(jī)數(shù)據(jù)，而以出現(xiàn)手機(jī)數(shù)據(jù)的時(shí)段數(shù)表示時(shí)間密度并據(jù)此計(jì)算手機(jī)數(shù)據(jù)出現(xiàn)的時(shí)間間隔。CDR數(shù)據(jù)的時(shí)間間隔可以達(dá)到數(shù)小時(shí)之久[2]，而信令數(shù)據(jù)的時(shí)間間隔通常也超過(guò)1 h[3]。本文采用某城市2015年的手機(jī)數(shù)據(jù)，以手機(jī)數(shù)據(jù)出現(xiàn)時(shí)段最多的15 h(大多數(shù)出行和活動(dòng)集中的時(shí)段7:00—22:00)為研究周期，統(tǒng)計(jì)得到手機(jī)數(shù)據(jù)平均出現(xiàn)時(shí)段數(shù)量分布(見(jiàn)圖1)。手機(jī)數(shù)據(jù)出現(xiàn)的時(shí)段數(shù)量平均為9.1 個(gè)，平均時(shí)間間隔為84 min，數(shù)據(jù)特征與已有文獻(xiàn)中的描述基本吻合。預(yù)計(jì)未來(lái)隨著智能手機(jī)用戶(hù)比例的上升，手機(jī)數(shù)據(jù)的時(shí)間密度將會(huì)顯著提高。

圖1 手機(jī)數(shù)據(jù)的時(shí)間密度分布Fig.1 Time-density distribution of cell phone data

圖2 手機(jī)數(shù)據(jù)誤差示例Fig.2 Example of cell phone data error

根據(jù)大多數(shù)城市的居民出行調(diào)查結(jié)果，城市居民單次出行平均出行時(shí)耗大多集中在20～30 min。結(jié)合手機(jī)數(shù)據(jù)的平均時(shí)間間隔可以判斷，由手機(jī)數(shù)據(jù)推演出行時(shí)耗的可靠性不高，并且一些出行活動(dòng)也不能被手機(jī)數(shù)據(jù)所反映。

1.2 手機(jī)數(shù)據(jù)處理的關(guān)鍵問(wèn)題

1）乒乓效應(yīng)和數(shù)據(jù)漂移。

在通信網(wǎng)絡(luò)覆蓋的區(qū)域，通常一個(gè)具體地點(diǎn)會(huì)被周?chē)鷰讉€(gè)基站的信號(hào)重疊覆蓋。該區(qū)域內(nèi)的手機(jī)所聯(lián)系的基站會(huì)隨各基站信號(hào)強(qiáng)度的變化而不斷改變，從而產(chǎn)生在兩個(gè)或多個(gè)基站間來(lái)回切換的現(xiàn)象，該現(xiàn)象被稱(chēng)為“乒乓效應(yīng)”。另外，為保證手機(jī)用戶(hù)通訊的效率與質(zhì)量，服務(wù)基站往往有負(fù)荷優(yōu)化的調(diào)節(jié)機(jī)制。當(dāng)手機(jī)鄰近的基站負(fù)荷較大時(shí)，手機(jī)信號(hào)會(huì)被自動(dòng)切換至較遠(yuǎn)且負(fù)荷較小的基站，從而產(chǎn)生信號(hào)的漂移。因此，手機(jī)數(shù)據(jù)對(duì)地點(diǎn)的代表具有很大的不確定性。文獻(xiàn)[4]對(duì)于信令數(shù)據(jù)的研究認(rèn)為其在城市區(qū)域的位置誤差在300 m 以?xún)?nèi)。文獻(xiàn)[5]認(rèn)為CDR 數(shù)據(jù)的位置誤差可以從幾百米到幾千米，主要取決于基站的密度。如圖2 所示，數(shù)據(jù)在兩個(gè)主要活動(dòng)地點(diǎn)有大量的乒乓效應(yīng)并伴隨數(shù)據(jù)漂移現(xiàn)象。文獻(xiàn)[6]指出乒乓效應(yīng)和數(shù)據(jù)漂移的數(shù)據(jù)約占數(shù)據(jù)總量的30%。

乒乓效應(yīng)和數(shù)據(jù)漂移并不代表用戶(hù)的真實(shí)移動(dòng)，對(duì)這類(lèi)數(shù)據(jù)進(jìn)行處理是利用手機(jī)數(shù)據(jù)進(jìn)行出行鏈推演的重要一環(huán)。在這方面研究中，已有三種方法被提出和應(yīng)用。文獻(xiàn)[7]提出基于速度的方法：即當(dāng)基站(或位置點(diǎn))A夾雜在基站(或位置點(diǎn))B中并且由A至B的轉(zhuǎn)換速度超過(guò)一個(gè)設(shè)定的極限值，則定義為乒乓效應(yīng)。在手機(jī)數(shù)據(jù)的時(shí)間密度較低并存在空間不確定性的情況下，選擇一個(gè)速度極限值是該方法的一個(gè)挑戰(zhàn)。文獻(xiàn)[6]和文獻(xiàn)[8]則提出基于模式的方法，即根據(jù)乒乓效應(yīng)的特征定義幾個(gè)基站(或位置點(diǎn))間切換的模式，當(dāng)檢測(cè)到該模式時(shí)即視為乒乓效應(yīng)進(jìn)行處理。由于實(shí)際中乒乓效應(yīng)的形式非常多樣，有時(shí)發(fā)生在兩個(gè)基站間、有時(shí)發(fā)生在多個(gè)基站間，并間雜有數(shù)據(jù)漂移現(xiàn)象，因此，將所有乒乓效應(yīng)的模式進(jìn)行列舉十分困難；另一方面，實(shí)際發(fā)生在兩點(diǎn)之間的真實(shí)高頻移動(dòng)可能會(huì)被誤以為乒乓效應(yīng)。將以上兩種方法結(jié)合而成的混合方法也是比較常見(jiàn)的應(yīng)用[9]，但也無(wú)法完全避免各自方法內(nèi)在的缺陷。

2）活動(dòng)地點(diǎn)識(shí)別。

利用手機(jī)數(shù)據(jù)進(jìn)行出行鏈推演的另一個(gè)關(guān)鍵點(diǎn)是對(duì)于活動(dòng)地點(diǎn)的識(shí)別。一般認(rèn)為，停留超過(guò)一定時(shí)間(通常為10 min)的位置點(diǎn)可以視為一個(gè)活動(dòng)地點(diǎn)。由于手機(jī)數(shù)據(jù)的空間不確定性，需要將空間臨近的位置點(diǎn)聚合在一點(diǎn)才能形成停留時(shí)間的累積。聚類(lèi)算法通常用來(lái)實(shí)現(xiàn)這一目標(biāo)。在眾多聚類(lèi)算法中，無(wú)須預(yù)設(shè)參數(shù)的基于距離的聚類(lèi)算法[10-11]最受青睞。文獻(xiàn)[5]提出另一種不需預(yù)設(shè)參數(shù)的聚類(lèi)方法，即基于模型的聚類(lèi)方法。但該方法對(duì)于時(shí)間密度稀疏的手機(jī)數(shù)據(jù)的運(yùn)行效果并不理想[1]。顯而易見(jiàn)，基于距離的聚類(lèi)算法的結(jié)果容易受到數(shù)據(jù)漂移的影響。例如，在幾個(gè)時(shí)間相繼、空間臨近的位置點(diǎn)中夾雜一個(gè)較遠(yuǎn)距離的數(shù)據(jù)漂移，聚類(lèi)的結(jié)果將由一個(gè)類(lèi)(位置點(diǎn)集合)變成三個(gè)類(lèi)，漂移數(shù)據(jù)成為其中單獨(dú)的一類(lèi)。這顯然會(huì)影響位置點(diǎn)停留時(shí)間的累積，進(jìn)而影響活動(dòng)地點(diǎn)的識(shí)別。

文獻(xiàn)[12-15]提出一種改進(jìn)的基于距離的聚類(lèi)算法，即隨著類(lèi)中位置點(diǎn)的增加，重新計(jì)算類(lèi)的型心。這種改進(jìn)方法可以在一定限度上提高算法對(duì)乒乓效應(yīng)和漂移數(shù)據(jù)的容忍度，但算法有效性仍然會(huì)受到數(shù)據(jù)空間不確定性的影響。

手機(jī)數(shù)據(jù)的預(yù)處理與活動(dòng)地點(diǎn)的識(shí)別相互依賴(lài)、相互影響。大量乒乓效應(yīng)和數(shù)據(jù)漂移會(huì)影響活動(dòng)地點(diǎn)識(shí)別算法的效率和準(zhǔn)確性。因此，在大多數(shù)處理CDR 數(shù)據(jù)的流程中，先進(jìn)行手機(jī)數(shù)據(jù)的預(yù)處理[16]，再執(zhí)行聚類(lèi)算法進(jìn)行活動(dòng)地點(diǎn)識(shí)別。而對(duì)于信令數(shù)據(jù)，文獻(xiàn)[1]認(rèn)為應(yīng)先執(zhí)行聚類(lèi)算法消除空間不確定性，才能有效識(shí)別和處理乒乓效應(yīng)。迄今為止，眾多研究在城市層面上基于手機(jī)數(shù)據(jù)進(jìn)行活動(dòng)和出行鏈的推算[1,16]，但算法在個(gè)體數(shù)據(jù)層面的有效性從未詳細(xì)探討。手機(jī)數(shù)據(jù)乒乓效應(yīng)和漂移的內(nèi)在規(guī)律目前仍不明確，對(duì)這些數(shù)據(jù)預(yù)處理方法的有效性也難以評(píng)價(jià)。與以往研究不同，本文提出一種新的方法——時(shí)空貪婪同化法，該方法更多地利用了人們出行和活動(dòng)的一般規(guī)律以及手機(jī)數(shù)據(jù)在某一時(shí)段密集出現(xiàn)的特征，最大限度地消除手機(jī)數(shù)據(jù)的空間不確定性。另外，改進(jìn)的空間聚類(lèi)算法在進(jìn)行類(lèi)型心更新時(shí)，考慮了位置點(diǎn)的停留時(shí)長(zhǎng)，能夠更加有效地錨固居住地、工作地等人們長(zhǎng)時(shí)間停留的活動(dòng)點(diǎn)，從而更加準(zhǔn)確地推算出行鏈。

2 算法描述

本文提出基于手機(jī)數(shù)據(jù)推演出行鏈的算法流程，如圖3所示。

2.1 數(shù)據(jù)初始化

數(shù)據(jù)初始化的步驟主要包括：1)對(duì)手機(jī)數(shù)據(jù)進(jìn)行柵格化處理，以柵格型心經(jīng)緯度取代落在柵格內(nèi)各位置點(diǎn)的經(jīng)緯度。手機(jī)數(shù)據(jù)位置點(diǎn)從本源上均是基于基站定位的，而手機(jī)基站經(jīng)緯度通常有保密性要求，柵格化處理一方面可以實(shí)現(xiàn)保密的目的，另一方面，不同數(shù)據(jù)源(如基于基站定位的數(shù)據(jù)和基于三角定位的數(shù)據(jù))可進(jìn)行融合處理。2)建立各位置點(diǎn)的開(kāi)始時(shí)間和結(jié)束時(shí)間項(xiàng)。有些手機(jī)信令數(shù)據(jù)既給出信令開(kāi)始時(shí)間也給出了信令結(jié)束時(shí)間。在只給出信令開(kāi)始時(shí)間時(shí)，可以在開(kāi)始時(shí)間上加一個(gè)極小的時(shí)間段(如20 s)生成信令結(jié)束時(shí)間，這樣手機(jī)時(shí)空數(shù)據(jù)的一條記錄可表示為li表示第i條數(shù)據(jù)記錄的位置點(diǎn)，tis和tif分別表示第i條數(shù)據(jù)記錄的開(kāi)始時(shí)間和結(jié)束時(shí)間，數(shù)據(jù)記錄集合為N。3)按開(kāi)始時(shí)間對(duì)所有數(shù)據(jù)記錄進(jìn)行排序，合并同一位置點(diǎn)的相鄰數(shù)據(jù)記錄。也就是說(shuō)，將同一位置點(diǎn)的所有相鄰數(shù)據(jù)記錄合并為一條新記錄，新記錄的開(kāi)始時(shí)間設(shè)為被合并數(shù)據(jù)記錄中開(kāi)始時(shí)間的最小值，結(jié)束時(shí)間設(shè)為這些數(shù)據(jù)記錄中結(jié)束時(shí)間的最大值。

2.2 時(shí)空貪婪同化

圖3 算法流程Fig.3 Algorithm process

時(shí)空貪婪同化的基本思想是依次從當(dāng)前數(shù)據(jù)記錄集中找出最頻繁出現(xiàn)的位置點(diǎn)(即數(shù)據(jù)記錄最多的位置點(diǎn))，識(shí)別短時(shí)間內(nèi)夾雜在該位置點(diǎn)的兩條數(shù)據(jù)記錄間的其他位置點(diǎn)，形成位置點(diǎn)集合進(jìn)行同化。由于借鑒了貪婪算法的思想，該步驟被稱(chēng)為時(shí)空貪婪同化流程。具體算法如下：

1）將初始化的數(shù)據(jù)記錄集N設(shè)為當(dāng)前數(shù)據(jù)記錄集，時(shí)間段集合T設(shè)為空集；

2）從當(dāng)前數(shù)據(jù)記錄集中找出數(shù)據(jù)記錄最多的位置點(diǎn)m，提取位置點(diǎn)m的所有數(shù)據(jù)記錄生成數(shù)據(jù)記錄子集Nm={mj,tjs,tjf}，并生成位置點(diǎn)集合Cm={m}；

3）從Nm中第一條記錄開(kāi)始，若當(dāng)前數(shù)據(jù)記錄的結(jié)束時(shí)間距下一條記錄的開(kāi)始時(shí)間的間隔小于等于τ，即(t(j+1)s-tjf)≤τ，則更新時(shí)間段集合T=?j(tjf,t(j+1)s)，執(zhí)行完畢生成時(shí)間段集合T；

4）對(duì)于當(dāng)前數(shù)據(jù)記錄集N中的每一條數(shù)據(jù)記錄(li,tis,tif)，若(tis,tif)?T并且li不在位置點(diǎn)集合Cm中，則將li加入Cm中，執(zhí)行完畢生成位置點(diǎn)集合Cm，并計(jì)算Cm的型心經(jīng)緯度，即為其所包含的各位置點(diǎn)經(jīng)緯度的加權(quán)平均值，權(quán)重為各位置點(diǎn)在數(shù)據(jù)記錄集N中出現(xiàn)的頻率或累積停留時(shí)間；

5）去除當(dāng)前數(shù)據(jù)記錄集N中位置點(diǎn)屬于Cm的所有記錄，返回步驟2)；循環(huán)結(jié)束生成位置點(diǎn)集合C={Cm}；

6）將原數(shù)據(jù)記錄集N中位置點(diǎn)屬于Cm的所有記錄替代為Cm的型心，然后將同一位置點(diǎn)的所有相鄰數(shù)據(jù)記錄合并為一條新記錄，新記錄的開(kāi)始時(shí)間設(shè)為這些數(shù)據(jù)記錄中開(kāi)始時(shí)間的最小值，結(jié)束時(shí)間設(shè)為這些數(shù)據(jù)記錄中結(jié)束時(shí)間的最大值。執(zhí)行完畢生成數(shù)據(jù)記錄集N′。

在上述算法中，依次從空間位置點(diǎn)最多的數(shù)據(jù)記錄開(kāi)始處理，這些位置點(diǎn)通常為手機(jī)用戶(hù)居住和就業(yè)所在地以及經(jīng)常訪(fǎng)問(wèn)地點(diǎn)，這樣不僅保證算法有很高的計(jì)算效率，也有助于錨固這些經(jīng)常訪(fǎng)問(wèn)的活動(dòng)點(diǎn)。步驟3)中時(shí)間間隔τ可取15 min。根據(jù)各城市的居民出行調(diào)查結(jié)果，一次出行的時(shí)耗通常在5 min以上，而在出行目的地活動(dòng)所花時(shí)間一般在5 min 以上。從一個(gè)地點(diǎn)出行再返回原地的過(guò)程涉及一個(gè)活動(dòng)和兩次出行，因此最小時(shí)間間隔應(yīng)為15 min以上。另外，由于手機(jī)信令數(shù)據(jù)通常會(huì)在某些時(shí)段密集發(fā)生，尤其是發(fā)生乒乓效應(yīng)和數(shù)據(jù)漂移時(shí)，那么通過(guò)上述步驟對(duì)夾雜數(shù)據(jù)進(jìn)行搜索同化后，手機(jī)數(shù)據(jù)的空間不確定性將在很大限度上被消除。

2.3 空間聚類(lèi)

空間聚類(lèi)是對(duì)當(dāng)前數(shù)據(jù)記錄集的空間位置點(diǎn)按聚類(lèi)算法進(jìn)行分類(lèi)，改進(jìn)的聚類(lèi)算法如下：

1）將上一階段結(jié)果N′設(shè)為當(dāng)前數(shù)據(jù)記錄集，計(jì)算各位置點(diǎn)l的總停留時(shí)間Tl=∑i∈Il(tif-tis)，Il為數(shù)據(jù)記錄集中位置點(diǎn)為l的序列號(hào)集合，按總停留時(shí)間由大到小對(duì)各位置點(diǎn)排序，形成位置點(diǎn)集合L={l1,l2,…,lk}；

2）在L中按順序取li進(jìn)入類(lèi)Ch，li為Ch型心，依次計(jì)算L中其他位置點(diǎn)lj至Ch型心的距離Dis(lj,Ch)，若 Dis(lj,Ch)＜δ，則將lj加入Ch，更新Ch型心的經(jīng)緯度為Ch中各位置點(diǎn)經(jīng)緯度的加權(quán)平均值，權(quán)重為各位置點(diǎn)的總停留時(shí)間；否則繼續(xù)進(jìn)行，直到L中任意一點(diǎn)至Ch型心的距離不小于δ，生成類(lèi)Ch；

3）從L中刪除Ch中所含位置點(diǎn)，若L不為空，返回步驟2)。否則輸出類(lèi){C1,C2,…,Cf}；

4）在N′數(shù)據(jù)記錄中，將各位置點(diǎn)替換為其所屬的類(lèi)型心；然后將同一位置點(diǎn)的所有相鄰數(shù)據(jù)記錄合并為一條新記錄，新記錄的開(kāi)始時(shí)間設(shè)為這些數(shù)據(jù)記錄中開(kāi)始時(shí)間的最小值，結(jié)束時(shí)間設(shè)為這些數(shù)據(jù)記錄中結(jié)束時(shí)間的最大值，最后得到結(jié)果數(shù)據(jù)記錄集N′。

上面的空間聚類(lèi)方法實(shí)質(zhì)上是一種漸進(jìn)聚類(lèi)算法[13]的改進(jìn)算法。漸進(jìn)聚類(lèi)算法會(huì)因位置點(diǎn)的不同排列次序而產(chǎn)生不同的聚類(lèi)結(jié)果，文獻(xiàn)[1]選擇K-means聚類(lèi)方法來(lái)克服這一缺點(diǎn)。但K-means聚類(lèi)方法的預(yù)設(shè)參數(shù)需要經(jīng)過(guò)試算才能確定，會(huì)極大地影響計(jì)算效率。本文提出的方法先對(duì)位置點(diǎn)按停留時(shí)間進(jìn)行排序，聚類(lèi)始終從長(zhǎng)時(shí)間活動(dòng)的位置點(diǎn)發(fā)起，保證了聚類(lèi)結(jié)果的唯一性和合理性。另外，類(lèi)型心更新的機(jī)制中引入了位置點(diǎn)停留時(shí)間的權(quán)重，更加錨固了長(zhǎng)時(shí)間停留點(diǎn)的位置。大多數(shù)的出行距離為500 m 以上，步驟2)中δ可取200～500 m。

表1 手機(jī)數(shù)據(jù)原始記錄Tab.1 Original raw cell phone data

續(xù)表

2.4 活動(dòng)點(diǎn)識(shí)別

活動(dòng)點(diǎn)識(shí)別指辨認(rèn)用戶(hù)活動(dòng)地點(diǎn)，一般將單次停留時(shí)間超過(guò)一定值(如5 min)的位置點(diǎn)作為活動(dòng)點(diǎn)。在時(shí)空貪婪同化和空間聚類(lèi)步驟之后，存在活動(dòng)的位置點(diǎn)能夠最大限度地累積到停留時(shí)間，便于活動(dòng)點(diǎn)的識(shí)別。

3 算例

表1 為隨機(jī)抽取的匿名用戶(hù)一天的手機(jī)數(shù)據(jù)，共121 條，表中序號(hào)按數(shù)據(jù)開(kāi)始時(shí)間排序，位置點(diǎn)共計(jì)16 個(gè)(見(jiàn)表2)，位置點(diǎn)編號(hào)按各位置點(diǎn)經(jīng)度由小到大排序?？梢钥闯?，出現(xiàn)次數(shù)最多的位置點(diǎn)編號(hào)為2，表1中藍(lán)色框表示相鄰兩條位置點(diǎn)為2 的數(shù)據(jù)記錄滿(mǎn)足開(kāi)始時(shí)間小于15 min的條件，紅色框表示相鄰兩條位置點(diǎn)為15 的數(shù)據(jù)記錄滿(mǎn)足開(kāi)始時(shí)間小于15 min的條件。

根據(jù)時(shí)空貪婪同化流程建立位置點(diǎn)集合C1={1 ,2,3,4,6}。同理，對(duì)應(yīng)于位置點(diǎn)15(見(jiàn) 表 1 中 紅 色框)，可 以 得 到C2={12,14,15,16}。表1 中合并標(biāo)識(shí)表示這些數(shù)據(jù)記錄的位置點(diǎn)屬于同一個(gè)位置點(diǎn)集合，將被集合型心所取代。時(shí)空貪婪同化流程的結(jié)果如表3 所示。為直觀(guān)對(duì)比，表3 中序號(hào)與表1 保持一致，合并的數(shù)據(jù)記錄保留了起始數(shù)據(jù)記錄序號(hào)。

為說(shuō)明算法的有效性和計(jì)算效率，同時(shí)采用K-means 聚類(lèi)方法對(duì)以上數(shù)據(jù)進(jìn)行處理，結(jié)果如圖4 所示。K-means 聚類(lèi)方法(δ取500 m)的結(jié)果生成3個(gè)類(lèi)，按文獻(xiàn)[1]提出的處理框架，類(lèi)C2與C3將在接下來(lái)的步驟中被檢測(cè)為乒乓效應(yīng)而進(jìn)行合并，從而得到與時(shí)空貪婪同化流程完全類(lèi)似的結(jié)果。但K-means 聚類(lèi)方法需要計(jì)算兩點(diǎn)之間的空間距離，本質(zhì)上是一種O(|N|2)算法( |N|為初始數(shù)據(jù)記錄條數(shù))，而時(shí)空貪婪同化流程為O(|N|)算法，計(jì)算量遠(yuǎn)遠(yuǎn)小于前者。

基于K-means 聚類(lèi)方法[1]得到的類(lèi)C1={1 ,2,3,4,5,6,7,8} 會(huì) 因δ取 值 而 變化，從用戶(hù)多日的數(shù)據(jù)分析來(lái)看，時(shí)空貪婪同化流程得到的C1={1 ,2,3,4,6} 能更客觀(guān)地反映用戶(hù)居住地的位置。位置點(diǎn)1，3，4，6夾雜在相鄰兩條位置點(diǎn)為2的記錄中的最小時(shí)間間隔分別為2 min 52 s，8 min 46 s，1 min 23 s 和1 min 45 s。也就是說(shuō)，只要時(shí)間間隔τ取10 min 以上時(shí)，C1即可包含位置點(diǎn)1，2，3，4，6。另一方面，位置點(diǎn)5，7 和8 夾雜在相鄰兩條位置點(diǎn)為2 的記錄中的最小時(shí)間間隔分別為27 min 9 s，27 min 9 s和1 min 20 s，當(dāng)τ取17～27 min時(shí)，位置點(diǎn)8將進(jìn)入C1；當(dāng)τ取28 min以上時(shí)，位置點(diǎn)5和7將進(jìn)入C1。由于C1型心計(jì)算會(huì)以各位置點(diǎn)停留時(shí)間為權(quán)重，位置點(diǎn)8，5和7進(jìn)入C1對(duì)于型心位置的影響很小。由此可以看出，只要τ在一定范圍內(nèi)，時(shí)空貪婪同化流程的結(jié)果相當(dāng)穩(wěn)定。

從表3 可以看出，經(jīng)過(guò)時(shí)空貪婪同化流程，121條原始數(shù)據(jù)記錄被精簡(jiǎn)至10條，計(jì)算量遠(yuǎn)遠(yuǎn)小于各種空間聚類(lèi)算法，且原始數(shù)據(jù)記錄中各種形式的乒乓效應(yīng)完全被消除，位置點(diǎn)C1和C2的停留時(shí)間得到最大限度的累積。不難推測(cè)，C1為居住地，而C2為工作地，位置點(diǎn)11 為上班途中留下的痕跡，而位置點(diǎn)13，10 和9 為下班途中留下的痕跡。位置點(diǎn)7 和5 可能表征一次基于家的活動(dòng)，但由于出行距離較短，在接下來(lái)的空間聚類(lèi)流程中可能會(huì)被抹去(取決于聚類(lèi)所采用的參數(shù))。

雖然從這個(gè)具體例子來(lái)看，在時(shí)空貪婪同化流程之后進(jìn)行空間聚類(lèi)并非十分必要，但由于數(shù)據(jù)記錄已大幅精簡(jiǎn)，改進(jìn)后的空間聚類(lèi)的計(jì)算量非常小。況且手機(jī)數(shù)據(jù)產(chǎn)生漂移和乒乓效應(yīng)的情形多種多樣，保留空間聚類(lèi)流程可以彌補(bǔ)時(shí)空貪婪同化流程可能力不能及的地方。從表3可以看出，位置點(diǎn)13在空間聚類(lèi)流程中進(jìn)入C2，這雖然無(wú)助于提升對(duì)于停留點(diǎn)位置的判斷，但是能夠提升對(duì)于離開(kāi)工作地時(shí)間判斷的精度。

表2 各位置點(diǎn)經(jīng)緯度及出現(xiàn)次數(shù)Tab.2 The latitude and longitude of different location point and its occurrences

表3 時(shí)空貪婪同化流程處理結(jié)果Tab.3 Results of space-time greedy assimilation process

圖4 算法結(jié)果比較Fig.4 Results of different algorithms

4 結(jié)語(yǔ)

與各種基于空間緊密性的聚類(lèi)算法不同，本文提出一種基于時(shí)間緊密性的新算法——時(shí)空貪婪同化流程，用于從手機(jī)數(shù)據(jù)推演出行鏈。在隨機(jī)抽取的個(gè)體手機(jī)數(shù)據(jù)測(cè)試中，新算法表現(xiàn)出很高的效率，對(duì)于居住地、工作地等停留較長(zhǎng)時(shí)間的活動(dòng)點(diǎn)的錨固作用尤其明顯。由于篇幅限制算例是針對(duì)一天的手機(jī)數(shù)據(jù)，顯然算法無(wú)須調(diào)整即可應(yīng)用于多天手機(jī)數(shù)據(jù)。未來(lái)的研究將集中在整個(gè)城市層面居民出行鏈的推演以及推演結(jié)果與交通調(diào)查數(shù)據(jù)的比對(duì)方面。