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

(1.桂林電子科技大學(xué) 計(jì)算機(jī)與信息安全學(xué)院，廣西 桂林 541004；2.桂林電子科技大學(xué) 廣西可信軟件重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004)

0 引 言

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

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

結(jié)合上述研究，本文提出一種算法。首先根據(jù)文本中的特征詞及特征詞出現(xiàn)的次數(shù)，利用本文提出的計(jì)算方法計(jì)算每條文本的權(quán)重，對(duì)每個(gè)類別中的文本重要性進(jìn)行排序；再利用kmeans聚類算法將文本向量空間模型進(jìn)行聚類，刪除掉每個(gè)類別中的噪聲樣本；然后結(jié)合已經(jīng)計(jì)算的樣本的重要性序列，在每個(gè)類別中篩選出等量的文本，構(gòu)建新的訓(xùn)練樣本空間。后續(xù)的KNN操作，在新的訓(xùn)練樣本空間上進(jìn)行。

1 相關(guān)工作

1.1 文本預(yù)處理

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

1.2 特征提取

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

(1)

1.3 向量空間模型

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

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

(2)

1.4 KNN分類

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

(3)

2 結(jié)合文本信息量和kmeans的文本裁剪

KNN在文本分類問題上，存在明顯缺點(diǎn)。當(dāng)訓(xùn)練樣本量大時(shí)，會(huì)花費(fèi)大量時(shí)間在相似度計(jì)算上；當(dāng)訓(xùn)練文本中存在著類別區(qū)分度低或噪聲文本時(shí)，也會(huì)對(duì)分類造成干擾。針對(duì)KNN在文本分類上存在的問題，本文結(jié)合文本信息量和kmeans聚類對(duì)文本進(jìn)行裁剪。然后在新的訓(xùn)練文本空間上進(jìn)行KNN分類。

2.1 文本信息量的引入

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

(1)χ2統(tǒng)計(jì)量

χ2統(tǒng)計(jì)方法衡量特征詞與文檔類別c之間的相關(guān)程度，特征詞t對(duì)于類別c的χ2統(tǒng)計(jì)量計(jì)算公式為

(4)

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

(2)聯(lián)合χ2和IG計(jì)算文本信息量

利用IG計(jì)算出特征詞對(duì)于訓(xùn)練文本的全局信息量，χ2計(jì)算出特征詞對(duì)于各類別的局部信息量。一個(gè)特征詞包含的信息量IG表示，對(duì)于不同類別中出現(xiàn)的特征詞，用χ2值來加權(quán)。則文本信息量可以如下表述：

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

(5)

2.2 VSM模型的kmeans聚類

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

聚類把相似度高的樣本歸為一簇，簇內(nèi)的相似度高，而簇間相似度低。經(jīng)過聚類后，再在結(jié)合樣本的類別標(biāo)簽，刪除掉簇內(nèi)干擾性樣本，刪減掉一些交叉類別樣本，以獲得表現(xiàn)能力更強(qiáng)的樣本。

算法：訓(xùn)練樣本空間kmeans聚類。

輸入：經(jīng)TFIDF構(gòu)造的向量空間模型，聚類個(gè)數(shù)K。

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

(1)對(duì)于訓(xùn)練樣本集，隨機(jī)選擇K個(gè)向量作為質(zhì)心，K為樣本的類別個(gè)數(shù)。

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

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

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

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

2.3 結(jié)合文本信息量和聚類的樣本裁剪

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

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

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

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

(2)根據(jù)式(4)計(jì)算特征詞對(duì)于不同類別的相關(guān)性程度。

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

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

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

3 改進(jìn)KNN文本分類算法流程

經(jīng)過改進(jìn)后的KNN文本分類的流程如圖1所示。

圖1 樣本裁剪KNN分類流程

步驟1 對(duì)文本訓(xùn)練集進(jìn)行預(yù)處理操作、中文分詞、停用詞處理。

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

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

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

步驟5 對(duì)構(gòu)建好的訓(xùn)練文本向量空間模型進(jìn)行聚類操作，刪除掉文本中的噪聲樣本。結(jié)合步驟4得出的重要性序列，在每個(gè)類別中篩選等量的樣本。

