文本分類概述

1、文本分類概述第一章 緒 論研究背景當(dāng)今的時(shí)代，是一個(gè)信息技術(shù)飛速發(fā)展的時(shí)代。隨著信息技術(shù)的飛速發(fā)展，科學(xué)知識(shí)也在短時(shí)間內(nèi)發(fā)生了急劇的、爆炸性的增長(zhǎng)。據(jù)1998年的資料顯示1，70年代以來(lái)，全世界每年出版圖書(shū)50萬(wàn)種，每一分鐘就有一種新書(shū)出版。80年代每年全世界發(fā)表的科學(xué)論文大約500萬(wàn)篇，平均每天發(fā)表包含新知識(shí)的論文為萬(wàn)萬(wàn)篇；登記的發(fā)明創(chuàng)造專利每年超過(guò)30萬(wàn)件，平均每天有800-900件專利問(wèn)世。近二十年來(lái)，每年形成的文獻(xiàn)資料的頁(yè)數(shù)，美國(guó)約1,750億頁(yè)。另?yè)?jù)聯(lián)合國(guó)教科文組織所隸屬的“世界科學(xué)技術(shù)情報(bào)系統(tǒng)”曾做的統(tǒng)計(jì)顯示，科學(xué)知識(shí)每年的增長(zhǎng)率，60年代以來(lái)已從增長(zhǎng)到，到80年代每年增長(zhǎng)率達(dá)。據(jù)

2、說(shuō)，一位化學(xué)家每周閱讀40小時(shí)，光是瀏覽世界上一年內(nèi)發(fā)表的有關(guān)化學(xué)方面的論文和著作就要讀48年。而2005年的資料顯示2，進(jìn)入20世紀(jì)后全世界圖書(shū)品種平均20年增加一倍，冊(cè)數(shù)增加兩倍。期刊出版物，平均10年增加一倍?？萍嘉墨I(xiàn)年均增長(zhǎng)率估計(jì)為13，其中某些學(xué)科的文獻(xiàn)量每10年左右翻一番，尖端科技文獻(xiàn)的增長(zhǎng)則更快，約2-3年翻一番。同時(shí)，伴隨著Internet的迅猛發(fā)展，網(wǎng)站和網(wǎng)頁(yè)數(shù)也在迅速增長(zhǎng)，大約每年翻一番。據(jù)估計(jì)，目前全世界網(wǎng)頁(yè)數(shù)已高達(dá)2000億，而Google宣稱其已索引250億網(wǎng)頁(yè)。在我國(guó)，中國(guó)互聯(lián)網(wǎng)絡(luò)信息中心從2001年起每年都對(duì)中文網(wǎng)頁(yè)總數(shù)作統(tǒng)計(jì)調(diào)查，統(tǒng)計(jì)結(jié)果顯示，中文網(wǎng)頁(yè)總數(shù)已由2

3、001年4月30日的159,460,056個(gè)發(fā)展到2005年12月31日的24億個(gè)，增長(zhǎng)之快可見(jiàn)一斑3,4。從這些統(tǒng)計(jì)數(shù)字可以看出，我們被淹沒(méi)在一個(gè)多么浩大的信息海洋里！然而信息的極大豐富并沒(méi)有提高人們對(duì)知識(shí)的吸收能力，面對(duì)如此浩瀚的信息，人們?cè)絹?lái)越感覺(jué)無(wú)法快速找到需要的知識(shí)。這就是所謂的“信息是豐富的，知識(shí)是貧乏的”。如何在這樣一個(gè)巨大的信息海洋中更加有效的發(fā)現(xiàn)和使用信息以及如何利用這個(gè)信息寶庫(kù)為人們提供更高質(zhì)量和智能化的信息服務(wù)，一直是當(dāng)前信息科學(xué)和技術(shù)領(lǐng)域面臨的一大挑戰(zhàn)。盡管用戶對(duì)圖像、音頻和視頻等信息資源的需求也在急劇增加，但文本仍然是最主要的非結(jié)構(gòu)化和半結(jié)構(gòu)化的信息資源。針對(duì)目前的出

4、版物和網(wǎng)絡(luò)信息大部分都以文本形式存在的狀況，自動(dòng)文本分類技術(shù)作為處理和組織大量文本數(shù)據(jù)的關(guān)鍵技術(shù)，受到了廣泛的關(guān)注。文本分類的定義文本分類的定義文本分類是指依據(jù)文本語(yǔ)義內(nèi)容將未知類別的文本歸類到已知類別體系中的過(guò)程。文本分類有多個(gè)英文名稱，如Text Categorization5、Text Classification6、Document Categorization7、Document Classification8以及Topic Spotting9等，現(xiàn)在比較常用的為T(mén)ext Categorization (TC)。文本分類的形式化定義如下，假設(shè)有一個(gè)文本集合D = d1,d|D|和一個(gè)

5、預(yù)先定義的類別集合C = c1,c|C|，二者之間的真實(shí)關(guān)系可由以下函數(shù)表示5： (1-1)于是，自動(dòng)文本分類問(wèn)題可以轉(zhuǎn)化為找到函數(shù)的近似表示： (1-2)使得盡量逼近未知的真實(shí)函數(shù)。此處的函數(shù)稱為文本分類器，力求真實(shí)反映文檔和類別的關(guān)系，以便盡可能對(duì)未知類別的文本進(jìn)行正確分類。文本分類根據(jù)分類算法的不同，可以分為兩類分類算法和多類分類算法。所謂兩類分類算法是指算法本質(zhì)上只能進(jìn)行兩類分類，即只能判別文檔屬于兩類中的某一類，如支持向量機(jī)算法；而多類分類算法是指算法可以同時(shí)對(duì)多個(gè)類別進(jìn)行操作，即同時(shí)判別文檔屬于多類中的某一類或某幾類，如KNN算法。兩類分類算法應(yīng)用于多類分類問(wèn)題時(shí)，通常需要將一個(gè)多

6、類分類問(wèn)題轉(zhuǎn)化為若干個(gè)兩類分類問(wèn)題來(lái)解決。具體轉(zhuǎn)化方法將在本文第二章詳細(xì)論述。另外，文本分類根據(jù)文檔所屬類別是否單一還可以分為單標(biāo)號(hào)分類(Single-label Text Categorization)問(wèn)題和多標(biāo)號(hào)分類(Multilabel Text Categorization)問(wèn)題。所謂單標(biāo)號(hào)分類指文檔的類別體系沒(méi)有重合，一篇文檔屬于且只屬于一個(gè)類別，而多標(biāo)號(hào)分類是指文檔的類別體系有重合，一篇文檔可以屬于多個(gè)不同的類別。自動(dòng)文本分類過(guò)程現(xiàn)代自動(dòng)文本分類技術(shù)涉及到人工智能、機(jī)器學(xué)習(xí)、模式識(shí)別和統(tǒng)計(jì)理論等多個(gè)學(xué)科，自動(dòng)文本分類的過(guò)程實(shí)際上也是機(jī)器學(xué)習(xí)和模式識(shí)別的過(guò)程。圖1-1為基本的分類過(guò)程

