基于類別特征改進的KNN短文本分類算法*

黃賢英,熊李媛,劉英濤,李沁東

(重慶理工大學計算機科學與工程學院，重慶 400054)

1 引言

K-最近鄰KNN(K-Nearest Neighbor)分類[1]作為一種經典的分類方法，由于其直接利用樣本間的相似關系，有效地減少了類別特征選取不當對分類準確率的影響；同時，KNN分類的樣本相似度拆分處理方式，使得KNN分類算法更利于大數據的并行化處理，而且其在不平衡數據集上也表現有良好的分類性能，更適用于現實的文本分類情況。但是，KNN分類在找K最近鄰的過程中，要與整個訓練空間的每個樣本進行相似度的計算，KNN分類的效率會隨著訓練空間的增大而大幅度下降。同時，文本分類算法在進行分類時存在待分類文本中關鍵詞稀疏、難以充分表征文本特性的問題[2]，在短文本中關鍵詞特征更加稀疏，同時存在樣本高度不均衡等特點[3]。KNN文本分類算法通過各種輔助方式擴展測試文本來提高短文本分類的準確性，適用到短文本分類，增加了KNN分類算法相似度計算的時間復雜度，使得在短文本分類方面，KNN分類算法運行效率進一步下降。

目前針對KNN分類器效率提升主要是有兩種方法。一種是通過降維來降低相似度計算復雜性，文獻[4]依據概念進行特征選取,降低特征空間維數,提高KNN分類效率；文獻[5]通過優化特征和分類器的結合，提升了KNN分類算法的性能；文獻[6]通過自編碼網絡重構文本得到流形映射，提取短文本的流形特征，提升分類效果；文獻[7]提出基于最大邊緣相關的特征選擇方法減少大量的冗余特征，提升分類效率；文獻[8]運用熵特征變換指標設計相互類別差異量的相似度計算，來降低特征參數，提高KNN算法效率。另一種是通過樣本間關聯縮減訓練空間，文獻[9]利用擴展能力GC(Generalization Capability)算法使用案例維護學習減少訓練空間，從而提高近鄰檢索效率；文獻[10,11]利用粗糙集上下近似概念，對訓練樣本進行核心和邊界區域劃分，減少分類代價，以提高KNN分類效率；文獻[12,13]利用聚類方法對訓練集進行裁剪，解決傳統KNN算法在訓練集過大時速度慢的問題。但是，這些都是針對長文本分類的效率提升，針對短文本分類算法效率優化的文獻較少。

結合不同算法的特點，本文采用卡方提取的方法在每個類別中提取各個類別的類別特征詞項，利用類別特征詞項結合hownet詞典對訓練空間進行二次拆分，將與類別特征詞項相似的樣本歸到一個子集中，并以類別特征詞項定義這個子集。這樣，就將整個訓練空間的每個類別拆分成為更小的訓練子集。然后，根據測試數據的關鍵詞項從拆分后的訓練空間中，提取與測試數據相關的訓練子集重構測試數據的訓練集，依據KNN算法判定測試數據類別。通過這種方法來降低基于語義的KNN短文本分類算法在短文本相似度計算時的訓練空間大小，提高KNN分類在短文本分類上的性能。

2 相關工作

2.1 卡方統計

依據卡方統計量的卡方提取是一種最常用的文本特征詞項選擇方法，通過計算類別ci和詞項wj的相互獨立性來表示類別ci與詞項wj的相關程度?？ǚ街档挠嬎愎饺缦拢?/p>

(1)

其中，A表示在類別ci中包含詞項wj的樣本數，B表示不在類別ci中但包含詞項wj的樣本數，C表示在類別ci中不包含詞項wj的樣本數，D表示不在類別ci中且不包含詞項wj的樣本數。

卡方值越大，則類別ci和詞項wj的相關程度越大，詞項wj也就越能表示類別ci；反之，詞項wj越無法表示類別ci。傳統的卡方提取是在整個訓練空間中提取卡方值最大的前K個特征，但這種方法提取不平衡訓練空間時可能造成個別類別特征詞項過少，影響分類準確性。本文采用申紅等[14]的特征提取改進方法，在每個類別中分別提取在該類別中卡方值最大前K個作為該類別的類別特征，然后將所有類別的類別特征組合起來形成訓練空間的特征詞集。

在公式(1)中，(A+C)表示類別ci中的樣本總數，(B+D)表示訓練空間中除類別ci外的樣本總數，(A+B+C+D)表示訓練空間的樣本總數。在一個類別中，上述3個值是恒定的，所以公式(1)可簡化為：

(2)

