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

1、WORD文本分類中的特征提取和分類算法綜述摘要：文本分類是信息檢索和過濾過程中的一項關鍵技術，其任務是對未知類別的文檔進行自動處理，判別它們所屬于的預定義類別集合中的類別。本文主要對文本分類中所涉與的特征選擇和分類算法進行了論述，并通過實驗的方法進行了深入的研究。采用kNN和Naive Bayes分類算法對已有的經典征選擇方法的性能作了測試，并將分類結果進行對比，使用查全率、查準率、F1值等多項評估指標對實驗結果進行綜合性評價分析.最終，揭示特征選擇方法的選擇對分類速度與分類精度的影響。關鍵字：文本分類 特征選擇 分類算法A Review For Feature Selection And C

2、lassification Algorithm In Text CategorizationAbstract:Text categorization is a key technology in the process of information retrieval and filtering,whose task is to process automatically the unknown categories of documents and distinguish the labels they belong to in the set of predefined categorie

3、s. This paper mainly discuss the feature selection and classification algorithm in text categorization, and make deep research via experiment. kNN and Native Bayes classification algorithm have been applied to test the performance of classical feature detection methods, and the classification result

4、s based on classical feature detection methods have been made a comparison. The results have been made a comprehensive evaluation analysis by assessment indicators, such as precision, recall, F1. In the end, the influence feature selection methods have made on classification speed and accuracy have

5、been revealed.Keywords:Text categorization Feature selection Classification algorithm前言互聯(lián)網技術的高速發(fā)展引起了信息量的爆炸式增長，面對龐大的數(shù)據(jù)信息，如何在大規(guī)模的文本異構信息中準確、快速、全面地查找到個人所需的特定信息，已經成為了一項具有非常重要意義的研究課題1。文本分類的主要功能就是對相關的文檔集合進行類別的標簽與分配，其主要依據(jù)是在文本訓練過程中將那些已經被提前分配合理的作為類別標簽的訓練文檔集和。作為自動信息管理的核心技術，人工智能與信息檢索技術是文本自動分類的兩大技術基礎，在組織和管理海量文本信

6、息技術領域中文本分類是一種非常有效的技術手段1。所以，對文本自動分類技術的深入研究有著非常重要的理論意義與實用價值。目前通常采用向量空間模型來描述文本向量2。然而，面對高維的文本特征，如果不進行降維處理，則會造成“維度災難”，從而大大影響分類效果。特征降維是文本分類過程中的一個重要環(huán)節(jié)。特征提取和特征抽取是特征降維技術的兩大類，相對于特征抽取方法，特征提取方法因其快速、簡單、便捷的優(yōu)點，在文本分類領域中得到廣泛的應用。選擇合適的文本表示模型、特征降維方法和分類器算法對文本分類的速度和精度有著至關重要的影響。本文主要采用NewsGroups語料庫中的20news-18828數(shù)據(jù)源，使用kNN和N

7、ative Bayes分類算法對驗證幾種已有的經典特征選擇方法，并將其分類結果進行比較，揭示特征提取算法對分類性能的影響。1、 幾種經典的特征提取方法1.1 文檔頻率（DF）文檔頻率是指在訓練文檔集中某詞條出現(xiàn)過的文檔總數(shù)3。文檔頻率特征提取方法的基本思想是：首先根據(jù)具體情況設定最小和最大的文檔頻率閾值，接著計算每個特征詞的文檔頻率。如果該特征詞的文檔頻率大于已設定的最大文檔頻率閾值或小于最小的文檔頻率閾值，則刪除該特征詞，否則保留。 （式1-1）其中，表示詞條在文檔中出現(xiàn)的次數(shù)，表示文本的總詞匯數(shù)。是一種最簡單的詞約簡技術，常用于大規(guī)模的語料特征選擇中。但其缺點是如果某一稀有詞條主要出現(xiàn)在某

8、類訓練集中，能夠很好地反應該類別的特征，但因低于某個設定的閾值而直接濾除掉，因此就可能影響文本分類器的分類精度。1.2 信息增益（IG）在文本分類系統(tǒng)中，信息增益算法通過統(tǒng)計某一個特征詞在文本類別中是否出現(xiàn)的文檔頻數(shù)來計算該特征項對于文本類別的信息增益。該算法考慮了特征在文檔中出現(xiàn)前后的信息熵之差，公式定義為3： （式1-2）其中，表示語料庫中文檔類別總數(shù)；表示類文檔在語料庫中出現(xiàn)的概率；表示包含特征的文檔的概率；表示不包含特征的文檔的概率；表示包含特征的文檔屬于類別的概率；表示包含特征的文檔不屬于類別的概率。信息增益法的缺點是，它考慮了特征未發(fā)生的情況，盡管特征不出現(xiàn)的情況也可能對文本分類的

