基于PageRank改進(jìn)的文獻(xiàn)排名算法研究

王丹

摘? 要： 在文獻(xiàn)檢索領(lǐng)域，如何更好地檢索到與用戶檢索請(qǐng)求相匹配的文獻(xiàn)是一個(gè)值得研究的問題。通常，檢索系統(tǒng)往往會(huì)采用一定的排序算法對(duì)與用戶檢索請(qǐng)求相關(guān)的文獻(xiàn)進(jìn)行排序。然而，由于文獻(xiàn)數(shù)量龐大，文獻(xiàn)內(nèi)容繁多，當(dāng)前的文獻(xiàn)檢索系統(tǒng)的性能仍有待提高。文章基于Lucene排序機(jī)制及PageRank算法，提出了一種新的文獻(xiàn)搜索排序算法。該算法同時(shí)考慮了文獻(xiàn)的相關(guān)性和權(quán)威性。通過實(shí)驗(yàn)表明，與傳統(tǒng)的檢索算法相比，該算法的性能有一定程度的提高。

關(guān)鍵詞： 文獻(xiàn)檢索; 排序算法; Lucene; PageRank

中圖分類號(hào)：G712? ? ? ? ? 文獻(xiàn)標(biāo)志碼：A? ? ?文章編號(hào)：1006-8228（2019）01-59-04

Abstract： In the field of bibliography retrieval， how to retrieve literatures that meet users' need is a complicated problem. Usually， retrieval systems tend to adopt certain sorting algorithm for sorting the user retrieval request related literature. However， the performance of the current literature retrieval system needs to be improved. Based on Lucene sorting mechanism and PageRank algorithm， this paper proposes a new literature search ranking algorithm. The algorithm takes into account both the correlation literature and authority. Experiments show that compared with the traditional retrieval algorithm， the performance of this algorithm has a certain degree of improvement.

Key words： bibliography retrieval; sorting algorithm; Lucene; PageRank

0 引言

人們?cè)谧珜懣萍颊撐牡倪^程中，往往會(huì)查閱大量的文獻(xiàn)資料，文獻(xiàn)檢索系統(tǒng)成為了眾多學(xué)者不可或缺的工具。然而在文獻(xiàn)檢索系統(tǒng)中，用戶如何很好地檢索到符合期望的文獻(xiàn)是一個(gè)值得研究的問題[1]。當(dāng)前，文獻(xiàn)檢索系統(tǒng)種類繁多，存在多種領(lǐng)域，不同類型的檢索系統(tǒng)[2]。如CNKI、萬方、Google Scholar、Microsoft Academic Research、ArentMiner等。如今，隨著科學(xué)技術(shù)迅猛發(fā)展，科技文獻(xiàn)數(shù)量也在不斷增長(zhǎng)[1]。文獻(xiàn)數(shù)量的增長(zhǎng)一方面為研究者提供了豐富的資源，另一方面也為研究者在文獻(xiàn)檢索過程中帶來了一些問題。如何較為準(zhǔn)確地從眾多的文獻(xiàn)中找到符合研究者需要的文獻(xiàn)資料，顯然已成為人們關(guān)注的熱點(diǎn)問題。

針對(duì)文獻(xiàn)檢索過程中的問題，一些學(xué)者提出了不同的解決方法，主要表現(xiàn)在兩個(gè)方面：針對(duì)文獻(xiàn)相關(guān)性算法的研究以及針對(duì)文獻(xiàn)影響力排名的研究[2]。文獻(xiàn)相關(guān)性算法主要是基于對(duì)文獻(xiàn)的基本特征提出，通過一定的算法對(duì)文獻(xiàn)的主題相關(guān)性進(jìn)行計(jì)算，如一些文獻(xiàn)檢索系統(tǒng)即采用了傳統(tǒng)的Lucene[1]搜索引擎的排序算法[2]。此外，也有一些研究者針對(duì)文獻(xiàn)的關(guān)鍵信息的提取和分析，提出了一些算法，如Steven Bethard[2]等人對(duì)影響文獻(xiàn)排名的不同因素進(jìn)行了分析，提出了一種基于多因素的文獻(xiàn)相關(guān)排序方法[2]。柳泉波[3]等人則提出了一種基于鏈接分析的文獻(xiàn)排名方法。劉欣[4]等人基于文獻(xiàn)價(jià)值對(duì)文獻(xiàn)排名算法進(jìn)行了改進(jìn)。劉松濤[5]則基于科技文獻(xiàn)按關(guān)鍵詞檢索后得到的引文網(wǎng)絡(luò)系統(tǒng)，提出了一種引文排序算法。

