【計(jì)算機(jī)專業(yè)畢業(yè)論文】大規(guī)模網(wǎng)頁(yè)模塊識(shí)別與信息提取系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

《【計(jì)算機(jī)專業(yè)畢業(yè)論文】大規(guī)模網(wǎng)頁(yè)模塊識(shí)別與信息提取系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)》由會(huì)員分享，可在線閱讀，更多相關(guān)《【計(jì)算機(jī)專業(yè)畢業(yè)論文】大規(guī)模網(wǎng)頁(yè)模塊識(shí)別與信息提取系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)（43頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 本科生畢業(yè)論文 題目：(中文) 大規(guī)模網(wǎng)頁(yè)模塊識(shí)別與信息提取 系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn) (英文) Design and Implementation of Large Scale Web Template Detection and Information Extraction System 姓 名： 學(xué) 號(hào)： 院 系：計(jì)算機(jī) 專 業(yè)：搜索引擎與互聯(lián)網(wǎng)信息挖掘 指導(dǎo)教師： 41

2、 摘要 本文在已有的基于Dom-Tree和啟發(fā)式規(guī)則的網(wǎng)頁(yè)信息提取算法的基礎(chǔ)上，通過(guò)為所有符合W3C規(guī)范的Html標(biāo)簽分類，逐個(gè)分析各Html標(biāo)簽所包含的語(yǔ)義信息，細(xì)化規(guī)則設(shè)置，實(shí)現(xiàn)了一種自底向上的無(wú)信息遺漏的網(wǎng)頁(yè)分塊算法，并在此基礎(chǔ)上，利用統(tǒng)計(jì)方法得到詳細(xì)的概率分布數(shù)據(jù)，實(shí)現(xiàn)了文本相似度比較和Bayes后驗(yàn)概率估計(jì)兩種網(wǎng)頁(yè)主題內(nèi)容信息塊識(shí)別算法，并將其求交，提高了主題內(nèi)容信息塊的識(shí)別精確度。 上述算法已集成到天網(wǎng)搜索引擎平臺(tái)的網(wǎng)頁(yè)預(yù)處理模塊中，并且在SEWM 2008會(huì)議中，以這套算法為框架，組織了主題型網(wǎng)頁(yè)識(shí)別和網(wǎng)頁(yè)主題內(nèi)容信息塊提取兩個(gè)中文Web信息檢索評(píng)測(cè)項(xiàng)目。在這套算法的基礎(chǔ)上

3、，基于天網(wǎng)文件系統(tǒng)與Map-Reduce計(jì)算平臺(tái)，實(shí)現(xiàn)了分布式的網(wǎng)頁(yè)塊級(jí)別PageRank算法，命名為QuarkRank算法。實(shí)際檢驗(yàn)表明，該套算法具有很好的適應(yīng)性與可擴(kuò)展性，并達(dá)到了很高的精度和召回率。 關(guān)鍵詞：網(wǎng)頁(yè)分塊 信息提取 SEWM 評(píng)測(cè) PageRank Abstract This paper has been based on the Dom-Tree and heuristic rules of the Web information extraction method, by classifying all the Html tags in line with

4、W3C standards, and by analyzing semantic information contained in the Html tags one by one, it refines the rules set and achieves a bottom-up page block algorithm without information missing. On this basis, with the probability distribution of data getting from statistical methods, this paper

5、realizes two algorithms of information block recognition, one is text similarity comparison and the other is Bayes posterior probability estimates, and the final result comes from their intersection, which improves the accuracy of information theme block recognition. These algorithms have been in

6、tegrated into the page pretreatment module of TianWang search engine platform, and in SEWM 2008 meeting, using these algorithms, we organized two Chinese Web Information Retrieval Evaluation Project, Which two are theme-based Web page identification and block extraction of the information theme con

7、tent. In this method, based on TianWang file system and the Map-Reduce computing platform, this paper reports the distributed block-level PageRank algorithm, named QuarkRank algorithm here. The actual test showed that these algorithms are good at adaptability and scalability, and reach a very hig

8、h precision and recall. Keywords: Web-Page Blocking, SEWM, Information Extraction, Evaluation , PageRank 目錄 第 1 章 序言 3 第 2 章 相關(guān)研究工作 5 2.1 基于語(yǔ)義的網(wǎng)頁(yè)信息提取算法 5 2.2 基于視覺(jué)的網(wǎng)頁(yè)分塊算法 6 2.3 Block Level PageRank算法 8 2.3.1 Block Level Web Graph 8 2.3.2 Block Level PageRank 10 第 3 章 天網(wǎng)搜索引擎Quark模塊 11

9、 3.1 網(wǎng)頁(yè)分塊算法 13 3.2 網(wǎng)頁(yè)主題內(nèi)容提取 16 3.3 算法效果演示 18 第 4 章 SEWM2008中文Web信息檢索評(píng)測(cè) 23 4.1 評(píng)測(cè)任務(wù)介紹 23 4.1.1 主題型網(wǎng)頁(yè)發(fā)現(xiàn)任務(wù) 23 4.1.2 網(wǎng)頁(yè)內(nèi)容信息發(fā)現(xiàn)任務(wù) 24 4.2 評(píng)測(cè)格式 25 4.3 評(píng)測(cè)結(jié)果 25 4.3.1 主題型網(wǎng)頁(yè)發(fā)現(xiàn)任務(wù)評(píng)測(cè)結(jié)果 26 4.3.2 網(wǎng)頁(yè)內(nèi)容信息發(fā)現(xiàn)任務(wù)評(píng)測(cè)結(jié)果 28 4.4 評(píng)測(cè)綜述 31 第 5 章 網(wǎng)頁(yè)分塊的分布式應(yīng)用 32 5.1 QuarkRank 32 5.2 其他應(yīng)用 34 第 6 章 總結(jié)與展望 35 6.1 總結(jié) 35

10、 6.2 展望 36 第 1 章 序言 信息時(shí)代，非Web無(wú)以制勝。互聯(lián)網(wǎng)的高速發(fā)展，改變了我們的生活方式，打破了我們的時(shí)空界限，重塑著我們的社會(huì)形態(tài)。經(jīng)濟(jì)、政治、學(xué)習(xí)、工作、生活、娛樂(lè)等等各個(gè)層面都在Web網(wǎng)絡(luò)中激蕩起伏，深刻地影響著人類的未來(lái)。而Web網(wǎng)絡(luò)的靈魂，就是流動(dòng)在其中的無(wú)窮無(wú)盡的信息。Web2.0的意義就在于 網(wǎng)絡(luò)內(nèi)容的提供方從商人和專業(yè)人員轉(zhuǎn)變?yōu)榫W(wǎng)絡(luò)上的每一個(gè)普通用戶，從而幾何級(jí)數(shù)地增長(zhǎng)了Web的信息量。然而信息量的增大，隨著而來(lái)的就是存儲(chǔ)成本的增大和信息提取難度的增大，如何有效的獲取和整合Web信息成為大家面對(duì)的共同課題。 傳統(tǒng)意義上，整個(gè)Web

11、網(wǎng)絡(luò)就是由無(wú)數(shù)的Web頁(yè)面而構(gòu)成，它們是網(wǎng)絡(luò)信息存儲(chǔ)和提取的基本單位，獲取了這些Web頁(yè)面就相當(dāng)于獲取了Web信息內(nèi)容。但是把整個(gè)頁(yè)面作為最基本的信息處理單位有一些不合理之處。首先是因?yàn)閃eb頁(yè)面中信息量的分布非常不均勻，有主題內(nèi)容，也有廣告，導(dǎo)航欄，版權(quán)信息，裝飾信息，以及在大量網(wǎng)頁(yè)中重復(fù)出現(xiàn)的部分，它們自身的信息含量千差萬(wàn)別。當(dāng)網(wǎng)頁(yè)瀏覽者剛打開(kāi)一個(gè)新頁(yè)面的時(shí)候，如果之前沒(méi)有瀏覽過(guò)類似頁(yè)面，就會(huì)目不暇接，眼花繚亂，有無(wú)所適從的感覺(jué)，必須仔細(xì)探尋一番才能定位到這個(gè)頁(yè)面的要害；如果之前瀏覽過(guò)類似頁(yè)面，比如常上這個(gè)網(wǎng)站，那么通常瀏覽者就已經(jīng)訓(xùn)練出一種直覺(jué)或者說(shuō)是條件反射，他會(huì)立刻定位到他所想要瀏覽