9、判別有積極作用，但這種積極作用往往要遠小于考慮這種情況時對文本分類帶來的干擾。1.3 互信息（MI）互信息衡量的是某個特征詞和特征類別之間的統(tǒng)計相關性。因此，某個特征詞和某個文本類別互信息定義度量兩個給定對象之間的相關性，在不良信息過濾問題中用以度量特征項對于文本主題的區(qū)分度。特征詞和類別的互信息公式定義如下4： （式1-3） 其中，為類別數(shù)；表示類別的概率；表示包含特征且屬于類別的概率；表示特征的概率；表示屬于類別的概率?；バ畔⒅递^高的特征詞通常在某個類別中出現(xiàn)的概率高，而在其他文本類別中出現(xiàn)的概率低，也就更有可能被選作為文本類別的特征。在個類別的文本訓練集上特征項的互信息值公式定義如下5：

10、 （式1-4）1.4統(tǒng)計（CHI）統(tǒng)計用來衡量特征詞條和類別之間的統(tǒng)計相關性。假設特征和類別之間是符合一階自由度的分布，則特征詞對于類別的統(tǒng)計公式定義如下6： （式1-5）其中，表示屬于類且包含的文檔頻數(shù)，表示不屬于類但是包含的文檔頻數(shù)，表示屬于類但是不包含的文檔頻數(shù)，表示不屬于類且不包含的文檔頻數(shù)。對于多類問題，分別計算對于每個類別的卡方統(tǒng)計值，再用下面兩種公式計算特征對于整個樣本的卡方統(tǒng)計值，分別進行檢驗： （式1-6） （式1-7）其中，為類別數(shù)，從原始特征空間中移除低于特定閾值的特征，保留高于該閾值的特征作為文檔表示的特征。當特征詞與文本類別相互獨立時，此時特征不含有任何與文本類別有關

11、的鑒別信息。反之，的值越大，與的統(tǒng)計相關性越強。但是通過統(tǒng)計的公式可看出，該方法對低文檔頻率的特征項不靠譜，因其提高了在指定文本類別中出現(xiàn)的頻率較低但卻大量存在于其他類別的特征項在該文本類別中的權值。1.5 TF-IDF詞匯頻率： ，其中，表示文本的總詞匯數(shù)，表示詞在文本中出現(xiàn)的次數(shù)，的值越大，詞與文本的相關性就越強；逆文檔頻率：其中，表示包含詞的文檔數(shù)，表示語料庫中的總文檔數(shù)目，值越大，該詞與文檔的相關性越低。 （式1-8）針對TFIDF算法的歸一化計算公式為： （式1-9）2、 文本分類方法文本分類方法主要分為兩大類：基于規(guī)則的分類方法和基于統(tǒng)計的分類方法。其中基于規(guī)則的分類方法包括：決策

12、樹、關聯(lián)規(guī)則和粗糙集等；基于統(tǒng)計的分類方法包括：K-最近鄰算法、樸素貝葉斯、支持向量機等算法。由于后者具有實現(xiàn)簡單、分類性能良好的優(yōu)點，故而在文本自動分類領域中應用廣泛。2.1 K-最近鄰算法K-最近鄰算法（kNN），是一種基于向量空間模型的類比學習方法。因其簡單、穩(wěn)定、有效的特點，被廣泛應用于模式識別系統(tǒng)中。使用kNN算法分類時，首先將待分類文檔通過特征權重計算表示成空間向量形式的特征集合；然后，根據(jù)相應的準則將特征向量與預先確定好類別的樣本權重向量進行相關的計算，得到前K個相似度較高的文本；最后，判定該文檔的文本類別屬性。在計算文本相似度時，通常采用向量夾角余弦來度量。在空間模型中，通過計

13、算兩個文本向量之間夾角的余弦值來表示兩個文檔和之間的文本相似度，計算公式如下： （式2-1）其中，表示第個文檔的第個屬性值。當兩個文本越相似時，的值越大。通過上述計算公式，從預先確定好類別的文檔集合中選取前K個與待分類文檔最接近的樣本。對于待分類樣本的K個近鄰樣本，依次計算對每個類別的權重，計算公式如下： （式2-2）其中，表示待分類文檔的特征向量，則表示文本類別屬性函數(shù)，若文檔屬于類，則該函數(shù)值為1，否則為0.在文本分類中，K-最近鄰算法的主要過程是：在文本的訓練階段，將文本訓練集文檔分別表示成機器可識別操作的特征向量的形式；在文本分類階段，主要進行文本的相似度計算和權重值排序。在分類中，K

