薛曉慧，芮光輝，李煒東，袁培森

(1.國網(wǎng)青海省電力公司，青海 西寧 810008； 2.國網(wǎng)青海省電力公司海北供電公司，青海 海晏 812200； 3.南京農業(yè)大學 人工智能學院，江蘇 南京 210095)

0 引 言

搜索引擎作為一種基于關鍵字查詢的信息檢索工具，已經有30多年的發(fā)展歷史。尤其在最近十年，搜索引擎隨著因特網(wǎng)的普及而得到迅速發(fā)展，同時搜索引擎向著個性化和智能化的方向發(fā)展[1]。搜索引擎的個性化是指搜索相同的內容時會根據(jù)用戶不同的需求特點，得到不同搜索結果；而智能化則是指搜索引擎能夠進行自我學習，自動地適應用戶的搜索需求并將用戶進行智能分類，從而為搜索引擎的個性化提供依據(jù)[2]。

搜索引擎根據(jù)檢索方式的不同分為獨立型搜索引擎和元搜索引擎[3]。目前用戶普遍使用的Google和百度是獨立型搜索引擎的代表，其原理是利用Robot從網(wǎng)絡中搜集信息并且建立屬于自己的索引數(shù)據(jù)庫[4]。當需要搜索的時候則檢索其索引數(shù)據(jù)庫，再通過數(shù)據(jù)庫的內容搜索到相應的信息或連接站點并提供給用戶。元搜索引擎與獨立型搜索引擎不同，其原理是將獲得的用戶搜索需求，交給多個獨立型搜索引擎以獲得多個搜索結果，之后進行集中處理將處理過的搜索結果返回給用戶[5]。目前比較出色的元搜索引擎包括Mamma，MateCrawler，SavvySearch，萬緯，360綜合搜索等。

元搜索引擎致力于解決人們在搜索時無法得到所需信息的困擾，不至于使用戶陷入“信息過載”和“資源迷向”的困境[6]。元搜索引擎集合了多個搜索引擎檢索結果并且能對此做出整合處理，有效地解決了獨立搜索引擎信息覆蓋率不足和查準率不高的問題，為搜索引擎的發(fā)展開辟了一個新的方向。目前對于元搜索引擎的研究主要集中在搜索結果的排序和搜索結果的合成等方面[7]。

對搜索結果的排序很大程度影響了用戶對搜索結果瀏覽時的選擇，目前研究的方向不僅是單單基于相關度對結果進行排序，而是期望根據(jù)用戶的個性和特點排序搜索結果[8]。因此，排序學習(learning to rank)這一個概念應運而生，它運用了機器學習的概念，能夠基于特征集合產生訓練模型，并在之后能夠自動學習得到結果，為實現(xiàn)搜索引擎的個性化奠定了基礎[9-10]。已有的排序學習算法可以根據(jù)訓練樣例的不同分為3類：單文檔方法(pointwise)、文檔對方法(pairwise)和文檔列表方法(listwise)[5]。一般情況下性能較優(yōu)的是文檔對方法，其原理是采用查詢對應的文檔對(document pairs)作為訓練樣例，這類方法中應用較為廣泛的是Ranking SVM，一種基于支持向量機(support vector machine)的排序學習方法[11]。

對于搜索結果的合成，由于元搜索引擎從多個獨立型搜索引擎得到結果后，不同的搜索引擎采用了各不相同的排序技術，因此沒有一個統(tǒng)一的標準去重新排列得到搜索結果，如何將與用戶查詢相似度高的放在前面的位置是搜索結果合成的關鍵。目前大部分元搜索引擎會根據(jù)局部相似度或全局相似度的計算，將每個成員搜索引擎返回的文檔降序排列[12]。例如J. P. Callana等[13]針對搜索引擎返回結果的排序、相關性分值的不同，給出了間隔排列合成法、分值合成法、加權分值法；再如Krisch等[14]提出的通過修改下層搜索引擎以獲得更多信息并進行合成處理的方法[8]；再如元搜索引擎系統(tǒng)MetaCrawler引入概念可信度來決定文檔與用戶請求相關程度[15]。

