基于LBS的信息搜索系統和鏈接算法模型的設計

王一同

摘要：本文介紹了LBS的概念，簡述了與本文相關的LBS系統功能模塊的技術實現方法。設計了基于LBS功能的信息搜索系統模型和檢索信息過濾、索引排序的鏈接算法模型。

關鍵詞：LBS系統 信息搜索 PageRank 鏈接算法模型 網頁排序

中圖分類號：TP311 文獻標識碼：A 文章編號：1007-9416（2014）08-0131-02

1 引言

LBS（location based service）---基于位置的服務，結合了定位技術、移動通信技術、GIS技術和互聯網技術，通過地理信息系統平臺提供相應的無線數據業務[1]。LBS系統基本功能模塊有：基于位置的信息數據庫、LBS應用平臺、無線通信網絡及移動終端組成。LBS系統的方便之處在于通過移動終端不受時間和空間的限制獲得需要的信息服務。

2 LBS搜索系統設計

2.1 搜索系統設計

本LBS搜索系統基本功能模塊有，搜索引擎、地圖數據庫、Web地圖數據庫、基于位置的信息數據庫、LBS應用平臺、無線通信網絡及移動終端組成（圖1）。LBS應用平臺包括：移動定位網關、LBS業務管理、LBS服務器、業務處理服務器、智能業務網關、WAP網關、WEB網關、短信網關。

2.2 信息搜索模型設計

本系統以LBS應用平臺為基礎，應用元搜索技術[3]設計了一種空間位置、時間相關的搜索模型；采用空間位置和時間向量特征值作為檢索信息過濾的閥值；最后對PageRank鏈接算法進行改進，引入空間和時間計算因子對過濾后的搜索結果進行排序。本設計的地址相關搜索引擎由兩個搜索功能模塊組成（圖2），分別是：靜態數據搜索和動態數據搜索[5]。靜態數據搜索用于對移動終端上已存儲的移動空間數據和服務數據進行搜索，移動終端對用戶的查詢響應都在本地完成，不需要無線網絡服務。

動態數據搜索，進行搜索關鍵詞的地址相關的搜索和排序并再次過濾搜索結果得到與地址相關的最新信息。動態搜索的范圍應比靜態搜索的范圍更加廣泛，所以首先要對輸入的搜索關鍵詞進行擴展，在搜索關鍵詞的基礎上擴展與該地址相關的常用信息，擴大搜索查詢的范圍。互聯網包含了海量的網頁信息，使用某一個搜索引擎搜索的結果可能包含了大量不相干的網頁信息，而且無法覆蓋所有相關信息。本搜索模型設計使用了元搜索引擎技術，用戶輸入的查詢關鍵詞由元搜索引擎模塊導入給通用搜索引擎，經多個通用搜索引擎檢索后返回檢索信息，經再次過濾后得到檢索結果。本文的元搜索引擎包含以下模塊：（1）關鍵詞提取擴展；（2）搜索結果的過濾；（3）搜索結果過濾后排序。

2.2.1 關鍵詞提取和擴展

對于關鍵詞的搜索，本地的靜態搜索功能完成并返回搜索結果。動態搜索關鍵詞，使系統能夠獲得更多的位置相關信息，所以需要對關鍵詞進行擴展，實現關鍵詞擴展的方法有兩個途徑：（1）可通過搜索引擎得到和關鍵詞相關的特征詞，實際上是對關鍵詞的特征進行提取。擴展可通過訓練文檔的方法進行提取，找到查詢關鍵詞領域內的信息增益、互信息等。再將擴展后的關鍵詞構造成哈希加鏈表的詞典。在解析一個新訓練文檔的時候，對于某個在文檔中出現的單詞，首先利用哈希函數獲得哈希值，之后根據哈希值對應的哈希表項讀取其中保存的指針，找到對應的沖突鏈表。如果沖突鏈表里已經存在這個單詞說明單詞在之前解析的文檔里已經出現過。如果在沖突鏈表里沒有發現這個單詞，說明該單詞是首次碰到，則將其加入沖突鏈表里。哈希鏈表構造的詞典需要借助和維護網絡數據庫。（2）比較簡單的方法是，可以對關鍵詞進行固定維度的擴展如進行地址、時間、同義詞、屬性、添加形容詞的方式的擴展，通過人工進行擴展，構造詞典。

2.2.2 搜索結果的過濾

