韓 卓 肖躍雷

（西安郵電大學(xué)物聯(lián)網(wǎng)與兩化融合研究院 西安 710061）

1 引言

隨著科技的不斷進(jìn)步，人類的歷史移動數(shù)據(jù)以GPS定位、簽到位置信息及交通卡等形式得以持久化保存，經(jīng)過數(shù)據(jù)的不斷存留，從而形成了時(shí)空軌跡數(shù)據(jù)。通過具有時(shí)間、采樣位置、運(yùn)動速度等屬性信息的采樣點(diǎn)組成時(shí)空軌跡［1］。時(shí)空軌跡信息通過不斷成熟的數(shù)據(jù)挖掘技術(shù)，如聚類、關(guān)聯(lián)規(guī)則挖掘、分類等［2］，處理得到一些有價(jià)值的信息并應(yīng)用于旅游、交通、能源等領(lǐng)域。

時(shí)空數(shù)據(jù)挖掘是數(shù)據(jù)挖掘領(lǐng)域中一個(gè)重要的研究范疇，通過一些系列的軌跡點(diǎn)，進(jìn)行時(shí)空數(shù)據(jù)挖掘，可以得到相關(guān)的職住空間分布、興趣區(qū)域分布及出行特性分布等有用信息。而職住分析對旅游景點(diǎn)推薦、城市交通設(shè)施建設(shè)、城市產(chǎn)業(yè)規(guī)劃布局等有著重要參考作用，對建設(shè)智慧城市有著深刻影響［3］。傳統(tǒng)的聚類只分析處理在地理空間上的數(shù)據(jù)，為更好挖掘時(shí)空信息的地理空間數(shù)據(jù)、滿足研究要求，故采用時(shí)空聚類［4］。目前時(shí)空聚類的方法主要有空間聚類和時(shí)空耦合聚類，空間聚類的方法忽視了時(shí)空觀測值在時(shí)間維度上的動態(tài)性因而其捕捉時(shí)空動態(tài)的能力不足，故時(shí)空耦合的方法更加適合研究［5］。鄧敏等［6］基于時(shí)空數(shù)據(jù)的基本特征構(gòu)建時(shí)空鄰域進(jìn)而采用了密度聚類的方法。童曉君等［7］通過凝聚式層次聚類算法，基于乘客出行的空間特征，識別出乘客出行的空間熱點(diǎn)區(qū)域及其時(shí)段特征。

近年來，居民出行特征、職住空間平衡及通勤行為研究等方面都有不錯的研究進(jìn)展。楊超等［8］提出了基于最小通勤理論的最優(yōu)增長分布模型，用于職住平衡程度與通勤交通效率的研究。鄭思齊等［9］提出了一種說明居住與就業(yè)實(shí)質(zhì)性匹配的“職住平衡指數(shù)”，分析了造成職住空間差異的影響因子和作用機(jī)制。從目前的研究看來，職住地分析定位方面仍研究不足，現(xiàn)有研究仍偏向傳統(tǒng)社會調(diào)查。這些方式不僅耗費(fèi)人力物力財(cái)力且實(shí)時(shí)性較差?？茖W(xué)性的分析定位居民職住地顯得尤為重要。許寧等［10］提出了一種基于短期規(guī)則采樣的大量手機(jī)定位數(shù)據(jù)的居民職住地識別方法，通過規(guī)整的手機(jī)定位數(shù)據(jù)及相應(yīng)的用地性質(zhì)識別出職住地。ZangH 等［11］依據(jù)手機(jī)用戶在自定義的職住時(shí)間段內(nèi)分別產(chǎn)生的業(yè)務(wù)頻繁程度來確定職住地。IsaacmanS 等［12］基于手機(jī)通話定位，通過空間聚類識別用戶的重要活動地點(diǎn)，進(jìn)而時(shí)間分析確定職住地。唐小勇等［13］提出一種職住計(jì)算框架，識別用戶在一天內(nèi)的多日穩(wěn)定點(diǎn)和綜合工作日與節(jié)假日穩(wěn)定點(diǎn)，基于此來判斷用戶的職住地。賴見輝等［14］通過利用信令數(shù)據(jù)中職住地的各種通信特征建立隸屬度函數(shù)，基于權(quán)重思想提出一種改進(jìn)的識別方法。

