結(jié)合PageRank算法的Lucene評(píng)分機(jī)制改進(jìn)研究

張禹，周翔

（1.福建江夏學(xué)院 電子信息科學(xué)學(xué)院，福建 福州 350108；2.閩江學(xué)院 軟件學(xué)院，福建 福州 350108）

21世紀(jì)以來(lái)，因特網(wǎng)上的Web數(shù)量不斷增加，伴隨著近年來(lái)Web2.0理念的誕生，未來(lái)的桌面應(yīng)用可能有相當(dāng)大的一部分將轉(zhuǎn)移到Web平臺(tái)上，再加上云計(jì)算等技術(shù)的不斷完善，互聯(lián)網(wǎng)上的數(shù)據(jù)挖掘已經(jīng)凸顯出十分明顯的商業(yè)價(jià)值。搜索引擎自誕生以來(lái)就一直扮演著Web結(jié)構(gòu)挖掘者的角色，在當(dāng)前這樣一個(gè)萬(wàn)維網(wǎng)高速的擴(kuò)張的時(shí)代，網(wǎng)絡(luò)用戶為了獲得準(zhǔn)確的信息資源，已經(jīng)根本離不開它。

現(xiàn)有的搜索引擎與其誕生之初相比，無(wú)論在搜索的召回率（recall，又稱查全率）和精確度(pricision，又稱查準(zhǔn)率)方面都有了很大的進(jìn)步[1]。當(dāng)然，在部分搜索主題下，還存在著一些不完善的地方，例如：用戶在使用搜索引擎進(jìn)行搜索的過(guò)程中找到的并不完全是預(yù)期的結(jié)果，經(jīng)常會(huì)包含一些無(wú)關(guān)的頁(yè)面鏈接。更為嚴(yán)重的是，有時(shí)候這些數(shù)據(jù)還可能出現(xiàn)在返回的頁(yè)面鏈接列表的前端。這是搜索引擎開發(fā)者所不希望看到的[2]。如何有效地排除無(wú)關(guān)噪聲數(shù)據(jù)，獲得盡可能準(zhǔn)確的信息，一直是搜索引擎開發(fā)者的努力方向，而解決問題的有效途徑就是通過(guò)Web挖掘技術(shù)。

1 PageRank算法

Web挖掘技術(shù)分為：內(nèi)容挖掘、使用挖掘與結(jié)構(gòu)挖掘[3]。Web內(nèi)容挖掘包括文本數(shù)據(jù)挖掘、多媒體數(shù)據(jù)挖掘；Web使用挖掘包括用戶訪問模式（習(xí)慣）分析與網(wǎng)站定制分析兩類；Web結(jié)構(gòu)挖掘包括網(wǎng)頁(yè)超鏈接挖掘與頁(yè)面內(nèi)在結(jié)構(gòu)挖掘[4]?，F(xiàn)有的全文搜索引擎的數(shù)據(jù)收集過(guò)程都是通過(guò)網(wǎng)絡(luò)爬蟲程序訪問鏈接來(lái)實(shí)現(xiàn)的?；谠撎攸c(diǎn)，使用Web結(jié)構(gòu)挖掘技術(shù)更能有效地應(yīng)用于搜索引擎中，提高其搜索精度。

在Web結(jié)構(gòu)挖掘中，PageRank算法是其經(jīng)典算法之一。該算法是Google搜索引擎最早用到的挖掘算法，其基本理念是利用該算法和文本鏈接標(biāo)簽，詞頻統(tǒng)計(jì)等因素相結(jié)合的方法對(duì)由搜索主題檢索出的海量結(jié)果進(jìn)行排序，根據(jù)PageRank值的大小來(lái)判別頁(yè)面等級(jí)值高低，讓重要程度更高的頁(yè)面排在所有結(jié)果的前面[5]。

