文本分類概述文本分類概述/NUMPAGES44文本分類概述文本分類概述第一章緒論1.1研究背景當今的時代，是一個信息技術飛速發展的時代。隨著信息技術的飛速發展，科學知識也在短時間內發生了急劇的、爆炸性的增長。據1998年的資料顯示[1]，70年代以來，全世界每年出版圖書50萬種，每一分鐘就有一種新書出版。80年代每年全世界發表的科學論文大約500萬篇，平均每天發表包含新知識的論文為1.3萬-1.4萬篇；登記的發明創造專利每年超過30萬件，平均每天有800-900件專利問世。近二十年來，每年形成的文獻資料的頁數，美國約1,750億頁。另據聯合國教科文組織所隸屬的“世界科學技術情報系統”曾做的統計顯示，科學知識每年的增長率，60年代以來已從9.5％增長到10.6％，到80年代每年增長率達12.5％。據說，一位化學家每周閱讀40小時，光是瀏覽世界上一年內發表的有關化學方面的論文和著作就要讀48年。而2005年的資料顯示[2]，進入20世紀后全世界圖書品種平均20年增加一倍，冊數增加兩倍。期刊出版物，平均10年增加一倍。科技文獻年均增長率估計為13％，其中某些學科的文獻量每10年左右翻一番，尖端科技文獻的增長則更快，約2-3年翻一番。同時，伴隨著Internet的迅猛發展，網站和網頁數也在迅速增長，大約每年翻一番。據估計，目前全世界網頁數已高達2000億，而Google宣稱其已索引250億網頁。在我國，中國互聯網絡信息中心從2001年起每年都對中文網頁總數作統計調查，統計結果顯示，中文網頁總數已由2001年4月30日的159,460,056個發展到2005年12月31日的24億個，增長之快可見一斑[3,4]從這些統計數字可以看出，我們被淹沒在一個多么浩大的信息海洋里！然而信息的極大豐富并沒有提高人們對知識的吸收能力，面對如此浩瀚的信息，人們越來越感覺無法快速找到需要的知識。這就是所謂的“信息是豐富的，知識是貧乏的”。如何在這樣一個巨大的信息海洋中更加有效的發現和使用信息以及如何利用這個信息寶庫為人們提供更高質量和智能化的信息服務，一直是當前信息科學和技術領域面臨的一大挑戰。盡管用戶對圖像、音頻和視頻等信息資源的需求也在急劇增加，但文本仍然是最主要的非結構化和半結構化的信息資源。針對目前的出版物和網絡信息大部分都以文本形式存在的狀況，自動文本分類技術作為處理和組織大量文本數據的關鍵技術，受到了廣泛的關注。1.2文本分類的定義文本分類的定義文本分類是指依據文本語義內容將未知類別的文本歸類到已知類別體系中的過程。文本分類有多個英文名稱，如TextCategorization[5]、TextClassification[6]、DocumentCategorization[7]、DocumentClassification[8]以及TopicSpotting[9]等，現在比較常用的為TextCategorization(TC)。文本分類的形式化定義如下，假設有一個文本集合D={d1,…,d|D|}和一個預先定義的類別集合C={c1,…,c|C|}，二者之間的真實關系可由以下函數表示[5]：(1-1)于是，自動文本分類問題可以轉化為找到函數的近似表示：(1-2)使得盡量逼近未知的真實函數。此處的函數稱為文本分類器，力求真實反映文檔和類別的關系，以便盡可能對未知類別的文本進行正確分類。文本分類根據分類算法的不同，可以分為兩類分類算法和多類分類算法。所謂兩類分類算法是指算法本質上只能進行兩類分類，即只能判別文檔屬于兩類中的某一類，如支持向量機算法；而多類分類算法是指算法可以同時對多個類別進行操作，即同時判別文檔屬于多類中的某一類或某幾類，如KNN算法。兩類分類算法應用于多類分類問題時，通常需要將一個多類分類問題轉化為若干個兩類分類問題來解決。具體轉化方法將在本文第二章詳細論述。另外，文本分類根據文檔所屬類別是否單一還可以分為單標號分類(Single-labelTextCategorization)問題和多標號分類(MultilabelTextCategorization)問題。所謂單標號分類指文檔的類別體系沒有重合，一篇文檔屬于且只屬于一個類別，而多標號分類是指文檔的類別體系有重合，一篇文檔可以屬于多個不同的類別。自動文本分類過程現代自動文本分類技術涉及到人工智能、機器學習、模式識別和統計理論等多個學科，自動文本分類的過程實際上也是機器學習和模式識別的過程。圖1-1為基本的分類過程。圖1-1自動文本分類模型如其他機器學習問題一樣，文本分類也包括訓練和測試兩個模塊。訓練模塊由預處理、文本表示、特征選擇(FeatureSelection)、分類器(Classifier)和性能評價五個部分組成：1.預處理負責對訓練集中的文本進行去除停用詞、詞干化(Stemming)、分詞、統計等操作，并對文本進行去噪處理。此處對中英文分別采取不同的處理，英文使用空格進行分詞[1,10]，而中文則需要根據語義進行分詞[11-15]或采用N-gram法進行分詞[16,17]。2.文本表示把文本表示成分類算法可以識別的形式。最常用的統計模型是由Salton等人提出的向量空間模型[18]，在此模型中，文檔dj被表示成向量的形式，，表示訓練集中出現過的特征集合。3.特征降維在文本表示階段使用的特征集合的數目通常非常巨大，并常含有大量對分類沒有貢獻甚至具有相反作用的噪聲特征。使用如此巨大的特征量會大大影響分類速度，因而需要通過特征降維減少特征數目，以提高訓練和分類的速度與精度。特征選擇后需要根據新的特征子集對文本重新進行表示。4.分類器使用各種機器學習和模式識別算法對訓練集進行學習，確定算法的各參數值，生成分類器。5.性能評價評價分類器對訓練集的分類結果，如果性能達不到要求，返回特征選擇階段重新選擇特征。分類模塊由預處理、文本表示和分類器三個部分組成：1.預處理功能作用和訓練模塊中的預處理相同。2.文本表示與訓練模塊的第一個文本表示有所不同，此處的文本表示使用的特征空間為經過特征選擇后的特征空間。3.分類器使用訓練完成的分類器對文本分類，輸出最終分類結果。至此，完成了整個文本分類過程。除了預處理部分與語種密切相關外，其余部分均獨立于語種。文本分類是一個應用性很強的技術，分類器的實現需要建立在一個高質量的訓練集基礎上，不同的應用領域有截然不同的訓練集。為了評測文本分類技術的優劣，人們建立了一些標準語料庫，常用的英文語料庫有Reuters[19]、20_newsgroups[20]、OHSUMED[21]等。目前還沒有標準的中文語料庫，較多使用的有復旦大學語料庫[22]、北京大學天網語料庫[23]等。為了避免產生過分適合的現象，語料庫通常包含兩個互不相交的訓練集和測試集。所謂過分適合指的是用訓練集來測試分類器，產生較好的分類性能，但是用別的文本進行分類時發生分類性能急劇下降的情況。1.3文本分類的發展歷史文本分類最早可以追溯到20世紀60年代[5,24,25]，在這之前主要是采用手工分類的方法。進入60年代后，Maron發表了具有里程碑作用的論文“Automaticindexing:Anexperimentalinquiry”，采用貝葉斯公式進行文本分類，大大推進了文本分類工作。在該文中，Maron還假設特征間是相互獨立的，這就是后來被廣泛采用的“貝葉斯假設”。在隨后的二十多年，主要是采用知識工程(KnowledgeEngineering,KE)的方法進行文本分類[26]，它通過在專家知識基礎上手工建立一系列分類規則來構建分類器。知識工程方法需要大量領域的專家和工程師參與，勢必耗費很多人力物力，當電子文檔急劇增長時將無法滿足需求。這種方法最典型的應用實例為由CarnegieGroup開發的CONSTRUE系統[27]，該系統用來對路透社的新聞稿件自動分類。直到進入20世紀90年代，隨著Internet的迅猛發展，為了能夠更好地處理大量的電子文檔，并且伴隨著人工智能、機器學習、模式識別、統計理論等學科的發展，基于知識工程的文本分類方法漸漸退出了歷史舞臺，文本分類技術進入了更深入的自動分類時代。由于基于機器學習的自動文本分類系統幾乎可以達到與人類專家相當的正確度，但是卻不需要任何知識工程師或領域專家的干預，節約了大量的人力，并且分類效率遠遠高于人類專家，因此機器學習方法在文本分類領域得到了深入的研究和廣泛的應用，例如貝葉斯、最近鄰、神經網絡、支持向量機等。1.4文本分類的應用領域自動文本分類是對文本信息基于內容管理的基礎，文本分類技術產生的初衷就是為信息管理服務，伴隨著信息技術和內容的多元化發展，文本分類也得到了越來越廣泛的應用，甚至涉及到通過語音識別和文本分類合成的方式對語音進行分類[46]以及通過分析文本標簽對多媒體文本分類[47]等。下面簡要介紹文本分類的幾種應用，這些應用之間的劃分沒有非常明確的界限，有時某個應用可能是另一個應用的特例。文本組織與管理以科學論文為例，本文1.1節曾經提到，80年代僅科學論文一項每天就產生1.3萬-1.4萬篇，科學文獻平均年增長率為13％，有些學科每10年翻一番，某些尖端學科2-3年翻一番。從這些統計數據可以得出，到目前為止，科技論文每天約產生4萬-5萬篇，如果進行人工分類，那么如此龐大的數據量必將使得各領域的科學家付出巨大的勞動。另外，科技論文對實時性的要求也很高，研究人員需要了解到本學科最新的研究現狀，這就要求論文庫能夠及時動態更新。所有這些情況都使得人工組織文本越來越成為不可能，此時就需要使用自動文本分類技術。文本分類使得有序地按類別存儲海量文件并及時作出更新成為可能。另外，Internet已經成為人們生活中必不可少的一部分，人們已經習慣了坐在電腦前了解自己感興趣的知識。各大門戶網站如新浪、雅虎、搜狐等都建有各自的層次化分類體系，對網頁根據其內容進行分類，讀者只需按類別層層找下去就可以瀏覽到各種信息。目前各網站的分類都需要人工干預，如果采用自動文本分類技術，無疑將大大改善分類效率。文本分類在數字化圖書館[48]、專利分類[49]、新聞文章自動歸檔和會議文章自動分組等方面都有成功應用。信息檢索毫無疑問，信息檢索(InformationRetrieval)工具可以根據查詢詞返回相關信息，有效幫助了人們查找相關知識，如Goole、Baidu、Yahoo、Excite等搜索引擎。但是，所有的搜索引擎都存在著相同的一個問題，返回結果并沒有如用戶期望的那樣排列，并且包含了大量用戶不感興趣的網頁，用戶必須通過閱讀這些網頁濾除無用信息，這就降低了查詢效率。在信息檢索領域引入文本分類技術，由用戶選擇查詢類別，或者由搜索引擎給出分類存放的搜索結果，都可以提高查詢效率，方便用戶使用。另外，針對信息資源庫中各個不同類別，還可以建立各類別的專用搜索引擎，直接供僅對某個專題感興趣的人使用。冗余文檔過濾信息檢索不僅包含了大部分用戶不感興趣的類別，還包含了大量相同或相似的網頁，在搜索結果較少時更是如此。這些相同或相似的網頁稱為冗余文檔，相同網頁是指除了鏈接地址不同，內容完全相同的網頁；相似文檔是指內容只有少許不同的網頁。雖然各大搜索引擎都號稱對相同和相似網頁進行了過濾，但在搜索結果中包含大量相同或相似網頁的情況還是經常出現。利用文本分類技術對網頁計算相似度，超過指定閾值的網頁即可認為是冗余文檔，在數據庫中只保存一份。NarayananShivakumar等對24,000,000個網頁進行統計分析，發現有18％的網頁有一個重復網頁，5％的網頁有10到100個重復網頁，經過冗余檢測后，可以把存儲空間壓縮22％[50]。為了提高檢測效率，計算網頁相似度之前，可以先對抓取到的網頁進行預分類，然后再根據網頁類別僅僅在該類別進行檢測，這樣不僅可以大大減少檢測時間和計算復雜度。信息過濾信息過濾(InformationFiltering)是指根據用戶對信息的需求，對產生或到來的信息流進行動態地分類，保留對用戶有用的信息，屏蔽無用信息。信息過濾與信息檢索如同一面硬幣的兩面[51]：信息檢索關心的是如何從信息源中找到符合用戶需求的信息，可以形容為“人找信息”，用戶為主動方，稱之為“拉”(pull)；信息過濾關心的是過濾系統如何把信息發送給感興趣的用戶，可以形容為“信息找人”，信息發布方為主動方，稱之為“推”(push)。信息過濾的一個典型應用如新聞推送服務，信息發布方為某個新聞社，用戶為某種報紙[5,52]。在這個例子中，過濾系統應該屏蔽掉所有用戶不感興趣的文檔，例如對于體育報紙，應該屏蔽所有與運動無關的文檔。因此信息過濾可以看作是一個單標號分類問題，把所有到來的文本分為兩個互不相交的類別：相關文檔和無關文檔。另外，過濾系統還可以進一步對相關文本按照各個主題進行分類，方便用戶閱讀。在上一個例子中，與運動有關的文本還可以進一步按照運動類別分類。同樣，垃圾郵件過濾系統也可以丟棄垃圾郵件[53]，并對非垃圾郵件根據用戶興趣進行分類。過濾系統既可以安裝在信息的發送端，此時系統基于信息內容僅發送給對該信息感興趣的用戶；也可以安裝在信息的接收端，此時系統負責阻斷用戶不感興趣的信息。對于前一種情況，系統需要為每個用戶建立一個檔案[54]，而在后一種情況下，系統只需建立一個用戶檔案。文檔過濾(DocumentFiltering)可以追溯到上世紀60年代有選擇的信息分發技術(selectivedisseminationofinformation)，當今數字信息的爆炸更加促進了這類技術的發展，如基于內容的垃圾郵件過濾、新聞組訂閱等[5]。詞義辨析詞義辨析(WordSenseDisambiguation)是指根據多義詞所處上下文環境判斷該詞此時含義的活動[5]。例如，英文英文單詞“bank”至少有兩個不同含義，在“theBankofEngland”中為“銀行”，在“thebankofriverThames”中為“河岸”，在“Iborrowedsomemoneyfromthebank”中“bank”的含義就需要借助詞義辨析來確定。把單詞所處上下文看作文本，把單詞的各種不同含義看作不同類別，那么詞義辨析問題就可以轉化為一個文本分類問題。顯然，詞義辨析屬于單標號分類任務。詞義辨析只是解決自然語言歧義性時常見難題中的一個例子，也是計算語言學中最重要的一個難題。還有很多機器翻譯中的其他問題，比如基于上下文的拼寫校對(Context-sensitivespellingcorrection)[57]、介詞短語連接(PrepositionalPhraseAttachment)[58]、詞性標注(Part-of-speechTagging)[59,60]等，也都可以通過借助文本文類技術來解決。第二章文本分類的性能評估2.1引言由于自動文本分類技術在文本處理領域具有關鍵性作用和廣泛的應用前景，因此得到了眾多學者的高度重視。隨著人工智能、機器學習、模式識別和統計理論等領域技術的快速發展，涌現出了越來越多的文本分類方法。但是，這些分類方法的性能如何，以及如何客觀評估和比較這些分類方法，就成為了選擇分類方法時無法忽視的問題。分類器的評估是一個非常復雜的問題，目前還沒有一個可以從理論上對單個分類器進行評估或對不同分類器進行比較的方法。由于難以從理論上對分類器進行客觀公正的評估，文本分類領域沿用了信息檢索領域的評估辦法，從仿真的實驗結果來評估分類器的性能。已有很多學者使用實驗的方法對分類器進行了比較，并且研究者在說明某種分類算法的性能時也是用數據來表示。分類器的性能評估有兩個重要的作用，客觀比較不同分類器僅僅是其中的一個方面，另一個重要作用是在訓練過程中指導分類器的生成。如圖1.1中所示那樣，分類器評估是訓練過程中必不可少的一個模塊，分類器的構建需要根據評估結果調整各參數，以使分類器性能達到最優。如同任何一個其他領域的科學實驗，文本分類的實驗結果也受很多客觀因素的影響，比如：實驗數據集的選定、文本的表示模型、特征選擇的方法、分類算法的確定、各參數的選定、評估指標的確定以及實驗數據的分析與處理等。顯然，不同分類器只有在諸多客觀因素均一致的情形下才具有可比性。許多學者基于Reuters、20_Newgroups、OHSUMED等標準數據集對一些分類算法進行了比較，結果就具有較高的可信度[29,81]。另外，由于分類器對數據集的嚴重依賴性，依靠仿真實驗得出的任何一種評估結果都只能作為一定的參考，在不同數據集上同一種分類方法可能會表現出截然不同的性能。由此可見，文本分類的性能評估是文本分類領域的一個重要課題，針對不同的目的，評估側重點也應有所不同。2.2文本分類器的性能評估指標從實驗方面來看，文本分類器的性能主要表現在兩個方面：效率和效果。所謂效率指的是分類器訓練和分類的時間；所謂效果指的是分類器做出正確決定的能力。具體到評估指標上，效率的評估指標是時間，即分類器訓練的時間及單篇文本分類的時間；而效果的評估指標并不唯一，有多種類型，下面將重點進行討論。在目前的文本分類應用中，主要關心的是分類效果的度量，所以本文也將主要討論分類效果的評估，本文其余部分若未特別指出，文本分類性能評估均指分類效果的評估。文本分類有多個性能評估指標，常用的有查全率(Recall,r)、查準率(Precision,p)、正確率(Accuracy,acc)、錯誤率(Error,err)以及查全率與查準率的綜合評價值、11-點平均(Eleven-pointaverage,11-Ave)和平衡點(Breakevenpoint,BEP)等。下面針對單標號分類器給出這些指標的定義及計算方法。假設一個單標號文本分類器、測試文本集合和預先定義的類別集合，D中每篇文檔只屬于一個類別，C中各類別兩兩之間互不相交。分別由專家和分類器來對全部測試文本判斷類別，那么可建立如下的鄰接表：表2-1多類分類器列聯表專家判別……分類器判別………………在表2-1中，的含義如下：(2-1)其中，表示原本屬于類別并被分類器正確判斷為的文檔數目，表示原本屬于類別但被分類器錯誤判斷為的文檔數目。根據表2-1，各指標定義及計算方法如下：1.查全率(Recall,r)與查準率(Precision,p)查全率定義為正確判別為該類的測試樣本占該類總測試樣本的比例，查準率定義為正確判別為該類的測試樣本占判別為該類的測試樣本的比例，那么類別的查全率和查準率的計算公式如下[5]： (2-2) (2-3)查全率與查準率來源于信息檢索領域，是最為傳統、也是使用最多的兩個指標。查全率和查準率從不同方面反映了分類系統的性能，查全率反映了分類的完備程度，即應該正確分類的文本中有多少被正確分類；查準率反映了分類的準確程度，即分類結果中有多少是正確的。二者通常被一起使用，作為一對指標從不同側面共同描述分類器性能。2.把查全率和查準率分開考慮沒有任何意義，例如，100篇文檔中有10篇屬于類別，假設訓練了一個類別的“接受分類器”，即所有文本均判為，那么對于來講，查全率達到100％，但查準率只有10％。于是，Rijsbergen提出了把二者綜合考慮的指標，類別的定義如下[108]：(2-4)其中，，是可調節參數，反映了和的相對重要程度。當時，為查準率；當時，為查全率。越小，越強調的作用；越大，越強調的作用。最為常用的是值，此時，認為與具有同等重要程度，計算公式如下：(2-5)3.11-點平均(11-pointaverage,11-Ave)11-點平均也是一個常用的分類器綜合評價指標[31,61]，來源于信息檢索領域。11-點平均定義為調整分類器參數，使得查全率分別為0％,10％,…,90％,100％時相應的查準率的算術平均值。4.平衡點(Breakevenpoint,BEP)Break-even點是另外一個綜合評價指標[39,62]，指的是分類器查全率與查準率相等時的值，這是分類器的一種特殊情況，此時。有時通過實驗可能得不到和相等的值，這時就取和最接近的值的平均值作為，稱為插值。5.宏平均(Macro-average)與微平均(Micro-average)前面所述幾個指標都是針對單個類別的局部性能進行評估的，對于一個多類分類器來講，關心的是整體性能。宏平均和微平均是計算全局性能的兩種方法。宏平均是指先計算各類別的性能指標，然后再求算術平均值，宏平均查全率()、宏平均查準率()及宏平均()的定義如下：(2-6)(2-7)(2-8)微平均是指計算各個樣本的分類性能，然后求算術平均值。微平均查全率()、微平均查準率()及微平均()的定義如下：(2-9)(2-10)(2-11)從微平均各指標的定義可以看出，如果在分類器中未引入拒識策略，則有，此時。宏平均和微平均兩種方式的結果可能相差很大，尤其是對于不均衡的測試集更是如此。宏平均是按類別求平均，微平均是按樣本求平均，故宏平均的結果受小類別影響較大，微平均的結果受大類別影響較大。6.正確率(Accuracy,acc)與錯誤率(Error,err)正確率與錯誤率也是兩個衡量分類器整體性能的指標。正確率定義為分類器正確分類的樣本占所有測試樣本的比例，錯誤率定義為分類器錯誤分類的樣本占所有測試樣本的比例，計算公式如下：(2-12)(2-13)正確率與錯誤率來源于機器學習領域，由公式(2-9)可以看出，正確率與微平均查全率的值完全相等，只是物理意義不同罷了。第三章文本表示3.1引言文本是一個由眾多字符構成的字符串，人類在閱讀文章后，可以根據自身的理解能力產生對文章的模糊認識，并對其進行分類。但計算機并不能理解文章的內容，從根本上說，它只認識0和1，所以必須把文本轉換為計算機或者說分類算法可以識別的形式。文本表示方法的選擇取決于文本中的語義單元以及把這些單元結合在一起的自然語言處理規則。對文本中語義單元的研究屬于詞匯語義學的范疇，對各單元組合規則的研究屬于組合語義學的范疇。文本表示首先根據詞匯語義學及組合語義學的相關知識對文本dj進行分割，把文本轉化為由若干個語義單元組成的空間形式，這就是在文本分類及信息檢索領域廣泛應用的向量空間模型(VectorSpaceModel，VSM)，這些語義單元tk稱為特征(term或feature)。確定文本所用特征后，再計算各特征在文本中的權重(weight)，文本dj被表示為特征向量的形式，其中權重值wkj表示特征tk在文本dj中的重要程度，T表示特征空間的特征集。向量空間模型是由Salton提出的[18]，最早成功應用于信息檢索領域，后來在文本分類領域也得到了成功應用。Salton的向量空間模型基于這樣一個假設：文本所屬類別僅與特定單詞或詞組在該文本中出現的頻數有關，而與這些單詞或詞組在該文本中出現的位置或順序無關。針對如何盡可能準確地表示文本，眾多學者進行了廣泛研究，主要集中在特征空間的選取和特征權重的計算方面。雖然使用向量空間模型表示文本將丟失大量文本信息，但這種文本的形式化處理使得大量機器學習算法在文本分類領域得到成功應用，大大促進了自動文本分類的發展。隨著文本分類技術的不斷進步，向量空間模型也處于不斷發展變化中。我們稱Salton最初提出的向量空間模型為狹義向量空間模型，在這基礎上發展起來的所有以向量形式表示文本的模型稱為廣義向量空間模型。事實上，目前使用的文本表示法基本上都是以向量形式表示的，各方法之間的差異主要表現在特征粒度及權重計算方法的不同。本文其余部分若不特別指出，向量空間模型均指廣義向量空間模型。3.2向量空間模型向量空間模型中，特征是文本表示的最小單位。劃分文本的特征可以是詞（包括字）、詞組、n-gram和概念等，根據特征粒度的不同，一篇文本可以有多種表示方式。下面介紹各種文本特征及特征權重計算方法。特征.1詞詞是自然語言理解的最小語義單位。不同的語種獲取詞的方式也大不相同。對英文等拼音文字而言，各個詞之間用空格進行分隔，計算機處理時可以用空格作為切分標志，來提取文本的特征。但是對于中文等亞洲文字來說，表達方式以字為最小單位，在自然理解當中又是以詞作為有意義的最小單位，詞與詞之間沒有自然分割標志，這樣就需要通過分詞來取得文本的詞特征。無論何種語種，都會有一些對分類沒有任何貢獻的代詞、介詞和連詞等，這些詞稱為停用詞(stopwords)。中英文對停用詞的處理也不同。英文通常根據分類任務構建停用詞表，然后在取詞特征時根據該表去除停用詞，表3-1是本文實驗中采用的停用詞表，包含319個停用詞。而中文通常通過分詞時建立的詞典去除停用詞，即詞典初始建立時就不包含停用詞。表3-1停用詞表aaboutaboveacrossafterafterwardsagainagainstallalmostalonealongalreadyalsobutbycallcancannotcantcocomputerconcouldcouldntcrydedescribefurthergetgivegohadhashasnthavehehenceherherehereafterherebymostlymovemuchmustmymyselfnamenamelyneitherneverneverthelessnextninenoseveralsheshouldshowsidesincesinceresixsixtysosomesomehowsomeonesomethingtowardstwelvetwentytwounderuntilupuponuseusedveryviawaswealthoughalwaysamamongamongstamoungstamountanandanotheranyanyhowdetaildodonedowndueduringeachegeighteitherelevenelsehereinhereuponhersherselfhimhimselfhishowhoweverhundrediienobodynonenoonenornotnothingnownowhereofoffoftenonsometimesometimessomewherestillsuchsystemtaketenthanthatthetheirwellwerewhatwhateverwhenwhencewheneverwherewhereafterwhereaswherebywherein表3-1（續）anyoneanythinganywayanywherearearoundasatbackbebecamebecausebecomebecomesbecomingbeenbeforebeforehandbehindbeingbelowbesidebesidesbetweenbeyondbillbothbottomelsewhereemptyenoughetcevenevereveryeveryoneeverythingeverywhereexceptfewfifteenfifyfillfindfirefirstfiveforformerformerlyfortyfoundfourfromfrontfullifinincindeedinterestintoisititsitselfkeeplastlatterlatterlyleastlessltdmademanymaymemeanwhilemightmillminemoremoreovermostonceoneonlyontoorotherothersotherwiseouroursourselvesoutoverownpartperperhapspleaseputratherresameseeseemseemedseemingseemsseriousthemthemselvesthenthencetherethereaftertherebythereforethereinthereuponthesetheythickthinthirdthisthosethoughthreethroughthroughoutthruthustotogethertootoptowardwhereuponwhereverwhetherwhichwhilewhitherwhowhoeverwholewhomwhosewhywillwithwithinwithoutwouldyetyouyouryoursyourselfyourselves另外，英文中存在各種時態、語態及名詞的單復數，故英文還可對文本中各單詞進行取詞根(stemming)處理，就是依據一定的語法規則剝離各個單詞的后綴，得到表明單詞基本含義的詞根。例如，answer,answered,answers的詞根都為answer,則統一用answer來表示。目前常用的是Porter的取詞根算法[115]。但也有研究說取詞根會降低分類性能[116]，但取詞根還是得到了很廣泛的應用，因為該方法可以有效降低特征維數。雖然以詞作為特征的詞表示法丟失了大量的文本信息，但依然能夠在文本分類中取得很好的效果，因而得到了廣泛使用。詞組以詞組作為特征的表示法稱為詞組表示法，該方法與詞表示法非常相似，唯一不同的是特征粒度變大了。顯然，用詞組作為特征可以更多地包含文本信息，但分類結果卻不盡人意[10,117]。主要原因在于詞組表示法雖然提高了特征的語義質量，但卻降低了特征的統計質量。和詞特征相比，詞組特征具有較多的特征、較多的同義或近義特征、較低的一致性以及較低的文檔頻率[10]。統計質量的降低只能使得特征向量更加稀疏，從而對分類性能產生影響。.3字符串與詞表示法和詞組表示法需要依賴于語種不同，字符串(n-gram)表示法[118]是完全獨立于語種的一種表示法。n-gram表示法把文本看作一個大字符串，由若干個以n個字符組成的字符串作為特征單位。在字符串表示法中，不再考慮文本的語義單位，文本只是一個由各種字符組成的字符串，由計算機根據字符長度n對文本進行分割。例如，“textcategorization”被14-gram分解為包含特征“textcategoriz”、“extcategoriza”、“xtcategorizat”、“tcategorizati”、“categorizatio”和“categorization”；“華南理工大學”被2-gram分解為包含特征“華南”、“南理”、“理工”、“工大”和“大學”。n-gram表示法可以避免分詞的工作，因此尤其適合中文等亞洲語言。但是n-gram的缺點也非常明顯，存在數據噪聲大、特征復雜、計算量大和易于過學習等問題。.4概念在自然語言中，一義多詞的現象非常普遍，比如“計算機”“電腦”“微機”表示的都是一個概念。概念具有很高的抽象性，一個概念可以對應一個詞，也可以對應若干個詞。從自然語言理解的角度看，采用概念作為特征是最高級的表示。采用概念作為特征有很多好處。首先，一個概念可能對應若干個不同的詞，這樣將大大降低特征空間的維數，提高分類速度；其次，同義詞的聚類使得該概念的權重集中，避免了權重分散帶來的對該特征的削弱，從而提高分類的精度。用概念表示文本需要有一個專門的語義詞典，這就需要語言專家和各領域專家的參與，無疑將耗費大量的人力和物力。所以，用概念表示文本的想法雖然非常好，但進展并不十分理想[119]。特征向量特征空間中不同特征項對文檔的重要程度和對分類的貢獻是不同的，因此文本分類系統在對文本進行形式化處理的時候，需要對文本的每個特征項賦權，以形成特定文本的特征向量，權重越大的特征認為對文本越重要。由于各研究者對特征重要性認識的不同，涌現出了許多特征權重計算方法，下面介紹幾種常用方法，這些方法都基于Zobel和Moffat提出的假設[64,120]：（1）IDF(InvertedDocumentFrequency)假設：稀有特征的重要程度不低于常見特征；（2）TF(TermFrequency)假設：一篇文檔中出現多次的特征的重要程度不低于只出現一次的特征；（3）規范化(Normalization)假設：同樣的特征匹配數，長文檔的重要程度不高于短文檔。從把文本轉換為若干個特征的集合到生成文本的特征向量，通常需要經過三個步驟：生成索引向量；對索引向量賦權；規范化。.1文本索引設訓練集有N篇文檔，特征空間為，對文本dj進行索引后得到索引向量，其中，fkj表示特征tk在文本dj中的索引值。索引值的計算通常有以下幾種方式。布爾索引是最簡單的一種索引方式，fkj值的取0或1，取值方式如下：(3-1)詞頻索引采用特征tk在文本dj中出現的次數TFkj作為索引值：(3-2)對數索引也利用了特征tk在文本dj中出現的次數TFkj，計算公式如下：(3-3)可以看出，無論采用何種方式計算的索引向量均為非負向量。雖然索引向量真實反映了文本中各特征項出現的情況，但由于各特征對分類的貢獻不同，需要在索引向量中進一步加入類別信息，以便準確分類。.2特征賦權特征賦權的方式有很多種，可以分為“均權”與“非均權”兩類。顧名思義，所謂“均權”，就是研究者認為特征在整個訓練集中的統計信息對分類不會產生實質性的影響，所以給索引向量中的每個特征賦以相同的權重，也就是使用原索引向量，既不突出也不抑制任何特征。而“非均權”認為特征分為主要特征和次要特征，經過賦權處理可以放大主要特征的作用，縮小次要特征的作用。目前的研究普遍認為不同特征在分類中的貢獻是不同的，一般采用“非均權”對特征加權。其中最有代表性的是“IDF(InvertedDocumentFrequency)權”。IDF權認為訓練集中包含特征tk的文檔數目越多，則該特征對分類的貢獻越小，這樣的特征需要受到抑制；相反，訓練集中包含特征tk的文檔數目越少，則該特征對分類的貢獻越大，這樣的特征需要被放大。設特征加權向量為，訓練集中出現過特征tk的文檔數為DFk，那么特征tk的加權值gk由下式計算：(3-4)至此，文檔dj由加權索引向量表示，等于索引向量與特征加權向量g的內積，由公式(3-5)計算。(3-5).3規范化為了消除文檔長度不同對加權索引向量h的影響，需要對h進行規范化處理，使得各特征權重落在區間[0,1]內，最終生成文本dj的特征向量。特征tk的權重wkj的計算公式如下：(3-6).4相似度計算文本表示為向量后，文本之間的距離或相似度可以通過空間中這兩個向量的幾何關系來度量。設有兩個特征向量和。如果特征向量是布爾向量，那么相似度函數通常采用漢明距離，定義如下：(3-7)如果特征向量非布爾向量，則相似度函數通常采用夾角余弦函數，定義如下：(3-8)3.3經典特征權重在文本分類領域，通常使用Salton等人提出的TFIDF(TermFrequencyandInvertedDocumentFrequency)公式計算特征項權重，特征tk在文檔dj中的TFIDF計算公式如(3-9)所示[5]：(3-9)其中，TFkj表示特征tk在文檔dj中出現的次數，DFk表示在整個訓練集中包含特征tk的文檔數，N表示整個訓練集中包含的文檔數。該公式的直觀解釋為：特征tk在文檔中出現的次數越高，在整個訓練集中包含該特征項的文檔數目越少，則該特征權重越大；反之，特征tk在文檔中出現的次數越少，在整個訓練集中包含該特征項的文檔數目越多，則該特征權重越小。對的規范化處理如下式所示：(3-10)其中，|T|表示特征向量的維數。第四章文本分類算法4.1引言文本分類算法作為自動文本分類技術的核心，一直處于重點研究與不斷發展當中。多年來的研究積累了很多經典的分類算法，如NaiveBayes[32,33]、k近鄰[30]、決策樹[34]等，也涌現出了不少新算法和改進的分類算法[35-45]。這些研究基本都致力于改進訓練和分類的速度和精度。目前文本分類的算法有很多種，包括k近鄰法、樸素貝葉斯算法、決策樹算法、決策規則算法、回歸模型、在線算法、Rocchio算法、神經網絡算法、支持向量機算法、最小二乘擬合與分類器組方法等。文本分類算法基本來源于機器學習與信息論領域，總體來說分類算法大致可分為兩大類：基于統計的方法和基于規則的方法。樸素貝葉斯算法是經典的基于統計的算法，決策樹則是基于規則的方法中的典型。為分類系統選擇分類算法時需要考慮以下幾個方面的問題：第一，分類算法本質上是兩類算法還是多類算法，例如支持向量機是兩類分類算法，而k近鄰則可以用于多類分類，如果使用兩類算法進行多類分類，則需要首先把多類分類任務分解為若干個兩類分類任務后，再進行訓練；第二，分類算法使用的是局部特征還是全局特征，所謂局部特征是指訓練與分類時每個類別分別采用不同的特征空間，全局特征是指訓練與分類時所有類別采用相同的特征空間，大部分分類算法使用全局特征與局部特征均可，但有些算法如樸素貝葉斯只能采用全局特征；第三，訓練與分類的時間復雜度，一個好的分類系統應該對文本能夠快速準確地分類，訓練時間較長通常可以忍受，但如果分類時間過長則往往讓人難以接受，例如k近鄰法在大規模文本分類問題中就存在時間災難的問題。雖然已經出現了一些性能不錯的文本分類算法，但由于各個算法在不同應用中的表現差異較大，因此仍然有很多學者致力于更為高效的算法的研究。4.2文本分類算法目前的文本分類領域已經有了一些比較成熟的文本分類算法，下面我們介紹幾個常用算法。樸素貝葉斯算法樸素貝葉斯(NaiveBayes,NB)算法是機器學習領域中常用的一種基于概率的分類算法，非常簡單有效。NB算法基于這樣一個樸素的基本假設（稱作貝葉斯假設）：假設文本中各個特征的出現是相互獨立的[125]。該算法的關鍵是計算文本dj屬于類別ci的后驗概率，根據貝葉斯公式(4-1)，把后驗概率的計算轉化為先驗概率的計算，然后取后驗概率最大的一個或幾個類別作為文本最終類別。顯然，NB法是個多類算法，并可直接應用于多標號分類問題中。 (4-1)其中，表示文本dj屬于類別ci的后驗概率，表示文本dj在訓練集中的概率，表示類別ci中dj的先驗概率，P(ci)表示訓練集中類別ci的先驗概率。由于如果dj確定，那么對所有類別為常數，因此有(4-2)接下來的問題就是如何估計和P(ci)。目前存在兩種計算模型，多變量貝努利模型(Multi-variateBernoulliModel)與多項式模型(MultinomialModel)。假定訓練集的特征空間為，tk表示第k個特征，|T|表示特征空間的維數，下面對這兩種模型分別進行介紹。1.多變量貝努利模型多變量貝努利模型中，特征向量采用二進制權重，在文檔中出現過的特征權重為1，未在文檔中出現過的特征權重為0。該模型是貝葉斯網絡中的傳統方法，已被廣泛應用于文本分類中[10,102,126]。在整個計算過程中，未考慮特征在文檔中出現的次序。由于貝葉斯假設認為文檔中各特征間是相互獨立的，所以可由下式計算：(4-