2.2 基于hownet的語義相似度算法

基于hownet的短文本相似度算法主要是依賴hownet詞典來計算兩個短文本中關鍵詞的相似度值來計算短文本的相似程度。基于hownet詞典的詞語相似度計算主要是劉群的相似度算法[15]及一些基于此改進的相似度算法，文本選取李峰的中文詞語語義相似度算法[16]作為短文本語義相似度算法中基礎的詞語語義相似度算法，公式如下：

sim(w1,w2)=

(3)

其中，min(depthw1,depthw2)表示在知網中w1與w2的最小深度，distance(w1,w2)表示在知網中w1與w2的路徑長度，α是一個調節參數，表示詞語相似度為0.5時的路徑長度。

假設兩個短文本預處理后的結果為：

d1=(w11,w12,…,w1n)

d2=(w21,w22,…,w2m)

則d1和d2的語義相似度計算公式如下：

Sim(d1,d2) =

(4)

其中，mi= min(m,n),ma=max(m,n)，delta是一個調節參數，定義一個非空值與空值的相似度。

本文中依據李峰的中文詞語語義相似度算法定義文檔與詞語相似度值如下：

(5)

其中，wi文檔d中的第i關鍵詞。

3 基于特征語義的短文本分類算法

本文算法的重點在于利用類別特征詞項對訓練空間的拆分細化，根據測試數據構建近鄰計算訓練空間，以此來縮減訓練空間，提升算法效率，其流程圖如圖1所示。

Figure 1 Flow chart of the KNN short text classificactionalgorithm based on category feature words圖1 基于類別特征的KNN短文本分類算法流程圖

Step1數據預處理。對訓練數據和測試數據進行預處理，主要包括：無效字符剔除、文本分詞(采用ICTCLAS[17])、停用詞處理等，將文本數據用詞項向量表示，得到處理后的訓練空間和測試數據。

Step2類別特征詞項提取。采用公式(2)在訓練空間每個類別中提取相同數量的類別特征詞項。為避免在Step 3的拆分過程中產生太多同名集，并保證特征的有效性，此處對取得的所有類別特征詞項進行約減，去掉同時出現在3個及以上類別的類別特征詞項。

Step3訓練空間樣本拆分細化。對于每個類別的每個樣本，采用公式(5)的方法與該類別的類別特征詞項做相似度計算。若相似度值大于相似度拆分閾值thresholdsplit，則將該樣本加入對應的類別特征詞項樣本子集，若最后該樣本未加入任何類別特征詞集，則將其加入非類別特征集中。

為保證訓練空間細化后的類別特征詞項樣本子集的樣本數量的大小，防止大量樣本被分入非類別特征詞項樣本子集，相似度拆分閾值不能太大；但如果相似度拆分閾值太小，細化后的類別特征詞項樣本子集的樣本太多，訓練集的重構過程會很耗時，且樣本重復量太大，因此，本文定義相似度拆分閾值thresholdsplit為0.6，以類別Auto為例，類別Auto中包含“保養”“改裝”“奔馳”等等多個類別特征詞項樣本子集，原訓練空間類別Auto中有樣本di：“成品油/n，價/n，漲/vi，部分/n，城市/n，汽車/n，排隊/vn，加油/vi,”。按照式(5)計算文本“優惠/vn,元/m,部分/n,顏色/n,缺貨/vi,手動擋/nz,奔騰/vi,詳情/n,”與類別特征詞項“保養”的相似度值為0.65，因此將樣本di加入到類別特征詞項“保養”所對應的樣本子集中。

Step4訓練集重構。根據測試數據提取對應的訓練子集，將測試數據文本與所有類別的類別特征詞項采用公式(5)進行相似度計算，將相似度值大于提取相似度閾值的類別特征詞項所對應的類別特征詞項樣本子集中的數據提取到該測試數據的訓練集。同時，對得到的訓練集合進行去重處理，去掉重復的訓練樣本。具體流程如圖2所示。

Figure 2 Flow chart of the training set recontruction圖2 訓練集重構流程圖

Step5KNN文本分類。應用重構后的訓練集使用KNN文本分類算法對測試文本進行分類處理，這里采用多數研究統計得到的傳統KNN分類算法的K優值，取K值為10。文本相似度的計算采用基于知網的短文本相似度算法，利用公式(4)的方法計算測試文本dtest與重構得到的訓練集中的每個樣本的短文本語義相似度值，并取與測試文本dtest相似度最大的前10個樣本作為K近鄰集。

