【導(dǎo)讀】畢業(yè)論文(設(shè)計(jì)). 論文（設(shè)計(jì)）題目:. 基于Nutch的新聞主題搜索引擎的設(shè)計(jì)與實(shí)現(xiàn)

　　

【正文】 使得 HITS 算法比 PageRank 算法在收斂速度上快很多，但是在信息檢索的過(guò)程中不得不考慮排序的代價(jià)問(wèn)題。 本文實(shí)現(xiàn) 的 算法 由于 目前的網(wǎng)頁(yè)多 才用 了半結(jié)構(gòu)化的 HTML 語(yǔ)言 ， 其中包含有豐富的結(jié)構(gòu)信 息，在 抽取 網(wǎng)頁(yè)的主題內(nèi)容時(shí)，應(yīng)對(duì)此加以利用。對(duì) 位于 title、 meta、 anchor等標(biāo)記 之內(nèi)的關(guān)鍵詞應(yīng)該重視，計(jì)算時(shí)賦予較大的權(quán)重系數(shù)。 并且 實(shí)踐 發(fā)現(xiàn)各大報(bào)紙網(wǎng)站中 的 鏈接大部分指向內(nèi)部，并且新聞頁(yè)面 都是 的形式， 所以 設(shè)置 Nutch 種子文件為報(bào)紙 新聞 網(wǎng)站 入口 ， 并且控制抓取的頁(yè)面都是 的形式， 保證 抓取 頁(yè)面的主題相關(guān)準(zhǔn)確率。 山東大學(xué)本科畢業(yè)論文 20 基于內(nèi)容 評(píng)價(jià) Fish Search 算法 基 于內(nèi)容評(píng)價(jià)的搜索策略的特點(diǎn)是利用網(wǎng)頁(yè)中文本信息作為某一相關(guān)領(lǐng)域的知識(shí)來(lái)指導(dǎo)搜索過(guò)程，并根據(jù)網(wǎng)頁(yè)內(nèi)容和網(wǎng)頁(yè)鏈接與 (關(guān)鍵詞和主題 )之間的相關(guān)度來(lái)評(píng)價(jià)這個(gè)網(wǎng)頁(yè)鏈接對(duì)搜索主題來(lái)說(shuō)的價(jià)值的高低，這種基于內(nèi)容搜索策略代表有： Fish Search 算法、 Shark Search 算法。 Fish Search 算法的核心是根據(jù)用戶主題相關(guān)度，實(shí)時(shí)動(dòng)態(tài)地維護(hù)待爬行 URL 地址的優(yōu)先隊(duì)列 URL_Queue。此隊(duì)列分為三部分前端、中部、尾部。另外還有幾個(gè)重要的參數(shù)分別是 depth、 width 和 potential_score。它們 作用分別為記錄被搜索網(wǎng)頁(yè)的深度、網(wǎng)頁(yè)的鏈路數(shù)目和 URL 的相關(guān)度。 Fish Search 算法的基本工作流程是：將一個(gè) URL 地址作為起始頁(yè)面進(jìn)行搜索，在搜索頁(yè)面的同時(shí)動(dòng)態(tài)的建立一個(gè)主題相關(guān)列表，用來(lái)存放待查詢的 URL地址，該列表的 URL 孩子鏈接或者子鏈接按照優(yōu)先級(jí)進(jìn)行區(qū)分。 URL 地址的排序也是按照優(yōu)先級(jí)從高到低來(lái)排序的，在每進(jìn)行一次查詢時(shí)，首先把優(yōu)先級(jí)最高的 URL 進(jìn)行分析，假設(shè)該網(wǎng)頁(yè)和搜索內(nèi)容相關(guān)，即對(duì) URL 的 potential_score 進(jìn)行賦值，同時(shí)也就改變此 URL 地址其相應(yīng)的 depth 和 width 參數(shù)值 ，然后再對(duì)下一個(gè) URL 地址進(jìn)行檢索，以此循環(huán)操作。 Fish Search 算法的具體流程描述如下： 1. 從動(dòng)態(tài) URL 列表中從高到低的提取 URL 地址，對(duì)提取的 URL 地址進(jìn)行搜索，取得與用戶搜索主題相關(guān)的網(wǎng)頁(yè)文件，將查詢出來(lái)的結(jié)果和用戶搜索內(nèi)容進(jìn)行比對(duì)，檢查二者的相關(guān)性。 2. 給每個(gè)從 URL 列表中提取的 URL 賦相應(yīng)的 depth 值，假設(shè)這個(gè) URL 文件列表是相關(guān)，那么就對(duì)這個(gè) URL 文件列表中的 URL 的 potential_score 值賦為1，并且得到一個(gè)最初設(shè)定的 depth 值。反之，如果 URL 文件列表不相關(guān)，那 么就給 URL 的 potential_score 的值賦為 或 0。隨著 denpth 值遞減，具體賦值操作方法如下描述： ①如果 URL 文件列表相關(guān)，則可以將這個(gè) URL 文件列表前得 a*width 個(gè)孩子加入到 URL_Queue 列表的最前端，其中 a 為事先定義的大于 1 常量。 山東大學(xué)本科畢業(yè)論文 21 ②如果 URL 文件列表不相關(guān)，則可以將這個(gè) URL 文件列表前得 width 個(gè)孩子加入到 URL_Queue 列表中臨時(shí)孩子相關(guān)網(wǎng)頁(yè)的節(jié)點(diǎn)的后面。 ③最后，剩下的節(jié)點(diǎn)全部加入到 URL_Queue 的尾部，就按照事先設(shè)定時(shí)間爬行，直至爬行時(shí)間用完為止。 3. 在取得 URL列表文件的同時(shí)， Web 服務(wù)器的網(wǎng)絡(luò)傳輸速度也要進(jìn)行檢測(cè)。如果速度太低，則將 URL 列表文件中的 URL 的 depth 設(shè)為 0。 4. 在經(jīng)過(guò)設(shè)定的一段時(shí)間之后，或者當(dāng) URL_Queue 已經(jīng)為空時(shí)，停止運(yùn)行。 Fish Search 的搜索算法是模擬了魚(yú)群捕食以及延續(xù)后代的情況。目的是為了查詢主題相關(guān)網(wǎng)頁(yè)，在特定范圍內(nèi)增加搜索寬度和深度的值，深度的值它代表魚(yú)得到食物可以生產(chǎn)和延續(xù)后代。在生產(chǎn)過(guò)程中會(huì)有更多后代被加入到 URL_Queue 列表的尾部，被加入到尾部的 URL地址在算法就被認(rèn)為魚(yú)已經(jīng)死了，想要訪問(wèn)這些 URL 地址，必須是 URL 列表中的其它 URL 都已經(jīng)被訪問(wèn)完，在設(shè)定的訪問(wèn)時(shí)間還沒(méi)有用盡的情況下可以訪問(wèn)。 Fish Search魚(yú)群檢索算法最關(guān)鍵的內(nèi)容就是維護(hù) URL_Queue 中 URL地址在列表的順序，與傳統(tǒng)搜索算法有著本質(zhì)的區(qū)別，傳統(tǒng)搜索都按照 URL 在父網(wǎng)頁(yè)中出項(xiàng)的順序來(lái)進(jìn)行搜索查詢操作 [17]。但是， Fish Search 則是根據(jù) URL 列表中potential_score 的值動(dòng)態(tài)改變 URL 項(xiàng)在列表中先后順序，進(jìn)而也就改變網(wǎng)頁(yè)被搜索的先后順序，這樣就可以處理更多相關(guān)網(wǎng)頁(yè)，避免了檢索無(wú)關(guān)網(wǎng)頁(yè)浪費(fèi)時(shí)間。但是 Fish Search 不是完美的，它也是有缺點(diǎn)的，相關(guān)性設(shè)計(jì)相對(duì)比較簡(jiǎn)單，只是分為兩種狀態(tài)相關(guān)或者不相關(guān)，再就是 potential_score 精度不高，且精度只分為三種狀態(tài)，分別為 0， ， 1，所以它不能代表所有網(wǎng)頁(yè)的相關(guān)度。 Shark Search 算法 Shark Search 算法是在 Fish Search 算法的基礎(chǔ)上，經(jīng)過(guò)修改而提出來(lái)的，此修改主要體現(xiàn)在：改進(jìn)了頁(yè)面、查詢信息的相關(guān)度計(jì)算、 potential_score 值的計(jì)算，下面對(duì)其修改作詳細(xì)說(shuō)明： 1. Shark Search 算法引入向量空間模型，用來(lái)計(jì)算查詢頁(yè)面與用戶查詢內(nèi)容兩者之間的相關(guān)度，改善對(duì)于 Fish Search 相關(guān)度過(guò)于簡(jiǎn)單所帶來(lái)的問(wèn)題，因此山東大學(xué)本科畢業(yè)論文 22 對(duì)相關(guān)度的量化值作了詳細(xì)設(shè)計(jì)。 2. 在計(jì)算用戶查詢內(nèi)容的相關(guān)度時(shí)，要考慮超鏈接的文本以及網(wǎng)頁(yè)上下文所包含的提示信息。子節(jié)點(diǎn)的 potential_score 的計(jì)算公式需要綜合考慮上面所講述的兩個(gè)因素，在 Shark Search 算法中求解 potential_score 的時(shí)候，利用下面講述的方法： ① 計(jì)算孩子節(jié)點(diǎn)繼承相關(guān)度， inherited_score(child_node): if(current_node 相關(guān) ) inherited_score(child_node)=δ *sim_score。 //δ 是預(yù)先定義的衰減因子 else inherited_score(child_node)= δ*inherited_score(current_node)。 ② anchor_text 為 child_node 的錨文本， anchor_text_context 為錨文本的上下文； ③ 計(jì)算錨文本的相似度： anchor_score=sim(topic,anchor_text)。 ④ 計(jì)算 anchor_text_context 相似度的值： if(anchor_score0) anchor_context_score=1。 else anchor_context_score=sim(topic,anchor_text_context)。 ⑤計(jì)算 anchor 的值，用 neighborhood_score，β為自定義常量，方法如下： neighborhood_score=β*anchor_score+(1β)*anchor_context_score。 ⑥計(jì)算 potential_score(child node)，方法如下： potential_score(child_node)=γ*inherited_score(child_node)+ (1γ)*neighborhood_score(child_node)。 其它一些算法與 Fish Search 算法類(lèi)似，以上所研究的兩種算法 Fish Search 算法和 Shark Search 算法都是基于內(nèi)容評(píng)價(jià)的查詢搜索算法，根據(jù)查詢內(nèi)容與主題的相關(guān)度的高低來(lái)判斷訪問(wèn)鏈接的先后次序，此類(lèi)算法最早是從檢索文本相關(guān)度的評(píng)價(jià)衍生而來(lái)的 [18]，此 類(lèi)算法最顯著的優(yōu)點(diǎn)就是計(jì)算量非常非常小，但是Web 頁(yè)面與傳統(tǒng)的文本在結(jié)構(gòu)上具有較大的差異性，文本網(wǎng)頁(yè)是一種半結(jié)構(gòu)化的文本文檔，它包含了許多結(jié)構(gòu)化的信息，并且每個(gè) Web 頁(yè)面都不是孤立存在，Web 頁(yè)面中的超鏈接把一個(gè)個(gè)存放在不同位置的頁(yè)面聯(lián)系起來(lái)，由于基于內(nèi)容山東大學(xué)本科畢業(yè)論文 23 相關(guān)度評(píng)價(jià)的爬蟲(chóng)忽略了這些存在于網(wǎng)頁(yè)之間的關(guān)系，因此預(yù)測(cè)出來(lái)的超鏈接的價(jià)值是不準(zhǔn)確的，存在一些漏洞，很容易使得網(wǎng)頁(yè)存在錯(cuò)選和誤選，另外主題內(nèi)容評(píng)價(jià)的準(zhǔn)確性與主題關(guān)鍵詞的選擇和構(gòu)建有著密切的關(guān)聯(lián)。 其他相關(guān)策略 基于鞏固學(xué)習(xí)的聚焦搜索 近年來(lái)對(duì) Web信息資源分布的研究表明很多類(lèi)型相同的網(wǎng)站在構(gòu)建方式上， 主題相同的網(wǎng)頁(yè)在組織方式上都存在著一定的相似性，有的學(xué)者就考慮將鞏固學(xué)習(xí)引入網(wǎng)絡(luò)爬蟲(chóng)的訓(xùn)練過(guò)程中，從這些相似性獲取一些“經(jīng)驗(yàn)”。 而這些經(jīng)驗(yàn)信息在搜索距相關(guān)頁(yè)面集較遠(yuǎn)的地方往往能獲得較好的回報(bào)， 而前兩種策略在這種情況下容易迷失方向。在鞏固學(xué)習(xí)模型中，把網(wǎng)絡(luò)爬蟲(chóng)經(jīng)過(guò)若干無(wú)關(guān)頁(yè)面的訪問(wèn)之后才能獲得的主題相關(guān)頁(yè)面稱(chēng)為未來(lái)回報(bào)，對(duì)未來(lái)回報(bào)的預(yù)測(cè)值稱(chēng)為未來(lái)回報(bào)價(jià)值， 用 Q 價(jià)值表示 [18]。 這種方法的核心就是學(xué)習(xí)如何計(jì)算鏈接的 Q 價(jià)值， 根據(jù)未 來(lái)回報(bào)價(jià)值確定正確的搜索方向。目前這類(lèi)搜索策略不足之處在于學(xué)習(xí)效率低的問(wèn)題，而且在訓(xùn)練過(guò)程中增加了用戶的負(fù)擔(dān)。 基于語(yǔ)境圖的聚焦搜索 基于鞏固學(xué)習(xí)的網(wǎng)絡(luò)爬蟲(chóng)通過(guò)計(jì)算鏈接的 Q 價(jià)值可以確定搜索方向，但它卻無(wú)法估計(jì)距離目標(biāo)頁(yè)面的遠(yuǎn)近。為此， Diligent 等提出了基于“語(yǔ)境圖”的搜索策略，它通過(guò)構(gòu)建典型頁(yè)面的 web“語(yǔ)境圖”來(lái)估計(jì)離目標(biāo)頁(yè)面的距離 [19]，距離較近的頁(yè)面較早得到訪問(wèn)基于“語(yǔ)境圖”的搜索策略需要借助已有的通用搜索引擎構(gòu)建“語(yǔ)境圖”，而搜索引擎的檢索結(jié)果并非一定代表真實(shí)的 web 結(jié)構(gòu)，因而 這種方式也具有局限性。 本章小結(jié) 本章節(jié)主要介紹了幾種主流的主題爬蟲(chóng) 策略， 并闡述 了本文所使用的基于URL 地址 相關(guān) 的 抓取 策略，為主題搜索引擎的實(shí)現(xiàn)奠定了基礎(chǔ)。 山東大學(xué)本科畢業(yè)論文 24 第 4 章 主題 搜索引擎的實(shí)現(xiàn) Nutch 搜索 引擎的實(shí)現(xiàn)需要 集成 Tomcat，由 JDK 提供支持，本章將重點(diǎn)介紹 部署 新聞主題搜索引擎 的 具體步驟。 開(kāi)發(fā)環(huán)境介紹 硬件環(huán)境： CPU: Intel 酷睿 i3 550 @ RAM: 2GB Memory 軟件環(huán)境： Java VM: 操作系統(tǒng)版本： Ubuntu 開(kāi)發(fā)工具： JavaCC 系統(tǒng) 的體系結(jié)構(gòu) 主題搜索引擎應(yīng)提供主題信息而不是大而全的結(jié)果，故必須制定有效的信息采集策略以滿足用戶的需要。在系統(tǒng)實(shí)現(xiàn)上，主題搜索引擎和通用搜索引擎的最大區(qū)別在于信息采集策略不同。主題搜索引擎的信息采集通過(guò)主題爬蟲(chóng)完成，需要使用多種輔助策略。由于網(wǎng)速的限制，本文的訓(xùn)練文本和初始 URL 主要針對(duì)計(jì)算機(jī)主題選取，構(gòu)造了一個(gè)基于 Nutch 的計(jì)算機(jī)主題搜索引擎，重點(diǎn)是主題爬蟲(chóng)的實(shí)現(xiàn)，其它主題均可通過(guò)更改訓(xùn)練文本和初始 URL 的范圍來(lái)實(shí)現(xiàn)。在主題信息提取方面，我們構(gòu) 建了計(jì)算機(jī)主題詞典用于主題特征提取。 主題搜索引擎和通用搜索引擎一樣，由三個(gè)部分組成：信息采集模塊(Crawler)、索引模塊 (Indexer)和查詢模塊 (Query)[20]。采集模塊負(fù)責(zé)從網(wǎng)絡(luò)上搜集網(wǎng)頁(yè)、 Word 文本或者 PDF 文本，并將文本及文本的其他信息保存在本地機(jī)器的硬盤(pán)上。索引模塊對(duì)搜索到的信息進(jìn)行整理、分類(lèi)和索引。查詢模塊提供網(wǎng)絡(luò)用戶檢索界面，并根據(jù)用戶的查詢要求，從信息數(shù)據(jù)庫(kù)中檢索出與之相關(guān)的信息資料并反饋給讀者。我們建立的計(jì)算機(jī)主題搜索引擎系統(tǒng)總體結(jié)構(gòu)如圖 41： 山東大學(xué)本科畢業(yè)論文 25 圖 41 主題 搜索引擎系統(tǒng)結(jié)構(gòu) 主題 爬 蟲(chóng) 的 配置 配置 Java 環(huán)境 實(shí)現(xiàn)環(huán)境為 Linux Ubuntu ，需要編譯 Java 源碼，所以安裝相關(guān)工具 1. 安裝 Ant $ aptget install 2. 安裝配置 Java 環(huán)境 $ aptget install openjdk7jdk $ export JAVA_HOME=/usr/lib/jvm/openjdk7jdk 3. 安裝 JavaCC（用于中文分詞時(shí)生成 java 代碼） $ aptget install javacc 配置 Nutch 1. 從官網(wǎng)下載 并解壓 ~$ cd ~$ ant //編譯，生成可執(zhí)行程序和庫(kù) ~$ ant war //編譯 war 文件，供 tomcat 使用 2. 設(shè)置要搜索的 URL 山東大學(xué)本科畢業(yè)論文 26 ~$ gedit 將 下面兩行輸入到文本中 ~$ gedit conf/ 編輯如下（否則運(yùn)行時(shí)會(huì)報(bào) agent 相關(guān)錯(cuò)誤） property name/name valuetest/value /property 3. 設(shè)置搜索地址過(guò)濾 ~$ gedit conf/ 編輯如下 accept