熊才權(quán) 田浩

湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院 湖北 430068

0 引言

在Google模式中，PageRank值的計(jì)算和向量空間模型的計(jì)算是相互獨(dú)立的，在向量空間模型的計(jì)算中也沒(méi)有考慮到 PageRank值本身所包含的信息含義。本文在計(jì)算文本相似度時(shí)結(jié)合 PageRank值所包含的信息提出在計(jì)算文本相似度時(shí)先以 PageRank值的大小作為特征選擇的條件，然后在VSM模型中考慮類別信息以提高檢索的質(zhì)量。

1 基于PageRank值的VSM改進(jìn)模型

對(duì)文本進(jìn)行分類是一個(gè)比較復(fù)雜的問(wèn)題，文本自動(dòng)分類是信息檢索與數(shù)據(jù)挖掘領(lǐng)域的研究熱點(diǎn)與核心技術(shù)，而基于機(jī)器學(xué)習(xí)的文本分類技術(shù)的相關(guān)研究已經(jīng)取得較大進(jìn)展。本文首先簡(jiǎn)單的把具有相同 PageRank值的網(wǎng)頁(yè)歸為同一類，然后在計(jì)算相似度的過(guò)程中考慮這種分類的影響，并區(qū)分不同類別間的信息差異，最終得到更為有效的檢索結(jié)果。如果把具有相同 PageRank值的網(wǎng)頁(yè)歸為同一類，就可以把所有網(wǎng)頁(yè)文本根據(jù)其重要性簡(jiǎn)單劃分為11種類別。在下載系統(tǒng)中對(duì)網(wǎng)絡(luò)爬蟲(chóng)添加部分代碼使其根據(jù) PageRank值的大小對(duì)網(wǎng)頁(yè)分類存儲(chǔ)可以簡(jiǎn)單實(shí)現(xiàn)這種初步的分類。

1.1 詞頻的統(tǒng)計(jì)方法

在文本分類中詞頻一般是基于自然語(yǔ)言的，經(jīng)過(guò)文本分類后得到的詞條可以認(rèn)為是計(jì)算機(jī)可識(shí)別的機(jī)器語(yǔ)言，在真實(shí)生活中使用頻率高的詞條可能在機(jī)器語(yǔ)言中使用率并不高。在考慮文本分類的同時(shí)為了保證相似度計(jì)算的一致性，可以對(duì)機(jī)器語(yǔ)言的文本頻率進(jìn)行統(tǒng)計(jì)以在文本相似度計(jì)算中使用。

詞條頻率的統(tǒng)計(jì)過(guò)程如下：

（1）對(duì)所有分類后的頁(yè)面提取特征詞；

（2）統(tǒng)計(jì)各個(gè)類別Ci的文本總數(shù)Mi和包含詞條t的文檔數(shù)mi；

（3）計(jì)算詞條t在各個(gè)類別的各個(gè)文本中的詞頻，公式如下：

在詞條頻率的統(tǒng)計(jì)過(guò)程中首先需要提取特征詞，特征詞的提取與用戶可能的檢索詞是相關(guān)的。例如“搜索引擎”、“天安門”等都可能是用戶潛在的檢索詞，所以必須做為特征詞進(jìn)行統(tǒng)計(jì)。本文提供了包含 1370個(gè)檢索內(nèi)容的檢索庫(kù)，所有檢索庫(kù)中的詞都作為特征詞進(jìn)行統(tǒng)計(jì)。然而，在搜索引擎中進(jìn)行的每一次檢索都對(duì)詞條進(jìn)行一次頻率統(tǒng)計(jì)是不現(xiàn)實(shí)的，即使根據(jù)本文所提供的檢索庫(kù)所得到的最終統(tǒng)計(jì)結(jié)果也是不全面的。但是，由 PageRank算法可知，網(wǎng)頁(yè)的連接是基于詞條的，所以詞條頻率的變化與 PageRank值的傳遞具有一致性，在 PageRank值更新的時(shí)期內(nèi)，基于網(wǎng)絡(luò)的詞條頻率可認(rèn)為保持不變?？梢栽谟?jì)算 PageRank值的同時(shí)進(jìn)行詞條頻率的統(tǒng)計(jì)計(jì)算，也可以改進(jìn) PageRank算法，利用PageRank算法計(jì)算出詞條頻率。