PageRank算法的思想基于以下幾個(gè)假設(shè)條件：(1)某一頁(yè)面被其他頁(yè)面引用次數(shù)多，那么，該頁(yè)面可能具備很高的重要程度；(2)某一頁(yè)面雖然被其他頁(yè)面引用的次數(shù)有限，但是如果引用它的頁(yè)面中存在著已經(jīng)被評(píng)價(jià)為重要等級(jí)的網(wǎng)頁(yè)，則該頁(yè)面也有可能是重要的；(3)任何一個(gè)頁(yè)面的重要程度都是被平均地分配給它所引用的頁(yè)面去；(4)如果用戶一開始隨機(jī)地訪問Web集合中的一個(gè)頁(yè)面Web1，之后以這個(gè)頁(yè)面為基準(zhǔn)隨著頁(yè)面上的鏈接向外或者向前瀏覽其他目標(biāo)頁(yè)面（過(guò)程中不后退），那么，用戶點(diǎn)擊超鏈接瀏覽下一個(gè)頁(yè)面WebX的概率就被認(rèn)為是頁(yè)面WebX的PageRank值[6]。

PageRank算法的定義如下：假設(shè)u是一個(gè)Web頁(yè)，F(xiàn)(u)是u指向的所有頁(yè)面集合，B(u)是所有指向 u的頁(yè)面集合，設(shè) N（u）=|F(u)|是從 u發(fā)出的鏈接數(shù) ，c（其值小于 1）是一個(gè)歸一化因子（以Google為例，取的是 0.85），則 u的PageRank值的定義公式[7]如式（1）：

PageRank算法的主要缺點(diǎn)是在于它的隨機(jī)特性，其算法思想是基于用戶以某個(gè)頁(yè)面為起點(diǎn)訪問該頁(yè)面上所有鏈接的幾率相等這一假設(shè)，因此一個(gè)頁(yè)面的重要性被均勻分布并傳遞到它所引用的頁(yè)面[8]。正因?yàn)橹匾缘钠骄峙涠赡芤鹬黝}相關(guān)度高的頁(yè)面與相關(guān)度低的頁(yè)面被同等對(duì)待，即過(guò)分注重鏈接的出入度，從而在相當(dāng)程度上導(dǎo)致主題偏移現(xiàn)象的出現(xiàn)。

2 Lucene框架

2.1 Lucene框架簡(jiǎn)介

Lucene是基于Java的開源框架[9]，是著名的Apache Jakarta中的一個(gè)主要組成部分，而且具有Apache軟件許可（ASF License）。此外，它還是一個(gè)高效率、功能完善的信息檢索庫(kù)[10]。利用Lucene框架，開發(fā)人員可以在其應(yīng)用程序中部署強(qiáng)大的索引與搜索功能，如圖1所示。

圖1 搜索應(yīng)用程序和Lucene之間的關(guān)系

2.2 Lucene框架下的頁(yè)面評(píng)價(jià)機(jī)制

Lucene 對(duì)文檔的評(píng)分公式[11]如式（2）：

該公式中：d表示某一待評(píng)分的文檔；q表示某一查詢；score(q,d)就是反映文檔d關(guān)于查詢q的主題相關(guān)程度的權(quán)值；t指的是term（詞），它是搜索的基本單位，構(gòu)建該對(duì)象需要提供兩個(gè)字符串類型的參數(shù)，第一個(gè)參數(shù)表示在當(dāng)前的document中查找的field的位置，另一個(gè)參數(shù)則代表了要查詢的關(guān)鍵詞；coord(q,d)表示的是某一文檔中所包含的與查詢q相關(guān)的匹配關(guān)鍵詞的個(gè)數(shù)，數(shù)量越大，則該文檔所獲得的分值越大；queryNorm(q)表示當(dāng)前查詢q的方差和，它的結(jié)果不影響當(dāng)前查詢結(jié)果的排序，只是進(jìn)行歸一化處理，用于對(duì)于當(dāng)前查詢語(yǔ)句中的各個(gè)詞設(shè)置適合的權(quán)重，以體現(xiàn)當(dāng)前查詢的中心含義所在；getBoost()方法用于對(duì)不同的對(duì)象設(shè)置權(quán)值，表明其重要程度，其中t.getBoost()用于設(shè)置查詢語(yǔ)句中每個(gè)詞的權(quán)重；d.getBoost()用于在生成索引時(shí)設(shè)置某文檔的權(quán)重；f.getBoost()用于在生成索引時(shí)設(shè)置域的權(quán)重。 queryNorm（q）公式[12]如式（3）。

