信息檢索之HITS算法

1、-1- 、實驗目的 理解搜索引擎的鏈接結(jié)構(gòu)子系統(tǒng)的基本功能； 了解萬維網(wǎng)鏈接的結(jié)構(gòu)圖及特性； 理解HITS算法的基本思想和原理。 二、實驗原理及基本技術路線圖（方框原理圖） 萬維網(wǎng)的鏈接結(jié)構(gòu)通常使用有向圖的方式來描述， 在萬維網(wǎng)鏈接結(jié)構(gòu)圖中，網(wǎng)頁是圖的節(jié)點; 而超鏈接則是鏈接節(jié)點的有向邊（從源網(wǎng)頁指向目的網(wǎng)頁） 。每一條從源網(wǎng)頁指向目的網(wǎng)頁的超 鏈接，既稱為源網(wǎng)頁的“出鏈接” ，乂稱為目的網(wǎng)頁的“入鏈接”。用圖表示萬維網(wǎng)鏈接結(jié)構(gòu)，如 下圖： 關丁萬維網(wǎng)結(jié)構(gòu)圖的規(guī)模很難給出一個準確的統(tǒng)計結(jié)果， 這是因為：圖中的節(jié)點存在形式紛 繁復雜，即使不考慮網(wǎng)頁的可訪問性問題（部分網(wǎng)頁會對用戶訪問加以限制，如

2、采取登錄策略等）， 只考慮能夠被自由訪問的網(wǎng)頁，這些網(wǎng)頁中既有以傳統(tǒng)形式存在的靜態(tài)頁面， 乂有隨用戶查詢要 求在服務器端實時生成的動態(tài)頁面，甚至還有用 AJAX技術生成的URL相同但頁面內(nèi)容千差萬 別的頁面。而超鏈接的界定在當前的網(wǎng)絡環(huán)境下也存在諸多困難。 2008年7月，谷歌在其官方 博客上聲稱其索引量達到1萬億網(wǎng)頁，這一估計一定程序上反映了圖的節(jié)點集合規(guī)模。 鏈接結(jié)構(gòu)信息是網(wǎng)絡信息環(huán)境與傳統(tǒng)信息媒介的最大區(qū)別之一。 對丁搜索引擎而言，與用戶 查詢需求乃至頁面內(nèi)容均相對獨立的超鏈接結(jié)構(gòu)是用以評價萬維網(wǎng)數(shù)據(jù)質(zhì)量的重要依據(jù)。 在2001年SIGIR會議上，Craswell等人對鏈接結(jié)構(gòu)分析算法的

3、應用方式進行了分析，提出 萬維網(wǎng)超鏈接應具有的兩個特性： -2- 如果存在超鏈接L從頁面Psource指向頁面Pdestiny,則Psource與Pdestiny W足： 特性1：（內(nèi)容推薦特性）頁面Psource的作者推薦頁面Pdestiny的內(nèi)容，且利用L的鏈接文本內(nèi) 容對Pdestiny進行描述。 特性2：（主題相關特性）被超鏈接連接的兩個頁面Psource與P destiny的頁面內(nèi)容涉及類似的主 題。 然而這兩個特性對于萬維網(wǎng)數(shù)據(jù)爆炸性增長的背景下被認為過于理想主義。 萬維網(wǎng)節(jié)點之間 的超鏈接關系遠比特性1和特性2描述的情況要復雜的多。但是，一方面，經(jīng)過改進的鏈接分析 算法還是可以為

4、頁面質(zhì)量評估提供參考； 另一方面，在經(jīng)過數(shù)據(jù)活理之后的近似理想的網(wǎng)絡環(huán)境 中，它們還是可以發(fā)揮其挑選高質(zhì)量網(wǎng)頁的作用，因此鏈接分析算法仍舊是當前研究的熱點之一。 HITS算法是由Jon Kleinberg在20世紀90年代提出的一種鏈接分析算法。 HITS算法是 Hyperlink-Induced Topic Search基于超鏈接推演的主題搜索算法）的簡稱，它的核心思想是對 網(wǎng)頁如下兩個方面的權(quán)威程度進行評價。首先，內(nèi)容權(quán)威度（ Authority Value）,即網(wǎng)頁本身內(nèi)容 的受歡迎程序；其次，鏈接權(quán)威度（Hub Value）,即網(wǎng)頁鏈接到其他受歡迎資源的程度。 HITS算法的實施包括兩