對(duì)文獻(xiàn)影響力排名的研究十分廣泛。通常，文獻(xiàn)影響力可以采用被引次數(shù)來計(jì)算。也有一些學(xué)者采用PageRank來計(jì)算文獻(xiàn)的排名。如Chen P[2]等人基于PageRank算法對(duì)文獻(xiàn)進(jìn)行了排序，并討論了PageRank在不同參數(shù)值下得到的排名情況。Ma N[6]等人也基于PageRank算法提出了一種改進(jìn)的文獻(xiàn)排名算法，并對(duì)文獻(xiàn)排名的結(jié)果進(jìn)行了分析。

為了更好地提高文獻(xiàn)檢索的效果，本文基于Lucene的排名機(jī)制及PageRank算法，提出了一種新的文獻(xiàn)搜索排名算法。該算法一方面考慮了檢索結(jié)果和用戶查詢請(qǐng)求的相關(guān)性，另一方面也考慮了文獻(xiàn)的實(shí)際影響力。

本文的基本結(jié)構(gòu)如下：第二部分介紹了算法的主要思想，第三部分給出了對(duì)比實(shí)驗(yàn)結(jié)果，對(duì)算法的有效性進(jìn)行了驗(yàn)證。第四部分對(duì)本文的工作進(jìn)行了總結(jié)。

1 提出的算法

1.1 問題定義

定義全部文獻(xiàn)集為：，定義全部的作者構(gòu)成的集合為，作者和文獻(xiàn)撰寫關(guān)系為，文獻(xiàn)之間的引用關(guān)系為。此外，可以定義會(huì)議和期刊的集合為：。而會(huì)議和期刊跟文獻(xiàn)的關(guān)系即可定義為：，其中。

定義全部查詢請(qǐng)求的集合，定義查詢，其中term表示將查詢內(nèi)容進(jìn)行分詞之后得到的詞匯單元，一個(gè)查詢請(qǐng)求由若干個(gè)詞匯單元構(gòu)成。

那么，實(shí)際上由作者、文獻(xiàn)及其之間的關(guān)系可以構(gòu)成一個(gè)六元組。我們研究的問題即找到一種方法，對(duì)于查詢請(qǐng)求q，能夠基于G給出最為合理的結(jié)果列表X。

1.2 PageRank算法

PageRank[1]算法是由Larry Page等人于1999年提出的一種網(wǎng)頁排序算法。該算法同時(shí)考慮了網(wǎng)頁的流行性和權(quán)威性。也即，如果一個(gè)頁面P被更多的頁面引用，如{C1，C2，C3…}，同時(shí)，當(dāng)這些頁面{C1，C2，C3…}也都是被很多其他頁面引用的優(yōu)質(zhì)網(wǎng)頁的時(shí)候，那么網(wǎng)頁P(yáng)則是一個(gè)優(yōu)質(zhì)的網(wǎng)頁。

由于文獻(xiàn)引用網(wǎng)絡(luò)和網(wǎng)頁引用網(wǎng)絡(luò)的結(jié)構(gòu)是非常相似的，而PageRank算法作為一種鏈接關(guān)系排序算法，所以，PageRank被移植到文獻(xiàn)網(wǎng)絡(luò)中用于文獻(xiàn)和作者的排序。一般認(rèn)為，一篇文章引用另一篇文章，往往表示一種認(rèn)同關(guān)系（這里，我們假定所有的文獻(xiàn)引用都是一種認(rèn)同，不考慮文獻(xiàn)之間相互批判的情況）[5]。如果一篇文獻(xiàn)M能得到非常多的文獻(xiàn)的引用，且如果這些引用M的文獻(xiàn)也是質(zhì)量很高的文獻(xiàn)，那么顯然M應(yīng)該是一篇非常優(yōu)秀的文獻(xiàn)。此外由于文獻(xiàn)之間的引用關(guān)系相比網(wǎng)頁之間的引用關(guān)系而言，更加嚴(yán)謹(jǐn)，不會(huì)像網(wǎng)頁引用那樣隨意，所以將PageRank應(yīng)用與文獻(xiàn)價(jià)值排序是比較可行的。

