【畢業(yè)學(xué)位論文】（Word原稿）文檔自動(dòng)分類技術(shù)及其在搜索引擎中應(yīng)用的研究-計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)網(wǎng)絡(luò)與分布式系統(tǒng)

北京大學(xué)碩士論文 文檔自動(dòng)分類技術(shù)及其在搜索引擎中應(yīng)用的研究 1 論 文 摘 要 本文首先介紹了 發(fā)展?fàn)顩r，指出 一個(gè)龐大、雜亂、瞬息萬變的信息源泉，僅僅依靠網(wǎng)頁上的超文本鏈用戶是無法方便、快捷地找到自己所需的信息的，提供 息導(dǎo)航服務(wù)的搜索引擎是解決這個(gè)問題的一個(gè)途徑。在介紹了傳統(tǒng)的 搜索引擎和基于人工分類的目錄式搜索引擎的特點(diǎn)并對它們作了比較之后，指出支持分類目錄是 搜索引擎發(fā)展的趨勢，而應(yīng)用文檔自動(dòng)分類領(lǐng)域的研究對收集的網(wǎng)頁自動(dòng)分類，實(shí)現(xiàn)對分類目錄的支持是一種可行的方法。然后，本文介紹了天網(wǎng)搜索引擎的 現(xiàn)狀，分析了它的特點(diǎn)，說明要進(jìn)一步發(fā)展天網(wǎng)系統(tǒng)，應(yīng)當(dāng)采用文檔自動(dòng)分類技術(shù)支持分類目錄。 接下來，本文介紹了文檔自動(dòng)分類的意義和算法的分類，然后分別介紹了類系統(tǒng)和 類系統(tǒng)常用的算法和各個(gè)算法的特點(diǎn)，接著介紹了從 類系統(tǒng)轉(zhuǎn)換到 類系統(tǒng)常用的三種算法以及這兩種分類系統(tǒng)的性能評價(jià)指標(biāo)，然后分析了特征項(xiàng)選取對分類系統(tǒng)的影響，介紹了常用的五種特征項(xiàng)選取的方法。 結(jié)合現(xiàn)有的天網(wǎng)搜索引擎，本文提出了天網(wǎng)系統(tǒng)支持分類目錄的設(shè)計(jì)方 案，詳細(xì)介紹了自動(dòng)分類系統(tǒng)的實(shí)現(xiàn)，說明了分類系統(tǒng)選用的分類算法的是 法，選用的評價(jià)特征項(xiàng)重要性的指標(biāo)是 計(jì)量，選用的轉(zhuǎn)換算法是 法，然后討論了自動(dòng)分類系統(tǒng)在實(shí)現(xiàn)過程中遇到的問題以及解決的辦法： 1 使用兩個(gè)文件描述分類目錄，用 構(gòu)表示類之間的層次結(jié)構(gòu)； 2 通過限制文檔向量最大分量的值顯著地提高了系統(tǒng)分類的性能指標(biāo)； 3 使用稀疏矩陣在程序中表示文檔向量，極大地縮短了分類響應(yīng)時(shí)間，節(jié)省了占用的內(nèi)存空間。在說明了分類系統(tǒng)使用的分類目錄、訓(xùn)練集和測試集之后，本文給出了系統(tǒng)的測試 數(shù)據(jù)。 最后，本文詳細(xì)介紹了將自動(dòng)分類系統(tǒng)集成在現(xiàn)有的天網(wǎng)系統(tǒng)中的方法，討論了對天網(wǎng)系統(tǒng)各個(gè)子系統(tǒng)的改造。 關(guān)鍵詞： 文檔自動(dòng)分類、搜索引擎、 京大學(xué)碩士論文 文檔自動(dòng)分類技術(shù)及其在搜索引擎中應(yīng)用的研究 2 目 錄 目 錄 . 2 第一章 課題研究背景 . 3 第二章 文檔自動(dòng)分類的主要算法和性能評價(jià) . 6 2 1 文檔自動(dòng)分類的主要算法 . 6 2 1 1 算法的分類 . 6 2 1 2 文檔的向量空間模型 . 7 2 1 3 類系統(tǒng) . 8 2 1 4 類系統(tǒng) . 10 2 2 分類系統(tǒng)的性能評價(jià) . 13 2 2 1 類系統(tǒng)的性能評價(jià) . 13 2 2 2 類系統(tǒng)的性能評價(jià) . 15 2 3 特征項(xiàng)的選取 . 17 第三章 自動(dòng)分類系統(tǒng)的實(shí)現(xiàn)及其在天網(wǎng)系統(tǒng)中的應(yīng)用 . 21 3 1 支持分類目錄的天網(wǎng)系統(tǒng)的設(shè)計(jì) . 21 3 2 自動(dòng)分類系統(tǒng)的實(shí)現(xiàn) . 22 3 2 1 自動(dòng)分類算法的選用 . 22 3 2 2 對中文的支持 . 22 3 2 3 自動(dòng)分類系統(tǒng)的實(shí)現(xiàn) . 23 3 2 4 自動(dòng)分類系統(tǒng)的測試 . 27 3 3 現(xiàn)有天網(wǎng)系統(tǒng)各子系統(tǒng)的改造 . 31 3 3 1 收集分析子系統(tǒng)的改造 . 31 3 3 2 詢頁面和查詢處理程序的改造 . 32 第四章 展望 . 33 參考書目 . 35 附錄 . 36 北京大學(xué)碩士論文 文檔自動(dòng)分類技術(shù)及其在搜索引擎中應(yīng)用的研究 3 第一章 課題研究背景 一個(gè)由不同類型和規(guī)模的獨(dú)立自主運(yùn)行和管理的計(jì)算機(jī)網(wǎng)絡(luò)組成的全球范圍的計(jì)算機(jī)網(wǎng)絡(luò)，它的前身是 1969 年美國國防部高級研究計(jì)劃署組建的實(shí)驗(yàn)性網(wǎng)絡(luò) 著計(jì)算機(jī)網(wǎng)絡(luò)和通 信技術(shù)的發(fā)展，各個(gè)國家和組織的網(wǎng)絡(luò)的不斷加入， 成為一個(gè)規(guī)模巨大、自治性強(qiáng)、發(fā)展變化快、用戶訪問頻繁的全球最大的國際互聯(lián)網(wǎng)絡(luò)，截至 1996 年 7 月， 連接了134346 個(gè)網(wǎng)絡(luò)，入網(wǎng)的國家和地區(qū)超過 150 個(gè)，主機(jī) 1228 萬臺(tái)，用戶人數(shù)以億計(jì)。 是一個(gè)無窮無盡的信息源泉，它已深入到人們生產(chǎn)、生活的各個(gè)領(lǐng)域，向人們提供著巨大的并且還在不斷增長的信息資源和服務(wù)，越來越多的公司、企業(yè)通過網(wǎng)頁宣傳自己，越來越多的科研機(jī)關(guān)和學(xué)校通過網(wǎng)頁交流科研成果，越來越多的組織和個(gè)人擁有 了自己的主頁，越來越多的報(bào)刊、雜志加入了 不出戶而知天下事已不再是神話。據(jù)不完全統(tǒng)計(jì)， 1996 年 900 萬，時(shí)至今日，這個(gè)數(shù)目決不會(huì)少于 4 億。 為了讓用戶能夠在如此龐大、雜亂、瞬息萬變的信息海洋中，方便、快捷地找到自己感興趣的信息，而不是茫然不知所措，僅靠網(wǎng)頁上的超文本鏈?zhǔn)沁h(yuǎn)遠(yuǎn)不夠的，提供 息導(dǎo)航服務(wù)的搜索引擎（ 解決這個(gè)問題的一個(gè)途徑。傳統(tǒng)的 搜索引擎通過被稱為 程序自動(dòng)地在網(wǎng)上循著超文本 鏈遞歸地訪問、收集 頁，分析頁面的內(nèi)容，生成索引和摘要，并向用戶提供 詢頁面，根據(jù)用戶的查詢請求在索引庫中查找相關(guān)信息在網(wǎng)上的位置，最后將查詢結(jié)果按照相關(guān)度排序后返回，幫助用戶盡快地找到所需的信息，給用戶帶來了極大的便利。這類搜索引擎的代表有 于人工分類的目錄式搜索引擎稍后出現(xiàn)，它在人工的參與下建立分類目錄，對收集的網(wǎng)頁按主題或者學(xué)科進(jìn)行分類，編寫摘要，用戶可以沿著分類目錄的層次結(jié)構(gòu)，進(jìn)入自己感興趣的主題，進(jìn)而找到所需的信息。這類搜索引擎的代表是 比較這兩種搜索引擎， 搜索引擎自動(dòng)地收集、分析和處理網(wǎng)頁，因北京大學(xué)碩士論文 文檔自動(dòng)分類技術(shù)及其在搜索引擎中應(yīng)用的研究 4 而它索引的網(wǎng)頁數(shù)多，信息量大，并且能定期重新收集網(wǎng)頁，更新索引庫的內(nèi)容，向用戶提供最新的導(dǎo)航信息，但由于它只提供基于關(guān)鍵詞或全文的檢索，用戶只有確切地知道自己想查什么，自己感興趣的網(wǎng)頁應(yīng)當(dāng)含有哪些關(guān)鍵詞時(shí)，查詢的效果才比較理想，否則，返回的結(jié)果很可能和用戶的實(shí)際需要相距甚遠(yuǎn)；目錄式搜索引擎在對網(wǎng)頁的分類和網(wǎng)頁內(nèi)容的理解上引進(jìn)了人工干預(yù)的機(jī)制，因而在查詢的準(zhǔn)確性方面要優(yōu)于 搜索引擎。它支持基于分類目錄的查詢， 當(dāng)用戶對某個(gè)領(lǐng)域感興趣但并不熟悉這個(gè)領(lǐng)域的關(guān)鍵詞時(shí)，這種查詢方式能很好地為用戶提供服務(wù)，而此時(shí) 搜索引擎則基本上無能為力。由于人工分類和摘要編寫的效率低，網(wǎng)頁更新困難，目錄式搜索引擎在索引的網(wǎng)頁的數(shù)量上受到了很大的限制，維護(hù)管理工作量大， 搜索引擎索引的網(wǎng)頁數(shù)早以突破千萬，而 還停留在百萬級的水平。 信息量大是 搜索引擎的一大優(yōu)點(diǎn)，但這也常常使得返回的查詢結(jié)果成千上萬，用戶經(jīng)常需要在一大堆不感興趣的信息中費(fèi)很大力氣才能找 到自己感興趣的網(wǎng)頁，有時(shí)甚至還會(huì)一無所獲，無功而返。如果搜索引擎能夠?qū)κ占木W(wǎng)頁按學(xué)科或者主題進(jìn)行分類，用戶可以選擇只在自己感興趣的領(lǐng)域內(nèi)查詢，這樣就能將許多無關(guān)網(wǎng)頁排除在返回結(jié)果之外，極大地提高查詢結(jié)果的準(zhǔn)確性，方便用戶的使用。目前，支持分類目錄是 搜索引擎發(fā)展的趨勢， 用戶基于分類目錄進(jìn)行查詢時(shí)，系統(tǒng)實(shí)際上是使用目錄式搜索引擎人工處理的數(shù)據(jù)提供服務(wù)。除了采用人工的方法對網(wǎng)頁分類之外，還可以人工建立分類目錄，利用人工智能領(lǐng)域研究的一些技術(shù)對網(wǎng)頁自 動(dòng)分類。搜索引擎大家庭中的后起之秀 采用的就是這種方法，它參照美國國會(huì)圖書館圖書分類的方法，人工建立基于主題的分類目錄，然后通過網(wǎng)上自動(dòng)地收集網(wǎng)頁，采用離線的方式，應(yīng)用文檔自動(dòng)分類技術(shù)對網(wǎng)頁自動(dòng)分類，建立索引，向用戶提供導(dǎo)航服務(wù)。 所謂文檔自動(dòng)分類 2就是指定文檔和預(yù)先定義好的一些類之間的類屬關(guān)系，分類的工作由計(jì)算機(jī)自動(dòng)完成。從分類的準(zhǔn)確性來看，文檔人工分類要優(yōu)于自動(dòng)分類，但這并不說明自動(dòng)分類就沒有存在的價(jià)值。首先，自動(dòng)分類在速度和效率上要大大優(yōu)于人工分類，它 能節(jié)省大量的人力、物力和資金；其次，對于人工分類，如果分類人員的素質(zhì)不夠高，或者面對不熟悉的領(lǐng)域，分類的準(zhǔn)確性很難保北京大學(xué)碩士論文 文檔自動(dòng)分類技術(shù)及其在搜索引擎中應(yīng)用的研究 5 證，在這個(gè)時(shí)候，自動(dòng)分類系統(tǒng)可以作為人工分類的輔助工具，分類人員可以參考自動(dòng)分類的結(jié)果，作出正確的判斷，提高分類的準(zhǔn)確性。 采用文檔自動(dòng)分類技術(shù)，對收集的網(wǎng)頁自動(dòng)分類，實(shí)現(xiàn)對分類目錄的支持既保持了傳統(tǒng)的 搜索引擎索引網(wǎng)頁多、信息量大的特點(diǎn)，又保證了分類的效率，同時(shí)，在文檔自動(dòng)分類領(lǐng)域的研究成果保證了分類的準(zhǔn)確性。 1994 年，我國正式加入 過幾年的迅猛發(fā)展，至 1998 年底已經(jīng)形成了以 大網(wǎng)為主干，遍布全國的互聯(lián)網(wǎng)絡(luò)，注冊域名 18396 個(gè)，直連主機(jī) 臺(tái)，撥號上網(wǎng)的計(jì)算機(jī) 63萬臺(tái)， 點(diǎn)超過 8000 個(gè)，上網(wǎng)用戶 210 萬人， 1999 年 3 月，用戶人數(shù)已突破 300 萬。為了方便日益增多的國內(nèi)用戶，促進(jìn) 尤其是 中文信息的交流，增強(qiáng)全世界華人的凝聚力， “九五”攻關(guān)項(xiàng)目“計(jì)算機(jī)信息網(wǎng)絡(luò)及其應(yīng)用關(guān)鍵技術(shù)研究”中設(shè)立了“中文編碼和分布式中英文信息發(fā)現(xiàn)”子專題，北京大學(xué) 網(wǎng)絡(luò)研究室承擔(dān)了該子專題的部分研究開發(fā)工作，設(shè)計(jì)開發(fā)了“天網(wǎng)”中英文搜索引擎（ 3。 1997 年 10 月 29 日，天網(wǎng)搜索引擎正式在 提供查詢服務(wù)，到現(xiàn)在為止，天網(wǎng)索引的網(wǎng)頁數(shù)超過100 萬，新聞組信息 30 萬條，訪問人次達(dá)到一百萬，點(diǎn)擊次數(shù)突破一千萬，軟件世界（ 1998 年 7 月）將天網(wǎng)評為國內(nèi)最值得關(guān)注的搜索引擎， 1998 年 12 月，天網(wǎng)通過了 鑒定。 天網(wǎng)是典型的 搜索引擎，它立足于國內(nèi)，主要收集大陸和香港地區(qū)的網(wǎng)頁，支持多種中文編碼，基于詞建立索引，索 引的網(wǎng)頁數(shù)在國內(nèi)的搜索引擎中名列前茅，查詢的響應(yīng)速度極快，是網(wǎng)上用戶訪問國內(nèi)資源的強(qiáng)有力的導(dǎo)航工具，受到了廣泛的好評。但是，也有一些用戶抱怨天網(wǎng)查詢的結(jié)果不夠準(zhǔn)確，有用的信息常常夾雜在一大堆無關(guān)的東西中返回，為了把它們找出來需要不斷地向后翻頁，很是麻煩，還有一些用戶在希望天網(wǎng)能支持分類目錄。為了適應(yīng)時(shí)代發(fā)展的需要，進(jìn)一步發(fā)展天網(wǎng)系統(tǒng)，提高它的性能，更好地滿足用戶的需求，同時(shí)借鑒 成功經(jīng)驗(yàn)，在已有“天網(wǎng)”的基礎(chǔ)上，應(yīng)當(dāng)采用對收集的頁面自動(dòng)分類的方法，實(shí)現(xiàn)對分類目錄的支持，我的論文工 作就是圍繞這個(gè)目標(biāo)展開的，在對當(dāng)前常用的文檔自動(dòng)分類算法作了認(rèn)真的調(diào)查之后，選用 法實(shí)現(xiàn)了一個(gè)自動(dòng)分類系統(tǒng)，并提出了在現(xiàn)有天網(wǎng)系統(tǒng)基礎(chǔ)上支持分類目錄的設(shè)北京大學(xué)碩士論文 文檔自動(dòng)分類技術(shù)及其在搜索引擎中應(yīng)用的研究 6 計(jì)方案。 第二章 文檔自動(dòng)分類的主要算法和性能評價(jià) 文檔自動(dòng)分類屬于信息檢索領(lǐng)域的研究范疇，它涉及人工智能、近世代數(shù)、概率統(tǒng)計(jì)等多個(gè)領(lǐng)域。為了推進(jìn)在信息檢索領(lǐng)域的研究，交流研究成果，評價(jià)各種算法的優(yōu)劣，美國國家標(biāo)準(zhǔn)和技術(shù)研究院（ 信息訪問和用戶界面公司（ 息技術(shù)實(shí)驗(yàn)室（ 然語言處理和信息檢索部（ 美國國防部高級研究計(jì)劃署信息技術(shù)處共同主持召開了信息檢索會(huì)議（ 至今已召開了七次。 議實(shí)際上是信息檢索系統(tǒng)的擂臺(tái)賽，一些大學(xué)包括一些公司帶著自己開發(fā)的文檔分類系統(tǒng)參加會(huì)議，由大會(huì)使用相同的訓(xùn)練集和測試用例對這些系統(tǒng)進(jìn)行評測，從第三次會(huì)議開始，大會(huì)增加了西班牙文分類系統(tǒng)的評測，從第五次會(huì)議開始，增加了對中文分類系統(tǒng)的評測，和面向英文的分類系統(tǒng)相比，中文分類系統(tǒng)的起步較晚，實(shí)際上，參加 中文分類系統(tǒng)處理的重點(diǎn)還停留在中文的切詞上?？梢哉f， 在展示的文檔分類系統(tǒng)代表了文檔分類領(lǐng)域的最新研究成果。 在國內(nèi)做這方面工作的主要有兩家：一個(gè)是復(fù)旦大學(xué)計(jì)算機(jī)系，另一個(gè)是光公司，實(shí)際上，曙光公司使用的文檔自動(dòng)分類系統(tǒng)是由復(fù)旦大學(xué)計(jì)算機(jī)系開發(fā)的。 2 1 文檔自動(dòng)分類的主要算法 2 1 1 算法的分類 基于計(jì)算機(jī)的文檔分類算法主要分以下三類：簡單詞匹配法，基于同義詞的詞匹配法和經(jīng)驗(yàn)學(xué)習(xí)法。簡單詞匹配法是最簡單，最直接的文檔分類算法，它根據(jù)文檔和類名中共同出現(xiàn)的詞決定文檔屬于哪些類，很顯然，這種算法的分類規(guī)則過于簡單，機(jī)械，分類效果極差 ?；谕x詞的詞匹配法是對簡單詞匹配法的北京大學(xué)碩士論文 文檔自動(dòng)分類技術(shù)及其在搜索引擎中應(yīng)用的研究 7 改進(jìn)，它先定義一張同義詞表（可以是機(jī)器自動(dòng)生成的，也可以是手工創(chuàng)建的），然后根據(jù)文檔和類名以及類的描述中共同出現(xiàn)的詞（含同義詞）決定文檔屬于哪些類。這種分類算法擴(kuò)大了詞的匹配范圍，在性能上要優(yōu)于簡單詞匹配法。不過，這種算法的分類規(guī)則仍然很機(jī)械，而且同義詞表的構(gòu)成是靜態(tài)的，對文檔的上下文不敏感，無法正確處理文檔中其具體含義依賴于上下文的詞，分類的準(zhǔn)確度還是很低。經(jīng)驗(yàn)學(xué)習(xí)法和詞匹配法在分類機(jī)制上有著本質(zhì)的不同，它的基本思路是先收集一些與待分類文檔同處一個(gè)領(lǐng)域的文檔作為訓(xùn)練 集（ 由專家人工進(jìn)行分類，保證分類的準(zhǔn)確性，然后分析這些已分好類的文檔，從中挖掘詞和類之間的語義聯(lián)系，最后再利用學(xué)到的知識(shí)對文檔分類，而不再是機(jī)械地按詞進(jìn)行匹配。經(jīng)驗(yàn)學(xué)習(xí)法在文檔分類的準(zhǔn)確性方面要大大優(yōu)于詞匹配法，目前實(shí)用的分類系統(tǒng)都是采用這種分類方法。本文介紹的幾種文檔分類算法都屬于經(jīng)驗(yàn)學(xué)習(xí)法。 2 1 2 文檔的向量空間模型 待分類的文檔和訓(xùn)練集中的文檔在分類和訓(xùn)練時(shí)用何種形式表示是一個(gè)很實(shí)際的問題。 1969 年， 出了向量空間模型 是文檔表示的一個(gè) 統(tǒng)計(jì)模型，該模型以特征項(xiàng)（ 為文檔表示的基本單位，特征項(xiàng)由字，詞和短語組成。 令 D=示文檔集， T=示特征項(xiàng)集，它由文檔集 D 中的所有或部分特征項(xiàng)組成，文檔 特征項(xiàng)空間中的向量 表示， 示特征項(xiàng) 文檔 的權(quán)重， 示特征項(xiàng) 文檔 出現(xiàn)的頻率，稱為項(xiàng)頻， 表示文檔集 D 中出現(xiàn)了特征項(xiàng) 文檔的數(shù)目，稱為文檔頻率。 量空間模型是目前最好的文檔表示模型，參加 大部分文檔分類系統(tǒng)都采用 這種模型，不同系統(tǒng)都著重在特征項(xiàng)的選取，短語的生成，查詢擴(kuò)展和權(quán)重評價(jià)等四個(gè)方面作文章，以提高系統(tǒng)的性能。 北京大學(xué)碩士論文 文檔自動(dòng)分類技術(shù)及其在搜索引擎中應(yīng)用的研究 8 2 1 3 類系統(tǒng) 根據(jù)分類結(jié)果的不同，采用經(jīng)驗(yàn)學(xué)習(xí)法的文檔分類系統(tǒng)又可以分成兩類：類系統(tǒng)和 類系統(tǒng)。 給定一篇文檔，這種分類系統(tǒng)對每一個(gè)類都獨(dú)立地判斷這篇文檔是否屬于該類，不同類之間互不影響。 類系統(tǒng)常用的分類算法如下： 策樹， 4 決策樹是 常用的一種歸納算法，它通過對訓(xùn)練數(shù)據(jù)的學(xué)習(xí)總結(jié)出一般化，普遍化，概括化的規(guī)則，然后再利用這些規(guī)則分析，解決問題。用決策樹進(jìn)行文檔分類的基本思路是這樣的：先用訓(xùn)練集為預(yù)先定義的每一個(gè)類構(gòu)造一棵決策樹，構(gòu)造方法如下： 以訓(xùn)練集作為樹的根結(jié)點(diǎn)，它表示所有的訓(xùn)練文檔，將它標(biāo)記為“未被檢測”； 找到一個(gè)標(biāo)記為“未被檢測”的葉結(jié)點(diǎn)，如果它表示的所有文檔都屬于這個(gè)類，或者都不屬于這個(gè)類，將這個(gè)葉 結(jié)點(diǎn)的標(biāo)記改為“已被檢測”，然后直接跳到第三步；否則，挑選當(dāng)前最能區(qū)分這個(gè)結(jié)點(diǎn)表示的文檔集中屬于這個(gè)類的文檔和不屬于這個(gè)類的文檔的特征項(xiàng)作為這個(gè)結(jié)點(diǎn)的屬性值，然后以這個(gè)結(jié)點(diǎn)為父結(jié)點(diǎn)，增添兩個(gè)新的葉結(jié)點(diǎn)，都標(biāo)記為“未被檢測”，父結(jié)點(diǎn)表示的訓(xùn)練文檔集中含有這個(gè)特征項(xiàng)的所有文檔用左子結(jié)點(diǎn)表示，所有不含有這個(gè)特征項(xiàng)的文檔用右子結(jié)點(diǎn)表示； 重復(fù)第二步操作，直到所有的葉結(jié)點(diǎn)都被檢測過了，此時(shí)，決策樹就構(gòu)造好了。 每個(gè)類的決策樹都構(gòu)造好了以后，就可以用它們進(jìn)行分類。分類的方法很簡單，對每 棵決策樹，從它的根結(jié)點(diǎn)開始，判斷結(jié)點(diǎn)的屬性值（特征項(xiàng)）是否在待分類的文檔中出現(xiàn)，如果出現(xiàn)，則沿著左子樹向下走；否則沿著右子樹向下，再繼續(xù)判斷當(dāng)前結(jié)點(diǎn)的屬性值是否在待分類的文檔中出現(xiàn)，直到到達(dá)決策樹的某個(gè)葉結(jié)點(diǎn)，如果這個(gè)葉結(jié)點(diǎn)表示的訓(xùn)練文檔都屬于這個(gè)類，則判定這篇待分類的文檔也屬于這個(gè)類；反之亦然。 決策樹算法的構(gòu)造復(fù)雜度取決于特征集的大小和決策樹的內(nèi)部結(jié)點(diǎn)數(shù)，分類復(fù)雜度取決于決策樹的內(nèi)部結(jié)點(diǎn)數(shù)。目前常用的分類系統(tǒng)中有兩個(gè)使用決策樹算北京大學(xué)碩士論文 文檔自動(dòng)分類技術(shù)及其在搜索引擎中應(yīng)用的研究 9 法的分類系統(tǒng)： 們構(gòu)造的決策樹的內(nèi)部結(jié)點(diǎn)數(shù)一般控制在 200以內(nèi)，這主要是因?yàn)閮?nèi)部結(jié)點(diǎn)數(shù)目越多，計(jì)算越復(fù)雜，從可計(jì)算的角度考慮，內(nèi)部結(jié)點(diǎn)數(shù)不能太多。 簡單 法 這種方法的基本思想是給定一個(gè)類和一篇文檔，利用 概率公式：P(A|B)=P(B|A)*P(A)/P(B)，根據(jù)這個(gè)類對于每個(gè)特征項(xiàng)的條件概率計(jì)算它對于這篇文檔的條件概率。 給定一個(gè)類和一篇文檔，令 ， 其中 示文檔中出現(xiàn)的第 i 個(gè)特征項(xiàng)， n 為文檔中出現(xiàn)的特征項(xiàng)的總數(shù)。根據(jù)全概率公式，我們可以得到如下式子： P( + | = P( + ) * P( + ) / P( ； P( - | = P( - ) * P( - ) / P( ； 其中 P( = P(a1 P( + )表示待分類的文檔所處的領(lǐng)域中的文檔屬于這個(gè)類的概率， P( - )表示不屬于這個(gè)類的概率，在具體的計(jì)算中可以分別用訓(xùn)練集中屬于和不屬于這個(gè)類的文檔所占的比例代替。 如果 P( + | P( - | ， 法就判定這篇文檔屬于這個(gè)類；否則就判定這篇文檔不屬于這個(gè)類，算法的 關(guān)鍵是如何計(jì)算 P( + )和P( - )。 為了使這兩個(gè)概率可計(jì)算，簡單 1）對于屬于這個(gè)類的文檔，特征項(xiàng)之間是獨(dú)立無關(guān)的；（ 2）對于不屬于這個(gè)類的文檔，特征項(xiàng)之間也是獨(dú)立無關(guān)的。于是， P()和 P()可以化簡成： P()=P()*P()* *P() (1)； P()=P()*P()* *P() (2)； 對于任意一個(gè)特征項(xiàng) t， P(t|+)可以近似地用特征項(xiàng) 于這個(gè)類的文檔中出現(xiàn)的次數(shù)與訓(xùn)練集中所有屬于這個(gè)類的文檔中特征項(xiàng)出現(xiàn)的總次數(shù)的比值表示， P(t|-)可以近似地用特征項(xiàng) 們都是可計(jì)算的。簡單 法利用兩條假設(shè)極大地降低了計(jì)北京大學(xué)碩士論文 文檔自動(dòng)分類技術(shù)及其在搜索引擎中應(yīng)用的研究 10 算的復(fù)雜度，使得算法的實(shí)現(xiàn)成為可能，但是這兩條假設(shè)缺乏嚴(yán)格的理論推導(dǎo)作為基礎(chǔ)，無法保證它的正確性，這也在一定程度上限制了算法的性能。 神經(jīng)網(wǎng)絡(luò) 神經(jīng)網(wǎng)絡(luò)也是 常用的一種算法，它以人類的思維活動(dòng)為模型。神經(jīng)網(wǎng)絡(luò)的基本單位是神經(jīng)結(jié)點(diǎn)，它有輸入，輸出，閾值三個(gè)元素組成，將這些神經(jīng)結(jié)點(diǎn)級連在一起，就形成神經(jīng)網(wǎng)絡(luò)。目前常用的文檔分類系統(tǒng)中有兩個(gè)系統(tǒng)采用了神經(jīng)網(wǎng)絡(luò)算法：一個(gè)是 司開發(fā)的 一個(gè)是 兩個(gè)系統(tǒng)都為每個(gè)類建立了一個(gè)獨(dú)立的神經(jīng)網(wǎng)絡(luò)，通過訓(xùn)練集學(xué)習(xí)從特征項(xiàng)映射到類的非線性關(guān)系，然后再利用學(xué)到的知識(shí)對文檔進(jìn)行分類。 納算法 這種算法和決策樹算法一樣，也是 常用的一種算法，它在原理上和決策樹算法具有相同的歸納能力。 法 法是用于文檔分類的經(jīng)典的向量空間模型算法，它的基本思想是使用訓(xùn)練集為每個(gè)類構(gòu)造一個(gè)原型向量，構(gòu)造方法如下：給定一個(gè)類，訓(xùn)練集中所有屬于這個(gè)類的文檔對應(yīng)向量的分量用正數(shù)表示，所有不屬于這個(gè)類的文檔對應(yīng)向量的分量用負(fù)數(shù)表示，然后把所有的向量加起來，得到的和向量就是這個(gè)類的原型向量，定義兩個(gè)向量的相似度為這兩個(gè)向量夾角的余弦，逐一計(jì)算訓(xùn)練集中所有文檔和原型向量的相似度，然后按一 定的算法從中挑選某個(gè)相似度作為界。給定一篇文檔，如果這篇文檔與原型向量的相似度比界大，則這篇文檔屬于這個(gè)類，否則這篇文檔就不屬于這個(gè)類。 法的突出優(yōu)點(diǎn)是容易實(shí)現(xiàn)，計(jì)算（訓(xùn)練和分類）特別簡單，它通常用來實(shí)現(xiàn)衡量分類系統(tǒng)性能的基準(zhǔn)系統(tǒng)，而實(shí)用的分類系統(tǒng)很少采用這種算法解決具體的分類問題。 2 1 4 類系統(tǒng) 給定一篇文檔， 類系統(tǒng)對所有預(yù)先定義的類綜合考慮，輸出候選類北京大學(xué)碩士論文 文檔自動(dòng)分類技術(shù)及其在搜索引擎中應(yīng)用的研究 11 列表，給出這篇文檔和各個(gè)候選類的相關(guān)度并按此排序。這種分類系統(tǒng)可用于人機(jī)交互環(huán)境下的計(jì)算機(jī)輔助分類，工作人員 根據(jù)系統(tǒng)返回的候選類列表決定文檔應(yīng)該屬于哪些類。 下面介紹 法 這種算法實(shí)際上不屬于經(jīng)驗(yàn)學(xué)習(xí)法，它就是前面介紹的詞匹配法，是一種最簡單、非學(xué)習(xí)的算法。在這種算法里，待分類的文檔和類名都用 型表示，定義文檔和類之間的相識(shí)度為它們對應(yīng)的向量的夾角余弦，逐一計(jì)算待分類文檔和各個(gè)類的相識(shí)度，然后按相似度排序就得到了候選類列表。這種算法主要是用來和其他學(xué)習(xí)算法進(jìn)行比較，看看采用其他算法能在多大程度上提高分類系統(tǒng)的性能，當(dāng)兩種分類算法不能直接進(jìn)行比較時(shí)， 為它們的參照物。 法 5 這是一種多元線性回歸算法，它通過對訓(xùn)練集文檔的學(xué)習(xí)，構(gòu)造一個(gè)多元回歸模型描述特征項(xiàng)和類之間的線性關(guān)系。用 j 個(gè)特征項(xiàng)， 陣 特征項(xiàng)之間的關(guān)系， 矩陣 類之間的類屬關(guān)系， 或 1， 表示文檔 j； 表示文檔 j， 出矩陣 X，使得 |E=最小，矩陣類之間的線性關(guān)系， 出矩陣 X 后，對待分類的文檔 算 C=， 最近鄰居算法（ 6 這種算法和 先將訓(xùn)練集中的文檔用 后對預(yù)先定義的每一個(gè)類，將訓(xùn)練集中所有屬于這個(gè)類的文檔對應(yīng)的向量求和，再除以屬于這個(gè)類的文檔的總數(shù)，這個(gè)步驟實(shí)際上求出屬于這個(gè) 類的文檔在北京大學(xué)碩士論文 文檔自動(dòng)分類技術(shù)及其在搜索引擎中應(yīng)用的研究 12 向量空間的幾何中心（質(zhì)心），并以此作為這個(gè)類的原型向量。和前面介紹的幾種方法一樣，這種算法也以向量夾角的余弦作為向量之間的相似度，給定一篇文檔，逐一計(jì)算它和各個(gè)類的原型向量的相似度，哪個(gè)類的原型向量和它的相似度最大，它就屬于哪個(gè)類。這種方法的特點(diǎn)和 的計(jì)算非常簡單，復(fù)旦大學(xué)開發(fā)的分類系統(tǒng)使用的就是這種算法。 法 法可以說是從 法上衍生出來的， 法是找一個(gè)最近的鄰居，而 個(gè)最近的鄰居。給定一篇文 檔， 是計(jì)算訓(xùn)練集中所有文檔和這篇文檔的夾角余弦即相似度，然后從中挑出與之最相關(guān)（相似度最大）的 K 篇文檔，這 選類與這篇文檔的相關(guān)度用這 再假設(shè)一個(gè)類只有一個(gè)中心，在這一點(diǎn)上它要優(yōu)于 法和 法，但它的分類響應(yīng)時(shí)間要長于 N 算法，計(jì)算復(fù)雜度和訓(xùn)練集中的文檔數(shù)目成正比，不過，由于 法本身簡單而且有效，所以這并不妨礙它和簡單 法， 法， 法一樣，是在大型應(yīng)用中可以使用的分類算法。 在有些應(yīng)用場合，要求分類系統(tǒng)明確判定給定的這篇文檔屬于哪些類，顯然，類系統(tǒng)能滿足這種需求，而 類系統(tǒng)則需要對輸出的結(jié)果進(jìn)行轉(zhuǎn)換才能提供這種功能。常用的轉(zhuǎn)換算法如下： 置截尾法 ) 設(shè)分類系統(tǒng)定義的候選類列表的長度為 m，系統(tǒng)預(yù)先根據(jù)經(jīng)驗(yàn)定義一個(gè)結(jié)尾位置 k， k 的取值在 1 和 m 之間，對每篇待分類的文檔，分類系統(tǒng)都返回一個(gè)長為 候選類列表的前 篇文檔就屬于這 不屬于其他的類。這種轉(zhuǎn)換算法在實(shí)現(xiàn)上非常簡單，但它存在很嚴(yán)重的問題：設(shè)待分類的文檔數(shù)目為 n，候選類列表的每個(gè)位置都對應(yīng) 括相同的類），即使 ，也會(huì)有 法平滑地調(diào)整分類系統(tǒng)的性能。 北京大學(xué)碩士論文 文檔自動(dòng)分類技術(shù)及其在搜索引擎中應(yīng)用的研究 13 例截尾法 ) 設(shè)待分類的文檔數(shù)目為 n，預(yù)先定義的類數(shù)為 m， 示訓(xùn)練集中屬于類 據(jù)每篇待分類文檔的候選類列表，系統(tǒng)生成每個(gè)類的候選文檔列表，并按類和文檔的相關(guān)度排序，對類 i，取這個(gè)類的候選文檔列表中的前 n* 他的 文檔則不屬于這個(gè)類。在這里， 過改變它的大小，可以平滑地調(diào)整系統(tǒng)的性能。 法的基本思想是控制分入各個(gè)類的文檔數(shù)，使它們保持訓(xùn)練集中各個(gè)類文檔數(shù)的比例關(guān)系，這種算法最大的問題是過分依賴于這種比例關(guān)系，而沒有考慮類和文檔的相關(guān)度以及類在候選類列表中的位置。 優(yōu)截尾法 ) 這種方法的基本思路是給定一篇待分類的文檔，先計(jì)算每個(gè)類的最優(yōu)截尾相關(guān)度，然后給出這篇文檔的候選類列表，對于候選類列表里的每一個(gè)類，如果這篇文檔和這個(gè)類的相關(guān)度大于這個(gè)類的最優(yōu)截尾相關(guān)度，那么這篇文檔就屬于這個(gè)類，否則，這篇文檔就不屬于這個(gè)類。將訓(xùn)練集分成兩部分，其中一部分仍然作為訓(xùn)練集，另一部分作為測試集，對每一個(gè)類，評價(jià)分類系統(tǒng)在這個(gè)測試集下對于這個(gè)類的分類性能，調(diào)整截尾相關(guān)度，使得系統(tǒng)的性能達(dá)到最優(yōu)，此時(shí)截尾相關(guān)度的值就是這個(gè)類的最優(yōu)截尾相關(guān)度。 上面介紹的這三種轉(zhuǎn)換算法中， 次是 次是 2 2 分類系統(tǒng)的性能評價(jià) 2 2 1 類系統(tǒng)的性能評價(jià) 1 評價(jià)方法 類系統(tǒng)的輸入是一篇待分類的文檔，輸出是按照相關(guān)度排序的候選類列表，給定一個(gè)閾值（ 如果這篇文檔與某個(gè)候選類的相關(guān)度大于這個(gè)閾值，那北京大學(xué)碩士論文 文檔自動(dòng)分類技術(shù)及其在搜索引擎中應(yīng)用的研究 14 么它就屬于這個(gè)類，否則它就不屬于這個(gè)類），對每篇輸入的文檔，定義： F=候選類列表中與這篇文檔的相關(guān)度大于閾值的類的數(shù)目； C=這篇文檔實(shí)際所屬的類的數(shù)目； 選類列表中這篇文檔實(shí)際所屬且與之相關(guān)度大于閾值的類的數(shù)目； 召回率 =； 精度 =； 評價(jià) 111均精度），它的計(jì)算步驟如下： 1）對每篇文檔，計(jì)算它的候選類列表上每個(gè)它實(shí)際屬于的類所在位置對應(yīng)的召回率和精度 ； 2）將召回率劃分成十個(gè)區(qū)間： 0%， 10%)， 90%， 100%)，再將第一步求出的精度按照它對應(yīng)的召回率劃入相應(yīng)的區(qū)間，用每個(gè)區(qū)間的最大精度作為區(qū)間左界，即 0%， 90%，對應(yīng)的召回率的代表精度，如果某個(gè)區(qū)間為空，就用0作為這個(gè)區(qū)間的代表精度； 3）如果 100%的召回率能達(dá)到，就用它對應(yīng)的精度作為它的代表精度；如果不能達(dá)到，就用最接近 100%的召回率對應(yīng)的精度代替。 4）對 0%， 100%這 11 個(gè)召回率，用每個(gè)召回率和比它大的召回率對應(yīng)的代表精度的最大值代替它的代表精度； 5）計(jì)算所有測 試文檔在這 11個(gè)召回率上的平均代表精度 ）計(jì)算這 11 個(gè)召回率的平均代表精度 平均值，得到的平均值就是分類系統(tǒng)的 11 2 評價(jià)結(jié)果 使用路透社 5個(gè)版本的新聞稿作為訓(xùn)練集和測試集對 6： 版本 1 版本 2 版本 本 3 版本 4 28 22 22 80 93 91 92 京大學(xué)碩士論文 文檔自動(dòng)分類技術(shù)及其在搜索引擎中應(yīng)用的研究 15 復(fù)旦大學(xué)計(jì)算機(jī)系開發(fā)的分類系統(tǒng)用新華 社的新聞稿評測的數(shù)據(jù)如下 7： ) ) ) ) 74 83 88 90 其中 測試文檔數(shù) *100%。 假設(shè) 00%，則 11+= 2 2 2 類系統(tǒng)的性能評價(jià) 1 評價(jià)方法 給定一個(gè)測試集，對每一個(gè)類，可以用這樣一個(gè)表來表示分類情況： 屬于這個(gè)類的文檔 不屬于這 個(gè)類的文檔 系統(tǒng)判定屬于該類的文檔 a b 系統(tǒng)判定不屬于該類的文檔 c d 令 n=a+b+c+d； 義： b/(b+d)=(b/n)/(b+d)/n)=P(不屬于這個(gè)類 系統(tǒng)判斷屬于這個(gè)類 )/P(不屬于這個(gè)類 )=P(系統(tǒng)判斷屬于這個(gè)類 |不屬于這個(gè)類 )； 召回率 =a/(a+c)=(a/n)/(a+c)/n)=P(屬于這個(gè)類 系統(tǒng)判定屬于這個(gè)類 )/P(屬于這個(gè)類 )=P(系統(tǒng)判定屬于這個(gè)類 |屬于這個(gè)類 )； 精度 =a/(a+b)=(a/n)/(a+b)/n)=P(屬于這個(gè)類 系統(tǒng)判定屬于這個(gè)類 )/P(系統(tǒng)判定屬于這個(gè)類 )=P(屬于這個(gè)類 |系統(tǒng)判定屬于這個(gè)類 )； 評價(jià)系統(tǒng)的整體性能有兩種常用的方法： 計(jì)算每個(gè)類的性能指標(biāo)，然后求出這些指標(biāo)的平均值來衡量系統(tǒng)的整體性能。 統(tǒng)計(jì)出每個(gè)類的分類情況表，然后求每個(gè)表單元對于所有的類的總和得到系統(tǒng)的總體分類情況表，再分別計(jì)算相應(yīng)的性能指標(biāo)。 有考慮每個(gè)類占的比例的不同，而是給予北京大學(xué)碩士論文 文檔自動(dòng)分類技術(shù)及其在搜索引擎中應(yīng)用的研究 16 相同的權(quán)值， 每篇文檔給予相同的權(quán)值，考慮到了大類和小類在反映系統(tǒng)整體性能上的不同地位，（在整體性能上，大類是起決定作用的），因此在評價(jià)系統(tǒng)的整體性能上， 優(yōu)于 目前常用的評價(jià) 類系統(tǒng)的性能的方法是綜合考慮召回率和精度這兩個(gè)性能指標(biāo)，根據(jù)前面的分析，精度 =P(屬于這個(gè)類 |系統(tǒng)判定屬于這個(gè)類 )，召回率 =P(系統(tǒng)判定屬于這個(gè)類 |屬于這個(gè)類 )，令 P=P(屬于這個(gè)類 )，利用全概率公式有： 精度 =召回 率 *P(屬于這個(gè)類 )/P(系統(tǒng)判定屬于這個(gè)類 )； P(系統(tǒng)判定屬于這個(gè)類 )=P(屬于這個(gè)類 系統(tǒng)判定屬于這個(gè)類 )+P(不屬于這個(gè)類 系統(tǒng)判定屬于這個(gè)類 )=P(系統(tǒng)判定屬于這個(gè)類 |屬于這個(gè)類 )*P(屬于這個(gè)類 )+P(系統(tǒng)判定屬于這個(gè)類 |不屬于這個(gè)類 )*P(不屬于這個(gè)類 )； 精度 =P*召回率 /(P*召回率 +(1 對一個(gè)分類系統(tǒng)，召回率是屬于這個(gè)類的文檔被判定為屬于這個(gè)類的概率，精度是被判定為這個(gè)類的文檔確實(shí)屬于這個(gè)類的概率，如果加強(qiáng)將一篇文檔判斷為屬于某個(gè)類的限制條件，如提高截尾相關(guān)度 ， 回率會(huì)下降，但相應(yīng)地，錯(cuò)誤地被判定為屬于這個(gè)類的文檔數(shù)目也會(huì)減少， 般情況下，此時(shí)精度就會(huì)上升；類似地，減弱將一篇文檔判斷為屬于某個(gè)的限制條件，如降低截尾相關(guān)度， 回率會(huì)上升，但相應(yīng)地，錯(cuò)誤地被判定為屬于這個(gè)類的文檔數(shù)目也會(huì)增加， 般情況下，此時(shí)精度就會(huì)下降。因此分類系統(tǒng)通常通過調(diào)整閾值和一些參數(shù)的值在精度和召回率之間進(jìn)行取舍，為了獲得較高的召回率，就需要犧牲系統(tǒng)的精度；反之亦然。如果可以通過對閾值和參數(shù)的調(diào)整使得精度和召回率的值相等，這個(gè)值就 被稱為系統(tǒng)的 評價(jià) 檔分類系統(tǒng)常用的性能指標(biāo)之一。如果不能使得精度和召回率的值正好相等，就用最接近的精度和召回率的值的平均值來代替，這個(gè)值稱作 精度和召回率的值相距甚遠(yuǎn)時(shí)，使用 一個(gè)經(jīng)常用來評價(jià)系統(tǒng)的整體性能的指標(biāo)是精度和召回率的調(diào)和平均值： (1/精度 +1/召回率 )，它的大北京大學(xué)碩士論文 文檔自動(dòng)分類技術(shù)及其在搜索引擎中應(yīng)用的研究 17 小主要取決于召回率和精度中較小的那一個(gè)，當(dāng)召回率 =精度時(shí)， 最大值。 2 評價(jià) 結(jié)果 使用路透社 5個(gè)版本的新聞稿作為訓(xùn)練集和測試集對一些常見的分類系統(tǒng)的性能評測結(jié)果如下： 版本 1 版本 2 版本 3 版本 4 80 76 75 71 觀察上表中給出的性能指標(biāo)，可以得出如下結(jié)論： 性能最好的分類系統(tǒng)， 性能也還不錯(cuò)，簡單 然不能考慮 統(tǒng)）， 為衡量其它系統(tǒng)性