結合文本信息量和聚類的文本裁剪算法

謝 攀，鄧珍榮,2，朱益立

(1.桂林電子科技大學 計算機與信息安全學院，廣西 桂林 541004；2.桂林電子科技大學 廣西可信軟件重點實驗室，廣西 桂林 541004)

0 引 言

KNN方法是基于實例的學習，在分類過程中存在著耗時的缺陷[1-4]，所以對訓練數據集進行優化操作以減小計算量就顯得很有意義。針對KNN文本分類的研究，很多學者也提出了自己的想法。周慶平等提出了一種基于聚類改進的KNN文本分類算法[5]，對訓練文聚類產生m個簇，利用每個簇的聚類中心構建新的訓練樣本空間與測試文本計算相似度，提高了時間效率，但是并沒考慮文本的重要性程度；茍和平等提出一種基于密度的KNN分類器樣本裁剪算法[6]，該算法雖然能提高分類的準確率和時間效率，但是樣本裁剪率過低；劉海峰等提出了一種基于位置的文本分類樣本裁剪及加權方法[7]，先通過聚類方法裁剪掉孤立點，再通過對樣本加權，提高了分類的準確率，但時間效率并沒有太大改進；譚學清等提出了一種基于類平均相似度的文本分類算法，在每個類中采用聚類中心作為待訓練文本空間[8]，提高了分類的時間效率和分類效果。

從目前的研究看，常用的解決辦法是通過一定的方式篩選出具有類別代表性的訓練文本，作為新的訓練樣本，或者通過聚類的思想找出每個類別的樣本中心，然后在此基礎上進行相似度計算[9-12]。

結合上述研究，本文提出一種算法。首先根據文本中的特征詞及特征詞出現的次數，利用本文提出的計算方法計算每條文本的權重，對每個類別中的文本重要性進行排序；再利用kmeans聚類算法將文本向量空間模型進行聚類，刪除掉每個類別中的噪聲樣本；然后結合已經計算的樣本的重要性序列，在每個類別中篩選出等量的文本，構建新的訓練樣本空間。后續的KNN操作，在新的訓練樣本空間上進行。

1 相關工作

1.1 文本預處理

文本預處理主要包括對文本正則化處理、中文分詞、停用詞操作。對于給定的文本，其中包含了許多特殊字符和無用的數字信息，需要通過正則化的方法去除掉這樣的內容。文本操作的核心是對特征詞的操作，因此必須把給定的文本序列劃分成一個一個獨立的詞。經中文分詞后，文本中存在著大量分類貢獻性小的詞，比如“的”、“好”等。這些詞不僅占用內存，而且會影響特征詞的選取，需要經過停用詞操作。

1.2 特征提取

文本分類的首要問題是從高維特征中選擇出具有代表性的特征，特征選擇的好壞直接影響到后續的分類。高維度會導致許多問題，首先，會使得維度之間獨立性變差，影響算法的分類準確性。其次，包含大量的噪聲特征，存在大量類別區分度低的特征。最后，嚴重影響計算量及分類效率。信息增益[13]和卡方檢驗是目前認定較好的特征選擇方法。信息增益是基于信息熵和條件熵的評估方法，是一種全局特征選取方法，同時考慮了特征詞出現和特征詞不出現的情況。IG計算公式為

(1)

1.3 向量空間模型

本文選擇向量空間模型(VSM)[14]表示文本。在VSM模型中，每個文本被表示成向量形式d=(w1∶v1,w2∶v2,…,wn∶vn),d表示一個文本向量，wi(i=1,2,…,n)代表特征詞，vi(i=1,2,…,n)為特征詞在文本中的權重，n為文本集中的特征詞個數。特征詞權重計算公式為TFIDF。公式表述如下

Wij=tfij*idfj=tfij*log(N/nj)

(2)

1.4 KNN分類

KNN核心思想是：對一個測試樣本，算出該樣本與訓練樣本的相似度，考慮其中相似度最近的K個樣本，根據多票表決制來判斷待分類樣本屬于哪個類別。相似度計算公式為

(3)

2 結合文本信息量和kmeans的文本裁剪

KNN在文本分類問題上，存在明顯缺點。當訓練樣本量大時，會花費大量時間在相似度計算上；當訓練文本中存在著類別區分度低或噪聲文本時，也會對分類造成干擾。針對KNN在文本分類上存在的問題，本文結合文本信息量和kmeans聚類對文本進行裁剪。然后在新的訓練文本空間上進行KNN分類。