1.2 改進(jìn)的IDF方法

一個(gè)詞條如果在一個(gè)類別的文檔中頻率較高，則說(shuō)明該詞條能夠很好的代表這個(gè)類別的文本特征，這樣的詞條應(yīng)該給它們賦予較高的權(quán)重，并選來(lái)作為該類文本的特征詞以區(qū)別其它類文檔。例如，計(jì)算機(jī)類的文本中“CPU”會(huì)出現(xiàn)在許多文檔中，“CPU”應(yīng)該選來(lái)作為計(jì)算機(jī)類文本的特征詞以區(qū)別其它類文檔。

根據(jù)上述原理提出改進(jìn)的IDF方法如下：

設(shè)總的文檔數(shù)為 N，包含詞條t的文檔數(shù)為 n，其中某一類Ci中包含詞條t的文檔數(shù)為mi，除Ci類外，包含詞條t的文檔數(shù)為k，則t在Ci類中的IDFi值為：

顯然，IDFi隨mi增大而增大，隨k增大而減小。如果在某一類Ci中包含詞條t的文檔數(shù)量大，而在其它類中包含詞條t的文檔數(shù)量小的話，則t能夠代表Ci類的文本的特征，具有很好的類別區(qū)分能力。

1.3 改進(jìn)的VSM模型

綜上所述，在對(duì)搜索引擎中文本相似度計(jì)算的方法和過(guò)程進(jìn)行改進(jìn)后提出“基于PageRank值的VSM改進(jìn)模型”，其文本相似度的計(jì)算過(guò)程如下：

（1）對(duì)所有下載的頁(yè)面根據(jù)PageRank值的大小進(jìn)行分類，并統(tǒng)計(jì)特征詞條在各個(gè)類別中的詞頻TFi；

（2）由改進(jìn)的IDF方法計(jì)算詞條在各個(gè)類別中的IDFi；

（3）計(jì)算該特征項(xiàng)t在文本d中的重要程度Wt,d；

（4）計(jì)算文本d和查詢式q的相似度sim(q，d)；其公式如下：

（5）根據(jù)相似度的大小生成相似度排序列表。其中，具有相同相似度的頁(yè)面PageRank值大的排在前面。

為了驗(yàn)證改進(jìn)后的效果，需對(duì)原模型和改進(jìn)后的模型所生成的結(jié)果進(jìn)行比較。假設(shè)：由原模型(VSM)得到的排序?yàn)椋簕A1，A2，……，An}；由改進(jìn)后的模型(BPVSM)得到的排序?yàn)椋簕B1，B2，……，Bn}。

定義1：相關(guān)：若檢索結(jié)果頁(yè)面Ai或Bi中包含檢索信息則Ai或Bi相關(guān)，否則Ai或Bi不相關(guān)。

定義2：異點(diǎn)：在兩次排序中若Ai≠Bi則Ai和Bi為異點(diǎn)。

定義 3：優(yōu)異點(diǎn)：在兩次排序中?Ai≠Bi，若 Ai相關(guān)而B(niǎo)i不相關(guān)則Ai為優(yōu)異點(diǎn)，若Bi相關(guān)而Ai不相關(guān)則Bi為優(yōu)異點(diǎn)；在兩次排序中?Ai=Bj，若i>j則Ai為優(yōu)異點(diǎn)，若i＜j則Bj為優(yōu)異點(diǎn)。

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

