蘇琴 謝衛(wèi)華

摘要：文檔檢索的相關性是依據(jù)用戶的搜索需求對搜索結果的一種符合用戶期望的排名。為了提高用戶對檢索系統(tǒng)的滿意度，考慮到查詢與文檔大多由名詞和動詞組成，而且在不同上下文中詞性可以起到語義消岐的作用;另外，考慮到文檔的不同字段具有不同的重要程度，因此詞位置加權將有效改進檢索系統(tǒng)的性能。由于默認的Lucene排序算法未考慮文檔不同字段、查詢詞詞性和詞性分布對檢索相關性排名的影響，因此在Lucene排序算法的基礎上，提出一種融合詞性與位置信息的改進算法。通過對比實驗分析，該改進算法能夠有效提升檢索系統(tǒng)的性能，相比默認的Lucene排名算法，準確率、召回率與F值都有不同程度的提升。

關鍵詞：BM25算法;信息檢索;相關性排序;Lucene;排序算法;垂直搜索

中圖分類號：TP391? ? ? 文獻標識碼：A

文章編號：1009-3044（2019）17-0082-04

開放科學（資源服務）標識碼（OSID）：

Abstract： The relevance of document retrieval is a ranking of the search results that meets the user's expectations based on the user's search needs. In order to improve the user's satisfaction with the retrieval system， it is considered that the query and the document are mostly composed of nouns and verbs， and parts of speech in different contexts can play the role of semantic disambiguation; in addition， considering that different fields of the document have different importance levels， the word position weighting will effectively improve the performance of the retrieval system. Because the default Lucene ranking algorithm does not consider the influence of different fields of the document， query term part of speech and its distribution on the ranking of search relevance， an improved algorithm combining part of speech and location information is proposed on the basis of Lucene ranking algorithm. Through comparative experiment analysis， the improved algorithm can effectively improve the performance of the retrieval system. Compared with the default Lucene ranking algorithm， the accuracy， recall rate and F value have different degrees of improvement.

Key words： BM25; Information retrieval; Relevance sorting; Lucene; Sorting algorithm; Vertical search

1 引言

在信息檢索領域，前人做了大量研究提出了許多算法與框架，例如布爾檢索模型[1]、向量空間模型TF-IDF[2]與概率檢索框架BM25[3]算法等。Okapi BM25算法目前已經(jīng)是很多開源框架（Elasticsearch、Solr等）的默認排序算法;該算法在自然語言處理文本加權[4] 、搜索排序等領域有廣泛的應用;目前很多商業(yè)搜索引擎使用的也是在BM25基礎上改進的排序算法。

Lucene是一個高性能、可伸縮的信息檢索庫[5]，具有添加索引和搜索的功能。Lucene自6.0版本起默認相關性排名算法采用基于概率檢索框架的BM25算法。在Lucene中，BM25算法通過IDF、文檔長度、文檔頻次、查詢詞頻信息計算查詢和文檔的相關性，按照文檔得分高低對文檔排序。相較于基于向量空間模型的TF-IDF算法，BM25算法抑制了高術語頻率對整體評分的影響。早期學者對Lucene評分算法做了大量研究，文獻[6]將BM25算法應用到個性化排名算法中，討論了用戶的查詢術語中名詞占據(jù)很大比例，因此賦予名詞較高的權重以改進檢索排名。但是該算法并沒有對查詢與文檔中詞性進行統(tǒng)計說明，并且僅僅對名詞賦予較高權重可能導致返回結果的相關性有誤。文獻[7]通過對詞位置加權并結合PageRank算法提高搜索精度。文獻[8]提出一種改進的向量空間模型，基于文檔中術語之間的鄰接關系為關鍵字賦予更多權重，該算法考慮文檔中查詢術語間的關系進而提升查詢結果的相關性。但是該算法只是考慮了局部信息，未將查詢術語在文檔不同位置的出現(xiàn)信息考慮在內。文獻[9-10]基于Lucene的默認排序算法提出一種融合位置和概率排序的改進算法，但是該算法是基于向量空間模型TF-IDF算法的改進，并且該改進算法是一種基于TF-IDF排序算法的基礎上的二次排序算法。