元搜索引擎需要根據(jù)相似度來對搜索結果進行合成和排序，而這種相似度通常是通過詞頻來度量的[16]。但是在中文語境下對于詞頻的計算并不容易，這是因為英文的單詞與單詞之間使用空格斷開，每個單詞分別有各自的語義，電腦也因此能夠更容易地識別從而解釋這句話；而中文的每個句子由許多字和詞組成，而大多數(shù)情況下每個字并不是單獨表示意思的，必須與其他字組成詞才能表達準確的意思，但是詞語之間并沒有明顯的分隔或其他標志[17]。因此對于中文語境下的元搜索引擎，在計算相似度之前需要將搜索的關鍵字和獲取的網(wǎng)頁內容進行分詞處理[18]。分詞方法根據(jù)原理可以分為基于統(tǒng)計的，基于詞典的。中國科學院計算技術研究所的漢語詞法分析系統(tǒng)ICTCLAS(institute of computing technology，Chinese lexical analysis system)[19]是一種性能優(yōu)越的中文分詞器，綜合了基于統(tǒng)計和詞典的分詞方法，有著很好的性能并得到了廣泛的應用。

文中基于元搜索引擎的原理以及相關技術方法，設計并實現(xiàn)了一個網(wǎng)頁個性化搜索自適應排序系統(tǒng)。該系統(tǒng)使用ICTCLAS中文分詞方法對多個獨立型搜索引擎的搜索結果進行分詞處理，利用TF-IDF算法計算關鍵詞與搜索結果的相似度，以排序并合成搜索結果，再利用Ranking SVM排序學習方法對搜索結果進行重排序以形成對用戶個性化的和自適應的搜索結果。實驗結果表明，該系統(tǒng)在中文語境下能對多個獨立型搜索引擎的結果進行整合，能對整合結果進行個性化的重排序，具有良好的性能和運行效率。

1 技術原理

1.1 排序學習

為了使搜索引擎的結果能夠更好地呈現(xiàn)，使其更好地完成信息檢索的功能，近年來關于如何利用排序函數(shù)的特征去構建有效的排序函數(shù)成為熱門問題。它運用了機器學習的概念，能夠基于特征集合產生訓練模型，并在之后自動學習得到結果，為實現(xiàn)搜索引擎的個性化奠定了基礎。

排序學習算法需要的數(shù)據(jù)是由三部分構成的：查詢、與該查詢相對應的文檔的特征序列，以及由人工進行標注的查詢與文檔之間的相關度[9]。已有的排序學習算法可以根據(jù)訓練樣例的不同分為3類：單文檔方法，文檔對方法和文檔列表方法。單文檔方法，如Pranking with Ranking算法，采用一個查詢對應的單一文檔作為訓練樣例，而不考慮此文檔與該查詢對應的其他文檔之間的關系；文檔對方法，如Ranking SVM算法，采用查詢對應的文檔對作為訓練樣例；而文檔列表方法，如ListNet算法，采用查詢對應的文檔序列(document lists)作為訓練樣例。已有的研究表明，一般來說文檔對和文檔列表方法優(yōu)于單文檔方法，但是由于文檔列表對于訓練樣例的要求較高，因此系統(tǒng)采用了文檔對方法中的Ranking SVM方法對搜索引擎結果重排序的算法。

Ranking SVM是基于支持向量機的排序學習算法。它通過對機器學習中的支持向量機進行訓練，并用訓練所得的模型對網(wǎng)頁進行排序。Ranking SVM的原理如圖1所示。

圖1 Ranking SVM流程

假設有輸入空間X∈n，其中n表示特征數(shù)量。有由標簽表示的rank值空間Y={r1,r2,…,rq}，其中q代表rank值的個數(shù)[10]。另外，假設rank值之間存在一個順序關系rq?rq-1?…?r1，其中?表示參考關系。存在一系列函數(shù)的集合f∈F，集合中每個函數(shù)都能確定兩個樣本之間的參考關系：

(1)

首先，假設f是線性函數(shù)：

(2)

將公式(1)和公式(2)相加，得到：

(3)

(4)

根據(jù)所給的訓練數(shù)據(jù)集合S，創(chuàng)建了一個新的數(shù)據(jù)集合S'，新的數(shù)據(jù)集合包含l個標簽向量。

