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

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