文本分類概述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

31、于組合語義學(xué)的范疇。文本表示首先根據(jù)詞匯語義學(xué)及組合語義學(xué)的相關(guān)知識對文本dj進(jìn)行分割，把文本轉(zhuǎn)化為由若干個語義單元組成的空間形式，這就是在文本分類及信息檢索領(lǐng)域廣泛應(yīng)用的向量空間模型(Vector Space Model，VSM)，這些語義單元tk稱為特征(term或feature)。確定文本所用特征后，再計(jì)算各特征在文本中的權(quán)重(weight)，文本dj被表示為特征向量的形式，其中權(quán)重值wkj表示特征tk在文本dj中的重要程度，T表示特征空間的特征集。向量空間模型是由Salton提出的18，最早成功應(yīng)用于信息檢索領(lǐng)域，后來在文本分類領(lǐng)域也得到了成功應(yīng)用。Salton的向量空間模型基于這樣一

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

33、式表示的，各方法之間的差異主要表現(xiàn)在特征粒度及權(quán)重計(jì)算方法的不同。本文其余部分若不特別指出，向量空間模型均指廣義向量空間模型。3.2向量空間模型向量空間模型中，特征是文本表示的最小單位。劃分文本的特征可以是詞（包括字）、詞組、n-gram和概念等，根據(jù)特征粒度的不同，一篇文本可以有多種表示方式。下面介紹各種文本特征及特征權(quán)重計(jì)算方法。特征.1詞詞是自然語言理解的最小語義單位。不同的語種獲取詞的方式也大不相同。對英文等拼音文字而言，各個詞之間用空格進(jìn)行分隔，計(jì)算機(jī)處理時可以用空格作為切分標(biāo)志，來提取文本的特征。但是對于中文等亞洲文字來說，表達(dá)方式以字為最小單位，在自然理解當(dāng)中又是以詞作為有意義的

34、最小單位，詞與詞之間沒有自然分割標(biāo)志，這樣就需要通過分詞來取得文本的詞特征。無論何種語種，都會有一些對分類沒有任何貢獻(xiàn)的代詞、介詞和連詞等，這些詞稱為停用詞(stop words)。中英文對停用詞的處理也不同。英文通常根據(jù)分類任務(wù)構(gòu)建停用詞表，然后在取詞特征時根據(jù)該表去除停用詞，表3-1是本文實(shí)驗(yàn)中采用的停用詞表，包含319個停用詞。而中文通常通過分詞時建立的詞典去除停用詞，即詞典初始建立時就不包含停用詞。表3-1 停用詞表aaboutaboveacrossafterafterwardsagainagainstallalmostalonealongalreadyalsobutbycallcan

35、cannotcantcocomputerconcouldcouldntcrydedescribefurthergetgivegohadhashasnthavehehenceherherehereafterherebymostlymovemuchmustmymyselfnamenamelyneitherneverneverthelessnextninenoseveralsheshouldshowsidesincesinceresixsixtysosomesomehowsomeonesomethingtowardstwelvetwentytwounderuntilupuponuseusedvery

36、viawaswealthoughalwaysamamongamongstamoungstamountanandanotheranyanyhowdetaildodonedowndueduringeachegeighteitherelevenelsehereinhereuponhersherselfhimhimselfhishowhoweverhundrediienobodynonenoonenornotnothingnownowhereofoffoftenonsometimesometimessomewherestillsuchsystemtaketenthanthatthetheirwellw

37、erewhatwhateverwhenwhencewheneverwherewhereafterwhereaswherebywherein表3-1 （續(xù)）anyoneanythinganywayanywherearearoundasatbackbebecamebecausebecomebecomesbecomingbeenbeforebeforehandbehindbeingbelowbesidebesidesbetweenbeyondbillbothbottomelsewhereemptyenoughetcevenevereveryeveryoneeverythingeverywhereex

38、ceptfewfifteenfifyfillfindfirefirstfiveforformerformerlyfortyfoundfourfromfrontfullifinincindeedinterestintoisititsitselfkeeplastlatterlatterlyleastlessltdmademanymaymemeanwhilemightmillminemoremoreovermostonceoneonlyontoorotherothersotherwiseouroursourselvesoutoverownpartperperhapspleaseputratherre