7、。圖1-1自動(dòng)文本分類模型如其他機(jī)器學(xué)習(xí)問(wèn)題一樣，文本分類也包括訓(xùn)練和測(cè)試兩個(gè)模塊。訓(xùn)練模塊由預(yù)處理、文本表示、特征選擇(Feature Selection)、分類器(Classifier)和性能評(píng)價(jià)五個(gè)部分組成：1. 預(yù)處理負(fù)責(zé)對(duì)訓(xùn)練集中的文本進(jìn)行去除停用詞、詞干化(Stemming)、分詞、統(tǒng)計(jì)等操作，并對(duì)文本進(jìn)行去噪處理。此處對(duì)中英文分別采取不同的處理，英文使用空格進(jìn)行分詞1,10，而中文則需要根據(jù)語(yǔ)義進(jìn)行分詞11-15或采用N-gram法進(jìn)行分詞16,17。2. 文本表示把文本表示成分類算法可以識(shí)別的形式。最常用的統(tǒng)計(jì)模型是由Salton等人提出的向量空間模型18，在此模型中，文檔dj

8、被表示成向量的形式，表示訓(xùn)練集中出現(xiàn)過(guò)的特征集合。3. 特征降維在文本表示階段使用的特征集合的數(shù)目通常非常巨大，并常含有大量對(duì)分類沒(méi)有貢獻(xiàn)甚至具有相反作用的噪聲特征。使用如此巨大的特征量會(huì)大大影響分類速度，因而需要通過(guò)特征降維減少特征數(shù)目，以提高訓(xùn)練和分類的速度與精度。特征選擇后需要根據(jù)新的特征子集對(duì)文本重新進(jìn)行表示。4. 分類器使用各種機(jī)器學(xué)習(xí)和模式識(shí)別算法對(duì)訓(xùn)練集進(jìn)行學(xué)習(xí)，確定算法的各參數(shù)值，生成分類器。5. 性能評(píng)價(jià)評(píng)價(jià)分類器對(duì)訓(xùn)練集的分類結(jié)果，如果性能達(dá)不到要求，返回特征選擇階段重新選擇特征。分類模塊由預(yù)處理、文本表示和分類器三個(gè)部分組成：1. 預(yù)處理功能作用和訓(xùn)練模塊中的預(yù)處理相同。

9、2. 文本表示與訓(xùn)練模塊的第一個(gè)文本表示有所不同，此處的文本表示使用的特征空間為經(jīng)過(guò)特征選擇后的特征空間。3. 分類器使用訓(xùn)練完成的分類器對(duì)文本分類，輸出最終分類結(jié)果。至此，完成了整個(gè)文本分類過(guò)程。除了預(yù)處理部分與語(yǔ)種密切相關(guān)外，其余部分均獨(dú)立于語(yǔ)種。文本分類是一個(gè)應(yīng)用性很強(qiáng)的技術(shù)，分類器的實(shí)現(xiàn)需要建立在一個(gè)高質(zhì)量的訓(xùn)練集基礎(chǔ)上，不同的應(yīng)用領(lǐng)域有截然不同的訓(xùn)練集。為了評(píng)測(cè)文本分類技術(shù)的優(yōu)劣，人們建立了一些標(biāo)準(zhǔn)語(yǔ)料庫(kù)，常用的英文語(yǔ)料庫(kù)有Reuters19、20_newsgroups20、OHSUMED21等。目前還沒(méi)有標(biāo)準(zhǔn)的中文語(yǔ)料庫(kù)，較多使用的有復(fù)旦大學(xué)語(yǔ)料庫(kù)22、北京大學(xué)天網(wǎng)語(yǔ)料庫(kù)23等。為

10、了避免產(chǎn)生過(guò)分適合的現(xiàn)象，語(yǔ)料庫(kù)通常包含兩個(gè)互不相交的訓(xùn)練集和測(cè)試集。所謂過(guò)分適合指的是用訓(xùn)練集來(lái)測(cè)試分類器，產(chǎn)生較好的分類性能，但是用別的文本進(jìn)行分類時(shí)發(fā)生分類性能急劇下降的情況。文本分類的發(fā)展歷史文本分類最早可以追溯到20世紀(jì)60年代5,24,25，在這之前主要是采用手工分類的方法。進(jìn)入60年代后，Maron發(fā)表了具有里程碑作用的論文“Automatic indexing: An experimental inquiry”，采用貝葉斯公式進(jìn)行文本分類，大大推進(jìn)了文本分類工作。在該文中，Maron還假設(shè)特征間是相互獨(dú)立的，這就是后來(lái)被廣泛采用的“貝葉斯假設(shè)”。在隨后的二十多年，主要是采用知識(shí)

11、工程(Knowledge Engineering, KE)的方法進(jìn)行文本分類26，它通過(guò)在專家知識(shí)基礎(chǔ)上手工建立一系列分類規(guī)則來(lái)構(gòu)建分類器。知識(shí)工程方法需要大量領(lǐng)域的專家和工程師參與，勢(shì)必耗費(fèi)很多人力物力，當(dāng)電子文檔急劇增長(zhǎng)時(shí)將無(wú)法滿足需求。這種方法最典型的應(yīng)用實(shí)例為由Carnegie Group開(kāi)發(fā)的CONSTRUE系統(tǒng)27，該系統(tǒng)用來(lái)對(duì)路透社的新聞稿件自動(dòng)分類。直到進(jìn)入20世紀(jì)90年代，隨著Internet的迅猛發(fā)展，為了能夠更好地處理大量的電子文檔，并且伴隨著人工智能、機(jī)器學(xué)習(xí)、模式識(shí)別、統(tǒng)計(jì)理論等學(xué)科的發(fā)展，基于知識(shí)工程的文本分類方法漸漸退出了歷史舞臺(tái)，文本分類技術(shù)進(jìn)入了更深入的自動(dòng)分

12、類時(shí)代。由于基于機(jī)器學(xué)習(xí)的自動(dòng)文本分類系統(tǒng)幾乎可以達(dá)到與人類專家相當(dāng)?shù)恼_度，但是卻不需要任何知識(shí)工程師或領(lǐng)域?qū)＜业母深A(yù)，節(jié)約了大量的人力，并且分類效率遠(yuǎn)遠(yuǎn)高于人類專家，因此機(jī)器學(xué)習(xí)方法在文本分類領(lǐng)域得到了深入的研究和廣泛的應(yīng)用，例如貝葉斯、最近鄰、神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)等。文本分類的應(yīng)用領(lǐng)域自動(dòng)文本分類是對(duì)文本信息基于內(nèi)容管理的基礎(chǔ)，文本分類技術(shù)產(chǎn)生的初衷就是為信息管理服務(wù)，伴隨著信息技術(shù)和內(nèi)容的多元化發(fā)展，文本分類也得到了越來(lái)越廣泛的應(yīng)用，甚至涉及到通過(guò)語(yǔ)音識(shí)別和文本分類合成的方式對(duì)語(yǔ)音進(jìn)行分類46以及通過(guò)分析文本標(biāo)簽對(duì)多媒體文本分類47等。下面簡(jiǎn)要介紹文本分類的幾種應(yīng)用，這些應(yīng)用之間的劃分