tf(t in d)表示詞t在當(dāng)前文檔d中出現(xiàn)的頻率 ，idf(t)用于表示詞t在索引中各文檔中出現(xiàn)的頻率,norm(t,d)表示對(duì)于文檔d的歸一化，

式(4)中

它表示一個(gè)域中包含的Term總數(shù)越多，也即文檔越長(zhǎng)，此值越小，文檔越短，此值越大，該項(xiàng)的設(shè)置主要是為了保證篇幅短的文檔不會(huì)因?yàn)槲臋n長(zhǎng)度短的原因而使得其評(píng)分受影響，因?yàn)槠痰奈臋n，其tf值一般情況下要比篇幅長(zhǎng)的文檔小，即查詢?cè)~t在文章中的頻率小，比如，“web”這個(gè)詞在一篇1萬(wàn)個(gè)詞的文檔d1中出現(xiàn)10次，而在一篇100個(gè)詞的文檔d2中出現(xiàn)9次，而按照tf來(lái)衡量的話，必然對(duì)文檔d2不公平，因而lengthNorm正是用一種反比的形式，來(lái)中和這種不公平現(xiàn)象[13]。

然而，如果進(jìn)一步分析Lucene的評(píng)分機(jī)制，可以發(fā)現(xiàn)該機(jī)制過(guò)分注重頁(yè)面與搜索主題的匹配程度，而忽略了頁(yè)面本身的鏈接出入度，即有可能出現(xiàn)這樣的情況：一個(gè)網(wǎng)頁(yè)在某一搜索主題下，是非常重要的頁(yè)面，由它發(fā)出的超鏈接，以及外部指向它的超鏈接數(shù)量很多，但是由于該頁(yè)面中與搜索主題詞的匹配數(shù)量有限，導(dǎo)致在Lucene的評(píng)分機(jī)制下，該頁(yè)面反而不如鏈接出入度小，而與搜索主題詞匹配數(shù)量大的頁(yè)面，明顯有失公平。

3 Lucene框架下結(jié)合PageRank的評(píng)分機(jī)制改進(jìn)

通過(guò)對(duì)比可以發(fā)現(xiàn)，Lucene框架下的評(píng)分算法，剛好可以與PageRank算法形成有效互補(bǔ)，即PageRank算法過(guò)分關(guān)注于鏈接出入度為標(biāo)志的頁(yè)面權(quán)威度，忽略了搜索主題，產(chǎn)生主題漂移現(xiàn)象；Lucene的評(píng)分算法過(guò)分關(guān)注主題匹配，忽略了鏈接出入度。這里，可以考慮以Lucene評(píng)分機(jī)制為主體，結(jié)合PageRank算法，進(jìn)行改進(jìn)。

在第1節(jié)中已經(jīng)描述過(guò)了PageRank的形式化公式，如式(1)所示。這里可將Lucene中評(píng)價(jià)頁(yè)面的權(quán)值表示為 Score（u）引入式（1）并令

可得：

此公式即為結(jié)合PageRank算法的Lucene評(píng)分改進(jìn)公式，其中c為歸一化因子，取值為0.85，PL（u）即為頁(yè)面u關(guān)于查詢主題q的最后權(quán)值得分。

該權(quán)值的求解過(guò)程主要是通過(guò)將Lucene評(píng)分值加入到PageRank的迭代過(guò)程中去，并利用歸一化因子c，得到最后收斂的PL值。這里每個(gè)網(wǎng)頁(yè)的PR初值取為1。

4 校園網(wǎng)平臺(tái)下的算法應(yīng)用測(cè)試

4.1 應(yīng)用測(cè)試平臺(tái)構(gòu)建

算法應(yīng)用測(cè)試平臺(tái)是一個(gè)以采用J2EE架構(gòu)，結(jié)合Lucene開源程序包開發(fā)的校園網(wǎng)搜索引擎，測(cè)試數(shù)據(jù)來(lái)自于網(wǎng)絡(luò)爬蟲程序抓取的某高校校園網(wǎng)內(nèi)的Web數(shù)據(jù)集。平臺(tái)架構(gòu)如圖2所示。

4.2 基于PageRank算法的評(píng)分流程

該系統(tǒng)的評(píng)分流程圖如圖3所示。