39、sameseeseemseemedseemingseemsseriousthemthemselvesthenthencetherethereaftertherebythereforethereinthereuponthesetheythickthinthirdthisthosethoughthreethroughthroughoutthruthustotogethertootoptowardwhereuponwhereverwhetherwhichwhilewhitherwhowhoeverwholewhomwhosewhywillwithwithinwithoutwouldyetyouyou

40、ryoursyourselfyourselves另外，英文中存在各種時態(tài)、語態(tài)及名詞的單復(fù)數(shù)，故英文還可對文本中各單詞進(jìn)行取詞根(stemming)處理，就是依據(jù)一定的語法規(guī)則剝離各個單詞的后綴，得到表明單詞基本含義的詞根。例如，answer, answered, answers的詞根都為answer,則統(tǒng)一用answer來表示。目前常用的是Porter的取詞根算法115。但也有研究說取詞根會降低分類性能116，但取詞根還是得到了很廣泛的應(yīng)用，因?yàn)樵摲椒梢杂行Ы档吞卣骶S數(shù)。雖然以詞作為特征的詞表示法丟失了大量的文本信息，但依然能夠在文本分類中取得很好的效果，因而得到了廣泛使用。

41、詞組以詞組作為特征的表示法稱為詞組表示法，該方法與詞表示法非常相似，唯一不同的是特征粒度變大了。顯然，用詞組作為特征可以更多地包含文本信息，但分類結(jié)果卻不盡人意10,117。主要原因在于詞組表示法雖然提高了特征的語義質(zhì)量，但卻降低了特征的統(tǒng)計(jì)質(zhì)量。和詞特征相比，詞組特征具有較多的特征、較多的同義或近義特征、較低的一致性以及較低的文檔頻率10。統(tǒng)計(jì)質(zhì)量的降低只能使得特征向量更加稀疏，從而對分類性能產(chǎn)生影響。.3字符串與詞表示法和詞組表示法需要依賴于語種不同，字符串(n-gram)表示法118是完全獨(dú)立于語種的一種表示法。n-gram表示法把文本看作一個大字符串，由若干個以n個字符組成的字符串作為

42、特征單位。在字符串表示法中，不再考慮文本的語義單位，文本只是一個由各種字符組成的字符串，由計(jì)算機(jī)根據(jù)字符長度n對文本進(jìn)行分割。例如，“text categorization”被14-gram分解為包含特征“text categoriz”、“ext categoriza”、“xt categorizat”、“t categorizati”、“categorizatio”和“categorization”；“華南理工大學(xué)”被2-gram分解為包含特征“華南”、“南理”、“理工”、“工大”和“大學(xué)”。n-gram表示法可以避免分詞的工作，因此尤其適合中文等亞洲語言。但是n-gram的缺點(diǎn)也非常明顯，

43、存在數(shù)據(jù)噪聲大、特征復(fù)雜、計(jì)算量大和易于過學(xué)習(xí)等問題。.4概念在自然語言中，一義多詞的現(xiàn)象非常普遍，比如“計(jì)算機(jī)”“電腦”“微機(jī)”表示的都是一個概念。概念具有很高的抽象性，一個概念可以對應(yīng)一個詞，也可以對應(yīng)若干個詞。從自然語言理解的角度看，采用概念作為特征是最高級的表示。采用概念作為特征有很多好處。首先，一個概念可能對應(yīng)若干個不同的詞，這樣將大大降低特征空間的維數(shù)，提高分類速度；其次，同義詞的聚類使得該概念的權(quán)重集中，避免了權(quán)重分散帶來的對該特征的削弱，從而提高分類的精度。用概念表示文本需要有一個專門的語義詞典，這就需要語言專家和各領(lǐng)域?qū)＜业膮⑴c，無疑將耗費(fèi)大量的人力和物力。所以，用概念表示文

44、本的想法雖然非常好，但進(jìn)展并不十分理想119。特征向量特征空間中不同特征項(xiàng)對文檔的重要程度和對分類的貢獻(xiàn)是不同的，因此文本分類系統(tǒng)在對文本進(jìn)行形式化處理的時候，需要對文本的每個特征項(xiàng)賦權(quán)，以形成特定文本的特征向量，權(quán)重越大的特征認(rèn)為對文本越重要。由于各研究者對特征重要性認(rèn)識的不同，涌現(xiàn)出了許多特征權(quán)重計(jì)算方法，下面介紹幾種常用方法，這些方法都基于Zobel和Moffat提出的假設(shè)64,120：（1）IDF(Inverted Document Frequency)假設(shè)：稀有特征的重要程度不低于常見特征；（2）TF(Term Frequency)假設(shè)：一篇文檔中出現(xiàn)多次的特征的重要程度不低于只出現(xiàn)

