文本分類中的特征提取和分類算法綜述

文本分類中的特征提取和分類算法綜述摘要：文本分類是信息檢索和過(guò)濾過(guò)程中的一項(xiàng)關(guān)鍵技術(shù)，其任務(wù)是對(duì)未知類別的文檔進(jìn)行自動(dòng)處理，判別它們所屬于的預(yù)定義類別集合中的類別。本文主要對(duì)文本分類中所涉及的特征選擇和分類算法進(jìn)行了論述，并通過(guò)實(shí)驗(yàn)的方法進(jìn)行了深入的研究。采用kNN和NaiveBayes分類算法對(duì)已有的經(jīng)典征選擇方法的性能作了測(cè)試，并將分類結(jié)果進(jìn)行對(duì)比，使用查全率、查準(zhǔn)率、F1值等多項(xiàng)評(píng)估指標(biāo)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行綜合性評(píng)價(jià)分析.最終，揭示特征選擇方法的選擇對(duì)分類速度及分類精度的影響。關(guān)鍵字：文本分類特征選擇分類算法AReviewForFeatureSelectionAndClassificationAlgorithmInTextCategorizationAbstract：Textcategorizationisakeytechnologyintheprocessofinformationretrievalandfiltering,whosetaskistoprocessautomaticallytheunknowncategoriesofdocumentsanddistinguishthelabelstheybelongtointhesetofpredefinedcategories.Thispapermainlydiscussthefeatureselectionandclassificationalgorithmintextcategorization,andmakedeepresearchviaexperiment.kNNandNativeBayesclassificationalgorithmhavebeeappliedtotesttheperformanceofclassicalfeaturedetectionmethods,andtheclassificationresultsbasedonclassicalfeaturedetectionmethodshavebeenmadeacomparison.Theresultshavebeenmadeacomprehensiveevaluationanalysisbyassessmentindicators,suchasprecision,recall,F1.Intheend,theinfluencefeatureselectionmethodshavemadeonclassificationspeedandaccuracyhavebeenrevealed.Keywords:TextcategorizationFeatureselectionClassificationalgorithm