綜上所述，對于識別職住地的研究，有的識別方法不能很好適應(yīng)數(shù)據(jù)集大小，有的結(jié)果驗(yàn)證比較薄弱。為了在不同數(shù)據(jù)量的情況下，職住地的識別結(jié)果更為可靠，本文利用采集到的基站信令數(shù)據(jù)，對軌跡點(diǎn)進(jìn)行基于K-Means的時(shí)空聚類，聚類結(jié)果能夠?qū)β氉〉販?zhǔn)確定位，此外也能夠劃分區(qū)域內(nèi)常駐與非常駐人口，經(jīng)過大量真實(shí)數(shù)據(jù)驗(yàn)證對比本文的模型有更好識別效果，且更夠投入正常使用。

2 基于K-Means的時(shí)空聚類

對于軌跡點(diǎn)的聚類，通常有基于密度的聚類、基于網(wǎng)格聚類以及基于模型的聚類等方法［15］。由于基于劃分的聚類方法的實(shí)現(xiàn)復(fù)雜度較低，故而被主要應(yīng)用于大規(guī)模數(shù)據(jù)聚類。這里采用的是基于劃分方法的K-Means 聚類。它是一種基于距離的非層次聚類算法。在最小化誤差函數(shù)的基礎(chǔ)上，將數(shù)據(jù)分為K 個(gè)集合，以距離作為相似度的評價(jià)指標(biāo)，即認(rèn)為兩個(gè)對象的距離越近，其相似度越大［16］。算法過程描述如下：

1）隨機(jī)選取K 個(gè)點(diǎn)作為初步迭代的聚類質(zhì)心點(diǎn)a1，a2，…aK。

2）計(jì)算其余樣本點(diǎn)到K 個(gè)聚類點(diǎn)的距離，選擇距離質(zhì)心aj最近的類別j，更新質(zhì)心aj為該類全部樣本的平均值，并標(biāo)記。

3）屬于同一類的點(diǎn)進(jìn)行取質(zhì)心運(yùn)算，計(jì)算新的簇質(zhì)心點(diǎn)。

4）重復(fù)步驟2）、3）直到簇質(zhì)心點(diǎn)不再發(fā)生變化。

2.1 目標(biāo)函數(shù)

目標(biāo)函數(shù)又稱為失真代價(jià)函數(shù)。當(dāng)目標(biāo)函數(shù)達(dá)到最優(yōu)或者達(dá)到最大的迭代次數(shù)時(shí)算法結(jié)束。對于樣本集D={x1，x2，…，xm} ，K-Means 針對聚類劃分為C={C1，C2，…，CK}，最小化平方誤差：

其中，ui是簇Ci的均值向量（質(zhì)心），表達(dá)式為。

從上述公式中可以看出，簇內(nèi)樣本圍繞簇均值向量的緊密程度，最小化平方誤差E 值越小簇內(nèi)樣本的相似度越高［17］。

2.2 距離量度

不同的距離量度下的聚類結(jié)果不盡相同。像歐幾里得距離度量會受不同單位刻度的影響，因此一般需要先進(jìn)行標(biāo)準(zhǔn)化。余弦相似度傾向給出更優(yōu)解。常用的距離度量表達(dá)式如下所示：

用戶的信令數(shù)據(jù)包含信令產(chǎn)生時(shí)間及產(chǎn)生信令所處地理經(jīng)緯度坐標(biāo)。通過用戶的經(jīng)緯度數(shù)據(jù)可得到用戶活動范圍及常駐點(diǎn)信息。由于是地理位置聚類，坐標(biāo)采用的是國際地心坐標(biāo)系WGS-84，因此此次研究選取的距離度量是經(jīng)緯度計(jì)算的球面距離。球面距離公式：

