基于時空約束密度聚類的職住地識別方法

收稿日期：2021-11-18；修回日期：2022-01-08

基金項目：國家自然科學基金資助項目（61741216）；國家重點研發計劃資助項目（2018YFC08242-04）；陜西省科技統籌創新工程計劃資助項目（2016KTTSGY01-03）

作者簡介：苗登逢（1995-），男，山西晉中人，碩士研究生，主要研究方向為數據分析與挖掘；肖躍雷（1979-），男（通信作者），江西吉安人，副教授，博士，主要研究方向為信息安全與大數據（xiao_yuelei@163.com）.

摘 要：為了從移動終端位置數據中精準識別居民職住地，提出了一種基于時空約束密度聚類的職住地識別方法。首先，利用基于K-means的DBSCAN（density-based spatial clustering of applications with noise）時空駐點聚類過程將居民多天的原始軌跡點分成不同的時空駐點簇;然后，利用基于速度閾值的停留點簇和移動點簇識別過程將居民的每一個時空駐點簇區分為停留點簇或移動點簇;接著，利用基于K近距離的DBSCAN重要停留點聚類過程將居民的停留點分成不同的重要停留點簇;最后，利用基于KD-tree優化的KNN（K-nearest neighbor）職住地識別過程將居民的每個重要停留點識別為工作地、居住地、職住同一區域或興趣地點區域。實驗結果表明，該方法的每個過程都是合理有效的，并且最終的職住地識別效果要優于時間閾值法、累加時間法和信息熵法。

關鍵詞：密度聚類； 職住地識別； K-均值； 基于密度的噪聲空間聚類算法； KD-tree； K-近鄰

中圖分類號：TP181"" 文獻標志碼：A

文章編號：1001-3695（2022）06-030-1779-06

doi：10.19734/j.issn.1001-3695.2021.11.0628

Home-work location identification method based on spatiotemporal constrained density clustering

Miao Dengfeng1a， Xiao Yuelei1b，2

（1.a.School of Computer， b.School of Modern Posts， Xi’an University of Posts amp; Telecommunications， Xi’an 710121， China; 2.Shaanxi Provincial Information Engineering Research Institute， Xi’an 710075， China）

Abstract：To accurately identify residential home-work locations from mobile terminal location data， this paper proposed a home-work location identification method based on spatiotemporal constrained density clustering. Firstly， the method used a K-means based DBSCAN spatiotemporal stationary point clustering process to divide the original trajectory points of many days for each resident into different spatiotemporal stagnation point clusters. Then， it used a recognition process of residence point cluster and moving point cluster based on velocity threshold to recognize every spatiotemporal stationary point cluster of each resident as a stationary point cluster or a moving point cluster. After that， it used a DBSCAN important residence point clustering process based on K-nearest distance to divide the residence points of each resident into different important residence point clusters. Finally， it used a KNN home-work location identification process optimized by KD-tree to identify every important residence point of each resident as a home location， a work location， a home-work location or an interest location. The experimental results show that each process of this method is reasonable and effective， and the final recognition effect of home-work locations is better than the time threshold method， the cumulative time method and the information entropy method.

Key words：density clustering; home-work location identification; K-means; DBSCAN; KD-tree; K-nearest neighbor（KNN）

0 引言

職住地是城市居民最基本和最重要的兩個日常活動場所，且居民在職住地的活動規律呈現高度的規律性，反映了居民在工作地和居住地之間的時空關系。精準識別居民職住地以及挖掘居民處于職住地的時空規律為城市職住規劃、公共資源分配和交通管理決策提供數據支持。由于移動終端位置數據具有覆蓋范圍廣、數據實時性高、采樣周期長等特點，所以基于移動終端位置數據的居民活動模式分析具有良好的研究前景，能夠從大規模時空軌跡信息中挖掘居民的出行移動速度、出行時長、常駐地點、重要停留點和出行方式等重要時空屬性特征。

在DBSCAN時空駐點聚類算法的參數設定方面， Li等人［1］提出先使用基于蝙蝠算法優化的改進DBSCAN算法生成初始聚類，然后再使用改進的DBSCAN內部無標簽聚類驗證指標作為適應度函數來控制蝙蝠算法優化確定閾值參數。王慧東等人［2］提出通過繪制時空對象距離頻數柱狀圖來設定聚類算法中時空閾值。王兆豐等人［3］提出了一種動態參數選擇方法，首先基于K-均值算法對數據集進行初步聚類，聚類中采用最大最小距離方法確定初始聚類中心，然后通過聚類結果統計聚類中樣本間距離的分布得到具有最大樣本對數的距離值作為對應類的Eps值并獲得MinPts值。