(5)

根據(jù)SVM原理，得出建立SVM模型就相當于對下面的二次最優(yōu)問題求解：

(6)

引入拉格朗日對偶公式，把公式(6)經過變化得到以下公式：

(7)

通過求解上述二次規(guī)劃問題，可以計算出最優(yōu)解α，依據(jù)公式(8)計算出最優(yōu)特征權向量w。

(8)

如果w是最優(yōu)權向量，對于一個新樣本z，Ranking SVM算法的排序函數(shù)f(z)根據(jù)公式(9)計算z的排序得分。

(9)

1.2 中文分詞方法

在計算詞頻之前，需要將搜索的關鍵字和獲取的網(wǎng)頁內容進行分詞處理。中文中每個句子由許多字和詞組成，而大多數(shù)情況下每個字并不是單獨表示意思的，必須與其他字組成詞才能表達準確的意思，但是詞語之間并沒有明顯的分隔或其他標志，增加了中文分詞的難度[20]。漢語詞法分析系統(tǒng)ICTCLAS是常用的漢語詞法分析器[19]，它使用了基于統(tǒng)計和詞典的分詞方法，主要功能包括：中文分詞、詞性標注、命名實體識別、新詞識別等。

從結構上來講，詞是由幾個字組合而成。因此在檢索上下文時，發(fā)現(xiàn)有兩個或多個字多次相鄰出現(xiàn)，則它們就很有可能構成一個詞，出現(xiàn)的次數(shù)越多，構成詞的概率越高。因此字與字相鄰共現(xiàn)的頻率或概率能夠較好地反映成詞的可信度[12]。所以只要通過對語料中相鄰共現(xiàn)的各個字的組合的頻度進行統(tǒng)計，從而計算得到它們的互現(xiàn)信息，即可以此為依據(jù)判斷這幾個字是否為一個詞。定義兩個字的互現(xiàn)信息如公式(10)所示：

(10)

其中，P(X,Y)是漢字X,Y的相鄰共現(xiàn)概率，P(X)，P(Y)分別是X,Y在語料中出現(xiàn)的概率。互現(xiàn)信息體現(xiàn)的就是通常意義上漢字之間結合關系的緊密程度，而當緊密程度高于某一個閾值時，便可判定這些字的組合可能構成了一個詞。通過上述方法可以根據(jù)中文文本識別單詞，進而完成中文分詞處理。

1.3 網(wǎng)頁內容與搜索關鍵詞相似度的計算

對于搜索結果的合成，通常采用的方法是分別計算關鍵詞和搜索結果文本的相似度指標，按照指標進行合成排序。TF-IDF(term frequency-inverse document frequency)算法是一種用于信息檢索的常用加權算法，該算法可以有效地評估一個單詞在文檔集合中的重要程度，以進行關鍵字提取和分析，廣泛地應用于數(shù)據(jù)挖掘等專業(yè)領域[21]。TF-IDF的思想是：如果某關鍵詞在一段文本中出現(xiàn)的頻率高，而在其他文本中很少出現(xiàn)，則認為此詞具有很好的類別區(qū)分能力，也就是這個關鍵詞與這一段文本相似度高，應該出現(xiàn)在合成結果的前面。

關鍵詞在一段文本中出現(xiàn)的頻率可以用詞頻(term frequency，TF)來衡量，其計算公式如式(11)所示：

(11)

其中，T是搜索的關鍵字在文檔中出現(xiàn)的次數(shù)，F(xiàn)是整篇文章詞語的總數(shù)。

關鍵詞在其他文本出現(xiàn)的頻率是否較低，或者說這個詞語的普遍重要性，可以用逆向文檔頻率(inverse document frequency，IDF)來衡量，其計算公式如式(12)所示：

(12)

其中，N表示文檔的總數(shù)量，M表示包含該關鍵字的文檔數(shù)量。

