文本分類算法畢業(yè)論文VIP

文本分類算法畢業(yè)論文學院：計算機科學與技術學院專業(yè)：電子信息科學與技術論文題目：基于半監(jiān)督的文本分類算法摘要隨著Internet的出現，大量的文字信息開始以計算機可讀的形式存在，以傳統(tǒng)的手工方式對這些信息進行組織整理既費時費力且效果不理想。文本分類作為處理和組織大量文本數據的關鍵技術，可以利用機器來對文本進行分析整理，使用戶從繁瑣的文檔處理工作中解放出來，并能極大地提高了信息的利用率。文本分類是指分析文本內容并按一定的策略把文本歸入一個或多個合適的類別的應用技術。而作為信息過濾、信息檢索、搜索引擎、文本數據庫、數字化圖書館等領域的技術基礎，文本分類技術有著廣泛的應用前景。本文首先介紹了文本分類的背景，文本分類所用的半監(jiān)督算法及文本分類的幾個關鍵技術。然后鑒于高分類精度需要大規(guī)模己標記訓練集而已標記文檔缺乏，利用未標識文檔進行學習的半監(jiān)督學習算法己成為文本分類的研究重點這一情況，著重研究了半監(jiān)督分類算法。最后本文設計了一個文本分類原型系統(tǒng)，為保證分類的準確性，采用了不同的標準數據集進行測試，并評價了其分類的性能。通過以上實驗表明，當有足夠的己標識文檔時，本算法與其它算法性能相當，但當已標識文檔很少時，本算法優(yōu)于現有的其它算法。關鍵詞:文本分類；半監(jiān)督學習；聚類；EM；KNNABSTRACTWiththeemergenceofInternet,alargenumberoftextmessagesbegantoexistintheformofcomputer-readable,tothetraditionalmanualwayfororganizationstocollatetheinformationistime-consumingeffortandtheresultisnotsatisfactory.Asthekeytechnologyinorganizingandprocessinglargemountofdocumentdata,Textclassificationcanusethemachinetocollatethetextanalysis,allowingusersfromthetediousworkofdocumentprocessingliberatedandcangreatlyimprovetheutilizationofinformation.Textclassificationisasupervisedleaningtaskofassigningnaturallanguagetextdocumentstooneormorepredefinedcategoriesorclassesaccordingtotheircontents.Moreover,textclassificationhasthebroadappliedfutureasthetechnicalbasisofinformationfiltering,informationretrieval,searchengine,textdatabase,anddigitallibraryandsoon..Thisthesisfirstlyintroducesthebackgroundofthetextclassification,textclassificationusingsemi-supervisedalgorithmandafewkeytechnologiesabouttextclassification.Secondlyconsideringthecontradictionofdeadlyneedforlargelabeledtrain-settoobtainhighclassificationaccuracyandthescarcityoflabeleddocuments，thisthesisemphasizesonimprovementofSemi-supervisedclassificationalgorithms，Finallywedesignadocumentclassificationsystem.Inordertoensuretheaccuracyofclassification,usingadatasetdifferentstandardsfortextingandevaluationoftheperformanceoftheirclassification.Theexperimentsaboveshowedthesuperiorperformanceofourmethodoverexistingmethodswhenlabeleddatasizeisextremelysmall.Whenthereissufficientlabeleddata，ourmethodiscomparabletootherexistingalgorithms.Keywords:textclassification;semi-supervisedleaning;clustering;EM;KNN目錄1引言 11.1課題背景 11.2本文的內容組織 22半監(jiān)督學習 32.1半監(jiān)督學習的概念及意義 32.2半監(jiān)督學習的研究進展 42.3半監(jiān)督學習的方法 52.3.1協同訓練(Co-training) 52.3.2自訓練 62.3.3半監(jiān)督支持向量機（S3VMs） 72.3.4基于圖的方法（Graph-BasedMethods） 82.4本章小結 93文本分類 103.1文本分類的概念及意義 103.2文本分類的國內外研究情況 103.3文本分類的關鍵技術 113.3.1文本特征生成 123.3.2特征選擇與降維 143.3.3權重計算 163.3.4文本分類技術 173.3.5文本分類技術性能評價 223.4本章小結 254基于EM和KNN的半監(jiān)督文本分類 274.1引言 274.2相關工作 274.2.1聚類分析 274.2.2EM算法 304.2.3KNN算法 314.3基于EM和KNN的半監(jiān)督文本分類算法 314.3.1問題描述 324.3.2算法思想 324.3.3基于EM算法的聚類分析 334.3.4基于Knn算法的分類 354.3.5算法步驟 364.4算法效率分析 374.5本章小結 385實驗與分析 395.1實現EM-KNN算法 395.1.1實驗平臺 395.1.2算法實現及流程圖 395.2實驗結果與分析 435.3小結 43總結 44參考文獻 45翻譯部分 48英文原文 48中文譯文 54致謝 611引言1.1課題背景隨著信息技術的發(fā)展，互聯網數據及資源呈現海量特征，而且，越來越多的信息以電子文本的形式存在。統(tǒng)計表明，目前網頁的數量呈指數型增長，平均每年增加一倍。截至2006年，全球每年制造、復制出的數字信息量共計1610億GB，這大約是有史以來出版的圖書信息總量的300萬倍。為了有效地管理和利用這些分布式的海量信息，基于內容的信息檢索和數據挖掘逐漸成為備受關注的領域。其中，文本分類(TextClassification)技術是信息檢索和文本挖掘的重要基礎。文本分類在自然語言處理、信息組織與管理、內容信息過濾等領域都有著廣泛的應用。因為文本分類可以極大地增強人們對海量信息的處理能力，早在上世紀中葉，有關文本分類的研究就已經開展起來。早在1957年，美國IBM公司的H．P．Luhn在自動分類領域最先進行了開創(chuàng)性的研究，提出了詞頻統(tǒng)計思想用于自動分類。1960年，M．E．Maron在JournalofACM上發(fā)表了有關自動分類的第一篇文章《OnRelevanceProbabilisticIndexingandInformationRetrieva1》，提出了自動關鍵詞分類技術，正式宣告了自動分類技術的誕生。[1]從20世紀60年代起步至80年代末，文本分類主要是以專家人工構建的知識工程技術為支撐，具有代表性的是卡內基集團為路透社開發(fā)的新聞自動分類系統(tǒng)(ConstrueSystem)?；谥R工程的分類系統(tǒng)具有較好的分類效果，但無法移植，需要大量領域專家的參與。從20世紀9O年代開始，隨著機器學習技術的不斷進步和發(fā)展，為自動文本分類器的出現奠定了基礎[3]?；跈C器學習的文本分類方法，更注重分類器的模型自動挖掘和生成及動態(tài)優(yōu)化能力，在分類效果和靈活性上都比之前基于知識工程和專家系統(tǒng)的文本分類模式有較大的提高與進步。從預先經人工正確分類的訓練文本集合中學習類別的特征信息，根據算法生成分類器。這種分類方法適應性強，方便移植，不需要行業(yè)專家的介入。從此以后，文本分類器處理海量信息的能力逐步受到IT業(yè)和廣大用戶的賞識，開始發(fā)揮越來越大的社會與經濟效益。例如，雖然各種搜索引擎部分地解決了Web上的資源發(fā)現問題，但由于搜索引擎存在著信息相關度差、精確度不高等原因，效果遠不能使人滿意；同時，搜索引擎的目的在于發(fā)現Web上的資源，就Web上的知識發(fā)現而言，即使檢索精確度再高也無法勝任。為此，我們需要開發(fā)比搜索引擎信息檢索技術更高層次的新技術。Web文本挖掘技術包括Web網頁文本內容的挖掘及結構挖掘。Web文本挖掘技術可以同搜索引擎、信息推送、信息過濾等信息處理技術相結合，有效地提高了信息服務的質量。[1][3]不可否認，上世紀90年代以來，文本分類技術取得了很大的進步，取得了值得稱道的喜人成績。隨著時代的進步，互聯網中分布傳播的海量電子化文本數量呈幾何級數增長，文本之間的關系也越來越復雜；同時，人們對分類效果評估指標（如查全率和查準率）的要求也越來越高，傳統(tǒng)的機器學習技術已經呈現“老態(tài)”。在機器學習領域，分類屬于監(jiān)督學習。絕大數的有監(jiān)督的機器學習方法依賴于標注的訓練樣本集，忽略了未標注樣本的作用，利用大規(guī)模的標注過的訓練數據固然可以提高學習算法結果的準確度，但是標記必須由人手工完成，這是一項費時費力的工作，己經不能適應Internet網上信息的增長速度。同時，網上存在大量容易獲得的未標識數據資源，半監(jiān)督學習算法就是利用這些未標注樣本，在傳統(tǒng)的機器學習方法中結合未標注樣本進行學習的算法。無疑它將在一定程度上提高學習算法的性能。1.2本文的內容組織本文首先介紹半監(jiān)督和文本分類的一些相關知識，然后提出了一種基于EM和KNN的半監(jiān)督文本分類算法，給出了算法的思想和步驟，并對其性能進行了測試分析。最后，給出了系統(tǒng)的實驗和分析結果。全文共分五章，具體安排如下：第一章是引言，介紹本文研究背景；第二章是半監(jiān)督學習，介紹關于半監(jiān)督的一些相關知識；第三章是文本分類，介紹文本分類的一些基本知識及文本分類的關鍵技術；第四章是基于EM和KNN的半監(jiān)督文本分類算法，提出了一種基于EM和Knn的半監(jiān)督文本分類算法，并分析了算法運行的效率；第五章是實驗與分析，首先用C語言實現本文算法的過程，然后通過標準數據集的實驗驗證和分析了本文算法的有效性。總結部分對本文的工作進行了總結，并指出了進一步需要開展的工作。2半監(jiān)督學習2.1半監(jiān)督學習的概念及意義半監(jiān)督學習是相對于監(jiān)督學習和無監(jiān)督學習提出來的，其介于監(jiān)督學習和無監(jiān)督學習之間。監(jiān)督學習通過具有標記的訓練示例進行學習，以盡可能正確地對訓練集之外的示例標記進行預測。無監(jiān)督學習通過對沒有標記的訓練示例進行學習，以發(fā)現訓練示例中隱藏的結構性知識。所謂的“標記”是指示例所對應的輸出，在分類問題中標記就是示例的類別，通常想要獲得有標記的訓練示例是很困難的，或者是費時耗力的，因為要標記它們需要使用人類的經驗進行人工的干預。然而，未標記的數據能夠很容易就被收集到，但卻沒有方法使用它們。半監(jiān)督學習通過使用大量的未標記的數據，用以輔助標記的數據，建立更好的分類器。半監(jiān)督學習除了提供給學習算法未標記的數據，還要提供給學習算法一些監(jiān)督信息。[2][11]半監(jiān)督學習的基本設置是給定一個來自某未知分布的有標記示例集以及一個未標記示例集，期望學得函數可以準確地對示例預測其標記。這里均為維向量，為示例的標記，||和||分別為和的大小，即它們所包含的示例數。半監(jiān)督學習是模式識別和機器學習中的重要研究領域。近幾年隨著機器學習理論在數據分析和數據挖掘的實際問題，例如網頁檢索和文本分類，基于生物特征的身份識別，圖像檢索和視頻檢索，醫(yī)學數據處理等問題中的廣泛應用，半監(jiān)督學習在理論和實際應用研究中都獲得了長足的發(fā)展。半監(jiān)督學習研究主要關注當訓練數據的部分信息缺失的情況下，如何獲得具有良好性能和推廣能力的學習機器，這里的信息缺失涵蓋數據的類別標簽缺失或者存在噪聲，數據的部分特征維缺失等多種情況。半監(jiān)督學習的理論研究對于我們深入理解機器學習中的許多重要理論問題，例如數據的流形與數據的類別信息的關系，缺失數據的合理處理，標注數據的有效利用，監(jiān)督學習和非監(jiān)督學習之間的聯系，主動學習算法的設計等都有非常重要的指導意義。[11]2.2半監(jiān)督學習的研究進展半監(jiān)督學習(Semi-supervisedLearning)是模式識別和機器學習中的重要研究領域。近幾年隨著機器學習理論在數據分析和數據挖掘的實際問題，例如網頁檢索和文本分類，基于生物特征的身份識別，圖像檢索和視頻檢索，醫(yī)學數據處理等問題中的廣泛應用，半監(jiān)督學習在理論和實際應用研究中都獲得了長足的發(fā)展。自20世紀八九十年代以來國際機器學習界研究者在半監(jiān)督學習研究領域展開了廣泛深入的探討和研究。其涵蓋的范圍非常廣泛，例如半監(jiān)督回歸問題；利用標簽和特征維都缺失的數據集進行學習；標簽有噪聲時的數據處理；利用少量正樣本和大量未標注數據進行學習以及對于大量未標注數據中已知只存在少量正樣本的情況下對于正樣本進行檢測；對各種監(jiān)督學習算法進行修改，探討如何融入非監(jiān)督數據信息或者對于非監(jiān)督學習算法進行修改，探討監(jiān)督數據信息的引入；利用有限混合模型對于數據的概率分布進行建?；蛘呃闷渌Ｐ蛯τ跀祿撕炾P于特征維的條件概率進行建模，利用EM算法學習模型參數的半監(jiān)督學習的研究；引入合適的數學方法進行半監(jiān)督學習，例如基于核矩陣的譜的分析，高斯隨機場的利用，利用圖論中的方法來對于樣本集進行聚類分析；半監(jiān)督數據的流形分析等。研究者同時開展了將半監(jiān)督學習和傳統(tǒng)模式識別和機器學習中的一些問題相結合的研究，例如基于半監(jiān)督學習的特征提取，半監(jiān)督學習和集分類器的設計等。國際研究者同時開展了與半監(jiān)督學習有著密切關聯的一些相關研究，具有代表性的是利用半監(jiān)督數據和數據的不同特征維子集在數據的不同視圖上同時訓練具有良好性能的學習機器。[2]半監(jiān)督學習研究正在繼續(xù)從廣度和深度上不斷進行擴展，但是依然存在很多問題。一方面半監(jiān)督學習的前提：聚類假設的數學分析依然不是十分完善，另一方面不同的監(jiān)督和非監(jiān)督算法的半監(jiān)督修改版本依然存在相當多的問題，有的因計算量太大受到問題規(guī)模的限制，有的是因為缺乏理論依據只是技術上的設計，有的是因為模型參數過多非常容易陷入局部極值等等。另外半監(jiān)督學習中如何更加有效利用標注數據的標簽信息和未標注數據的分布或者流形信息依然沒有得到很好的解決。半監(jiān)督學習實際應用的研究隨著許多實際領域需要分析和利用半監(jiān)督數據集廣泛開展起來。第一個問題涉及到聚類假設的合理性。主要探討的問題是在歐氏空間聚集程度比較高的地方，也就是比較大的地方，變化一定很平緩的假設的合理性。數據的標簽信息可以調整樣本之間的相似性度量，那么在特定的核空間討論和的關系或者說在核空間討論聚類假設會更加合理。顯然是與問題相關的，在實驗中，可以設計均勻的地方變化比較大或者存在梯度的人工仿真數據集合，這時如果利用聚類假設進行半監(jiān)督學習應當在特定的核空間才能進行。分析如何利用監(jiān)督數據信息設計合適的核空間以進行半監(jiān)督學習，討論和的關系對于半監(jiān)督學習機理中的聚類假設的分析有著很重要的理論研究意義。第二個問題是如何將監(jiān)督信息中的等約束和不等約束（Side-information）[8]引入更多的半監(jiān)督學習算法。半監(jiān)督學習的本質是在給出半監(jiān)督學習模型以及優(yōu)化目標后，對模型參數求解，其中監(jiān)督信息就是這些約束。目前，已經有一些基于這些約束的算法，例如相關成分分析（RelevantComponentAnalysis）[9]，這些方法在實際的分類問題中，獲得了很好的性能。那么，如果有效利用各種類型的監(jiān)督信息設計不同類型的半監(jiān)督學習模型依然是開放性的問題。2.3半監(jiān)督學習的方法根據半監(jiān)督學習算法的工作方式，可以大致將現有的很多半監(jiān)督學習算法分為三大類。第一類算法以生成式模型為分類器；第二類算法是基于圖正則化框架的半監(jiān)督學習算法；第三類算法是協同訓練算法。而主要的半監(jiān)督算法有：EM算法、S3VMs、自訓練、協同訓練、基于圖的方法等。由于在后文中會對EM算法有詳細介紹，故在此將不作介紹。2.3.1協同訓練(Co-training)Co-Training方法[3]通過把特征集分為兩個獨立部分并分別在各個特征空間下用己標記數據訓練分類器，再用分類器來分類未標記數據，挑出最確定的正例和反例加到標記例子中，兩個分類器針對增大的標記例子集合重新訓練，該過程重復執(zhí)行。以網頁為例，網頁本身存在兩種特征，一種特征是出現在網頁上的單詞，另一種特征是指向網頁鏈接上的單詞。聯合訓練通過NB（NaiveBayes）分類器訓練兩種不同特征生成的單詞，由此建立兩個內嵌的分類器A和B，利用已標記文檔，A用網頁特征的單詞訓練，B用鏈接特征的單詞訓練。然后，對于未標記文檔，A和B分別以最大后驗概率選出評分最高的文檔，標記類別并一起加入己標記訓練集，再如此逐次標記所有未標記文檔，由此得到擴大后的訓練集。然后利用此訓練集集合某種分類器再進行分類。重復執(zhí)行。實驗結果表明，利用聯合訓練得到的訓練集進行文本分類，平均分類錯誤率比EM-NB方法要低，性能比較穩(wěn)定。文獻[5]分析了聯合訓練算法優(yōu)于EM-NB的三個主要原因:原因之一是前者利用了網頁文檔的兩種結構信息進行聯合訓練;原因之二是它將兩個用NB分類算法建立的分類器作為內嵌的分類器訓練數據，從而降低了NB假設條件的影響;另一原因則是前者采用了增量訓練未標記文檔的方法，即在訓練分類器時，每次對未標記文檔只選出分值最高的部分文檔標記其類別，加入已標記文檔訓練集中。而EM技術則是在每次迭代中，對每篇未標記文檔都標記一個臨時類別，直到迭代收斂。但聯合訓練算法不適用于自身沒有多重特征的文檔(比如純文本文件)，而且很多類型的文檔不易切分特征。多種資源數據也不易統(tǒng)一切分特征屬性，在某些領域(如自然語言)，聯合訓練算法也存在許多局限[6][7]。2.3.2自訓練自訓練是半監(jiān)督學習的常用技術，在自訓練中，分類器首先用少量有標記的數據訓練。然后分類器用于對未標記的數據進行分類。典型地，最先確定的未標記數據點，連同其預測的標記，都被添加到訓練集。然后分類器重新訓練并且重復上述過程。分類器采用其自身的預測以訓練自己，這個過程也稱為自教，或自舉。這種方法來源于人類在沒有直接老師的情況下，對自己以前的經歷進行自學習，半監(jiān)督學習中的自訓練即是自動地對未標記的數據進行標記，自訓練是一個迭代地對自身進行預測并且迭代地訓練分類器的過程。在這個信息爆炸的時代，自訓練技術具有天然的優(yōu)勢：訓練過程的完全自動化，手工標記樣本引入的人為誤差可以避免，訓練樣本按需產生，訓練過程簡單高效。生成式模型以及EM方法可看成是“軟”自訓練的特例?？梢韵胂笠粋€分類錯誤可以加強其自身。如果預測的可信任度降低到某個門檻值，一些算法試圖避免這一點通過“忘掉”未標記的數據點。[11]自訓練已經被應用于幾個自然語言處理的工作。Yarowsky使用自訓練用于詞義消歧。Riloff等人使用自訓練辨別主觀名詞。自訓練還用于語法分析和機器翻譯。自訓練是一種封裝算法，一般來說很難進行分析。2.3.3半監(jiān)督支持向量機（S3VMs）半監(jiān)督支持向量機（Semi-SupervisedSVMs）本來被稱為直推式支持向量機（TSVM），之所以現在稱為半監(jiān)督支持向量機是因為它們也適用于歸納，而不僅僅是直推。其思想很簡單，即在低密度區(qū)找到一條決策邊界。但是，其背后的優(yōu)化問題是困難的。[11]TSVM通過把邊界置于低密度區(qū)域建立了和判別式決策邊界之間的聯系。TSVM是一種使用未標記數據的標準的支持向量機的擴展。標準的支持向量機只使用有標記的數據，目標是在再生核希耳伯特空（ReproducingKernelHilbertSpace）找到最大邊緣的線性邊界。在TSVM中未標記的數據也被使用，目標是找到未標記數據的一個標記，以便一個線性邊界在原始數據和未標記數據之間有最大邊緣。由于判別式方法直接利用類條件概率，在參數估計迭代過程中可能會偏離，而直推式支持向量機通過引導決策邊界遠離稠密區(qū)的方法建立決策邊界與間的聯系，因而成為一種克服這一問題的較好選擇。盡管找到精確的TSVM解是NP完全問題，但一些近似的方法已經提出并有積極的效果[23]。由于成功地把無標記樣本中所隱含的分布信息引入了支持向量機的學習過程中，TSVM算法比單純使用有標記樣本訓練得到的分類器在性能上有了顯著提高。但該算法在執(zhí)行前必須人為指定待訓練的無標記樣本中的正標記樣本數，而值一般是很難準確地估計的，在TSVM算法中采用了一種簡單的方法，即根據有標記樣本中的正標記樣本所占比例來估計無標記樣本中的正標記樣本比例，進而估計出值?？梢钥闯?，這種估計是有問題的，尤其是有標記樣本較少的情況下，一旦估計不正確，將會導致較差的結果。對這個問題，陳毅松等提出了一種改進算法漸進直推式支持向量機（ProgressiveTransductiveSupportVectorMachine,PTSVM）[24]，該算法通過成對標記和標記重置的辦法改進了TSVM的性能，但只適合于無標記樣本較少的情況，樣本較多時，這種頻繁的標記與標記重置將導致算法的復雜性迅速增加，并且遠超過一般的TSVM算法。現實應用的大多數情況是無標記樣本遠多于標記樣本,因而需要開發(fā)適應于這種情況的相應算法。鐘清流等提出了一種漸近式半監(jiān)督學習算法[25],它采用的特定取樣規(guī)則和核參數可以確保減少誤標記數量并控制決策面的動態(tài)調節(jié)進程，通過刪除非支持向量來提高訓練速度。實驗表明,這種算法能夠適應不同的樣本分布情況,并取得較好的效果,是一種值得關注的新嘗試。2.3.4基于圖的方法（Graph-BasedMethods）這曾經是半監(jiān)督學習研究最活躍的領域。基于圖的半監(jiān)督方法定義了一個圖，這個圖的各個節(jié)點表示有標記的和未標記的數據，圖的邊則反映了數據間的相似度，這些方法通常假定標記在圖上的平滑性。圖方法是非參量的、判別的、直推式的?；趫D的方法建立在流行假設上。圖的正規(guī)化：許多基于圖的方法可被視作估算一個在圖上的函數，需要同時滿足兩個條件：其應該接近于給定的在已標記的節(jié)點的標記；其應在整個圖上是平滑的。這是個正規(guī)化的框架，第一階段是一個損失函數，第二階段是一個正規(guī)化因子。當前有許多種基于圖的方法，它們都是相似的。重要的是怎麼構造一個好的圖，然而對于如何構造圖的研究還不夠成熟。大多數圖方法通過利用圖的拉普拉斯算子來涉及到圖。用表示一個圖，其邊權重為。邊的權重我指示出數據間的相似度。圖的權重矩陣表示為：由定義的對角陣稱為的度矩陣?，F在有多種方法來定義圖的拉普拉斯算子，較為著名的有：規(guī)范化圖的拉普拉斯算子，未規(guī)范化圖的拉普拉斯算子，分別表示為：通常預測由未標記節(jié)點的標記組成。因此，這種算法本質上時直推式的，也就是說，其只返回在未標記數據點上決策函數的值，而不是決策函數本身的值。圖的信息傳播也能有助于改進一個給定的考慮未標記的數據的分類。通常圖是由計算機目標的相似性而構成的，例如在歐幾里得數據點上使用核函數。但有時源數據已經具有圖的形式。2.4本章小結本章對于半監(jiān)督的概念、研究意義、研究進展以及半監(jiān)督學習方法進行了分析和討論，重點討論了半監(jiān)督學習常用的幾種方法，并且重點放在半監(jiān)督分類上。3文本分類3.1文本分類的概念及意義Internet信息量的迅猛增加，增加了人們獲取有效信息的難度，而且信息產生的速度遠遠超過人們收集信息、利用信息的速度，使得人們無法快速地查找到最新的信息，從而造成了時間、資金和精力的巨大浪費。面對網上海量的信息，傳統(tǒng)的做法是對網上信息進行人工分類，并加以組織和整理，從而為人們提供一種相對有效的信息獲取手段。但是，這種人工分類的做法存在著許多弊端，不僅耗費大量的人力、物力和財力，而且存在著分類性能不佳的問題。因此，如何有效的組織和管理數據，方便人們的檢索?如何區(qū)分有用的信息和無用信息?如何從海量的數據中高效地獲取有用知識?如何滿足用戶的個性化需求?所有這些都成了人們亟待解決的問題。文本分類是指按照預先定義的分類體系，根據文本內容自動地將文本集合的每個文本歸入某個類別，系統(tǒng)的輸入是需要進行分類處理的大量文本，而系統(tǒng)的輸出是與文本關聯的類別。簡單地說，文本分類就是對文檔標以合適的類標簽。從數學的角度來看，文本分類是一個映射過程，它將未標明類別的文本映射到現有類別中，該映射可以是一一映射，也可以是一對多映射，因為通常一篇文本可以與多個類別相關聯。文本分類的映射規(guī)則是，系統(tǒng)根據已知類別中若干樣本的數據信息總結出分類的規(guī)律性，建立類別判別公式和判別規(guī)則。當遇到新文本時，根據總結出的類別判別規(guī)則確定文本所屬的類別。在理論研究方面，對單類別分類的研究要遠遠多于對多類別分類的研究。主要是由于單類別分類算法可以非常容易地轉化成多類別分類算法，不過這種方法有一個假設條件，即各個類之間是獨立的，沒有相互依存關系或其它影響，當然在實際應用中，絕大多數情況是可以滿足此假設條件的。因此，在文本分類的研究中，大部分實驗都是基于單類別分類問題的探討。3.2文本分類的國內外研究情況國外自動分類研究始于1950年代末，H.P.Luhn在這一領域進行了開創(chuàng)性的研究，他首先將詞頻統(tǒng)計的思想用于文本分類中。1960年Maron在JournalofASM上發(fā)表了有關自動分類的第一篇論文“Onrelevanceprobabiliticindexingandinformarionretriral"。1962年博科(H.Borko)等人提出了利用因子分析法進行文獻的自動分類。其后許多學者在這一領域進行了卓有成效的研究。國外的自動分類研究大體上可以分為三個階段:第一階段（1958年-1964年)主要進行自動分類的可行性研究;第二階段(1965年-1974年)，自動分類的實驗研究;第三階段(1975年-至今)，自動分類的實用化階段。[26]國外當前流行的文本分類方法有Rocchio法及其變異方法、k近鄰法（KNN)、決策樹、樸素貝葉斯、貝葉斯網絡、支持向量機(SVM)等方法。這些方法在英文以及歐洲語種文本自動分類上有廣泛的研究，而且很多研究表明KNN和SVM是英文文本分類的最好方法。國外很多研究人員對英文文本分類領域的各個問題都有相當深入的研究，對幾種流行的方法進行了大量的對比研究。SusanDumais等學者對這5種方法進行了專門的比較研究。國內自動分類研究起步較晚，始于20世紀80年代初期。1981年侯漢清對計算機在文獻分類工作中的應用作了探討[27]，并介紹了國外在計算機管理分類表、計算機分類檢索、計算機自動分類、計算機編制分類表等方面的概況。我國自動分類的研究大體上正在經歷從可行性探討--輔助分類--自動分類系統(tǒng)的發(fā)展階段。關于中文文本分類的研究相對較少，國內外的研究基本上是在英文文本分類研究的基礎上采取相應策略，結合中文文本的特定知識，然后應用于中文之上，繼而形成中文文本自動分類研究體系。國內外的很多學者在基于知識和統(tǒng)計的兩種方法上對中文文本分類進行了大量的研究工作，主要有基于詞典的自動分類系統(tǒng)和基于專家系統(tǒng)的分類系統(tǒng)。如上海交通大學、中國科學院、清華大學、北京大學、北京信息工程學院、復旦大學、東北大學、山西大學以及新加坡、香港和臺灣的一些大學都有相應的研究成果，也研制出了不少的實驗系統(tǒng)。3.3文本分類的關鍵技術一般的自動文本分類有以下幾個階段[10]，具體如圖3-1所示。生成訓練語料庫的文本特征全集；文本特征提取，形成特征子集；采用某種數學模型和分類方法進行分類器構造；利用訓練語料庫中的文本對分類器進行訓練，得到分類器的相關參數。訓練文本采集及處理訓練文本采集及處理特征提取/文本表示特征空間降維構造分類器分類和輸出新文本預處理訓練過程分類過程圖3-1文本分類過程[26]由圖3-1所示及上述的文本分類的幾個階段，可以看出文本分類過程所需要的幾個關鍵技術，現下面開始介紹文本分類的關鍵技術。3.3.1文本特征生成在當前的計算機技術的研究水平下，機器還不可能識別自然文本，從根本上說，它只認識0和1，所以必須將文本轉換為計算機可以識別的形式。而要想讓計算機“讀懂”文本，必須能夠找到用于文本表示的數學模型。隨著信息檢索技術的發(fā)展，逐漸發(fā)展起來的主要有三個文本檢索模型，分別是:布爾模型[10](BooleanModel，BM)、向量空間模型[12][13](VectorSpaceModel，VSM)和概率模型(ProbabilisticModel，PM)，這些模型從不同角度使用不同的方法處理特征加權、類別學習和相似度計算等問題，而最經典、最實用的是向量空間模型，本文的研究是建立在向量空間模型之上的。向量空間模型是由Salton在20世紀60年代末提出的，它最早應用于信息檢索領域，例如著名的SMART(SystemfortheManipulationandRetrievalofText)系統(tǒng)就成功的應用了向量空間模型技術，后來又在文本分類領域得到了廣泛的應用。向量空間模型的基于兩個基本假設，一是文檔所屬的類別僅與某些特定的詞或詞組在該文檔中出現的頻數有關，而與詞或詞組在文檔中出現的位置或順序無關;二是假設文檔的各特征詞之間是相互獨立的。這樣，只需要提取出一份文檔中蘊涵的各個特征詞的詞頻信息就可以對其進行正確的分類。向量空間是由一組線性無關的基本向量組成，向量維數與向量空間維數一致，并可以通過向量空間進行描述。下面介紹文檔向量空間的一些基本概念:文本:泛指一般的文獻或文獻中的片段(段落、句子或句子組)，一般指一篇文章(假設文檔中不包含除文字以外的其他多媒體信息)。特征項:文本的內容特征常常用它所含有的基本語言單位(字、詞、詞組或短語)來表示，一般中文中使用詞語作為文本的特征項。特征項的權重:對于含有個特征項的文本，常用一定的權重表示特征項在文本中的重要程度。即把文本表示為，特征詞表示為，特征詞的權重表示為。這樣自然語言形式的文本文檔就可以在向量空間中完全由特征向量來表示。對兩個文本試和之間的內容相關程度的度量被稱為相似度，可以用如下公式計算：（3-1）tkttktitj圖3-2文本的向量空間模型及文本間的相似度其中，為特征向量的維數，表示第個文本的第個特征項的權重值。向量空間模型的主要優(yōu)點在于:(l)標引詞加權改進了檢索效果;(2)其部分匹配策略允許檢出與查詢條件相接近的文獻;(3)利用余弦公式，根據待測文獻與訓練文獻之間的相似度對其進行排序。與其他的檢索模型相比，向量空間模型簡單、便捷，而且分類性能也非常好，已成為當今最流行的檢索模型。3.3.2特征選擇與降維實現文本自動分類的基本困難之一是特征項空間的維數過高。數量過大的特征項一方面導致分類算法的代價過高，另一方面導致無法準確地提取文檔的類別信息，造成分類效果不佳。因此，需要在不犧牲分類質量的前提下盡可能地降低特征項空間的維數。特征選擇的任務就是要將信息量小，“不重要”的詞匯從特征項空間中刪除，從而減少特征項的個數，它是文本自動分類系統(tǒng)中的一個關鍵步驟。常用的文本特征選擇方法有:文檔頻率()、信息增益()、互信息()、統(tǒng)計量()，文本證據權，優(yōu)勢率，統(tǒng)計()等。這些方法都是基于閾值的統(tǒng)計方法，它們的基本思想都是對每一個特征計算某種統(tǒng)計度量值，然后設定一個閩值，把度量值小于閾值的那些特征過濾掉，剩下的即認為是有效特征。1、文檔頻率文檔頻率(DocumentFrequency)，就是文檔集合中出現某個特征項的文檔數目。在特征項選擇中，計算每個特征項在訓練集合中出現的頻率，根據預先設定的閡值排除那些文檔頻率特別低和特別高的特征項。文檔頻率的計算復雜度較低，隨訓練集的增加而線性增加，能夠適用于大規(guī)模語料，因此是特征降維的常用方法。其基本原則是:很少出現的特征對分類價值極小，對整個分類系統(tǒng)的效果影響也很小，因此，將這些特征去掉有助于降低特征空間維數，并且當這些不常出現的特征為噪音時，還會有助于提高分類正確率。但在信息檢索領域，文檔頻率較低的特征項被認為是信息含量較高，與文本分類中的原則是相反的。2、信息增益信息增益(InformationGain)，是一種在機器學習領域應用較為廣泛的特征選擇方法。它從信息論角度出發(fā)，用各個特征取值情況來劃分學習樣本空間，根據所獲取信息增益的多寡，來選擇相應的特征。其計算公式如下:（3-2）其中，表示文本中出現單詞時，文本屬于的概率；同樣表示文中不出現單詞時文本屬于的概率;表示類文本在語料中現的概率;表示在整個文本訓練集中出現的概率?；バ畔⒒バ畔⒎椒?MutualInformation)，可以度量特征項和類別的共現關系，特征項對于類別的互信息越大，說明特征中包含的與類別有關的鑒別信息就越多。因此，互信息衡量的是詞與類之間的相關程度。文本分類中，一個特征詞只有一個信息增益和文檔頻率，但擁有的互信息數目卻是與訓練語料中類別的數目相同的，對應于每個類，該特征詞都會有一個互信息值。一個詞可以對應幾個互信息值，一般來說，因為我們的目的是選出對分類比較有用的詞，所以通常根據每個詞最大的互信息值來排序，然后從高到低選擇特征詞或者設定一個閾值排除那些互信息值比較低的詞。假設文檔集合分為類，記為，，…，，特征項對于文檔類別的互信息(，)的計算公式如下:（3-3）其中(，)為特征項出現在類中的概率，(，)為特征項在所有文檔中的出現概率。4、統(tǒng)計使用衡量特征項的重要程度時，只考慮到了正相關對特征項重要程度的影響。如果特征項和類別反相關，就說明含有特征項的文檔不屬于的概率要大一些，這對于判斷一篇文檔是否不屬于類別也是很有指導意義的。為克服這個缺陷，使用以下公式計算特征項和類別的相關性:（3-4）其中:為和同時出現的次數;為出現而沒有出現的次數。為出現而沒有出現的次數;為和同時沒有出現的次數。為訓練集中的文檔數。和類似，如果和不相關，則(，)值為0，因為在這種情況下，個訓練文本的數目應該在這四種文本中均勻分布，即===。而另一個極端，詞與類別非常相關，體現在這四個數量上，就是詞出現的文本屬于類別，而詞不出現的文本不屬于類別。這樣的話，==/2，而==。在衡量詞和類別之間的相關關系上，互信息和統(tǒng)計量之間有一定的相似之處。這兩個向量間的不同之處在于互信息是一個非規(guī)格化的值，其取值范圍很大，特別是對于那些邊緣概率分布很小的情況。而統(tǒng)計量則是一個規(guī)格化的量。對于詞，我們可以采用兩種方法來求取其在訓練集上的統(tǒng)計量值：（3-5）或是：（3-6）同相同，如果有個類，每個就會有個值，取它們的平均，就能得到特征選取所需的一個線性序列。平均值大的特征優(yōu)先被選取。算法的計算復雜度也為。特征權方法基于術語在鄰近相關文檔中出現的頻率來測試術語的強度。和是任意不同但相關的文檔，術語的權值可由下式計算出:（3-7）但是實際中發(fā)現某些值很低的特征反而是信息量比較高的，不能從特征空間中刪去，因此這種方法在某些情況下不可靠。以上介紹了五種常用的特征選擇方法，它們具有的共同優(yōu)勢是計算量相對較小，而且結果特征集的解釋性強，就是原來特征詞集的子集，但是它們一些方面還需改進，比如分類器的特征集包含很多冗余的信息，同義詞、多義詞都能造成這種情況;一個詞單獨可能對分類器的作用不大，選擇時被刪去，但和其它一些詞結合卻是很好的辨別因素等等。3.3.3權重計算特征項選擇出來后，要對每個項賦予權重，應使文本中越重要的項的權重越大。目前最普遍的賦權重的方法是運用統(tǒng)計方法，即用文本的統(tǒng)計信息，主要是詞頻，來計算特征項的權重。下面對常用的加權函數進行詳細介紹。布爾權重布爾權重是最簡單的一種加權方法，如果特征詞出現次數為0，則其權重為0，如果特征詞出現詞數大于0，則其權重為1。公式如下:（3-8）其中表示特征詞在文檔中的權重，表示特征詞在文檔中出現次數。詞頻權重該方法將特征詞的頻次作為權重。公式如下：（3-9）-權重該方法基于以下兩點原因:一是特征詞在文檔中出現詞數越多越重要，權重和成正比;二是文檔集中含有特征詞的文檔數越大越不重要，權重和成反比。公式如下:（3-10）該式表明，若特征詞在所有文檔中均出現，即=，則=0，也就是說，雖然特征詞出現次數多，但它的分布比較均勻，說明它沒有區(qū)分類別的能力?？紤]到文檔長度的影響，對上面公式進行歸一化:（3-11）為了降低的作用將式(3-11)調整為：（3-12）3.3.4文本分類技術1、文本分類模式CCjCkCjCjCk圖3-3樣本的多峰分布圖3-4樣本的邊界重疊文本分類器包括兩個要素，一個是文本存在的特征空間，另一個是在該特征空間中所采取的分類方法。分類器的構造模式有兩種，一種是單分類器模式，一種是多分類模式[15][16]，分別敘述如下:（1）單分類器模式所謂單分類模式，是指文本的全集及類別的全集共享一個特征空間，所有的文本及類別在這個特征空間中的不同區(qū)域內分布，并在這個特征空間中執(zhí)行一種分類方法。在單分類器模式下的輸出為待分類文本所屬的具體的類別[12]。由于各個類別的樣本同時存在于一個特征空間中，因而各個類別的樣本之間存在著多峰分布和邊界重疊的問題(見圖3-3，3-4)。具體地說，就是同類樣本之間的距離可能會大于不同樣本之間的距離，各類樣本存在著混雜分布的情況;同類樣本的分布不夠緊湊，大多數的樣本處于類別的邊界，類與類之間存在著邊界重疊的情況。這樣一來，在單分類器模式下，對處于這兩種情況下的樣本，很難給予正確的分類。比如，圖3-4中位于和類交界處的樣本，就無法區(qū)分他們究竟屬于類還是屬于類。而對于圖3-3所示的情況，在采用KNN法或SVM法的時候，很難給予正確的分類，而采用Rocchio法則需要很好地選擇類向量。（2）、多分類器模式CCjCj圖3-5多分類器模式下類樣本的多峰分布所謂多分類器模式，是指各類的文本獨享一個特征子空間，每個類的文本只在自己的特征子空間中分布，類與類的特征子空間之間相互獨立，各個特征子空間中可以執(zhí)行不同的分類方法。多分類器模式下，每個類別的分類器的輸出為待分類文本是否屬于該類別。這種模式下，不會存在各類的樣本混雜分布的情況，同類樣本之間的多峰分布表現為該類樣本在自己的特征子空間中的不同區(qū)域內分布(圖3-5)。對于樣本的邊界重疊問題，也就是對存在著兼類現象的文本，在多分類器模式下，會對此類文本賦予多個類別。多分類器模式事實上是通過特征空間的劃分取代單分類器模式下的區(qū)域劃分，以此來解決樣本的多峰分布及邊界重疊問題，而空間的劃分也導致了其上執(zhí)行的分類方法的隔離。但采用多分類器的假設前提是認為各類文本之間是相互獨立的，事實上，這一點很難做到，因為自然語言的豐富多樣性使得各類文本之間存在著用語“斜交”的情況，也就是說，這種獨立性的假設前提是不存在的，因而各個類別的特征子空間之間的相互獨立也是很難做到的。這也是為什么現有的文本分類系統(tǒng)大多采用單分類器的原因，不過采用多分類器模式可以比采用單分類器模式使用更少的向量維數而達到較好的分類效果。2、常用的文本分類算法文本轉化為向量形式并經特征提取以后，便可以進行文本分類了，也稱特征匹配。機器學習領域常用的分類算法有:Rocchio算法、Knn算法、樸素貝葉斯分類、決策樹、支持向量機等分類法。下面介紹幾種常用的分類方法:（1）、Rocchio算法[17]Rocchio算法是情報檢索領域最經典的算法。該算法中，首先為每一個類建立一個原型向量，然后通過計算文檔向量與每一個原型向量的距離來給分類。Rocchio公式為：（3-13）其中指類的中心向量，是指文檔向量的權重，是所有訓練樣本的數目，是訓練集中屬于類的正例樣本的個數，為反例樣本的個數。、、分別用來控制中心向量、正例集和反例集所占的權重。通常，為了強調正例文本的重要性，正例的權值取得較大，而反例的權值取得比較小。（2）、樸素貝葉斯分類(NaiveBayes)[18]NaiveByaes(以下簡稱NB)分類方法是一種簡單而又非常有效的分類方法。NB方法的一個前提假設是:在給定的文檔類語境下，文檔屬性是相互獨立的。假設為一任意文檔，它屬于文檔類中的某一類。根據NB分類法有:（3-14）(3-15)對文檔進行分類，就是按(3-15)式計算所有文檔類在給定情況下的概率。概率值最大的那個類就是所在的類，即:(3-16)由(3-14)、(3-15)和(3-16)可知，對于給定分類背景和測試文檔，用NB方法分類的關鍵就是計算和。計算和的過程就是建立分類模型的過程。NB方法假設一個單詞在一個分類文檔中的發(fā)生概率與該文檔中的其它單詞無關，從而使得計算復雜度簡單，具有較高的效率。但是該假設對于絕大多數真實的文本都不成立，從而分類精度有所降低。（3）、決策樹(DecisionTree)[19]決策樹提供了一種展示類似在什么條件下會得到什么值這類規(guī)則的方法，比如，在貸款申請中，要對申請的風險大小做出判斷，圖3-6是為了解決這個問題而建立的一棵決策樹，從中可以看到決策樹的基本組成部分:決策節(jié)點、分支和葉子。決策樹中最上面的節(jié)點稱為根節(jié)點，是整個決策樹的開始。本例中根節(jié)點是“收入>￥40，000”，對此問題的不同回答產生了“是”和“否”收入>收入>￥40，000工作時間>5年高負債低風險高風險低風險高風險否否否是是是圖3-6一棵簡單的決策樹決策樹的每個節(jié)點子節(jié)點的個數與決策樹所用的算法有關。如CART算法得到的決策樹每個節(jié)點有兩個分支，這種樹稱為二叉樹。允許節(jié)點含有多于兩個子節(jié)點的樹稱為多叉樹。每個分支要么是一個新的決策節(jié)點，要么是樹的結尾，稱為葉子。在沿著決策樹從上到下遍歷的過程中，在每個節(jié)點都會遇到一個問題，對每個節(jié)點上問題的不同回答導致不同的分支，最后會達到一個葉子節(jié)點。這個過程是利用決策樹進行分類的過程，利用幾個變量(每個變量對應一個問題)來判斷所屬的類別(最后每個葉子會對應一個類別)。（4）、支持向量機SVM[20]SVM是一種建立在統(tǒng)計學習理論基礎上的機器學習方法，有較好的推廣性能和較高的分類準確率。該算法基于結構風險最小化原理，將數據集合壓縮到支持向量集合(通常為前者的3％～5％)，學習得到分類決策函數。SVM的主要思想是在向量空間中尋找一個決策面，使它能最好地將數據點分割為兩部分。Margin=Margin=H1HH2圖3-7支持向量機的決策面在線性可分空間中，決策面常被稱為超平面。如圖3-7所示，圓圈為一類數據點，實心圓為另一類數據點，H即為分割它們的超平面。離超平面最近的數據點就被稱為支持向量，也就是圖中在H1和H2上的數據點。H1和H2間的距離稱為分隔間隔(Margin)，SVM就是要達到既使這個間隔最大，也能精確地分類的目的。支持向量與超平面之間的距離為，則支持向量間距為，尋找超平面的問題可化為求解以下二次規(guī)劃問題：最小化泛函數約束條件為：利用Lagrange優(yōu)化方法得到最優(yōu)分類面：，，為任意支持向量從上式可以看出，=0的樣本對于分類不起任何作用，只有>0的樣本起作用，從而決定分類結果，這樣的樣本即為支持向量。相應的分類器為：在線性可分情況下，支持向量機的內積核函數：SVM本質上是解決兩類分類問題，所以SVM解決個類的分類問題需要轉化為兩類分類問題，其方法可以是：構造個分類器，第個分類器的訓練數據是第類的數據作為正例，其他類的數據作為反例，為每個類構造一個分類器，第個分類器在第類和其他－1類之間構造一個超平面，在多個兩類分類器中具有最大輸出的類別即是測試文本所屬的類別。3.3.5文本分類技術性能評價1、影響分類效果的主要因素根據實驗和經驗，影響文本分類算法和系統(tǒng)質量評價的因素是多方面的，除分類算法的因素外，還與測試方法、分類標準、分類層次和語料庫是否標準等有關。(1)、測試方法的影響:開放性測試與封閉性測試的分類準確度的差距非常明顯，但是隨著訓練文本集的增大，這一差距在縮小。封閉性測試是指訓練語料的學習獲取分類知識，開放性測試是對測試語料進行分類實驗。與封閉性實驗相比，開放性測試的結果更具有實際意義，一般而言，封閉式實驗結果比開放式測試效果好，但是，當訓練語料庫的規(guī)模達到相當大的程度，封閉性測試結果與開放性測試結果應趨于吻合，如當語料數量從2000篇增加到5000篇左右時，差距僅縮小一個百分點。(2)、訓練語料的影響:在相同的分類標準下，各人對分類規(guī)則的理解差異，較大程度影響分類系統(tǒng)的準確度，以相同的分類標準與分類層次(1層)等測試環(huán)境，以來源于復旦大學的訓練語料作為學習樣板，測試來源于人民日報和sina網的語料，發(fā)現分類的精度下降很多。一個合理的解釋是各人對分類規(guī)則的理解差異導致人工標注的不同。(3)、類別特點的影響:分類標準的制定，在相當程度上影響文本分類的準確度，特別是存在類別交叉情況時更突出。有的學科，分類類別定義范圍比較明確，如體育、電腦技術等，此類分類精度比較高;而部分學科，存在著交叉現象，分類精度較低，如政治、經濟等。主要原因是分類標準對于交叉學科的范圍定義含糊，訓練集受人工干預較大，沒有特別明顯的概念特征，對于測試文檔，很難提取出有效的分類特征向量。(4)、類別總量是影響分類系統(tǒng)準確度的一個重要因素，類別總量越多，分類精度越低，產生分類交叉的可能性也就越大，如果人工分類過于詳細，系統(tǒng)在自動分類中，對于一些交叉的類別分類精度會降低。(5)、訓練文本類別的分布情況的影響:如果訓練文本類別的分布過度不均勻，則將會使分類結果偏向于文本數較多的一類。從而導致分類精度的降低。2、評價標準傳統(tǒng)的信息檢索著眼于發(fā)現資源，所用的指標主要有準確率(Precision)和召回率(Recall)等。文本分類是為了揭示分類器的分類性能，因此除了上述兩項指標外，還采用了收益率(Gain)、分類正確率(ClassifiCation)、準確率與召回率的幾何平均數、信息估計值等來衡量分類器的性能。一般用準確率、召回率、F值和微平均來衡量系統(tǒng)的性能，其中，是實際屬于類的測試文檔數;是分類器預測為類的文檔數;是正確分類的文檔數。對于簡單的兩類分類器，評價系統(tǒng)性能的指標分別定義如下:（1）正確率:識別正確的樣本數/識別樣本總數（2）召回率()/查全率:分類器正確判為該類的樣本數/該類的樣本總數，即：漏識率，（3）準確率（）:正確判為該類的樣本數/判為該類的樣本總數，即:誤識率，（4）錯誤率:識別錯誤的樣本數/識別樣本總數（5）漏識率:該類樣本中沒有被判為該類的樣本數/該類樣本總數（6）誤識率:不屬于該類的樣本數/判為該類的樣本總數（7）F值:將準確率與召回率兩者結合為一個指標，兩者相對比重可用參數來刻畫，計算公式如下:（3-17）式中，，當=0時，；當=時，；當=1時（即F1），Precision與Recall在系統(tǒng)中有著同樣的重要性;當<l時，強調Precision的作用:當>l時，強調Recall的作用。對于多類別分類，一般采用平均的方法:微平均(micro-average)和宏平均(macro-average)。微平均統(tǒng)一計算全部類的召回率、準確率和F1(即中=1)值，宏平均計算每一類的召回率、準確率和F1值后取算術平均值。用、和表示微平均中的微觀召回率、微觀準確率和微觀F值，則分類系統(tǒng)的微平均計算公式如下:（3-18）（3-19）（3-20）用、和表示宏平均中的宏觀召回率、宏觀準確率和宏觀F值，則分類系統(tǒng)的宏平均計算公式如下:（3-21）（3-22）（3-23）一般來說，微平均易受到大類結果的影響，而宏平均是對全部類別取均值，相對易受小類分類結果的影響。影響文本分類的因素影響文本分類的因素主要有以下幾種:（1）使用不同的特征生成方法。（2）使用不同的特征提取方法。（3）使用不同數量的特征。（4）是否采用了特征平滑技術。（5）使用不同的權重計算函數。（6）使用不同的分類方法。所謂特征平滑技術是指對文本中沒有出現的特征的處理，比如，對那些沒在文本中出現的特征詞賦予一個較低權重值，避免文本向量過于稀疏。3.4本章小結本章主要是對文本分類相關知識的學習。除了對文本分類概念、意義及國內外發(fā)展情況作了簡要介紹外，重點介紹了文本分類的一些關鍵技術，如文本特征生成、特征選擇與降維、文本分類性能評價等。4基于EM和KNN的半監(jiān)督文本分類4.1引言本文針對的是KNN這種常用的文本分類算法。KNN算法是一種基于實例的文本分類算法，對于一個測試文檔，需要計算它與訓練樣本集中每個文本的文本相似度，依文本相似度找出K個最相似的訓練文本，然后在此基礎上分別計算測試文本與K個文本的權重，最后將測試文本分到權重最大的那個類中。在上述經典KNN算法中，對于一個測試文檔，需要計算它與訓練樣本集中每個文本的相似度，計算復雜度非常高。針對這一問題，本章提出了一種在聚類基礎上的半監(jiān)督文本分類算法，算法首先對訓練集進行聚類，計算每類的中心點，之后將每類的中心點和為聚類文本組合成新的訓練集，最后用經典KNN算法對新的訓練集進行訓練。通過實驗我們發(fā)現，上述算法在很大程度上減少了其計算復雜度，從而提高了分類器的性能。4.2相關工作4.2.1聚類分析聚類是人類一項最基本的認識活動。通過適當的聚類，事物才便于研究，事物的內部規(guī)律才可能為人類所掌握。所謂聚類就是按照事物的某些屬性，把事物聚集成類，使類間的相似性盡量小，類內相似性盡量大。聚類是一個無監(jiān)督的學習過程，分類是有監(jiān)督的學習過程，兩者的根本區(qū)別在于:分類時需要事先知道分類所依據的屬性值，而聚類是要找到這個分類屬性值。文本聚類和文本分類相比，最主要區(qū)別就是分類學習的樣本或數據有類別標記，而要聚類的樣本沒有標記，需要由聚類學習算法自動確定。分類方法是典型的有監(jiān)督學習方法，它需要預先定義一個訓練集，即對文本集合進行人工分類，作為構造分類函數或分類模式的基礎。但定義訓練文本集是一個枯燥而又費時的工作，并且隨著時間的推移，這些文本集合隨時都在添加新內容，主題也可能發(fā)生變化，從而需要重新定義主題類別和訓練集。而采用無監(jiān)督學習方法時，就不需要人工預先確定訓練文本類別，省去了枯燥而又費時的工作。相似性度量聚類分析是基于這樣一個認識:每一類別對象之間較為相似，而類間對象之間應該具有較大差異。對應不同性質的數據，人們給出了不同的相似性度量標準。主要有以下兩類函數:（1）、相似函數:兩個樣本點愈相似，則相似系數值愈接1;樣本點愈不相似，則相似系數值愈接近0。這樣就可以使用相似系數值來刻畫樣本點性質的相似性。如果一個函數:滿足以下條件，我們就稱之為相似系數函數：（4-1）（4-2）（4-3）越接近1，兩個特征變量間的關系越密切。經常采用的相似系數有以下兩種:a、夾角余弦：（4-4）這是受相似性啟發(fā)而來，夾角余弦函數忽略各個向量的絕對長度，著重從形狀方面考慮它們之間的關系。當兩個向量的方向相近時，夾角余弦值較大，反之則小。特例是當兩個向量平行時，夾角余弦值為1;而正交時值為0。b、相關系數（4-5）相關系數是對向量做標準化后的夾角余弦，表示兩個向量的線性相關程度。（2）、距離函數:設用個特征項來描述樣本，那么我們就可以把每個樣本點看作維空間中的一個點，進而使用某種距離來表示樣本點之間的相似性，距離越近的樣本點性質越相似，距離越遠的樣本點差異越大。假設有個對象，描述第個對象的個屬性值分別對應于區(qū)間變量值，，……，，描述第個對象的個屬性值分別對應于區(qū)間變量值，，……，。那么對象和之間的相似度一般以它們之間的距離來表示。其計算公式如下:（4-6）其中，，，為正整數。當=1時，表示曼哈頓距離。當=2時，表示歐幾里德距離，它是比較常用的距離計算公式。不論采用上述那一種距離計算方法，區(qū)間變量計量單位越小，度量值越大，對距離計算影響也就越大，從而使得差異度值也越大。為了避免計量單位對差異度計算的這種影響，可以對變量進行標準化處理。主要的聚類算法可以劃分為如下幾類：（1）劃分的方法(Partioningmethod):它是一種基于原型的聚類方法，其基本思路是:首先從數據集中隨機地選擇幾個對象作為聚類的原型，然后將其他對象分別分配到由原型所代表的最相似、也就是距離最近的類中。對于劃分聚類方法，一般需要一種迭代控制策略，對原型不斷進行調整，從而使得整個聚類得到優(yōu)化，例如使得各對象到其原型的平均距離最小。實際上，絕大多數應用采用了以下兩個比較流行的啟發(fā)式方法:（i）k-平均算法:在此算法中，每個簇用該簇中對象的平均值來表示;（ii）k-中心點算法:在此算法中，每個簇用接近聚類中心的一個對象表示。此類方法比較適用于聚類的形狀為凸形，大小和密度相似，聚類的數目可以合理估計的情況。此外這兩種方法都要求用戶指定聚類數目k。（2）基于層次的方法(heirarchicalmethod):該方法對給定的數據對象集合進行層次分解。根據層次的分解如何形成，層次聚類方法可以分為凝聚的和分裂的。（i）凝聚的方法，也稱自底向上方法。一開始將每個對象作為單獨的一個組，然后相繼合并相近的對象或組，直到所有的組合并為一個(層次的最上層)，或者達到一個終止條件。（ii）分裂的方法，也稱為自頂向下方法，一開始將所有對象置于一個簇中。在迭代的每一步中，一個簇被分裂為更小的簇，直到最終每個對象在單獨的一個簇中，或者達到一個終止條件。層次聚類方法的缺陷在于，一旦一個步驟(合并或者分裂)完成，它就不能被撤銷，即不能更正錯誤的決定。（3）基于密度的方法(density-basedmethod):絕大多數劃分方法基于對象之間的距離進行聚類。這類方法只能發(fā)現球狀簇，而在發(fā)現任意形狀的簇上遇到了困難。隨之提出了基于密度的另一類聚類方法。以局部數據特征作為聚類的判斷標準，主要思想是:只要臨近區(qū)域的密度(對象或數據點的數目)超過了某個閥值，就繼續(xù)聚類。也就是說，對給定類中的每個數據點，在一個給定范圍的區(qū)域中必須至少包含某個數目的點。這樣的方法可以用來過濾“噪音”孤立點數據，發(fā)現任意形狀的簇。（4）基于網格的方法(grid-basedmehotd):基于網格的方法把對象空間量化為有限數目的單元，形成了一個網絡結構。所有的聚類操作都在這個網絡結構(即量化的空間)上進行。這種方法的主要優(yōu)點是處理速度快，其處理時間獨立于數據對象的數目，只與量化空間中每一維的單元數目有關。（5）基于模型的方法(model-basedmethod):基于模型的方法為每個簇假定了一個模型，尋找數據對給定模型的最佳擬合。如一個基于模型的算法可能通過構建反映數據點空間分布的密度函數來定位聚類。就某一個聚類算法而言，往往融合了多種聚類方法的思想，并不能簡單地將其歸為上述某一類方法。4.2.2EM算法EM算法[21]是由Dempster提出，是一種被廣泛使用的半監(jiān)督學習算法，這是一種在不完全資料情況下計算極大似然函數估計和后驗概率分布的迭代算法，亦用于計算邊緣分布。名為EM算法是為了強調迭代算法的兩個步驟，即Expectationstep和Maximizationstep：（1）E-step：在給定觀測資料和前一次迭代所得的參數估計情況下計算完全資料對應的條件期望，利用當前網絡結構和參數對未標記樣本數據做軟分類；（2）M-step：用極大似然函數估計確定參數的值，用于下一步的迭代。把所有已標記樣本和已軟分類的樣本作為訓練樣本集，計算出新的最大可能的參數分布，并用來替換原有的。EM算法要求在E-step和M-step之間不斷迭代，直到所估計的參數達到局部最優(yōu)。EM算法的具體步驟操作將在4.3.3章節(jié)講述。目前，許多EM算法的擴展版本關注的是如何修改EM算法使得能夠盡量收斂到合理的局部極值，例如確定性退火EM算法（DeterministicAnnealingEMalgorithm簡寫為DAEM)[28]，分裂融合EM算法（SplitandMergeEM簡寫為SMEM）[29]，或者使得EM算法在理論上能夠收斂到全局最優(yōu)值，例如利用可逆的可跳轉的MarkovMonteCarlo[30]鏈基于隨機采樣的機制搜索全局最優(yōu)，另一方面，是關于如何對于模型復雜度加入約束以使EM算法能夠自動選擇有限混合模型的成分的數量同時收斂到合理的局部極值，例如基于最小信息長度（MinimumMessageLength簡寫為MML）[31]準則的一個算法，和基于競爭機制的EM算法。4.2.3KNN算法K近鄰算法[22]是一種穩(wěn)定而有效的基于實例的文本分類方法。采用KNN方法進行文檔分類的過程如下：對于某一給定的測試文檔d，在訓練文檔集中，通過相似度找到與之最相似的K個訓練文檔。在此基礎上，給每一個文檔類打分，分值為K個訓練文檔中屬于該類的文檔與測試文檔之間的相似度之和。也就是說，如果在這K個文檔中，有多個文檔同屬于一個類，則該類的分值為這些文檔與測試文檔之間的相似度之和。對這K個文檔所屬類的分值統(tǒng)計完畢后，即按分值進行排序，只有分值超過閾值的類才予以考慮。具體步驟如下：（1）假定K=最近鄰數；（2）計算測試文檔d與所有訓練文本的相似度；（3）從中選出K個與文本d最相似的訓練文本為測試文本d的最近鄰；（4）收集這些已選出的最近鄰的類別；（5）根據K個最近鄰，給每一個類別打分；其中，，為閾值。（6）分值最大的類別即為測試文本的類別。4.3基于EM和KNN的半監(jiān)督文本分類算法本節(jié)將重點介紹本文所研究的基于半監(jiān)督的文本分類算法，對算法思想、算法步驟、算法的具體操作及算法的效率都做了詳細的介紹。4.3.1問題描述前面已經介紹了，文本分類需要大量的數據集進行訓練。然而在眾多訓練集中，得到有標記的數據是非常困難的，且費時費力；但未標記的數據卻很容易就能得到。故現在文本分類大部分都是應用的半監(jiān)督算法，以標記數據為主，未標記數據為輔來不斷完善分類器。然而就是因為帶標記數據比較難得到，數據非常少，從而可能造成前期訓練分類器時出現錯誤，如圖4-1示：圖4-1圖4-1分類示圖其中，實心為已標記數據，空心為未標記數據，三角形和圓形代表兩類。虛線代表可能造成的錯誤分類，實線為正確的分類。如圖4-1，在分類中由于標記數據非常少，很可能造成如“虛線”一般的錯誤分類。本文所研究的基于半監(jiān)督的分類算法就是為解決此類問題，盡可能減少錯誤的分類，從而提高分類器的性能。4.3.2算法思想本章所研究的算法思想是：先根據標記數據進行聚類，計算每類的中心點，用新的中心點和未聚類文本組成新的訓練集，然后用新的訓練集進行分類?；舅枷肴鐖D4-2所示，圖中兩個多邊形代表聚類結果，其它的與圖4-1相同。算法的具體步驟及實現將在4.3.5小節(jié)詳細介紹。圖4-2聚類圖4-2聚類-分類圖根據以上所述，本文所研究的基于半監(jiān)督的文本分類算法就是先對數據集進行聚類之后，然后在應用半監(jiān)督分類算法進行分類。如此可以很大的提高分類器的性能。4.3.3基于EM算法的聚類分析本章所研究的基于EM算法的聚類數據集是基于高斯混合模型的。故本節(jié)將分別介紹高斯混合模型和聚類EM算法。[32][33]（1）高斯混合模型假設有一系列觀測值由某混合分布產生，該分布又是由個成分構成，每一個成分都代表一個不同的類別(cluster)。假設觀測樣本，每個向量都是維的。表示是第類的密