基于信息熵與詞長信息改進的TFIDF算法

金 燕，黃 杰

(浙江工業(yè)大學 信息工程學院，浙江 杭州 310023)

文本分類是自然語言處理、數(shù)據(jù)挖掘、搜索等領(lǐng)域中不可缺少的技術(shù)。文本分類中以提取到的特征詞與計算得到的特征詞權(quán)重來表達文本，表達后的文本給分類器訓練，訓練好的分類器可以將未知類別的文本識別為分類器已知類別的文本。在文本分類中，文本的表達方法有向量空間模型(VSM)、布爾模型[1]與概率模型。Salton等[2]提出的向量空間模型(VSM)是常用的文本表達方法,以文本中各個特征詞的權(quán)重為向量來表示文本。分類任務中常用KNN、樸素貝葉斯、SVM[3]、神經(jīng)網(wǎng)絡[4]等算法作分類器，神經(jīng)網(wǎng)絡不僅在圖像識別[5]任務中有著較好的識別結(jié)果，而且在文本分類中仍然有不錯的分類效果。

為了保證Web文本信息準確度高的特點，要求文本分類具有較高準確率的分類效果[6-7]，而分類準確率很大程度受到特征提取效果的影響。在文本分類中特征提取的方法有互信息[8]、卡方檢驗[9]、信息增益[10]與TFIDF[11]等。其中，Jones[12]提出的TFIDF算法是最常用的文本特征提取算法，TFIDF涉及到兩個概念：特征詞在文本中的頻率與特征詞的逆文本頻率。傳統(tǒng)的TFIDF算法存在著嚴重的缺陷，學者們針對傳統(tǒng)TFIDF算法的不足提出了改進。為了解決文本集偏斜帶來的問題，How等[13]提出了描述類別詞的方法，用特征詞在類別中的總頻數(shù)代替TFIDF的詞頻因子。針對傳統(tǒng)算法中沒有考慮到類別間的信息，徐冬冬等[14]引入描述類別因子，提出了包含類別信息的改進算法，提高了分類的平均準確度。周炎濤等[15]引入詞條信息熵，描述詞條在類別間的分布，解決了IDF忽略文本數(shù)據(jù)集中特征分散的問題。一些研究者將文本中特征詞的位置[16]、長度等因素加入到權(quán)重計算中，楊彬等[17]提出特征詞的長度不同能夠表達的信息也不相同，提出了一種結(jié)合詞長信息改進的TFIDF算法(TFIDFL)，相比于傳統(tǒng)的TFIDF算法，加入詞長信息后的算法在分類性能上有了提升。但是，文獻[17]中使用的方法不能準確地描述詞長特征，并且以上的改進方法都缺少了詞條在文本中的分布特征。筆者改進文獻[17]中描述詞長信息的因子并以文本內(nèi)詞條信息熵反映特征詞在文本中的分布特征來改進傳統(tǒng)的TFIDF算法，改進后的算法通過使用不同的分類器，使得文本分類在多個性能指標方面得到較大提升。

1 相關(guān)研究

1.1 TFIDF算法

TFIDF的核心思想是詞條t在該文本內(nèi)出現(xiàn)的頻率大，文本集中包含詞條t的文本數(shù)量少，則認為該詞條可以清楚地區(qū)分文本。TFIDF算法為

(1)

式中：tf為詞條t在文本中出現(xiàn)的頻數(shù)；n為包含詞條t的文本個數(shù)，加0.01是為了防止分母為0；N為總的文本數(shù)量。在文本長度不同的情況下，僅以詞頻來度量特征詞在文本內(nèi)的權(quán)重會出現(xiàn)偏差，為了避免詞頻對長文本的偏袒問題，將詞頻除以文本長度對詞頻進行規(guī)范化，得到規(guī)范化后的計算式為

(2)