Step6判定類別。根據得到的相似度值最大的前10個樣本的歸屬類別判斷測試數據所屬的類別。分類類別中對應前10個樣本數目最大的即為測試數據的歸屬類別，若有多個最大，則取其中相似度和值最大的為測試數據的歸屬類別。

4 實驗結果與分析

4.1 實驗數據

實驗選取從數據堂下載的搜狗新聞語料庫[18]，以其中的新聞標題作為實驗語料數據源，從中提取出可確定類別的數據，剔除類別中數據條數小于10條的類別及數據。對于剩下的數據，對每條數據只提取其中的標題及所屬類別。對提取得到的數據按照9∶1的比例提取訓練集數據和測試集數據，并進行標題去重處理。

4.2 類別特征數量確定

類別特征數量的大小對本文算法的性能有較大影響，特征詞項個數太少，訓練集拆分程度過少，對效率的提升效果太弱；反之，若特征詞項個數太多，則訓練集合重構過程耗時太長，影響分類效率。

本文選取測試文本數量為100，對選取不同數目的類別特征詞項時的KNN短文本分類算法進行實驗。

圖3是在不同特征詞項數量下對100條測試文本進行KNN短文本分類的平均運行時間。從圖3中可以看出，類別特征詞項數量小于400時，改進的KNN短文本分類算法的測試文本的平均運行時間隨類別特征詞項數量的增加而減少。這是由于此時類別特征詞項數量較小，訓練空間樣本重新拆分時根據類別特征詞項數量拆分得到的樣本數量少，拆分后每個類別內保留的樣本數量過少，訓練空間中的大部分樣本被分入非類別特征集。一部分測試文本重構后的訓練集中樣本數量少于100，要加入非類別特征集中的樣本，測試文本重構后的訓練集較原訓練空間樣本數量減小有限，加上訓練集重構過程的耗時，使得測試文本的平均運行時間較長。隨著類別特征詞項數量的增大，拆分后每個類別內保留的樣本數量也在逐漸增加，非類別特征集的樣本數量也會隨之減少，重構后的訓練集中樣本數量小于100的測試文本數量也逐步減小，無需非類別特征集的樣本的測試文本增多，測試文本的重構訓練集的樣本數量得到有效減少，測試文本的平均運行時間越來越短。

Figure 3 Running time of the algorithm under different numbers of feature words圖3 不同特征詞項數目下算法的運行時間

當類別特征詞項數量大于400后，改進的KNN短文本分類算法的測試文本的平均運行時間隨類別特征詞項數量的增加而增加。根據類別特征詞項數量拆分后的訓練空間的樣本子集數量已經足夠，基本上所有測試文本在訓練集重構時，無需非類別特征詞項樣本子集中的樣本，此時測試文本的訓練集重構過程隨類別特征詞項數量的增加，添加的類別特征詞項所對應的類別特征詞項樣本子集就越多，重構后的訓練集樣本數量越來越多，測試文本的平均運行時間也越來越長。

但圖3中，當類別特征詞項數量為900時的測試文本的平均運行時間要低于類別特征詞項數量為800時。這是由于實驗的測試文本是隨機提取的，當對測試文本進行訓練集重構時，存在訓練空間的15個類別抽取完樣本去重后，訓練集中樣本數量都小于100的情況，此時測試文本的訓練集需要加入非類別特征集中的樣本，這樣測試文本的運行時間就很長，當這種測試文本較多時，測試文本的平均運行時間就會較長。

表1是不同特征詞項數目下優化后的KNN短文本分類算法的準確率。類別特征詞項數目不大于700時，優化后算法的準確率隨著類別特征詞項數目的增加而提高，隨著類別特征詞項數目的增加，訓練空間的拆分逐漸細化，測試文本重構的訓練集合樣本與測試文本的相關程度越來越高，優化后的算法的準確率也越來越高。類別特征詞項數目大于700后，優化后的算法的準確率隨著類別特征詞項數目的增加反而有所降低。這是由于類別特征詞項數目大于700后隨著類別特征詞項數目的增加，訓練空間的拆分細化程度提高，類別特征詞項集合中樣本的數量減少，在測試文本訓練集合重構時將一部分相關樣本剔除，未加入到測試文本的訓練集合中，使得算法的準確率下降。

Table 1 Algorithm accuracy underdifferent numbers of feature words

綜合分析后，本文選取類別特征詞項數目為400，此時優化算法的運行時間短，且準確率也相對較高。

4.3 實驗過程與結果

實驗從整個測試數據集中，按照不同的選取比率來隨機抽取不同數量的測試數據，比較在不同測試數據下算法的性能。圖4顯示的是傳統KNN算法與本文改進后的KNN算法的運行時間對比。