13、沒(méi)有非常明確的界限，有時(shí)某個(gè)應(yīng)用可能是另一個(gè)應(yīng)用的特例。文本組織與管理以科學(xué)論文為例，本文節(jié)曾經(jīng)提到，80年代僅科學(xué)論文一項(xiàng)每天就產(chǎn)生萬(wàn)萬(wàn)篇，科學(xué)文獻(xiàn)平均年增長(zhǎng)率為13，有些學(xué)科每10年翻一番，某些尖端學(xué)科2-3年翻一番。從這些統(tǒng)計(jì)數(shù)據(jù)可以得出，到目前為止，科技論文每天約產(chǎn)生4萬(wàn)-5萬(wàn)篇，如果進(jìn)行人工分類，那么如此龐大的數(shù)據(jù)量必將使得各領(lǐng)域的科學(xué)家付出巨大的勞動(dòng)。另外，科技論文對(duì)實(shí)時(shí)性的要求也很高，研究人員需要了解到本學(xué)科最新的研究現(xiàn)狀，這就要求論文庫(kù)能夠及時(shí)動(dòng)態(tài)更新。所有這些情況都使得人工組織文本越來(lái)越成為不可能，此時(shí)就需要使用自動(dòng)文本分類技術(shù)。文本分類使得有序地按類別存儲(chǔ)海量文件并及時(shí)作出

14、更新成為可能。另外，Internet已經(jīng)成為人們生活中必不可少的一部分，人們已經(jīng)習(xí)慣了坐在電腦前了解自己感興趣的知識(shí)。各大門(mén)戶網(wǎng)站如新浪、雅虎、搜狐等都建有各自的層次化分類體系，對(duì)網(wǎng)頁(yè)根據(jù)其內(nèi)容進(jìn)行分類，讀者只需按類別層層找下去就可以瀏覽到各種信息。目前各網(wǎng)站的分類都需要人工干預(yù)，如果采用自動(dòng)文本分類技術(shù)，無(wú)疑將大大改善分類效率。文本分類在數(shù)字化圖書(shū)館48、專利分類49、新聞文章自動(dòng)歸檔和會(huì)議文章自動(dòng)分組等方面都有成功應(yīng)用。信息檢索毫無(wú)疑問(wèn)，信息檢索(Information Retrieval)工具可以根據(jù)查詢?cè)~返回相關(guān)信息，有效幫助了人們查找相關(guān)知識(shí)，如Goole、Baidu、Yahoo、E

15、xcite等搜索引擎。但是，所有的搜索引擎都存在著相同的一個(gè)問(wèn)題，返回結(jié)果并沒(méi)有如用戶期望的那樣排列，并且包含了大量用戶不感興趣的網(wǎng)頁(yè)，用戶必須通過(guò)閱讀這些網(wǎng)頁(yè)濾除無(wú)用信息，這就降低了查詢效率。在信息檢索領(lǐng)域引入文本分類技術(shù)，由用戶選擇查詢類別，或者由搜索引擎給出分類存放的搜索結(jié)果，都可以提高查詢效率，方便用戶使用。另外，針對(duì)信息資源庫(kù)中各個(gè)不同類別，還可以建立各類別的專用搜索引擎，直接供僅對(duì)某個(gè)專題感興趣的人使用。冗余文檔過(guò)濾信息檢索不僅包含了大部分用戶不感興趣的類別，還包含了大量相同或相似的網(wǎng)頁(yè)，在搜索結(jié)果較少時(shí)更是如此。這些相同或相似的網(wǎng)頁(yè)稱為冗余文檔，相同網(wǎng)頁(yè)是指除了鏈接地址不同，內(nèi)容

16、完全相同的網(wǎng)頁(yè)；相似文檔是指內(nèi)容只有少許不同的網(wǎng)頁(yè)。雖然各大搜索引擎都號(hào)稱對(duì)相同和相似網(wǎng)頁(yè)進(jìn)行了過(guò)濾，但在搜索結(jié)果中包含大量相同或相似網(wǎng)頁(yè)的情況還是經(jīng)常出現(xiàn)。利用文本分類技術(shù)對(duì)網(wǎng)頁(yè)計(jì)算相似度，超過(guò)指定閾值的網(wǎng)頁(yè)即可認(rèn)為是冗余文檔，在數(shù)據(jù)庫(kù)中只保存一份。Narayanan Shivakumar等對(duì)24,000,000個(gè)網(wǎng)頁(yè)進(jìn)行統(tǒng)計(jì)分析，發(fā)現(xiàn)有18的網(wǎng)頁(yè)有一個(gè)重復(fù)網(wǎng)頁(yè)，5的網(wǎng)頁(yè)有10到100個(gè)重復(fù)網(wǎng)頁(yè)，經(jīng)過(guò)冗余檢測(cè)后，可以把存儲(chǔ)空間壓縮2250。為了提高檢測(cè)效率，計(jì)算網(wǎng)頁(yè)相似度之前，可以先對(duì)抓取到的網(wǎng)頁(yè)進(jìn)行預(yù)分類，然后再根據(jù)網(wǎng)頁(yè)類別僅僅在該類別進(jìn)行檢測(cè)，這樣不僅可以大大減少檢測(cè)時(shí)間和計(jì)算復(fù)雜度。信

17、息過(guò)濾信息過(guò)濾(Information Filtering)是指根據(jù)用戶對(duì)信息的需求，對(duì)產(chǎn)生或到來(lái)的信息流進(jìn)行動(dòng)態(tài)地分類，保留對(duì)用戶有用的信息，屏蔽無(wú)用信息。信息過(guò)濾與信息檢索如同一面硬幣的兩面51：信息檢索關(guān)心的是如何從信息源中找到符合用戶需求的信息，可以形容為“人找信息”，用戶為主動(dòng)方，稱之為“拉”(pull)；信息過(guò)濾關(guān)心的是過(guò)濾系統(tǒng)如何把信息發(fā)送給感興趣的用戶，可以形容為“信息找人”，信息發(fā)布方為主動(dòng)方，稱之為“推”(push)。信息過(guò)濾的一個(gè)典型應(yīng)用如新聞推送服務(wù)，信息發(fā)布方為某個(gè)新聞社，用戶為某種報(bào)紙5,52。在這個(gè)例子中，過(guò)濾系統(tǒng)應(yīng)該屏蔽掉所有用戶不感興趣的文檔，例如對(duì)于體育報(bào)紙

