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

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