在職住地識別方面，Isaacman等人［4］基于定位數據，首先通過空間聚類識別居民的重要活動地點，最后分析時間規律確定職住地。Long等人［5］結合公交刷卡記錄和土地性質圖，將決策樹和關聯規則相互結合識別通勤人群，在通勤距離可視化的基礎上分析職住地的時空特征。簡志春等人［6］結合土地利用類型數據和容積率數據，提出了一種基于邏輯回歸模型的社交網絡定位數據識別居民職住地的方法。彭飛等人［7］從追蹤出行鏈的角度出發，通過選取潛在職住地設置高頻職住地集合，提出公共交通常乘客職住地識別方法。張天然［8］利用每日20：00至次日8：00和工作日9：00～18：00的手機數據訓練識別，將出現概率最高且超過60%的區域作為用戶的職住地。許寧等人［9］根據深圳市企事業單位工作時段和深圳市居民生活習慣，設定工作時段為9：00～18：00，夜間睡眠時段為00：00～06：00，篩選用戶在工作（居住）時段累計停留時間超過閾值的基站作為該用戶的工作（居住）地所對應的基站。

以上研究仍然存在以下問題：a）上述DBSCAN時空駐點聚類算法中兩個參數的設定都是通過相關經驗和規律選取一個初始值，然后再多次調整，而且沒有考慮軌跡數據的速度特征；b）城市居民在居住地、工作地、商場、公園等重要地點的停留具有高度的規律性和停留時間分布特征，但同時也存在個體差異性，上述職住地識別方法沒有充分考慮這一點。為了解決這些問題，本文提出一種基于時空約束密度聚類的職住地識別方法，并以某運營商的移動終端位置數據進行了實驗驗證和對比分析。

1 基于時空約束密度聚類的職住地識別方法

基于時空約束密度聚類的職住地識別方法框架如圖1所示。

在圖1中，基于時空約束密度聚類的職住地識別方法的具體步驟如下：

a）利用基于K-means的DBSCAN時空駐點聚類過程將用戶A（A=1，2，…，m）多天的原始軌跡點集合分成不同的時空駐點簇，其中時空駐點簇的中心點為時空駐點。

b）利用基于速度閾值的停留點簇和移動點簇識別過程將用戶A的每一個時空駐點簇區分為停留點簇或移動點簇，其中停留點簇的中心點為停留點，移動點簇的中心點為移動點。

c）利用基于K近距離的DBSCAN重要停留點聚類過程將用戶A的停留點集合分成不同的重要停留點簇，其中重要停留點簇的中心點為重要停留點。

d）利用基于KD-tree優化的KNN（K-nearest neighbor）職住地識別過程將所有用戶的每個重要停留點識別為工作地、居住地、職住同一區域或興趣地點區域。

該職住地識別方法首先利用前三個步驟對每個用戶的原始軌跡數據集合進行逐步劃分和識別，生成相應高質量的重要停留點簇集合，然后在步驟d）中基于停留時間分布特征對所有用戶的每個重要停留點進行職住地識別，充分考慮了用戶軌跡數據的速度特征，以及每個用戶在重要停留點的高度規律性和個體差異性， 從而提高了職住地識別的準確率。

1.1 基于K-means的DBSCAN時空駐點聚類

DBSCAN聚類算法是基于密度的聚類算法，主要根據數據分布的緊密程度進行聚類。DBSCAN聚類算法的兩個參數鄰域樣本閾值MinPts和距離閾值Eps的取值是決定聚類效果的關鍵所在，同時通過這兩個參數來刻畫數據的緊密程度。

傳統DBSCAN時空駐點聚類算法中兩個參數的設定與取值方法都是通過相關經驗和規律選取一個初始值，再通過多次實驗對聚類效果進行評估對比，再次調整參數。但是，由于MinPts和Eps這兩個參數具有全局性，再者本文的軌跡數據為移動終端位置數據，存在數據稀疏性和空間不確定性等特點，所以通過相關經驗和規律很難達到預期聚類效果。此外，傳統DBSCAN時空駐點聚類算法主要考慮時間距離和空間距離兩個特征維度，沒有考慮軌跡數據的運動特征（即移動速度），使得生成的時空駐點簇中軌跡點之間在時間距離和空間距離上是緊密的，但在速度距離上可能是分散的（當軌跡點之間時間距離遠小于空間距離時，速度距離趨于無窮大）。

為了解決這些問題，本文提出了基于K-means的DBSCAN時空駐點聚類，如圖2所示。