2.1 文本信息量的引入

文本的信息量是指一篇文本包含的類別信息，對于一篇文本D的信息量由它所包含的特征詞來衡量，特征詞及特征詞的個數都將影響文本的信息量。特征詞對于分類的信息量用IG(式(1))計算出，但是同一個特征詞出現在不同類別中所攜帶的類別信息是不同的，引入了χ2來衡量特征詞對類別相關性程度。對各類別中的文本計算信息量，并按照信息量權重的大小進行排序，得出每個類別中文本的重要性序列。

(1)χ2統計量

χ2統計方法衡量特征詞與文檔類別c之間的相關程度，特征詞t對于類別c的χ2統計量計算公式為

(4)

在多分類中，分別計算特征詞t對于每個類別的χ2(t,ci)值。其中特征與各類別卡方最大值表示為：χmax2(t)=max{χ2(t,ci)}。

(2)聯合χ2和IG計算文本信息量

利用IG計算出特征詞對于訓練文本的全局信息量，χ2計算出特征詞對于各類別的局部信息量。一個特征詞包含的信息量IG表示，對于不同類別中出現的特征詞，用χ2值來加權。則文本信息量可以如下表述：

設文本訓練集D={d1,d2,…,dn}，其中n代表訓練文本的編號。訓練文本的類別為C={c1,c2,…,ck},k代表類別編號。根據詞袋模型統計每個特征詞在每個類中出現的次數，結合信息增益公式挑選出特征詞集合為T={t1,t2,…,tm}，m代表特征詞編號。特征詞的信息增益集合IG={ig1,ig2,…,igm}，每個特征詞在一篇文本中出現的次數N={Nt1,Nt2,…,Ntm}，根據卡方檢驗公式計算某個特征詞的類別傾向性可以表示為：χ2(i,j)={χ2(i,1),χ2(i,2),…,χ2(i,k)}， 則每一條文本文本信息量的公式為

(5)

2.2 VSM模型的kmeans聚類

在文本數據中一些文本的類別具有模糊性，一方面一個文本可能本身具有多個類別屬性，比如一個文本可能既包含體育的類別信息，又包含健康的類別信息；另一方面一些文本的書寫不規范，包含的類別信息不明顯。在TFIDF構建向量空間模型后，這樣的文本常處于各個類別的交叉區域、或者錯分到其它類別。這樣的類別表現能力差的文本將成為噪聲文本，對分類的準確性造成了負面的影響。

聚類把相似度高的樣本歸為一簇，簇內的相似度高，而簇間相似度低。經過聚類后，再在結合樣本的類別標簽，刪除掉簇內干擾性樣本，刪減掉一些交叉類別樣本，以獲得表現能力更強的樣本。

算法：訓練樣本空間kmeans聚類。

輸入：經TFIDF構造的向量空間模型，聚類個數K。

輸出：樣本所在的簇及刪減掉噪聲樣本的訓練樣本空間。

(1)對于訓練樣本集，隨機選擇K個向量作為質心，K為樣本的類別個數。

(2)計算非質心文本與K個質心的相似度，并把它們加入相似度最近的質心所在的簇中。

(3)每個文本都已經屬于其中的一個簇，然后根據每個質心所包含的文本的集合，重新計算得到新的質心。

(4)如果新計算的質心和上次質心之間的距離達到一個設置的閾值，算法終止，否則需要繼續迭代步驟(2)至步驟(4)。

(5)結合文本原本的類別信息，刪除掉每個簇中干擾性的文本，得到刪減噪聲樣本的訓練樣本空間。

2.3 結合文本信息量和聚類的樣本裁剪

算法的主要思想是通過計算文本的信息量，得到每個類別中文本的重要性序列。假設原始訓練樣本空間為W1(d),通過kmeans聚類，刪減掉每個類別中的噪聲文本，得到訓練樣本空間W2(d)。結合訓練樣本的重要性程度，在每個類別中篩選出等量的代表性訓練樣本，得到新的訓練樣本空間W3(d)。

假設文本訓練集為S，S有K個類別C1,C2,…，Ck，S的總文本數為n。具體流程如下。

