[發明專利]基于軌跡數據挖掘的城市語義圖譜構建方法

在審

• 申請號: 202011418901.4
• 申請日: 2020-12-06
• 公開（公告）號: CN112765226A
• 公開（公告）日: 2021-05-07
• 發明（設計）人: 孫未未;單張卿
• 申請（專利權）人: 復旦大學
• 主分類號: G06F16/2458
• 分類號: G06F16/2458;G06F16/29;G06F16/36
• 代理公司: 上海正旦專利代理有限公司 31200
• 代理人: 陸飛;陸尤

1.一種基于軌跡數據挖掘的城市語義圖譜構建方法，其特征在于，是通過軌跡數據挖掘將語義興趣點(簡稱POI)數據進行轉化，具體步驟分為如下四個階段：

(一)預處理階段：對軌跡數據進行位置與時間判定，尋找駐留點；隨后對軌跡數據進行精簡，只保留駐留點；

(二)聚類階段：根據預處理階段處理好的駐留點對臨近POI點進行到訪頻次計數，利用頻次計數、鄰域密度和語義類別對POI點進行基于密度的帶額外判定條件的DBScan聚類

(三)純化階段，根據聚類階段得到的大量聚類進行內部語義純凈度校驗；對于純凈度不足的，進行迭代的二分裂操作，直到得到多個純凈的小聚類為止；

(四)重組階段，對于純化階段產生的大量新聚類通過外部語義比較進行聚類合并。

2.根據權利要求1所述的基于軌跡數據挖掘的城市語義圖譜構建方法，其特征在于，預處理階段的具體做法為，對軌跡數據進行位置與時間判定，尋找在連續的30分鐘時間以上的，位置變動在50m距離內的GPS點，這些點的幾何中心位置定義為駐留點(stay point)，認定為出行者在此地活動，到訪了附近的POI點。

3.根據權利要求1所述的基于軌跡數據挖掘的城市語義圖譜構建方法，其特征在于，聚類階段的具體步驟為：

步驟(1)，利用駐留點位置，對附近每個POI點做到訪頻次計數；對于每個POI點p^I，其到訪頻次定義為：

即根據GPS的分布誤差符合二維高斯分布的特點，定義三倍標準差距離R_3σ，利用所有距離p^I點R_3σ以內的駐留點sp累計頻次，d(sp，p^I)指兩點之間的距離；頻次采用高斯分布系數進行描述，符合越近到訪概率越大的客觀規律；

步驟(2)，利用POI點的頻次計數、鄰域密度和語義類別對POI點進行密度聚類；采用DBScan聚類算法為基礎稍作改進，對所有POI點進行聚類，即在DBScan聚類算法的擴充聚類階段加入若干判定條件，當判定條件為真時，才允許執行加入新點到當前聚類集合；該條件定義如下：對于當前聚類集合的代表元p^I，其臨近的點在聚類算法中需要滿足額外條件：

其中，和p^I.s指POI點的語義類別標簽屬性，α指到訪頻次相似系數取值區間(0，1)，dv指投影重疊距離；該額外條件的含義為在兩個相臨近的POI點，如果在到訪頻次接近的前提下，語義標簽屬性相同或者其距離接近到近乎上下重疊則認為二者屬于同一個聚類集合。

4.根據權利要求3所述的基于軌跡數據挖掘的城市語義圖譜構建方法，其特征在于，純化階段，對于每個聚類而言，執行以下步驟：

步驟(1)、校驗；對于該聚類C₀，對內部每個POI點進行語義類別校驗和空間分布校驗，只要通過任意一項，即認為是純凈聚類，直接結束無需執行后續步驟；其中：

語義類別校驗指即聚類內部所有點語義類別一致；

空間分布校驗指即聚類的內部兩點之間最大距離小于直徑閾值d_c；

步驟(2)、描述；對于無法通過校驗步驟的聚類，對內部每個點的語義類別分布概率進行描述，該概率分布代表每個聚類內部每個POI點局部位置的語義類別組成占比；對于任意點其內部語義類別分布概率定義為：

即每一種語義類別占比被定義為該類別其余點到該點的到訪頻次計數在所有類別的計數總和中的占比；

步驟(3)、分裂；選擇聚類內部最鄰近幾何中心的POI點作為代表點，比較其他點和代表點語義類別分布概率之間的差值距離，差值距離從小到大排序，以中位數作為劃分線而分裂原聚類，形成兩個較小的聚類；其中差值距離較小的點組成的新聚類比原先的舊聚類更為語義純凈；對于任意的和其概率分布差值距離定義為兩個語義類別概率分布的KL散度，即：

步驟(4)、迭代；對于分裂步驟產生的兩個新聚類分別重復前3個步驟，進行循環迭代。