式中：m為詞條t在文本中出現(xiàn)的個數(shù)；s為文本中詞條的總數(shù)量。TFC[18]是最為廣泛使用的TFIDF算法，目前對TFIDF算法的研究都是基于TFC進行的，它是將式(2)中的算法進行了歸一化，歸一化后的計算式為

(3)

式中：t為文本中的詞條；d為文本；分母為歸一化因子。

1.2 TFIDF存在的問題

1) TFIDF中僅以詞頻TF與逆文檔頻率IDF為計算權(quán)重的因子，忽略了詞長信息，不同的詞長能夠表達的信息也不一樣，而傳統(tǒng)算法中缺少了這個重要的因子。實驗證明缺少詞長因子嚴重地影響了分類器的分類準確性。

2) 傳統(tǒng)的TFIDF算法中僅以詞頻來表達特征詞在文本中的權(quán)重是不準確的，它忽略了文本中特征詞的分布特征，導致了分類準確率低。實驗證明詞條信息熵可以準確地反映文本中特征詞的分布特征。

2 改進的TFIDF算法

2.1 信息熵

熵是熱力學中表達系統(tǒng)混亂程度的度量，香農(nóng)將熵引入信息論中來表示信源的不確定性，它是對一個隨機事件發(fā)生不確定性的度量[19]，熵越大表示不確定性越大。信息熵的計算式為

(4)

式中：G為系統(tǒng)的信息熵；pk為詞條的分布概率，分布越平均的詞條，其對應的信息熵也越大。周炎濤等[15]引入信息熵，描述詞條在類別間的分布，將詞條信息熵的倒數(shù)疊加到TFIDF算法中得到了TFIDFu算法，然而TFIDFu算法對分類性能的提升并不明顯。筆者以引入詞條信息熵來反映特征詞在文本內(nèi)的分布特征的方法改進TFIDF算法，給出文本中詞條信息熵的計算式為

(5)

式中：H(t)為文本內(nèi)的詞條信息熵；p(t)為詞條t在文本中的分布概率。加入詞條信息熵后的改進TFIDF算法為

(6)

通過實驗，HIDF算法與傳統(tǒng)的TFIDF算法相比，在分類的準確率、查全率以及F值上都有了較大的提升。使用相同的訓練集與測試集，在邏輯回歸分類器上，TFIDF算法的平均準確率為85.73%，改進算法HIDF的平均準確率達到92.02%，比TFIDF高出6.29%，表明引入信息熵的思想能夠有效地改進TFIDF算法的不足，提升文本分類的準確度。

2.2 詞長信息

傳統(tǒng)的TFIDF算法中并未考慮到詞長信息，它將所有長度不同的詞條都統(tǒng)一對待，算法損失了詞長信息這一重要的部分。葉雪梅等[20]也提到，詞條短的詞能夠包含的信息少，詞條長的詞能夠包含的信息多，詞長也是衡量特征詞權(quán)重的關(guān)鍵因素。實驗證明了加入詞長信息后的算法能夠提升文本分類的各項性能指標。筆者提出了衡量詞條長度信息的重要因子為

Lt=log(a×l+b)

(7)

式中：Lt為詞條t的詞長權(quán)重；l為詞條t的長度；a為控制詞長信息增長快慢的因子；b為偏置。經(jīng)過10組的調(diào)參實驗，最終將a確定為1.2，b確定為5，此時算法能夠達到較優(yōu)的效果。在式(3)的基礎上加入詞長信息后的算法計算式為

(8)

式中：m為詞條t在文本中的數(shù)量；s為文本詞條的總數(shù)量；N為文本總數(shù)；n為包含詞條t的文本數(shù)；d為文本。加入詞長因子Lt的TFIDFLT算法在邏輯回歸分類器上，平均準確率達到了89.42%，楊彬等[17]提出的算法在邏輯回歸分類器上，平均準確率達到了87.08%。實驗證明：TFIDFLT算法提出的描述詞長信息的方法更為合理，并彌補了TFIDF詞長信息缺陷的問題。