18、，應(yīng)該屏蔽所有與運(yùn)動(dòng)無(wú)關(guān)的文檔。因此信息過(guò)濾可以看作是一個(gè)單標(biāo)號(hào)分類問(wèn)題，把所有到來(lái)的文本分為兩個(gè)互不相交的類別：相關(guān)文檔和無(wú)關(guān)文檔。另外，過(guò)濾系統(tǒng)還可以進(jìn)一步對(duì)相關(guān)文本按照各個(gè)主題進(jìn)行分類，方便用戶閱讀。在上一個(gè)例子中，與運(yùn)動(dòng)有關(guān)的文本還可以進(jìn)一步按照運(yùn)動(dòng)類別分類。同樣，垃圾郵件過(guò)濾系統(tǒng)也可以丟棄垃圾郵件53，并對(duì)非垃圾郵件根據(jù)用戶興趣進(jìn)行分類。過(guò)濾系統(tǒng)既可以安裝在信息的發(fā)送端，此時(shí)系統(tǒng)基于信息內(nèi)容僅發(fā)送給對(duì)該信息感興趣的用戶；也可以安裝在信息的接收端，此時(shí)系統(tǒng)負(fù)責(zé)阻斷用戶不感興趣的信息。對(duì)于前一種情況，系統(tǒng)需要為每個(gè)用戶建立一個(gè)檔案54，而在后一種情況下，系統(tǒng)只需建立一個(gè)用戶檔案。文檔過(guò)濾

19、(Document Filtering)可以追溯到上世紀(jì)60年代有選擇的信息分發(fā)技術(shù)(selective dissemination of information)，當(dāng)今數(shù)字信息的爆炸更加促進(jìn)了這類技術(shù)的發(fā)展，如基于內(nèi)容的垃圾郵件過(guò)濾、新聞組訂閱等5。詞義辨析詞義辨析(Word Sense Disambiguation)是指根據(jù)多義詞所處上下文環(huán)境判斷該詞此時(shí)含義的活動(dòng)5。例如，英文英文單詞“bank”至少有兩個(gè)不同含義，在“the Bank of England”中為“銀行”，在“the bank of river Thames”中為“河岸”，在“I borrowed some money

20、from the bank”中“bank”的含義就需要借助詞義辨析來(lái)確定。把單詞所處上下文看作文本，把單詞的各種不同含義看作不同類別，那么詞義辨析問(wèn)題就可以轉(zhuǎn)化為一個(gè)文本分類問(wèn)題。顯然，詞義辨析屬于單標(biāo)號(hào)分類任務(wù)。詞義辨析只是解決自然語(yǔ)言歧義性時(shí)常見(jiàn)難題中的一個(gè)例子，也是計(jì)算語(yǔ)言學(xué)中最重要的一個(gè)難題。還有很多機(jī)器翻譯中的其他問(wèn)題，比如基于上下文的拼寫(xiě)校對(duì)(Context-sensitive spelling correction)57、介詞短語(yǔ)連接(Prepositional Phrase Attachment)58、詞性標(biāo)注(Part-of-speech Tagging)59,60等，也都可

21、以通過(guò)借助文本文類技術(shù)來(lái)解決。26第二章 文本分類的性能評(píng)估引言由于自動(dòng)文本分類技術(shù)在文本處理領(lǐng)域具有關(guān)鍵性作用和廣泛的應(yīng)用前景，因此得到了眾多學(xué)者的高度重視。隨著人工智能、機(jī)器學(xué)習(xí)、模式識(shí)別和統(tǒng)計(jì)理論等領(lǐng)域技術(shù)的快速發(fā)展，涌現(xiàn)出了越來(lái)越多的文本分類方法。但是，這些分類方法的性能如何，以及如何客觀評(píng)估和比較這些分類方法，就成為了選擇分類方法時(shí)無(wú)法忽視的問(wèn)題。分類器的評(píng)估是一個(gè)非常復(fù)雜的問(wèn)題，目前還沒(méi)有一個(gè)可以從理論上對(duì)單個(gè)分類器進(jìn)行評(píng)估或?qū)Σ煌诸惼鬟M(jìn)行比較的方法。由于難以從理論上對(duì)分類器進(jìn)行客觀公正的評(píng)估，文本分類領(lǐng)域沿用了信息檢索領(lǐng)域的評(píng)估辦法，從仿真的實(shí)驗(yàn)結(jié)果來(lái)評(píng)估分類器的性能。已有很多

22、學(xué)者使用實(shí)驗(yàn)的方法對(duì)分類器進(jìn)行了比較，并且研究者在說(shuō)明某種分類算法的性能時(shí)也是用數(shù)據(jù)來(lái)表示。分類器的性能評(píng)估有兩個(gè)重要的作用，客觀比較不同分類器僅僅是其中的一個(gè)方面，另一個(gè)重要作用是在訓(xùn)練過(guò)程中指導(dǎo)分類器的生成。如圖中所示那樣，分類器評(píng)估是訓(xùn)練過(guò)程中必不可少的一個(gè)模塊，分類器的構(gòu)建需要根據(jù)評(píng)估結(jié)果調(diào)整各參數(shù)，以使分類器性能達(dá)到最優(yōu)。如同任何一個(gè)其他領(lǐng)域的科學(xué)實(shí)驗(yàn)，文本分類的實(shí)驗(yàn)結(jié)果也受很多客觀因素的影響，比如：實(shí)驗(yàn)數(shù)據(jù)集的選定、文本的表示模型、特征選擇的方法、分類算法的確定、各參數(shù)的選定、評(píng)估指標(biāo)的確定以及實(shí)驗(yàn)數(shù)據(jù)的分析與處理等。顯然，不同分類器只有在諸多客觀因素均一致的情形下才具有可比性。許

23、多學(xué)者基于Reuters、20_Newgroups、OHSUMED等標(biāo)準(zhǔn)數(shù)據(jù)集對(duì)一些分類算法進(jìn)行了比較，結(jié)果就具有較高的可信度29,81。另外，由于分類器對(duì)數(shù)據(jù)集的嚴(yán)重依賴性，依靠仿真實(shí)驗(yàn)得出的任何一種評(píng)估結(jié)果都只能作為一定的參考，在不同數(shù)據(jù)集上同一種分類方法可能會(huì)表現(xiàn)出截然不同的性能。由此可見(jiàn)，文本分類的性能評(píng)估是文本分類領(lǐng)域的一個(gè)重要課題，針對(duì)不同的目的，評(píng)估側(cè)重點(diǎn)也應(yīng)有所不同。文本分類器的性能評(píng)估指標(biāo)從實(shí)驗(yàn)方面來(lái)看，文本分類器的性能主要表現(xiàn)在兩個(gè)方面：效率和效果。所謂效率指的是分類器訓(xùn)練和分類的時(shí)間；所謂效果指的是分類器做出正確決定的能力。具體到評(píng)估指標(biāo)上，效率的評(píng)估指標(biāo)是時(shí)間，即分類器