12、的部分，從而忽略掉頁(yè)面中的其他部分。 其次還因?yàn)楝F(xiàn)在很多Web頁(yè)面是動(dòng)態(tài)更新的，比如博客頁(yè)面或者論壇討論帖，它們的更新是以一個(gè)一個(gè)網(wǎng)頁(yè)塊的形式進(jìn)行的，更新時(shí)頁(yè)面上大部分內(nèi)容并沒(méi)有變化，如果仍然以整個(gè)頁(yè)面為處理單位，則不可避免地存在效率損失和定義的混淆。這些情況促使我們反思以整個(gè)頁(yè)面為基本信息單元的做法不僅不盡合理，一定程度上甚至已經(jīng)損害了網(wǎng)絡(luò)瀏覽者的用戶體驗(yàn)，妨礙了網(wǎng)絡(luò)信息提取的效率。 解決這個(gè)問(wèn)題的辦法其實(shí)有兩種思路。第一種就是從信息的產(chǎn)生方那兒就不再提供網(wǎng)頁(yè)式的信息，而改為直接提供網(wǎng)頁(yè)塊或者文字段式的信息。最常見(jiàn)的例子就是RSS（聚合內(nèi)容，Really Simple Syndi

13、cation），博客或者新聞的提供方省去了瀏覽者訪問(wèn)網(wǎng)站查看更新的麻煩，直接將精簡(jiǎn)后的網(wǎng)頁(yè)塊或者文字段發(fā)送給RSS的訂閱方。第二種則更為普適，就是細(xì)分網(wǎng)頁(yè)中的信息單元，也就是給網(wǎng)頁(yè)分塊，在網(wǎng)頁(yè)分塊的基礎(chǔ)上存儲(chǔ)和提取Web頁(yè)面的語(yǔ)義信息。 基于網(wǎng)頁(yè)分塊的Web頁(yè)面的語(yǔ)義信息提取在很多方面都有應(yīng)用。比如，在常規(guī)搜索引擎中，可以以網(wǎng)頁(yè)分塊為基礎(chǔ)去除網(wǎng)頁(yè)中的噪音信息，識(shí)別出網(wǎng)頁(yè)中的主題內(nèi)容信息塊，從而用提取出的主題內(nèi)容信息來(lái)構(gòu)建對(duì)這個(gè)頁(yè)面的描述，完成網(wǎng)頁(yè)分類、網(wǎng)頁(yè)消重等應(yīng)用。還可以憑此改進(jìn)搜索引擎的索引模塊和檢索模塊的效率，比如改進(jìn)TF/IDF和PageRank的算法（詳見(jiàn)第五章）。 W

14、eb頁(yè)面的語(yǔ)義分塊另外一個(gè)重要用途在于移動(dòng)終端訪問(wèn)互聯(lián)網(wǎng)，比如手機(jī)和IPod等。因?yàn)槟壳按蟛糠值腤eb頁(yè)面都是針對(duì)PC機(jī)設(shè)計(jì)的，要求有相對(duì)較大的屏幕。而移動(dòng)設(shè)備通常屏幕較小，計(jì)算能力有限，無(wú)法直接訪問(wèn)這些頁(yè)面。 為了解決這個(gè)問(wèn)題，要么是內(nèi)容提供商手工編輯專門適用于移動(dòng)設(shè)備的頁(yè)面，要么就只有對(duì)頁(yè)面進(jìn)行語(yǔ)義分割，并在分割后的頁(yè)面中選擇信息量最高的語(yǔ)義塊。 除此之外，Web頁(yè)面的語(yǔ)義分塊還可能對(duì)常規(guī)搜索引擎之外的其他信息檢索系統(tǒng)有幫助。比如類似于新聞人物追蹤和歷史新聞檢索等應(yīng)用，出于節(jié)約存儲(chǔ)空間，提高檢索精度，方便更新等目的，可以直接存儲(chǔ)和操作網(wǎng)頁(yè)中的主題內(nèi)容語(yǔ)義塊，而舍棄網(wǎng)頁(yè)中其他與系統(tǒng)需

15、求無(wú)關(guān)的語(yǔ)義塊。 在這篇論文中，第二章介紹了本文的相關(guān)研究工作，包括常見(jiàn)的網(wǎng)頁(yè)分塊和信息提取算法、基于視覺(jué)的網(wǎng)頁(yè)分塊算法，以及網(wǎng)頁(yè)分塊的一個(gè)應(yīng)用Block Level PageRank算法；第三章介紹了我實(shí)現(xiàn)的網(wǎng)頁(yè)分塊和主題信息提取算法——Quark算法；第四章介紹了Quark算法在SEWM2008中文Web信息檢索評(píng)測(cè)項(xiàng)目中的實(shí)際檢驗(yàn)；第五章介紹了在Quark算法基礎(chǔ)上實(shí)現(xiàn)的一個(gè)分布式QuarkRank程序。第六章是對(duì)本文的總結(jié)和工作展望。 第 2 章 相關(guān)研究工作 2.1 基于語(yǔ)義的網(wǎng)頁(yè)信息提取算法 由于對(duì)Web頁(yè)面有效分塊之后可以

16、極大地方便內(nèi)容提取、數(shù)據(jù)挖掘、Web結(jié)構(gòu)分析等各項(xiàng)Web信息檢索領(lǐng)域的相關(guān)工作，所以早有很多研究人員前赴后繼，就此展開(kāi)了很多工作。其中，基于語(yǔ)義信息對(duì)網(wǎng)頁(yè)分塊是最簡(jiǎn)便，也最基礎(chǔ)的一種方法。所謂語(yǔ)義信息，通常包括網(wǎng)頁(yè)中包含的HTML標(biāo)簽信息，HTML DOM樹(shù)的結(jié)構(gòu)信息，文字內(nèi)容信息，超鏈接信息，以及其他通過(guò)統(tǒng)計(jì)或?qū)W習(xí)而得到的全局信息等等，也可以理解成為除了網(wǎng)頁(yè)中的視覺(jué)信息之外的所有可以得到的信息。 通?；谡Z(yǔ)義的網(wǎng)頁(yè)分塊算法是和后續(xù)的網(wǎng)頁(yè)主題內(nèi)容提取結(jié)合在一起的，也就是在網(wǎng)頁(yè)分塊的過(guò)程中，同時(shí)完成了主題內(nèi)容提取的工作，并且主要的注意點(diǎn)是在主題內(nèi)容提取上，因此分塊算法就比較簡(jiǎn)單，甚至不顯式

17、地分塊，在此我們統(tǒng)稱它們?yōu)榫W(wǎng)頁(yè)信息提取算法?？偟膩?lái)說(shuō)，網(wǎng)頁(yè)信息提取算法可以分為兩類，一類屬于網(wǎng)站級(jí)別（Site-Level），一類屬于網(wǎng)頁(yè)級(jí)別（Page-Level），當(dāng)然也有將兩類方法結(jié)合使用的算法。 Site-Level的算法顧名思義，就是分析一個(gè)網(wǎng)站或者網(wǎng)頁(yè)集內(nèi)部的所有網(wǎng)頁(yè)，從中提取反復(fù)出現(xiàn)的模式，而一般來(lái)說(shuō)，在多個(gè)網(wǎng)頁(yè)里重復(fù)出現(xiàn)的模式（可理解為Dom-Tree子樹(shù)）就是導(dǎo)航欄、廣告等噪音信息了，單個(gè)網(wǎng)頁(yè)中減去這些信息，剩下的就是主題信息內(nèi)容。關(guān)于Site-Level的研究一直在繼續(xù)，WWW2008上就有一篇名為Web page sectioning using regex-bas

18、ed template[1]的論文使用正則表達(dá)式來(lái)提取重復(fù)模式，從而更適應(yīng)網(wǎng)頁(yè)間的細(xì)微變化，增加了Site-Level的召回率。 Page-Level的算法在處理大型網(wǎng)站的網(wǎng)頁(yè)時(shí)效率常常不如Site-Level，但優(yōu)勢(shì)在于靈活，不受網(wǎng)頁(yè)類型限制。它只利用單個(gè)頁(yè)面內(nèi)部的信息，當(dāng)然也可能會(huì)用到一些全局信息。賓夕法尼亞州立大學(xué)2005年的論文[2]就是其中的典型。這篇論文提出簡(jiǎn)化塊與塊之間的層次結(jié)構(gòu)，直接提取一些原子塊（Atomic Block），諸如以list, table, link, object, frame, form等為根節(jié)點(diǎn)的html子樹(shù)，來(lái)完成分塊工作。這一方法雖然簡(jiǎn)單而易于實(shí)