通過同時結(jié)合詞條信息熵與加入詞長因子，提出了一種改進的TFIDF算法，其計算式為

(9)

式中：p(t)為詞條t在文本中的分布概率；N為總的文本數(shù)量；n為包含詞條t的文本數(shù)量；l為詞條t的長度；d為文本。通過實驗驗證了式(9)算法優(yōu)于HIDF、TFIDFLT算法。

2.3 算法復雜度分析

對筆者的HIDFLT算法進行時間復雜度與空間復雜度分析，假設文本長度為M，文本總數(shù)為N。式(9)中HIDFLT算法由特征詞的信息熵H、詞長因子LT與逆文本頻率IDF組成。H與LT因子可以同時進行計算即H×LT，遍歷文本求得特征詞的頻率，根據(jù)式(5，7)求得H×LT，此時算法的時間復雜度為O(M×1)。求IDF時需對所有文本進行遍歷，同時判斷文本中是否包含所求特征詞，計算出包含所求特征詞的文本個數(shù)，最終求得IDF，遍歷所有文本的時間復雜度為O(N)，判斷文本中是否包含所求特征詞的時間復雜度為O(M)，故求IDF時的時間復雜度為O(MN)。HIDFLT算法的時間復雜度為O(M)+O(MN)。若所有文本中的詞都相同，則算法額外的空間復雜度為O(1)，若文本中的所有詞都不同，則算法額外的空間復雜度為O(MN)，HIDFLT算法的空間復雜度介于O(1)與O(MN)之間。傳統(tǒng)TFIIDF算法的時間復雜度與空間復雜度的分析過程與分析結(jié)果與HIDFLT算法相同，改進后的算法復雜度沒有增加，并對文本分類有更好的分類結(jié)果。

3 實 驗

3.1 實驗環(huán)境

實驗用電腦硬件配置為CPU為Intel i7-5500U、內(nèi)存為8 G，編譯環(huán)境為jupyter notebook,編譯語言python3.7,使用的分類器為python3.7下sklearn中的邏輯回歸、KNN和多項式樸素貝葉斯等分類器，分類器的參數(shù)設置為默認參數(shù)。實驗數(shù)據(jù)集選用了10 個類別分別的文本，分別為教育、家居、時尚、體育、財經(jīng)、科技、時政、游戲、房產(chǎn)和娛樂等，每個類別有400 個文本，總共4 000 個文本作為訓練數(shù)據(jù)集，測試集有10 000 個文本，分成10 個小測試集，每個測試集有1 000 個文本，測試集中每個類別有100 個文本。

3.2 實驗流程

文本分類的過程包括語料預處理、文本分詞、去停用詞、特征提取和分類器等訓練，如圖1所示。

圖1 文本分類流程圖

實驗流程如圖1所示，對訓練文本預處理，使用jieba分詞對文本分詞，分完詞后的文本消去停用詞，將一些無意義的詞、符號與表情等消去。用處理完的文本統(tǒng)計出特征詞表，按照特征詞表的順序，使用特征提取算法計算文本中特征詞的特征值。使用文本的各個特征值組成特征向量來表示文本，對文本向量歸一化，將訓練集中的所有文本向量合成特征矩陣，把特征矩陣輸入給分類器訓練。測試集使用訓練集中的特征詞表對測試集文本提取特征，最后將得到的特征矩陣輸入分類器，得到分類結(jié)果。

實驗縱向?qū)Ρ攘艘延械膫鹘y(tǒng)的TFIDF算法與筆者提出的改進算法TFIDFLT、HIDF和HIDFLT的分類性能，實驗結(jié)果證明了對傳統(tǒng)的TFIDF算法的改進能夠提升分類性能。橫向?qū)Ρ确矫妫瑢⒐P者提出的HIDFLT算法與已有的TFIDF、TFIDFL和TFIDFu算法進行來了對比實驗，結(jié)果證明了筆者提出的HIDFLT算法在邏輯回歸、KNN和樸素貝葉斯分類器上的分類性能相比其他算法有了較大的提升。

