基于潛在語義索引的超鏈接分析模型

《基于潛在語義索引的超鏈接分析模型》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、http://www.paper.edu.cn基于潛在語義索引的超鏈接分析模型劉華生，劉剛，呂玉琴北京郵電大學(xué)電子工程學(xué)院，北京(100876)E-mail：liuhuasheng@sohu.com摘要：為了更合理的排名Web文檔本文提出了一個新的鏈接分析模型。該模型結(jié)合了基[1,2]于馬爾科夫鏈的鏈接分析技術(shù)和基于潛在語義索引以及文檔聚類分析的內(nèi)容分析技術(shù)，能很好的適應(yīng)新增Web頁面，并且能用來解決基于鏈接和基于內(nèi)容的搜索引擎作弊以及上下文搜索和主題相關(guān)搜索問題。關(guān)鍵詞：鏈接分析模型；潛在語義索引；搜索

2、引擎中圖分類號：TP1．引言信息檢索理論在搜索引擎中的應(yīng)用并沒有達到預(yù)期的效果，主要是因為以下原因：（1）Web文檔量非常大而用戶輸入的查詢通常是很短的幾個關(guān)鍵詞，因此檢索到的文檔太多以至于很難滿足用戶的需求；（2）Web文檔的質(zhì)量參差不齊并且變化頻繁，有的Web文檔作者為了提升自己網(wǎng)頁在檢索結(jié)果中的位置故意重復(fù)與文檔內(nèi)容無關(guān)但是用戶普遍查詢的關(guān)鍵字，這也就是搜索引擎作弊（spamming）的一個方面。因此僅僅基于關(guān)鍵字的文本檢索技術(shù)不能很好的應(yīng)用于Web搜索。隨著Web鏈接分析技術(shù)的出現(xiàn)情況有所改觀，尤

3、其是PageRank算法給商業(yè)搜索引擎Google帶來巨大的成功更直接說明超鏈接分析技術(shù)能有效地給Web頁面帶來權(quán)威的評價以滿足用戶的信息需求。[3,4]比較成功的鏈接分析算法主要是PageRank和HITS，他們的基本思想都是如果一個頁面被引用的越多說明其價值越高，因此被檢索到的時候應(yīng)該排在前面。自從PageRank算法被提出之后，有很多文章提出了不少的改進方法，而且實驗也表明這些改進算法較之PageRank算法非常有效。尤其是內(nèi)容分析與鏈接分析的結(jié)合，機器學(xué)習(xí)算法在鏈接分析中的應(yīng)用，主題相關(guān)的動態(tài)權(quán)重

4、計算方法等更為有效的改善頁面權(quán)重的準確度和可靠度。本文主要從這些方面出發(fā)提出一種新的頁面質(zhì)量評測模型——基于潛在語義索引的鏈接分析模型。2．PageRank算法和存在的問題[3,4]PageRank鏈接分析算法基于以下事實：（1）鏈接意味著文檔的權(quán)值從源頁面轉(zhuǎn)移到目的頁面，因此如果一個頁面被很多頁面鏈接則其權(quán)重就很高；（2）如果一個頁面有很高的權(quán)重，則被它鏈接的頁面相應(yīng)的權(quán)重也應(yīng)該很高；（3）一個頁面有很多指向其它頁面的鏈接，該頁面的權(quán)重應(yīng)該被這些北至想的頁面所共享。如果O表示指向頁面i的鏈接數(shù)，(i,)

5、jE?表示頁面j有指向頁面i的鏈接，pi()表j示頁面i的PageRank權(quán)值，則可表示為：pj()pi()=?（1）(i,)jE?Oj可以用矩陣形式來表示所有頁面的權(quán)值，假設(shè)共有n個頁面，n維列向量P表示所有頁T面的權(quán)值，即P=(p(1),p(2),...,pn())，-1-http://www.paper.edu.cn矩陣A表示頁面間歸一化的鄰接矩陣：ì1?,ifi(,)jE?Aij=íOi（2）??0,if(i,)jE?T則整個系統(tǒng)可表示為：P=AP。該公式是循環(huán)定義的，因此可以用迭代的辦法求解。但

6、這里有幾個問題，首先Web的有向圖表示并不一定是連同的，其次有很多的頁面沒有向外的鏈接，因此矩陣A中有很多行值是全零。為了使其適應(yīng)Web隨機沖浪模型，做出了如下的修改：ETP=((1-+d))dAP（3）n1其中，E為全1的n維方陣，表示頁面間隨機跳轉(zhuǎn)的概率，d為衰減因子取值在0和1之n間，即d?[0,1]，經(jīng)驗值為d=0.85。矩陣的求解可以用迭代的方式求解：PageRank-Iterate(G)P?en/0k?1RepeatTP?(1)-+dedAPk1k-kk?+1Until

7、

8、PP-<

9、

10、ekk-

11、1ReturnPk從增強的PageRank計算公式可以看出，方陣E為全1矩陣，意味著所有頁面之間的跳轉(zhuǎn)是完全隨機的，這與事實不符，實際上網(wǎng)上沖浪者在獲取信息時更關(guān)注內(nèi)容相關(guān)的頁面，因此等概率模型不準確。另外，矩陣A中每一行表示所有被鏈接的頁面共享原頁面的所有權(quán)重分值，并且也是均分，這也是不合理的。本文主要從這兩方面改進PageRank算法，提出基于內(nèi)容的潛在語義索引的鏈接分析模型，該模型的主要思想仍然是社會網(wǎng)絡(luò)分析的應(yīng)用。3．基于內(nèi)容的鏈接分析模型T根據(jù)馬爾科夫鏈模型P=AP，A表示從狀態(tài)i跳轉(zhuǎn)到狀態(tài)j的

12、概率，可以得到描kk-1ij述頁面之間鏈接關(guān)系的模型：TP=((1-+d))EdAP（4）kk-1TP=(p,pp,...,)表示在狀態(tài)k時所有頁面的權(quán)重，n表示頁面集合的大小，矩陣A中kk12kkn的元素A表示頁面i和頁面j間的鏈接關(guān)系。避免沒有向外的鏈接的頁面影響隨機矩陣A，ij1對A進行特殊處理，如果頁面i沒有向外的鏈接，則有A=。為了使P能收斂，結(jié)合ijijkn-2-http://www.paper.edu.cnWeb