Figure 4 Comparison of running time圖4 運行時間結果比較

從圖4的對比結果中可以看出，在相同測試數據量下，改進后算法的運行時間約為傳統KNN算法的一半，有的運行時間更少，這表明本文算法對測試數據提取出的訓練集的樣本數據有明顯的減少，使得相似度計算的文本對數大量減少，運行效率有明顯的提升。但是，由于不同測試數據提取訓練樣本所對應的樣本數量不同，提取過程相似的類別特征詞集合數不同，造成對于不同的測試數據，運行效率不同。特別是在測試數據量為91時，改進后的算法運行時間偏高，這是由于提取出的類別特征詞項與隨機選取的測試數據進行相似度計算時，相似度值大于提取相似度閾值的特征詞項過多，使得提取到的訓練集中的樣本數量較多，比之原訓練空間的樣本數量減少量較少；同時，由于訓練集合重構過程所需要的時間耗費，這樣在對這些測試數據進行分類時，算法的運行時間就相對延長，效率提升就不會很大。但總體上，本文算法的運行時間還是要低于傳統KNN算法。

改進后算法的準確率的宏平均與傳統KNN算法的對比如表2所示，改進后算法的準確率的微平均與傳統KNN算法的對比如表3所示。除去測試數據量為91時，準確率低于傳統KNN，其他的情況下，本文算法的準確率較傳統的KNN算法均有所提高。這是由于針對性的訓練數據的提取，有效地將相關性較高的訓練樣本提取出來，減少由于知網語義相似度計算時，知網拓展引入冗余特征對相似度計算的影響，在一定程度上，提高了分類算法的準確率。但是，在隨機提取的91條測試數據中，根據測試數據提取的訓練集樣本數量多，且非類別特征集樣本未加入訓練集，造成分類性能有小幅度下降。但總體而言，本文算法的準確率相對于傳統KNN算法是有所提升的。

Table 2 Comparison of the accurary of macro average results

Table 3 Comparison of the accurary of micro average results

4.4 實驗結果分析

從實驗結果中可以看出，本文算法在效率上要明顯好于傳統KNN分類算法，主要是由于在本文算法中測試數據的訓練集合是根據測試數據動態重構的。訓練集合的選取是根據測試數據的特征來動態提取的，在整個訓練空間中提取出與測試數據相關的樣本重組訓練集合。這樣，就會對訓練集合進行縮減，在相似度值的計算時，只需要跟縮減后訓練集中的樣本進行比較即可，大大提高了分類的效率。同時，結合了語義因素，避免由于短文本過短，信息量少而造成的分類準確率下降。

在準確率的比較上，本文算法的準確率要略高于結合知網的KNN分類算法，這是由于改進后的算法提取的測試數據訓練集合都是與測試數據最相近的數據，一定程度上減少了因為特殊樣本的偏差而造成的分類準確率下降。

5 結束語

本文在結合知網的KNN分類算法的基礎上，通過類別特征詞集，結合知網語義信息，對訓練空間進行二次拆分，實現測試數據相似度計算時訓練集合的動態重構，縮減訓練集合樣本數目。與傳統KNN分類算法相比，該算法可以根據測試數據自適應地提取訓練集合，實驗表明，該算法可以在保證準確率的情況下，有效地提高KNN短文本分類效率。

但是，本文算法在分類的準確率上還有待改進，如何結合短文本的語義特征提高短文本相似度計算的準確性，還有待進一步研究。

[1] Cover T,Hart P.Nearest neighbor pattern classification[J].IEEE Transactions on Information Theory,1967,13(1):21-27.

[2] Li Bo, Shi Hui-xia,Wang Yi.A test extension algorithm based on synonymy discovery[J].Journal of Chongqing University of Technology(Natural Science),2014,28(2):76-81.(in Chinese)

[3] Yan Rui,Cao Xian-bin,Li Kai.Dynamic assembly classification algorithm for short text[J].Acta Electronica Sinica,2009,37(5):1019-1024.(in Chinese)

[4] Ding Ze-ya, Zhang Quan. Text categorization based on concept knowledge[J].Journal of Applied Sciences,2013,31(2):197-203.(in Chinese)

[5] Kacur J,Varga M,Rozinaj G.Speaker identification in a multimodal interface [C]∥Proc of the 2013 55th International Symposium on ELMAR,2013:191-194.

[6] Wei Chao,Luo Sen-lin,Zhang Jing,et al.Short text manifold representation based on AutoEncoder network[J].Journal of Zhejiang University (Engineering Science),2015,49(8):1591-1599.(in Chinese)