輸入：訓練文本集合D={d1,d2,…,dn}， 特征詞集合T={t1,t2,…,tm}， 特征詞的詞袋模型。

(1)根據式(1)計算特征詞的信息增益值，按信息增益值大小篩選特征詞。

(2)根據式(4)計算特征詞對于不同類別的相關性程度。

(3)結合式(5)計算每個文本所包含的信息量。并對每個類別中的文本按照信息量進行排序。

(4)根據kmeans聚類刪除掉每個類別中的噪聲訓練樣本，得到新的訓練樣本集合W2(d)。

(5)根據信息量有序訓練樣本集合W1(d)和訓練樣本集合W2(d)，在每個類別中選擇出L個訓練樣本，組建成新的訓練樣本空間W3(d)，用作后續的操作。

3 改進KNN文本分類算法流程

經過改進后的KNN文本分類的流程如圖1所示。

圖1 樣本裁剪KNN分類流程

步驟1 對文本訓練集進行預處理操作、中文分詞、停用詞處理。

步驟2 構建詞袋模型，采用式(1)計算特征詞的信息增益值，選擇出特征詞集合。

步驟3 根據提取的特征詞構建VSM，采用式(2)計算。

步驟4 利用選取的特征詞及式(5)計算每個文本的信息量，并對每個類別中的文本包含的信息量進行排序，得出文本的重要性序列。

步驟5 對構建好的訓練文本向量空間模型進行聚類操作，刪除掉文本中的噪聲樣本。結合步驟4得出的重要性序列，在每個類別中篩選等量的樣本。

步驟6 對測試文本進行步驟1和步驟3的操作。

步驟7 采用式(3)計算相似度，并選出K個相似度最近的樣本。

步驟8 選出隸屬度最大的類別C，并將待分類的文本歸到該類別。

4 實驗及分析

4.1 實驗環境及實驗數據集

實驗設計如下：實驗環境為Ubuntu 16.04 64位操作系統、處理器為Intel E3-1241、內存為8G，python2.7編程完成實驗。本文所采用的實驗數據集是搜狗實驗室公開新聞語料庫。從中選取了訓練文本21 600篇，包括汽車、教育、財經、醫療、軍事、體育6個類別，每個類別3600篇；選取了測試文本2400篇，每個類別400篇。分類效果的評估指標采用準確率、召回率、和F1值，時間采用秒來計時。

4.2 實驗度量標準

準確率是指分類正確的條數與分類到該類別的條數的比值，數學公式表示為

(6)

召回率是指分類正確的條數與樣本中該類別的條數的比值，數學公式表示為

(7)

F1值綜合考慮準確率和召回率這兩個因素,公式表示為

(8)

在針對多分類時，評估分類方法的整體性能可以用宏平均準確率、宏平均查全率、宏平均F1值只來評估。計算公式為

(9)

(10)

(11)

在多次實驗對比中，當K值取30左右的時候分類效果最佳。

4.3 實驗對比

比較不同特征數詞目下，文本裁剪后的KNN分類、傳統KNN分類及隨機選取等量訓練文本KNN的實驗效果。比較選擇特征詞數為100、300、800、1000、1500、2000，2500，3000，3500，4000每個類裁剪后文本數為300時的宏平均準確率、宏平均召回率、宏平均F1值及相似度計算時間T。此時從21 600篇訓練文本中篩選出了1800篇代表性樣本。

由表1實驗結果看出，通過文中提出的訓練樣本裁剪方法，在不同特征詞數時都能大幅度的降低相似度計算的時間，時間降低10倍以上，而且各類評估指標并沒有明顯下降。實驗添加了一組隨機挑選等量訓練文本的對比實驗，雖然計算時間減少了，但分類結果會下降很多。實驗在特征詞數為3500左右時分類效果趨于最佳，隨著特征詞的增多，干擾的特征也會增加，時間復雜性變高，但分類的準確率趨于平穩。

表1 裁剪文檔為300不同特征數下實驗結果

從每個類別中分別篩選10、50、100、150、200、300、400、600個訓練樣本，選擇特征詞數3000，文檔裁剪的實驗結果如圖2和圖3所示。

圖2 不同裁剪數下實驗結果

圖3 不同裁剪度下運行時間