TF-IDF算法是計算一個關鍵詞在文檔集合中的TF-IDF指標，這項指標是TF指標和IDF指標的乘積，即TF-IDF=TF×IDF。對搜集到的每個搜索結果文本，計算對應的TF-IDF指標，若該指標越高，則說明該關鍵字在一條搜索結果文本中出現(xiàn)的次數(shù)越多，其重要性越高，同時也說明這個關鍵字與這項搜索結果的相似度越高，能更好地體現(xiàn)和概括文檔內容，進而說明該搜索結果是用戶期望得到的，應該放在前面；反之若TF-IDF指標越低，則說明該條搜索結果重要性越低，應該放在后面。使用TF-IDF算法計算相似度指標，相較于傳統(tǒng)的TF算法，降低了考慮IDF的所帶來結果的不可靠性[22]。

2 系統(tǒng)結構和流程

2.1 系統(tǒng)結構

系統(tǒng)功能模塊主要由網(wǎng)頁數(shù)據(jù)獲取、數(shù)據(jù)處理排序以及用戶界面三個部分組成，系統(tǒng)的內核包括：(1)根據(jù)網(wǎng)頁的URL得到百度、有道和360搜索引擎的搜索結果；(2)利用HtmlParser解析工具解析網(wǎng)頁的HTML；(3)利用ICTCLAS分詞工具對解析的結果進行分詞處理；(4)利用TF-IDF算法計算關鍵字和搜索結果文本的相似性，據(jù)此排序；(5)在得到訓練集和測試集之后，利用Ranking SVM實現(xiàn)對搜索結果的重排序，處理過程如圖2所示。

圖2 搜索引擎程序實現(xiàn)原理

第(1)步需要使用URLEncoder工具，由于客戶端在進行網(wǎng)頁請求的過程中，不允許出現(xiàn)非ASCII碼的內容。然而本系統(tǒng)是針對中文的個性化搜索引擎，請求中必然包含中文，需要使用URLEncoder將中文請求進行轉換以生成請求交由獨立型搜索引擎處理。URLEncoder的轉換方法是：(a)將請求中的非ASCII字符用其16進制的Unicode編碼表示，并在前面加上“%”；(b)請求內容中的空格全部用“+”代替；(c)其余ASCII字符不處理。

第(2)步是對獨立型搜索引擎返回的搜索結果進行解析，返回的結果是HTML形式的，因此可以考慮使用HtmlParser工具對HTML進行解析，得到搜索結果正文。HtmlParser可以對HTML文檔的DOM進行解析，進而提取出搜索結果的標題文本和正文文本。

第(3)步使用ICTCLAS分詞工具對解析得到的獨立型搜索引擎的結果進行分詞，將連續(xù)的文本根據(jù)中文語法分割成一個個單詞并標注詞性。另外標注詞性之后，需要對搜索結果文本中的無意義的虛詞(例如助詞，語氣詞，嘆詞等)進行刪除，這樣處理可以在下一步計算相似度的TF-IDF方法有更好的區(qū)分度。

第(4)步使用TF-IDF算法計算搜索關鍵詞和搜索結果文本的相似度并進行排序，按照1.3節(jié)所述的方法進行計算，得到每一條搜索結果的TF-IDF指標，按照該指標降序排列并合成搜索結果。

第(5)步則使用Ranking SVM對結果進行重排序，該步驟的目的是根據(jù)用戶的偏好，提供更加個性化的搜索結果。該方法會記錄用戶的個人偏好以形成訓練集，使用Ranking SVM進行訓練以生成排序學習模型，根據(jù)訓練得到的模型，對上一步結果使用TF-IDF算法合成得到的搜索結果進行重排序，最終得到個性化的自適應排序搜索結果。

2.2 系統(tǒng)運行流程

關于搜索引擎的系統(tǒng)流程設計，主要分為多個搜索引擎搜索結果的獲取，對搜索結果內容與標題的解析，對內容與標題的中文分詞，計算內容、標語與搜索關鍵字直接的相關度，確定搜索結果的排序，系統(tǒng)運行時，直接進入搜索界面，輸入關鍵詞即可查詢，得到搜索結果，系統(tǒng)運行流程如圖3所示。

圖3 系統(tǒng)運行流程