5、個階段，對用戶輸入的查詢主題而言，首先是通過文本搜索過程獲 取與此查詢主題內(nèi)容相關的網(wǎng)頁集合，并適當擴充該網(wǎng)頁集合，以包括盡可能多的結(jié)果候選網(wǎng)頁， 同時使用結(jié)果集合網(wǎng)頁問的鏈接結(jié)構(gòu)關系更加完整； 隨后則是通過一個“迭代一收斂”的過程計 算網(wǎng)頁集合中每個頁面對應的鏈接權(quán)威度和內(nèi)容權(quán)威度數(shù)值。 算法最后輸出的是分別按照鏈接權(quán) 威度與內(nèi)容權(quán)威度排序的結(jié)果列表，用戶可以根據(jù)需求不同，選擇其中的結(jié)果頁面進行瀏覽。-3- HITS ( HyperlinkHITS ( Hyperlink- -Induced T opic Search)Induced T opic Search)算法 (1) 選取網(wǎng)絡信息檢

6、索系統(tǒng)的結(jié)果集合 R 將R, R所指向的網(wǎng)頁和指向 R的網(wǎng)頁構(gòu)成的鏈接結(jié)構(gòu)圖稱為 G。 對于G中每一個節(jié)點n,設H(n)和A(n)分別是其鏈接權(quán)威度和內(nèi)容權(quán)威度，向量 H和A分別為G的鏈接 權(quán)威度和內(nèi)容權(quán)威度結(jié)果向量。 (2) 設定H = A=(1, 1, - , 1),即：對G中每一個節(jié)點n,設定其初始值 H(0)(n)和A(0)(n)均為1. (3) For k=1,2, 3,，N 對G中每一個節(jié)點n, A(k)(n)， H (k)m )(稱為 I 操作) 對G中每一個節(jié)點n, H (n)A(k)(mi)(稱為 O 操作) 將 H(0)(n)和 A(0)(n)(n G)作規(guī)范化處理，使A(

7、k) n) 2冒 1 , W ( H (k) n)2 且1。 n 二G n G (4)當結(jié)果向量H和A未收斂時，返回(3)；當H和A收斂時，輸出算法所計算出的 G中每一個節(jié)點 n 的 H(0)(n)和 A(0)(n)的結(jié)果。 三、所用儀器、材料(設備名稱、型號、規(guī)格等) 硬件：PC機一臺 操作系統(tǒng)：Windows 7 編程語言：Java IDE: eclipse 3.5.2 四、 實驗方法、步驟 實現(xiàn)HITS算法的主要功能模塊，并可對測試數(shù)據(jù)計算所需要內(nèi)容權(quán)威度和鏈接權(quán)威度的 值。要求能夠輸出每次迭代過程的詳細信息。 五、 實驗過程原始記錄(數(shù)據(jù)、圖表、計算等) 本次實驗中沒有實現(xiàn)HITS算法