14、-最近鄰算法的時間復雜度與文本訓練集合的文檔總數(shù)成正比，該算法的時間復雜度較高，更適用于文本訓練集合規(guī)模較小的文本分類系統(tǒng)。2.2 樸素貝葉斯算法樸素貝葉斯算法7可應用到大規(guī)模文本集合中，具有方法簡單、速度快、分類準確率高等優(yōu)點。理論上，由于樸素貝葉斯算法所基于的假設太過于嚴格，故而其分類效果要普遍優(yōu)于其他分類算法，但是在實際應用中并不能完全符合理論中的假設條件，則算法的準確率會有一定程度的下降。在類別數(shù)目較多或者類別之間相關性較小的情況下，該模型的分類性能才能達到最佳。假設訓練集中存在個類別，類別集合表示為，文本特征詞集合表示為，各個文本特征對給定文本類別的影響是相互獨立的。那么，類別的先驗

15、概率為： （式2-3）其中，表示屬于類別的文本數(shù)目，表示訓練集的文本總數(shù)。設表示文本特征集合中的第個特征詞，表示特征詞在所有屬于類別的文檔集中出現(xiàn)的概率。則未知類別文本屬于文本類別的條件概率為： （式2-4）根據(jù)貝葉斯定理，文本類別的后驗概率為： （式2-5） （式2-6）其中，表示文本中所有特征詞在整個文本集合中出現(xiàn)的概率，為常數(shù)。因此，上式簡化為： （式2-7）結合式2-4和2-7，可得 （式2-8）利用式2-8計算出的每個類別對于文檔的后驗概率值，然后將文檔判定到概率值最大的那個文本類別中去。2.3 支持向量機（SVM）支持向量機SVM算法是一種基于統(tǒng)計學理論的機器學習方法。該理論的基本

16、思想是在準確性和機器容量之間，對于給定的具有有限數(shù)量訓練文本集的學習任務進行折衷，以期望得到最佳的應用性能8。該算法依據(jù)結構風險最小化的原則，合理地選擇特征集合以與文本類別的判定函數(shù)，以保證通過有限實驗條件下所得到的性能良好的文本分類器在對實際的分類中效果仍然良好，最終得到一個分類性能優(yōu)異并具有廣泛應用性的學習機9。SVM算法是依據(jù)線性且可分情況下的最優(yōu)分類平面提出的，如圖所示：圖1 最優(yōu)分類超平面和支持向量圖1：SVM中的分類平面如圖1所示，樣本集合能夠被平面H完全區(qū)分開，同時使直線H1、H2間的距離最大。其中，H1、H2是指在樣本集合中平行于H并且過離H最近的點的直線。支持向量機的基本思想

17、是：首先將樣本輸入空間，通過某種非線性變換（通過定義適當?shù)姆e實現(xiàn)）轉換到高維空間中去，并且在高維空間線性可分的情況下通過計算得到文本最優(yōu)分類平面10。通常，一個分類面只能對兩個類別進行劃分，而對于多類別的文本分類問題，就需要構造多個超平面，將每一類別和其它的類別區(qū)分開來。同時，稀疏、高維的數(shù)據(jù)對SVM算法基本沒影響，因此能夠更好地體現(xiàn)文本數(shù)據(jù)的類別特征，相對于其它分類算法，SVM算法的文本分類準確率較高。大量實驗結果表明，支持向量機的文本分類效果明顯優(yōu)于其它的文本分類算法11。3、分類系統(tǒng)實現(xiàn)與結果分析3.1 文本分類系統(tǒng)的整體設計本文使用Newsgroups18828數(shù)據(jù)源和java軟件設計

18、平臺做分類分類實驗，實現(xiàn)了文本訓練與測試前的文本預處理等相關工作，通過利用java軟件編程，生成了樸素貝葉斯分類器和KNN分類器。在面對大規(guī)模的文本數(shù)據(jù)時，文本預處理后所得到的特征項數(shù)量巨大，給分類器的處理工作打來很大困難，因此需通過特征降維（即加入特征降維模塊）來降低分類器的處理的復雜度。整個系統(tǒng)分為四個模塊：文本預處理模塊、特征降維模塊、分類模塊與測試評估模塊，系統(tǒng)框架如圖2所示。具體的處理流程如下：（1） 將語料庫中的文本進行預處理（去停頓詞、虛詞等處理）后，形成原始特征集和；（2） 在文本預處理模塊處理的結果的基礎上，循環(huán)讀取每個特征詞條，獲得其相關的詞頻以與文檔頻率等信息。然后統(tǒng)計特