其中，A，B是球面的坐標(biāo)；點(diǎn)A：經(jīng)度α1、緯度β1；點(diǎn)B：經(jīng)度α2、緯度β2；R是地球半徑（約6371km）。

2.3 K值的確定

K-Means 通常需要迭代十幾次甚至上百次。每次迭代時(shí)，隨機(jī)地從不同位置開始初始化，最終初始化位置就是最小的代價(jià)函數(shù)對應(yīng)的重心位置。據(jù)目前研究，K值的選擇有以下方法：

1）K個(gè)初始點(diǎn)是隨機(jī)地在訓(xùn)練數(shù)據(jù)中抽取選定。

2）當(dāng)K值確定，迭代n次，最終的聚類結(jié)果是最小代價(jià)函數(shù)值的K，從而避免隨機(jī)造成的局部最優(yōu)。

3）手肘法則選取K 值：繪制出K-代價(jià)函數(shù)閃點(diǎn)圖，有明顯拐點(diǎn)所對應(yīng)的數(shù)值，設(shè)為K 值，并把對應(yīng)不同值的代價(jià)函數(shù)值畫出來。平均畸變程度隨著代價(jià)函數(shù)的增大而減??；每類包含的樣本數(shù)慢慢減少，樣本離會更接近其簇質(zhì)心。平均畸變程度的聚類效果因代價(jià)函數(shù)值增大而減弱。在值增加過程中，畸變程度下降幅度最大時(shí)所對應(yīng)的值即為肘部位置。

4）K 值有時(shí)需要針對不同的應(yīng)用場景選取，而不能完全地依靠評估參數(shù)來決定［18］。

此次研究采用第二種方法，即手肘法則來確定K 值。由于每個(gè)用戶的信令數(shù)據(jù)不一，或多或少，因此每個(gè)用戶K 的取值是不同的。正常情況下用戶一個(gè)月的信令數(shù)在400 條左右，在信令數(shù)較少的情況下大概在幾十條左右。數(shù)據(jù)較少不足以分成太多簇，對聚類中心點(diǎn)也會有所影響。手肘法則能夠準(zhǔn)確選取K 值且不受信令總數(shù)極值（極大或者極?。┑挠绊?。在信令總數(shù)處于幾條或幾萬條這種極值情況下仍能選取合適的K 值，達(dá)到更好的聚類效果。

2.4 時(shí)間特性標(biāo)簽

據(jù)調(diào)查，近年來居民出行的早晚高峰集中在7至8 點(diǎn)及17 至18 點(diǎn)，依據(jù)居民白天工作、晚上休息的一般作息時(shí)間規(guī)律，結(jié)合信令數(shù)據(jù)，時(shí)間閾值可以選定為白天時(shí)段（9：00～18：00）和夜間時(shí)段（20：00～8：00），其余時(shí)間定為閑時(shí)時(shí)段。鑒于用戶在上班路上或下班途中也有可能產(chǎn)生通話短信業(yè)務(wù)，且有交通、通勤的因素影響，上下班的路途時(shí)間可能有延長，故除白天和夜間時(shí)段外需劃分出另一時(shí)間段。為白天、夜間和閑時(shí)時(shí)段分別給出0、1、2的時(shí)間特性標(biāo)簽。每個(gè)軌跡點(diǎn)都有對應(yīng)的進(jìn)入時(shí)間，根據(jù)該點(diǎn)進(jìn)入時(shí)間所在的時(shí)間段來判定該點(diǎn)類屬的時(shí)間標(biāo)簽。白天時(shí)段的常駐點(diǎn)可能為工作地，夜間的常駐點(diǎn)可能為居住地，閑時(shí)時(shí)段的常駐點(diǎn)可能為非事務(wù)性常駐地。本文僅研究正常上班制，不考慮夜班等特殊情況。