其具體步驟如下：

a）輸入用戶A（A=1，2，…，m）多天的軌跡數據集合D_A={Di|i=1，2，…，n}。其中：m為移動終端用戶數;Di為第i條軌跡數據;n為用戶A的軌跡數據總條數。

b）依次計算Di與Di+1的時間距離ti和空間距離disi［10］，得到時間距離集合{t1，t2，…，tn－1}和空間距離集合{dis1，dis2，…，disn－1}，其計算公式分別為

ti=TDi+1－TDi（1）

disi=arccos（sin LatDi）×sin（LatDi+1）+cos（LatDi）×

cos（LatDi+1）×cos（LonDi-LonDi+1）×R×π/180）（2）

其中：TDi為第i條軌跡數據的時間戳;LonDi和LatDi為第i條軌跡數據的經度和緯度（均為角度單位）;R為地球半徑。

c）使用自適應K-means聚類算法對時間距離集合{t1，t2，…，tn－1}和空間距離集合{dis1，dis2，…，disn－1}分別聚類，輸出時間距離閾值集合{T1，T2，…，Tq}和空間距離閾值集合{Dis1，Dis2，…，Disr}，其中，時間距離閾值和空間距離閾值是每個簇中的平均值。本文自適應K-means聚類算法是通過計算輪廓系數來描述聚類質量進而確定最優K值。

d）對時間距離閾值集合{T1，T2，…，Tq}和空間距離閾值集合{Dis1，Dis2，…，Disr}進行組合形成q×r時空距離閾值二維矩陣，使用二維矩陣中每一個元素的空間距離閾值與時間距離閾值相除得到其對應的速度距離閾值{Vj×k|1≤j≤q，1≤k≤r}，將時間距離閾值和速度距離閾值組合得到對應的距離閾值組合參數Epsj×k={Tj，Vj×k|1≤j≤q，1≤k≤r}，然后使用Epsj×k計算其對應的MinPtsj×k值，最后輸出不同參數值集合{Epsj×k，MinPtsj×k|1≤j≤q，1≤k≤r}。其中MinPtsj×k的計算公式［11］為

MinPtsj×k=1n∑ni=1pi（3）

其中：pi為第i條軌跡數據Epsj×k鄰域內包含的軌跡點的數量。

e）將{Epsj×k，MinPtsj×k|1≤j≤q，1≤k≤r}中的每一對參數值作為DBSCAN聚類算法的兩個參數，然后對用戶A的軌跡數據進行聚類，得出每一對參數值所對應的聚類結果，并利用輪廓系數作為衡量聚類效果的判斷指標，以輪廓系數最大時所對應的那一對參數值作為最優的MinPts和Eps。

f）輸出最優MinPts和Eps所對應的DBSCAN聚類結果（即最終的時空駐點簇集合）。

在執行上述基于K-means的DBSCAN時空駐點聚類過程后，用戶A的原始軌跡點集合被分成不同的時空駐點簇。時空駐點簇的中心點稱為時空駐點。在本文中，時空駐點簇的中心點為時空駐點簇中與某一基站連接時長最長的軌跡點。

根據以上所述可知，本文DBSCAN時空駐點聚類算法的MinPts和Eps是基于時間距離閾值、空間距離閾值和速度距離閾值計算的，使得生成的時空駐點簇中軌跡點之間在時間距離、空間距離和速度距離上都是緊密的，不包含在速度距離上分散的軌跡點。此外，本文基于數據分布特征計算得到MinPts和Eps集合，然后從中選取每一對MinPts和Eps參數用于DBSCAN時空駐點聚類，最后輸出最優MinPts和Eps所對應的DBSCAN聚類結果，即聚類效果最佳的時空駐點簇集合。因此，上述基于K-means的DBSCAN時空駐點聚類可以提高后續識別過程的準確率。

1.2 基于速度閾值的停留點簇和移動點簇識別

由于用戶在不同的時空駐點簇有著不同的時間停留、移動距離和移動速度，所以時空駐點簇可能是停留點簇，也可能是移動點簇。用戶在時空駐點簇中低速運動與高速運動所產生的軌跡點密度不同并且區別大，低速運動產生的軌跡點密度大，高速運動產生的軌跡點密度小。這為區分停留點簇和移動點簇提供了清晰的辨識特征。本文提出了基于速度閾值的停留點簇和移動點簇識別，如圖3所示。

其具體步驟如下：

