信息檢索之HITS算法

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

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

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

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

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

6、索系統(tǒng)的結(jié)果集合 R 將R, R所指向的網(wǎng)頁(yè)和指向 R的網(wǎng)頁(yè)構(gòu)成的鏈接結(jié)構(gòu)圖稱為 G。 對(duì)于G中每一個(gè)節(jié)點(diǎn)n,設(shè)H(n)和A(n)分別是其鏈接權(quán)威度和內(nèi)容權(quán)威度，向量 H和A分別為G的鏈接 權(quán)威度和內(nèi)容權(quán)威度結(jié)果向量。 (2) 設(shè)定H = A=(1, 1, - , 1),即：對(duì)G中每一個(gè)節(jié)點(diǎn)n,設(shè)定其初始值 H(0)(n)和A(0)(n)均為1. (3) For k=1,2, 3,，N 對(duì)G中每一個(gè)節(jié)點(diǎn)n, A(k)(n)， H (k)m )(稱為 I 操作) 對(duì)G中每一個(gè)節(jié)點(diǎn)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)當(dāng)結(jié)果向量H和A未收斂時(shí)，返回(3)；當(dāng)H和A收斂時(shí)，輸出算法所計(jì)算出的 G中每一個(gè)節(jié)點(diǎn) n 的 H(0)(n)和 A(0)(n)的結(jié)果。 三、所用儀器、材料(設(shè)備名稱、型號(hào)、規(guī)格等) 硬件：PC機(jī)一臺(tái) 操作系統(tǒng)：Windows 7 編程語言：Java IDE: eclipse 3.5.2 四、 實(shí)驗(yàn)方法、步驟 實(shí)現(xiàn)HITS算法的主要功能模塊，并可對(duì)測(cè)試數(shù)據(jù)計(jì)算所需要內(nèi)容權(quán)威度和鏈接權(quán)威度的 值。要求能夠輸出每次迭代過程的詳細(xì)信息。 五、 實(shí)驗(yàn)過程原始記錄(數(shù)據(jù)、圖表、計(jì)算等) 本次實(shí)驗(yàn)中沒有實(shí)現(xiàn)HITS算法

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

9、; / 初始化相關(guān)變量 BufferedReader reader = new BufferedReader( new FileReader(file); String line; int urllndex = 0; /讀入文件，解析并存儲(chǔ)結(jié)點(diǎn)及邊的信息 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; / 存儲(chǔ)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); ) / 存儲(chǔ)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); ) / 存儲(chǔ)邊 Map tedge = new HashMap(); tedge.put(urllndexFrom, urllndexTo); edge .add(tedge.entrySet().i

12、terator().next(); ) ) this . nodeCount = idToURL .size(); / 結(jié)點(diǎn)數(shù)量 / 填充邊到對(duì)應(yīng)的鄰接矩陣 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)威度的計(jì)算: /* * 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)威度均設(shè)為 1 for ( int i = 0; i webGraph.getNodeCount(); i

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

15、rityScore = new HashMap(); Map preHubScore = new HashMap(); for ( int i = 0; i 0 & !isConvergence(preAuthorityScore, authorityScores preHubScore, hubScores ) ( /存儲(chǔ)計(jì)算所得的內(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 圖所對(duì)應(yīng)的矩陣:); 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 測(cè)試數(shù)據(jù)以上圖

19、（左）為例，將結(jié)點(diǎn)和邊信息存入文件 hits.txt，如上圖（右），將輸入設(shè)為 文件hits.txt,然后運(yùn)行以上測(cè)試程序，得運(yùn)行結(jié)果如下: HITSW法示例：法示例： s*s*圖圖所對(duì)應(yīng)所對(duì)應(yīng)的鄰接拒陣的鄰接拒陣: : 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 六、實(shí)驗(yàn)結(jié)果分析、經(jīng)驗(yàn)總結(jié)或結(jié)論（例如對(duì)實(shí)驗(yàn)獲取數(shù)據(jù)的誤差分析、數(shù)據(jù)處理、成果 等。其中，繪制曲線圖時(shí)必須用標(biāo)準(zhǔn)計(jì)算紙，不得隨意用普通白紙繪畫） 通過本次實(shí)驗(yàn)我們理解了 HIT S算法的基本思想和方法，并編程實(shí)現(xiàn)了一個(gè)簡(jiǎn)單的HITS 算法的程序，對(duì)鏈接結(jié)構(gòu)分析子系統(tǒng)的作用和功能有了一個(gè)較為直觀的認(rèn)識(shí)。另外，這里 所得的鏈接結(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次