3.3 評價指標

評價文本分類性能的指標有準確率、查準率(precision)、查全率(recall)、F值[21]，準確率為分類正確的文本數(shù)除以總的文本數(shù)，文本分類結(jié)果指標如表1所示。

表1 分類結(jié)果指標

查準率為分類器正確地判斷為該類的文本數(shù)量與判斷為該類的文本總數(shù)的比值，體現(xiàn)了分類結(jié)果的準確性,其計算式為

precision=A/(A+B)

(10)

查全率是正確的判斷為該類的文本數(shù)與實際上該類的總文本數(shù)的比值，體現(xiàn)出了分類結(jié)果的完備性，其計算式為

recall=A/(A+C)

(11)

查準率與查全率是相互制衡的，而F值則是調(diào)和查準率與查全率的，文本分類中常用F值來衡量分類性能的好壞，其計算式為

F=2×precision×recall/(precision+recall)

(12)

4 實驗結(jié)果與分析

4.1 縱向?qū)Ρ葘嶒?/h3>

縱向?qū)Ρ葘嶒炇菍⒁延械膫鹘y(tǒng)的TFIDF算法與筆者提出的改進算法TFIDFLT、HIDF和HIDFLT的分類結(jié)果作對比，實驗使用了相同的環(huán)境與數(shù)據(jù)集，實驗結(jié)果得到10 組測試集的平均準確率、查全率以及F值，查準率如表2所示。

表2 縱向?qū)Ρ葘嶒灥牟闇事?/p>

觀察表2，針對傳統(tǒng)的TFIDF算法的改進算法TFIDFLT、HIDF和HIDFLT在邏輯回歸、KNN和樸素貝葉斯分類器上的查準率都比TFIDF高，加入詞長信息和引入詞條信息熵能夠提升分類結(jié)果的查準率，同時加入詞長因子與引入詞條信息熵的HIDFLT算法在多個分類器上的準確率都是最高的，證明HIDFLT算法能夠有效地提高分類的查準率。

圖2為縱向?qū)Ρ鹊姆诸悳蚀_率，對TFIDF算法逐一改進后，在不同的分類器上分類準確率都有提升。TFIDFLT在TFIDF算法上加入了詞長信息因子后，可以發(fā)現(xiàn)文本的分類準確率在邏輯回歸上有較明顯的提升，在KNN與樸素貝葉斯分類器也有略微的提升，證明了詞長信息是特征提取中不可缺少的重要因素。對比HIDF與TFIDF算法，在邏輯回歸與KNN分類器上HIDF的平均準確率有較為明顯的提升，在樸素貝葉斯上有略微的提升，結(jié)果證明了引入的詞條信息熵能夠準確地反映特征詞在文本中的分布特征。

圖2 縱向?qū)Ρ鹊姆诸悳蚀_率

縱向?qū)Ρ葘嶒灥牟槿嗜绫?所示，針對TFIDF缺陷改進的算法TFIDFLT、HIDF和HIDFLT的查全率全都比TFIDF算法的高。在TFIDF算法基礎上加入詞長因子與引入詞條信息熵能夠有效地提升分類結(jié)果的查全率。同時加入詞長因子與引入詞條信息熵的HIDFLT算法在多個分類器上的查全率都是最高的，證明了HIDFLT算法改進的有效性。

表3 縱向?qū)Ρ葘嶒灥牟槿?/p>

結(jié)合表4與圖2可以觀察到：引入詞條信息熵與詞長因子的HIDFLT算法的平均準確率與綜合性能F值都高于TFIDF、HIDF與TFIDFLT算法，實驗結(jié)果充分證明了引入詞條信息熵與詞長信息的思想能夠彌補傳統(tǒng)TFIDF算法的缺陷，提升算法的性能。