a）輸入上述基于K-means的DBSCAN時空駐點聚類過程中生成的用戶A（A=1，2，…，m）的時空駐點簇集合C_A={Ci|i=1，2，…，n1}，其中m為移動終端用戶數，Ci為用戶A的第i個時空駐點簇，n1為用戶A的時空駐點簇個數，每個時空駐點簇包含多個軌跡點。

b）判斷Ci中是否含有速度為0的軌跡點，若有則執行步驟e），否則執行步驟d）。

c）設定V1為用戶正常跑步的速度閾值，計算Ci中兩兩相鄰軌跡點速度的和的平均值Vavg，若Vavg≥V1，則將Ci標記為移動點簇，否則執行步驟e）。

d）設定V2和V3分別為小范圍內慢速移動和正常行走的速度閾值，計算Ci中兩兩相鄰軌跡點速度小于V2的百分比P2，以及用戶A所有時空駐點簇中兩兩相鄰軌跡點速度小于V2的百分比的平均值P2，avg，若P2≥P2，avg且Vavglt;V3，則將Ci標記為停留點簇，否則將Ci標記為移動點簇。

e）設定V4為正常騎自行車的速度閾值，計算Ci中兩兩相鄰軌跡點速度為0的百分比P4（如果P4越趨近于1，那么說明可能是交通堵塞形成的點），以及用戶A所有時空駐點簇中兩兩相鄰軌跡點速度為0的百分比的平均值P4，avg，若P4≤P4，avg，以及Ci的上一個時空駐點簇是移動點簇且該移動點簇中兩兩相鄰軌跡點速度的和的平均值V′avg大于V4，則將Ci標記為移動點簇，否則將Ci標記為停留點簇。

在執行上述基于速度閾值的停留點簇和移動點簇識別過程后，用戶A的每一個時空駐點簇被區分為停留點簇或移動點簇。停留點簇的中心點稱為停留點，而移動點簇的中心點稱為移動點。在本文中，停留點簇的中心點為停留點簇中與某一基站連接時長最長的軌跡點。對于一個停留點簇，將進入該簇的第一個軌跡點的時間作為該簇停留點的起始時間，而將離開該簇的下一個軌跡點的時間作為該簇停留點的終止時間，最后該簇停留點的經緯度、起始時間和終止時間作為下面的識別基礎。

根據以上所述可知，本文時空駐點簇需要基于速度閾值進一步識別為停留點簇或移動點簇，而且只有停留點簇才能夠用于后續職住地識別，消除了移動點簇對后續職住地識別的影響。然而，現有的職住地識別方法是直接使用時空駐點簇進行職住地識別，這顯然是不合理的。

1.3 基于K近距離的DBSCAN重要停留點聚類

對于城市居民而言，其日常生活中的出行活動和通勤行為都具有周期性，在居住地、工作地、商場、公園等重要地點的停留具有高度的規律性，所以可以使用基于空間維度的DBSCAN聚類算法對上述基于速度閾值的停留點簇和移動點簇識別過程中生成的停留點進行聚類，生成重要停留點簇。DBSCAN算法主要考慮鄰域樣本閾值MinPts和距離閾值Eps兩個關鍵參數，而不同用戶會有不同出行通勤行為，所以需要根據每個用戶的個體差異性來確定MinPts和Eps。因此，本文提出了基于K近距離的DBSCAN重要停留點聚類，如圖4所示。

其具體步驟如下：

a）輸入上述基于速度閾值的停留點簇和移動點簇識別過程中生成的用戶A（A=1，2，…，m）的停留點集合TD_A={TDi|i=1，2，…，n2}，其中m為移動終端用戶數，TDi為用戶A的第i個停留點，n2為用戶A的停留點個數。

b）根據用戶A的停留點個數計算MinPts，其計算公式［12］為

MinPts=|ln（n2）|（4）

c）計算用戶A所有停留點的距離矩陣，計算公式為

TDn2×n2={TDis（i，j）|1≤i，j≤n2}（5）

其中：TDis（i，j）為第i個停留點和第j個停留點之間的距離，計算方式與式（2）相同。

d）對距離矩陣TDn2×n2中的每一行進行升序排序，選取矩陣中第K（令K值為MinPts）列數據，即為第K近距離序列，對此序列進行升序排序，得到有序第K近距離序列，即

TDK={TDisi|1≤i≤n2}（6）

其中：TDisi為有序第K近距離序列中的第i個距離值。

e）以TDK={TDisi|1≤i≤n2}的序列索引和對應的距離值作為點的橫縱坐標，得到有序第K近距離曲線，計算其中每一個距離值TDisi與第一個距離值TDis1和最后一個距離值TDisn2連線間的垂直距離，設置最遠的點為拐點［13］，拐點對應的距離值即為距離閾值Eps。