1.3 Lucene排序機(jī)制

Lucene[2]是由Apache基金會(huì)支持和提供的一款用于全文檢索的開源工具。由于其使用的便捷性和靈活性，以及Lucene在全文檢索中表現(xiàn)出的優(yōu)異性能，Lucene已經(jīng)被廣泛地用于眾多的檢索系統(tǒng)中。一些圖書館、文獻(xiàn)檢索系統(tǒng)也都直接采用了Lucene作為其檢索工具。

Lucene的主要內(nèi)容包括了分詞、倒排索引、排序機(jī)制等。其中，Lucene排序機(jī)制的研究也十分廣泛。已有一些學(xué)者在Lucene現(xiàn)有的排序機(jī)制上進(jìn)行擴(kuò)展和改進(jìn)，以優(yōu)化其排序結(jié)果。本文基于Lucene的排序機(jī)制，結(jié)合PageRank算法，提出一種新的文獻(xiàn)排序方法。

1.4 文獻(xiàn)檢索排序算法

1.4.1 評(píng)價(jià)文獻(xiàn)的價(jià)值

對(duì)于用戶而言，檢索的到的文獻(xiàn)能容十分相關(guān)，并不意味著這篇文獻(xiàn)是用戶想要的。因?yàn)閷?duì)于研究者而言，我們往往希望去閱讀更有價(jià)值的文獻(xiàn)。而文獻(xiàn)的價(jià)值一般可以通過被引次數(shù)、作者水平、文獻(xiàn)所在的期刊或會(huì)議的級(jí)別等來認(rèn)定，所以，我們主要從如下三個(gè)方面對(duì)文獻(xiàn)進(jìn)行評(píng)價(jià)。

⑴ 文獻(xiàn)的PageRank值

我們采用PageRank值而非被引次數(shù)的原因在于，PageRank值的衡量結(jié)果比被引次數(shù)更為合理。如前所述，PageRank是一種鏈接排序算法，在文獻(xiàn)系統(tǒng)中，我們可以基于文獻(xiàn)之間的引用關(guān)系構(gòu)建一個(gè)引用關(guān)系矩陣，基于該矩陣來運(yùn)行PageRank算法。

首先，我們構(gòu)造文獻(xiàn)引用數(shù)據(jù)集。然后，基于該數(shù)據(jù)集，采用如下公式進(jìn)行PageRank迭代計(jì)算：

其中，表示文獻(xiàn)pj的PageRank得分，N表示全部文獻(xiàn)的數(shù)量，p表示某一篇文章，pi表示引用文章p的其他文章，Citation（pi）表示文章pi的參考文獻(xiàn)數(shù)，d為參數(shù)，可以設(shè)置為0.85。

最后，基于公式⑴進(jìn)行迭代，計(jì)算每一篇論文的PageRank值，即為該片論文的價(jià)值。

PageRank值和單純的引用值有一個(gè)較為明顯的差異，即一篇文獻(xiàn)的價(jià)值的衡量不僅僅是通過被其他論文引用的次數(shù)來決定，同時(shí)，每一個(gè)引用的質(zhì)量也將被考慮。

⑵ 作者研究水平

目前，衡量作者研究水平往往可以從作者被引用次數(shù)、發(fā)文量、合作者數(shù)等角度來衡量，而當(dāng)前最為流行且認(rèn)可度較高的是采用h-index來衡量作者的研究水平。這里我們直接采用作者的h-index的值來評(píng)估作者的研究水平。定義作者研究水平為：，其中ai∈A。由于一篇文獻(xiàn)往往有多位作者，我們將某一篇文獻(xiàn)的作者影響力為：AImpact（pj），且：

⑶ 期刊或會(huì)議級(jí)別