[7] Liu He,Zhang Xiang-hong,Liu Da-you,et al.A feature selection method based on maximal marginal relevance[J].Journal of Computer Research and Development,2012,49(2):354-360.(in Chinese)

[8] Liu Jin-sheng.On KNN algorithm based on optimizing similarity distance with entropy noise reduction[J].Computer Applications and Software,2015,32(9):254-256.(in Chinese)

[9] Zhan Yan, Chen Hao.Short text categorization based on theme ontology feature extended[J].Journal of Hebei University(Natural Science Edition),2014,34(3):307-311.(in Chinese)

[10] Wang Yuan,Liu Ye-zheng,Jiang Yuan-chun.Method of text classification based on roughk-nearest neighbor algorithm[J].Journal of Hefei University of Technology(Natural Science),2014,37(12):1513-1517.(in Chinese)

[11] Yu Ying, Miao Duo-qian, Liu Cai-hui,et al.An improved KNN algorithm based on variable precision rough sets[J].PR & AI,2012,25(4):617-623.(in Chinese)

[12] Ren Li-fang.Speeding K-NN classification method based on clustering [J].Computer Applications and Software,2015,32(10):298-301.(in Chinese)

[13] Luo Xian-feng, Zhu Sheng-lin,Chen Ze-jian,et al.Improved KNN text categorization algorithm based on K-Medoids algorithm[J].Computer Engineering and Design,2014,35(11):3864-3867.(in Chinese)

[14] Shen Hong,Lü Bao-liang,Utiyam a Masao,et al.Comparison and improvments of feature extraction methods for text categorization[J].Computer Simulation,2003,23(3):222-224.(in Chinese)

[15] Liu Qun, Li Su-jian.Word similarity computing based on How-net[J].Computational Linguistics & Chiese Language Processiong,2002,7(2):59-76.(in Chinese)

[16] Li Feng,Li Fang.An new approach measuring semantic similarity in Hownet 2000[J].Journal of Chinese Information Processing,2007,21(3):99-105.(in Chinese)

[17] Zhang H P, Yu H K, Xiong D Y, et al.HHMM-based Chinese lexical analyzer ICTCLAS[C]∥Proc of the 2nd SIGHAN Workshop on Chinese Language Processing:Association for Computational Linguistics,2003:758-759.

[18] http://www.datatang.com/data/43723.(in Chinese)

附中文參考文獻：

[2] 李波,石慧霞,王毅.一種基于同義詞發現的文本擴充算法[J].重慶理工大學學報(自然科學版),2014,28(2):76-81.

[3] 閆瑞,曹先彬,李凱.面向短文本的動態組合分類算法[J].電子學報,2009,37(5):1019-1024.

[4] 丁澤亞,張全.利用概念知識的文本分類[J].應用科學學報,2013,31(2):197-203.

[6] 魏超,羅森林,張競，等.自編碼網絡短文本流形表示方法[J].浙江大學學報(工學版),2015,49(8):1591-1599.

[7] 劉赫,張相洪,劉大有，等.一種基于最大邊緣相關的特征選擇方法[J].計算機研究與發展,2012,49(2):354-360.

[8] 劉晉勝.基于熵降噪優化相似性距離的KNN算法研究[J].計算機應用與軟件,2015,32(9):254-256.

[9] 湛燕,陳昊.基于主題本體擴展特征的短文本分類[J].河北大學學報(自然科學版),2014,34(3):307-311.

[10] 王淵,劉業政,姜元春.基于粗糙KNN算法的文本分類方法[J].合肥工業大學學報(自然科學版),2014,37(12):1513-1517.

[11] 余鷹,苗奪謙,劉財輝，等.基于變精度粗糙集的KNN分類改進算法[J].模式識別與人工智能,2012,25(4):617-623.

[12] 任麗芳.基于聚類的加速k-近鄰分類方法[J].計算機應用與軟件,2015,32(10):298-301.

[13] 羅賢峰,祝勝林,陳澤健，等.基于K-Medoids聚類的改進KNN文本分類算法[J].計算機工程與設計,2014,35(11):3864-3867.

[14] 申紅,呂寶糧,內山將夫，等.文本分類的特征提取方法比較與改進[J].計算機仿真,2006,23(3):222-224.

[15] 劉群,李素建.基于《知網》的詞匯語義相似度的計算[J].中文計算語言學,2002,7(2):59-76.

[16] 李峰,李芳.中文詞語語義相似度計算——基于《知網》2000[J].中文信息學報,2007,21(3):99-105.

[18] http://www.datatang.com/data/43723.