詞性是根據(jù)詞的特點劃分詞類，很多學者對詞性進行了研究，提出大量詞性標注方法，例如基于決策樹的方法[11]，基于規(guī)則的方法[12]以及基于統(tǒng)計的方法[13]等。考慮到詞在不同的上下文中對應不同的詞性，每種詞性又對應著不同的詞義，因此將詞性標注引入到信息檢索中將實現(xiàn)詞義消歧的功能，提高信息檢索系統(tǒng)的召回率。一些早期的文獻針對詞性標注對信息檢索系統(tǒng)的影響做了研究，文獻[14]認為用戶查詢術語通常很短因此會產(chǎn)生歧義，因此提出使用詞性標注減少查詢歧義。文獻[15]研究不同詞性特征在文本聚類中的貢獻度，通過實驗發(fā)現(xiàn)名詞是表征文本內容的重要詞性。文獻[16]將詞性標注加入信息檢索，實驗發(fā)現(xiàn)在信息檢索中加入詞性標注可能對某些特定Topic和Document的檢索結果有所改進。

本文基于上述文獻，對Lucene默認的相關性排序算法進行研究，并且針對目前相關性排序算法存在的不足進行改進，提出一種結合詞性、詞性分布、詞位置加權與Lucene默認評分算法的改進的相關性排序算法。文獻[17]中提到詞性有兩種用法：1）對某些詞性的詞進行索引;2）不同詞性的詞分開，只讓查詢文檔中詞性相同的詞能夠匹配上。本文所做工作如下：1）對給定垂直檢索系統(tǒng)中的數(shù)據(jù)進行詞性標注，并統(tǒng)計各種詞性占比，按照詞性占比排名添加負載;2）分析垂直搜索系統(tǒng)中數(shù)據(jù)的詞性分布（包括特定字段的詞性分布與整體的詞性分布）;分析查詢項的詞性分布;根據(jù)這些詞性分布信息計算每個字段的權重;3）分析給定的垂直檢索系統(tǒng)文檔的不同字段，按照字段的重要性添加權重，實現(xiàn)詞位置加權。

從Lucene的默認評分公式BM25中可以看到，默認相關性計算公式的基本思想是：通過查詢詞在文檔中的頻率、逆文檔頻率、文檔長度與兩個調優(yōu)參數(shù)對文檔的相關性進行打分，得分越高的文檔排名越靠前。該算法將文檔作為整體考慮，未考慮文檔不同字段的重要程度;另外該算法也沒有考慮查詢詞的詞性和查詢詞的詞性分布對檢索系統(tǒng)的影響。然而在實際的信息檢索系統(tǒng)中，例如在電影檢索系統(tǒng)中，電影標題往往是主要的檢索對象，賦予電影標題字段的權重顯然應高于其他字段;名詞和動詞等詞性明顯比其他詞性出現(xiàn)在文檔中的頻率更高，也應分別賦予較高的權重。

因此本文對Lucene默認評分算法做一些改進，融合詞性與位置信息，提升檢索系統(tǒng)的性能。

3 基于Lucene默認排序算法的改進

3.1文檔不同字段的權重計算

其中，f（qj）表示查詢詞qj在wi字段出現(xiàn)的頻率，|F|表示字段wi的長度，avgdlf表示平均字段長度。

3.2 與詞性分布有關的改

在本文提出的改進中，用戶查詢時，系統(tǒng)首先引用外部的詞性標注工具（Thulac[18]，結巴等）對查詢項進行詞性分析，統(tǒng)計查詢字段的詞性分布。按照查詢時的詞性分布、結合系統(tǒng)中文檔整體的詞性分布與特定字段的詞性分布計算每個字段的權重。本文基于詞性分布的改進：1）分析查詢時的詞性分布;2）分析系統(tǒng)中文檔的整體詞性分布;3）分析不同字段的詞性分布;4）計算每個字段的權重?；谠~性分布的改進公式如式（6）所示：

其中，qd表示查詢時詞性分布的占比;d表示系統(tǒng)中文檔的整體詞性分布的占比;pd表示特定字段的詞性分布的占比;field表示文檔的不同字段;m表示涉及的詞性分類;1.0表示默認權重為1.0。

3.3 詞性信息成為評分算法的一部分