經元搜索引擎后，搜索的結果是與搜索關鍵詞相關的內容，和空間的相關性較弱，再次過濾的目的是獲得與空間相關性較強的檢索結果。為了突出檢索信息與空間的特征，提取出與當前LBS位置相關性最強的信息，本文使用向量空間模型進行檢索排序，因為搜索到的網頁信息眾多，為了盡量保留新的網頁，所以選取一定時間內產生的網頁，這樣引入了一個新的向量---時間。因為過濾的主要目的是查找空間相關性強的網頁，所以特征向量空間位置的權重值最高。空間位置向量的選取原則是空間位置向量特征值是與當前LBS定位的地理位置在同一區域中。將文檔轉換為特征向量后，向量空間模型將問題做了轉換，即以查詢和文檔之間的內容相似性作為相關性的替代，按照文檔和查詢的相似性得分由高到低排序作為搜索結果，相似性計算公式為：

這個公式計算用戶查詢Q和D文檔的相似性，公式中的分子部分，將文檔的每個特征權重和查詢的每個特征值相乘取和；公式的分母是兩個特征向量在歐式空間中長度的乘積，它的作用是為點積計算結果進行規范化。目的是抑制長文檔在排序中的位置[8]。

2.2.3 信息搜索鏈接算法設計

經向量特征值過濾后的檢索結果已具有一定的空間和時間的相關性，但是對于想得到和LBS系統中定位空間信息相關性更強的信息，還需要對過濾后的信息進一步的索引和排序。

本文的主要目標是基于位置的搜索算法，所以在使用爬蟲獲取網頁信息的時候，搜索的維度主要因素就是地理位置，地理位置信息作為爬蟲獲取網頁的重要條件，對指定位置以外的信息不做搜索，再結合PageRank算法對已獲取的網頁進行排序。為了進一步提高檢索到的信息與終端位置的相關性，對檢索到的網頁進行距離和時間上的PageRank網頁排序（DT-PageRank）。網頁地址距離當前終端位置越近，網頁的空間權重值越高，距離權重因子為；網頁產生時間距離當前時間越近，網頁的時間權重值越高，時間權重因子為，Dc為當前時間，Di為網頁產生時間，時間單位為天。

公式（4）中，PR（p）表示當前網頁p的PageRank值，Ti（i= 1，2，…，n）為指向網頁p的其他網頁；α為衰減系數且α∈（0，1），C （Ti）為網頁Ti的鏈出鏈接數。公式（4）在計算PR（p）時依賴于其鏈出網頁Ti的PR（Ti）值，因此，在實際計算的時候，先給每個網頁一個初始的PageRank值，比如1，然后通過迭代算法計算出每個網頁p的PageRank值。將公式（2）和公式（3）代入公式（4）得到經修正的網頁排序算法公式（5）：

通過LBS系統的定位信息和對網頁生成的位置或網頁中包含的地理位置信息可以計算出同區域中LBS服務位置與網頁位置信息的距離M，同樣的思路獲得當前LBS服務時間與網頁生成或網頁包含的時間的時間間隔（Dc-Di），經計算得分最高的網頁就是空間和時間與當前LBS系統服務空間和時間相關性最強的網頁。根據以上公式經排序后得到的網頁索引就是與定位終端位置和時間相關性最強的網頁搜索結果。

3 結語

本文提出了使用LBS系統的位置信息進行通用信息搜索的功能設計，介紹了LBS系統的組成架構、LBS位置信息服務模型的相關技術。闡述了LBS動態服務模型下，基于地理位置的信息檢索流程和鏈接算法。使基于LBS系統的搜索更加廣泛、直觀、服務的針對性更強。基于LBS的搜索技術在移動數據應用中具有廣泛的應用潛力。

參考文獻

[1]柳林，張繼賢，唐新明，李萬武.LBS體系結構及關鍵技術的研究.測繪科學，2007.

[2]倪淑潔.基于LBS的移動地理信息系統.通化師范學院學報，2007.

[3]王錚，王慶，汪定偉.基于互聯網的元搜索引擎中領域搜索模型的設計.系統仿真學報，2008.

[4]呂林濤，陳麗萍，周紅芳.面向垂直搜索引擎的主題提取算法.計算機工程，2009.

[5]陳飛翔，李華，周志武.面向LBS 的移動空間信息服務研究.計算機工程與應用，2008.

[6]鄒國兵，向陽.基于領域本體的信息搜索模型.同濟大學學報（自然科學版），2009.

[7] Chau M，Chen H. A Machine Learning Approach to Web Page Filtering Using Content and Structure Analysis[J].Decision Support Systems，2007，44（2）：482-494.

[8]張俊林.這就是搜索引擎-核心技術詳解.電子工業出版社.endprint