19、現(xiàn)，但依賴于事先給出的原子塊列表，同時(shí)忽略了原子塊之間的嵌套鏈接問(wèn)題。在分塊之后，它也只是簡(jiǎn)單計(jì)算了文字長(zhǎng)度等幾個(gè)變量來(lái)決定主題信息塊。 合并Site-Level和Page-Level的方法也一直有人嘗試。WWW2007的論文Page-level template detection via isotonic smoothing[3]先利用一個(gè)Site-Level噪音模板提取器來(lái)構(gòu)建訓(xùn)練集，然后對(duì)所有頁(yè)面構(gòu)建DOM樹(shù)，為各節(jié)點(diǎn)提取分類特征，比如各節(jié)點(diǎn)的文本向量，各節(jié)點(diǎn)中鏈接的平均字?jǐn)?shù)，各節(jié)點(diǎn)中鏈接文字所占比例等，最后利用以上訓(xùn)練集對(duì)測(cè)試集中每一個(gè)DOM樹(shù)節(jié)點(diǎn)打分，經(jīng)過(guò)等壓平滑之后，判

20、定每個(gè)DOM樹(shù)節(jié)點(diǎn)的類型。所以它是典型的先Site-Level，后Page-Level的方法。 2.2 基于視覺(jué)的網(wǎng)頁(yè)分塊算法 基于語(yǔ)義的網(wǎng)頁(yè)分塊算法具有一些無(wú)法克服的先天性局限。首先，HTML語(yǔ)言版本眾多，一直沒(méi)有有效統(tǒng)一，而且其語(yǔ)法規(guī)范很松散，一些不符合HTML規(guī)則的網(wǎng)頁(yè)也能被完全識(shí)別，所以網(wǎng)頁(yè)編寫者在制作網(wǎng)頁(yè)時(shí)相對(duì)隨意，導(dǎo)致Web上的很多網(wǎng)頁(yè)都沒(méi)有完全遵循W3C規(guī)范；其次，IE、Firefox等瀏覽器各自為政，對(duì)HTML標(biāo)簽的識(shí)別不盡相同，IE甚至還特別為Office軟件設(shè)計(jì)了特別的html標(biāo)簽以輔助顯示，這些都增加了基于規(guī)則分塊的復(fù)雜性。在實(shí)際編程中，就必須得借助一些HTML

21、規(guī)范工具如tidy等來(lái)修正DOM樹(shù)結(jié)構(gòu)的錯(cuò)誤，但個(gè)別中文網(wǎng)頁(yè)仍然存在無(wú)法修正的情況。而且DOM樹(shù)最早引入是為了在瀏覽器中進(jìn)行布局顯示而不是進(jìn)行Web頁(yè)面的語(yǔ)義結(jié)構(gòu)描述。比如，即使DOM樹(shù)中兩個(gè)結(jié)點(diǎn)具有同一個(gè)父結(jié)點(diǎn)，那么這兩個(gè)結(jié)點(diǎn)在語(yǔ)義上也不一定就是有聯(lián)系的。反之，兩個(gè)在語(yǔ)義上有關(guān)系的結(jié)點(diǎn)卻可能分布在DOM樹(shù)的不同之處。因此僅僅通過(guò)分析DOM樹(shù)并不能完全獲取Web頁(yè)面的語(yǔ)義信息，所以依賴于DOM樹(shù)的啟發(fā)式規(guī)則算法存在先天不足。 而基于視覺(jué)的網(wǎng)頁(yè)分塊算法就彌補(bǔ)了這個(gè)不足。它的原理來(lái)自于用戶的實(shí)際觀察體驗(yàn)，即用戶并不關(guān)心Web頁(yè)面的內(nèi)部結(jié)構(gòu)，而是使用一些視覺(jué)因素，比如背景顏色、字體顏色和大小、

22、邊框、邏輯塊和邏輯塊之間的間距等等來(lái)識(shí)別出頁(yè)面中的語(yǔ)義塊。因此如果充分的使用Web頁(yè)面的視覺(jué)信息，模擬人眼識(shí)別語(yǔ)義塊的過(guò)程，并結(jié)合DOM樹(shù)結(jié)構(gòu)分析進(jìn)行頁(yè)面分塊，則可以達(dá)到更好的效果。 微軟亞洲研究院在其2003年的論文VIPS: A vision based page segmentation algorithm[4]里首次提出了基于視覺(jué)的網(wǎng)頁(yè)分塊算法VIPS(Vision-based page segmentation)。VIPS算法充分利用了Web頁(yè)面的布局特征（見(jiàn)圖1），它有三個(gè)主要步驟：首先從DOM樹(shù)中以較小的粒度提取出所有可視標(biāo)簽塊，并且給每個(gè)可視標(biāo)簽塊計(jì)算出一個(gè)DOC（“一致

23、性程度”，Degree of Coherence）值來(lái)描述該塊內(nèi)部?jī)?nèi)容的相關(guān)性。DOC的值越大，則表明該塊內(nèi)部的內(nèi)容之間的聯(lián)系越緊密，反之越松散。第二步利用每個(gè)可視標(biāo)簽塊的絕對(duì)位置和相對(duì)位置信息，檢測(cè)出它們之間的所有的分割條，包括水平和垂直方向。最后基于這些分割條，利用更多的諸如顏色等視覺(jué)信息，重新構(gòu)建Web頁(yè)面的語(yǔ)義結(jié)構(gòu)。 VIPS算法的優(yōu)點(diǎn)十分明顯，它充分利用了網(wǎng)頁(yè)的視覺(jué)信息和結(jié)構(gòu)信息，相對(duì)于傳統(tǒng)的基于規(guī)則的分塊算法來(lái)說(shuō)，大大提高了分塊的精確度。但VIPS算法也有其局限性： 首先，提取網(wǎng)頁(yè)視覺(jué)信息代價(jià)很高。因?yàn)镠TML語(yǔ)言本身并沒(méi)有包含足夠的視覺(jué)信息，所以網(wǎng)頁(yè)真正顯示出來(lái)的效果因?yàn)g

24、覽器，因操作系統(tǒng)，甚至因硬件而異。為了得到網(wǎng)頁(yè)的完整視覺(jué)信息，必須完全下載該網(wǎng)頁(yè)所鏈接的CSS文件，JavaScript文件，圖片文件等等，然后調(diào)用瀏覽器內(nèi)核代碼渲染這些網(wǎng)頁(yè)文件，最后從瀏覽器內(nèi)核代碼的接口中得到每個(gè)HTML標(biāo)簽的視覺(jué)信息。整個(gè)步驟不僅耗時(shí)，而且十分依賴于瀏覽器內(nèi)核代碼。網(wǎng)絡(luò)上看到的一些VIPS算法實(shí)現(xiàn)都是調(diào)用了IE COM接口，而微軟自身的實(shí)現(xiàn)是利用單獨(dú)優(yōu)化后的IE內(nèi)核，他們都是基于Windows編程環(huán)境。在Linux編程環(huán)境下，可以利用的只有Mozilla（Firefox）瀏覽器的開(kāi)源代碼。但Mozilla代碼并沒(méi)有針對(duì)網(wǎng)頁(yè)視覺(jué)信息提取這一需求給出方便的使用接口，只有在其渲

25、染完網(wǎng)頁(yè)之后再截取視覺(jué)信息。我們實(shí)驗(yàn)室的毛先領(lǐng)師兄曾經(jīng)研究Mozilla代碼，完成了這項(xiàng)艱苦的工作，但實(shí)驗(yàn)表明，提取一個(gè)網(wǎng)頁(yè)的視覺(jué)信息所需時(shí)間超過(guò)1秒鐘，不能滿足搜索引擎等常規(guī)應(yīng)用的使用要求。 其次，VIPS算法雖能改進(jìn)分塊精確度，但算法相對(duì)比較復(fù)雜，迭代輪數(shù)較多，而基于規(guī)則的分塊算法卻只用較少的迭代輪數(shù)。 2.3 Block Level PageRank算法 在VIPS算法的分塊基礎(chǔ)上，微軟2004年的論文Block-level Link Analysis[5]中提出了Block Level PageRank(BLPR)算法。之前的大多數(shù)鏈接分析算法都是以一個(gè)Web頁(yè)面為Web圖中