當(dāng)前，衡量期刊或會(huì)議級(jí)別存在多種不同的衡量方法，如SCI的影響因子IF、被引次數(shù)等、平均。由于影響因子近年來多被人詬病，且其確實(shí)存在對(duì)期刊評(píng)價(jià)的不合理處，而被引次數(shù)顯然是一種非常不合理的指標(biāo)（該指標(biāo)和刊物的發(fā)文量非常相關(guān)），且當(dāng)前不同排名機(jī)制尚存爭(zhēng)議。這里，我們采用了一種折衷方法，即基于CCF的推薦排名[12]來計(jì)算期刊和會(huì)議的得分。由于CCF的《中國(guó)計(jì)算機(jī)學(xué)會(huì)推薦國(guó)際學(xué)術(shù)會(huì)議和期刊目錄》當(dāng)前已經(jīng)被廣泛地認(rèn)同，且本身非常權(quán)威，所以比較適合用于期刊和會(huì)議的評(píng)價(jià)。

這里，由于這里我們并不需要得到實(shí)際的期刊和會(huì)議排名，只需要做一定的區(qū)分，所以，我們將CCF排名映射為不同的數(shù)值，其中CCF中的A類排名，我們?nèi)≈禐?，B類為3，C類為2，沒有出現(xiàn)在CCF上的為1。那么，可以將期刊和會(huì)議的影響力定義為：CImpact（Ji），其中Ji∈J。

⑷ 文獻(xiàn)發(fā)表的年限

在文獻(xiàn)檢索中，檢索用戶往往希望查詢較為新近的文章，因?yàn)檠芯空咝枰私庾钚碌难芯壳闆r，掌握最新的科研動(dòng)態(tài)。所以，一般而言，研究者在使用檢索系統(tǒng)的過程中，往往偏好于較新的文獻(xiàn)。所以，我們將文獻(xiàn)發(fā)表的年限融入文獻(xiàn)價(jià)值評(píng)定的指標(biāo)，并將其定義如下：

其中，tc為當(dāng)前的時(shí)間，為文獻(xiàn)pj的發(fā)表時(shí)間。顯然，越久遠(yuǎn)的文獻(xiàn)，其獲得的值越小;而越新近的文獻(xiàn)，其獲得的值越大。

基于以上四個(gè)指標(biāo)，我們將文獻(xiàn)價(jià)值定義如下：

其中，且。

1.4.2 文獻(xiàn)評(píng)分函數(shù)

前面小節(jié)中，我們對(duì)文獻(xiàn)的價(jià)值評(píng)價(jià)方法進(jìn)行了分析和定義。實(shí)際上，影響文獻(xiàn)最終得分的因素非常之多，比如，文獻(xiàn)和查詢請(qǐng)求的相關(guān)度，文獻(xiàn)本身的價(jià)值，文獻(xiàn)發(fā)表的年限等。為了綜合衡量文獻(xiàn)和查詢請(qǐng)求的相關(guān)性以及文獻(xiàn)本身的價(jià)值，我們將文獻(xiàn)評(píng)分函數(shù)定義如下：

idf（t）表示逆詞頻，它表達(dá)了詞匯單元在所有文檔中的頻率。即，如果一個(gè)詞匯出現(xiàn)的次數(shù)越少，那么那就應(yīng)該更加重要，所以idf（t）的定義如下：

其中，numPub表示文獻(xiàn)數(shù)量，而pubFreq則表示詞頻。

coord（q，d）衡量的查詢請(qǐng)求中的詞匯單元，有多少個(gè)出現(xiàn)在了這個(gè)文檔d中。coord（q，d）的定義如下：

其中，overlap表示查詢請(qǐng)求的全部詞匯單元在給定文獻(xiàn)中都有多少個(gè)命中了，而maxoverlap則表示查詢請(qǐng)求q的全部詞匯單元個(gè)數(shù)，即|q|。

實(shí)際上，我們可以將公式⑷代入公式⑸，即可得到最終的文獻(xiàn)檢索排序公式，定義如下：

基于該函數(shù)，我們可計(jì)算每個(gè)查詢請(qǐng)求所對(duì)應(yīng)的結(jié)果集，以及結(jié)果集中的文獻(xiàn)排序。

2 實(shí)驗(yàn)

2.1 實(shí)驗(yàn)數(shù)據(jù)集