24、訓(xùn)練的時(shí)間及單篇文本分類的時(shí)間；而效果的評(píng)估指標(biāo)并不唯一，有多種類型，下面將重點(diǎn)進(jìn)行討論。在目前的文本分類應(yīng)用中，主要關(guān)心的是分類效果的度量，所以本文也將主要討論分類效果的評(píng)估，本文其余部分若未特別指出，文本分類性能評(píng)估均指分類效果的評(píng)估。文本分類有多個(gè)性能評(píng)估指標(biāo)，常用的有查全率(Recall, r)、查準(zhǔn)率(Precision, p)、正確率(Accuracy, acc)、錯(cuò)誤率(Error, err)以及查全率與查準(zhǔn)率的綜合評(píng)價(jià)值、11-點(diǎn)平均(Eleven-point average, 11-Ave)和平衡點(diǎn)(Breakeven point, BEP)等。下面針對(duì)單標(biāo)號(hào)分類器給出這些指

25、標(biāo)的定義及計(jì)算方法。假設(shè)一個(gè)單標(biāo)號(hào)文本分類器、測(cè)試文本集合和預(yù)先定義的類別集合，D中每篇文檔只屬于一個(gè)類別，C中各類別兩兩之間互不相交。分別由專家和分類器來(lái)對(duì)全部測(cè)試文本判斷類別，那么可建立如下的鄰接表：表2-1 多類分類器列聯(lián)表專家判別分類器判別在表2-1中，的含義如下： (2-1)其中，表示原本屬于類別并被分類器正確判斷為的文檔數(shù)目，表示原本屬于類別但被分類器錯(cuò)誤判斷為的文檔數(shù)目。根據(jù)表2-1，各指標(biāo)定義及計(jì)算方法如下：1.查全率(Recall, r)與查準(zhǔn)率(Precision, p)查全率定義為正確判別為該類的測(cè)試樣本占該類總測(cè)試樣本的比例，查準(zhǔn)率定義為正確判別為該類的測(cè)試樣本占判別為

26、該類的測(cè)試樣本的比例，那么類別的查全率和查準(zhǔn)率的計(jì)算公式如下5： (2-2) (2-3)查全率與查準(zhǔn)率來(lái)源于信息檢索領(lǐng)域，是最為傳統(tǒng)、也是使用最多的兩個(gè)指標(biāo)。查全率和查準(zhǔn)率從不同方面反映了分類系統(tǒng)的性能，查全率反映了分類的完備程度，即應(yīng)該正確分類的文本中有多少被正確分類；查準(zhǔn)率反映了分類的準(zhǔn)確程度，即分類結(jié)果中有多少是正確的。二者通常被一起使用，作為一對(duì)指標(biāo)從不同側(cè)面共同描述分類器性能。2.把查全率和查準(zhǔn)率分開(kāi)考慮沒(méi)有任何意義，例如，100篇文檔中有10篇屬于類別，假設(shè)訓(xùn)練了一個(gè)類別的“接受分類器”，即所有文本均判為，那么對(duì)于來(lái)講，查全率達(dá)到100，但查準(zhǔn)率只有10。于是，Rijsbergen

27、提出了把二者綜合考慮的指標(biāo)，類別的定義如下108： (2-4)其中，是可調(diào)節(jié)參數(shù)，反映了和的相對(duì)重要程度。當(dāng)時(shí)，為查準(zhǔn)率；當(dāng)時(shí)，為查全率。越小，越強(qiáng)調(diào)的作用；越大，越強(qiáng)調(diào)的作用。最為常用的是值，此時(shí)，認(rèn)為與具有同等重要程度，計(jì)算公式如下： (2-5)點(diǎn)平均(11-point average, 11-Ave)11-點(diǎn)平均也是一個(gè)常用的分類器綜合評(píng)價(jià)指標(biāo)31,61，來(lái)源于信息檢索領(lǐng)域。11-點(diǎn)平均定義為調(diào)整分類器參數(shù)，使得查全率分別為0, 10, , 90, 100時(shí)相應(yīng)的查準(zhǔn)率的算術(shù)平均值。4.平衡點(diǎn)(Breakeven point, BEP)Break-even點(diǎn)是另外一個(gè)綜合評(píng)價(jià)指標(biāo)39,6

28、2，指的是分類器查全率與查準(zhǔn)率相等時(shí)的值，這是分類器的一種特殊情況，此時(shí)。有時(shí)通過(guò)實(shí)驗(yàn)可能得不到和相等的值，這時(shí)就取和最接近的值的平均值作為，稱為插值。5.宏平均(Macro-average)與微平均(Micro-average)前面所述幾個(gè)指標(biāo)都是針對(duì)單個(gè)類別的局部性能進(jìn)行評(píng)估的，對(duì)于一個(gè)多類分類器來(lái)講，關(guān)心的是整體性能。宏平均和微平均是計(jì)算全局性能的兩種方法。宏平均是指先計(jì)算各類別的性能指標(biāo)，然后再求算術(shù)平均值，宏平均查全率()、宏平均查準(zhǔn)率()及宏平均()的定義如下： (2-6) (2-7) (2-8)微平均是指計(jì)算各個(gè)樣本的分類性能，然后求算術(shù)平均值。微平均查全率()、微平均查準(zhǔn)率()

29、及微平均()的定義如下： (2-9) (2-10) (2-11)從微平均各指標(biāo)的定義可以看出，如果在分類器中未引入拒識(shí)策略，則有，此時(shí)。宏平均和微平均兩種方式的結(jié)果可能相差很大，尤其是對(duì)于不均衡的測(cè)試集更是如此。宏平均是按類別求平均，微平均是按樣本求平均，故宏平均的結(jié)果受小類別影響較大，微平均的結(jié)果受大類別影響較大。6.正確率(Accuracy, acc)與錯(cuò)誤率(Error, err)正確率與錯(cuò)誤率也是兩個(gè)衡量分類器整體性能的指標(biāo)。正確率定義為分類器正確分類的樣本占所有測(cè)試樣本的比例，錯(cuò)誤率定義為分類器錯(cuò)誤分類的樣本占所有測(cè)試樣本的比例，計(jì)算公式如下： (2-12) (2-13)正確率與錯(cuò)誤

30、率來(lái)源于機(jī)器學(xué)習(xí)領(lǐng)域，由公式(2-9)可以看出，正確率與微平均查全率的值完全相等，只是物理意義不同罷了。第三章 文本表示引言文本是一個(gè)由眾多字符構(gòu)成的字符串，人類在閱讀文章后，可以根據(jù)自身的理解能力產(chǎn)生對(duì)文章的模糊認(rèn)識(shí)，并對(duì)其進(jìn)行分類。但計(jì)算機(jī)并不能理解文章的內(nèi)容，從根本上說(shuō)，它只認(rèn)識(shí)0和1，所以必須把文本轉(zhuǎn)換為計(jì)算機(jī)或者說(shuō)分類算法可以識(shí)別的形式。文本表示方法的選擇取決于文本中的語(yǔ)義單元以及把這些單元結(jié)合在一起的自然語(yǔ)言處理規(guī)則。對(duì)文本中語(yǔ)義單元的研究屬于詞匯語(yǔ)義學(xué)的范疇，對(duì)各單元組合規(guī)則的研究屬于組合語(yǔ)義學(xué)的范疇。文本表示首先根據(jù)詞匯語(yǔ)義學(xué)及組合語(yǔ)義學(xué)的相關(guān)知識(shí)對(duì)文本dj進(jìn)行分割，把文本轉(zhuǎn)化

