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

1、 本科生畢業(yè)論文 題目：(中文) 大規(guī)模網(wǎng)頁模塊識(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)頁信息提取算法的基礎(chǔ)上，通過為所有符合W3C規(guī)范的Html標(biāo)簽分類，逐個(gè)分析各Html標(biāo)簽所包含的語義信息，細(xì)化規(guī)則設(shè)置，實(shí)現(xiàn)了一種自底向上的無信息遺漏的網(wǎng)頁分塊算法，并在此基礎(chǔ)上，利用統(tǒng)計(jì)方法得到詳細(xì)的概率分布數(shù)據(jù)，實(shí)現(xiàn)了文本相似度比較和Bayes后驗(yàn)概率估計(jì)兩種網(wǎng)頁主題內(nèi)容信息塊識(shí)別算法，并將其求交，提高了主題內(nèi)容信息塊的識(shí)別精確度。 上述算法已集成到天網(wǎng)搜索引擎平臺(tái)的網(wǎng)頁預(yù)處理模塊中，并且在SEWM 2008會(huì)議中，以這套算法為框架，組織了主題型網(wǎng)頁識(shí)別和網(wǎng)頁主題內(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)頁塊級(jí)別PageRank算法，命名為QuarkRank算法。實(shí)際檢驗(yàn)表明，該套算法具有很好的適應(yīng)性與可擴(kuò)展性，并達(dá)到了很高的精度和召回率。 關(guān)鍵詞：網(wǎng)頁分塊 信息提取 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 基于語義的網(wǎng)頁信息提取算法 5 2.2 基于視覺的網(wǎng)頁分塊算法 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)頁分塊算法 13 3.2 網(wǎng)頁主題內(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)頁發(fā)現(xiàn)任務(wù) 23 4.1.2 網(wǎng)頁內(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)頁發(fā)現(xiàn)任務(wù)評(píng)測(cè)結(jié)果 26 4.3.2 網(wǎng)頁內(nèi)容信息發(fā)現(xiàn)任務(wù)評(píng)測(cè)結(jié)果 28 4.4 評(píng)測(cè)綜述 31 第 5 章 網(wǎng)頁分塊的分布式應(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無以制勝。互聯(lián)網(wǎng)的高速發(fā)展，改變了我們的生活方式，打破了我們的時(shí)空界限，重塑著我們的社會(huì)形態(tài)。經(jīng)濟(jì)、政治、學(xué)習(xí)、工作、生活、娛樂等等各個(gè)層面都在Web網(wǎng)絡(luò)中激蕩起伏，深刻地影響著人類的未來。而Web網(wǎng)絡(luò)的靈魂，就是流動(dòng)在其中的無窮無盡的信息。Web2.0的意義就在于 網(wǎng)絡(luò)內(nèi)容的提供方從商人和專業(yè)人員轉(zhuǎn)變?yōu)榫W(wǎng)絡(luò)上的每一個(gè)普通用戶，從而幾何級(jí)數(shù)地增長(zhǎng)了Web的信息量。然而信息量的增大，隨著而來的就是存儲(chǔ)成本的增大和信息提取難度的增大，如何有效的獲取和整合Web信息成為大家面對(duì)的共同課題。 傳統(tǒng)意義上，整個(gè)Web

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

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

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

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

15、求無關(guān)的語義塊。 在這篇論文中，第二章介紹了本文的相關(guān)研究工作，包括常見的網(wǎng)頁分塊和信息提取算法、基于視覺的網(wǎng)頁分塊算法，以及網(wǎng)頁分塊的一個(gè)應(yīng)用Block Level PageRank算法；第三章介紹了我實(shí)現(xiàn)的網(wǎng)頁分塊和主題信息提取算法——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 基于語義的網(wǎng)頁信息提取算法 由于對(duì)Web頁面有效分塊之后可以

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

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