為了形成個性化的搜索結果，需要保存用戶的搜索記錄供Ranking SVM訓練使用，因此設計了登錄系統(tǒng)和數(shù)據(jù)庫，用于收集和存儲用戶的搜索記錄，同時后臺也可以獲取這些用戶信息進行排序學習，從而完成對搜索結果個性化重排序的功能。如果用戶不進行登錄，則得到的搜索結果僅為根據(jù)關鍵詞和搜索結果相似度排序得到的合成搜索結果，不具有個性化的特征。系統(tǒng)支持用戶多次查詢，用戶查詢次數(shù)越多，系統(tǒng)的個性化排序效果越顯著。

3 實驗和結果分析

3.1 實驗環(huán)境

CPU：Intel(R) Core(TM) i3 CPU；內存：8 GB；開發(fā)用JDK版本 1.8；依賴項：Gson，HtmlParser，ICTCLAS，Ranking SVM。

3.2 系統(tǒng)性能測試

在線搜索結果的時間由搜索的關鍵字、網(wǎng)頁內容、網(wǎng)速等多種因素決定，實驗中選取部分具有代表性的關鍵詞進行搜索并記錄搜索時間，實驗結果如表1所示。

表1 性能測試結果

目前，由于沒采用緩存，系統(tǒng)的搜索時間還有較大的優(yōu)化空間。根據(jù)性能測試結果可以發(fā)現(xiàn)，對于一些較為寬泛的關鍵詞(例如計算機、語文等)，搜索用時較長，這是因為這一類關鍵詞獨立型搜索引擎得到的結果數(shù)量就比較龐大，因而計算相似度和重排序的規(guī)模也比較大，最終導致用時增加；而對于一些比較明確的關鍵詞(例如南京大學等)，搜索用時較短，同理是因為這類關鍵詞獨立型搜索引擎結果數(shù)量較少導致的。

3.3 系統(tǒng)流程測試

輸入“計算機”關鍵詞，系統(tǒng)排序結果對比如圖4所示。其中圖4(a)是使用TF-IDF算法對搜索結果的合成，圖4(b)是使用Ranking SVM對搜索結果的重排序，可以看出順序已經調整，更加符合用戶的使用偏好。

對于關鍵詞“計算機”，經過TF-IDF計算相似度排序合成的搜索結果，可以看到“計算機互動百科”這一項出現(xiàn)在了第3個到第5個，而“計算機基礎知識教程”這一項出現(xiàn)在第1個和第2個，這是因為“計算機基礎知識教程”這一項的搜索結果文本包含了大量“計算機”這一關鍵詞，導致其TF-IDF指標比較大，所以合成排序結果的時候會前置，而“計算機互動百科”這一搜索結果對應的TF-IDF指標就比較小，所以排在稍后的位置。而經過Ranking SVM對結果進行了重排序，由于系統(tǒng)已經記錄了用戶的搜索記錄并訓練了排序學習模型，該用戶在之前的搜索中偏向于選擇與這個關鍵詞相關的百科，因此在重排序的過程中將“計算機互動百科”放在了前面，變成了第1個到第3個，而“計算機基礎知識教程”則被重排到了第8個和第9個。

圖4 排序結果示例

通過上述分析可以發(fā)現(xiàn)，該系統(tǒng)可以按照前文所述的TF-IDF算法依據(jù)相似性對獨立型搜索引擎的結果進行合成，同時Ranking SVM可以記錄用戶的搜索記錄生成排序學習模型，對合成的搜索結果進行個性化的重排序，提供給用戶自適應的個性化搜索結果。

4 結束語

基于元搜索引擎的原理以及相關技術方法，文中設計并實現(xiàn)了一個網(wǎng)頁個性化搜索自適應排序系統(tǒng)。該系統(tǒng)使用ICTCLAS中文分詞方法對多個獨立型搜索引擎的搜索結果進行處理，使用TF-IDF算法計算相似度指標以合成搜索結果，再利用Ranking SVM排序學習方法對搜索結果進行重排序以形成對用戶個性化的和自適應的搜索結果。使用Java和JSP實現(xiàn)該系統(tǒng)，實驗結果表明，該系統(tǒng)在中文語境下能對多個獨立型搜索引擎的結果進行整合，能對合成后的搜索結果進行個性化的重排序。