圖2結果表明，當每個類樣本保留200以上時，文本的分類準確率沒有明顯的下降。由圖3結果表明，當每個類的樣本保留的越多時，耗費的時間成倍增長。結合圖2和圖3的實驗結果表明，當每個類別樣本裁剪到200到300的時候分類的準確率在最高值附近，且計算相似度耗費的時間也可接受。

通過實驗得出，訓練文本中存在著分類無關樣本或噪聲樣本時，對分類的時間效率和分類的準確性都存在著干擾，通過本文提出的樣本裁剪方法不僅時間效率提高了，而且分類效果并沒有下降，本算法在訓練文本存在大量干擾樣本時會表現出更強的魯棒性。

5 結束語

本文對KNN文本分類進行了研究，鑒于KNN效率低的局限性，提出了結合文本信息量和聚類的文本裁剪算法。考慮到文本的信息量越大，則文本的重要性越高，賦予的權重也越大，越有可能被篩選為新的訓練樣本；同時考慮到訓練樣本空間中噪聲文本會干擾文本的選擇，結合聚類刪除掉噪聲的樣本。實驗結果表明，該樣本裁剪算法可篩選出分類性能強的樣本，減少計算開銷，但不可避免地帶來了樣本信息的損失，如何既高效又實效地進行樣本裁剪，是今后可研究的方向。

[1]Bijalwan V,Kumar V,Kumari P,et al.KNN based machine learning approach for text and document mining[J].International Journal of Database Theory and Application,2014,7(1):61-70.

[3]Jaderberg M,Simonyan K,Vedaldi A,et al.Reading text in the wild with convolutional neural networks[J].International Journal of Computer Vision,2016,116(1):1-20.

[4]Al-Salemi B,Ab Aziz M J,Noah S A.LDA-AdaBoost.MH:Accelerated AdaBoost.MH based on latent Dirichlet allocation for text categorization[J].Journal of Information Science,2015,41(1):27-40.

[5]ZHOU Qingping,TAN Changgeng,WANG Hongjun,et al.Improved KNN text classification algorithm based on clustering[J].Computer Application Research,2016,33(11):3374-3377(in Chinese).[周慶平,譚長庚,王宏君,等.基于聚類改進的KNN文本分類算法[J].計算機應用研究,2016,33(11):3374-3377.]

[6]GOU Heping,JING Yongxia,FENG Baiming,et al.Sample clipping algorithm based on density KNN classifier[J].Journal of Jiamusi University(Natural Science Edition),2013,31(2):242-244(in Chinese).[茍和平,景永霞,馮百明,等.基于密度的KNN分類器樣本裁剪算法[J].佳木斯大學學報(自然科學版),2013,31(2):242-244.]

[7]LIU Haifeng,LIU Shousheng,SU Zhan.Sample clipping and weighting method for text categorization based on location[J].Computer Engineering and Applications,2015,51(2):131-135(in Chinese).[劉海峰,劉守生,蘇展.基于位置的文本分類樣本剪裁及加權方法[J].計算機工程與應用,2015,51(2):131-135.]

[8]TAN Xueqing,ZHOU Tong,LUO Lin.A text classification algorithm based on class average similarity[J].Modern Library and Information Technology,2014,30(9):66-73(in Chinese).[譚學清,周通,羅琳.一種基于類平均相似度的文本分類算法[J].現代圖書情報技術,2014,30(9):66-73.]

[9]Bijalwan V,Kumar V,Kumari P,et al.KNN based machine learning approach for text and document mining[J].International Journal of Database Theory and Application,2014,7(1):61-70.

[10]Sharma M,Sarma K K.Dialectal Assamese vowel speech detection using acoustic phonetic features,KNN and RNN[C]//IEEE SPIN,2015:674-678.

[11]Liu H,Liu S S,Yao Z.An improved KNN text categorization algorithm based on the training samples distribution[J].Journal of The China Society for Scientific and Technical Information,2013,32(1):80-85.

[12]Dong T,Cheng W,Shang W.The research of kNN text categorization algorithm based on eager learning[C]//International Conference on Industrial Control and Electronics Engineering.IEEE,2012:1120-1123.

[13]Xu J,Jiang H.An improved information gain feature selection algorithm for SVM text classifier[C]//International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery,2015:273-276.

[14]Yu C Y,Shan J.Research on the web Chinese keywords extraction algorithm based on the improved TFIDF[J].Applied Mechanics & Materials,2015,727-728:915-919.