45、一次的特征；（3）規(guī)范化(Normalization)假設(shè)：同樣的特征匹配數(shù)，長文檔的重要程度不高于短文檔。從把文本轉(zhuǎn)換為若干個特征的集合到生成文本的特征向量，通常需要經(jīng)過三個步驟：生成索引向量；對索引向量賦權(quán)；規(guī)范化。.1文本索引設(shè)訓(xùn)練集有N篇文檔，特征空間為，對文本dj進(jìn)行索引后得到索引向量，其中，fkj表示特征tk在文本dj中的索引值。索引值的計(jì)算通常有以下幾種方式。布爾索引是最簡單的一種索引方式，fkj值的取0或1，取值方式如下： (3-1)詞頻索引采用特征tk在文本dj中出現(xiàn)的次數(shù)TFkj作為索引值： (3-2)對數(shù)索引也利用了特征tk在文本dj中出現(xiàn)的次數(shù)TFkj，計(jì)算公式如下：

46、(3-3)可以看出，無論采用何種方式計(jì)算的索引向量均為非負(fù)向量。雖然索引向量真實(shí)反映了文本中各特征項(xiàng)出現(xiàn)的情況，但由于各特征對分類的貢獻(xiàn)不同，需要在索引向量中進(jìn)一步加入類別信息，以便準(zhǔn)確分類。.2特征賦權(quán)特征賦權(quán)的方式有很多種，可以分為“均權(quán)”與“非均權(quán)”兩類。顧名思義，所謂“均權(quán)”，就是研究者認(rèn)為特征在整個訓(xùn)練集中的統(tǒng)計(jì)信息對分類不會產(chǎn)生實(shí)質(zhì)性的影響，所以給索引向量中的每個特征賦以相同的權(quán)重，也就是使用原索引向量，既不突出也不抑制任何特征。而“非均權(quán)”認(rèn)為特征分為主要特征和次要特征，經(jīng)過賦權(quán)處理可以放大主要特征的作用，縮小次要特征的作用。目前的研究普遍認(rèn)為不同特征在分類中的貢獻(xiàn)是不同的，一般

47、采用“非均權(quán)”對特征加權(quán)。其中最有代表性的是“IDF(Inverted Document Frequency)權(quán)”。IDF權(quán)認(rèn)為訓(xùn)練集中包含特征tk的文檔數(shù)目越多，則該特征對分類的貢獻(xiàn)越小，這樣的特征需要受到抑制；相反，訓(xùn)練集中包含特征tk的文檔數(shù)目越少，則該特征對分類的貢獻(xiàn)越大，這樣的特征需要被放大。設(shè)特征加權(quán)向量為，訓(xùn)練集中出現(xiàn)過特征tk的文檔數(shù)為DFk，那么特征tk的加權(quán)值gk由下式計(jì)算： (3-4)至此，文檔dj由加權(quán)索引向量表示，等于索引向量與特征加權(quán)向量g的內(nèi)積，由公式(3-5)計(jì)算。 (3-5).3規(guī)范化為了消除文檔長度不同對加權(quán)索引向量h的影響，需要對h進(jìn)行規(guī)范化處理，使得各特

48、征權(quán)重落在區(qū)間0,1內(nèi)，最終生成文本dj的特征向量。特征tk的權(quán)重wkj的計(jì)算公式如下： (3-6).4相似度計(jì)算文本表示為向量后，文本之間的距離或相似度可以通過空間中這兩個向量的幾何關(guān)系來度量。設(shè)有兩個特征向量和。如果特征向量是布爾向量，那么相似度函數(shù)通常采用漢明距離，定義如下： (3-7)如果特征向量非布爾向量，則相似度函數(shù)通常采用夾角余弦函數(shù)，定義如下： (3-8)3.3經(jīng)典特征權(quán)重在文本分類領(lǐng)域，通常使用Salton等人提出的TFIDF(Term Frequency and Inverted Document Frequency)公式計(jì)算特征項(xiàng)權(quán)重，特征tk在文檔dj中的TFIDF計(jì)算

