【正文】 業(yè)： 搜索引擎與 互聯(lián)網(wǎng)信息 挖掘 指導(dǎo)教師： 閆宏飛 二〇二二年二月八日 ii 摘要 本文 在 已有的基于 DomTree 和啟發(fā)式規(guī)則的網(wǎng)頁信息提取算法 的基礎(chǔ)上，通過 為所有符合 W3C 規(guī)范的 Html 標(biāo)簽分類， 逐個分析各 Html 標(biāo)簽所包含的語義信息， 細(xì)化規(guī)則設(shè)置，實現(xiàn)了一種自底向上的 無信息遺漏的網(wǎng)頁分塊算法，并在此基礎(chǔ)上，利用統(tǒng)計方法得到詳細(xì)的概率分布數(shù)據(jù)，實現(xiàn)了文本相似度比較和Bayes 后驗概率估計兩種網(wǎng)頁主題內(nèi)容信息塊識別算法，并將其求交，提高了主題內(nèi)容信息塊的識別精確度 。 實際檢驗表明，該套算法具有 很好的適應(yīng)性與可擴展性，并達(dá)到了很高的精度和召回率。而 Web 網(wǎng)絡(luò)的靈魂，就是流動在其中的無窮無盡的信息。但是把整個頁面作為最基本的信息處理單位有一些不合理之處。 這 些情況 促使我們反思以整個頁面為基本信息單元的做法不僅不盡合理，一定程度上甚至已經(jīng)損害了網(wǎng)絡(luò)瀏覽者的用戶體驗 ，妨礙了網(wǎng)絡(luò)信息提取的效率 。第二種則更為 普適，就是細(xì)分網(wǎng)頁中的信息單元，也就是給網(wǎng)頁分塊，在網(wǎng)頁分塊的基礎(chǔ)上存儲和提取 Web 頁面的語義信息。 Web 頁面的語義分塊另外一個 重要 用途 在于 移動終端訪問互聯(lián)網(wǎng)，比如手機和 IPod 等。 除此之外， Web 頁面的語義分塊還可能對常規(guī)搜索引擎之外的其他信息檢索系統(tǒng)有幫助。 第 2 章 相關(guān)研究工作 基于語義 的網(wǎng)頁信息提取 算法 由于 對 Web 頁面 有效 分 塊 之后可以極大地方便內(nèi)容提取、數(shù)據(jù)挖掘、 Web結(jié)構(gòu)分析等各項 Web 信息檢索領(lǐng)域的相關(guān)工作 ， 所以早有很多研究人員前赴后繼，就此展開了很多工作?？偟膩碚f，網(wǎng)頁信息提取算法可以分為兩類，一類屬于網(wǎng)站級別（ SiteLevel），一類屬于網(wǎng)頁級別（ PageLevel），當(dāng)然也有將兩類方法結(jié)合使用的算法。它只利用單個頁面內(nèi)部的信息， 當(dāng)然也 可能會用到一些全局信息 。 在分塊之后，它也只是簡單計算了文字長度等幾個變量來決定主題信息塊。 基于視覺的網(wǎng)頁分塊算法 基于 語義 的網(wǎng)頁分塊算法具有一些無法克服的先天性局限。比如，即使 DOM 樹中兩個結(jié)點具有同一個父結(jié)點，那么這兩個結(jié)點在語義上也不一定就是有聯(lián)系 的 。它的原理來自于用戶的實際觀察體驗，即用戶并不 關(guān)心 Web 頁面的內(nèi)部結(jié)構(gòu) ，而是 使用一些視覺因素，比如背景顏色、字體顏色和大小、邊框、邏輯塊和邏輯塊之間的間距等等 來識別出頁面中的語義塊 。 DOC 的值越大，則表明 該 塊內(nèi)部的內(nèi)容之間的聯(lián)系越緊密 ，反之越松散。但 VIPS 算法也有其局限性： 首先，提取網(wǎng)頁視覺信息代價很高。網(wǎng)絡(luò)上看到的一些 VIPS 算法實現(xiàn)都是調(diào)用了 IE COM 接口，而微軟自身的實現(xiàn)是利用單獨優(yōu)化后的 IE 內(nèi)核，他們都是基于 Windows 編程環(huán)境。 其次， VIPS 算法雖能改進(jìn) 分塊精確度，但算法相對比較復(fù)雜，迭代輪數(shù)較多，而基于規(guī)則的分塊算法卻只用較少的迭代輪數(shù)。 Block Level Web Graph 首先定義 兩個集合 P 和 B。而每個網(wǎng)頁包含有多個語義塊。 BlocktoPage 矩陣 塊頁（ blocktopage）矩陣 Z 的維數(shù)為 n k，定義如下： si 是 block i 所鏈接的網(wǎng)頁總數(shù)。在BLPR 算法中，采用了一個簡單的 block 重要度區(qū)分的公式，即用 block 的文字多少和離整個頁面中心點位置的遠(yuǎn)近來計算 block 的重要度。在 BLPR 的實現(xiàn)中函數(shù) f 的定義如下： 其中 β 為正規(guī)化因子，使得對每個 page， fp(b)的總和為 1。也就是說，當(dāng)用戶點擊頁面中的超鏈接時，更偏好選擇重要的語義塊中的 URL。 WB(a,b)可以理解為 用戶從 block a 開始，以包含 block b 的 page β 為媒介，跳轉(zhuǎn)到 block b 的概率。 所以 U 為 n n 的 轉(zhuǎn)換矩陣 ，它滿足對所有的 i， j， Uij = 1/n。因為它的計算基于 網(wǎng)頁中各語義塊的重要程度，噪音塊、廣告塊中的超鏈接指向的網(wǎng)頁的重要性顯然不如導(dǎo)航塊、正文塊中的超鏈接所指向的網(wǎng)頁，所以前者會被分配到較少的 PageRank 值，而后者則被分配到較多的 PageRank 值。 在天網(wǎng)搜索引擎平臺的搭建過程中， 也包括了抓取、存儲、分析（預(yù)處理）、索引、檢索等模塊，其中的分析模塊 接受成批量原始網(wǎng)頁的輸入，然后對每個網(wǎng)頁調(diào)用 Quark 模塊，進(jìn)行 網(wǎng)頁分塊、信息提取等工作 ，最后將處理后的數(shù)據(jù)存成TwDocView 格式，再提供給下游模塊。而基于對原始網(wǎng)頁數(shù)據(jù)集中處理的原則，為了應(yīng)對下游模塊可能提取的新的數(shù)據(jù)訪問需求， Quark 模塊必須具備良好的可擴展性 ，并且提供盡量多的各種類型的數(shù)據(jù)訪問接口。 獨立性。 該模塊的類結(jié)構(gòu)圖 如下 ： 圖中右下及中間 藍(lán)色的部分為 Quark模塊 的核心功能類，包括 QuarkTree、QuarkElement、 QuarkRecognizer、 QuarkAnalyzer 等四個類。它依賴于前面的兩個類。 QuarkEvaluation 類 是評測類 ，用來評測 Quark 核心類的實現(xiàn)效果。目前 可以查看 網(wǎng)頁分塊的效果，也可以查看主題信息提取的效果。 網(wǎng)頁分塊算法 算法 主體在 QuarkRecognizer 類中。 這一算法首先的一大特點就是實用性強。 包括： HEAD, SCRIPT, STYLE, OBJECT, FIELDSET, FRAMESET, IFRAME 大標(biāo)簽（ Big Tag， 簡稱為 B 型標(biāo)簽）： 這種標(biāo)簽 通常都代表一個網(wǎng)頁塊，只不過有時其內(nèi)部內(nèi)容過少，需要跟其他節(jié)點合并成一個網(wǎng)頁塊，或者在特殊情況下其內(nèi)部沒有可見字符。 如果一顆 html 子樹中包含多個 L 型標(biāo)簽，則該子樹單獨成塊的可能性增加。由于它們一般不單獨出現(xiàn)，對網(wǎng)頁布局的影響體現(xiàn)在了其屬主標(biāo)簽中，所以 在 QuarkRecognizer 算法中也不予考慮。例如： H1, H2, TITLE 在明確了各 html 標(biāo)簽的類別之后， 利用 DomTree 中各標(biāo)簽節(jié)點 的類別信息和內(nèi) 部文字長度 ，以 及 其 子標(biāo)簽節(jié)點的類別信息， 對 DomTree 自底向上遍歷，在遍歷的過程中不斷判斷出新的網(wǎng)頁塊，并 加入網(wǎng)頁塊池中，當(dāng)遍歷到最上部的html 根節(jié)點時，算法結(jié)束，網(wǎng)頁分塊完畢。 4 如果遇到 C 型節(jié)點，則立即將 此節(jié)點加入網(wǎng)頁塊池。 8 當(dāng)前節(jié)點隊列為空時，遍歷結(jié)束 ，算法終止。 QuarkAnalyzer 算法的核心偽碼如下： _________________________________________________________________ 第一步， 基于文本相似度的 方法 ： 首先，把所有網(wǎng)頁塊中，文本長度最大的那個網(wǎng)頁塊判定為主題內(nèi)容塊。 對排序后的兩個 token 流計算 token 的重復(fù)數(shù)。若該后驗概率大于 ，則判定該網(wǎng)頁塊為主題內(nèi)容塊，否則反之。 該塊中包含 常見噪音詞并且文本長度小于 100 的概率 p1_noise = 。 在該網(wǎng)頁塊為非主題內(nèi)容塊的條件下， 該塊中包含定制標(biāo)簽的概率 p2_costomizedTag = 。 該塊中錨接文本和非錨接文本的長度之比大于 p2_scale = 。 限于篇幅，這里就不再詳細(xì)介紹算法的細(xì)節(jié)，但是附有幾張對照圖片，以利說明。 第一幅圖：這是從新浪網(wǎng)上保存的一個新聞網(wǎng)頁。 從圖中可以看出 ，紅色、綠色、紫色的網(wǎng)頁塊 間雜排列，就像地圖一樣，每一種顏色表示一個被識別出的網(wǎng)頁塊。從圖中可以看出，就這個網(wǎng)頁而言，網(wǎng)頁主題內(nèi)容的提取基本成功了。 第 4 章 SEWM2022 中文 Web 信息檢索評測 評測任務(wù)介紹 SEWM 中文 Web 信息檢索評測 [6]是由北京大學(xué)網(wǎng)絡(luò)實驗室主辦的中文 Web檢索評測項目，自 2022 年起，在 SEWM 會議中已連續(xù)舉辦了五屆，今年（ 2022年）是第五屆。文檔集數(shù)據(jù)格式參見 [7]。 下面是對主題型網(wǎng)頁的一個補充定義： 僅由圖片， flash，網(wǎng)絡(luò)視頻等構(gòu)成主題塊的網(wǎng)頁，除非亦包括獨立成段的文字性描述信息，否則不屬于主題型網(wǎng)頁。 任務(wù)評測根據(jù)準(zhǔn)確度、召回率和 MacroF1 三個指標(biāo)，它們的定義如下： 網(wǎng)頁內(nèi)容信息發(fā)現(xiàn)任務(wù) 在一個主題型的網(wǎng)頁中， 一般會包括主題內(nèi)容信息， 噪音信息 ，和相關(guān)鏈接信息 。 一個網(wǎng)頁中的內(nèi)容信息不一定只有一塊，可能有多塊，甚至可能是零散分布的文字段。具體要求如下： 主題型網(wǎng)頁發(fā)現(xiàn)：提交一個純文本文件，包含所有找到的主題網(wǎng)頁，每個網(wǎng)頁的編號占一行。 大連理工大學(xué)信息檢索實驗室 DLUT1 DLUT2 四川大學(xué)計算機學(xué)院數(shù)據(jù)庫與知識工程研究所 SCU1 SCU2 華南理工大學(xué)廣東省計算機網(wǎng)絡(luò)重點實驗室 一隊 SCUT1 SCUT2 華南理工大學(xué)廣東省計算機網(wǎng)絡(luò)重點實驗室二隊 SCUT3 SCUT4 山東大學(xué)信 息檢索實驗室 SDU1 SDU2 人民大學(xué)信息學(xué)院 RUC 北京大學(xué)網(wǎng)絡(luò)實驗室 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 個網(wǎng)頁中，有 71281 個不重復(fù) URL。 雖然我們的樣本數(shù)偏少，但由于樣本中的類型分布大致符合原網(wǎng)頁集中的類型分布，所以評測結(jié)果基本反映了各組的實際分類質(zhì)量，只不過沒有形成明顯差距。 華南理工一隊也屬于整體性判斷方法，但只使用了分類器方法；山東大學(xué)隊則只使用了較簡單的啟發(fā)式規(guī)則。其中判斷各個網(wǎng)頁塊的類型是綜合基于規(guī)則和基于概率的方法，同時針對本次任務(wù)的網(wǎng)頁特 性做了優(yōu)化。 其他特征信息 包括 網(wǎng)頁文本內(nèi)容中標(biāo)點符號的個數(shù) 、正文的文字長度、 特殊標(biāo)簽 （如p, br,h1） 是否出現(xiàn) ，以及包含特殊關(guān)鍵詞與否。 根據(jù)各組提交的格式為（ doc_no start_pos length）的結(jié)果文件，為各組產(chǎn)生出對應(yīng)的 104 個內(nèi)容信息塊網(wǎng)頁，然后逐一比較標(biāo)記過的網(wǎng)頁與各組提取的網(wǎng)頁。同樣，各隊的實現(xiàn)方法可大致分為網(wǎng)頁整體性判斷和網(wǎng)頁分塊判斷兩種。而山東大學(xué)提到根據(jù) table， div， td， p等容器標(biāo)簽對網(wǎng)頁分塊，再根據(jù)某種規(guī)則對某些網(wǎng)頁塊進(jìn)行合并 的改進(jìn)型算法，但不知是否最終實現(xiàn)。 網(wǎng)頁整體性判斷 華南理工一隊，二隊采用了整體性判斷方法。 華南理工二隊采用 DSE 算法， 考察了 URL 相 似度對 DSE 的影響 ，通過網(wǎng)頁 間 結(jié)構(gòu)比較 ，并計算 錨文本與正文塊的比例 來提取內(nèi)容信息塊，算法相對比較完善，但也有對不同類型的網(wǎng)頁處理時普適性不夠的問題。 對主題型網(wǎng)頁的定義不夠清晰。比如論壇或者博客的回帖該不該算作主題型應(yīng)該明確規(guī)定，以后可以考慮將這種類型的網(wǎng)站單獨作為評測項目，比如 分別提取主貼與回帖（提問與解答）的內(nèi)容。以后我們應(yīng)該制作更精良和更具有代表性的樣本網(wǎng)頁集。 QuarkRank 在 MapReduce 上， QuarkRank 算法主要需要實現(xiàn)兩個類，一個是QuarkRankMapper 類，一個是 QuarkRankReducer 類。 下面是主控程序的核心部分偽碼： _________________________________________________________________ ALGORITHM QuarkRank (TwRawPage Cwt200G) INPUT : 天網(wǎng)原始數(shù)據(jù) BEGIN 預(yù)處理： 將 Cwt200G 處理成 （ URL， 初始 PageRank 值 ， Quark 編號 ， Quark 權(quán)值，該 Quark 的出鏈列表 ） 格式，存到 input 文件中。 Reducer 的輸出格式： （ URL， 新一輪的 PageRank 值 ， Quark 編號 ， Quark 權(quán)值 ， 該 Quark的出鏈列表 ） Writer：將 reducer