2.5 基于時(shí)空聚類

用戶信令中的每個(gè)軌跡點(diǎn)，表示著曾在該點(diǎn)逗留，在一段時(shí)間內(nèi)軌跡點(diǎn)的頻次大小預(yù)示著該點(diǎn)是否是用戶的常駐點(diǎn)。頻次高，說明用戶在此軌跡點(diǎn)曾多次出現(xiàn)，可視為用戶的常駐點(diǎn)之一。頻次低，說明用戶可能在此軌跡點(diǎn)偶然經(jīng)過。由于K-Means 算法在迭代過程中使用所有樣本點(diǎn)的均值作為新的質(zhì)心，如果簇內(nèi)存在異常點(diǎn)，將會導(dǎo)致質(zhì)心點(diǎn)偏離。用戶偶然經(jīng)過或是非頻繁性去往某地所留下的軌跡點(diǎn)又稱離群點(diǎn)，這些點(diǎn)會影響到質(zhì)心點(diǎn)的最終位置，故在聚類中加入頻次維度，保證聚類過程中盡量避免離群點(diǎn)的影響，使得聚類結(jié)果更加逼近實(shí)際常駐點(diǎn)。加入頻次維度后，在信令數(shù)據(jù)預(yù)處理中不需刪減剔除離群點(diǎn)。時(shí)間段是用戶在軌跡點(diǎn)出現(xiàn)時(shí)的時(shí)間，白天、夜間或者閑時(shí)。頻次和時(shí)間段有利于對常駐點(diǎn)性質(zhì)的判斷，具體分清職駐地。

對于居住地的判定：通過連續(xù)多天的信令數(shù)據(jù)，根據(jù)手機(jī)用戶在居住時(shí)段逗留的軌跡點(diǎn)及在此軌跡點(diǎn)出現(xiàn)的次數(shù)，多天累計(jì)逗留頻次最高的一點(diǎn)。利用用戶每天的手機(jī)出行軌跡，分析每位用戶單天的出行目的地。當(dāng)每位手機(jī)用戶離開居住地后，出現(xiàn)頻次最高的且在時(shí)間段具有周期性即作為其工作目的地，視為出行地的判定。

基于時(shí)空軌跡數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘，主要是以時(shí)間、空間、業(yè)務(wù)特征等屬性作為聚類緯度，在對所有的屬性維度聚類后，定期實(shí)現(xiàn)基于新增的軌跡數(shù)據(jù)實(shí)現(xiàn)二次聚類，進(jìn)而更新為新的類［19］。將用戶的經(jīng)度、緯度、頻次、時(shí)間段四維數(shù)據(jù)進(jìn)行基于時(shí)空的K-Means 聚類。聚類后的K 個(gè)聚類中心并不是作為用戶的常駐點(diǎn)直接輸出的，還需進(jìn)一步分析判定。常駐判定1：由于聚類是傳統(tǒng)意義上距離的聚類，時(shí)間標(biāo)簽是用數(shù)字來表示其含義的，對于時(shí)間標(biāo)簽聚類后肯定是有所偏差的，所以聚類后的時(shí)間標(biāo)簽值要根據(jù)其落入?yún)^(qū)間來識別哪一時(shí)間段。普遍地，信令數(shù)據(jù)中夜晚時(shí)段的信令要遠(yuǎn)遠(yuǎn)多于白天時(shí)段，由于聚類的影響，聚類結(jié)果的時(shí)間標(biāo)簽會有偏差，對在時(shí)間標(biāo)簽0的影響會偏大，故時(shí)間標(biāo)簽0的區(qū)間設(shè)定會比較大，時(shí)間標(biāo)簽1 設(shè)定的區(qū)間會相對比較小。常駐判定2：聚類結(jié)果中，當(dāng)幾個(gè)常駐點(diǎn)具有相同的時(shí)間屬性時(shí)，按其頻次大小賦予“常駐點(diǎn)1、常駐點(diǎn)2”的標(biāo)簽。一個(gè)人可能有一個(gè)或兩個(gè)或以上的工作地，例如常駐工作地、非常駐工作地、出差地等。隨著生活水平的提高，居民可能擁有幾處房產(chǎn)，另外由于親緣關(guān)系等內(nèi)部原因，因此居住地可能不止一處。模型設(shè)計(jì)如圖1。