圖2 校園網(wǎng)搜索平臺(tái)架構(gòu)

圖3 系統(tǒng)評(píng)分流程圖

4.3 測(cè)試結(jié)果與分析

實(shí)驗(yàn)選擇了8個(gè)特征性比較明顯的二級(jí)學(xué)院網(wǎng)站主頁(yè)作為測(cè)試標(biāo)記，將其名稱上的特征詞作為搜索主題。以學(xué)校內(nèi)的二級(jí)學(xué)院——電子信息科學(xué)學(xué)院為例，其最明顯的特征詞是“電子”。在校園網(wǎng)內(nèi)搜索 “電子”，同時(shí)考慮主題契合度與頁(yè)面權(quán)威度，只要頁(yè)面結(jié)構(gòu)合理，最理想的搜索結(jié)果應(yīng)該是電子信息科學(xué)學(xué)院的網(wǎng)站主頁(yè)（其他二級(jí)學(xué)院的情況以此類推）。

選定測(cè)試標(biāo)記后，通過(guò)系統(tǒng)運(yùn)行產(chǎn)生Lucene評(píng)分機(jī)制下結(jié)合PageRank算法改進(jìn)前后的兩組實(shí)驗(yàn)測(cè)試結(jié)果，結(jié)果如表1～2所示。

測(cè)試均在校園網(wǎng)數(shù)據(jù)環(huán)境下進(jìn)行。每一個(gè)搜索均能保證得到10個(gè)以上的搜索結(jié)果。在Lucene默認(rèn)評(píng)分機(jī)制下，頁(yè)面的評(píng)分值設(shè)為L(zhǎng)，在8個(gè)標(biāo)記網(wǎng)頁(yè)中，能達(dá)到預(yù)期的只有3個(gè)（如表1所示）。分析其原因，在于Lucene過(guò)分注重內(nèi)容的匹配，而未考慮頁(yè)面的出入度。從5個(gè)未達(dá)預(yù)期的搜索結(jié)果來(lái)看，排名第一的頁(yè)面都有一個(gè)共同特點(diǎn)，即這些頁(yè)面中存在著大量的搜索主題詞。像“獎(jiǎng)學(xué)金名單公示”、“論文答辯安排”這類的頁(yè)面中，包含每個(gè)學(xué)生的班級(jí)信息，這些班級(jí)信息里就包含了許多用戶搜索的主題詞，比如“電子信息工程1班”中的“電子”，“金融2班”中的“金融”等。因而在未考慮PageRank的網(wǎng)頁(yè)出入度的情況下，所得到的結(jié)果是不理想的，未能體現(xiàn)出頁(yè)面的重要性。

表1 結(jié)合PageRank算法前系統(tǒng)測(cè)試結(jié)果

表2 結(jié)合PageRank算法后系統(tǒng)測(cè)試結(jié)果

表2中體現(xiàn)的是結(jié)合了PageRank算法后的搜索結(jié)果，通過(guò)分別計(jì)算PR值和L值，利用式（7），得到最終的評(píng)分值PL。從各標(biāo)記網(wǎng)頁(yè)的排序上來(lái)看，搜索結(jié)果了有了很大改觀，基本上達(dá)到了預(yù)期。二級(jí)學(xué)院的主頁(yè)在結(jié)果排序中位列第一位的數(shù)量達(dá)到了6個(gè)，而剩余兩個(gè)未達(dá)到第一的主頁(yè)也排到了第二位，而且在權(quán)值上與第一位的網(wǎng)頁(yè)差距也很微小，作具體分析如下：

（1）電子信息科學(xué)學(xué)院的主頁(yè)在搜索結(jié)果中的排名從原來(lái)的第五上升到第二，但與排名第一的“獎(jiǎng)學(xué)金名單公示”頁(yè)面的主要差距還是在主題詞匹配上，后者的Lucene評(píng)分值高出許多。因而，今后在算法改進(jìn)上，可以進(jìn)一步研究在式(6)中設(shè)置PageRank和Lucene評(píng)分的分值加權(quán)比例的問題，以避免此類問題的出現(xiàn)。