26、的一個(gè)節(jié)點(diǎn)，而B(niǎo)LPR算法以網(wǎng)頁(yè)中的語(yǔ)義塊為原子節(jié)點(diǎn)，從鏈接結(jié)構(gòu)和頁(yè)面結(jié)構(gòu)中提取出Page-to-Block，Block-to-Page關(guān)系矩陣，構(gòu)建出新的Web語(yǔ)義圖，并以此計(jì)算PageRank。實(shí)驗(yàn)表明，BLPR改進(jìn)了PageRank的質(zhì)量。 2.3.1 Block Level Web Graph 首先定義兩個(gè)集合P和B。P為所有網(wǎng)頁(yè)的集合，P = {p1, p2, …, pk}，k為網(wǎng)頁(yè)總數(shù)。B為所有語(yǔ)義塊的集合，B = {b1, b2, …, bn}，n為語(yǔ)義塊總數(shù)。對(duì)每個(gè)語(yǔ)義塊來(lái)說(shuō)，只有一個(gè)網(wǎng)頁(yè)包含它，bi ∈pj意味著語(yǔ)義塊i包含于網(wǎng)頁(yè)j。而每個(gè)網(wǎng)頁(yè)包含有多個(gè)語(yǔ)義塊。然后定義兩

27、個(gè)矩陣，block-to-page 矩陣Z和page-to-block矩陣X。在上述兩個(gè)矩陣的基礎(chǔ)之上，可以構(gòu)建兩個(gè)web圖模型，即網(wǎng)頁(yè)圖GP (VP,EP, WP) 和語(yǔ)義塊圖GB (VB, EB, WB)。對(duì)這兩個(gè)圖來(lái)說(shuō)，V是節(jié)點(diǎn)集合（節(jié)點(diǎn)分別是網(wǎng)頁(yè)和語(yǔ)義塊），E是連接兩個(gè)節(jié)點(diǎn)的邊的集合，而W是邊的權(quán)值矩陣。 2.3.1.1 Block-to-Page矩陣 塊頁(yè)（block-to-page）矩陣Z的維數(shù)為nk，定義如下： si是block i所鏈接的網(wǎng)頁(yè)總數(shù)。Zij可以理解成是用戶從block i鏈接到page j的概率。 2.3.1.2 Page-to-Bl

28、ock矩陣 頁(yè)塊（page-to-block）矩陣X的維數(shù)為kn，定義如下： si是page i所包含的block總數(shù)。上面的公式分配給page i中的每一個(gè)block以相同的權(quán)值，顯然是過(guò)于簡(jiǎn)化了，不能區(qū)分block的重要程度。在BLPR算法中，采用了一個(gè)簡(jiǎn)單的block重要度區(qū)分的公式，即用block的文字多少和離整個(gè)頁(yè)面中心點(diǎn)位置的遠(yuǎn)近來(lái)計(jì)算block的重要度。每個(gè)block包含的文本長(zhǎng)度越大，離頁(yè)面中心點(diǎn)越近，則越重要。改進(jìn)后的X定義如下： 其中f函數(shù)給page i中的每一個(gè)block j賦予一個(gè)重要度權(quán)值。函數(shù)值越大，則block越重要。

29、在BLPR的實(shí)現(xiàn)中函數(shù)f的定義如下： 其中β為正規(guī)化因子，使得對(duì)每個(gè)page，fp(b)的總和為1。即 fp(b)可以理解為是用戶在瀏覽page p的時(shí)候，關(guān)注block b的可能性。 2.3.1.3 Page Graph 傳統(tǒng)的PageRank算法中Page Graph的權(quán)值矩陣計(jì)算十分簡(jiǎn)單，如果從page i到page j有鏈接的話，則WP(i,j)為1，反之為0。然而在BLPR算法中，Page Graph需要體現(xiàn)出不同的語(yǔ)義塊的重要程度的不同。也就是說(shuō)，當(dāng)用戶點(diǎn)擊頁(yè)面中的超鏈接時(shí)，更偏好選擇重要的語(yǔ)義塊中的URL。所以在BLPR中，WP的定義

30、為： 即。 WP(α, β)可以理解為是從page α 開(kāi)始，以page α中包含的各語(yǔ)義塊為媒介，跳轉(zhuǎn)到page β的概率。 2.3.1.4 Block Graph WB的定義為： 即。 WB(a,b)可以理解為用戶從block a開(kāi)始，以包含block b的page β為媒介，跳轉(zhuǎn)到block b的概率。 2.3.2 Block Level PageRank Block Level PageRank跟PageRank區(qū)別的實(shí)質(zhì)在于，PageRank算法基于原始的只有1和0的Page Graph，而B(niǎo)LPR算法基于上面提到的GP。BLPR

31、算法的數(shù)學(xué)計(jì)算公式如下： 其中p為結(jié)果向量，共n維，每一維代表一個(gè)網(wǎng)頁(yè)的PageRank值。ε為適配參數(shù)，以1-ε的概率，用戶在當(dāng)前頁(yè)面中隨機(jī)選擇一個(gè)超鏈接，跳轉(zhuǎn)到該鏈接指向的頁(yè)面；以ε的概率，用戶從所有網(wǎng)頁(yè)中隨機(jī)選擇一個(gè)URL并跳轉(zhuǎn)。所以U為nn的轉(zhuǎn)換矩陣，它滿足對(duì)所有的i，j，Uij = 1/n。而M也是nn的轉(zhuǎn)換矩陣，它是由上面提到的WP權(quán)值矩陣對(duì)每一行做歸一化，令每一行的權(quán)值之和為1得到的。p向量的值以馬爾科夫鏈的形式循環(huán)計(jì)算下去，直到算法收斂。 Block Level PageRank比單純的PageRank包含了更多的語(yǔ)義信息。因?yàn)樗挠?jì)算基于網(wǎng)頁(yè)中各語(yǔ)義塊

32、的重要程度，噪音塊、廣告塊中的超鏈接指向的網(wǎng)頁(yè)的重要性顯然不如導(dǎo)航塊、正文塊中的超鏈接所指向的網(wǎng)頁(yè)，所以前者會(huì)被分配到較少的PageRank值，而后者則被分配到較多的PageRank值。也就是說(shuō)，網(wǎng)頁(yè)中的無(wú)關(guān)信息區(qū)域在PageRank的計(jì)算過(guò)程中起的作用相對(duì)較小，所以BLPR的效果要優(yōu)于單純的PageRank。 第 3 章 天網(wǎng)搜索引擎Quark模塊 搜索引擎系統(tǒng)一般包括網(wǎng)頁(yè)的抓取、預(yù)處理、存儲(chǔ)、索引、檢索等幾個(gè)部分，其中預(yù)處理部分的作用是分析、處理原始網(wǎng)頁(yè)數(shù)據(jù)如去除網(wǎng)頁(yè)噪音，消除重復(fù)網(wǎng)頁(yè)，計(jì)算PageRank，中文切詞等等，并為后繼模塊提供統(tǒng)一的數(shù)據(jù)訪問(wèn)接口，規(guī)范數(shù)據(jù)管理，避免重復(fù)計(jì)

33、算。同時(shí)在天網(wǎng)搜索引擎平臺(tái)中，基于功能擴(kuò)展和實(shí)驗(yàn)室內(nèi)部其他相關(guān)研究的需要，必須將對(duì)原始網(wǎng)頁(yè)的處理部分單獨(dú)出來(lái)，從而方便模塊復(fù)用，統(tǒng)一代碼管理，減少重復(fù)勞動(dòng)。 在天網(wǎng)搜索引擎平臺(tái)的搭建過(guò)程中，也包括了抓取、存儲(chǔ)、分析（預(yù)處理）、索引、檢索等模塊，其中的分析模塊接受成批量原始網(wǎng)頁(yè)的輸入，然后對(duì)每個(gè)網(wǎng)頁(yè)調(diào)用Quark模塊，進(jìn)行網(wǎng)頁(yè)分塊、信息提取等工作，最后將處理后的數(shù)據(jù)存成TwDocView格式，再提供給下游模塊。我的畢業(yè)設(shè)計(jì)的主要工作，就是圍繞Quark模塊而展開(kāi)。 從上面的介紹中可以看出，天網(wǎng)搜索引擎Quark模塊有兩個(gè)比較重要的特點(diǎn)： 1、可擴(kuò)展性。 因?yàn)樗阉饕媸且粋€(gè)比較

