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

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