前言互聯(lián)網(wǎng)技術(shù)的高速發(fā)展引起了信息量的爆炸式增長(zhǎng)，面對(duì)龐大的數(shù)據(jù)信息，如何在大規(guī)模的文本異構(gòu)信息中準(zhǔn)確、快速、全面地查找到個(gè)人所需的特定信息，已經(jīng)成為了一項(xiàng)具有非常重要意義的研究課題［1］。文本分類的主要功能就是對(duì)相關(guān)的文檔集合進(jìn)行類別的標(biāo)簽與分配，其主要依據(jù)是在文本訓(xùn)練過(guò)程中將那些已經(jīng)被提前分配合理的作為類別標(biāo)簽的訓(xùn)練文檔集和。作為自動(dòng)信息管理的核心技術(shù)，人工智能與信息檢索技術(shù)是文本自動(dòng)分類的兩大技術(shù)基礎(chǔ)，在組織和管理海量文本信息技術(shù)領(lǐng)域中文本分類是一種非常有效的技術(shù)手段［1］。所以，對(duì)文本自動(dòng)分類技術(shù)的深入研究有著非常重要的理論意義與實(shí)用價(jià)值。目前通常采用向量空間模型來(lái)描述文本向量⑵。然而，面對(duì)高維的文本特征，如果不進(jìn)行降維處理，則會(huì)造成“維度災(zāi)難”，從而大大影響分類效果。特征降維是文本分類過(guò)程中的一個(gè)重要環(huán)節(jié)。特征提取和特征抽取是特征降維技術(shù)的兩大類，相對(duì)于特征抽取方法，特征提取方法因其快速、簡(jiǎn)單、便捷的優(yōu)點(diǎn)，在文本分類領(lǐng)域中得到廣泛的應(yīng)用。選擇合適的文本表示模型、特征降維方法和分類器算法對(duì)文本分類的速度和精度有著至關(guān)重要的影響。本文主要采用NewsGroups語(yǔ)料庫(kù)中的20news-18828數(shù)據(jù)源，使用kNN和NativeBayes分類算法對(duì)驗(yàn)證幾種已有的經(jīng)典特征選擇方法，并將其分類結(jié)果進(jìn)行比較，揭示特征提取算法對(duì)分類性能的影響。1、幾種經(jīng)典的特征提取方法1.1文檔頻率(DF)文檔頻率是指在訓(xùn)練文檔集中某詞條出現(xiàn)過(guò)的文檔總數(shù)［3］。文檔頻率特征提取方法的基本思想是：首先根據(jù)具體情況設(shè)定最小和最大的文檔頻率閾值，接著計(jì)算每個(gè)特征詞的文檔頻率。如果該特征詞的文檔頻率大于已設(shè)定的最大文檔頻率閾值或小于最小的文檔頻率閾值，則刪除該特征詞，否則保留。一一，、nDF()=節(jié)(式1-1)其中，n^表示詞條t在文檔中出現(xiàn)的次數(shù)，N表示文本的總詞匯數(shù)。DF是一種最簡(jiǎn)單的詞約簡(jiǎn)技術(shù)，常用于大規(guī)模的語(yǔ)料特征選擇中。但其缺點(diǎn)是如果某一稀有詞條主要出現(xiàn)在某類訓(xùn)練集中，能夠很好地反應(yīng)該類別的特征，但因低于某個(gè)設(shè)定的閾值而直接濾除掉，因此就可能影響文本分類器的分類精度。1.2信息增益(IG)在文本分類系統(tǒng)中信息增益算法通過(guò)統(tǒng)計(jì)某一個(gè)特征詞t在文本類別中是否出現(xiàn)的文檔頻數(shù)來(lái)該算法考慮了特征t在文檔中出現(xiàn)前后的信息熵之差-p(C11)logp(C11)計(jì)算該特征項(xiàng)W于文本類別c-的信息增益。公式定義O=iLmp(C)logP(C)+該算法考慮了特征t在文檔中出現(xiàn)前后的信息熵之差-p(C11)logp(C11)+p(t)S-p(C11+p(t)S-p(C11)logp(C11)(式1-2)其中，m表示語(yǔ)料庫(kù)中文檔類別總數(shù)；P(C)表示C類文檔在語(yǔ)料庫(kù)中出現(xiàn)的概率；p(t)表示包含特征t的文檔的概率；p(t)表示不包含特征t的文檔的概率；p(C.|t)表示包含特征t的文檔屬于類別C.的概率；P(C)f)表示包含特征t的文檔不屬于類別C的概率。信息增益法的缺點(diǎn)是，它考慮了特征未發(fā)生的情況，盡管特征不出現(xiàn)的情況也可能對(duì)文本分類的判別有積極作用，但這種積極作用往往要遠(yuǎn)小于考慮這種情況時(shí)對(duì)文本分類帶來(lái)的干擾。1.3互信息(MI)互信息衡量的是某個(gè)特征詞和特征類別之間的統(tǒng)計(jì)相關(guān)性。因此，某個(gè)特征詞t和某個(gè)文本類別匕互信息定義度量?jī)蓚€(gè)給定對(duì)象之間的相關(guān)性，在不良信息過(guò)濾問(wèn)題中用以度量特征項(xiàng)對(duì)于文本主題的區(qū)觥t°C特征回^和類別珞散互信息公式定義如下［4］:"()"(「(式1-3)TOC\o"1-5"\h\z其中，m為類別數(shù)；p(^)表示類別C的概率；p(t,C)表示包含特征t且屬于類別C的概率；p(t)表示特征t的概率；pC表示屬于類'別C的概率。' '互信息值較高的特征詞通常在某個(gè)類別匕中出現(xiàn)的概率高，而在其他文本類別中出現(xiàn)的概率低，也就更有可能被選作為文本類別c的特征。在m個(gè)類別的文本訓(xùn)練集上特征項(xiàng)t的互信息值公式定義如下［5］： ZMI=p(ci)^mMI(t,c「 (式1-4)i=11.4X2統(tǒng)計(jì)(CHI)X2統(tǒng)計(jì)用來(lái)衡量特征詞條t和類別C之間的統(tǒng)計(jì)相關(guān)性。假設(shè)特征t和類別C之間是符合一階自由度的X2分布，則特征詞的對(duì)于類cB的X2統(tǒng)計(jì)公式定義如下⑹： 'X2(t，以-(?+C)*(B+D)*(A+B)*(C+D)(式1-5)其中，A表示屬于C類且包含t的文檔頻數(shù)，B表示不屬于C類但是包含t的文檔頻數(shù)，C表示屬于C類但是不包含t的文檔頻數(shù)，D表示不屬于C類且不包含t的文檔頻數(shù)。對(duì)于多類問(wèn)題，分別計(jì)算t對(duì)于每個(gè)類別的卡方統(tǒng)計(jì)值，再用下面兩種公式計(jì)算特征t對(duì)于整個(gè)樣本的卡方統(tǒng)計(jì)值，分別進(jìn)行檢驗(yàn)：x2(t)=maxwx2(t,c) (式1-6)xHt)=￡p(C)x2(t,C)a^vg i ii=1(式1-7)其中，n為類別數(shù)，從原始特征空間中移除低于特定閾值的特征，保留高于該閾值的特征作為文檔表示的特征。當(dāng)特征詞t與文本類別,相互獨(dú)立時(shí)，X2(t,C「=0，此時(shí)特征t不含有任何與文本類別七有關(guān)的鑒別信息。反之，X2(t,ci)的值越大，t與c的統(tǒng)計(jì)相關(guān)性越強(qiáng)。但是通過(guò)X2統(tǒng)計(jì)的公式可看出，

該方法對(duì)低文檔頻率的特征項(xiàng)不靠譜，因其提高了在指定文本類別中出現(xiàn)的頻率較低但卻大量存在于其他類別的特征項(xiàng)在該文本類別中的權(quán)值。N1.5TF-IDF詞匯頻率：IDF=log其中)N表示文本的總詞匯數(shù)，N^表示詞w在文本中出現(xiàn)的次數(shù)，TFN表示包含詞W的文檔數(shù)，N表示包含詞W的文檔數(shù)，D表示語(yǔ)料庫(kù)中的總文檔數(shù)逆文檔頻竟：,d)=TF(t,d)其0中’目，IDF值越大'，該詞與文檔的相關(guān)性越低ATFIDF（t,d）針對(duì)（式1-TFIDF（t,d）針對(duì):/TFIDF（t,d）2V ij*i=1（式1-9）2、文本分類方法文本分類方法主要分為兩大類：基于規(guī)則的分類方法和基于統(tǒng)計(jì)的分類方法。其中基于規(guī)則的分類方法包括：決策樹、關(guān)聯(lián)規(guī)則和粗糙集等；基于統(tǒng)計(jì)的分類方法包括：K-最近鄰算法、樸素貝葉斯、支持向量機(jī)等算法。由于后者具有實(shí)現(xiàn)簡(jiǎn)單、分類性能良好的優(yōu)點(diǎn)，故而在文本自動(dòng)分類領(lǐng)域中應(yīng)用廣泛。2.1K-最近鄰算法K-最近鄰算法(kNN)，是一種基于向量空間模型的類比學(xué)習(xí)方法。因其簡(jiǎn)單、穩(wěn)定、有效的特點(diǎn)，被廣泛應(yīng)用于模式識(shí)別系統(tǒng)中。在計(jì)算文本相似度時(shí)，通常采用冤毒夾角余弦來(lái)度量。在空間模型中，通過(guò)計(jì)算兩個(gè)文本向量使用kNN在計(jì)算文本相似度時(shí)，通常采用冤毒夾角余弦來(lái)度量。在空間模型中，通過(guò)計(jì)算兩個(gè)文本向量之間夾角%j的余弦值)本表示兩個(gè)文檔滴和d；?之間的文本相似度，計(jì)算公式如下：" ，(XW2)*(XW2)\ ik jk（式2-1）TOC\o"1-5"\h\z'k=1 k=1（式2-1）其中，w^表示第i個(gè)文檔的第k個(gè)屬性值。當(dāng)兩個(gè)文本越相似時(shí)，sim(dj,dj)的值越大。通過(guò)上述計(jì)算公式，從預(yù)先確定好類別的文檔集合中選取前K個(gè)與待分類文檔最接近的樣本。對(duì)于待分類樣本的K個(gè)近鄰樣本，依次計(jì)算對(duì)每個(gè)類別的權(quán)重，計(jì)算公式如下：_ —> —>p(X,c)=zsim(x,d)y(d,c) (式2-2)\o"CurrentDocument"j iij—*djekNN