圖1 K值平均畸變程度

3 實(shí)驗(yàn)分析與討論

3.1 數(shù)據(jù)來源

研究的數(shù)據(jù)集來源于某運(yùn)營商2017 年2 月13日到2017 年3 月15 日的近一個(gè)月的基站信令數(shù)據(jù)。該數(shù)據(jù)集包含了669 萬個(gè)用戶約8 億條信令。樣例數(shù)據(jù)如圖2 所示。基站信令數(shù)據(jù)各字段的具體含義見表1。

圖2 樣例數(shù)據(jù)

表1 信令數(shù)據(jù)各字段及其含義

3.2 數(shù)據(jù)處理

3.2.1 數(shù)據(jù)存儲

在該數(shù)據(jù)集中抽取2017年2月13日到2017年3月15日的相關(guān)信令數(shù)據(jù)，且各用戶間信令總數(shù)不均等。由Spark 平臺執(zhí)行提取操作后按用戶存儲，刪除替換除字段外含有其他多余字符后保存為本地的.txt形式的文件［20］。

3.2.2 數(shù)據(jù)預(yù)處理

原始文件以.txt形式存儲，對數(shù)據(jù)進(jìn)行預(yù)處理：原始數(shù)據(jù)中的業(yè)務(wù)發(fā)生時(shí)間（Time Stamp）的轉(zhuǎn)換，將字符串編碼形式替換為北京時(shí)間；將每位用戶數(shù)據(jù)按照產(chǎn)生信令的時(shí)間先后進(jìn)行排序；對于字段經(jīng)度和緯度，有個(gè)別經(jīng)緯度調(diào)換的現(xiàn)象，將其對調(diào)修正。

3.3 參數(shù)驗(yàn)證

取500 用戶信令數(shù)據(jù)作為參數(shù)驗(yàn)證集。選取某位用戶作為展示：通過手肘法則判定K=4，如圖3所示。K 值從1 至4 變化過程中，遞減程度最為劇烈，平均畸變程度下降程度最為明顯。K 值超過4之后，遞減緩慢，平均畸變程度變化顯著降低，因此肘部K=4。

圖3 K值平均畸變程度

K 值選取3 和4，距離分別采用歐氏距離和球面距離。于是得到四種組合：K=3&歐氏距離、K=3&球面距離、K=4&歐氏距離、K=4&球面距離。經(jīng)過不同參數(shù)設(shè)置得到聚類后每一類的質(zhì)心點(diǎn)，將質(zhì)心點(diǎn)作為常駐點(diǎn)輸出。根據(jù)聚類后的分類結(jié)果，取每一類中頻次最高的信令位置作為聚類（頻次）常駐點(diǎn)進(jìn)行比較。不同參數(shù)下的常駐點(diǎn)統(tǒng)計(jì)結(jié)果如圖4所示。

圖4 不同參數(shù)下的常駐點(diǎn)距離對比（某用戶）

在地圖上實(shí)測不同參數(shù)下的常駐點(diǎn)到最終常駐點(diǎn)的距離。其中，信令位置的經(jīng)緯度是國際上通用的地心坐標(biāo)系WGS-84 坐標(biāo)系，而高德地圖等目前普通地圖采用的是加密處理后的火星或者百度坐標(biāo)系，所以對應(yīng)到實(shí)際地圖測量實(shí)際距離需要坐標(biāo)系轉(zhuǎn)換。據(jù)不同參數(shù)下的常駐點(diǎn)統(tǒng)計(jì)結(jié)果得到其常駐點(diǎn)距離對比圖。

