融合詞性與位置信息改進(jìn)的Lucene排序算法

蘇琴 謝衛(wèi)華

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

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

中圖分類(lèi)號(hào)：TP391? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2019）17-0082-04

開(kāi)放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（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 引言

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

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

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

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

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

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

3 基于Lucene默認(rèn)排序算法的改進(jìn)

3.1文檔不同字段的權(quán)重計(jì)算

其中，f（qj）表示查詢(xún)?cè)~qj在wi字段出現(xiàn)的頻率，|F|表示字段wi的長(zhǎng)度，avgdlf表示平均字段長(zhǎng)度。

3.2 與詞性分布有關(guān)的改

在本文提出的改進(jìn)中，用戶(hù)查詢(xún)時(shí)，系統(tǒng)首先引用外部的詞性標(biāo)注工具（Thulac[18]，結(jié)巴等）對(duì)查詢(xún)項(xiàng)進(jìn)行詞性分析，統(tǒng)計(jì)查詢(xún)字段的詞性分布。按照查詢(xún)時(shí)的詞性分布、結(jié)合系統(tǒng)中文檔整體的詞性分布與特定字段的詞性分布計(jì)算每個(gè)字段的權(quán)重。本文基于詞性分布的改進(jìn)：1）分析查詢(xún)時(shí)的詞性分布;2）分析系統(tǒng)中文檔的整體詞性分布;3）分析不同字段的詞性分布;4）計(jì)算每個(gè)字段的權(quán)重。基于詞性分布的改進(jìn)公式如式（6）所示：

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

3.3 詞性信息成為評(píng)分算法的一部分

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

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

3.4 改進(jìn)的Lucene排序算法

本文在默認(rèn)排序算法的基礎(chǔ)上，對(duì)查詢(xún)?cè)~進(jìn)行詞性分析，將詞性和位置信息融合到默認(rèn)Lucene排序算法中。改進(jìn)的Lucene相關(guān)性排序算法如公式（8）所示：

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

輸入：用戶(hù)查詢(xún);

輸出：按照用戶(hù)查詢(xún)計(jì)算文檔排序并返回。

索引階段：對(duì)文檔進(jìn)行詞性分析，將名詞和動(dòng)詞的權(quán)重作為負(fù)載添加到倒排索引中;

查詢(xún)階段：1）對(duì)查詢(xún)?cè)~進(jìn)行詞性分析，按照式（6）計(jì)算特定字段的權(quán)重;2）利用Lucene的檢索功能，在返回結(jié)果的基礎(chǔ)上按照式（4）計(jì)算查詢(xún)?cè)~分布在不同字段的權(quán)重;3）根據(jù)式（8）獲取最終的相關(guān)性評(píng)分;4）將搜索結(jié)果按照相關(guān)性評(píng)分排序返回。

4 實(shí)驗(yàn)結(jié)果與分析

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

4.1 評(píng)價(jià)指標(biāo)

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

4.2 實(shí)驗(yàn)結(jié)果分析

如上文所述，本次實(shí)驗(yàn)的查詢(xún)項(xiàng)主要分為四類(lèi)：?jiǎn)稳嗣樵?xún)項(xiàng);組合人名查詢(xún)項(xiàng);關(guān)鍵字查詢(xún)項(xiàng);組合人名與關(guān)鍵字查詢(xún)項(xiàng)。實(shí)驗(yàn)針對(duì)每一類(lèi)進(jìn)行多次實(shí)驗(yàn)，并記錄每次實(shí)驗(yàn)的準(zhǔn)確率、召回率與F值，最后將這些實(shí)驗(yàn)的準(zhǔn)確率、召回率和F值求均值。表1-3記錄了算法改進(jìn)前后準(zhǔn)確率、召回率與F值的對(duì)比：

實(shí)驗(yàn)結(jié)果分析：

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

4 總結(jié)與展望

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

參考文獻(xiàn)：

[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]. 北京： 北京交通大學(xué)， 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] 胡博， 蔣宗禮. 融合位置相關(guān)和概率排序的Lucene排序算法改進(jìn)[J]. 計(jì)算機(jī)科學(xué)， 2016， 43（9）：247-249.

[10] 胡博. 基于Lucene的垂直搜索引擎研究與實(shí)現(xiàn)[D]. 北京： 北京工業(yè)大學(xué)， 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] 韓普， 王東波， 劉艷云， 等. 詞性對(duì)中英文文本聚類(lèi)的影響研究[J]. 中文信息學(xué)報(bào)， 2013， 27（2）：65-74.

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

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

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

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