作者從ArnetMiner爬取了Semantic Web、Information Retrieval、Fuzzy System以及Data Mining領(lǐng)域的4個(gè)文獻(xiàn)數(shù)據(jù)集。數(shù)據(jù)集中包含了作者、作者單位、標(biāo)題、摘要、引用等信息。

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

為了對(duì)算法的有效性進(jìn)行驗(yàn)證，我們采用了P@N指標(biāo)來進(jìn)行評(píng)估。P@N是指返回的前N個(gè)結(jié)果中，相關(guān)文獻(xiàn)所占的比率。其定義形式如下：

其中，Rn為返回的前n個(gè)結(jié)果構(gòu)成的集合，他們的得分是最高的。而Cn則表示與該查詢實(shí)際相關(guān)的結(jié)果構(gòu)成的集合。P@N的值越大，則表示該算法更為有效。

2.3 實(shí)驗(yàn)結(jié)果

這里，我們選取了傳統(tǒng)的Lucene算法作為對(duì)比對(duì)象。我們分別在爬取到的Semantic Web、Information Retrieval、Fuzzy System以及Data Mining領(lǐng)域的4個(gè)文獻(xiàn)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)。

首先，我們構(gòu)建了一個(gè)查詢集合，該查詢集合包含了128個(gè)常用的查詢請(qǐng)求。然后，我們對(duì)查詢到的結(jié)果進(jìn)行收集，并打亂其順序，構(gòu)成新的結(jié)果集R'。接下來，對(duì)于每個(gè)領(lǐng)域分別邀請(qǐng)5位領(lǐng)域?qū)＜覍?duì)得到的結(jié)果進(jìn)行標(biāo)記（標(biāo)記相關(guān)和不相關(guān)）。最后，對(duì)專家的標(biāo)記情況進(jìn)行整理，即可得到四個(gè)領(lǐng)域下本文算法和Lucene算法在P@5、P@10和P@20下的準(zhǔn)確率。實(shí)驗(yàn)結(jié)果如表1所示。

圖1至圖4以更加直觀的方式展示了兩種算法的性能對(duì)比。從表1和圖1-圖4可以看出，本文的算法在一定程度上提高了系統(tǒng)的性能。實(shí)際上，由于本文算法考慮了文獻(xiàn)的價(jià)值，所以實(shí)驗(yàn)結(jié)果較傳統(tǒng)結(jié)果更豐富，更符合用戶的需求。

3 結(jié)束語

本文針對(duì)文獻(xiàn)檢索排序問題，分析了文獻(xiàn)檢索過程中用戶關(guān)注的要點(diǎn)，即用戶不僅僅只是關(guān)注返回的結(jié)果是否與查詢是相關(guān)的，同樣關(guān)注文獻(xiàn)的質(zhì)量和文獻(xiàn)的新舊程度。基于文獻(xiàn)的相關(guān)性和文獻(xiàn)的重要性，本文提出了一種新的文獻(xiàn)檢索排序算法。該算法綜合考慮了文獻(xiàn)的重要性和相關(guān)性。最后，通過實(shí)驗(yàn)驗(yàn)證了該方法的有效性。

參考文獻(xiàn)（References）：

[1] 宋京京，潘云濤，蘇成.基于PageRank算法的圖書影響力評(píng)價(jià)[J].中華醫(yī)學(xué)圖書情報(bào)雜志，2015.12（24）：9-14

[2] 曾瑋.文獻(xiàn)排名預(yù)測(cè)算法及作者影響力評(píng)估算法研究[D].西南大學(xué)，2014.

[3] 柳泉波，許駿.基于鏈接分析的科學(xué)文獻(xiàn)個(gè)性化排序算法[J].中山大學(xué)學(xué)報(bào)：自然科學(xué)版，2008.47（6）：87-92

[4] 劉欣.基于閱讀價(jià)值的科技文獻(xiàn)排序方法研究[D].大連理工大學(xué)，2010.

[5] 劉松濤.基于引文排序的科技文獻(xiàn)檢索研究[D].東北師范大學(xué)，2010.

[6] 李稚楹，楊武，謝治軍.PageRank 算法研究綜述[J].計(jì)算機(jī)科學(xué)，2011.38（B10）：185-188