19、征提取方法所需要的參數(shù)，利用特征提取方法進行計算，選出預定數(shù)目的最能代表各個類別特征的最優(yōu)特征集和，經過權重計算，區(qū)別每個特征詞條所代表的文本類別信息大小并存儲；（3） 把文檔表示為文本特征向量的表示形式，經過分類模塊處理過程得到最終的文本分類結果；（4） 最后通過測試評估模塊，對文本分類結果進行分析與比較，驗證采用不同的特征提取方法進行特征降維，對分類結果的影響。 訓練文本集 文本預處理 構造分類器 測試文本集 特征提取 文本預處理 分類 建立特征模型文本向量化表示分類結果的分析 與評價 分類器圖2：文本分類實驗系統(tǒng)框圖3.2 系統(tǒng)功能模塊設計3.2.1 文本預處理模塊文本預處理模塊主要是利

20、用分詞詞典對語篇容進行詞的劃分，并去除標點符號、各類虛詞、停頓詞等，得到一個詞的列表文件。詳細的處理過程參照文檔預處理類DataPreProcess.java。具體步驟如下：1） 英文詞法分析，去除數(shù)字、連字符、標點符號、特殊字符，所有大寫字母轉換成小寫，可以用正則表達式 String res=line.split(“a-zA-Z”)；2） 去停用詞，過濾對分類無價值的詞；3） 詞根還原stemming,基于Porter算法3.22 特征降維模塊文本預處理將語料庫中出現(xiàn)的絕大部分詞條作為文檔的特征項，形成特征向量空間，致使原始特征空間的維數(shù)非常大，勢必會增加機器學習的時間和空間的復雜度。因此，

21、需通過特征降維實現(xiàn)對原始特征集的空間降維處理，以便提高文本分類系統(tǒng)的工作效率。該模塊將原始特征集合中的特征詞條按照特征提取方法進行計算評價，最后選出前N個（預定數(shù)目）個權重值最大的特征詞構成特征集合。在提取特征詞時，首先統(tǒng)計所有文檔中出現(xiàn)不重復的單詞的數(shù)目，通過兩種策略選取特征詞。策略一：可保留所有詞作為特征詞；策略二：選取出現(xiàn)次數(shù)大于等于4次的詞作為特征詞。統(tǒng)計結果如下： 出現(xiàn)次數(shù)大于等于1次的詞有87554個 出現(xiàn)次數(shù)大于等于2次的詞有49352個 出現(xiàn)次數(shù)大于等于3次的詞有36456個 出現(xiàn)次數(shù)大于等于4次的詞有30095個保留所有詞作為特征詞 共計87554個選取出現(xiàn)次數(shù)大于等于4次的

22、詞作為特征詞共計30095個3.2.3 文本分類模塊（1）樸素貝葉斯分類器樸素貝葉斯分類器有兩種模型 ：1） 多項式模型（以單詞為粒度）類條件概率P(tk|c)=(類c下單詞tk在各個文檔中出現(xiàn)過的次數(shù)之和+1)/ （類c下單詞總數(shù)+訓練樣本中不重復特征詞總數(shù)）先驗概率P(c)=類c下的單詞總數(shù)/整個訓練樣本的單詞總數(shù) 2） 伯努利模型（以文件為粒度）類條件概率P(tk|c)=（類c下包含單詞tk的文件數(shù)+1）/(類c下單詞總數(shù)+2)先驗概率P(c)=類c下文件總數(shù)/整個訓練樣本的文件總數(shù) 由于多項式模型分類準確率較高，故本文的樸素貝葉斯分類器采用多項式模型。（2）KNN分類器KNN算法描述：

23、1） 文本向量化表示，由特征詞的TF*IDF值計算；2） 在新文本到達后，根據(jù)特征詞確定新文本的向量；3） 在訓練文本集中選出與新文本最相似的k個文本，相似度用向量夾角余弦度量，計算公式為：一般采用先設定一個初始k值，然后根據(jù)實驗測試結果調整k值，本文中取k=20。4） 在新文本的 K 個鄰居中，依次計算每類的權重，每類的權重等于K個鄰居中屬于該類的訓練樣本與測試樣本的相似度之和；5） 比較類的權重，將文本分到權重最大的那個類別中。3.2.4 測試評估模塊（1）樸素貝葉斯算法實現(xiàn)在java編程實現(xiàn)中，包含兩大類：貝葉斯算法類（NaiveBayesianClassifier.java）與測試集與