Lucene默認計算公式中提供了負載[5]（默認負載字段值為1.0），本文將詞性信息以負載的形式添加到Lucene默認評分公式中，主要通過對系統(tǒng)中存儲文檔進行詞性分析，為詞性占比較高的幾種詞性添加權重?？紤]到如果對所有的詞都按照詞性添加權重將導致在搜索引擎中占據(jù)大量存儲空間，因此只對名詞和動詞添加詞性信息。此時默認的Lucene排序算法修改為公式（7）所示：

其中，payloads表示按照詞性添加的負載信息;old_score表示式（1）給出的默認的Lucene評分算法的得分。此負載信息是在索引階段建立，搜索引擎添加數(shù)據(jù)時分析詞性，如果是動詞或者名詞就按照上面給出的負載添加方式添加負載信息。

3.4 改進的Lucene排序算法

本文在默認排序算法的基礎上，對查詢詞進行詞性分析，將詞性和位置信息融合到默認Lucene排序算法中。改進的Lucene相關性排序算法如公式（8）所示：

其中，score表示式（7）中結合payloads和默認Lucene排序算法的相關性得分，weight為式（6）給出的相關字段與詞性分布有關的權重。WPosition為式（4）中給出的位置信息的權重。關于改進的Lucene排序算法的描述如下：

輸入：用戶查詢;

輸出：按照用戶查詢計算文檔排序并返回。

索引階段：對文檔進行詞性分析，將名詞和動詞的權重作為負載添加到倒排索引中;

查詢階段：1）對查詢詞進行詞性分析，按照式（6）計算特定字段的權重;2）利用Lucene的檢索功能，在返回結果的基礎上按照式（4）計算查詢詞分布在不同字段的權重;3）根據(jù)式（8）獲取最終的相關性評分;4）將搜索結果按照相關性評分排序返回。

4 實驗結果與分析

本文采用基于Lucene開發(fā)的全文檢索搜索引擎Elasticsearch進行算法的改進實驗，Elasticsearch版本為6.3.2。數(shù)據(jù)采用從時光網(wǎng)上爬取的四萬條電影數(shù)據(jù)（標題，演員列表，導演，類型，劇情簡介等），對這些數(shù)據(jù)分析、處理后得到實驗數(shù)據(jù)集。首先，從演員、導演和編劇這三個字段中隨機選取50條數(shù)據(jù)作為單人名字段查詢項;然后將這50條數(shù)據(jù)隨機組合，產(chǎn)生另外50條數(shù)據(jù)組成組合人名字段查詢項;接下來，從標題和劇情簡介字段中隨機選擇關鍵詞組合產(chǎn)生100條關鍵詞查詢項;最后將人名字段查詢項和關鍵字查詢項隨機組合產(chǎn)生100條組合人名與關鍵字查詢項。Lucene默認評分算法與改進算法的對比實驗將依據(jù)這300條查詢項展開，并且針對每次查詢返回的前200條數(shù)據(jù)分析，計算評價指標。

4.1 評價指標

本文采用信息檢索系統(tǒng)中常用的評價指標對算法進行評估，這些評價指標包括召回率（Recall），準確率（Precision）和F值度量（F measure）。準確率是指與查詢相關的檢索文檔得分;召回率指的是搜索返回結果中相關文檔的百分比;F值度量是一種測試準確性的度量，F(xiàn)值度量將準確率和召回率都包含在內。使用R表示召回率，P表示準確率，F(xiàn)表示F值度量，公式表示如下：

4.2 實驗結果分析

如上文所述，本次實驗的查詢項主要分為四類：單人名查詢項;組合人名查詢項;關鍵字查詢項;組合人名與關鍵字查詢項。實驗針對每一類進行多次實驗，并記錄每次實驗的準確率、召回率與F值，最后將這些實驗的準確率、召回率和F值求均值。表1-3記錄了算法改進前后準確率、召回率與F值的對比：

實驗結果分析：

如圖1-3所示，Lucene算法在改進后，相比改進前準確率、召回率與F值都有不同程度的提高。改進后算法的性能在基于關鍵字和組合人名與關鍵字查詢上面表現(xiàn)很好，準確率、召回率、F值的提升空間都很大。但是對于基于人名的查詢上三種評價指標的上升幅度較小，這里考慮是分詞的影響。

4 總結與展望