f）基于確定的樣本閾值MinPts和距離閾值Eps，利用DBSCAN算法對用戶A的所有停留點進行聚類，生成重要停留點簇。

在執行上述基于K近距離的DBSCAN重要停留點聚類過程后，用戶A的停留點集合被分成不同的重要停留點簇，簇的中心點稱為重要停留點。在本文中，重要停留點簇的中心點為重要停留點簇中與某一基站連接時長最長的停留點。

根據以上所述可知，DBSCAN重要停留點聚類的MinPts是根據每個用戶的停留點個數計算的，而Eps是根據每個用戶的所有停留點的距離矩陣并通過有序第K近距離曲線計算拐點得到的，充分考慮了每個用戶在重要停留點的高度規律性和個體差異性，從而提高了后續職住地識別的準確率。

1.4 基于KD-tree優化的KNN職住地識別

如果用戶在某一區域的出現頻次更高、停留時間更多，那么這個區域可能是工作地、居住地、興趣點區域，也有可能是職住同一的區域。另外，若這個區域是居住地，則用戶在這個區域的居家時段的停留時長明顯多于工作時段的停留時長；若這個區域是工作地，則用戶在這個區域的工作時段的停留時長遠多于居家時段的停留時長；若這個區域是屬于職住同一的區域，則用戶在這個區域的居家時段的停留時長與工作時段的停留時長會近似相等；若這個區域是興趣點區域，則用戶在這個區域的居家時段和工作時段的停留時長相對較少。

本文提出的基于KD-tree優化的KNN職住地識別，如圖5所示。

其具體步驟如下：

a）輸入上述基于K近距離的DBSCAN重要停留點聚類過程中生成的用戶A（A=1，2，…，m）的重要停留點簇集合IC_A={ICi|i=1，2，…，n3}。其中，m為移動終端用戶數，ICi為用戶A的第i個重要停留點簇，n3為用戶A的重要停留點簇個數。每個重要停留點簇包含多個停留點。

b）計算ICi中停留點的累計出現天數占比fi1：ICi中停留點的累計出現天數與軌跡數據的總天數的比值。若ICi中同一天有多個停留點，則僅記一次出現天數，即出現1 d。

c）計算ICi中停留點的累計停留時長占比fi2，計算公式為

fi2=TAiTA（7）

其中：TAi為用戶A第i個重要停留點簇中所有停留點的停留時長之和;TA為用戶A所有停留點的停留時長之和。一個停留點的停留時長為該停留點的終止時間與起始時間之差。

d）計算ICi中停留點的累計工作時段時長占比fi3，計算公式為

fi3=TWiTA（8）

其中：TWi為用戶A第i個重要停留點簇中所有停留點的工作時段時長之和。一個停留點的工作時段時長為該停留點的停留時長中處于工作時段的時長。

e）計算ICi中停留點的累計居家時段時長占比fi4，計算公式為

fi4=THiTA（9）

其中：THi為用戶A第i個重要停留點簇中所有停留點的居家時段時長之和。一個停留點的居家時段時長為該停留點的停留時長中處于居家時段的時長。

f）經過上述步驟a）～e）后，對于每個用戶的每個重要停留點簇，將會生成一個四維特征的樣本，選取大量樣本并使用自適應K-means算法進行聚類，然后根據用戶在不同場所的時間分布特征對聚類結果進行人工標記，標記為四大類語義場所，即工作地、居住地、職住同一區域和興趣地點區域，從而形成一個“四維特征＋一維語義場所標簽”的樣本集。

g）以步驟f）中生成的樣本集為KD-tree優化的KNN分類算法的訓練樣本集，然后基于KD-tree優化的KNN分類算法對步驟a）～e）中生成的其他樣本進行分類，使得步驟a）～e）中生成的每個樣本都將有一個語義場所標簽，實現了用戶的職住地識別。

在執行上述基于KD-tree優化的KNN職住地識別過程后，每個用戶的每個重要停留點被識別為工作地、居住地、職住同一區域或興趣地點區域。根據以上所述可知，本文基于重要停留點簇中停留點的累計出現天數占比、累計停留時長占比、累計工作時段時長占比和累計居家時段時長占比生成重要停留點的語義場所標簽，而且采用聚類人工標記和分類自動標記相結合的方式，從而可以實現大規模用戶的職住地識別。此外，本文職住地識別方法能夠識別工作地、居住地、職住同一區域和興趣地點區域，而現有的職住地識別方法只能識別工作地和居住地。

2 實驗與結果分析

2.1 實驗數據集及預處理