網(wǎng)絡(luò)上的數(shù)據(jù)是極其巨大的，對(duì)所有網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行完備的實(shí)驗(yàn)分析是困難的。整個(gè)互連網(wǎng)是由一個(gè)個(gè)網(wǎng)絡(luò)構(gòu)成的，其中任意一個(gè)網(wǎng)絡(luò)都可以認(rèn)為是一個(gè)較小的互連網(wǎng)。例如：分別對(duì)中國(guó)教育網(wǎng)和對(duì)中國(guó)電信網(wǎng)進(jìn)行實(shí)驗(yàn)所得到的結(jié)果幾乎沒(méi)有區(qū)別。所以，適當(dāng)縮小實(shí)驗(yàn)范圍不會(huì)影響最終的實(shí)驗(yàn)結(jié)果。在本實(shí)驗(yàn)中，限制網(wǎng)絡(luò)蜘蛛的爬取范圍是在中國(guó)教育網(wǎng)內(nèi)(即網(wǎng)址后部分為.edu.cn)。但是即使僅對(duì)中國(guó)教育網(wǎng)進(jìn)行全面的分析計(jì)算也是一個(gè)巨大的工程，為了證明改進(jìn)后的算法對(duì)檢索結(jié)果的影響可進(jìn)行驗(yàn)證性實(shí)驗(yàn)，其過(guò)程如下：

首先，精選檢索內(nèi)容，生成包含了 1370個(gè)檢索條目的檢索內(nèi)容庫(kù)，然后分別在Google中檢索，并用網(wǎng)絡(luò)蜘蛛爬取檢索結(jié)果頁(yè)面。

其次，根據(jù)改進(jìn)后的模型對(duì)檢索結(jié)果進(jìn)行再排序。由于在搜索引擎中一個(gè)頁(yè)面顯示 10個(gè)結(jié)果，而用戶一般難以容忍翻看到 10以后的結(jié)果，所以盡量避免對(duì)后面的結(jié)果頁(yè)面進(jìn)行分析計(jì)算。在實(shí)驗(yàn)中，只對(duì)結(jié)果頁(yè)面的前1/3進(jìn)行了分析計(jì)算(檢索結(jié)果少于 300則全部進(jìn)行分析計(jì)算)，最終只顯示前10個(gè)頁(yè)面的排序。

最后，分別統(tǒng)計(jì)兩次排序前十個(gè)頁(yè)中所包含的相關(guān)頁(yè)面的數(shù)目，比較兩次排序的相關(guān)性；分別統(tǒng)計(jì)兩次排序的優(yōu)異點(diǎn)，比較兩次排序的優(yōu)異性；并用 MATLAB對(duì)統(tǒng)計(jì)結(jié)果進(jìn)行模擬得到仿真圖。

在實(shí)驗(yàn)中，檢索內(nèi)容庫(kù)主要分為復(fù)雜檢索和簡(jiǎn)單檢索，復(fù)雜檢索為可以確定具體結(jié)果的檢索，例如檢索內(nèi)容為“毛澤東 開(kāi)國(guó)典禮 語(yǔ)錄”為復(fù)雜檢索，而“毛澤東 語(yǔ)錄”為簡(jiǎn)單檢索。同時(shí)考慮到部分新詞如“綠領(lǐng)”并未被詞典收錄，檢索內(nèi)容庫(kù)具有 37條包含新詞的檢索如“綠領(lǐng) 含義”。檢索內(nèi)容庫(kù)概要見(jiàn)表1。

表1 檢索內(nèi)容庫(kù)

經(jīng)過(guò)對(duì)實(shí)驗(yàn)數(shù)據(jù)統(tǒng)計(jì)分析發(fā)現(xiàn)改進(jìn)后的模型在提高檢索的準(zhǔn)確率上比原模型更加有效，在對(duì)包含新詞的檢索中貢獻(xiàn)更加明顯。最終統(tǒng)計(jì)結(jié)果見(jiàn)表2。

表2 兩次排序的效率比較

對(duì) 1370次排序的相關(guān)性進(jìn)行模擬，發(fā)現(xiàn)兩條相關(guān)性曲線相互交織在一起，其中BPVSM的大部分略高于VSM；見(jiàn)圖 1(縱坐標(biāo)表示相關(guān)頁(yè)面的數(shù)目，橫坐標(biāo)表示按照相關(guān)頁(yè)面的數(shù)目的大小排列的1370次統(tǒng)計(jì))。

圖1 相關(guān)性統(tǒng)計(jì)圖

