基于核函數的搜索引擎研究

摘 要：通過語義相關度進行搜索引擎的設計是一種有效途徑，現通過分析搜索時獲得的頁面數和各頁面的關鍵詞密度，提出一種基于核函數的語義相關度算法。同時，在標準測試集上進行數據實驗，并與其它幾種已有方法對比，結果顯示該方法與專家打分值的Spearman相關系數最高，進一步表明了該算法的有效性，由于新算法中使用的關鍵詞沒有詞性、語法等限制，且算法簡便，所以有利于實際應用和推廣。

關鍵詞：搜索引擎；語義相關度；核函數；關鍵詞密度

中圖分類號：TP391.41 文獻標識碼：A 文章編號：2096-4706（2018）09-0077-03

Abstract：It is an effective way to design search engine through semantic relevancy. By analyzing the number of pages obtained and the keyword density of each page，a semantic correlation algorithm based on kernel function is proposed. At the same time，the data experiment on the standard test set is carried out and compared with several other existing methods. The results show that the correlation coefficient of the method and the Spearman of the expert score is the highest，which further indicates the effectiveness of the algorithm. Because the key words used in the new algorithm are not restricted by parts of speech and grammar，and the algorithm is simple，it is conducive to practical application and promotion.

Keywords：search engine；semantic relatedness；kernel function；keywords density

0 引 言

隨著“互聯網+”時代的到來，信息資源數量激增，搜索引擎已成為獲取信息的重要工具之一，這也必然會引起人們對搜索引擎的重視與研究。目前，搜索引擎研究的兩個主要方面分別是搜索結果排序與評測，將語義相關度、相似度的工作融入到搜索引擎的工作中，會使其更精確、更智能[1]。

現有的語義相關度計算方法大致可分為傳統的和基于網絡百科全書的計算方法[2]，如上下文向量方法[3]，潛在語義分析（LSA）[4]，顯示語義分析（ESA）[5]都可以用于計算，但其大多依賴Wordnet、Hownet等語義詞典或語料庫，使得算法本身就存在局限性，如受數據噪聲的影響較大[2]且不便于計算。基于搜索引擎算法的出現使得這部分問題得到有效緩解，李素建在QA系統中引入語義計算，通過詞與詞之間的相似度與相關度，算得語句間的相關度[6]；陳海燕利用語義片段去除噪音，提出SRPMI算法[7]；陳肖雨等提出基于Page Counts的相關度算法[1]。本文則在其研究的基礎上，提出了一種基于核函數的算法。

1 基于核函數的語義相關度算法

1.1 基本原理

陳肖雨等[2]假設若兩詞在同一頁面內出現，那么它們必然存在一定的相關性，在此假設下由搜索詞語返回的頁面數來計算兩詞的關聯度大小（記為rel）；劉勝久等[8]借鑒集合論中集合相似度的概念，也定義了一種根據搜索引擎返回的匹配結果進行計算的方法（記為Liu）。經過測試，這兩種方法均取得了不錯的效果。

核函數最早在1964年被Ajzerman等[10]引入到機器學習中，但是一直停留在理論層面，1992年，Boser等[11]將運用此技術將線性的支持向量機（SVMs）推廣為非線性SVMs。此后，其在文本分類方面得到更廣泛的應用。《統計學習方法》一書指出核函數是映射關系的內積，運算時不用考慮映射函數具體形式，有利于簡化計算[9]。對文本來說，在一定程度上它可以反映兩個輸入數據x，y之間的相關性，更加側重詞語之間的相似性。本文在查閱相關文獻[1]的基礎上，提出一種基于核函數的改進算法，其流程如下：