8、中要求的Web圖的擴展功能，而是將圖的結(jié)點和邊的信息存 儲在文件中，由程序讀入并計算各自內(nèi)容權(quán)威度和鏈接權(quán)威度， 并能夠指定最大迭代次數(shù)和輸出 迭代過程的詳細信息。 Web圖的構(gòu)造過程的主要代碼: /* * Web圖類的構(gòu)造方法 -4- *參數(shù)文件中每一行存儲一條邊的信息 *該方法將掃描文件中的每一行，將所有的邊及結(jié)點信息讀入并構(gòu)造整個圖 * 注：程序設計思想?yún)⒖?http:/ * * param file 存儲了圖中邊及結(jié)點信息的文件 * throws lOException */ public WebGraph(File file) throws lOException ( this ()

9、; / 初始化相關變量 BufferedReader reader = new BufferedReader( new FileReader(file); String line; int urllndex = 0; /讀入文件，解析并存儲結(jié)點及邊的信息 while (line = reader.readLine() != null ) ( int index = line.indexOf( -); if (index 0) ( String urlFrom = line.substring(0, index).trim(); String urlTo = line.substring(ind

10、ex + 2).trim(); int urllndexFrom = -1; int urllndexTo = -1; / 存儲URL到lD的映射 if ( urlTold .containsKey(urlFrom) ( urllndexFrom = urlTold .get(urlFrom); ) else ( idToURL .put(urllndex, urlFrom.trim(); urlTold .put(urlFrom.trim(), urllndex); urllndex+; urllndexFrom = urlTold .get(urlFrom); ) / 存儲lD到URL的映

11、射 if ( urlTold .containsKey(urlTo) ( urllndexTo = urlTold .get(urlTo); ) else ( idToURL .put(urllndex, urlTo.trim(); urlTold .put(urlTo.trim(), urllndex); urllndex+; urllndexTo = urlTold .get(urlTo); ) / 存儲邊 Map tedge = new HashMap(); tedge.put(urllndexFrom, urllndexTo); edge .add(tedge.entrySet().i

12、terator().next(); ) ) this . nodeCount = idToURL .size(); / 結(jié)點數(shù)量 / 填充邊到對應的鄰接矩陣 this . matrix = new int nodeCount nodeCount ; for ( int i = 0; i edge .size(); i+) ( Entry entry = edge .get(i); ,格式如下：url1 - url2 -5- int from = entry.getKey(); int to = entry.getValue(); matrix fromto = 1; ) ) HITS算法內(nèi)容權(quán)

13、威度和鏈接權(quán)威度的計算: /* * HITS 類構(gòu)造方法 * param webGraph web 圖 */ public HITS(WebGraph webGraph) ( this . webGraph = webGraph; this . authorityScores = new HashMap(); this . hubScores = new HashMap(); this . nodeCount = webGraph.getNodeCount(); /初始的內(nèi)容權(quán)威度和鏈接權(quán)威度均設為 1 for ( int i = 0; i webGraph.getNodeCount(); i

14、+) ( this . authorityScores .put(i, 1.0); this . hubScores .put(i, 1.0); ) /計算結(jié)點的內(nèi)容權(quán)威度和鏈接權(quán)威度 ，指定最大迭代次數(shù)為 25 computeHITS(25); ) *計算結(jié)點的內(nèi)容權(quán)威度和鏈接權(quán)威度 * param numIterations 最大迭代次數(shù) */ private void computeHITS( int numIterations) ( / 迭代次數(shù) int iterNum = numIterations; / 上一次迭代的內(nèi)容權(quán)威度和鏈接權(quán)威度 ,初始值均設為0 Map preAutho

15、rityScore = new HashMap(); Map preHubScore = new HashMap(); for ( int i = 0; i 0 & !isConvergence(preAuthorityScore, authorityScores preHubScore, hubScores ) ( /存儲計算所得的內(nèi)容權(quán)威度和鏈接權(quán)威度值 ，用于下次迭代之前的收斂判斷 copyAtoB( authorityScores , preAuthorityScore);-6- WebGraph webGraphHITS = new WebGraph(fileHITS); S

16、ystem. out .println( HITS 算法示例：); System. out .println( nweb 圖所對應的矩陣:); webGraphHITS.printMatrix(); System. out .println( nHITS 算法的執(zhí)行過程:); hits = new HITS(webGraphHITS); copyAtoB( hubScores ,preHubScore); System. out .println( 第+ (iterNum - numIterations) + for ( int i = 0; i nodeCount ; i+) List in

17、Links = webGraph .getInLinks(i); / 入鏈接集 double authorityScore = 0; / 內(nèi)容權(quán)威度 for (Integer in : inLinks) /內(nèi)容權(quán)威度等于所有入鏈接的鏈接權(quán)威度之和 authorityScore += hubScores .get(in).doubleValue(); authorityScores .put(i, authorityScore); for ( int i = 0; i nodeCount ; i+) List outLinks = webGraph .getOutLinks(i); / 出鏈接集

18、 double hubScore = 0; / 鏈接權(quán)威度 for (Integer out : outLinks) /鏈接權(quán)威度等于所有出鏈接的內(nèi)容權(quán)威度之和 hubScore += authorityScores .get(out).doubleValue(); hubScores .put(i, hubScore); /歸一化(使用最大值) double aMax = getMaxValue( authorityScores ); double hMax = getMaxValue( hubScores ); for ( int i = 0; i 2A - 戲 5B 6C 測試數(shù)據(jù)以上圖

19、（左）為例，將結(jié)點和邊信息存入文件 hits.txt，如上圖（右），將輸入設為 文件hits.txt,然后運行以上測試程序，得運行結(jié)果如下: HITSW法示例：法示例： s*s*圖圖所對應所對應的鄰接拒陣的鄰接拒陣: : ABC A 1 1 1 B 1 0 1 C 0 1 0 HITSM法的執(zhí)行過程法的執(zhí)行過程: : 第。次迭代第。次迭代： aA = 1.0 aB = 0.732 ac = 1.0 hA = 1.0 hB = 0.732 hc = 0.2679 六、實驗結(jié)果分析、經(jīng)驗總結(jié)或結(jié)論（例如對實驗獲取數(shù)據(jù)的誤差分析、數(shù)據(jù)處理、成果 等。其中，繪制曲線圖時必須用標準計算紙，不得隨意用普通白紙繪畫） 通過本次實驗我們理解了 HIT S算法的基本思想和方法，并編程實現(xiàn)了一個簡單的HITS 算法的程序，對鏈接結(jié)構(gòu)分析子系統(tǒng)的作用和功能有了一個較為直觀的認識。另外，這里 所得的鏈接結(jié)構(gòu)分析結(jié)果，可A(A =1.0 AB：=1.0 AC=1.0 第第1次次迭代：迭代： AA=1.0 AC-1.0 第第2次次迭代：迭代： AA=1.0 AC =1.0 第第3次次迭代：迭代： AA=1.0 AB-0.7S AC=1.0 第第9次次迭代：迭代： AA=i.a AE=0.73S 第第5次