本文通過對Lucene默認評分算法進行分析，針對默認評分算法存在的不足進行改進。改進策略主要分為兩個方面，將詞性信息作為負載添加到Lucene默認算法的公式中;另外分析查詢字段的詞性分布，基于此為不同字段添加權重改進默認Lucene排序算法;考慮查詢詞出現(xiàn)在文檔的不同位置重要性的差別，改進Lucene默認評分算法。實驗結果表明，與Lucene默認排序算法相比改進后的排序算法的準確率、召回率和F值均有不同程度的提升。當然還存在一些缺點，例如負載信息的添加可能導致搜索引擎中存儲數(shù)據(jù)增加;另外每次查詢時需要先進行詞性分析，可能導致搜索實時性下降。下一步的工作就是優(yōu)化上述問題，以及研究不同的詞性分析方法，進一步提升檢索的相關性，以及研究如何減少檢索系統(tǒng)對分詞的依賴性。

參考文獻：

[1] Cooper W S. Getting beyond Boole.[J]. Information Processing & Management， 1988， 24（3）：243-248.

[2] Wu H C ， Luk R W P ， Wong K F ， et al. Interpreting TF-IDF term weights as making relevance decisions[J]. ACM Transactions on Information Systems， 2008， 26（3）.

[3] Robertson S， Zaragoza H. The probabilistic relevance framework： BM25 and beyond[J]. Foundations and Trends? in Information Retrieval， 2009， 3（4）： 333-389.

[4] Bestgen Y. Improving the character ngram model for the DSL task with BM25 weighting and less frequently used feature sets[C]//Proceedings of the Fourth Workshop on NLP for Similar Languages，Varieties and Dialects （VarDial）. 2017： 115-123.

[5] McCandless M， Hatcher E， Gospodnetic O. Lucene in action： covers Apache Lucene 3.0[M]. Manning Publications Co.， 2010.

[6] Cong L U O， LI Z. Personalized Ranking Algorithm Based on User Interest Modeling[J]. DEStech Transactions on Computer Science and Engineering， 2017 （cst）.

[7] 聞崢. 基于Lucene的搜索引擎優(yōu)化[D]. 北京： 北京交通大學， 2011.

[8] Wang L S. Relevance weighting of multi-term queries for Vector Space Model： 2009 IEEE Symposium on Computational Intelligence and Data Mining， 2009 [C]. Nashville， TN， USA： IEEE， 2009： 396-402.

[9] 胡博， 蔣宗禮. 融合位置相關和概率排序的Lucene排序算法改進[J]. 計算機科學， 2016， 43（9）：247-249.

[10] 胡博. 基于Lucene的垂直搜索引擎研究與實現(xiàn)[D]. 北京： 北京工業(yè)大學， 2016.

[11] Màrquez L， Rodríguez H. Part-of-speech tagging using decision trees： European Conference on Machine Learning， 1998[C].Springer， Berlin， Heidelberg： Lecture Notes in Computer Science （Lecture Notes in Artificial Intelligence） ， 1998： 25-36.

[12] Brill E. A simple rule-based part of speech tagger[C]//Proceedings of the third conference on Applied natural language processing. Association for Computational Linguistics， 1992： 152-155.

[13] Brants T. TnT： a statistical part-of-speech tagger[C]//Proceedings of the sixth conference on Applied natural language processing. Association for Computational Linguistics， 2000： 224-231.

[14] Allan J， Raghavan H. Using part-of-speech patterns to reduce query ambiguity[C]//Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval. ACM， 2002： 307-314.

[15] 韓普， 王東波， 劉艷云， 等. 詞性對中英文文本聚類的影響研究[J]. 中文信息學報， 2013， 27（2）：65-74.

[16] 蘇祺， 昝紅英， 胡景賀， 等. 詞性標注對信息檢索系統(tǒng)性能的影響[J]. 中文信息學報， 2005（2）.

[17] 程彬彬. 詞性在漢語科技文獻檢索中的作用與影響[D]. 南京： 南京農(nóng)業(yè)大學， 2008.

[18] Li Z ， Sun M . Punctuation as Implicit Annotations for Chinese Word Segmentation[J]. Computational Linguistics， 2009， 35（4）：505-512.

【通聯(lián)編輯：梁書】