18、ed template[1]的論文使用正則表達(dá)式來提取重復(fù)模式，從而更適應(yīng)網(wǎng)頁間的細(xì)微變化，增加了Site-Level的召回率。 Page-Level的算法在處理大型網(wǎng)站的網(wǎng)頁時(shí)效率常常不如Site-Level，但優(yōu)勢(shì)在于靈活，不受網(wǎng)頁類型限制。它只利用單個(gè)頁面內(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子樹，來完成分塊工作。這一方法雖然簡(jiǎn)單而易于實(shí)

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

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

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

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

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

24、覽器，因操作系統(tǒng)，甚至因硬件而異。為了得到網(wǎng)頁的完整視覺信息，必須完全下載該網(wǎng)頁所鏈接的CSS文件，JavaScript文件，圖片文件等等，然后調(diào)用瀏覽器內(nèi)核代碼渲染這些網(wǎng)頁文件，最后從瀏覽器內(nèi)核代碼的接口中得到每個(gè)HTML標(biāo)簽的視覺信息。整個(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）瀏覽器的開源代碼。但Mozilla代碼并沒有針對(duì)網(wǎng)頁視覺信息提取這一需求給出方便的使用接口，只有在其渲

25、染完網(wǎng)頁之后再截取視覺信息。我們實(shí)驗(yàn)室的毛先領(lǐng)師兄曾經(jīng)研究Mozilla代碼，完成了這項(xiàng)艱苦的工作，但實(shí)驗(yàn)表明，提取一個(gè)網(wǎng)頁的視覺信息所需時(shí)間超過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頁面為Web圖中

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

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

28、ock矩陣 頁塊（page-to-block）矩陣X的維數(shù)為kn，定義如下： si是page i所包含的block總數(shù)。上面的公式分配給page i中的每一個(gè)block以相同的權(quán)值，顯然是過于簡(jiǎn)化了，不能區(qū)分block的重要程度。在BLPR算法中，采用了一個(gè)簡(jiǎn)單的block重要度區(qū)分的公式，即用block的文字多少和離整個(gè)頁面中心點(diǎn)位置的遠(yuǎn)近來計(jì)算block的重要度。每個(gè)block包含的文本長(zhǎng)度越大，離頁面中心點(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)出不同的語義塊的重要程度的不同。也就是說，當(dāng)用戶點(diǎn)擊頁面中的超鏈接時(shí)，更偏好選擇重要的語義塊中的URL。所以在BLPR中，WP的定義

30、為： 即。 WP(α, β)可以理解為是從page α 開始，以page α中包含的各語義塊為媒介，跳轉(zhuǎn)到page β的概率。 2.3.1.4 Block Graph WB的定義為： 即。 WB(a,b)可以理解為用戶從block a開始，以包含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，而BLPR算法基于上面提到的GP。BLPR

31、算法的數(shù)學(xué)計(jì)算公式如下： 其中p為結(jié)果向量，共n維，每一維代表一個(gè)網(wǎng)頁的PageRank值。ε為適配參數(shù)，以1-ε的概率，用戶在當(dāng)前頁面中隨機(jī)選擇一個(gè)超鏈接，跳轉(zhuǎn)到該鏈接指向的頁面；以ε的概率，用戶從所有網(wǎng)頁中隨機(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àn)樗挠?jì)算基于網(wǎng)頁中各語義塊

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

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

34、龐大的系統(tǒng)，并且一直在不停的有新算法，新需求的加入，所以對(duì)數(shù)據(jù)的要求也會(huì)一直變化。而基于對(duì)原始網(wǎng)頁數(shù)據(jù)集中處理的原則，為了應(yīng)對(duì)下游模塊可能提取的新的數(shù)據(jù)訪問需求，Quark模塊必須具備良好的可擴(kuò)展性，并且提供盡量多的各種類型的數(shù)據(jù)訪問接口。同時(shí)由于實(shí)驗(yàn)室人員的不固定性，代碼的維護(hù)十分重要。我自己在剛開始閱讀舊有的天網(wǎng)搜索引擎相關(guān)代碼的時(shí)候，就常有十分難懂的感覺，無法復(fù)用已有代碼，只好自己重新編寫。而正由于Quark模塊的可擴(kuò)展性要求，所以它的代碼的可閱讀性也十分重要，在編寫的過程中，我盡量注意了這一點(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)頁的處理和數(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)頁為輸入，建立Html的Dom Tree；另一個(gè)是存儲(chǔ)分好的網(wǎng)頁塊（在我們的系統(tǒng)中

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

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

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

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

41、"FIELDSET", "CENTER", "NOFRAMES", "NOSCRIPT", "PRE", "BODY", "HTML" 這里需要注意的是像BODY，HTML兩個(gè)標(biāo)簽也作為B型標(biāo)簽，原因是這樣可以防止分塊之后網(wǎng)頁內(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)頁的顯示效果，改變文字布局。如果一顆html子樹中包含多個(gè)L型標(biāo)簽，則該子樹單獨(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)頁布局，所以不影響網(wǎng)頁分塊。包括： "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)頁布局的影響體現(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)頁分塊會(huì)有些不同的要求。比如我們實(shí)驗(yàn)室的WebDigest小組在進(jìn)行新聞網(wǎng)頁的數(shù)據(jù)挖掘的工作中，需要使用到網(wǎng)頁分塊，但

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

46、html根節(jié)點(diǎn)時(shí)，算法結(jié)束，網(wǎng)頁分塊完畢。QuarkRecognizer算法的核心偽碼如下： _________________________________________________________________ ALGORITHM QuarkRecognizer (DomTree tree，TagList CType) INPUT : 某單個(gè)網(wǎng)頁構(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ì)列，開始自底向上遍歷。 2 取當(dāng)前節(jié)點(diǎn)隊(duì)列的第一個(gè)節(jié)點(diǎn)。 3 如果遇到S型節(jié)點(diǎn)，則立即

47、將此節(jié)點(diǎn)加入網(wǎng)頁塊池。 4 如果遇到C型節(jié)點(diǎn)，則立即將此節(jié)點(diǎn)加入網(wǎng)頁塊池。 5 如果遇到B型節(jié)點(diǎn)，則判斷該節(jié)點(diǎn)內(nèi)部的文字長(zhǎng)度是否已超過閾值，或者該節(jié)點(diǎn)內(nèi)部的L型節(jié)點(diǎn)比例是否超過閾值，如果滿足上述兩個(gè)條件之一，則將此節(jié)點(diǎn)加入網(wǎng)頁塊池；否則將其內(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)頁塊池中的網(wǎng)頁塊是以QuarkElement的格式存儲(chǔ)，而QuarkElement類中包括原來的html子樹的DomTree結(jié)構(gòu)和其他相關(guān)信息，同時(shí)在上述遍歷的過程中，即使有的網(wǎng)頁塊從html結(jié)構(gòu)上來說包含在更高層的網(wǎng)頁塊之下，但在QuarkElement中也消除了包含關(guān)系，所有網(wǎng)頁塊都互相獨(dú)立，互不包含。 3.2 網(wǎng)頁主題內(nèi)容提取 算法主體在QuarkAnalyzer類中。采用了基于規(guī)則和基于Bayes的語義分析相交的方法，也就是分別用基

49、于文本相似度的方法和基于Bayes的方法判斷每個(gè)網(wǎng)頁塊的類型（是不是主題塊），然后對(duì)它們求交集，只有兩個(gè)方法共同認(rèn)定的主題內(nèi)容塊才能最終被認(rèn)定。 QuarkAnalyzer算法的核心偽碼如下： _________________________________________________________________ 第一步，基于文本相似度的方法： 1、首先，把所有網(wǎng)頁塊中，文本長(zhǎng)度最大的那個(gè)網(wǎng)頁塊判定為主題內(nèi)容塊。 2、然后用其余網(wǎng)頁塊逐個(gè)與最大的網(wǎng)頁塊比較文本相似度。文本相似度的計(jì)算如下： 2.1 將兩個(gè)網(wǎng)頁塊分別切詞，去除停用詞后，存儲(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)頁塊的文本相似度。 3、若文本相似度大于一個(gè)閾值，則該網(wǎng)頁塊也判定為主題內(nèi)容塊。 第二步，基于Bayes的方法： 根據(jù)下面列出的7項(xiàng)先驗(yàn)概率和該網(wǎng)頁塊相對(duì)應(yīng)的這7項(xiàng)特性的（0，1）值，利用Bayes概率的計(jì)算公式，計(jì)算出每個(gè)網(wǎng)頁塊是不是主題內(nèi)容塊的后驗(yàn)概率。若該后驗(yàn)概率大于0.5，則判定該網(wǎng)頁塊為主題內(nèi)容塊，否則反之。 第三步，求交。 兩個(gè)方法共同判定的主題內(nèi)容塊即為最后認(rèn)定的主題

51、內(nèi)容塊。 _________________________________________________________________ 其中Bayes方法的各先驗(yàn)概率事先用手工標(biāo)記的樣本網(wǎng)頁計(jì)算得到，結(jié)果如下： 在該網(wǎng)頁塊為主題內(nèi)容塊的條件下， # 該塊中包含定制標(biāo)簽的概率 p1_costomizedTag = 0.29; # 該塊中包含常見噪音詞并且文本長(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)頁塊為非主題內(nèi)容塊的條件下， # 該塊中包含定制標(biāo)簽的概率 p2_costomizedTag = 0.01; # 該塊中包含常見噪音詞并且文本長(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)頁塊為主題內(nèi)容塊的概率： p_isContent = 0.16; 網(wǎng)頁塊為非主題內(nèi)容塊的概率： p_isNoise = 1 - p_isCo

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

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

56、后的示意圖。圖中紅色的部分為QuarkAnalyzer識(shí)別的正文內(nèi)容，綠色部分為其識(shí)別的相關(guān)鏈接，其余紫色部分為噪音內(nèi)容。從圖中可以看出，就這個(gè)網(wǎng)頁而言，網(wǎng)頁主題內(nèi)容的提取基本成功了。 第五幅圖：這是第一幅圖所示Demo的結(jié)果界面截圖，可見，圖片上方是手工標(biāo)注的文字內(nèi)容，共720個(gè)字符。圖片下方是程序生成的文字內(nèi)容，共628個(gè)字符。兩部分內(nèi)容大致相等，說明網(wǎng)頁主題內(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)，希望在國內(nèi)外各個(gè)研究小組的共同參與下建立并完善以中文為主的網(wǎng)頁測(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)頁發(fā)現(xiàn)和網(wǎng)頁內(nèi)容信息塊發(fā)現(xiàn)，非網(wǎng)頁數(shù)字資源分類和垃圾郵件過濾，其中前兩個(gè)任務(wù)主要由何靖師兄設(shè)計(jì)，由我處理各參賽隊(duì)伍提交的數(shù)據(jù)并給出評(píng)測(cè)結(jié)果。本屆評(píng)測(cè)采用

58、的數(shù)據(jù)集是CWT70th。文檔集數(shù)據(jù)格式參見[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)頁主題內(nèi)容的評(píng)測(cè)，所以也可以作為天網(wǎng)Quark模塊的一個(gè)實(shí)驗(yàn)結(jié)果，檢驗(yàn)第三章提到的算法的效率。 4.1.1 主題型網(wǎng)頁發(fā)現(xiàn)任務(wù) 主題型網(wǎng)頁是指通過文字描述了一件或多件事物，具有一定主題的網(wǎng)頁。如一張具體的新聞網(wǎng)頁就是典型的主題型網(wǎng)頁。 下面是對(duì)主題型網(wǎng)頁的一個(gè)補(bǔ)充定義： 1、僅由圖片，flash，網(wǎng)絡(luò)視頻等

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

60、的目的在于找出主題型網(wǎng)頁中的主題內(nèi)容信息。 噪音信息定義： a. 與網(wǎng)頁主旨內(nèi)容不相關(guān)的信息 b. 由網(wǎng)站提供的內(nèi)容模板信息 c. 廣告信息 d. 腳本程序信息 相關(guān)鏈接定義： 指向與本網(wǎng)頁相關(guān)網(wǎng)頁的鏈接，如新聞網(wǎng)頁下方的相關(guān)新聞鏈接。 補(bǔ)充定義： 1、 新聞網(wǎng)頁的內(nèi)容信息應(yīng)包括出現(xiàn)在頁面里的標(biāo)題，時(shí)間，通訊社，記者名等信息。 2、一個(gè)網(wǎng)頁中的內(nèi)容信息不一定只有一塊，可能有多塊，甚至可能是零散分布的文字段。 3、無意義的論壇回帖（如”頂”等）不屬于內(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)頁發(fā)現(xiàn)：提交一個(gè)純文本文件，包含所有找到的主題網(wǎng)頁，每個(gè)網(wǎng)頁的編號(hào)占一行。如： CWTquark080103-00000010 CWTquark080103-00000019 網(wǎng)頁內(nèi)信息塊發(fā)現(xiàn)：只需要把正文內(nèi)容找出來即可， 一個(gè)網(wǎng)頁可能包括多個(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)頁的編號(hào)，Start-Position是某段正文內(nèi)容在原網(wǎng)頁文檔中的開始位置（網(wǎng)頁的起始位置從0開始計(jì)算）， Length是該段正文內(nèi)容的長(zhǎng)度。 一個(gè)網(wǎng)頁可以有多個(gè)正文內(nèi)容段， 因此可以有類似下面的情況： CWTquark080103-00000001 200 300 // 該網(wǎng)頁中的第一段正文內(nèi)容 CWTquark080103-00000001 450 500 // 該網(wǎng)頁中的第二段正文內(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ù)庫與知識(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)頁發(fā)現(xiàn)任務(wù)評(píng)測(cè)結(jié)果 在數(shù)據(jù)集CWT70th中的所有71502個(gè)網(wǎng)頁中，有71281個(gè)不重復(fù)URL。 在這71281個(gè)網(wǎng)頁中，隨機(jī)抽取了300個(gè)URL，人工判斷其類型。為了消除對(duì)主題型網(wǎng)頁認(rèn)定上的分歧，在300個(gè)URL中去除了部分混合型以及不易判別類型的網(wǎng)頁，共得到227個(gè)確定類型的網(wǎng)頁，其中包括138個(gè)主題型網(wǎng)頁，89個(gè)非主題型網(wǎng)頁，主題型網(wǎng)頁數(shù)目/非主題型網(wǎng)頁數(shù)目 = 1.5505618，經(jīng)驗(yàn)證，大致符合原網(wǎng)頁集中的類型分布。利用該227個(gè)網(wǎng)頁，評(píng)測(cè)各組參賽數(shù)據(jù)。 雖然我們的樣本數(shù)偏少，但由于樣本中的類型分布大致符合原網(wǎng)頁集

65、中的類型分布，所以評(píng)測(cè)結(jié)果基本反映了各組的實(shí)際分類質(zhì)量，只不過沒有形成明顯差距。華南理工一隊(duì)和大連理工的分類質(zhì)量相對(duì)最佳，而人民大學(xué)和山東大學(xué)提交的三個(gè)結(jié)果，分別將71502個(gè)網(wǎng)頁中的66498、56509、55111個(gè)判斷為了主題型網(wǎng)頁，過高地估計(jì)了主題型網(wǎng)頁的比例，從而大大降低了精度，但值得一提的是，山東大學(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