【正文】 人民大學(xué)信息學(xué)院 RUC 北京大學(xué)網(wǎng)絡(luò)實(shí)驗(yàn)室 PKU M a c r o Pr e c is io n M a c r o R e c a l lM a c r o F 1 M a c r o Pr e c is io n M a c r o R e c a l l?? ? ? ?2 * * 主題 型網(wǎng)頁發(fā)現(xiàn)任務(wù) 評測結(jié)果 在數(shù)據(jù)集 CWT70th 中的所有 71502 個(gè)網(wǎng)頁中，有 71281 個(gè)不重復(fù) URL。 在這 71281 個(gè)網(wǎng)頁中，隨機(jī)抽取了 300 個(gè) URL，人工判斷其類型。為了消除對主題型網(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ù)目 = ，經(jīng)驗(yàn)證，大致符合原網(wǎng)頁集中的類型分布。利用該 227 個(gè)網(wǎng)頁，評測各組參賽數(shù)據(jù)。 雖然我們的樣本數(shù)偏少，但由于樣本中 的類型分布大致符合原網(wǎng)頁集中的類型分布，所以評測結(jié)果基本反映了各組的實(shí)際分類質(zhì)量，只不過沒有形成明顯差距。華南理工一隊(duì)和大連理工的分類質(zhì)量相對最佳，而人民大學(xué)和山東大學(xué)提交的三個(gè)結(jié)果，分別將 71502 個(gè)網(wǎng)頁中的 6649 5650 55111 個(gè)判斷為了主題型網(wǎng)頁，過高地估計(jì)了主題型網(wǎng)頁的比例，從而大大降低了精度，但值得一提的是，山東大學(xué)提交的結(jié)果 2 獲得了最高的召回率。 評測結(jié)果如下： 主題型網(wǎng)頁發(fā)現(xiàn)任務(wù)評測結(jié)果較好的隊(duì)伍是華南理工一隊(duì)和大連理工， 分別代表了網(wǎng)頁整體性判斷和網(wǎng)頁分塊判斷兩種主要的實(shí)現(xiàn)方法。 網(wǎng)頁整體性判斷方法 以華南理工一隊(duì)的方法最為典型，綜合使用了啟發(fā)式規(guī)則和分類器方法： TEAM MacroPrecision MacroRecall MacroF1 DLUT1 DLUT2 SCU1 SCU2 SCUT1 SCUT2 SCUT3 SCUT4 SDU1 SDU2 RUC 第一步先根據(jù)主題型網(wǎng)頁的重要特征，基于啟發(fā)式規(guī)則判斷； 第二步提取更詳細(xì)的特征信息，用 SVM 分類； 第三步還基于信息塊提取的結(jié)果反饋，進(jìn)一步篩選出主題型網(wǎng)頁。 華南理工一隊(duì)也屬于整體性判斷方法，但只使用了分類器方法；山東大學(xué)隊(duì)則只使用了較簡單的啟發(fā)式規(guī)則 。 網(wǎng)頁分塊判斷方法 以大連理工隊(duì)的方法最為典型，在網(wǎng)頁分塊的基礎(chǔ)上，判斷各個(gè)網(wǎng)頁塊的類型。 如果一個(gè)網(wǎng)頁里都是非主題型塊，則為非主題網(wǎng)頁。若含有主題塊，則為主題型網(wǎng)頁 。其中判斷各個(gè)網(wǎng)頁塊的類型是綜合基于規(guī)則和基于概率的方法，同時(shí)針對本次任務(wù)的網(wǎng)頁特性做了優(yōu)化。 而四川大學(xué)的方法比較特殊，在網(wǎng)頁分塊的基礎(chǔ)上， 使用網(wǎng)頁塊分布的方差和彎曲度屬性 區(qū)分導(dǎo)航型和主題型網(wǎng)頁 ，不足在于使用規(guī)則過少，只使用了網(wǎng)頁塊的文本大小信息。 綜合所有隊(duì)伍提取和使用的特征信息，大致有如下幾類： URL 相 關(guān)的特征信息 包括 URL 中數(shù)字的個(gè)數(shù) 、 URL 的深度 以及 URL 的后綴 。 鏈接相關(guān)的特征信息 包括鏈接數(shù)、 鏈接文字與非鏈接文字比 、 鏈接標(biāo)簽占網(wǎng)頁的所有標(biāo)簽的比率 、 鏈接文本內(nèi)容占全文內(nèi)容的比率 、 非鏈接文字的長度 等等。 其他特征信息 包括 網(wǎng)頁文本內(nèi)容中標(biāo)點(diǎn)符號的個(gè)數(shù) 、正文的文字長度、 特殊標(biāo)簽 （如p, br,h1） 是否出現(xiàn) ，以及包含特殊關(guān)鍵詞與否。 下圖是各組結(jié)果的 MacroF1 值大小的直觀顯示： 網(wǎng)頁 內(nèi)容信息 發(fā)現(xiàn)任務(wù) 評測結(jié)果 我們事先人工標(biāo)記了 71281 個(gè)網(wǎng)頁中的 303 個(gè)主題型網(wǎng)頁，標(biāo)記方法為給html 的 tag 標(biāo)簽添加 quark 屬性，如： div quark=”content” 正文內(nèi)容 /div a quark=”rel_link” href=”” 相關(guān)鏈接 /a div quark=”noise” 噪音內(nèi)容 /div 其中標(biāo)記為 quark=”content”的就是內(nèi)容信息塊； 標(biāo)記為 quark=”rel_link”的 是相關(guān)鏈接； 而標(biāo)記為 quark=”noise”的 則是噪音內(nèi)容。 因?yàn)楦鹘M提 交的結(jié)果只針對第一項(xiàng)任務(wù)中發(fā)現(xiàn)的主題型網(wǎng)頁找出內(nèi)容信息塊，而我們標(biāo)記的 303 個(gè)網(wǎng)頁并沒有被各組一致判定為主題型網(wǎng)頁，只有其中的104 個(gè)網(wǎng)頁被各組一致判定為主題型并提取了內(nèi)容信息塊（其中華南理工二隊(duì)沒有根據(jù)他們第一項(xiàng)任務(wù)里找出的所有主題型網(wǎng)頁來完成第二項(xiàng)任務(wù)，一定程度上影響了各組的重合度）。所以本任務(wù)的評測就依據(jù)這 104 個(gè)標(biāo)記過的主題型網(wǎng)頁，樣本量偏少。 根據(jù)各組提交的格式為（ doc_no start_pos length）的結(jié)果文件，為各組產(chǎn)生出對應(yīng)的 104 個(gè)內(nèi)容信息塊網(wǎng)頁，然后逐一比較標(biāo)記過的網(wǎng)頁與 各組提取的網(wǎng)頁。 從評測結(jié)果可以看出，大連理工提交的結(jié)果 1 評測成績十分優(yōu)異，精度 和F1 值 超過 了 90%。鑒于我們標(biāo)記的樣本集中也可能存在少量的誤標(biāo)的情況，其召回率應(yīng)該也達(dá)到了 90%。 評測結(jié)果如下： 網(wǎng)頁內(nèi)容信息塊發(fā)現(xiàn)任務(wù) 評測結(jié)果較好的隊(duì)伍是大連理工 隊(duì)和我的 Quark模塊。同樣，各隊(duì)的實(shí)現(xiàn)方法可大致分為網(wǎng)頁整體性判斷和網(wǎng)頁分塊判斷兩種。 網(wǎng)頁分塊判斷 其余 各隊(duì)的分塊方法都比較簡單。大連理工提交的兩個(gè)結(jié)果分別采用了以 table、 tr、 td 、 div 四個(gè)標(biāo)簽為分塊節(jié)點(diǎn) ，和僅以 p標(biāo)簽為分塊節(jié)點(diǎn)兩種方法。后者由于過于簡單，實(shí)際評測效果不如前者。而山東大學(xué)提到根據(jù) table， div， td， p等容器標(biāo)簽對網(wǎng)頁分塊，再根據(jù)某種規(guī)則對某些網(wǎng)頁塊進(jìn)行合 并 的改進(jìn)型算法，但不知是否最終實(shí)現(xiàn)。 在噪音過濾，網(wǎng)頁分塊的基礎(chǔ)上，大連理工采用了基于規(guī)則和基于 Bayes的語義分析方法，同時(shí)針對本次任務(wù)的網(wǎng)頁特性做了優(yōu)化，效果優(yōu)異。 但大連理工的這兩種方法有一些重合之處，并且 從 它 提交的結(jié)果內(nèi)容看，對 H1等標(biāo)簽可能做了特殊處理，在他們的工作報(bào)告中沒有提及。 TEAM MacroPrecision MacroRecall MacroF1 DLUT1 DLUT2 SCU1 SCU2 SCUT1 SCUT2 SCUT3 SCUT4 SDU1 SDU2 RUC PKU 6 在網(wǎng)頁分塊的基礎(chǔ)上，山東大學(xué)提 取文字?jǐn)?shù)最多的網(wǎng)頁塊作為網(wǎng)頁內(nèi)容信息塊 ，這一方法的缺點(diǎn)是不能處理含有多個(gè)內(nèi)容信息塊的網(wǎng)頁。 網(wǎng)頁整體性判斷 華南理工一隊(duì)，二隊(duì)采用了整體性判斷方法。 華南理工一隊(duì) 的方法是由葉子節(jié)點(diǎn)開始，向上尋找包含所有有效文本信息的最近節(jié)點(diǎn)。其中有效文本信息的判斷是依靠每個(gè)節(jié)點(diǎn)的文本長度。這個(gè)方法的局限一是不能處理含有多個(gè)內(nèi)容信息塊的網(wǎng)頁，而是不能處理所有網(wǎng)頁，比如表格型網(wǎng)頁需要單獨(dú)處理。 華南理工二隊(duì)采用 DSE 算法， 考察了 URL 相似度對 DSE 的影響 ，通過網(wǎng)頁 間 結(jié)構(gòu)比較 ，并計(jì)算 錨文本與正文塊的比例 來提取內(nèi)容信息塊，算法相對比較完善，但也有對不同類型的網(wǎng)頁處理時(shí)普適性不夠的問題。 其他特殊方法 四川大學(xué)的算法比較特殊，他們認(rèn)為內(nèi)容信息塊在長度上相對孤立，所以使用了基于偏差的 孤立點(diǎn)檢測算法，以塊的大小作為屬性，檢測孤立點(diǎn)，得到的孤立點(diǎn)即內(nèi)容塊。 這個(gè)算法的缺點(diǎn)在于只以內(nèi)容長度作為衡量標(biāo)準(zhǔn)，特征過少。 下圖是各組結(jié)果的直觀顯示： 評測綜述 本次評測從設(shè)計(jì)上和數(shù)據(jù)上還有很多缺憾： 數(shù)據(jù)集的抓取不夠有代表性，集中在幾個(gè)網(wǎng)站，同種類型網(wǎng)頁過多，新聞?lì)惥W(wǎng)頁也過多，一定程度上降低了內(nèi)容提取的難度。 對主題型網(wǎng)頁的定義不夠清晰。比如有的新聞網(wǎng)頁由一幅大圖片和少量文字構(gòu)成主題塊，在現(xiàn)有的單純依靠文字的評測機(jī)制下傾向于認(rèn)為不是主題塊，但事實(shí)上應(yīng)該算是主題塊，而這種網(wǎng)頁也應(yīng)該算是主題型 網(wǎng)頁。又比如很多網(wǎng)頁雖然是一個(gè)鏈接型網(wǎng)頁，但對其中每個(gè)鏈接用了適量文字來介紹，這種網(wǎng)頁雖然文字比例很高，也應(yīng)該算是鏈接型網(wǎng)頁。 對內(nèi)容信息塊的定義不夠清晰。比如論壇或者博客的回帖該不該算作主題型應(yīng)該明確規(guī)定，以后可以考慮將這種類型的網(wǎng)站單獨(dú)作為評測項(xiàng)目，比如分別提取主貼與回帖（提問與解答）的內(nèi)容。又比如相關(guān)鏈接算不算內(nèi)容信息塊，在這次評測中是不算的，以后可以考慮將相關(guān)鏈接的提取也列為評測項(xiàng)目。 由于標(biāo)記樣本網(wǎng)頁工作量很大，而我們事先準(zhǔn)備不夠，所以最后用作評測的樣本網(wǎng)頁數(shù)量較少，從而使得評測結(jié)果可能不夠準(zhǔn) 確。而且在評測過程中發(fā)現(xiàn)，已標(biāo)記的 303 個(gè)網(wǎng)頁，由于標(biāo)記人員工作不夠細(xì)致，質(zhì)量不高，部分存在將噪音內(nèi)容也標(biāo)記為主題內(nèi)容的情況。以后我們應(yīng)該制作更精良和更具有代表性的樣本網(wǎng)頁集。 而 Quark 模塊從本次評測中得到的教育是： 各隊(duì)都沒有一個(gè)詳細(xì)，可操作性強(qiáng)的網(wǎng)頁分塊算法，這一點(diǎn)上， Quark模塊做的比較好。 在網(wǎng)頁主題信息提取方面，大連理工隊(duì)的方法效果比較明顯，所以我從中吸收了他們的長處，在原有的文本相似度 方法 的基礎(chǔ)上，增加了 Bayes方法，并自己定義和計(jì)算了 7 條先驗(yàn)概率， 然后讓兩個(gè)方法的結(jié)果求教，實(shí)驗(yàn) 數(shù)據(jù)顯示， 改進(jìn)后的天網(wǎng) Quark 模塊的評測結(jié)果大大提高，達(dá)到了大連理工隊(duì)的水平。 第 5 章 網(wǎng)頁分塊的 分布式 應(yīng)用 在前面提到的網(wǎng)頁分塊算法的基礎(chǔ)之上，我嘗試了 基于網(wǎng)頁分塊的PageRank 算法，與相關(guān)研究里提到的 BLPR 算法不同的是，我的這項(xiàng)工作是在我們實(shí)驗(yàn)室自己開發(fā)的天網(wǎng)文件系統(tǒng) [8]（ TFS）和分布式計(jì)算平臺(tái)（ MapReduce）上實(shí)現(xiàn)的。 QuarkRank 在 MapReduce 上， QuarkRank 算法主要需要實(shí)現(xiàn)兩個(gè)類，一個(gè)是QuarkRankMapper 類，一個(gè)是 QuarkRankReducer 類。 同時(shí)， 200GB 的原始網(wǎng)頁文件 作為輸入文件，而輸出則是一個(gè)列有所有 URL 的 PageRank 值的文件，輸入與輸出文件都存儲(chǔ)在天網(wǎng)文件系統(tǒng)中，以 最大 64MB 的 數(shù)據(jù)塊的形式存在于整個(gè)機(jī)群中。 由于 QuarkRank 是一個(gè)多輪迭代，直到收斂的算法，所以也要進(jìn)行多輪MapReduce。 所以除了實(shí)現(xiàn) MapReduce 工作類之外，還得自 己編寫 一個(gè) 主控程序中，控制 和 調(diào)用了多輪 MapReduce 任務(wù) ，并決定迭代何時(shí)終止 。 下面是主控程序的核心部分偽碼： _________________________________________________________________ ALGORITHM QuarkRank (TwRawPage Cwt200G) INPUT : 天網(wǎng)原始數(shù)據(jù) BEGIN 預(yù)處理： 將 Cwt200G 處理成 （ URL， 初始 PageRank 值 ， Quark 編號 ， Quark 權(quán)值，該 Quark 的出鏈列表 ） 格式，存到 input 文件中。 Mapper： Mapper 的輸入格式： （ URL， 當(dāng)前 PageRank 值 ， Quark 編號 ， Quark 權(quán)值 ， 該 Quark 的出鏈列表 ） Mapper 的輸出格式有兩種： 第一種： （ URL， Quark 編號 ， Quark 權(quán)值 ， 該 Quark 的出鏈列表 ） 第二種： foreach url in 該 url 的出鏈列表 ： 輸出 （ url， value） ， 其中 value 為根據(jù)該 url 所在的 Quark 的權(quán)值而計(jì)算出的當(dāng)前 URL 的 PageRank 的分配值。 Reducer： Reducer 的輸入格式有兩種： 第一種： （ URL， Quark 編號 ， Quark 權(quán)值 ， 該 Quark 的出鏈列表 ） 第二種： foreach url in 該 url 的出鏈列表： 輸出 （ url， value） ， 其中 value 為根據(jù)該 url 所在的 Quark 的權(quán)值而計(jì)算出的當(dāng)前 URL 的 PageRank 的分配值。 Reducer 加成得到新一輪的 PageRank 值。 Reducer 的輸出格式： （ URL， 新一輪的 PageRank 值 ， Quark 編號 ， Quark 權(quán)值 ， 該 Quark的出鏈列表 ） Writer：將 reducer 的輸出存入 output 文件中，并替換掉 input 文件。