34、龐大的系統(tǒng)，并且一直在不停的有新算法，新需求的加入，所以對(duì)數(shù)據(jù)的要求也會(huì)一直變化。而基于對(duì)原始網(wǎng)頁(yè)數(shù)據(jù)集中處理的原則，為了應(yīng)對(duì)下游模塊可能提取的新的數(shù)據(jù)訪問(wèn)需求，Quark模塊必須具備良好的可擴(kuò)展性，并且提供盡量多的各種類型的數(shù)據(jù)訪問(wèn)接口。同時(shí)由于實(shí)驗(yàn)室人員的不固定性，代碼的維護(hù)十分重要。我自己在剛開(kāi)始閱讀舊有的天網(wǎng)搜索引擎相關(guān)代碼的時(shí)候，就常有十分難懂的感覺(jué)，無(wú)法復(fù)用已有代碼，只好自己重新編寫。而正由于Quark模塊的可擴(kuò)展性要求，所以它的代碼的可閱讀性也十分重要，在編寫的過(guò)程中，我盡量注意了這一點(diǎn)，遵守了我們統(tǒng)一的代碼規(guī)范。 2、獨(dú)立性。 在我們實(shí)驗(yàn)室內(nèi)部，除了搜索引擎之外，還有W

35、eb數(shù)據(jù)挖掘，Map-reduce應(yīng)用等相關(guān)工作也可能需要使用對(duì)單個(gè)網(wǎng)頁(yè)的處理和數(shù)據(jù)提取程序。因此Quark模塊必須能獨(dú)立于搜索引擎代碼之外單獨(dú)編譯運(yùn)行，并且方便他人調(diào)用這部分代碼。 基于上述兩個(gè)特點(diǎn)，我初步實(shí)現(xiàn)了Quark模塊。該模塊的類結(jié)構(gòu)圖如下： 1、圖中右下及中間藍(lán)色的部分為Quark模塊的核心功能類，包括QuarkTree、QuarkElement、QuarkRecognizer、QuarkAnalyzer等四個(gè)類。 QuarkTree類的作用有兩個(gè)，一個(gè)是以原始網(wǎng)頁(yè)為輸入，建立Html的Dom Tree；另一個(gè)是存儲(chǔ)分好的網(wǎng)頁(yè)塊（在我們的系統(tǒng)中

36、，每一個(gè)網(wǎng)頁(yè)塊就叫做一個(gè)Quark）并記錄Quark與Quark之間的組織架構(gòu)。 QuarkElement類指代一個(gè)Quark,即每個(gè)Quark自身就是一個(gè)QuarkElement類的對(duì)象。 QuarkRecognizer類肩負(fù)網(wǎng)頁(yè)分塊的重任，從網(wǎng)頁(yè)中識(shí)別出所有語(yǔ)義塊。它依賴于前面的兩個(gè)類。 QuarkAnalyzer類依賴于QuarkRecognizer類，它在分好的塊的基礎(chǔ)上，判斷各個(gè)塊的類型，提取正文信息。這個(gè)類是整個(gè)Quark模塊最核心的類，目前功能只是初步實(shí)現(xiàn)，還有很大的改進(jìn)空間，將來(lái)也可以根據(jù)功能將其分割成多個(gè)類。 2、中上部綠色的部分為Quark模塊的

37、評(píng)測(cè)和演示類，包括QuarkEvaluation和QuarkHtmlBuilder兩個(gè)類。 QuarkEvaluation類是評(píng)測(cè)類，用來(lái)評(píng)測(cè)Quark核心類的實(shí)現(xiàn)效果。當(dāng)前實(shí)現(xiàn)的是對(duì)網(wǎng)頁(yè)正文信息提取的評(píng)測(cè)，評(píng)測(cè)需要接受人工標(biāo)記的網(wǎng)頁(yè)或網(wǎng)頁(yè)集為輸入。評(píng)測(cè)算法的細(xì)節(jié)見(jiàn)后文。 QuarkHtmlBuilder類是演示類，用來(lái)查看Quark模塊各步驟的實(shí)現(xiàn)效果。目前可以查看網(wǎng)頁(yè)分塊的效果，也可以查看主題信息提取的效果。 3、最上面黃色的部分為Quark模塊的應(yīng)用類，包括QuarkRank、QuarkDuplicate、QuarkClassification等，它們都是利用分好的網(wǎng)頁(yè)

38、塊實(shí)現(xiàn)的一些算法，比如基于Quark的PageRank算法，基于Quark的網(wǎng)頁(yè)消重算法，以及基于Quark的網(wǎng)頁(yè)分類算法。 4、左下方灰色的部分為Quark模塊依賴的外部類接口，包括中文切詞類ChineseTokenizer，以及圖中沒(méi)有的編碼轉(zhuǎn)換類CodeConvert等等。 5、中下部紅色的部分為Quark模塊直接的下游模塊，包括TwDocView類和TwMd5類。 3.1 網(wǎng)頁(yè)分塊算法 算法主體在QuarkRecognizer類中。參見(jiàn)在第二章相關(guān)研究里提到的，除了基于視覺(jué)的算法之外，大部分基于語(yǔ)義的算法都是利用html標(biāo)簽及其包含的文字信息的特性來(lái)給網(wǎng)頁(yè)分塊的

39、。并且由于大多數(shù)論文的著重點(diǎn)在于分塊后的內(nèi)容提取上，所以對(duì)分塊算法本身著墨不多。綜合各篇論文里提到的分塊方法，我設(shè)計(jì)實(shí)現(xiàn)了QuarkRecognizer算法。 這一算法首先的一大特點(diǎn)就是實(shí)用性強(qiáng)。所謂實(shí)用性強(qiáng)是指適合在實(shí)際系統(tǒng)中使用，效率高，定義完整。我詳細(xì)分析了W3C制定的HTML4.01格式規(guī)范，將所有規(guī)范的Html標(biāo)簽根據(jù)QuarkRecognizer算法的需要分類，完整地列出了所有對(duì)網(wǎng)頁(yè)分塊起重要作用的標(biāo)簽，而不是像所有已有論文那樣僅僅象征性地列舉出幾個(gè)html標(biāo)簽。分類后的詳細(xì)html標(biāo)簽清單如下： 1、超級(jí)標(biāo)簽（Super Tag，簡(jiǎn)稱為S型標(biāo)簽）： 這種標(biāo)簽可以被直

40、接認(rèn)定是一個(gè)網(wǎng)頁(yè)塊的根標(biāo)簽，在算法過(guò)程中一旦遇到這種標(biāo)簽，就可以直接將其加入網(wǎng)頁(yè)塊池。包括： "HEAD", "SCRIPT", "STYLE", "OBJECT", "FIELDSET", "FRAMESET", "IFRAME" 2、大標(biāo)簽（Big Tag，簡(jiǎn)稱為B型標(biāo)簽）： 這種標(biāo)簽通常都代表一個(gè)網(wǎng)頁(yè)塊，只不過(guò)有時(shí)其內(nèi)部?jī)?nèi)容過(guò)少，需要跟其他節(jié)點(diǎn)合并成一個(gè)網(wǎng)頁(yè)塊，或者在特殊情況下其內(nèi)部沒(méi)有可見(jiàn)字符。所以在算法過(guò)程中，遇到這種標(biāo)簽，就判斷其單獨(dú)作為一個(gè)網(wǎng)頁(yè)塊的條件是否已經(jīng)成熟，如成熟，則將其加入網(wǎng)頁(yè)塊池。包括： "DIV", "TD", "TABLE", "FORM",

41、"FIELDSET", "CENTER", "NOFRAMES", "NOSCRIPT", "PRE", "BODY", "HTML" 這里需要注意的是像BODY，HTML兩個(gè)標(biāo)簽也作為B型標(biāo)簽，原因是這樣可以防止分塊之后網(wǎng)頁(yè)內(nèi)部文字信息的遺漏，因?yàn)樽罱K即使有遺漏，也會(huì)至少包含在HTML這個(gè)最后把關(guān)的門神標(biāo)簽手中。 3、排版標(biāo)簽（Layout Tag，簡(jiǎn)稱為L(zhǎng)型標(biāo)簽）： 這種標(biāo)簽?zāi)苡绊懙骄W(wǎng)頁(yè)的顯示效果，改變文字布局。如果一顆html子樹(shù)中包含多個(gè)L型標(biāo)簽，則該子樹(shù)單獨(dú)成塊的可能性增加。包括： "P", "UL", "OL", "DL", "DIR", "LI", "DT",

42、 "BLOCKQUOTE", "ADDRESS", "BR", "HR", "COL", "COLGROUP", "IMG", "MENU", "SELECT" 4、顯示標(biāo)簽（Display Tag，簡(jiǎn)稱為D型標(biāo)簽）： 這種標(biāo)簽數(shù)量最多，都是對(duì)文字的顯示方式做微幅的調(diào)整，如改變字體、顏色、粗細(xì)等等。由于它們的存在與否不改變網(wǎng)頁(yè)布局，所以不影響網(wǎng)頁(yè)分塊。包括： "A", "ABBR", "ACRONYM", "AREA", "B", "BASE", "BASEFONT", "BDO", BIG", "BUTTON", "CAPTION", "CITE", "CODE", "DD