本文實驗數據集為某運營商71萬個用戶2020年10月1日～2020年10月7日七天內在某省內的移動終端位置數據（即軌跡數據），約7億條記錄，其中每條記錄包括用戶唯一標識、日期、時間、LAC、Cell-ID、經度和緯度字段。

由于移動終端與基站進行信息交互存在無線信號強度不穩定、系統在傳輸和存儲等過程有偏差，所以進行了如下數據預處理：首先，將移動終端位置數據中時間戳字段有編碼形式轉換為北京時間；然后，將每個用戶的數據按照業務發生時間先后順序進行升序排序；接著，對無效數據中只缺失經度和緯度字段的數據根據業務前后數據進行補全；再接著，對無效數據中除時間戳字段以外都相同的重復數據進行直接刪除；最后，使用乒乓數據和漂移數據過濾算法對由乒乓切換產生的乒乓數據和由信號漂移產生的漂移數據進行過濾。

2.2 實驗結果與分析

1）時空駐點聚類

針對每個用戶七天的軌跡數據集合，執行基于K-means的DBSCAN時空駐點聚類過程。表1為某用戶不同時空距離閾值下聚類結果的輪廓系數。

在表1中，時間距離閾值和空間距離閾值是利用自適應K-means聚類算法進行聚類得到的。針對不同的時間距離閾值和空間距離閾值，生成相應的鄰域樣本閾值MinPts和距離閾值Eps，并利用DBSCAN聚類算法進行聚類，由聚類結果得到相應的輪廓系數。從表1可知，時間距離閾值和空間距離閾值分別為751和674時，DBSCAN聚類結果的輪廓系數為最大，即聚類效果最優。圖6為該用戶最優DBSCAN聚類結果。

由圖6可知，該用戶最優DBSCAN聚類結果的聚類效果很好，其時空駐點簇呈現明顯的通勤特征，說明本文基于K-means的DBSCAN時空駐點聚類過程是合理的。

隨機選取五名用戶，本文方法和現有DBSCAN時空駐點聚類方法的聚類結果輪廓系數對比如表2所示。

在表2中，文獻［2］通過繪制時空事務對象之間的距離頻數柱狀圖進行Eps的設定，Eps值單一，缺少同等條件下其他閾值的對比，不能獲得使聚類效果更好的Eps；文獻［3］使用K-means算法對軌跡點進行聚類，進而得出Eps集合，通過計算Eps獲得相對應的MinPts并選取MinPts的最大值作為最終的鄰域樣本值，此方法中K-means的K值需要人為指定，具有較大的不確定性，而且選取MinPts的最大值會將部分本屬于該簇中的點聚類到其他簇中或者被識別為噪聲點；文獻［11］通過分析居民出行定義，將時空閾值Eps設置為固定數值，由于每個居民的移動速度和日常活動不同，所以形成的出行軌跡也將不同，同時軌跡點密度差異會影響最終聚類效果。由表2可知，本文方法的聚類效果要明顯優于現有DBSCAN時空駐點聚類方法的聚類效果。此外，在本文方法上表1和2的輪廓系數有著較大差異，這主要是因為用戶的個體差異性造成的。

2）停留點簇和移動點簇識別

針對上述時空駐點聚類過程中生成的每個用戶的時空駐點簇集合，執行基于速度閾值的停留點簇和移動點簇識別過程。文獻［14］給出了居民不同行為方式的速度，如表3所示。

跑步的速度閾值V1、小范圍內慢速移動的速度閾值V2、正常行走的速度閾值V3和正常騎自行車的速度閾值V4分別為4 m/s、0.6 m/s、1 m/s和6 m/s。圖7為圖6用戶的停留點和移動點。

圖7中三角形的點為該用戶的移動點。通過比較圖6、7可知，圖7中的移動點都是圖6中時空上比較離散的且不具有明顯通勤特征的點，說明本文基于速度閾值的停留點簇和移動點簇識別過程是合理的。

3）重要停留點聚類

針對上述停留點簇和移動點簇識別過程中生成的每個用戶的停留點集合，執行基于K近距離的DBSCAN重要停留點聚類過程。圖8為圖6用戶的重要停留點。

圖8中三角形的點為該用戶的重要停留點。通過對比圖7和8可知，圖8中的重要停留點都是圖7中具有多天相近位置停留行為且具有明顯通勤特征的各個停留點（構成重要停留點簇）的中心點，說明本文基于K近距離的DBSCAN重要停留點聚類過程是合理的。

4）職住地識別

