[發明專利]基于多關鍵字和用戶偏好的組合興趣點查詢方法

有效

• 申請號: 201910217464.0
• 申請日: 2019-03-21
• 公開（公告）號: CN109977309B
• 公開（公告）日: 2021-05-04
• 發明（設計）人: 俞東進;吳義宇;孫笑笑
• 申請（專利權）人: 杭州電子科技大學
• 主分類號: G06F16/9535
• 分類號: G06F16/9535;G06F16/9537
• 代理公司: 浙江千克知識產權代理有限公司 33246
• 代理人: 周希良

1.基于多關鍵字和用戶偏好的組合興趣點查詢方法，其特征在于包括如下步驟：

步驟(1).輸入查詢問題q，其中查詢問題q包含用戶q.u、查詢位置q.λ、查詢時間q.τ和一組查詢關鍵字q.ψ；

步驟(2).初始化查詢方法的基本參數，包括查詢范圍r、平衡參數γ、平衡參數β、平衡參數α；初始化一個IR樹作為查詢索引；初始化一個最小優先級隊列U用來維護中間查詢結果，并將IR樹的根節點插入最小優先級隊列U；初始化最小訪問成本curCost和最優訪問方案curGroup；

步驟(3).根據用戶q.u的歷史訪問行為，求得用戶的興趣偏好向量PV_u，計算公式如下所示：

其中，是用戶q.u在t_k時間訪問的興趣點的偏好向量，由用戶評分和該興趣點的一組特征詞組成；f(t_k)是訪問行為在時間t_k的時間權重，T₀是時間衰減參數；

步驟(4).根據查詢關鍵字q.ψ在查詢區域中為q.ψ中每個關鍵字尋找距離查詢位置q.λ最近的興趣點，將所有這些最近的興趣點組成一個候選解χ；

步驟(5).求候選解χ的訪問成本Cost，當Cost低于curCost時，更新curCost值為Cost，并更新最優訪問方案curGroup，其計算公式如下：

Cost(q,χ)＝α*Dist_s(q,χ)+(1-α)*Dist_p(q,χ)

其中，Dist_s(q,χ)為候選解的最大查詢歐氏距離，Dist_p(q,χ)為候選解的偏好距離；

步驟(6).初始化興趣點集合C＝{C₁,C₂,…,C_z}來保存所有包含查詢關鍵字的興趣點，其中C_z表示所有包含關鍵字z的興趣點的子集合；產生新候選解的具體過程如下：

步驟(6.1).若最小優先級隊列U不為空，從最小優先級隊列U中取出頭節點e；否則轉到步驟(7)；

步驟(6.2).判斷頭節點e中興趣點到查詢位置q.λ的最小距離是否超過查詢范圍r或者超過curCost/(α*γ)；若超過，則轉到步驟(8)；否則繼續運行步驟(6.3)；

步驟(6.3).若節點e為非葉子節點，將節點e中所有包含稀有關鍵字Key_rare的節點插入最小優先級隊列U，其中稀有關鍵字是指查詢關鍵字中包含最少數目興趣點的關鍵字，并轉到步驟(6.1)；若節點e為葉子節點，則繼續運行步驟(6.4)；

步驟(6.4).初始化一個關鍵字集合keySet，該關鍵字集合為查詢關鍵字中排除稀有關鍵字Key_rare后的關鍵字集合；初始化一個新的最小優先級隊列U₂，并將IR樹的根節點插入最小優先級隊列U₂；

步驟(6.5).若最小優先級隊列U₂不為空，則從最小優先級隊列U₂中取出頭節點v，并繼續運行步驟(6.6)；否則，轉到步驟(6.9)；

步驟(6.6).判斷頭節點v中任意興趣點到非葉子節點e的最小距離是否超過curCost/(α*γ)-γ*Dist(q,e)/(1-γ)或者頭節點v中任意興趣點到查詢位置q.λ的最小距離是否超過查詢范圍r；若超過，則轉到步驟(6.9)；

步驟(6.7).取出v中所有包含keySet中關鍵字的非葉子節點，即興趣點，并根據關鍵字將所有興趣點保存到集合C中對應的子集合中；

步驟(6.8).重復步驟(6.5)、步驟(6.6)、步驟(6.7)，直到最小優先級隊列U₂為空；

步驟(6.9).根據查詢關鍵字隨機組合C中的興趣點，組成新的候選解；

步驟(7).重復步驟(5)、(6)，直到最小優先級隊列U為空；

步驟(8).輸出此時的最小訪問成本curCost以及最優訪問方案curGroup；

其中步驟(5)中Dist_s(q,χ)和Dist_p(q,χ)的計算公式如下所示：

其中，Dist(q.λ,j)表示查詢位置q.λ到興趣點j的歐幾里得距離，Dist(i,j)表示查詢位置i到興趣點j的歐幾里得距離；

其中，N(χ)表示候選解χ中的興趣點數量，Pre(q.u,j)表示用戶q.u對興趣點j的偏好評分，其計算公式如下所示：

Pre(q.u,j)＝PV_u·PV_j^T

其中，PV_u表示步驟（ 3） 中求得的用戶q.u的偏好向量，PV_j表示由興趣點j的潛在主題構成的單位向量；

Access(j,q.τ)表示在q.τ時間興趣點j的可訪問程度，值越小表示興趣點在該時間段內越適合被訪問，Access(j,q.τ)的計算公式如下：

Access(j,q.τ)＝Popularity(j)×Congestion(j,q.τ)

其中，Popularity(j)表示興趣點j的受歡迎程度，由興趣點被所有訪客的歷史訪問次數決定；Congestion(j,q.τ)表示興趣點j在q.τ時間的擁擠程度，由歷史數據中以q.τ為中心的一小時內的興趣點的被訪問次數決定。

2.根據權利要求1所述的基于多關鍵字和用戶偏好的組合興趣點查詢方法，其特征在于：步驟(4)中最近距離查找利用了一個優先級隊列U₃和一個由所有興趣點組成的IR樹索引，并將IR樹的根節點插入優先級隊列U₃；具體查詢步驟如下：

步驟(4.1)：初始化一個待查詢關鍵字集合keySet，用于保存查詢關鍵字中當前尚未查詢的關鍵字；初始化一個初始候選解集合Result，用于保存候選興趣點；

步驟(4.2)：若優先級隊列U₃不為空，從優先級隊列U₃中取出頭節點e；否則轉到步驟(4.6)；

步驟(4.3)：若節點e為非葉子節點，將節點e中所有包含待查詢關鍵字的節點插入優先級隊列U₃，并轉到步驟(4.2)；

步驟(4.4)：若節點e為葉子節點，將節點e加入興趣點集合Result，并在待查詢關鍵字集合keySet中刪除節點e所包含的關鍵字；

步驟(4.5)：重復步驟(4.2)、步驟(4.3)和步驟(4.4)，直到待查詢關鍵字集合keySet為空；

步驟(4.6)：輸出Result為當前最優訪問方案curGroup。