（1）預處理。將一對查詢詞x，y放入搜索引擎中查詢，得到返回的頁面數（單個搜索和共同搜索），以及匹配的n篇頁面文檔。其中，查詢時返回的文檔數量是巨大的。基于多數人的查閱心理以及搜索引擎將網頁鏈接排序時遵從相關度由高至低的假設，取n=10，且去除詞數過少的頁面（少于70詞）。然后，將文檔轉化為文本向量，其方法是多樣的，如TFIDF。閆英杰的關鍵詞密度分布算法結合了詞頻法與查詢偏重法[12]，同樣可以提取文檔的特征。考慮到算法的簡潔性，這里借用了關鍵詞密度這一概念。關鍵詞密度是關鍵詞出現次數占頁面總字節的比例，一般在2%-8%為宜。計算搜索x時返回的頁面中對y的關鍵詞密度，將其值作為該頁面的文本向量vi，得一組值C（x）=（v1，v2，…，vn）。

1.2 實驗測試

語義相關度屬于自然語言領域中的一個研究方向，這一概念自提出以來，就具有較強的主觀判斷性，對其各類計算方法的評價更是一個難題。Budanitsky[13]在對各類方法的進行研究之后，總結出評測方法的三個要點：

第一，從理論上推導，該方法是否滿足必備的數學性質；

第二，將機器上算法實現的結果與人為判斷進行比較，吻合度如何；

第三，該方法在特定應用背景下表現如何。

綜合考慮下，本文對標準測試集進行實驗，將得到的結果與人工判斷作對比，并通過分析實驗結果來進一步說明算法的可行性。

在中文計算方面，未有公開的相關測試集[14]，且中文的關鍵詞難以把握，意義大多需聯系上下文在語境中進行考量，導致得到的文本向量噪聲很大[15]。所以本文采用Miller Charles英文測試集，其由30對相關性均勻分布的詞語組成，詞對的相關度取值范圍是0至4，由38個受試者的人工判定相關度取平均值得來，這也是目前國際普遍使用的數據集[16]。

常用搜索引擎有Google、baidu、搜狗、bing等，其中Google占的市場份額最大，而根據第三方獨立調研機構益普索的盲測結果顯示，在中國有75%的參與者首選微軟bing所提供的全球搜索結果，這一方面表明微軟必應在全球搜索上已具有明顯優勢[17]，所以選用bing（國際版）作為實驗的搜索引擎，也具有一定的合理性。

1.3 結果分析

從實驗結果（表1）不難發現本文給出的方法（new method）符合認知，與原方法（rel）和另一種方法（Liu）相比，與專家值的相關系數SROCC達到0.6661，且Pr值遠小于0.05，這從一定程度上說明該算法具有一定的優勢和更強的有效性，改進后可引入到搜索引擎的工作中。經分析，其原因主要有以下幾個方面：

（1）原方法實質上基于Page Counts，主要側重的是詞語之間關聯程度的大小。而本文基于語義核函數，加入了對詞語相似度的考量；

（2）本文在實際搜索過程中，已篩選出一部分無用網頁，并進行了初步除噪。

其中，需要注意的是，無論使用何種搜索引擎，其網頁信息都會處于實時動態更新維護中，這些將會使上述算法計算結果產生差異，但影響不大。

2 結 論

本文將已有的語義相關度算法簡化，又將核函數融入其中，提出改進的基于搜索引擎的相關度算法，并在MC數據集上測試，測試結果與專家值的重合度較高，且相關系數有了明顯的提高，說明該算法確實有效。后續加大數據集，對其進行訓練，可達到更穩定的狀態（表2），實際搜索時，將搜索詞進行分詞，與頁面的關鍵詞進行相關度分析，其結果可作為搜索引擎頁面排序的依據。

同時，查詢詞通常帶有語義信息，如今的搜索引擎大多還是采用基于關鍵詞匹配的技術，而該技術的語義理解能力較弱，不能很好地把握用戶意圖[20]。該方法雖然在實驗中的評測結果較原方法更優，但仍存在問題需要對其進一步優化和改進，以達到更高的要求。初步設想可以采用查詢擴展法對關鍵詞進行基于文本內容的適當的擴展，通過奇異值分解對詞匯—文檔矩陣進行降維，挖掘文檔與文檔間、詞匯與文檔間潛在的語義關系[21]，再進行相關度的計算。