對(duì)相關(guān)數(shù)(其范圍為0-100)進(jìn)行逆向統(tǒng)計(jì)的模擬，發(fā)現(xiàn)兩條曲線在11%和20%左右有較大的起伏；BPVSM在11%和20%有兩次波峰，而VSM僅在20%有一次波峰。見(jiàn)圖2(橫坐標(biāo)為頁(yè)面相關(guān)數(shù)，縱坐標(biāo)表示具有某個(gè)相關(guān)數(shù)的統(tǒng)計(jì)次數(shù))。

圖2 相關(guān)性逆向統(tǒng)計(jì)圖

對(duì)1370次排序的優(yōu)異點(diǎn)統(tǒng)計(jì)進(jìn)行模擬，發(fā)現(xiàn)VSM曲線有少量的奇異點(diǎn)落在BPVSM曲線的上方，忽略少量的奇異點(diǎn)后可認(rèn)為BPVSM曲線在VSM曲線的上方。見(jiàn)圖 3(縱坐標(biāo)表示優(yōu)異點(diǎn)數(shù)目，橫坐標(biāo)為按照優(yōu)異點(diǎn)數(shù)目排序的 1370次統(tǒng)計(jì))。

圖3 優(yōu)異點(diǎn)統(tǒng)計(jì)圖

綜上所述，實(shí)驗(yàn)結(jié)果表明：

（1）兩種模型檢索結(jié)果的查準(zhǔn)率比較接近，但改進(jìn)后的模型查準(zhǔn)率更高；

（2）兩次排序的查準(zhǔn)率在7%-35%之間，在11%和20%左右達(dá)到最大概率；

（3）改進(jìn)后的模型可以明顯提高對(duì)新詞的查準(zhǔn)率；

（4）改進(jìn)后的模型對(duì)前 100個(gè)網(wǎng)頁(yè)的可信度提高了約1.45174倍。

3 結(jié)束語(yǔ)

相似度的計(jì)算與排序是搜索引擎的一個(gè)重要部分，提高相似度的計(jì)算與排序的效率和質(zhì)量對(duì)提高整個(gè)搜索引擎的質(zhì)量具有重大的意義。本文基于搜索引擎的文本檢索部分提出了基于 PageRank值的文本相似度改進(jìn)模型，通過(guò)模擬實(shí)驗(yàn)表明改進(jìn)后的模型可以提高檢索的準(zhǔn)確率，在對(duì)新詞的檢索中更加明顯。

基于 PageRank值統(tǒng)計(jì)詞頻，詞頻的統(tǒng)計(jì)必須保持與PageRank值的更新同步，這必然會(huì)增加整個(gè)搜索引擎的工作量；其次，改進(jìn)后的模型依然存在奇異點(diǎn)(即完全不相關(guān)的頁(yè)面卻獲得了很高的相似度)，若在改進(jìn)后的模型中考慮消去產(chǎn)生奇異點(diǎn)的原因可以提高模型的穩(wěn)定性。

[1] PAGE.L,BRIN.S.The anatomy of a large scalehyper textual Web search engine [J].Computer Networks and ISDN Systems.1998.

[2] PAGE.L,BRIN.S,MOTWAN.R.WINOGRAD.T. The PageRank citation Ranking:Bringing Order to the Web[J]. Stanford Digital Library Technologies Project.1998.

[3] MATTEW.R,PEDRO.D.The intelligent surfer: Probabilistic combination of link and content information in PageRank[J].Neural Information Processing Systems.2002.

[4] SALTON G,WONG A,YANG C.A Vector SpaceModel for Automatic Indexing[J]. Comm-unications of ACM.1975.

[5] YANG Y.An Evaluation of Statistical Approaches to Text Categorization[J].Information Retrieval.1999.

[6] 梁斌.走進(jìn)搜索引擎[M].北京:電子工業(yè)出版社.2007.

[7] 蘇金樹(shù),張博鋒,徐昕.基于機(jī)器學(xué)習(xí)的文本分類技術(shù)研究進(jìn)展軟件學(xué)報(bào)[J].2006.