針對上述重要停留點聚類過程中生成的每個用戶的每個重要停留點簇，計算簇中停留點的累計出現天數占比、累計停留時長占比、累計工作時段時長占比和累計居家時段時長占比，生成相應的具有這四維特征的樣本。

選取1 000名用戶對應的四維特征樣本集并使用自適應K-means算法進行聚類，然后根據用戶在不同場所的時間分布特征對聚類結果進行人工標記，標記為工作地、居住地、職住同一區域和興趣地點區域四大類語義場所，形成KD-tree優化的KNN分類算法的訓練樣本集，最后基于KD-tree優化的KNN分類算法對其他用戶對應的四維特征樣本集進行分類，使得每個樣本都有一個語義場所標簽，從而實現了用戶的職住地識別。表4為部分重要停留點簇的四維特征樣本及分類結果。

按照用戶通勤規律，用戶在居住地有較高的停留頻次和停留時長，而且停留時間大多在居家時段；用戶在工作地有較高的停留頻次和停留時長，而且停留時間大多在工作時段；用戶在職住同一區域有較高的停留頻次和停留時長，而且停留時間在工作時段和在居家時段這兩個基本相當；用戶在興趣點區域有一定的停留頻次，但一般都是短暫停留，所以用戶在興趣點區域的累計停留時長占比、累計居家時段時長占比和累計工作時段時長占比都很低。由表4可知，每個重要停留點簇的四維特征與其分類結果是相符合的，說明本文基于KD-tree優化的KNN職住地識別過程是合理的。

5）對比分析

選取20 000名用戶，分別利用本文方法、時間閾值法［15］、累加時間法［16］、信息熵法［17］進行職住地識別，然后對這些用戶的職住地停留時間進行累加，得到整體停留時間分布如圖9所示。

從圖9可知，本文方法的用戶職住地整體停留時間分布明顯要優于時間閾值法、累加時間法和信息熵法，更加符合居民用戶的日常作息規律。說明本文方法的職住地識別效果要優于時間閾值法、累加時間法和信息熵法。

3 結束語

本文提出了一種基于時空約束密度聚類的職住地識別方法，包括基于K-means的DBSCAN時空駐點聚類過程、基于速度閾值的停留點簇和移動點簇識別過程、基于K近距離的DBSCAN重要停留點聚類過程和基于KD-tree優化的KNN職住地識別過程。第一個過程主要是通過自適應K-means聚類算法確定時間距離、空間距離、速度距離三大閾值集合，然后使用DBSCAN聚類算法對用戶的移動終端位置數據進行時空駐點聚類，并利用輪廓系數尋找最優的MinPts和Eps，形成最終的時空駐點簇。第二個過程主要是設定用戶不同移動行為方式下的速度閾值，然后根據這些速度閾值對用戶的每一個時空駐點簇進行識別，最終將其標記為停留點簇或移動點簇。第三個過程主要是根據用戶多天軌跡中的停留點個數確定樣本閾值MinPts，然后采用有序第K近距離曲線來確定距離閾值Eps，最后利用DBSCAN算法對用戶多天軌跡中的停留點進行聚類，生成重要停留點簇。第四個過程主要是對上述生成的每一個重要停留點簇，生成相應的四維特征樣本，然后選取大量樣本并使用自適應K-means算法進行聚類，并對聚類結果進行語義場所類別人工標記，最后以該樣本集為KD-tree優化的KNN分類算法的訓練樣本集，基于KD-tree優化的KNN分類算法對其他未標記樣本進行分類，實現用戶的職住地識別。實驗結果表明，本文方法的每個過程都是合理有效的，并且最終的職住地識別效果要優于時間閾值法、累加時間法和信息熵法。

參考文獻：

[1]Li Mingyang， Bi Xinhua， Wang Limin， et al. A method of two-stage clustering learning based on improved DBSCAN and density peak algorithm［J］.Computer Communications，2021，167：75-84.

［2]王慧東，宋耀蓮，田榆杰.一種多屬性的時空數據聚類算法分析研究［J］.重慶郵電大學學報：自然科學版，2021，33（4）：661-668.（Wang Huidong， Song Yaolian， Tian Yujie. Research on a multi-attribute spatial-temporal data clustering algorithm［J］.Journal of Chongqing University of Posts and Telecommunications：Natural Science Edition，2021，33（4）：661-668.）

［3]王兆豐，單甘霖.一種基于K-均值的DBSCAN算法參數動態選擇方法［J］.計算機工程與應用，2017，53（3）：80-86.（Wang Zhao-feng， Shan Ganlin. K-means based method for dynamically selecting DBSCAN algorithm parameters［J］.Computer Engineering and Applications，2017，53（3）：80-86.）