49、公式如(3-9)所示5： (3-9)其中，TFkj表示特征tk在文檔dj中出現(xiàn)的次數(shù)，DFk表示在整個訓(xùn)練集中包含特征tk的文檔數(shù)，N表示整個訓(xùn)練集中包含的文檔數(shù)。該公式的直觀解釋為：特征tk在文檔中出現(xiàn)的次數(shù)越高，在整個訓(xùn)練集中包含該特征項(xiàng)的文檔數(shù)目越少，則該特征權(quán)重越大；反之，特征tk在文檔中出現(xiàn)的次數(shù)越少，在整個訓(xùn)練集中包含該特征項(xiàng)的文檔數(shù)目越多，則該特征權(quán)重越小。對的規(guī)范化處理如下式所示： (3-10)其中，|T|表示特征向量的維數(shù)。第四章 文本分類算法4.1引言文本分類算法作為自動文本分類技術(shù)的核心，一直處于重點(diǎn)研究與不斷發(fā)展當(dāng)中。多年來的研究積累了很多經(jīng)典的分類算法，如Naive

50、Bayes32,33、k近鄰30、決策樹34等，也涌現(xiàn)出了不少新算法和改進(jìn)的分類算法35-45。這些研究基本都致力于改進(jìn)訓(xùn)練和分類的速度和精度。目前文本分類的算法有很多種，包括k近鄰法、樸素貝葉斯算法、決策樹算法、決策規(guī)則算法、回歸模型、在線算法、Rocchio算法、神經(jīng)網(wǎng)絡(luò)算法、支持向量機(jī)算法、最小二乘擬合與分類器組方法等。文本分類算法基本來源于機(jī)器學(xué)習(xí)與信息論領(lǐng)域，總體來說分類算法大致可分為兩大類：基于統(tǒng)計(jì)的方法和基于規(guī)則的方法。樸素貝葉斯算法是經(jīng)典的基于統(tǒng)計(jì)的算法，決策樹則是基于規(guī)則的方法中的典型。為分類系統(tǒng)選擇分類算法時需要考慮以下幾個方面的問題：第一，分類算法本質(zhì)上是兩類算法還是多類

51、算法，例如支持向量機(jī)是兩類分類算法，而k近鄰則可以用于多類分類，如果使用兩類算法進(jìn)行多類分類，則需要首先把多類分類任務(wù)分解為若干個兩類分類任務(wù)后，再進(jìn)行訓(xùn)練；第二，分類算法使用的是局部特征還是全局特征，所謂局部特征是指訓(xùn)練與分類時每個類別分別采用不同的特征空間，全局特征是指訓(xùn)練與分類時所有類別采用相同的特征空間，大部分分類算法使用全局特征與局部特征均可，但有些算法如樸素貝葉斯只能采用全局特征；第三，訓(xùn)練與分類的時間復(fù)雜度，一個好的分類系統(tǒng)應(yīng)該對文本能夠快速準(zhǔn)確地分類，訓(xùn)練時間較長通常可以忍受，但如果分類時間過長則往往讓人難以接受，例如k近鄰法在大規(guī)模文本分類問題中就存在時間災(zāi)難的問題。雖然已經(jīng)

52、出現(xiàn)了一些性能不錯的文本分類算法，但由于各個算法在不同應(yīng)用中的表現(xiàn)差異較大，因此仍然有很多學(xué)者致力于更為高效的算法的研究。4.2文本分類算法目前的文本分類領(lǐng)域已經(jīng)有了一些比較成熟的文本分類算法，下面我們介紹幾個常用算法。樸素貝葉斯算法樸素貝葉斯(Naive Bayes, NB)算法是機(jī)器學(xué)習(xí)領(lǐng)域中常用的一種基于概率的分類算法，非常簡單有效。NB算法基于這樣一個樸素的基本假設(shè)（稱作貝葉斯假設(shè)）：假設(shè)文本中各個特征的出現(xiàn)是相互獨(dú)立的 125。該算法的關(guān)鍵是計(jì)算文本dj屬于類別ci的后驗(yàn)概率，根據(jù)貝葉斯公式(4-1)，把后驗(yàn)概率的計(jì)算轉(zhuǎn)化為先驗(yàn)概率的計(jì)算，然后取后驗(yàn)概率最大的一個或幾個類別作為文本最

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