【畢業(yè)學(xué)位論文】（Word原稿）基于網(wǎng)頁的信息系統(tǒng)的一種預(yù)處理過程-計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)

北京大學(xué) 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室碩士學(xué)位論文 北京大學(xué)碩士研究生學(xué)位論文 題目：基于網(wǎng)頁的信息系統(tǒng)的一種預(yù)處理過程 姓 名：張志剛 學(xué) 號(hào)： 10108137 院 系：計(jì)算機(jī)科學(xué)技術(shù)系 專 業(yè)：計(jì)算機(jī)軟件與理論 研究方向：計(jì)算機(jī)網(wǎng)絡(luò)與分布式系統(tǒng) 導(dǎo) 師：李曉明 教授 2004 年 5 月 北京大學(xué) 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室碩士學(xué)位論文 版權(quán)聲明 任何收存和保管本論文各種版本的單位和個(gè)人，未經(jīng)本論文作者同意，不得將本論文轉(zhuǎn)借他人，亦不得隨意復(fù)制、抄錄、拍照或以任何方式傳播。否則，引起有礙作者著作權(quán)之問題，將可能承擔(dān)法律責(zé)任。 北京大學(xué) 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室碩士學(xué)位論文 摘要 隨 著 迅速發(fā)展， 的信息越來越豐富。 用方便、信息豐富，人們?cè)絹碓蕉嗟氖褂?尋找需要的信息。為了更好的使用的信息，人們也不斷的追求能夠有效組織和利用網(wǎng)上信息的技術(shù)和系統(tǒng)。然而， 的信息存在很多問題：網(wǎng)頁內(nèi)的噪音內(nèi)容多、 近似網(wǎng)頁量大以及缺乏必要的元數(shù)據(jù)信息，這些問題嚴(yán)重影響了 息系統(tǒng)的服務(wù)質(zhì)量。 針對(duì) 息系統(tǒng)的共性需求，本文提出了一個(gè)預(yù)處理框架及相應(yīng)的方法。該預(yù)處理框架包括了三個(gè)預(yù)處理工作：網(wǎng)頁凈化、近似網(wǎng)頁刪除和網(wǎng)頁元數(shù)據(jù)提取。通過預(yù)處理過程，原始網(wǎng)頁 集中的近似網(wǎng)頁被刪除，而保留下來的網(wǎng)頁被凈化并轉(zhuǎn)化為一個(gè)統(tǒng)一的結(jié)構(gòu)化模型（稱之為 該模型中提供了各個(gè)領(lǐng)域需求較多的元數(shù)據(jù)和內(nèi)容數(shù)據(jù)， 它包括網(wǎng)頁標(biāo)識(shí)、 網(wǎng)頁類型、內(nèi)容類別、 標(biāo)題、 關(guān)鍵詞、摘要、正文、相關(guān)鏈接等元素。本文提出的預(yù)處理方法的一個(gè)重要優(yōu)點(diǎn)是它不需要除原始網(wǎng)頁以外的其他信息，而這些額外信息是該領(lǐng)域中其他方法所必須的；另一個(gè)優(yōu)點(diǎn)是將 息系統(tǒng)的共性需求放到一個(gè)過程中一次性提取出來，可以避免相同中間過程的重復(fù)執(zhí)行，從而提高信息提取效率。 本文中提出的預(yù)處理框架和方法已經(jīng)應(yīng)用到了“天 網(wǎng)”搜索引擎和網(wǎng)頁自動(dòng)分類系統(tǒng)中。通過使用預(yù)處理后應(yīng)用系統(tǒng)質(zhì)量的提高，驗(yàn)證了該預(yù)處理方法的有效性。不難看出，通過這樣一個(gè)預(yù)處理過程，可以在任何一個(gè)網(wǎng)頁集上（包括 建一個(gè)組織良好的、凈化的、更易使用的信息層。 關(guān)鍵詞： 萬維網(wǎng) , 數(shù)據(jù)預(yù)處理，數(shù)據(jù)凈化，近似網(wǎng)頁識(shí)別，元數(shù)據(jù)提取 北京大學(xué) 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室碩士學(xué)位論文 of of eb eb to of ebs of In to eb eb eb in eb as in eb eb in of on of eb of eb eb of in In we a to of eb eb a of of of is no is to of in of 京大學(xué) 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室碩士學(xué)位論文 of Its to a we up a on of eb eb 京大學(xué) 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室碩士學(xué)位論文 目 錄 第 1 章 引言 . 1 究背景 . 1 文研究內(nèi)容 . 2 文貢獻(xiàn) . 3 文組織 . 3 第 2 章 相關(guān)研究 . 4 索引擎 . 4 頁自動(dòng)分類 . 7 息提取 . 9 數(shù)據(jù)提取 . 10 第 3 章 息系統(tǒng)面臨的問題及共性需求 . 12 第 4 章 預(yù)處理方法與技術(shù) . 14 處理框架及結(jié)果描述 . 14 處理框架 . 14 處理結(jié)果描述 . 14 頁表示 . 15 頁標(biāo)簽樹表示 . 16 頁量化表示 . 19 頁凈化 . 24 頁類型判斷 . 24 題網(wǎng)頁凈化 . 25 錄網(wǎng)頁凈化 . 25 片網(wǎng)頁凈化 . 26 頁凈化時(shí)空效率分析 . 26 似網(wǎng)頁的發(fā)現(xiàn) . 27 似網(wǎng)頁發(fā)現(xiàn)算法 . 27 能分析 . 29 頁元數(shù)據(jù)提取 . 29 頁元數(shù)據(jù)提取流程描述 . 30 北京大學(xué) 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室碩士學(xué)位論文 文提取 . 30 鍵詞提取 . 30 容類別判斷 . 31 題提取 . 32 要提取 . 32 題相關(guān)超鏈提取 . 33 章小結(jié) . 35 第 5 章 應(yīng)用與評(píng)測 . 36 頁凈化在網(wǎng)頁自動(dòng)分類系 統(tǒng)中的應(yīng)用與評(píng)測 . 36 用 . 36 測標(biāo)準(zhǔn) . 37 測結(jié)果與分析 . 37 似網(wǎng)頁消除在搜索引擎中的應(yīng)用與評(píng)測 . 38 驗(yàn)設(shè)計(jì) . 38 測標(biāo)準(zhǔn) . 39 測結(jié)果與分析 . 40 頁元數(shù)據(jù)在搜索引擎的索引過程中的應(yīng)用與評(píng)測 . 41 索效率評(píng)測 . 41 索精度評(píng)測 . 42 章小結(jié) . 44 第 6 章 總結(jié)與展望 . 45 結(jié) . 45 望 . 45 參考資料 . 47 作者就讀期間參加的科研項(xiàng)目和發(fā)表的論文 . 51 致謝 . 52 北京大學(xué) 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室碩士學(xué)位論文 1 第 1章 引言 究背景 萬維網(wǎng)（ 記為 因特網(wǎng)上最成功的應(yīng)用，起源于 1989 年歐洲粒子物理研究室 最初計(jì)劃是由 物理學(xué)家 1989 年 3 月提出的，第一個(gè)基于文本原型于18 個(gè)月后運(yùn)行。 1991 年 12 月在德克薩斯州的 1 超文本會(huì)議上進(jìn)行了一次演示，次年繼續(xù)發(fā) 展，并于 1993 年 2 月，隨著第一個(gè)圖形界面發(fā)布而達(dá)到了其發(fā)展的高峰 1995 年 4 月， 網(wǎng)上的流量超過了 其它服務(wù)的流量，成為 的第一大應(yīng)用服務(wù)。到 1997 年 12 月，網(wǎng)上大約有 3 億 2000 萬網(wǎng)頁 根據(jù) 000 年的數(shù)據(jù)庫數(shù)據(jù)表明，網(wǎng)頁數(shù)目已經(jīng)超過了 10 億。 002 年 4 月索引網(wǎng)頁表明，網(wǎng)頁數(shù)已經(jīng)超過 20 億 而在 2004 年 4 月， 索引擎索引網(wǎng)頁數(shù)已經(jīng)超過 42 億。 隨 著 迅速擴(kuò)展， 的信息也飛速膨脹。這一方面使得 一方面也使得其中絕大多數(shù)的信息對(duì)于絕大多數(shù)的用戶是沒有意義的，而且對(duì)于一個(gè)用戶而言，極小部分的有用信息也淹沒在無用信息中很難被找到。為了更好的使用 的信息，人們不斷的追求能夠有效組織和利用網(wǎng)上信息的技術(shù)和系統(tǒng)，包括搜索引擎、網(wǎng)頁自動(dòng)分類、信息提取以及主題搜索，等等。我們通常把以網(wǎng)頁為處理對(duì)象的系統(tǒng)稱為 基于網(wǎng)頁的信息系統(tǒng) ，為表達(dá)簡單，本文中我們稱其為 在相關(guān)的技術(shù)中，一方面涉及到對(duì)網(wǎng)頁內(nèi)容的分析，另一 方面也涉及到對(duì)網(wǎng)頁間鏈接關(guān)系的分析。其最終目的是通過對(duì) 信息的有效組織來方便用戶對(duì)所需信息的獲取。 在內(nèi)容分析的過程中傳統(tǒng)信息檢索領(lǐng)域的技術(shù)自然的會(huì)被引用進(jìn)來。但 網(wǎng)頁與傳統(tǒng)的文檔相比有著自己的特點(diǎn)： 一、 有用信息通常伴隨著大量的“噪音”內(nèi)容，而噪音內(nèi)容正是 頁與傳統(tǒng)文檔的一個(gè)主要區(qū)別。根據(jù)噪音內(nèi)容的粒度大小， 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室碩士學(xué)位論文 2 上的噪音內(nèi)容可以被分為兩類 全局噪音 ： 全局噪音 是指 具有較大粒度的噪音內(nèi)容，它通常包含鏡像網(wǎng)站、重復(fù)網(wǎng)頁。 局部噪音 ： 局部噪音 是指 頁內(nèi) 與網(wǎng)頁主題內(nèi)容無關(guān)的噪音內(nèi)容，比如：廣告、導(dǎo)航條以及版權(quán)聲明等內(nèi)容。 二、 網(wǎng)頁缺乏必要的元數(shù)據(jù)信息。而元數(shù)據(jù)在信息管理過程中有著重要的作用。 三、 文本信息大多數(shù)是以 頁的形式存在的， 定義了一套標(biāo)簽來描述網(wǎng)頁中內(nèi)容的布局和顯示方式，因而，網(wǎng)頁中的標(biāo)簽信息隱含了網(wǎng)頁內(nèi)容的重要性信息以及相關(guān)性信息。 信息的這些特點(diǎn)使得傳統(tǒng)信息檢索領(lǐng)域中的技術(shù)已經(jīng)不能滿足各種 息系統(tǒng)的要求。針對(duì) 頁的不足給各種 息系統(tǒng)帶來的問題，各個(gè)領(lǐng)域都有一套具體的解決方法。但并沒有一 個(gè)較為通用的預(yù)處理框架及相應(yīng)的方法。通過分析可以看到，這些問題都是源自 信息本身的不足，因而各種 息系統(tǒng)的需求是有共性的。這意味著我們有必要也有可能建立一個(gè)較為通用的預(yù)處理框架并給出相應(yīng)的方法，從而方便大多數(shù) 息系統(tǒng)的需求。本文中的研究工作就是在這樣一個(gè)背景下展開的。 文研究內(nèi)容 本文中的研究圍繞以下幾個(gè)方面展開： 分析 網(wǎng)頁的特點(diǎn)以及其不足對(duì) 應(yīng)用系統(tǒng)造成的影響，從而發(fā)現(xiàn) 各種應(yīng)用系統(tǒng)的共性需求。 針對(duì) 應(yīng)用系統(tǒng)的共性需求，給出一個(gè)較為通用的預(yù)處理框架和相應(yīng)的方 法，從而滿足大多數(shù) 息系統(tǒng)的需求。 將提出的預(yù)處理框架中的方法應(yīng)用到實(shí)際系統(tǒng)中，包括：搜索引擎和網(wǎng)頁自動(dòng)分類系統(tǒng)。 通過對(duì)應(yīng)用的效果評(píng)測和一系列實(shí)驗(yàn)，發(fā)現(xiàn)方法中的不足，繼續(xù)改進(jìn)方法。 北京大學(xué) 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室碩士學(xué)位論文 3 文貢獻(xiàn) 基于對(duì) 網(wǎng)頁的特點(diǎn)和 息系統(tǒng)共性需求的分析，提出一個(gè)較為通用的預(yù)處理框架，包括：網(wǎng)頁凈化、近似網(wǎng)頁發(fā)現(xiàn)和元數(shù)據(jù)提取。 提出一個(gè)新的網(wǎng)頁內(nèi)容凈化方法，該方法的一個(gè)重要優(yōu)點(diǎn)是它不需要除原始網(wǎng)頁以外的其他信息（例如： 網(wǎng)頁模板 ），而這些額外信息是該領(lǐng)域中其他方法所必須的。 在參考了 C和 ，提出了一個(gè)包含元數(shù)據(jù)和內(nèi)容數(shù)據(jù)的網(wǎng)頁表示模型（稱為該模型包含這樣幾項(xiàng)信息元素： 網(wǎng)頁標(biāo)識(shí) 、 網(wǎng)頁類型 、 內(nèi)容類別 、 標(biāo)題 、 關(guān)鍵詞 、 摘要 、 正文 、 相關(guān)鏈接 。并給出了該模型中元素的自動(dòng)提取方法。（ ） 將本文中提出的方法應(yīng)用到實(shí)際的系統(tǒng)中：搜 索引擎和網(wǎng)頁自動(dòng)分類系統(tǒng)，通過對(duì)原有系統(tǒng)質(zhì)量的提高，驗(yàn)證了方法的有效性和實(shí)用性。 通過本文中提出的方法，一方面能夠自動(dòng)去除 噪音網(wǎng)頁以及網(wǎng)頁內(nèi)與網(wǎng)頁主題內(nèi)容無關(guān)的噪音內(nèi)容，另一方面也能自動(dòng)的從網(wǎng)頁中提取相關(guān)的元數(shù)據(jù)，從而使我們看到了在原始 搭建一個(gè)噪音小、描述清晰、更易于處理和利用的網(wǎng)頁信息平臺(tái)。 文組織 本文后面是這樣組織的，第 2 章是相關(guān)領(lǐng)域的研究；第 3 章討論 4 章講述預(yù)處理過程的框架和其中的方法；第 5 章介紹本文中提出方法的應(yīng)用以及實(shí)驗(yàn)和實(shí)驗(yàn)結(jié)果分析；第 6章是對(duì)本文的總結(jié)和對(duì)未來工作的展望。 北京大學(xué) 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室碩士學(xué)位論文 4 第 2章 相關(guān)研究 索引擎 搜索引擎是 信息檢索的典型系統(tǒng)，它的作用是幫助人們快速準(zhǔn)確的在 找到所需的信息。根據(jù)搜索引擎基于的技術(shù)原理，可以分為三個(gè)類型： 基于機(jī)器人（ 搜索引擎 這種搜索引擎利用一個(gè)稱為 程序以某種策略自動(dòng)的將 的網(wǎng)頁搜集起來，并由一個(gè)索引器為搜集到的網(wǎng)頁建立索引。當(dāng)用戶通過服務(wù)提交查詢請(qǐng)求時(shí)，由檢索器從索引庫中檢索出相關(guān)的文檔返回給用戶。該類搜索引擎的優(yōu)點(diǎn)是提供服務(wù)的信息量大、無需人工參與；缺點(diǎn)是返回的信息過多，包 括很多與查詢無關(guān)的信息。 目錄式搜索引擎（ 這種搜索引擎以人工或半自動(dòng)方式搜集信息。由人工來訪問其中的網(wǎng)站，并對(duì)該網(wǎng)站撰寫一段描述，并根據(jù)網(wǎng)站中的信息將網(wǎng)站加入到一個(gè)預(yù)先定義好的分類體系下。用戶訪問時(shí)，通過該分類體系不斷按照自己關(guān)心的類別向下找，可以找到自己關(guān)心的網(wǎng)站。該搜索引擎的優(yōu)點(diǎn)是用戶找到的結(jié)果較為準(zhǔn)確；缺點(diǎn)是需要大量人工介入、信息量少。 元搜索引擎（ 元搜索引擎是建立在其他獨(dú)立搜索引擎之上的搜索引擎。當(dāng)用戶提交一 個(gè)查詢，元搜索引擎將查詢項(xiàng)做一定處理后，提交給多個(gè)獨(dú)立的搜索引擎，并將所有的查詢結(jié)果集中起來處理后返回給用戶。 本節(jié)中，我們將重點(diǎn)介紹基于 搜索引擎，并探討 息中的噪音內(nèi)容對(duì)搜索引擎中某些環(huán)節(jié)的影響。下圖是一個(gè)搜索引擎通用的結(jié)構(gòu)圖。 北京大學(xué) 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室碩士學(xué)位論文 5 圖表 1 搜索引擎通用結(jié)構(gòu)圖 基于 搜索引擎通常包含以下四個(gè)步驟： 網(wǎng)頁抓?。喊l(fā)現(xiàn)、搜集 的網(wǎng)頁信息。 網(wǎng)頁消重：消除搜集到的網(wǎng)頁中重復(fù)或近似重復(fù)的網(wǎng)頁。 建立索引：對(duì)搜集到的 息 建立索引庫。 提供檢索服務(wù)：根據(jù)用戶輸入的查詢項(xiàng)，在索引庫中檢索出文檔。 下面詳細(xì)討論網(wǎng)頁消重和建立索引。 網(wǎng)頁消重是指將搜集到的網(wǎng)頁中重復(fù)網(wǎng)頁去掉的過程，在消重后的網(wǎng)頁集上建索引再提供服務(wù)可以保證用戶查詢時(shí)不會(huì)出現(xiàn)大量內(nèi)容重復(fù)的網(wǎng)頁，同時(shí)節(jié)省建立索引的時(shí)間以及檢索的時(shí)間。 三種比較常用的重復(fù)網(wǎng)頁判斷方法，其中 使用。這些重復(fù)網(wǎng)頁發(fā)現(xiàn)算法都是基于相同的想法：為每張網(wǎng)頁計(jì)算一組指紋（ 如果兩張網(wǎng)頁中相同的指紋數(shù)量 超過一個(gè)閾值，這兩張網(wǎng)頁就被認(rèn)為是互為重復(fù)的網(wǎng)頁。然而，大量的重復(fù)網(wǎng)頁并不是對(duì)原始網(wǎng)頁的簡單拷貝，而是將要轉(zhuǎn)載的主題內(nèi)容放在不同的模板中形成的。我們把這種近似的重復(fù)網(wǎng)頁以及完全相同的重復(fù)網(wǎng)頁統(tǒng)稱為 近似網(wǎng)頁 。由于模板中的內(nèi)容絕大多數(shù)是與主題內(nèi)容無關(guān)的，因此模板中的內(nèi)容就會(huì)干擾近似網(wǎng)頁識(shí)別程序?qū)魄闆r的判斷，從而導(dǎo)致錯(cuò)誤消重。常見的錯(cuò)誤消重有北京大學(xué) 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室碩士學(xué)位論文 6 以下兩種情況： 情況 1：相同的內(nèi)容，由于放在了不同的模板中導(dǎo)致應(yīng)該被消掉但實(shí)際上被消重程序判斷為非近似網(wǎng)頁而保留。 情況 2：不同的內(nèi)容，由于放在了相同的模 板中導(dǎo)致不應(yīng)該被消掉但實(shí)際上被消重程序判斷為近似網(wǎng)頁而消掉。 對(duì)于完全相同的近似網(wǎng)頁，消重算法是容易識(shí)別的，因而，如何識(shí)別主題內(nèi)容相同但模板不同的情況是消重算法面臨的問題。 在索引過程中，索引器為搜集到的文檔建立了一個(gè)（或若干個(gè)）索引文件，索引文件是用來在檢索時(shí)對(duì)查詢?cè)~與文檔進(jìn)行匹配的，從而找到與查詢?cè)~相關(guān)的文檔。為了合理的對(duì)檢索到的文檔排序，研究人員提出了 法，這兩個(gè)算法通過分析 的鏈接結(jié)構(gòu)來計(jì)算網(wǎng)頁的重要性。正如 附錄所講述 的，由于廣告等噪音內(nèi)容通常伴隨著超鏈出現(xiàn)， 法得到的排序通常偏向于廣告網(wǎng)頁。另外，如果不去除原始網(wǎng)頁中的噪音內(nèi)容，檢索系統(tǒng)必然對(duì)噪音內(nèi)容也建立索引，從而導(dǎo)致僅僅因?yàn)椴樵冊(cè)~在某張網(wǎng)頁的噪音內(nèi)容中出現(xiàn)，而把該網(wǎng)頁作為結(jié)果返回，而網(wǎng)頁的主題內(nèi)容可能和這個(gè)查詢?cè)~完全無關(guān)。可以看出，噪音內(nèi)容不僅使索引結(jié)構(gòu)的規(guī)模變大，而且還導(dǎo)致了檢索準(zhǔn)確性的下降。針對(duì)這個(gè)問題， 提出了一個(gè)去除網(wǎng)頁中噪音內(nèi)容的方法，該方法首先依據(jù) 標(biāo)簽構(gòu)造網(wǎng)頁的標(biāo)簽樹，從而依據(jù) 標(biāo)簽將一張網(wǎng)頁規(guī)劃為相 互嵌套的內(nèi)容塊；而后，對(duì)于使用同一個(gè)模板作出的網(wǎng)頁集，利用基于信息熵的方法找出在該網(wǎng)頁集中多次出現(xiàn)的內(nèi)容，作為冗余內(nèi)容，而在該網(wǎng)頁集中出現(xiàn)較少的內(nèi)容塊就是有效信息塊。實(shí)驗(yàn)證明該方法是有效的，但該方法必須局限在基于同一個(gè)模板的網(wǎng)頁集，而 的網(wǎng)頁模板不計(jì)其數(shù)，該方法顯然不夠通用。 也提出了一個(gè)噪音內(nèi)容判斷方法，該方法必須針對(duì)某一個(gè)網(wǎng)站，通過對(duì)網(wǎng)站建立一棵特殊的標(biāo)簽樹的方法，自動(dòng)發(fā)現(xiàn)網(wǎng)站中網(wǎng)頁內(nèi)的噪音內(nèi)容。但這種方法的局限在于，它只能以網(wǎng)站為單位進(jìn)行處理。實(shí)際上，任意一張網(wǎng)頁，人是比較容易區(qū)別 其中的噪音內(nèi)容和主題內(nèi)容的。這說明我們有可能追求自動(dòng)識(shí)別一張網(wǎng)頁中的主題內(nèi)容和噪音內(nèi)容而不需要依賴于一個(gè)網(wǎng)頁集合；這樣就可以使去除網(wǎng)北京大學(xué) 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室碩士學(xué)位論文 7 頁噪音內(nèi)容的方法更加通用和獨(dú)立。 頁自動(dòng)分類 網(wǎng)頁自動(dòng)分類是指用計(jì)算機(jī)程序來自動(dòng)確定網(wǎng)頁與預(yù)先定義類別之間的隸屬關(guān)系 從總體上，分類器的整個(gè)工作周期可以分成訓(xùn)練過程和分類過程。 訓(xùn)練過程是指為預(yù)先確定的分類體系中的每個(gè)類別人工挑選一定量的樣本（我們稱這個(gè)樣本集合為訓(xùn)練集），目的在于通過每個(gè)類別內(nèi)的樣本來最大程度地體現(xiàn)每個(gè)類的特征并區(qū)別不同類之間的特征。 在訓(xùn)練 過程中，訓(xùn)練集實(shí)例經(jīng)過分詞和特征選取處理后被表示成向量形式。在 該特征向量集 上，統(tǒng)計(jì)不同類別內(nèi)的詞的分布，形成類別與詞之間的一個(gè)加權(quán)映射。這個(gè)映射關(guān)系將是后續(xù)分類過程的依據(jù)。另外， 校驗(yàn)集是訓(xùn)練集的一部分，通過應(yīng)用相應(yīng)的閾值策略來預(yù)先確定每個(gè)類別的截尾閾值。截尾閾值的作用在于，在分類過程中，每個(gè)網(wǎng)頁都會(huì)被賦予一些候選類，以及該網(wǎng)頁與每個(gè)候選類的類屬關(guān)系權(quán)值，那么候選類中，類屬關(guān)系權(quán)值大于對(duì)應(yīng)類截尾閾值的類別將被保留下來作為該網(wǎng)頁的分類結(jié)果。在分類過程中，一個(gè)待分類的中文網(wǎng)頁表示成向量形式后，應(yīng)用分類算法同訓(xùn)練過 程得到的類別模式逐一比較，得到候選類別列表，然后同訓(xùn)練過程中得到的每個(gè)類別的閾值相比較，保留大于閾值的類別，并作為該網(wǎng)頁的分類結(jié)果。 在這兩個(gè)過程中，包含以下幾個(gè)關(guān)鍵技術(shù)： 訓(xùn)練集整理：從上述的介紹可以知道，訓(xùn)練集是分類器的一個(gè)重要分類依據(jù)，訓(xùn)練集的質(zhì)量直接影響到后續(xù)分類的質(zhì)量。 特征項(xiàng)選取：在訓(xùn)練的過程中，對(duì)每個(gè)類別內(nèi)文檔中包含的詞項(xiàng)進(jìn)行取舍，選取那些能夠明確體現(xiàn)一個(gè)類別特征并有很強(qiáng)區(qū)分能力的詞項(xiàng)，而去掉那些區(qū)分能力弱，模糊不同類別間特征邊界的詞項(xiàng)。同時(shí)，特征項(xiàng)選取還有降低向量空間維度的作用，從而提高分類 系統(tǒng)的效率。 人們已經(jīng)研究了多種特征選取方法，如：文檔頻率（ 信息增益（ 互信息（ 開方擬和檢驗(yàn)（ 2術(shù)語強(qiáng)度（ 等。 北京大學(xué) 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室碩士學(xué)位論文 8 分類算法：通過比較給定網(wǎng)頁的特征向量與每個(gè)類別內(nèi)特征項(xiàng)的分布，確定網(wǎng)頁與類別的隸屬關(guān)系。常用的分類算法有以下幾種： 法、 算法、基于 分類算法、決策樹（ 法、 法，等等。 訓(xùn)練集 預(yù)處理 分類算法參數(shù)調(diào)整測試特征選取 分類結(jié)果 截尾算法I n d e p e n d e n c y B i n a r y 分類 M - a r y 分類圖表 2 實(shí)現(xiàn)中文網(wǎng)頁自動(dòng)分類的一般過程 待分類中文網(wǎng)頁向量表示預(yù)處理訓(xùn)練集實(shí)例預(yù)處理特征選取算法分類算法校驗(yàn)集 測試每個(gè)類的閾值訓(xùn)練結(jié)果類別表閾值策略候選類列表特征項(xiàng)向量表示訓(xùn)練過程 分類過程圖表 3 中文網(wǎng)頁分類器的工作原理圖 由于噪音內(nèi)容與主題內(nèi)容無關(guān)，因此，噪音內(nèi)容對(duì)上述的幾個(gè)關(guān)鍵技術(shù)都造成了不同程度的影響。在訓(xùn)練過程中，訓(xùn)練集中的噪音內(nèi)容會(huì)導(dǎo)致各個(gè)類別的特征變得模糊，甚至造成噪 音中的關(guān)鍵詞成為類別的重要特征項(xiàng)。在分類過程中，待分類網(wǎng)頁中的噪音內(nèi)容則會(huì)導(dǎo)致該網(wǎng)頁類別不明確，甚至網(wǎng)頁的分類結(jié)果被大量的噪音內(nèi)容所誤導(dǎo)，因而影響了網(wǎng)頁自動(dòng)分類的效果。 提出了通過去掉網(wǎng)頁中的噪音特征項(xiàng)來提高網(wǎng)頁分類質(zhì)量的方法。這兩個(gè)方法中，作者著重考慮如何從訓(xùn)練集中選取有代表性的特征項(xiàng)而去掉噪音的特征項(xiàng)，而沒有考慮先去掉訓(xùn)練集網(wǎng)頁中的噪音內(nèi)容，而后在網(wǎng)頁的主題內(nèi)容中選取特征項(xiàng)。 北京大學(xué) 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室碩士學(xué)位論文 9 息提取 信息提取是從文本中提取用戶感預(yù)先定義好的某些類型的信息（定義、實(shí)體、關(guān)系）并以結(jié)構(gòu)化的形式返回提 取結(jié)果的過程 它與信息檢索的區(qū)別在于：信息檢索是在一個(gè)文檔集合中找到與查詢?cè)~相關(guān)的文檔子集；而信息提取是在文檔內(nèi)部提取出預(yù)先定義的某些類型的信息。信息提取的結(jié)果通常自動(dòng)導(dǎo)入數(shù)據(jù)庫中，在這些數(shù)據(jù)之上可以作許多應(yīng)用層次上的分析，例如：趨勢分析；也可以直接在 提供服務(wù)，例如：當(dāng)前市場上某類商品價(jià)格表。 信息提取研究的目標(biāo)是建立具有如下功能的系統(tǒng)： 1、 從無結(jié)構(gòu)或半結(jié)構(gòu)化的文檔中自動(dòng)發(fā)現(xiàn)有用信息，并將其中相關(guān)的信息聯(lián)系起來。 2、 能夠在只做簡單修改的情況下方便的應(yīng)用到不同的領(lǐng)域。 3、 性能要滿 足用戶的需求。 一個(gè)信息提取系統(tǒng)通常分為三個(gè)自過程： 1、 從每個(gè)文檔內(nèi)提取有用信息。 2、 如果一個(gè)完整的記錄內(nèi)容分布在不同文檔中，則需要將不同文檔中提取的相關(guān)信息連接為一個(gè)完整的記錄。 3、 將用戶需要的信息按照一定格式輸出。 針對(duì) 頁的信息提取，較早的方法是：針對(duì)某一類具體網(wǎng)頁，人工提取該類網(wǎng)頁的內(nèi)容組織模式。然后，信息提取系統(tǒng)根據(jù)該模式從屬于該類的網(wǎng)頁中提取相應(yīng)的內(nèi)容 但這些方法有一個(gè)共同的局限性，那就是需要人工提取內(nèi)容組織模式，這對(duì)于內(nèi)容組織風(fēng)格繁多的說顯然是不適用的。因此，在 ，作者提出了 5 條啟發(fā)式規(guī)則，綜合利用這 5 條規(guī)則系統(tǒng)可以自動(dòng)地發(fā)現(xiàn)網(wǎng)頁中各個(gè)主題信息塊（ 邊界。 出了一種基于視覺相似性來自動(dòng)分析網(wǎng)頁語義結(jié)構(gòu)的方法，該方法首先比較 頁內(nèi)容的視覺相似性，然后使用一個(gè)模式發(fā)現(xiàn)算法來確定這些視覺相似的內(nèi)容最有可能的組織模式，最后按照該模式將內(nèi)容重新組合。 在網(wǎng)頁信息提取過程中，自動(dòng)識(shí)別網(wǎng)頁模式以及按照一定模式從網(wǎng)頁北京大學(xué) 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室碩士學(xué)位論文 10 中提取信息都是很費(fèi)時(shí)的，時(shí)間開銷主要取決于網(wǎng)頁中標(biāo)簽結(jié)構(gòu)的復(fù)雜性以及提取出的模式的復(fù)雜性。傳統(tǒng)的方法必須要從整個(gè)網(wǎng)頁中提取模式，而 不是只針對(duì)主題內(nèi)容提取。由于主題內(nèi)容的結(jié)構(gòu)是相對(duì)簡單的，因此直接從主題內(nèi)容中提取模式或信息可以大大節(jié)省時(shí)間開銷。綜上，在凈化后的網(wǎng)頁上作信息提取不僅可以排除噪音信息對(duì)信息提取的干擾，提高信息提取的準(zhǔn)確性，而且可以使得網(wǎng)頁中的結(jié)構(gòu)簡單化，提高信息提取的效率。 數(shù)據(jù)提取 元數(shù)據(jù)是指面向應(yīng)用的、能被計(jì)算機(jī)所理解和處理的、描述 檔特征的數(shù)據(jù) 長期以來，元數(shù)據(jù)在數(shù)據(jù)庫領(lǐng)域和圖書館領(lǐng)域扮演著重要角色。隨著 研究與應(yīng)用的發(fā)展，單純的網(wǎng)頁內(nèi)容已經(jīng)不能滿足需求，網(wǎng)頁元數(shù)據(jù)得到越來越廣泛的使用。在 息檢索領(lǐng)域，單純依賴關(guān)鍵詞匹配的檢索手段過于單一。內(nèi)容類別、摘要等元數(shù)據(jù)信息的合理使用，不僅使用戶可以從不同的角度進(jìn)行查詢，而且也使得查詢的準(zhǔn)確性得到提高。而主題搜索、個(gè)性化信息服務(wù)以及數(shù)字圖書館也都強(qiáng)烈的依賴資源的元數(shù)據(jù)信息。因此，準(zhǔn)確且高效的提取必要的元數(shù)據(jù)是 各個(gè)研究領(lǐng)域面臨的重要問題。 一個(gè)得到廣泛應(yīng)用的網(wǎng)絡(luò)資源元數(shù)據(jù)標(biāo)準(zhǔn)，它提供了一個(gè)描述網(wǎng)絡(luò)信息資源的元素集合。 在元數(shù)據(jù)提取領(lǐng)域，關(guān)鍵詞提取是一個(gè)比較活躍的分支。在關(guān)鍵詞提取的各種方法中，基于統(tǒng)計(jì)的方法被廣泛的 接受并被證明是有效的。 式通常被用來量化一個(gè)詞項(xiàng)的重要性。但 頁中有著豐富的標(biāo)簽信息，如果將這些有用信息與傳統(tǒng)的公式結(jié)合起來，將會(huì)提高關(guān)鍵詞提取的準(zhǔn)確性。在傳統(tǒng)的摘要提取方法中，摘要是通過選取權(quán)值較高的句子形成的，而句子的權(quán)值則是由它所包含的關(guān)鍵詞的權(quán)值決定的。除此之外，一些啟發(fā)式規(guī)則也起到了重要的作用，比如出現(xiàn)“綜上所述”、“本文論述了”等短語的句子通常有總結(jié)全文的功能。但基于啟發(fā)式規(guī)則的方法過于機(jī)械。 在本文中，我們首先對(duì)凈化后的網(wǎng)頁按照標(biāo)簽結(jié)構(gòu)進(jìn)行語義分段。在分段的基礎(chǔ)上，我們?cè)?每段內(nèi)按照句子的權(quán)值選取重要句子。通過這種方北京大學(xué) 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室碩士學(xué)位論文 11 法，可以保證自動(dòng)生成的摘要能夠覆蓋整篇網(wǎng)頁的內(nèi)容，而不會(huì)被幾個(gè)權(quán)值很高的關(guān)鍵詞所引導(dǎo)。 北京大學(xué) 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室碩士學(xué)位論文 12 第 3章 目前， 息系統(tǒng)通常面臨以下兩個(gè)問題： 一、 有用信息通常伴隨著大量的“噪音”內(nèi)容，而噪音內(nèi)容正是 頁與傳統(tǒng)文檔的一個(gè)主要區(qū)別。根據(jù)噪音內(nèi)容的粒度大小， 全局噪音 ： 全局噪音 是指 具有較大粒度的噪音內(nèi)容，它通常包含鏡像網(wǎng)站以及近似網(wǎng)頁。 全局噪音 內(nèi)容不僅影響了 信息檢索系統(tǒng)（比如搜索引擎）的網(wǎng)頁搜集、索引和檢索結(jié)果排序的質(zhì)量，也使得 局部噪音 ： 局部噪音 是指 頁內(nèi)與網(wǎng)頁主題內(nèi)容無關(guān)的噪音內(nèi)容，比如：廣告、導(dǎo)航條以及版權(quán)聲明等內(nèi)容。 局部噪音 使得應(yīng)用程序很難確切得到網(wǎng)頁的主題內(nèi)容，因此它嚴(yán)重的影響了基于網(wǎng)頁內(nèi)容的應(yīng)用程序。同時(shí)， 局部噪音 很多情況下是伴隨著超鏈出現(xiàn)的，因此， 局部噪音 也對(duì)基于網(wǎng)頁間鏈接關(guān)系的應(yīng)用程序造成影響。 雖然噪音內(nèi)容在某些應(yīng)用程序中是有用的，但對(duì)于大多數(shù)的 息系統(tǒng)而言，它們是有害的。 二、隨著 研究與應(yīng)用的發(fā)展，單純的網(wǎng)頁內(nèi)容已經(jīng)不能滿足需求，網(wǎng)頁元數(shù)據(jù)得到越來越廣泛的使用。在 息檢索領(lǐng)域，單純依賴關(guān)鍵詞匹配的檢索手段過于單一，內(nèi)容類別、摘要等元數(shù)據(jù)信息的合理使用，不僅使用戶可以從不同的角度進(jìn)行查詢，而且也使得查詢的準(zhǔn)確性得到提高。而主題搜索、個(gè)性化以及數(shù)字圖書館也都強(qiáng)烈的依賴資源的元數(shù)據(jù)信息。但網(wǎng)頁的元數(shù)據(jù)信息在網(wǎng)頁中并沒有被明確的表示出來。因此，準(zhǔn)確且高效的提取必要的元數(shù)據(jù)是 各個(gè)研究領(lǐng)域面臨的重要問題。 通過對(duì)各個(gè)領(lǐng)域工作及研究成果的分析，我們發(fā)現(xiàn)不同領(lǐng)域的工作存在兩個(gè)共性： 1、工作結(jié)果的共性。 雖然各個(gè)領(lǐng)域所做的工作都是為了解決網(wǎng)頁復(fù)雜化給本領(lǐng)域帶來的問題，但各個(gè)領(lǐng)域的工作結(jié)果中有著共同的部分。譬如，各個(gè)領(lǐng)域都需要去北京大學(xué) 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室碩士學(xué)位論文 13 除原始網(wǎng)頁中的噪音內(nèi)容，然后在凈化后的網(wǎng)頁上進(jìn)行后續(xù)工作；很多領(lǐng)域都需要獲取網(wǎng)頁的元數(shù)據(jù)信息。即凈化的網(wǎng)頁和元數(shù)據(jù)是它們都需要的結(jié)果。 2、 工作過程的共性。 在獲得不同結(jié)果的過程中存在著共同的中間環(huán)節(jié)。譬如：網(wǎng)頁分類、摘要的提取以及關(guān)鍵詞的選取都需要對(duì)文檔進(jìn)行分詞操作。而這些中間環(huán)節(jié)有時(shí)是整個(gè)工作中效率上的瓶頸。 這些共性啟示我們有可能通過歸納不同應(yīng) 用需求中的通用元素， 并作為一個(gè)模型一次性提取出來，從而對(duì)多種應(yīng)用提供一個(gè)統(tǒng)一的支持?？梢韵胂螅?這樣做既便于提高所需信息的質(zhì)量，又最大限度地避免重復(fù)工作帶來的時(shí)間開銷，從而在信息量和復(fù)雜性這兩個(gè)相互制約的因素之間找到一個(gè)合理的折衷點(diǎn)。 北京大學(xué) 網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室碩士學(xué)位論文 14 第 4章 預(yù)處理方法與技術(shù) 處理框架及結(jié)果描述 處理框架 本文中提出的預(yù)處理框架包括三部分：網(wǎng)頁凈化（局部噪音清除）、近似網(wǎng)頁消除（全局噪