（2）金融學(xué)院的主頁(yè)排名從第四上升到第二，明顯看出PageRank算法在權(quán)威度評(píng)價(jià)中的作用。但是，通過(guò)分析排名第一的金融學(xué)院學(xué)生社團(tuán)主頁(yè)，該頁(yè)面在未結(jié)合PageRank算法前，也未能列在結(jié)果的首位，同樣是PageRank算法的受益者。通過(guò)分析頁(yè)面的PR值可以發(fā)現(xiàn)，該頁(yè)面的鏈接出入度也非常大，而且頁(yè)面中的文字與搜索主題詞“金融”切合得更緊密，也就是說(shuō)，Lucene評(píng)分值仍然起到了很大的作用。從客觀的基于數(shù)據(jù)的評(píng)判角度來(lái)看，這樣的排名順序是完全合理的，也是符合算法改進(jìn)預(yù)期的。同時(shí)，這一結(jié)果也表明金融學(xué)院的網(wǎng)站主頁(yè)的頁(yè)面結(jié)構(gòu)需要進(jìn)一步進(jìn)行搜索引擎優(yōu)化（SEO）改進(jìn)，以提高其有效權(quán)值。

5 結(jié)論

PageRank算法與Lucene評(píng)分機(jī)制之間在主題相關(guān)與頁(yè)面出入度上，存在很大的互補(bǔ)特性。本文描述了一種結(jié)合PageRank算法的Lucene評(píng)分機(jī)制改進(jìn)策略，并通過(guò)在校園網(wǎng)內(nèi)利用Lucene搭建搜索引擎平臺(tái)的方式來(lái)進(jìn)行算法改進(jìn)測(cè)試。從測(cè)試的結(jié)果上來(lái)看，基本達(dá)到了預(yù)期的目標(biāo)，但與理想的結(jié)果仍然存在一定的偏差，后期還需在兩種體系的分值權(quán)重設(shè)置上開展進(jìn)一步的實(shí)際研究。

［1］HAN MIN，ZHANG XIANCHAO.Community identification based on a new approximate personalized page Rank algorithm［J］.Advances in Information Sciences and Service Sciences，2012，20（4）：649－657.

［2］WU HENGLIANG，ZHANG WEIWEI.An improved page ranking algorithm for web search engine［J］.International Journal of Digital Content Technology and Its Applications，2012，13（6）：38－44.

［3］黃德才，戚華春，錢能.基于主題相似度模型的 TS－PageRank 算法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2007（3）：510－514.

［4］王冬，雷景生.一種基于 PageRank 的頁(yè)面排序改進(jìn)算法［J］.微電子學(xué)與計(jì)算機(jī)，2009，26（4）：210－213.

［5］謝月.網(wǎng)頁(yè)排序中PageRank算法和HITS算法的研究［D］.成都：電子科技大學(xué)，2012：18－25.

［6］平衛(wèi)芳.Web數(shù)據(jù)挖掘中PageRank算法的研究與改進(jìn)［D］.上海：華東理工大學(xué)，2014.33－36.

［7］陳再良，凌力，周強(qiáng).dPageRank——一種改進(jìn)的分布式PageRank算法［J］.計(jì)算機(jī)應(yīng)用，2006，26（1）：21－24，36.

［8］潘偉豐，李兵，馬于濤，等.基于加權(quán) PageRank 算法的關(guān)鍵包識(shí)別方法［J］.電子學(xué)報(bào)，2014（11）：2174－2183.

［9］管建和，甘劍峰.基于 Lucene全文檢索引擎的應(yīng)用研究與實(shí)現(xiàn)［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2007（2）：489－491.

［10］李永春，丁華福.Lucene的全文檢索的研究與應(yīng)用［J］.計(jì)算機(jī)技術(shù)與發(fā)展， 2010（2）： 12－15.

［11］張曉濱，石美紅，蔡桂洲.校園網(wǎng)搜索引擎設(shè)計(jì)［J］.西安工程科技學(xué)院學(xué)報(bào)， 2002（3）：243－246.

［12］高玉良.一種基于Lucene的文檔檢索系統(tǒng)的研究及應(yīng)用［D］.大連：大連交通大學(xué)，2012：39－43.

［13］樊同科，謝勇.一種混合搜索算法在智能 Web 中的應(yīng)用［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2013（8）：220－222，226.