步驟6 對(duì)測(cè)試文本進(jìn)行步驟1和步驟3的操作。

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

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

4 實(shí)驗(yàn)及分析

4.1 實(shí)驗(yàn)環(huán)境及實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)設(shè)計(jì)如下：實(shí)驗(yàn)環(huán)境為Ubuntu 16.04 64位操作系統(tǒng)、處理器為Intel E3-1241、內(nèi)存為8G，python2.7編程完成實(shí)驗(yàn)。本文所采用的實(shí)驗(yàn)數(shù)據(jù)集是搜狗實(shí)驗(yàn)室公開新聞?wù)Z料庫。從中選取了訓(xùn)練文本21 600篇，包括汽車、教育、財(cái)經(jīng)、醫(yī)療、軍事、體育6個(gè)類別，每個(gè)類別3600篇；選取了測(cè)試文本2400篇，每個(gè)類別400篇。分類效果的評(píng)估指標(biāo)采用準(zhǔn)確率、召回率、和F1值，時(shí)間采用秒來計(jì)時(shí)。

4.2 實(shí)驗(yàn)度量標(biāo)準(zhǔn)

準(zhǔn)確率是指分類正確的條數(shù)與分類到該類別的條數(shù)的比值，數(shù)學(xué)公式表示為

(6)

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

(7)

F1值綜合考慮準(zhǔn)確率和召回率這兩個(gè)因素,公式表示為

(8)

在針對(duì)多分類時(shí)，評(píng)估分類方法的整體性能可以用宏平均準(zhǔn)確率、宏平均查全率、宏平均F1值只來評(píng)估。計(jì)算公式為

(9)

(10)

(11)

在多次實(shí)驗(yàn)對(duì)比中，當(dāng)K值取30左右的時(shí)候分類效果最佳。

4.3 實(shí)驗(yàn)對(duì)比

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

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

表1 裁剪文檔為300不同特征數(shù)下實(shí)驗(yàn)結(jié)果

從每個(gè)類別中分別篩選10、50、100、150、200、300、400、600個(gè)訓(xùn)練樣本，選擇特征詞數(shù)3000，文檔裁剪的實(shí)驗(yàn)結(jié)果如圖2和圖3所示。

圖2 不同裁剪數(shù)下實(shí)驗(yàn)結(jié)果

圖3 不同裁剪度下運(yùn)行時(shí)間

圖2結(jié)果表明，當(dāng)每個(gè)類樣本保留200以上時(shí)，文本的分類準(zhǔn)確率沒有明顯的下降。由圖3結(jié)果表明，當(dāng)每個(gè)類的樣本保留的越多時(shí)，耗費(fèi)的時(shí)間成倍增長(zhǎng)。結(jié)合圖2和圖3的實(shí)驗(yàn)結(jié)果表明，當(dāng)每個(gè)類別樣本裁剪到200到300的時(shí)候分類的準(zhǔn)確率在最高值附近，且計(jì)算相似度耗費(fèi)的時(shí)間也可接受。

通過實(shí)驗(yàn)得出，訓(xùn)練文本中存在著分類無關(guān)樣本或噪聲樣本時(shí)，對(duì)分類的時(shí)間效率和分類的準(zhǔn)確性都存在著干擾，通過本文提出的樣本裁剪方法不僅時(shí)間效率提高了，而且分類效果并沒有下降，本算法在訓(xùn)練文本存在大量干擾樣本時(shí)會(huì)表現(xiàn)出更強(qiáng)的魯棒性。

5 結(jié)束語

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

[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).[周慶平,譚長(zhǎng)庚,王宏君,等.基于聚類改進(jìn)的KNN文本分類算法[J].計(jì)算機(jī)應(yīng)用研究,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].佳木斯大學(xué)學(xué)報(bào)(自然科學(xué)版),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).[劉海峰,劉守生,蘇展.基于位置的文本分類樣本剪裁及加權(quán)方法[J].計(jì)算機(jī)工程與應(yīng)用,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).[譚學(xué)清,周通,羅琳.一種基于類平均相似度的文本分類算法[J].現(xiàn)代圖書情報(bào)技術(shù),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.