31、為由若干個(gè)語(yǔ)義單元組成的空間形式，這就是在文本分類及信息檢索領(lǐng)域廣泛應(yīng)用的向量空間模型(Vector Space Model，VSM)，這些語(yǔ)義單元tk稱為特征(term或feature)。確定文本所用特征后，再計(jì)算各特征在文本中的權(quán)重(weight)，文本dj被表示為特征向量的形式，其中權(quán)重值wkj表示特征tk在文本dj中的重要程度，T表示特征空間的特征集。向量空間模型是由Salton提出的18，最早成功應(yīng)用于信息檢索領(lǐng)域，后來(lái)在文本分類領(lǐng)域也得到了成功應(yīng)用。Salton的向量空間模型基于這樣一個(gè)假設(shè)：文本所屬類別僅與特定單詞或詞組在該文本中出現(xiàn)的頻數(shù)有關(guān)，而與這些單詞或詞組在該文本中出現(xiàn)的

32、位置或順序無(wú)關(guān)。針對(duì)如何盡可能準(zhǔn)確地表示文本，眾多學(xué)者進(jìn)行了廣泛研究，主要集中在特征空間的選取和特征權(quán)重的計(jì)算方面。雖然使用向量空間模型表示文本將丟失大量文本信息，但這種文本的形式化處理使得大量機(jī)器學(xué)習(xí)算法在文本分類領(lǐng)域得到成功應(yīng)用，大大促進(jìn)了自動(dòng)文本分類的發(fā)展。隨著文本分類技術(shù)的不斷進(jìn)步，向量空間模型也處于不斷發(fā)展變化中。我們稱Salton最初提出的向量空間模型為狹義向量空間模型，在這基礎(chǔ)上發(fā)展起來(lái)的所有以向量形式表示文本的模型稱為廣義向量空間模型。事實(shí)上，目前使用的文本表示法基本上都是以向量形式表示的，各方法之間的差異主要表現(xiàn)在特征粒度及權(quán)重計(jì)算方法的不同。本文其余部分若不特別指出，向量空

33、間模型均指廣義向量空間模型。向量空間模型向量空間模型中，特征是文本表示的最小單位。劃分文本的特征可以是詞（包括字）、詞組、n-gram和概念等，根據(jù)特征粒度的不同，一篇文本可以有多種表示方式。下面介紹各種文本特征及特征權(quán)重計(jì)算方法。特征詞詞是自然語(yǔ)言理解的最小語(yǔ)義單位。不同的語(yǔ)種獲取詞的方式也大不相同。對(duì)英文等拼音文字而言，各個(gè)詞之間用空格進(jìn)行分隔，計(jì)算機(jī)處理時(shí)可以用空格作為切分標(biāo)志，來(lái)提取文本的特征。但是對(duì)于中文等亞洲文字來(lái)說(shuō)，表達(dá)方式以字為最小單位，在自然理解當(dāng)中又是以詞作為有意義的最小單位，詞與詞之間沒(méi)有自然分割標(biāo)志，這樣就需要通過(guò)分詞來(lái)取得文本的詞特征。無(wú)論何種語(yǔ)種，都會(huì)有一些對(duì)分類沒(méi)

34、有任何貢獻(xiàn)的代詞、介詞和連詞等，這些詞稱為停用詞(stop words)。中英文對(duì)停用詞的處理也不同。英文通常根據(jù)分類任務(wù)構(gòu)建停用詞表，然后在取詞特征時(shí)根據(jù)該表去除停用詞，表3-1是本文實(shí)驗(yàn)中采用的停用詞表，包含319個(gè)停用詞。而中文通常通過(guò)分詞時(shí)建立的詞典去除停用詞，即詞典初始建立時(shí)就不包含停用詞。表3-1 停用詞表aaboutaboveacrossafterafterwardsagainagainstallalmostalonealongalreadyalsobutbycallcancannotcantcocomputerconcouldcouldntcrydedescribefurthe

35、rgetgivegohadhashasnthavehehenceherherehereafterherebymostlymovemuchmustmymyselfnamenamelyneitherneverneverthelessnextninenoseveralsheshouldshowsidesincesinceresixsixtysosomesomehowsomeonesomethingtowardstwelvetwentytwounderuntilupuponuseusedveryviawaswealthoughalwaysamamongamongstamoungstamountanan

36、danotheranyanyhowdetaildodonedowndueduringeachegeighteitherelevenelsehereinhereuponhersherselfhimhimselfhishowhoweverhundrediienobodynonenoonenornotnothingnownowhereofoffoftenonsometimesometimessomewherestillsuchsystemtaketenthanthatthetheirwellwerewhatwhateverwhenwhencewheneverwherewhereafterwherea

37、swherebywherein表3-1 （續(xù)）anyoneanythinganywayanywherearearoundasatbackbebecamebecausebecomebecomesbecomingbeenbeforebeforehandbehindbeingbelowbesidebesidesbetweenbeyondbillbothbottomelsewhereemptyenoughetcevenevereveryeveryoneeverythingeverywhereexceptfewfifteenfifyfillfindfirefirstfiveforformerformer

38、lyfortyfoundfourfromfrontfullifinincindeedinterestintoisititsitselfkeeplastlatterlatterlyleastlessltdmademanymaymemeanwhilemightmillminemoremoreovermostonceoneonlyontoorotherothersotherwiseouroursourselvesoutoverownpartperperhapspleaseputratherresameseeseemseemedseemingseemsseriousthemthemselvesthen

39、thencetherethereaftertherebythereforethereinthereuponthesetheythickthinthirdthisthosethoughthreethroughthroughoutthruthustotogethertootoptowardwhereuponwhereverwhetherwhichwhilewhitherwhowhoeverwholewhomwhosewhywillwithwithinwithoutwouldyetyouyouryoursyourselfyourselves另外，英文中存在各種時(shí)態(tài)、語(yǔ)態(tài)及名詞的單復(fù)數(shù)，故英文還可對(duì)文

40、本中各單詞進(jìn)行取詞根(stemming)處理，就是依據(jù)一定的語(yǔ)法規(guī)則剝離各個(gè)單詞的后綴，得到表明單詞基本含義的詞根。例如，answer, answered, answers的詞根都為answer,則統(tǒng)一用answer來(lái)表示。目前常用的是Porter的取詞根算法115。但也有研究說(shuō)取詞根會(huì)降低分類性能116，但取詞根還是得到了很廣泛的應(yīng)用，因?yàn)樵摲椒梢杂行Ы档吞卣骶S數(shù)。雖然以詞作為特征的詞表示法丟失了大量的文本信息，但依然能夠在文本分類中取得很好的效果，因而得到了廣泛使用。詞組以詞組作為特征的表示法稱為詞組表示法，該方法與詞表示法非常相似，唯一不同的是特征粒度變大了。顯然，用詞組作為特征可以更