表4 縱向?qū)Ρ葘嶒灥腇值

4.2 橫向?qū)Ρ葘嶒?/h3>

使用TFIDF、TFIDFL、TFIDFu與HIDFLT等特征提取算法對10 組測試集進行多分類，分類的平均準確率、查全率與F值的結(jié)果如圖3所示。

圖3 橫向?qū)Ρ鹊姆诸悳蚀_率

觀察圖3，HIDFLT算法在多個分類器上的分類準確率都比其他的特征提取算法的分類準確率要高。在邏輯回歸分類器上，HIDFLT算法的分類準確率比TFIDF算法高了7.34%，比文獻[17]提出的TFIDFL算法高了5.99%，比文獻[15]提出的TFIDFu算法高了5.26%。在KNN分類器上，HIDFLT算法的分類準確率比TFIDF算法高了4.77%，比TFIDFL高了3.03%，比TFIDFu高了4.85%。在樸素貝葉斯分類器上，HIDFLT與對比的特征提取算法的分類準確率相差無幾，HIDFLT仍然能夠達到最高的92.58%。實驗結(jié)果表明：引入詞條信息熵與詞長信息的HIDFLT算法相比與其他改進的算法有著較優(yōu)的準確率。

表5為橫向?qū)Ρ葘嶒灥牟闇事剩P者改進的算法HIDFLT與現(xiàn)有的TFIDF、TFIDFL和TFIDFu算法在多個分類器上對比，HIDFLT算法的查準率是最高的，證明了同時引入詞條信息熵與加入詞長信息改進TFIDF算法較于其他已有算法有較優(yōu)的查準率。

表5 橫向?qū)Ρ葘嶒灥牟闇事?/p>

表6是橫向?qū)Ρ葘嶒灥牟槿?，觀察表6可知HIDFLT算法在多個分類器上的查全率都是最高的。在邏輯回歸分類器與KNN上HIDFLT算法的查全率明顯的高于其他的特征提取算法，在樸素貝葉斯分類器上的查全率，各特征提取算法沒有明顯的差別，HIDFLT算法的查全率仍然是最高的，HIDFLT算法對比其他特征提取算法的分類結(jié)果更加完備。文本分類中，常用F值來衡量分類的綜合性能，對比實驗的平均F值如表7所示。

表6 橫向?qū)Ρ葘嶒灥牟槿?/p>

表7 橫向?qū)Ρ葘嶒灥腇值

結(jié)合F值、查全率與準確率，可以發(fā)現(xiàn)HIDFLT算法在分類結(jié)果的各項性能指標上都比其他算法高。從縱向?qū)嶒炁c橫向?qū)嶒灥慕Y(jié)果看：HIDFLT算法不僅改進了TFIDF算法的缺陷，而且對比其他算法有著較優(yōu)的分類性能。

5 結(jié) 論

面臨大數(shù)據(jù)時代，不管在數(shù)據(jù)挖掘、自然語言處理還是推薦系統(tǒng)領(lǐng)域中，文本分類對于日常的工作與學習有著很大的幫助，而文本分類過程中特征提取算法對文本分類的結(jié)果有較大的影響，將筆者提出的HIDFLT算法在文本分類中與其他改進的算法進行了對比，分析了算法間的優(yōu)缺點并證明了該算法擁有較高的性能效果。自然語言處理領(lǐng)域中，不僅僅只有文本分類需要提取文本的特征信息，在情感分析中也需要對情感信息進行特征提取，接下來的工作將改進的算法應用于情感分析中并對其作出適合于情感分析的改變，對用戶的情感信息有較真實的反饋。在搜索與推薦領(lǐng)域中，特征提取也較大地影響著推薦的效果，性能較好的特征提取算法為用戶帶來較準確的推薦結(jié)果，為用戶帶來良好的體驗。TFIDF使用的領(lǐng)域較寬廣，對不同的落地場景作出最適合的改變，以提高最后使用的性能。