王一同

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

關(guān)鍵詞：LBS系統(tǒng) 信息搜索 PageRank 鏈接算法模型 網(wǎng)頁排序

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

1 引言

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

2 LBS搜索系統(tǒng)設計

2.1 搜索系統(tǒng)設計

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

2.2 信息搜索模型設計

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

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

2.2.1 關(guān)鍵詞提取和擴展

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

2.2.2 搜索結(jié)果的過濾

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

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

2.2.3 信息搜索鏈接算法設計

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

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

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

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

3 結(jié)語

本文提出了使用LBS系統(tǒng)的位置信息進行通用信息搜索的功能設計，介紹了LBS系統(tǒng)的組成架構(gòu)、LBS位置信息服務模型的相關(guān)技術(shù)。闡述了LBS動態(tài)服務模型下，基于地理位置的信息檢索流程和鏈接算法。使基于LBS系統(tǒng)的搜索更加廣泛、直觀、服務的針對性更強?；贚BS的搜索技術(shù)在移動數(shù)據(jù)應用中具有廣泛的應用潛力。

參考文獻

[1]柳林，張繼賢，唐新明，李萬武.LBS體系結(jié)構(gòu)及關(guān)鍵技術(shù)的研究.測繪科學，2007.

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

[3]王錚，王慶，汪定偉.基于互聯(lián)網(wǎng)的元搜索引擎中領(lǐng)域搜索模型的設計.系統(tǒng)仿真學報，2008.

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

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

[6]鄒國兵，向陽.基于領(lǐng)域本體的信息搜索模型.同濟大學學報（自然科學版），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]張俊林.這就是搜索引擎-核心技術(shù)詳解.電子工業(yè)出版社.endprint