43、", "DEL", "DFN", "EM", "FONT", "H1", "H2", "H3", "H4", "H5", "H6", "I", "INS", "KBD", "LABLE", "SMALL", "STRIKE", "STRONG", "SUB", "SUP", "Q", "S", "SAMP", "SPAN", "THEAD", "TFOOT", "TEXTAREA", "U", "TT", "VAR", "O:SMARTTAGTYPE" 5、附屬標(biāo)簽（Affiliated Tag，簡(jiǎn)稱為A型標(biāo)簽）： 這種標(biāo)簽從屬與上述四種標(biāo)簽的某一種，同時(shí)有些也出現(xiàn)在了前面四種里面。由

44、于它們一般不單獨(dú)出現(xiàn)，對(duì)網(wǎng)頁(yè)布局的影響體現(xiàn)在了其屬主標(biāo)簽中，所以 在QuarkRecognizer算法中也不予考慮。包括： "FRAME", "INPUT", "ISINDEX", "LEGEND", "LINK", "MAP", "META", "OPTION", "OPTGROUP", "PARAM", "TD", "TH", "TR", "TBODY", "TITLE" 6、定制標(biāo)簽（Customized Tag，簡(jiǎn)稱為C型標(biāo)簽）： 因?yàn)椴煌膽?yīng)用中，對(duì)網(wǎng)頁(yè)分塊會(huì)有些不同的要求。比如我們實(shí)驗(yàn)室的WebDigest小組在進(jìn)行新聞網(wǎng)頁(yè)的數(shù)據(jù)挖掘的工作中，需要使用到網(wǎng)頁(yè)分塊，但

45、是他們特別需要提取該新聞網(wǎng)頁(yè)的發(fā)布日期和時(shí)間，而這部分內(nèi)容通常是在新聞標(biāo)題與新聞?wù)闹g的一小行文字，正常的網(wǎng)頁(yè)分塊程序并不會(huì)將其單獨(dú)提取成一個(gè)網(wǎng)頁(yè)塊。所以我添加了定制標(biāo)簽，由用戶指定，它可以是普通的標(biāo)簽如“TITLE”等，也可以是正則表達(dá)式，凡是其內(nèi)部文字滿足該正則表達(dá)式的S型、B型和L型標(biāo)簽，都將被單獨(dú)提取為網(wǎng)頁(yè)塊。例如： "H1", "H2", "TITLE" 在明確了各html標(biāo)簽的類別之后，利用DomTree中各標(biāo)簽節(jié)點(diǎn)的類別信息和內(nèi)部文字長(zhǎng)度，以及其子標(biāo)簽節(jié)點(diǎn)的類別信息，對(duì)DomTree自底向上遍歷，在遍歷的過(guò)程中不斷判斷出新的網(wǎng)頁(yè)塊，并加入網(wǎng)頁(yè)塊池中，當(dāng)遍歷到最上部的

46、html根節(jié)點(diǎn)時(shí)，算法結(jié)束，網(wǎng)頁(yè)分塊完畢。QuarkRecognizer算法的核心偽碼如下： _________________________________________________________________ ALGORITHM QuarkRecognizer (DomTree tree，TagList CType) INPUT : 某單個(gè)網(wǎng)頁(yè)構(gòu)建的DomTree，定制標(biāo)簽(C型)節(jié)點(diǎn)列表 BEGIN 1 用DomTree的葉子節(jié)點(diǎn)，也就是文字節(jié)點(diǎn)建立一個(gè)當(dāng)前節(jié)點(diǎn)隊(duì)列，開(kāi)始自底向上遍歷。 2 取當(dāng)前節(jié)點(diǎn)隊(duì)列的第一個(gè)節(jié)點(diǎn)。 3 如果遇到S型節(jié)點(diǎn)，則立即

47、將此節(jié)點(diǎn)加入網(wǎng)頁(yè)塊池。 4 如果遇到C型節(jié)點(diǎn)，則立即將此節(jié)點(diǎn)加入網(wǎng)頁(yè)塊池。 5 如果遇到B型節(jié)點(diǎn)，則判斷該節(jié)點(diǎn)內(nèi)部的文字長(zhǎng)度是否已超過(guò)閾值，或者該節(jié)點(diǎn)內(nèi)部的L型節(jié)點(diǎn)比例是否超過(guò)閾值，如果滿足上述兩個(gè)條件之一，則將此節(jié)點(diǎn)加入網(wǎng)頁(yè)塊池；否則將其內(nèi)部文字長(zhǎng)度信息和自身信息向父節(jié)點(diǎn)傳遞，然后將父節(jié)點(diǎn)加入當(dāng)前節(jié)點(diǎn)隊(duì)列，回到2。 6 如果遇到L型節(jié)點(diǎn)，則將其內(nèi)部文字長(zhǎng)度信息和其自身信息向父節(jié)點(diǎn)傳遞，然后將父節(jié)點(diǎn)加入當(dāng)前節(jié)點(diǎn)隊(duì)列，回到2。 7 如果遇到D型或A型節(jié)點(diǎn)，則將其內(nèi)部文字長(zhǎng)度信息向父節(jié)點(diǎn)傳遞，然后將父節(jié)點(diǎn)加入當(dāng)前節(jié)點(diǎn)隊(duì)列，回到2。 8 當(dāng)前節(jié)點(diǎn)隊(duì)列為空時(shí)，遍歷結(jié)束，算法終止。 END

48、 _________________________________________________________________ 網(wǎng)頁(yè)塊池中的網(wǎng)頁(yè)塊是以QuarkElement的格式存儲(chǔ)，而QuarkElement類中包括原來(lái)的html子樹(shù)的DomTree結(jié)構(gòu)和其他相關(guān)信息，同時(shí)在上述遍歷的過(guò)程中，即使有的網(wǎng)頁(yè)塊從html結(jié)構(gòu)上來(lái)說(shuō)包含在更高層的網(wǎng)頁(yè)塊之下，但在QuarkElement中也消除了包含關(guān)系，所有網(wǎng)頁(yè)塊都互相獨(dú)立，互不包含。 3.2 網(wǎng)頁(yè)主題內(nèi)容提取 算法主體在QuarkAnalyzer類中。采用了基于規(guī)則和基于Bayes的語(yǔ)義分析相交的方法，也就是分別用基

49、于文本相似度的方法和基于Bayes的方法判斷每個(gè)網(wǎng)頁(yè)塊的類型（是不是主題塊），然后對(duì)它們求交集，只有兩個(gè)方法共同認(rèn)定的主題內(nèi)容塊才能最終被認(rèn)定。 QuarkAnalyzer算法的核心偽碼如下： _________________________________________________________________ 第一步，基于文本相似度的方法： 1、首先，把所有網(wǎng)頁(yè)塊中，文本長(zhǎng)度最大的那個(gè)網(wǎng)頁(yè)塊判定為主題內(nèi)容塊。 2、然后用其余網(wǎng)頁(yè)塊逐個(gè)與最大的網(wǎng)頁(yè)塊比較文本相似度。文本相似度的計(jì)算如下： 2.1 將兩個(gè)網(wǎng)頁(yè)塊分別切詞，去除停用詞后，存儲(chǔ)成token流。

50、 2.2 對(duì)兩個(gè)token流分別排序。 2.3 對(duì)排序后的兩個(gè)token流計(jì)算token的重復(fù)數(shù)。 2.4 用token的重復(fù)數(shù)除以較小的token流中的token個(gè)數(shù)，得到兩個(gè)網(wǎng)頁(yè)塊的文本相似度。 3、若文本相似度大于一個(gè)閾值，則該網(wǎng)頁(yè)塊也判定為主題內(nèi)容塊。 第二步，基于Bayes的方法： 根據(jù)下面列出的7項(xiàng)先驗(yàn)概率和該網(wǎng)頁(yè)塊相對(duì)應(yīng)的這7項(xiàng)特性的（0，1）值，利用Bayes概率的計(jì)算公式，計(jì)算出每個(gè)網(wǎng)頁(yè)塊是不是主題內(nèi)容塊的后驗(yàn)概率。若該后驗(yàn)概率大于0.5，則判定該網(wǎng)頁(yè)塊為主題內(nèi)容塊，否則反之。 第三步，求交。 兩個(gè)方法共同判定的主題內(nèi)容塊即為最后認(rèn)定的主題