—?其中，頂表示待分類文檔的特征向量，y(d,c.)則表示文本類別屬性函數(shù)，若文檔d屬于類c，Ij I J則該函數(shù)值為1，否則為0.在文本分類中，K-最近鄰算法的主要過(guò)程是：在文本的訓(xùn)練階段，將文本訓(xùn)練集文檔分別表示成機(jī)器可識(shí)別操作的特征向量的形式；在文本分類階段，主要進(jìn)行文本的相似度計(jì)算和權(quán)重值排序。在分類中，K-最近鄰算法的時(shí)間復(fù)雜度與文本訓(xùn)練集合的文檔總數(shù)成正比，該算法的時(shí)間復(fù)雜度較高，更適用于文本訓(xùn)練集合規(guī)模較小的文本分類系統(tǒng)。2.2樸素貝葉斯算法樸素貝葉斯算法［7］可應(yīng)用到大規(guī)模文本集合中，具有方法簡(jiǎn)單、速度快、分類準(zhǔn)確率高等優(yōu)點(diǎn)。理論上，由于樸素貝葉斯算法所基于的假設(shè)太過(guò)于嚴(yán)格，故而其分類效果要普遍優(yōu)于其他分類算法，但是在實(shí)際應(yīng)用中并不能完全符合理論中的假設(shè)條件，則算法的準(zhǔn)確率會(huì)有一定程度的下降。在類別數(shù)目較多或者類別之間相關(guān)性較小的情況下，該模型的分類性能才能達(dá)到最佳。假設(shè)訓(xùn)練集中存在j個(gè)類別，類別集合表示為 C={c,c,...c}，文本特征詞集合表示為TOC\o"1-5"\h\z1 2jT={t,t，…,t}，各個(gè)文本特征對(duì)給定文本類別的影響是相互獨(dú)立的。那么，類別c的先驗(yàn)概率為：1 2j ip(c)=普，i=1,2,3,...,j (式2-3)其中，N表示屬于［類別的文本數(shù)目，N表示訓(xùn)練集的文本總數(shù)。設(shè)八表示文本特征集合中的第j個(gè)特征詞，p(t］ci)表示特征詞t.在所有屬于類別七的文檔集中出現(xiàn)的概率。則未知類別文本d屬于文本類別c的條件概率p(d|cJ為： '(式2-4)(式2-5)p(dlc)=p((t,t,...,t)1c)=rip(tlc)(式2-4)(式2-5)1 12j‘ i=1 j'根據(jù)貝葉斯定理，文本類別七的后驗(yàn)概率p(c\d)為：p(c|d)=四"'1 p(d)p(d)=寸p(c「p(d|c) (式2-6)i=1其中，p(d)表示d文本中所有特征詞在整個(gè)文本集合中出現(xiàn)的概率，為常數(shù)。因此，上式簡(jiǎn)化為：p(cild)=p(d|ci)p(c.) (式2-7)結(jié)合式2-4和2-7，可得p(cJd)=p(c，)rip(［匕) (式2-8)利用式2-8計(jì)算出的每個(gè)類別對(duì)于文檔d的后驗(yàn)概率值，然后將文檔d判定到概率值最大的那個(gè)文本類別中去。2.3支持向量機(jī)(SVM)支持向量機(jī)SVM算法是一種基于統(tǒng)計(jì)學(xué)理論的機(jī)器學(xué)習(xí)方法。該理論的基本思想是在準(zhǔn)確性和機(jī)器容量之間，對(duì)于給定的具有有限數(shù)量訓(xùn)練文本集的學(xué)習(xí)任務(wù)進(jìn)行折衷，以期望得到最佳的應(yīng)用性能⑻。該算法依據(jù)結(jié)構(gòu)風(fēng)險(xiǎn)最小化的原則，合理地選擇特征集合以及文本類別的判定函數(shù)，以保證通過(guò)有限實(shí)驗(yàn)條件下所得到的性能良好的文本分類器在對(duì)實(shí)際的分類中效果仍然良好，最終得到一個(gè)分類性能優(yōu)異并具有廣泛應(yīng)用性的學(xué)習(xí)機(jī)［9］。SVM算法是依據(jù)線性且可分情況下的最優(yōu)分類平面提出的，如圖所示：圖1：SVM中的分類平面如圖1所示，樣本集合能夠被平面H完全區(qū)分開，同時(shí)使直線H1、H2間的距離最大。其中，H1、H2是指在樣本集合中平行于H并且過(guò)離H最近的點(diǎn)的直線。支持向量機(jī)的基本思想是：首先將樣本輸入空間，通過(guò)某種非線性變換（通過(guò)定義適當(dāng)?shù)姆e實(shí)現(xiàn)）轉(zhuǎn)換到高維空間中去，并且在高維空間線性可分的情況下通過(guò)計(jì)算得到文本最優(yōu)分類平面［10］。通常，一個(gè)分類面只能對(duì)兩個(gè)類別進(jìn)行劃分，而對(duì)于多類別的文本分類問(wèn)題，就需要構(gòu)造多個(gè)超平面，將每一類別和其它的類別區(qū)分開來(lái)。同時(shí)，稀疏、高維的數(shù)據(jù)對(duì)SVM算法基本沒(méi)影響，因此能夠更好地體現(xiàn)文本數(shù)據(jù)的類別特征，相對(duì)于其它分類算法，SVM算法的文本分類準(zhǔn)確率較高。大量實(shí)驗(yàn)結(jié)果表明，支持向量機(jī)的文本分類效果明顯優(yōu)于其它的文本分類算法［11］。3、分類系統(tǒng)實(shí)現(xiàn)與結(jié)果分析3.1文本分類系統(tǒng)的整體設(shè)計(jì)本文使用Newsgroups18828數(shù)據(jù)源和java軟件設(shè)計(jì)平臺(tái)做分類分類實(shí)驗(yàn)，實(shí)現(xiàn)了文本訓(xùn)練與測(cè)試前的文本預(yù)處理等相關(guān)工作，通過(guò)利用java軟件編程，生成了樸素貝葉斯分類器和KNN分類器。在面對(duì)大規(guī)模的文本數(shù)據(jù)時(shí)，文本預(yù)處理后所得到的特征項(xiàng)數(shù)量巨大，給分類器的處理工作打來(lái)很大困難，因此需通過(guò)特征降維（即加入特征降維模塊）來(lái)降低分類器的處理的復(fù)雜度。整個(gè)系統(tǒng)分為四個(gè)模塊：文本預(yù)處理模塊、特征降維模塊、分類模塊及測(cè)試評(píng)估模塊，系統(tǒng)框架如圖2所示。具體的處理流程如下：（1） 將語(yǔ)料庫(kù)中的文本進(jìn)行預(yù)處理（去停頓詞、虛詞等處理）后，形成原始特征集和；（2） 在文本預(yù)處理模塊處理的結(jié)果的基礎(chǔ)上，循環(huán)讀取每個(gè)特征詞條，獲得其相關(guān)的詞頻以及文檔頻率等信息。然后統(tǒng)計(jì)特征提取方法所需要的參數(shù)，利用特征提取方法進(jìn)行計(jì)算，選出預(yù)定數(shù)目的最能代表各個(gè)類別特征的最優(yōu)特征集和，經(jīng)過(guò)權(quán)重計(jì)算，區(qū)別每個(gè)特征詞條所代表的文本類別信息大小并存儲(chǔ)；

把文檔表示為文本特征向量的表示形式，經(jīng)過(guò)分類模塊處理過(guò)程得到最終的文本分類結(jié)果；最后通過(guò)測(cè)試評(píng)估模塊，對(duì)文本分類結(jié)果進(jìn)行分析與比較，驗(yàn)證采用不同的特征提取方法進(jìn)行特征降維，對(duì)分類結(jié)果的影響。圖2：文本分類實(shí)驗(yàn)系統(tǒng)框圖3.2系統(tǒng)功能模塊設(shè)計(jì)3.2.1文本預(yù)處理模塊文本預(yù)處理模塊主要是利用分詞詞典對(duì)語(yǔ)篇容進(jìn)行詞的劃分，并去除標(biāo)點(diǎn)符號(hào)、各類虛詞、停頓詞等，得到一個(gè)詞的列表文件。詳細(xì)的處理過(guò)程參照文檔預(yù)處理類DataPreProcess.java。具體步驟如下：英文詞法分析，去除數(shù)字、連字符、標(biāo)點(diǎn)符號(hào)、特殊字符，所有大寫字母轉(zhuǎn)換成小寫，可以用正則表達(dá)式Stringres[]=line.split("「a-zA-Z]")；去停用詞，過(guò)濾對(duì)分類無(wú)價(jià)值的詞；詞根還原stemming,基于Porter算法3.2-2特征降維模塊文本預(yù)處理將語(yǔ)料庫(kù)中出現(xiàn)的絕大部分詞條作為文檔的特征項(xiàng)，形成特征向量空間，致使原始特征空間的維數(shù)非常大，勢(shì)必會(huì)增加機(jī)器學(xué)習(xí)的時(shí)間和空間的復(fù)雜度。因此，需通過(guò)特征降維實(shí)現(xiàn)對(duì)原始特征集的空間降維處理，以便提高文本分類系統(tǒng)的工作效率。該模塊將原始特征集合中的特征詞條按照特征提取方法進(jìn)行計(jì)算評(píng)價(jià)，最后選出前N個(gè)（預(yù)定數(shù)目）個(gè)權(quán)重值最大的特征詞構(gòu)成特征集合。在提取特征詞時(shí)，首先統(tǒng)計(jì)所有文檔中出現(xiàn)不重復(fù)的單詞的數(shù)目，通過(guò)兩種策略選取特征詞。策略一：可保留所有詞作為特征詞；策略二：選取出現(xiàn)次數(shù)大于等于4次的詞作為特征詞。統(tǒng)計(jì)結(jié)果如下：出現(xiàn)次數(shù)大于等于1次的詞有87554個(gè)出現(xiàn)次數(shù)大于等于2次的詞有49352個(gè)出現(xiàn)次數(shù)大于等于3次的詞有36456個(gè)出現(xiàn)次數(shù)大于等于4次的詞有30095個(gè)保留所有詞作為特征詞共計(jì)87554個(gè)選取出現(xiàn)次數(shù)大于等于4次的詞作為特征詞共計(jì)30095個(gè)3.2.3文本分類模塊（1） 樸素貝葉斯分類器樸素貝葉斯分類器有兩種模型：1） 多項(xiàng)式模型（以單詞為粒度）類條件概率P（tk|c）=（類c下單詞tk在各個(gè)文檔中出現(xiàn)過(guò)的次數(shù)之和+1）/（類c下單詞總數(shù)+訓(xùn)練樣本中不重復(fù)特征詞總數(shù)）先驗(yàn)概率P（c）=類c下的單詞總數(shù)/整個(gè)訓(xùn)練樣本的單詞總數(shù)2） 伯努利模型（以文件為粒度）類條件概率P（tk|c）=（類c下包含單詞4的文件數(shù)+1）/（類c下單詞總數(shù)+2）先驗(yàn)概率P（c）=類c下文件總數(shù)/整個(gè)訓(xùn)練樣本的文件總數(shù)由于多項(xiàng)式模型分類準(zhǔn)確率較高，故本文的樸素貝葉斯分類器采用多項(xiàng)式模型。（2） KNN分類器KNN算法描述：1） 文本向量化表示，由特征詞的TF*IDF值計(jì)算；2） 在新文本到達(dá)后，根據(jù)特征詞確定新文本的向量；3） 在訓(xùn)練文本集中選出與新文'本最相似的k個(gè)文本相似度用向量夾角余弦度量計(jì)算公式為：二W*Wsim（d,d）=cosa一 卜i =- ：（XW2）*（XW2）ik jk'k=1 k=1一般采用先設(shè)定一個(gè)初始k值，然后根據(jù)實(shí)驗(yàn)測(cè)試結(jié)果調(diào)整k值，本文中取k=20。在新文本的K個(gè)鄰居中，依次計(jì)算每類的權(quán)重，每類的權(quán)重等于K個(gè)鄰居中屬于該類的訓(xùn)練樣本與測(cè)試樣本的相似度之和；比較類的權(quán)重，將文本分到權(quán)重最大的那個(gè)類別中。3.2.4測(cè)試評(píng)估模塊樸素貝葉斯算法實(shí)現(xiàn)在java編程實(shí)現(xiàn)中，包含兩大類：貝葉斯算法類(NaiveBayesianClassifier.java)與測(cè)試集與訓(xùn)練集創(chuàng)建類(CreateTrainAndTestSample.java)。其中，分類器主類如圖3所示NaiveBayesianClassifier.javaE)--KSj.NuibycciuJZla.EEi￡iArC?no.itlt.String[]):vmid■:omput4Acaiji-acyCStrirag,Striiig):doutlecompi.Lt^Cat.ePrpb,Vector:-SIriFl^p任 Iloulild^doabl,MaptriIlcrnbl己>：l:Blglkairn^lMcomputerDonfusiorJila.trix(Map<5triile,3tring>,MapStriHg,3trirLg?.void日doFroceEs(StringString.,String): d日getCateWordsNwi(5triragj:MapString.Hcnjble&getCateWcirdsFrijb(Stringl:Map:Stririg,.Doablez日geHlapFrcirTiEeE-^iltFileEtring.):Map^tring,Striris?圖3：樸素貝葉斯分類器主類Java代碼注解：計(jì)算概率用到了BigDecimal類實(shí)現(xiàn)任意精度計(jì)算；用交叉驗(yàn)證法做十次分類實(shí)驗(yàn)，對(duì)準(zhǔn)確率取平均值；根據(jù)正確類目文件和分類結(jié)果文計(jì)算混淆矩陣并且輸出；Map<String,Double>cateWordsProbkey為"類目_單詞”,value為該類目下該單詞的出現(xiàn)次數(shù)，避免重復(fù)計(jì)算。樸素貝葉斯分類器分類結(jié)果(混淆矩陣)如圖4所示：D1 2 3 4r6 7 3 91D11 12ID1ijI：16 17JB19n61 n0 h j (i n0 o hn1 e o h 盟 1 a 0 o 時(shí)竣1 D 85 0 0 3 9 0 0 0 0 D D ￡ Z 1 3 D 1 ￡ 0 0.8^^(93877551D 1S3 2 3 19 0 0 0 3 1 9 E0 0 3 D (1 0 0 0.09(5(86868686860c U HU 1 f U ? U H U i! U U H d 1 U k H 土地；:岳理1約州J-D3i?5?[；(l000D93223D(]f0 0.G14^^33333333^1TOC\o"1-5"\h\zE (1 g 0 H j 芯 11 0 0 H (1 A E 0 1 j (1 R E 。 f?fU3033A53口0H0DA023U1E0 ^.巧？1藥8571曜8571? D ￡ 2 0 3 D 0 f 0 0 D 1 (1 0 J 3 J- 9 6 0 0.0u k u u j u u k u u u u u u u j k k u u.uD E 0 0 3 D 0 E 0 0 D Q 0 J a 1 1 f 0 0.0111n￡qH3n(Iq016(I￡0Hjn(1q1.011D90eaDI000D9990eaDI001.012D§1a32s0o0D196&29DDD003-673^939775518213Utaflduaau0UUk(5flduAau0』5蠣59典59595財(cái)U(kuò)D900a2a0a@DD1092aD30aeJ3B77551KMM1?15n￡q0jnaqo0liHce0K13qo土嚇眄眄將判616D90eaDI000D2900a872000J5fi^39560^3956117DD003Ds0o0DD0003DOil0o1.618Utaflduaau0UUk?2152tuo.e19590aDa0aDD912181A40193.3?158735873M57TltduuurduufJ-Ndiut!Ody^iciiCLdbi.fierii6thExpii:0.8仙叫肖歡4出19卜圖4:貝葉斯分類法分類結(jié)果的混淆矩陣表示(2)KNN算法實(shí)現(xiàn)在java編程實(shí)現(xiàn)中，包含兩大類：文檔向量計(jì)算類(ComputeWordsVector.java)和KNN算法實(shí)現(xiàn)類(KNNClassifier.java)。分別如圖5和圖6所示：-JComiuteVcircEVecto]'.java-ComputeYorcsVe:torrrainCStrin^ri:void3computelllF(String,SortedilapC-String,Double.>.):Sor11idJilaptring.,I)oulile>9computelFMultilDFGtrire,duuble,int.,SortedNap:Strang,Du^ble);,2ortedMap<String,DciubleQ:vold§c-：njTLllililords(Etririg,Eor+.e-I1!!ipCEtri .3〕 :Sortc-iMop-^StriDnull旦〉■pririlVordM：濁(S>n-tmdM迎<String：.,DoubLe>J:void圖5:文檔向量計(jì)算類Java代碼注解：計(jì)算IDF非常耗時(shí)，3萬(wàn)多個(gè)詞的屬性詞典初步估計(jì)需要25個(gè)小時(shí)；可以先嘗試所有詞的IDF都設(shè)成1的情況。-JjKNBClaEEifier.java|§??粉KBBlClaEsifier0政ByYalueComparator-■.conputsSlm(MapCString,Duiiljle},Map(String,Double.).):doulile—-jjllol'rE'Csee(String,String.,String.]:doubleDJ][CDnijiuteCate(String,Map<5tring,Houble>,Map<Etring,TreeFJap<String,Doable>>,Filetfriter.):Siring圖6:KNN分類器主類Java代碼注解：1） 用TreeMap<String,TreeMap<String,Double>>保存測(cè)試集和訓(xùn)練集；2） 注意要以"類目_文件名"作為每個(gè)文件的key，才能避免同名不同容的文件出現(xiàn)；3） 注意設(shè)置JM參數(shù)，否則會(huì)出現(xiàn)JAVAheap溢出錯(cuò)誤；4） 本程序用向量夾角余弦計(jì)算相似度。KNN算法的分類結(jié)果（混淆矩陣）如圖7所示：□1 23 4561二9ID1112i：16n】二19a62a:1:a:a:a:a:a:q::110.756097560975609611時(shí)D35gDaDaDa2￡DaD1D1D-7ma58B235￡g^llZD7Bl17:1-D1D-41D-1aD-Du7O^3^?E；Z6OSfi9566:]:11IS11aB01a：l052：l1：la：l10.609073394:495^11264D1■672■DaDi111■DaD■D.afl722S915i5626.5065D591Lis1-DaD-:11-DaD-D.T15510GDq：DSlfi326G:1jLLi21aD11211DaDa10r0r0r011r0r1r0r0r0r0.7777777777777773aDL-LDL-L:L-LDL-LDL-LLuD9:aDL:aDL:::DL:aDL:aDLL?[i10001z00:00.5971■la■|0■Ia■|0D.日我 日11DiDDiDDaD-ajaJa1a口泠心549皿迎的S12Da131is1DaDa7D210：la：i00.613953IBB：]7209313:i00000002001說(shuō)■|a■Ia■|10.926067-^1614DaD-1aD-DaDiDi91aJija0.957354736842105215B1DaDaDaD11aD2D391a：i?JD.0165137611：1601000i0i10201110ra■a0-601301601001301517DiD-1a1-DaDi11D日9jD.3913:a:a:a:a:a:a:a:a:a:alB013i100i00000001z000390-7037037037037037TheflEcarocvforEMMClassifierinbthExpis:0.62099162910^9582圖7:KNN分類器的分類結(jié)果表示3.3實(shí)驗(yàn)結(jié)果分析（1） 貝葉斯分類結(jié)果與分析由不同的特征提取策略，可得貝葉斯分類器結(jié)果如下：方法一：取所有詞作為特征詞，共87554個(gè)。做10次交叉驗(yàn)證實(shí)驗(yàn)，平均準(zhǔn)確率78.19%，用時(shí)23min，第6次實(shí)驗(yàn)準(zhǔn)確率超過(guò)80%；方法二：取出現(xiàn)次數(shù)大于等于4次的詞作為特征詞，共計(jì)30095個(gè)。做10次交叉驗(yàn)證實(shí)驗(yàn)，平均準(zhǔn)確率77.91%，用時(shí)22min，第6次實(shí)驗(yàn)準(zhǔn)確率超過(guò)80%。結(jié)論：樸素貝葉斯算法不必去除出現(xiàn)次數(shù)很低的詞，因?yàn)槌霈F(xiàn)次數(shù)很低的詞的IDF比較大，去除后分類準(zhǔn)確率下降，而計(jì)算時(shí)間并沒(méi)有顯著減少。（2） KNN分類結(jié)果與分析由于KNN分類算法的復(fù)雜度較高，若選取所有詞作為特征詞進(jìn)行分類實(shí)驗(yàn)，則所需時(shí)間較長(zhǎng)，為了適當(dāng)提高分類效率，考慮提取出現(xiàn)次數(shù)不小于4次的詞作為特征詞，分類結(jié)果如下：取出現(xiàn)次數(shù)大于等于4次的詞共計(jì)30095個(gè)作為特征詞：10次交叉驗(yàn)證實(shí)驗(yàn)平均準(zhǔn)確率78.19%，用時(shí)1h55min，其中有3次實(shí)驗(yàn)準(zhǔn)確率超過(guò)80%。（3） 兩種分類算法的性能比較在相同的硬件