41、多地包含文本信息，但分類結(jié)果卻不盡人意10,117。主要原因在于詞組表示法雖然提高了特征的語(yǔ)義質(zhì)量，但卻降低了特征的統(tǒng)計(jì)質(zhì)量。和詞特征相比，詞組特征具有較多的特征、較多的同義或近義特征、較低的一致性以及較低的文檔頻率10。統(tǒng)計(jì)質(zhì)量的降低只能使得特征向量更加稀疏，從而對(duì)分類性能產(chǎn)生影響。字符串與詞表示法和詞組表示法需要依賴于語(yǔ)種不同，字符串(n-gram)表示法118是完全獨(dú)立于語(yǔ)種的一種表示法。n-gram表示法把文本看作一個(gè)大字符串，由若干個(gè)以n個(gè)字符組成的字符串作為特征單位。在字符串表示法中，不再考慮文本的語(yǔ)義單位，文本只是一個(gè)由各種字符組成的字符串，由計(jì)算機(jī)根據(jù)字符長(zhǎng)度n對(duì)文本進(jìn)行分割。

42、例如，“text categorization”被14-gram分解為包含特征“text categoriz”、“ext categoriza”、“xt categorizat”、“t categorizati”、“categorizatio”和“categorization”；“華南理工大學(xué)”被2-gram分解為包含特征“華南”、“南理”、“理工”、“工大”和“大學(xué)”。n-gram表示法可以避免分詞的工作，因此尤其適合中文等亞洲語(yǔ)言。但是n-gram的缺點(diǎn)也非常明顯，存在數(shù)據(jù)噪聲大、特征復(fù)雜、計(jì)算量大和易于過(guò)學(xué)習(xí)等問(wèn)題。概念在自然語(yǔ)言中，一義多詞的現(xiàn)象非常普遍，比如“計(jì)算機(jī)”“電腦”“微機(jī)”

43、表示的都是一個(gè)概念。概念具有很高的抽象性，一個(gè)概念可以對(duì)應(yīng)一個(gè)詞，也可以對(duì)應(yīng)若干個(gè)詞。從自然語(yǔ)言理解的角度看，采用概念作為特征是最高級(jí)的表示。采用概念作為特征有很多好處。首先，一個(gè)概念可能對(duì)應(yīng)若干個(gè)不同的詞，這樣將大大降低特征空間的維數(shù)，提高分類速度；其次，同義詞的聚類使得該概念的權(quán)重集中，避免了權(quán)重分散帶來(lái)的對(duì)該特征的削弱，從而提高分類的精度。用概念表示文本需要有一個(gè)專門(mén)的語(yǔ)義詞典，這就需要語(yǔ)言專家和各領(lǐng)域?qū)＜业膮⑴c，無(wú)疑將耗費(fèi)大量的人力和物力。所以，用概念表示文本的想法雖然非常好，但進(jìn)展并不十分理想119。特征向量特征空間中不同特征項(xiàng)對(duì)文檔的重要程度和對(duì)分類的貢獻(xiàn)是不同的，因此文本分類系統(tǒng)

44、在對(duì)文本進(jìn)行形式化處理的時(shí)候，需要對(duì)文本的每個(gè)特征項(xiàng)賦權(quán)，以形成特定文本的特征向量，權(quán)重越大的特征認(rèn)為對(duì)文本越重要。由于各研究者對(duì)特征重要性認(rèn)識(shí)的不同，涌現(xiàn)出了許多特征權(quán)重計(jì)算方法，下面介紹幾種常用方法，這些方法都基于Zobel和Moffat提出的假設(shè)64,120：（1）IDF(Inverted Document Frequency)假設(shè)：稀有特征的重要程度不低于常見(jiàn)特征；（2）TF(Term Frequency)假設(shè)：一篇文檔中出現(xiàn)多次的特征的重要程度不低于只出現(xiàn)一次的特征；（3）規(guī)范化(Normalization)假設(shè)：同樣的特征匹配數(shù)，長(zhǎng)文檔的重要程度不高于短文檔。從把文本轉(zhuǎn)換為若干個(gè)特

45、征的集合到生成文本的特征向量，通常需要經(jīng)過(guò)三個(gè)步驟：生成索引向量；對(duì)索引向量賦權(quán)；規(guī)范化。文本索引設(shè)訓(xùn)練集有N篇文檔，特征空間為，對(duì)文本dj進(jìn)行索引后得到索引向量，其中，fkj表示特征tk在文本dj中的索引值。索引值的計(jì)算通常有以下幾種方式。布爾索引是最簡(jiǎn)單的一種索引方式，fkj值的取0或1，取值方式如下： (3-1)詞頻索引采用特征tk在文本dj中出現(xiàn)的次數(shù)TFkj作為索引值： (3-2)對(duì)數(shù)索引也利用了特征tk在文本dj中出現(xiàn)的次數(shù)TFkj，計(jì)算公式如下： (3-3)可以看出，無(wú)論采用何種方式計(jì)算的索引向量均為非負(fù)向量。雖然索引向量真實(shí)反映了文本中各特征項(xiàng)出現(xiàn)的情況，但由于各特征對(duì)分類的貢

46、獻(xiàn)不同，需要在索引向量中進(jìn)一步加入類別信息，以便準(zhǔn)確分類。特征賦權(quán)特征賦權(quán)的方式有很多種，可以分為“均權(quán)”與“非均權(quán)”兩類。顧名思義，所謂“均權(quán)”，就是研究者認(rèn)為特征在整個(gè)訓(xùn)練集中的統(tǒng)計(jì)信息對(duì)分類不會(huì)產(chǎn)生實(shí)質(zhì)性的影響，所以給索引向量中的每個(gè)特征賦以相同的權(quán)重，也就是使用原索引向量，既不突出也不抑制任何特征。而“非均權(quán)”認(rèn)為特征分為主要特征和次要特征，經(jīng)過(guò)賦權(quán)處理可以放大主要特征的作用，縮小次要特征的作用。目前的研究普遍認(rèn)為不同特征在分類中的貢獻(xiàn)是不同的，一般采用“非均權(quán)”對(duì)特征加權(quán)。其中最有代表性的是“IDF(Inverted Document Frequency)權(quán)”。IDF權(quán)認(rèn)為訓(xùn)練集中包

47、含特征tk的文檔數(shù)目越多，則該特征對(duì)分類的貢獻(xiàn)越小，這樣的特征需要受到抑制；相反，訓(xùn)練集中包含特征tk的文檔數(shù)目越少，則該特征對(duì)分類的貢獻(xiàn)越大，這樣的特征需要被放大。設(shè)特征加權(quán)向量為，訓(xùn)練集中出現(xiàn)過(guò)特征tk的文檔數(shù)為DFk，那么特征tk的加權(quán)值gk由下式計(jì)算： (3-4)至此，文檔dj由加權(quán)索引向量表示，等于索引向量與特征加權(quán)向量g的內(nèi)積，由公式(3-5)計(jì)算。 (3-5)規(guī)范化為了消除文檔長(zhǎng)度不同對(duì)加權(quán)索引向量h的影響，需要對(duì)h進(jìn)行規(guī)范化處理，使得各特征權(quán)重落在區(qū)間0,1內(nèi)，最終生成文本dj的特征向量。特征tk的權(quán)重wkj的計(jì)算公式如下： (3-6)相似度計(jì)算文本表示為向量后，文本之間的距離