51、內(nèi)容塊。 _________________________________________________________________ 其中Bayes方法的各先驗(yàn)概率事先用手工標(biāo)記的樣本網(wǎng)頁(yè)計(jì)算得到，結(jié)果如下： 在該網(wǎng)頁(yè)塊為主題內(nèi)容塊的條件下， # 該塊中包含定制標(biāo)簽的概率 p1_costomizedTag = 0.29; # 該塊中包含常見(jiàn)噪音詞并且文本長(zhǎng)度小于100的概率 p1_noise = 0.04; # 該塊中每10個(gè)字符中的標(biāo)點(diǎn)符號(hào)數(shù)大于0.3的概率 p1_punctuationScale = 0.85; # 該塊中標(biāo)點(diǎn)符號(hào)總數(shù)

52、大于4的概率 p1_punctuation = 0.77 # 該塊中非錨接文本的長(zhǎng)度大于200的概率 p1_size = 0.84 # 該塊中鏈接數(shù)量大于20的概率 p1_linkNum = 0.10; # 該塊中錨接文本和非錨接文本的長(zhǎng)度之比大于0.3 p1_scale = 0.08; 在該網(wǎng)頁(yè)塊為非主題內(nèi)容塊的條件下， # 該塊中包含定制標(biāo)簽的概率 p2_costomizedTag = 0.01; # 該塊中包含常見(jiàn)噪音詞并且文本長(zhǎng)度小于100的概率 p1_noise = 0.45; # 該塊中每10個(gè)字符中的標(biāo)

53、點(diǎn)符號(hào)數(shù)大于0.3的概率 p2_punctuationScale = 0.25; # 該塊中標(biāo)點(diǎn)符號(hào)總數(shù)大于4的概率 p2_punctuation = 0.34 # 該塊中非錨接文本的長(zhǎng)度大于200的概率 p2_size = 0.06 # 該塊中鏈接數(shù)量大于20的概率 p2_linkNum = 0.71; # 該塊中錨接文本和非錨接文本的長(zhǎng)度之比大于0.3 p2_scale = 0.85; 網(wǎng)頁(yè)塊為主題內(nèi)容塊的概率： p_isContent = 0.16; 網(wǎng)頁(yè)塊為非主題內(nèi)容塊的概率： p_isNoise = 1 - p_isCo

54、ntent; 3.3 算法效果演示 為了檢驗(yàn)上述算法的效果，除了下一章會(huì)提到的評(píng)測(cè)程序外，還可以用QuarkHtmlBuilder類所編寫的演示程序以及自搭的Apache服務(wù)器上的python腳本來(lái)查看網(wǎng)頁(yè)分塊后和主題信息提取后的效果。限于篇幅，這里就不再詳細(xì)介紹算法的細(xì)節(jié)，但是附有幾張對(duì)照?qǐng)D片，以利說(shuō)明。 第一幅圖： 這是用python腳本寫的一個(gè)在瀏覽器上查看網(wǎng)頁(yè)主題內(nèi)容提取效果的demo，可以選擇用PageModel的算法（即Quark模塊），也可以選擇用SiteModel的算法，點(diǎn)擊submit按鈕，就可以出現(xiàn)手工標(biāo)記的主題內(nèi)容，和程序判斷的主題內(nèi)容的對(duì)比畫

55、面。由于時(shí)間關(guān)系，該Demo比較粗糙，沒(méi)有過(guò)多修飾。Submit后的效果圖見(jiàn)后面的第五幅圖。 第一幅圖：這是從新浪網(wǎng)上保存的一個(gè)新聞網(wǎng)頁(yè)。顯然，其主題內(nèi)容信息塊應(yīng)該是屏幕中左部的大塊文字內(nèi)容。在處理這種類型的新聞網(wǎng)頁(yè)時(shí)，算法的效率很高，但事實(shí)上，Quark模塊還可以處理更復(fù)雜的網(wǎng)頁(yè)類型。 第二幅圖：這是網(wǎng)頁(yè)分塊之后的示意圖。從圖中可以看出，紅色、綠色、紫色的網(wǎng)頁(yè)塊間雜排列，就像地圖一樣，每一種顏色表示一個(gè)被識(shí)別出的網(wǎng)頁(yè)塊。圖中沒(méi)有顏色，依舊是藍(lán)色的鏈接色的部分是新浪網(wǎng)動(dòng)態(tài)生成的內(nèi)容，在html源代碼中并不存在，所以沒(méi)有被標(biāo)上字體顏色。 第三幅圖：這是網(wǎng)頁(yè)正文提取之

56、后的示意圖。圖中紅色的部分為QuarkAnalyzer識(shí)別的正文內(nèi)容，綠色部分為其識(shí)別的相關(guān)鏈接，其余紫色部分為噪音內(nèi)容。從圖中可以看出，就這個(gè)網(wǎng)頁(yè)而言，網(wǎng)頁(yè)主題內(nèi)容的提取基本成功了。 第五幅圖：這是第一幅圖所示Demo的結(jié)果界面截圖，可見(jiàn)，圖片上方是手工標(biāo)注的文字內(nèi)容，共720個(gè)字符。圖片下方是程序生成的文字內(nèi)容，共628個(gè)字符。兩部分內(nèi)容大致相等，說(shuō)明網(wǎng)頁(yè)主題內(nèi)容提取成功。 第 4 章 SEWM2008中文Web信息檢索評(píng)測(cè) 4.1 評(píng)測(cè)任務(wù)介紹 SEWM中文Web信息檢索評(píng)測(cè)[6]是由北京大學(xué)網(wǎng)絡(luò)實(shí)驗(yàn)室主辦的中文Web檢索評(píng)測(cè)項(xiàng)目

57、，自2004年起，在SEWM會(huì)議中已連續(xù)舉辦了五屆，今年（2008年）是第五屆。其目標(biāo)在于為中文信息檢索領(lǐng)域的研究人員提供一個(gè)標(biāo)準(zhǔn)的評(píng)測(cè)平臺(tái)，希望在國(guó)內(nèi)外各個(gè)研究小組的共同參與下建立并完善以中文為主的網(wǎng)頁(yè)測(cè)試集CWT(Chinese Web Test collection)，解決支持中文WEB研究的基礎(chǔ)設(shè)施建設(shè)和應(yīng)用中的基本方法與關(guān)鍵技術(shù)，一起推動(dòng)中文Web信息檢索技術(shù)的發(fā)展。 SEWM2008中文Web信息檢索評(píng)測(cè)有三個(gè)任務(wù)： 主題型網(wǎng)頁(yè)發(fā)現(xiàn)和網(wǎng)頁(yè)內(nèi)容信息塊發(fā)現(xiàn)，非網(wǎng)頁(yè)數(shù)字資源分類和垃圾郵件過(guò)濾，其中前兩個(gè)任務(wù)主要由何靖師兄設(shè)計(jì)，由我處理各參賽隊(duì)伍提交的數(shù)據(jù)并給出評(píng)測(cè)結(jié)果。本屆評(píng)測(cè)采用

58、的數(shù)據(jù)集是CWT70th。文檔集數(shù)據(jù)格式參見(jiàn)[7]。 由于本次評(píng)測(cè)任務(wù)的設(shè)計(jì)和上文提到的天網(wǎng)Quark模塊關(guān)系密切，評(píng)測(cè)所使用的程序就是天網(wǎng)Quark模塊中QuarkEvaluation類的python版本的代碼，同時(shí)天網(wǎng)Quark模塊的一個(gè)稍早期版本也參加了第二個(gè)任務(wù)關(guān)于網(wǎng)頁(yè)主題內(nèi)容的評(píng)測(cè)，所以也可以作為天網(wǎng)Quark模塊的一個(gè)實(shí)驗(yàn)結(jié)果，檢驗(yàn)第三章提到的算法的效率。 4.1.1 主題型網(wǎng)頁(yè)發(fā)現(xiàn)任務(wù) 主題型網(wǎng)頁(yè)是指通過(guò)文字描述了一件或多件事物，具有一定主題的網(wǎng)頁(yè)。如一張具體的新聞網(wǎng)頁(yè)就是典型的主題型網(wǎng)頁(yè)。 下面是對(duì)主題型網(wǎng)頁(yè)的一個(gè)補(bǔ)充定義： 1、僅由圖片，flash，網(wǎng)絡(luò)視頻等