另外，中文分詞詞典規模龐大，一般在5萬-25萬詞條之間[22]，且同義詞頻繁出現，可能會導致同樣的方法在中文測試集上的效果不明顯。后續工作中應針對中文文本特性，作合理的調整，使之同樣適用。

參考文獻：

[1] 陳肖雨，郭雷，方俊.應用搜索引擎計算語義相關度的實現 [J].計算機工程與應用，2010，46（30）：128-130.

[2] 游博.詞語語義相關度計算研究 [D].武漢：華中師范大學，2013.

[3] Patwardhan S，Pedersen T. Using WordNet-based context vectors to estimate the semantic relatedness of concepts [C]//Proceedings of the EACL 2006 Workshop，Making Sense of Sense：Bringing Computational Linguistics and Psycholinguistics Together，Trento，Italy，2006，17（6）：1-8.

[4] Dumais S T，Landauer T K. A solution to Plato's problem：The latent semantic analysis theory of acquisition，induction and representation of knowledge [J].Psychological Review，1997，104（2）：211-240.

[5] Gabrilovich E，Markovitch S.Computing semantic relatedness using Wikipedia-based explicit semantic analysis [C]//Proceedings of the 20th international joint conference on artificial intelligence，2007，6：1606-1611.

[6] 李素建.基于語義計算的語句相關度研究 [J].計算機工程與應用，2002（7）：75-76+83.

[7] 陳海燕.基于搜索引擎的詞匯語義相似度計算方法 [J].計算機科學，2015，42（1）：261-267.

[8] 劉勝久，李天瑞，賈真，等.基于搜索引擎的相似度研究與應用 [J].計算機科學，2014，41（4）：211-214.

[9] 李航.統計學習方法 [M].北京：清華大學出版社，2012.

[10] Ajzerman M A，Braverman E M，Rozonoehr L I. Theoretical foundations of the potential function method in pattern recognition learning [J].Automation and Remote Control，1964，25：821-837.

[11] Boser B E，Guyon I M，Vapnik V N. A training algorithm for optimal margin classifiers [C]//Proceedings of the Fifth Annual Workshop on Computational Learning Theory. New York：ACM Press，1992，5：144-152.

[12] 閆英杰，林鴻飛，楊志豪，等.關鍵詞密度分布法在偏重摘要中的應用研究 [J].計算機工程，2007（16）：156-158.

[13] BudanitskyA，Hirst G. Evaluating WordNet-based Measures of Lexical Semantic Relatedness [J].Computational Linguistics，2006，32（1）：13-47.

[14] 汪祥.基于中文維基百科的語義相關度計算的研究與實現 [D].長沙：國防科學技術大學，2011.

[15] 萬富強，吳云芳.基于中文維基百科的詞語語義相關度計算 [J].中文信息學報，2013，27（6）：31-37+109.

[16] 張波，陳宏朝，朱新華，等.基于多重繼承與信息內容的知網詞語相似度計算 [J].計算機應用研究，2018（10）：1-2.

[17] “必應搜索·全球PK賽”中國正式啟動 [OL].[2013-06-20].http：//news.eastday.com/society/2013-06-20/346941.html.

[18] Spearman's rank correlation coefficient [OL].[2018-05-19].https：//en.wikipedia.org/wiki/Spearman's_rank_correlation_coefficient.

[19] 胡金濱，唐旭清.人工神經網絡的BP算法及其應用 [J].信息技術，2004（4）：1-4.

[20] 王文斌.面向語義搜索的查詢前置技術研究與實現 [D].上海：華東師范大學，2015.

[21] 王洋.基于潛在語義分析的智能搜索技術研究 [D].哈爾濱：哈爾濱工程大學，2010.

[22] 黃昌寧，高劍峰，李沐.對自動分詞的反思 [C]//全國計算語言學聯合學術會議，2003：26-38.

作者簡介：陳倩（1997-），女，湖北黃石人，本科。研究方向：信息計算與處理；通信作者：唐旭清（1963-），男，教授，博士。研究方向：智能計算、生物信息學、生態系統建模與仿真。