在常駐點(diǎn)2和常駐點(diǎn)3，K=3比K=4條件下的聚類中心點(diǎn)的效果更佳；但在常駐點(diǎn)1，K=3條件下聚類中心點(diǎn)效果太差，相距太遠(yuǎn)。這是因?yàn)橛捎谟脩糗壽E點(diǎn)分布不均，聚類的簇較少，有些簇跨度較大，噪聲點(diǎn)無法排除，導(dǎo)致選取的質(zhì)心點(diǎn)與常駐點(diǎn)會有明顯出入。論整體效果而言，在K=4條件下聚類中心點(diǎn)的效果好些，與前面提到的肘部法則的結(jié)果一致。明顯地，不論K 值大小，距離度量選取球面距離比歐氏距離的效果更佳。因此，距離度量選取球面距離是可行的。經(jīng)對比驗(yàn)證，K 值的選取根據(jù)手肘法則聚類效果更佳，而距離度量選取球面度量比聚類默認(rèn)的距離度量更加精確。

3.4 模型檢驗(yàn)

隨機(jī)選取5 個(gè)已知測試用戶進(jìn)行模型檢測。其中，用戶1～5的聚類結(jié)果圖如圖5～9所示。

圖5 用戶1-基于時(shí)空聚類結(jié)果

圖6 用戶2-基于時(shí)空聚類結(jié)果

圖8 用戶4-基于時(shí)空聚類結(jié)果

圖9 用戶5-基于時(shí)空聚類結(jié)果

將5 個(gè)隨機(jī)用戶通過基于K-Means 時(shí)空聚類模型輸出待有時(shí)間性質(zhì)的常駐點(diǎn)，經(jīng)與實(shí)際地理位置計(jì)算得到距離誤差（單位：m）。距離誤差如圖10。

圖10 用戶1-5常駐地誤差對比圖

由圖10所知，在5個(gè)用戶的常駐地中的最大距離誤差是1200m。用戶1 和用戶2 準(zhǔn)確度較高，幾乎能精準(zhǔn)定位，在于這兩個(gè)用戶信令少避免了一些無用數(shù)據(jù)的影響。由于每個(gè)用戶數(shù)據(jù)不一，特征不同，因此每個(gè)用戶輸出的常駐點(diǎn)數(shù)量不一且性質(zhì)也不同。市區(qū)的基站覆蓋范圍半徑在大約為100m～500m，郊區(qū)的大約為400m～1000m。與真實(shí)位置相比，只要距離誤差小于該范圍，就可默認(rèn)職住地能夠被準(zhǔn)確識別到。移動基站定位在城區(qū)可能存在約800m的誤差，由于受基站負(fù)荷、信號被建筑物遮擋等因素的影響，用戶連接的基站可能不一定是距離其最近的基站，而且在乒乓效應(yīng)的影響下，可能在兩個(gè)相距比較近的基站間來回跳動，故在1000m的距離誤差允許值內(nèi)即可［21］。這5 個(gè)測試用戶都能達(dá)到職住地的準(zhǔn)確定位，因此該模型結(jié)果能達(dá)到可觀要求，可投放使用。

4 結(jié)語

本文對具有時(shí)空信息軌跡點(diǎn)的各屬性維度進(jìn)行基于K-Means的時(shí)空聚類，經(jīng)過一系列判定方法得到不同性質(zhì)的常駐地。經(jīng)實(shí)驗(yàn)驗(yàn)證，通過基于時(shí)空信息的K-Means聚類模型，能夠識別出居民的職住地，且不受乒乓效應(yīng)和離群點(diǎn)的影響，該模型的距離誤差在客觀范圍內(nèi)，且運(yùn)行結(jié)果接近真實(shí)職住地。