［4]Isaacman S， Becker R， Caceres R， et al. Identifying important places in people’s lives from cellular network data［M］.Berlin：Springer，2011：133-151.

［5]Long Ying， Thill J. Combining smart card data and household travel survey to analyze jobs-housing relationships in Beijing［J］.Compu-ters，Environment and Urban Systems，2015，53：19-35.

［6]簡志春，李清泉，常曉猛.社交網絡定位數據在居民職住地識別方法中的研究［J］.測繪地理信息，2020，45（1）：56-61.（Jian Zhi-chun， Li Qingquan， Chang Xiaomeng. Research on resident’s home—work locations identification based on social network location data［J］.Journal of Geomatics，2020，45（1）：56-61.）

［7]彭飛，宋國華，朱珊.城市公共交通常乘客通勤出行提取方法［J］.交通運輸系統工程與信息，2021，21（2）：158-165，172.（Peng Fei， Song Guohua，Zhu Shan. A method for extracting commuting trips of frequent passengers in urban public transportation［J］.Journal of Transportation Systems Engineering and Information Techno-logy，2021，21（2）：158-165，172.）

［8]張天然.基于手機信令數據的上海市域職住空間分析［J］.城市交通，2016，14（1）：15-23.（Zhang Tianran. Job-housing spatial distribution analysis in Shanghai metropolitan area based on cellular signaling data［J］.Urban Transport of China，2016，14（1）：15-23.）

［9]許寧，尹凌，胡金星.從大規模短期規則采樣的手機定位數據中識別居民職住地［J］.武漢大學學報：信息科學版，2014，39（6）：750-756.（Xu Ning， Yin Ling， Hu Jinxing. Identifying home-work locations from short-term， large-scale， and regularly sampled mobile phone tracking data［J］.Geomatics and Information Science of Wuhan University，2014，39（6）：750-756.）

［10]鐘罡.基于手機大數據的城市綜合客運樞紐乘客出行行為分析方法研究［D］.南京：東南大學，2019.（Zhong Gang. Research on passenger travel behavior analysis method of city multimodal passenger transportation hub based on mobile big data［D］.Nanjing：Southeast University，2019.）

［11]余錦斌.基于手機信令的數據分析引擎設計與實現［D］.南京：東南大學，2018.（Yu Jinbin. Design and implementation of data analysis engine based on mobile signaling[D].Nanjing： Southeast University，2018.）

［12]肖冰言.基于Cell-ID定位數據的居民職住地識別與通勤軌跡提取技術研究［D］.成都：西南交通大學，2019.（Xiao Bingyan. Research on home-work location identification and commuter trajectory extraction technology based on Cell-ID location data［D］.Chengdu：Southwest Jiaotong University，2019.）

［13]Rosalina E， Salim F D， Sellis T. Automated density-based clustering of spatial urban data for interactive data exploration［C］//Proc of IEEE Conference on Computer Communications Workshops. Piscata-way，NJ：IEEE Press，2017：295-300.

［14]萬佳，胡大裟，蔣玉明.多密度自適應確定DBSCAN算法參數的算法研究［J］.計算機工程與應用，2022，58（2）：78-85.（Wan Jia，Hu Dasha，Jiang Yuming. Research on method of multi-density self-adaptive determination of DBSCAN algorithm parameters［J］.Compu-ter Engineering and Applications，2022，58（2）：78-85.）

［15]陸劍鋒，郭茂祖，張昱，等.基于時空約束密度聚類的停留點識別方法［J］.智能系統學報，2020，15（1）：59-66.（Lu Jianfeng， Guo Maozu， Zhang Yu， et al. Stay point recognition method based on spatio-temporal constraint density clustering［J］.CAAI Trans on Intel-ligent Systems，2020，15（1）：59-66.）

［16]王艷濤，魏海平，何源浩，等.基于位置軌跡挖掘的城市居民職住地識別方法研究［J］.測繪與空間地理信息，2017，40（2）：113-116.（Wang Yantao， Wei Haiping， He Yuanhao， et al. Research on technologies of urban home-work locations identification based on position track mining［J］.Geomatics amp; Spatial Information Techno-logy，2017，40（2）：113-116.）

［17]宋少飛，李瑋峰，楊東援.基于移動通信數據的居民居住地識別方法研究［J］.綜合運輸，2015，37（12）：72-76.（Song Shaofei， Li Weifeng， Yang Dongyuan. Research on the methods of home identification based on mobile phone data［J］.Comprehensive Transportation，2015，37（12）：72-76.）