48、或相似度可以通過(guò)空間中這兩個(gè)向量的幾何關(guān)系來(lái)度量。設(shè)有兩個(gè)特征向量和。如果特征向量是布爾向量，那么相似度函數(shù)通常采用漢明距離，定義如下： (3-7)如果特征向量非布爾向量，則相似度函數(shù)通常采用夾角余弦函數(shù)，定義如下： (3-8)經(jīng)典特征權(quán)重在文本分類領(lǐng)域，通常使用Salton等人提出的TFIDF(Term Frequency and Inverted Document Frequency)公式計(jì)算特征項(xiàng)權(quán)重，特征tk在文檔dj中的TFIDF計(jì)算公式如(3-9)所示5： (3-9)其中，TFkj表示特征tk在文檔dj中出現(xiàn)的次數(shù)，DFk表示在整個(gè)訓(xùn)練集中包含特征tk的文檔數(shù)，N表示整個(gè)訓(xùn)練集中包

49、含的文檔數(shù)。該公式的直觀解釋為：特征tk在文檔中出現(xiàn)的次數(shù)越高，在整個(gè)訓(xùn)練集中包含該特征項(xiàng)的文檔數(shù)目越少，則該特征權(quán)重越大；反之，特征tk在文檔中出現(xiàn)的次數(shù)越少，在整個(gè)訓(xùn)練集中包含該特征項(xiàng)的文檔數(shù)目越多，則該特征權(quán)重越小。對(duì)的規(guī)范化處理如下式所示： (3-10)其中，|T|表示特征向量的維數(shù)。第四章 文本分類算法引言文本分類算法作為自動(dòng)文本分類技術(shù)的核心，一直處于重點(diǎn)研究與不斷發(fā)展當(dāng)中。多年來(lái)的研究積累了很多經(jīng)典的分類算法，如Naive Bayes32,33、k近鄰30、決策樹(shù)34等，也涌現(xiàn)出了不少新算法和改進(jìn)的分類算法35-45。這些研究基本都致力于改進(jìn)訓(xùn)練和分類的速度和精度。目前文本分類的

50、算法有很多種，包括k近鄰法、樸素貝葉斯算法、決策樹(shù)算法、決策規(guī)則算法、回歸模型、在線算法、Rocchio算法、神經(jīng)網(wǎng)絡(luò)算法、支持向量機(jī)算法、最小二乘擬合與分類器組方法等。文本分類算法基本來(lái)源于機(jī)器學(xué)習(xí)與信息論領(lǐng)域，總體來(lái)說(shuō)分類算法大致可分為兩大類：基于統(tǒng)計(jì)的方法和基于規(guī)則的方法。樸素貝葉斯算法是經(jīng)典的基于統(tǒng)計(jì)的算法，決策樹(shù)則是基于規(guī)則的方法中的典型。為分類系統(tǒng)選擇分類算法時(shí)需要考慮以下幾個(gè)方面的問(wèn)題：第一，分類算法本質(zhì)上是兩類算法還是多類算法，例如支持向量機(jī)是兩類分類算法，而k近鄰則可以用于多類分類，如果使用兩類算法進(jìn)行多類分類，則需要首先把多類分類任務(wù)分解為若干個(gè)兩類分類任務(wù)后，再進(jìn)行訓(xùn)練；

51、第二，分類算法使用的是局部特征還是全局特征，所謂局部特征是指訓(xùn)練與分類時(shí)每個(gè)類別分別采用不同的特征空間，全局特征是指訓(xùn)練與分類時(shí)所有類別采用相同的特征空間，大部分分類算法使用全局特征與局部特征均可，但有些算法如樸素貝葉斯只能采用全局特征；第三，訓(xùn)練與分類的時(shí)間復(fù)雜度，一個(gè)好的分類系統(tǒng)應(yīng)該對(duì)文本能夠快速準(zhǔn)確地分類，訓(xùn)練時(shí)間較長(zhǎng)通?？梢匀淌埽绻诸悤r(shí)間過(guò)長(zhǎng)則往往讓人難以接受，例如k近鄰法在大規(guī)模文本分類問(wèn)題中就存在時(shí)間災(zāi)難的問(wèn)題。雖然已經(jīng)出現(xiàn)了一些性能不錯(cuò)的文本分類算法，但由于各個(gè)算法在不同應(yīng)用中的表現(xiàn)差異較大，因此仍然有很多學(xué)者致力于更為高效的算法的研究。文本分類算法目前的文本分類領(lǐng)域已經(jīng)有

52、了一些比較成熟的文本分類算法，下面我們介紹幾個(gè)常用算法。樸素貝葉斯算法樸素貝葉斯(Naive Bayes, NB)算法是機(jī)器學(xué)習(xí)領(lǐng)域中常用的一種基于概率的分類算法，非常簡(jiǎn)單有效。NB算法基于這樣一個(gè)樸素的基本假設(shè)（稱作貝葉斯假設(shè)）：假設(shè)文本中各個(gè)特征的出現(xiàn)是相互獨(dú)立的 125。該算法的關(guān)鍵是計(jì)算文本dj屬于類別ci的后驗(yàn)概率，根據(jù)貝葉斯公式(4-1)，把后驗(yàn)概率的計(jì)算轉(zhuǎn)化為先驗(yàn)概率的計(jì)算，然后取后驗(yàn)概率最大的一個(gè)或幾個(gè)類別作為文本最終類別。顯然，NB法是個(gè)多類算法，并可直接應(yīng)用于多標(biāo)號(hào)分類問(wèn)題中。 (4-1)其中，表示文本dj屬于類別ci的后驗(yàn)概率，表示文本dj在訓(xùn)練集中的概率，表示類別ci中

53、dj的先驗(yàn)概率，P(ci)表示訓(xùn)練集中類別ci的先驗(yàn)概率。由于如果dj確定，那么對(duì)所有類別為常數(shù)，因此有 (4-2)接下來(lái)的問(wèn)題就是如何估計(jì)和P(ci)。目前存在兩種計(jì)算模型，多變量貝努利模型(Multi-variate Bernoulli Model)與多項(xiàng)式模型(Multinomial Model)。假定訓(xùn)練集的特征空間為， tk表示第k個(gè)特征，|T|表示特征空間的維數(shù)，下面對(duì)這兩種模型分別進(jìn)行介紹。1.多變量貝努利模型多變量貝努利模型中，特征向量采用二進(jìn)制權(quán)重，在文檔中出現(xiàn)過(guò)的特征權(quán)重為1，未在文檔中出現(xiàn)過(guò)的特征權(quán)重為0。該模型是貝葉斯網(wǎng)絡(luò)中的傳統(tǒng)方法，已被廣泛應(yīng)用于文本分類中10,102,126。在整個(gè)計(jì)算過(guò)程中，未考慮