59、構(gòu)成主題塊的網(wǎng)頁(yè)，除非亦包括獨(dú)立成段的文字性描述信息，否則不屬于主題型網(wǎng)頁(yè)。 2、某些導(dǎo)航型網(wǎng)頁(yè)，如同類軟件下載網(wǎng)頁(yè)中，雖然對(duì)每個(gè)鏈接都使用了適量文字來(lái)介紹，從而文字比例比較高，但也應(yīng)該算作非主題型網(wǎng)頁(yè)。 3、錯(cuò)誤網(wǎng)頁(yè)，空網(wǎng)頁(yè)，垃圾網(wǎng)頁(yè)，Spam網(wǎng)頁(yè)等屬于非主題型網(wǎng)頁(yè)。 4、論壇、博客網(wǎng)頁(yè)屬于主題型網(wǎng)頁(yè)，但沒(méi)有主貼，只包括無(wú)意義回復(fù)語(yǔ)句的網(wǎng)頁(yè)屬于非主題型網(wǎng)頁(yè)。 任務(wù)評(píng)測(cè)根據(jù)準(zhǔn)確度、召回率和Macro-F1三個(gè)指標(biāo)，它們的定義如下： 4.1.2 網(wǎng)頁(yè)內(nèi)容信息發(fā)現(xiàn)任務(wù) 在一個(gè)主題型的網(wǎng)頁(yè)中， 一般會(huì)包括主題內(nèi)容信息，噪音信息，和相關(guān)鏈接信息。本項(xiàng)任務(wù)

60、的目的在于找出主題型網(wǎng)頁(yè)中的主題內(nèi)容信息。 噪音信息定義： a. 與網(wǎng)頁(yè)主旨內(nèi)容不相關(guān)的信息 b. 由網(wǎng)站提供的內(nèi)容模板信息 c. 廣告信息 d. 腳本程序信息 相關(guān)鏈接定義： 指向與本網(wǎng)頁(yè)相關(guān)網(wǎng)頁(yè)的鏈接，如新聞網(wǎng)頁(yè)下方的相關(guān)新聞鏈接。 補(bǔ)充定義： 1、 新聞網(wǎng)頁(yè)的內(nèi)容信息應(yīng)包括出現(xiàn)在頁(yè)面里的標(biāo)題，時(shí)間，通訊社，記者名等信息。 2、一個(gè)網(wǎng)頁(yè)中的內(nèi)容信息不一定只有一塊，可能有多塊，甚至可能是零散分布的文字段。 3、無(wú)意義的論壇回帖（如”頂”等）不屬于內(nèi)容信息，但有一定內(nèi)容的論壇回帖屬于內(nèi)容信息。 4、相關(guān)鏈接不算內(nèi)容信息。 任務(wù)評(píng)測(cè)根據(jù)準(zhǔn)確度、召回率和Mac

61、ro-F1三個(gè)指標(biāo)，它們的定義如下： 4.2 評(píng)測(cè)格式 評(píng)測(cè)要求參加評(píng)測(cè)單位以一定的格式提交，每個(gè)評(píng)測(cè)任務(wù)接受參加者的一到二組檢索結(jié)果。具體要求如下： 主題型網(wǎng)頁(yè)發(fā)現(xiàn)：提交一個(gè)純文本文件，包含所有找到的主題網(wǎng)頁(yè)，每個(gè)網(wǎng)頁(yè)的編號(hào)占一行。如： CWTquark080103-00000010 CWTquark080103-00000019 網(wǎng)頁(yè)內(nèi)信息塊發(fā)現(xiàn)：只需要把正文內(nèi)容找出來(lái)即可， 一個(gè)網(wǎng)頁(yè)可能包括多個(gè)彼此不連續(xù)的正文內(nèi)容， 正文內(nèi)容可以包括包含內(nèi)容標(biāo)簽， 也可以不包含內(nèi)容標(biāo)簽。 結(jié)果的格式如下： Document-Num

62、ber Start-Position Length三元組 其中Document-Number是網(wǎng)頁(yè)的編號(hào)，Start-Position是某段正文內(nèi)容在原網(wǎng)頁(yè)文檔中的開(kāi)始位置（網(wǎng)頁(yè)的起始位置從0開(kāi)始計(jì)算）， Length是該段正文內(nèi)容的長(zhǎng)度。 一個(gè)網(wǎng)頁(yè)可以有多個(gè)正文內(nèi)容段， 因此可以有類似下面的情況： CWTquark080103-00000001 200 300 // 該網(wǎng)頁(yè)中的第一段正文內(nèi)容 CWTquark080103-00000001 450 500 // 該網(wǎng)頁(yè)中的第二段正文內(nèi)容 4.3 評(píng)測(cè)結(jié)果 本次評(píng)測(cè)任務(wù)最終共有七支參賽隊(duì)伍，提交了12組結(jié)果。 1、大連理

63、工大學(xué)信息檢索實(shí)驗(yàn)室 DLUT1 DLUT2 2、四川大學(xué)計(jì)算機(jī)學(xué)院數(shù)據(jù)庫(kù)與知識(shí)工程研究所 SCU1 SCU2 3、華南理工大學(xué)廣東省計(jì)算機(jī)網(wǎng)絡(luò)重點(diǎn)實(shí)驗(yàn)室一隊(duì) SCUT1 SCUT2 4、華南理工大學(xué)廣東省計(jì)算機(jī)網(wǎng)絡(luò)重點(diǎn)實(shí)驗(yàn)室二隊(duì) SCUT3 SCUT4 5、山東大學(xué)信息檢索實(shí)驗(yàn)室 SDU1 SDU2 6、人民大學(xué)信息學(xué)院 RUC 7、北京大學(xué)網(wǎng)絡(luò)實(shí)

64、驗(yàn)室 PKU 4.3.1 主題型網(wǎng)頁(yè)發(fā)現(xiàn)任務(wù)評(píng)測(cè)結(jié)果 在數(shù)據(jù)集CWT70th中的所有71502個(gè)網(wǎng)頁(yè)中，有71281個(gè)不重復(fù)URL。 在這71281個(gè)網(wǎng)頁(yè)中，隨機(jī)抽取了300個(gè)URL，人工判斷其類型。為了消除對(duì)主題型網(wǎng)頁(yè)認(rèn)定上的分歧，在300個(gè)URL中去除了部分混合型以及不易判別類型的網(wǎng)頁(yè)，共得到227個(gè)確定類型的網(wǎng)頁(yè)，其中包括138個(gè)主題型網(wǎng)頁(yè)，89個(gè)非主題型網(wǎng)頁(yè)，主題型網(wǎng)頁(yè)數(shù)目/非主題型網(wǎng)頁(yè)數(shù)目 = 1.5505618，經(jīng)驗(yàn)證，大致符合原網(wǎng)頁(yè)集中的類型分布。利用該227個(gè)網(wǎng)頁(yè)，評(píng)測(cè)各組參賽數(shù)據(jù)。 雖然我們的樣本數(shù)偏少，但由于樣本中的類型分布大致符合原網(wǎng)頁(yè)集

65、中的類型分布，所以評(píng)測(cè)結(jié)果基本反映了各組的實(shí)際分類質(zhì)量，只不過(guò)沒(méi)有形成明顯差距。華南理工一隊(duì)和大連理工的分類質(zhì)量相對(duì)最佳，而人民大學(xué)和山東大學(xué)提交的三個(gè)結(jié)果，分別將71502個(gè)網(wǎng)頁(yè)中的66498、56509、55111個(gè)判斷為了主題型網(wǎng)頁(yè)，過(guò)高地估計(jì)了主題型網(wǎng)頁(yè)的比例，從而大大降低了精度，但值得一提的是，山東大學(xué)提交的結(jié)果2獲得了最高的召回率。 評(píng)測(cè)結(jié)果如下： TEAM Macro-Precision Macro-Recall Macro-F1 DLUT1 0.888888888889 0.869565217391 0.879120879121 DLUT2 0.895

66、52238806 0.869565217391 0.882352941176 SCU1 0.846153846154 0.876811594203 0.861209964413 SCU2 0.840277777778 0.876811594203 0.858156028369 SCUT1 0.883211678832 0.876811594203 0.88 SCUT2 0.889705882353 0.876811594203 0.883211678832 SCUT3 0.82119205298 0.898550724638 0.858131487889 SCUT4 0.794871794872 0.898550724638 0.843537414966 SDU1 0.78125 0.905797101449 0.838926174497 SDU2 0.774566473988 0.971014492754 0.861736334405 RUC 0.670103092784 0.942028985507