[發明專利]一種基于區域化的多關鍵字地圖搜索方法

在審

• 申請號: 201610150280.3
• 申請日: 2016-03-16
• 公開（公告）號: CN105787092A
• 公開（公告）日: 2016-07-20
• 發明（設計）人: 王燦;卜佳俊;于智;孫忠漢;王煒
• 申請（專利權）人: 浙江大學
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06F17/22
• 代理公司: 杭州天正專利事務所有限公司 33201
• 代理人: 王兵;黃美娟

技術領域

本發明涉及地圖搜索的技術領域，特別是區域化的多關鍵字地圖搜索方法。

背景技術

地圖搜索已經成為人們生活的一部分，餐飲，住宿，娛樂，教育，購物等分類搜索人 們出行前提供了很好的查詢選擇。現在百度地圖等主流地圖搜索服務已經擁有精確，充實 而且及時更新的地圖數據庫，可以滿足大部分人的地圖搜索需求。當我們有明確的目的搜 索特定地點，例如浙江圖書館，地圖搜索引擎可以精確的定位，導航。但是當我們搜索的關 鍵字為需求或者多關鍵字的需求集合，例如購物，娛樂等，地圖搜索引擎提供我們的是散布 在地圖上的許多點，這樣就不夠直觀，我們可能需要一個區域化的地點，例如商圈，可以滿 足我們多種需求的區域。隨著社會的發展，人們區域化搜索的需求一定會越來越多。

傳統地圖搜索方法提供給用戶的是散落在地圖上的點，隨著社會發展許多服務類 的行業形成商圈，用戶的需求也隨著社會的發展在不停的變化，用戶希望的區域化搜索傳 統地圖搜索方法已經無法滿足。區域化搜索可以分四步來實現，首先進行關鍵字權值擴散， 其次使用傳統的地圖搜索方法找到區域的中心點(權重最大點)，然后通過設置閾值找到區 域的邊界節點，最后將區域邊界連接形成區域即可。

發明內容

為了幫助用戶實現多關鍵字的區域化搜索的目的，本發明提出了一種基于區域化 的多關鍵字地圖搜索方法，該方法包括以下步驟：

1、針對每個地圖進行如下操作：

1)根據地圖連通性和關鍵字信息抽取出地圖中地點節點間連通矩陣G和地點節點 與關鍵字間的關鍵字權重矩陣W；

2)根據連通矩陣G的連通信息，使用標簽傳遞算法將任意節點的關鍵字權重都擴 散到其相鄰的節點，更新關鍵字權重矩陣W；

3)多關鍵字地圖區域搜索，先計算每個節點的m個關鍵字調和平均權重保存在其次對排序，通過設置閾值的方法選取前l個節點，然后對于任意節點x_i分別在各個關鍵字k_i上搜索包含該節點的子圖C，將m個不同關鍵字對應的子圖C合并就是包含x_i節點的一個滿足多關鍵字區域R，最后中l節點對應的l個區域R合并即是多關鍵字搜索的結果。特別的，當m＝1即單關鍵字地圖區域搜索，假設此關鍵字為K_i，則中保存的為K_i在各節點中的權重。

所述的步驟1)中所述的地圖信息具體是：

11)連通矩陣G解釋如下：假設地圖有p個節點則G為p×p的矩陣，元素G_i,j＝1表示 節點i與j互為鄰居，元素G_i,j＝0表示節點i與j不為鄰居。

12)關鍵字權重矩陣W解釋如下：假設地圖有p個節點則G，q個關鍵字則W為p×q的 矩陣，元素W_i,j＝1表示節點i包含關鍵字j，元素W_i,j＝0表示節點i不包含關鍵字j。

所述的步驟2)中使用的標簽傳遞算法將關鍵字的權重傳遞給相鄰的節點，關鍵字 權重矩陣W的元素W_i,j初始值為1或者0，通過設置參數保留的權重百分比λ與傳遞次數，在完 成標簽傳遞后關鍵字權重矩陣W的元素W_i,j被更新成介于0與1之間的數字。

所述的步驟3)中所描述的調和平均數，子圖C和區域R具體是：

31)調和平均數又稱倒數平均數，指數值倒數的平均數的倒數。調和平均數有簡單調和平均數和加權調和平均數兩種。多關鍵字地圖區域搜索，任意節點t簡單調和平均數的關鍵字權重H_t計算公式為：其中m為關鍵字的個數，w_i為該節點的第i個關鍵字的權重。多關鍵字地圖區域搜索，任意節點t加權調和平均數的關鍵字權重H_t計算公式為：其中m為關鍵字的個數，w_i為該節點的第i個關鍵字的權重，n_i為第i個關鍵字在計算H_t的權重。

32)子圖C指的是與x_i連通且的關鍵字k_i的權重大于設定閾值的節點構成的樹結 構。

33)區域R指的是子圖C邊緣節點連線構成的區域。