24、訓練集創(chuàng)建類（CreateTrainAndTestSample.java）。其中，分類器主類如圖3所示圖3：樸素貝葉斯分類器主類Java代碼注解：1）計算概率用到了BigDecimal類實現(xiàn)任意精度計算；2）用交叉驗證法做十次分類實驗，對準確率取平均值；3）根據(jù)正確類目文件和分類結果文計算混淆矩陣并且輸出；4）Map cateWordsProb key為“類目_單詞”, value為該類目下該單詞的出現(xiàn)次數(shù)，避免重復計算。樸素貝葉斯分類器分類結果（混淆矩陣）如圖4所示：圖4：貝葉斯分類法分類結果的混淆矩陣表示（2）KNN算法實現(xiàn)在java編程實現(xiàn)中，包含兩大類：文檔向量計算類（ComputeW

25、ordsVector.java）和KNN算法實現(xiàn)類（KNNClassifier.java）。分別如圖5和圖6所示：圖5：文檔向量計算類Java代碼注解：1）計算IDF非常耗時，3萬多個詞的屬性詞典初步估計需要25個小時；2）可以先嘗試所有詞的IDF都設成1的情況。圖6：KNN分類器主類Java代碼注解：1）用TreeMapString,TreeMap保存測試集和訓練集；2）注意要以類目_文件名作為每個文件的key，才能避免同名不同容的文件出現(xiàn)；3）注意設置JM參數(shù)，否則會出現(xiàn)JAVA heap溢出錯誤；4）本程序用向量夾角余弦計算相似度。 KNN算法的分類結果（混淆矩陣）如圖7所示：圖7：KN

26、N分類器的分類結果表示3.3 實驗結果分析（1）貝葉斯分類結果與分析由不同的特征提取策略，可得貝葉斯分類器結果如下：方法一：取所有詞作為特征詞，共87554個。做10次交叉驗證實驗，平均準確率78.19%，用時23min，第6次實驗準確率超過80%；方法二：取出現(xiàn)次數(shù)大于等于4次的詞作為特征詞，共計30095個。做 10次交叉驗證實驗，平均準確率77.91%，用時22min，第6次實驗準確率超過80% 。結論：樸素貝葉斯算法不必去除出現(xiàn)次數(shù)很低的詞，因為出現(xiàn)次數(shù)很低的詞的IDF比較大，去除后分類準確率下降，而計算時間并沒有顯著減少。（2）KNN分類結果與分析由于KNN分類算法的復雜度較高，若選

27、取所有詞作為特征詞進行分類實驗，則所需時間較長，為了適當提高分類效率，考慮提取出現(xiàn)次數(shù)不小于4次的詞作為特征詞，分類結果如下：取出現(xiàn)次數(shù)大于等于4次的詞共計30095個作為特征詞： 10次交叉驗證實驗平均準確率78.19%，用時1h55min，其中有3次實驗準確率超過80%。（3）兩種分類算法的性能比較在一樣的硬件環(huán)境下，貝葉斯分類算法和KNN分類算法經比較，可知：在分類準確率方面，KNN算法更優(yōu)；在分類速度方面，樸素貝葉斯算法更優(yōu)。4、結論本文首先對文本分類的相關技術做了詳細的介紹，然后針對文本分類系統(tǒng)中的特征提取過程和算法進行了進一步的研究與探討。對特征降維模塊中常用的特征提取方法，如文檔頻率（DF）、信息增益（IG）、互信息（MI）、分布、TF-IDF，進行了系統(tǒng)的理論概述；對常用的分類算法（如樸素貝葉斯算法、KNN算法和支持向量(SVM)）的原理進行了詳細的描述。最后通過采用Newsgroups18828數(shù)據(jù)源以與java軟件環(huán)境搭建文本自動分類的實驗平臺，證明了文檔頻率（DF）和TF-IDF特征提取方法的有效性，并對樸素貝葉斯分類算法和KNN分類算法的實驗結果進行比較，得出結論：在分類準確率方面，KNN算法更優(yōu)；在分類速度方面，樸素貝葉斯算法更優(yōu)。本文存在的不足之處是并未驗證