基于時空聚類的職住分析研究*

韓 卓 肖躍雷

（西安郵電大學物聯網與兩化融合研究院 西安 710061）

1 引言

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

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

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

綜上所述，對于識別職住地的研究，有的識別方法不能很好適應數據集大小，有的結果驗證比較薄弱。為了在不同數據量的情況下，職住地的識別結果更為可靠，本文利用采集到的基站信令數據，對軌跡點進行基于K-Means的時空聚類，聚類結果能夠對職住地準確定位，此外也能夠劃分區域內常駐與非常駐人口，經過大量真實數據驗證對比本文的模型有更好識別效果，且更夠投入正常使用。

2 基于K-Means的時空聚類

對于軌跡點的聚類，通常有基于密度的聚類、基于網格聚類以及基于模型的聚類等方法［15］。由于基于劃分的聚類方法的實現復雜度較低，故而被主要應用于大規模數據聚類。這里采用的是基于劃分方法的K-Means 聚類。它是一種基于距離的非層次聚類算法。在最小化誤差函數的基礎上，將數據分為K 個集合，以距離作為相似度的評價指標，即認為兩個對象的距離越近，其相似度越大［16］。算法過程描述如下：

1）隨機選取K 個點作為初步迭代的聚類質心點a1，a2，…aK。

2）計算其余樣本點到K 個聚類點的距離，選擇距離質心aj最近的類別j，更新質心aj為該類全部樣本的平均值，并標記。

3）屬于同一類的點進行取質心運算，計算新的簇質心點。

4）重復步驟2）、3）直到簇質心點不再發生變化。

2.1 目標函數

目標函數又稱為失真代價函數。當目標函數達到最優或者達到最大的迭代次數時算法結束。對于樣本集D={x1，x2，…，xm} ，K-Means 針對聚類劃分為C={C1，C2，…，CK}，最小化平方誤差：

其中，ui是簇Ci的均值向量（質心），表達式為。

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

2.2 距離量度

不同的距離量度下的聚類結果不盡相同。像歐幾里得距離度量會受不同單位刻度的影響，因此一般需要先進行標準化。余弦相似度傾向給出更優解。常用的距離度量表達式如下所示：

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

其中，A，B是球面的坐標；點A：經度α1、緯度β1；點B：經度α2、緯度β2；R是地球半徑（約6371km）。

2.3 K值的確定

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

1）K個初始點是隨機地在訓練數據中抽取選定。

2）當K值確定，迭代n次，最終的聚類結果是最小代價函數值的K，從而避免隨機造成的局部最優。

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

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

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

2.4 時間特性標簽

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

2.5 基于時空聚類

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

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

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

圖1 K值平均畸變程度

3 實驗分析與討論

3.1 數據來源

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

圖2 樣例數據

表1 信令數據各字段及其含義

3.2 數據處理

3.2.1 數據存儲

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

3.2.2 數據預處理

原始文件以.txt形式存儲，對數據進行預處理：原始數據中的業務發生時間（Time Stamp）的轉換，將字符串編碼形式替換為北京時間；將每位用戶數據按照產生信令的時間先后進行排序；對于字段經度和緯度，有個別經緯度調換的現象，將其對調修正。

3.3 參數驗證

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

圖3 K值平均畸變程度

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

圖4 不同參數下的常駐點距離對比（某用戶）

在地圖上實測不同參數下的常駐點到最終常駐點的距離。其中，信令位置的經緯度是國際上通用的地心坐標系WGS-84 坐標系，而高德地圖等目前普通地圖采用的是加密處理后的火星或者百度坐標系，所以對應到實際地圖測量實際距離需要坐標系轉換。據不同參數下的常駐點統計結果得到其常駐點距離對比圖。

在常駐點2和常駐點3，K=3比K=4條件下的聚類中心點的效果更佳；但在常駐點1，K=3條件下聚類中心點效果太差，相距太遠。這是因為由于用戶軌跡點分布不均，聚類的簇較少，有些簇跨度較大，噪聲點無法排除，導致選取的質心點與常駐點會有明顯出入。論整體效果而言，在K=4條件下聚類中心點的效果好些，與前面提到的肘部法則的結果一致。明顯地，不論K 值大小，距離度量選取球面距離比歐氏距離的效果更佳。因此，距離度量選取球面距離是可行的。經對比驗證，K 值的選取根據手肘法則聚類效果更佳，而距離度量選取球面度量比聚類默認的距離度量更加精確。

3.4 模型檢驗

隨機選取5 個已知測試用戶進行模型檢測。其中，用戶1～5的聚類結果圖如圖5～9所示。

圖5 用戶1-基于時空聚類結果

圖6 用戶2-基于時空聚類結果

圖8 用戶4-基于時空聚類結果

圖9 用戶5-基于時空聚類結果

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

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

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

4 結語

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