[發明專利]一種基于度量學習的用戶軌跡相似性度量方法

有效

• 申請號: 201710847477.7
• 申請日: 2017-09-19
• 公開（公告）號: CN107679558B
• 公開（公告）日: 2019-09-24
• 發明（設計）人: 邵俊明;劉松靈;楊勤麗;于忠靖;朱慶
• 申請（專利權）人: 電子科技大學
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06F16/29
• 代理公司: 成都行之專利代理事務所(普通合伙) 51220
• 代理人: 溫利平

1.一種基于度量學習的用戶軌跡相似性度量方法，其特征在于，包括以下步驟：

(1)、用戶移動數據收集與整理清洗

收集用戶移動數據，根據分析需求對用戶移動數據進行整理清洗：采用關鍵地點信息提取技術對隱藏在用戶移動數據中關鍵地點的時間位置信息進行提取，得到用戶基于關鍵地點的軌跡表征；

(2)、用戶地點-時間聯合分布計算

首先利用聚類算法對全體用戶的關鍵地點時間位置信息進行聚類，獲取熱點區域，再結合城市已知關鍵地點的位置信息，得到全體用戶高頻訪問的關鍵地點，提取排名靠前也就是更多被訪問的P個關鍵地點作為用戶軌跡趨向訪問的地點；

對整個用戶活動時間，按照其在時間維度上的分布進行動態劃分，得到T個時間段，基于用戶軌跡趨向訪問地點和時間段劃分，對每個用戶，得到其地點-時間聯合概率分布矩陣m為用戶數量，該矩陣直接反映每位用戶軌跡在空間維度和時間維度上的分布情況；

(3)、用戶軌跡初始相似性矩陣獲取

基于每個用戶的地點-時間聯合概率分布矩陣計算用戶的軌跡與軌跡之間的初始相似性矩陣S：

其中，初始相似性矩陣S是一個對稱的相似性矩陣，s_i，j表示用戶i和用戶j的相似度，定義如下：

其中，σ是函數寬度參數，根據具體實施情況確定，KL散度d_i，j定義為：

其中，w_i(p，t)為地點-時間聯合概率分布矩陣中，在時間段t，用戶軌跡趨向訪問地點p用戶i出現的概率，w_j(p，t)為地點-時間聯合概率分布矩陣中，在時間段t，用戶軌跡趨向訪問地點p用戶j出現的概率；

(4)、軌跡初始類別獲取

對初始相似性矩陣S每行求和，按行對應依次作為對角矩陣D對角線上的元素，然后計算拉普拉斯矩陣L＝D-S，通過奇異值分解，求出拉普拉斯矩陣L的前k個最小特征值和對應特征向量

構造矩陣M：將每一個特征向量依次作為一列形成一個m行、k列的矩陣M，其中，矩陣M的每一行對應原來初始相似性矩陣S中的每一行也就是一個用戶軌跡的k維表征；

最后在這k維表征之上，采用K-Means的方式獲得每條用戶軌跡的類別標簽信息，組成軌跡初始類別集合C；

(5)、軌跡相似性度量學習

將初始相似性矩陣S和軌跡初始類別集合C分別對應到度量學習里中的兩個要素即：相似性矩陣和邊際信息，利用度量學習方法對整個用戶軌跡集合進行處理，從而得到經過學習優化后的度量函數A，同時能夠獲取各用戶軌跡在同一特征空間下的相似性表征向量

最后結合用戶軌跡的相似性表征向量和度量函數數A，利用馬氏距離算法計算得到用戶軌跡之間的距離：

用戶軌跡之間的距離dist(sv_i，sv_j)越小，相似性越大，反之，相似性越小。

2.根據權利要求1所述的基于度量學習的用戶軌跡相似性度量方法，其特征在于，步驟(2)中，所述按照其在時間維度上的分布進行動態劃分為：

其中，p_t時間段t內用戶出現的概率，δ為劃分參數用于控制時間段的跨度，取值介于0到1之間可自行調節，T_t表示時間段t。