基于改進(jìn)K最近鄰算法的中文文本分類

黃超 陳軍華

摘 要： 針對(duì)文本分類存在的高維文本問題，提出文檔頻率（DF）-卡方統(tǒng)計(jì)量特征提取方式，對(duì)特征項(xiàng)進(jìn)行有效約減，降低文本維度，提高分類精度.在K最近鄰（KNN）算法的基礎(chǔ)上，針對(duì)待分類文本需要和大量訓(xùn)練集樣本進(jìn)行相似度計(jì)算的問題，提出一種基于分組中心向量的KNN算法，對(duì)類別內(nèi)的樣本集分組求出各組中心向量，使其重新代表訓(xùn)練庫計(jì)算相似度，降低計(jì)算復(fù)雜度，提升算法的分類性能.通過實(shí)驗(yàn)表明：相較傳統(tǒng)KNN算法，改進(jìn)的算法在準(zhǔn)確率、召回率及F值方面都有提升，與其他分類算法相比，具有一定的優(yōu)勢.

關(guān)鍵詞： 文本分類; K最近鄰（KNN）算法; 特征提取; 相似度

中圖分類號(hào)： TP 393.092文獻(xiàn)標(biāo)志碼： A文章編號(hào)： 1000-5137（2019）01-0096-06

Abstract： This paper focuses on the high dimensional text problems encountered in text classification.Document frequency（DF）-chi square statistic feature extraction method is proposed to reduce the feature items and reduce the dimension of text.Based on the K Nearest Neighbor（KNN） algorithm，in view of the problem that text to be classified should be calculated in similarity with a large number of training set samples，a KNN algorithm based on grouping center vector is proposed.The center vectors of each group were obtained by grouping the sample sets in the category，so as to improve the classification performance of the algorithm.Experiments show that the improved algorithm has improved the precision rate，recall rate and F-measure compared with the traditional KNN algorithm，and it takes advantages of other classification algorithms.

Key words： text classification; K Nearest Neighbor（KNN）algorithm; feature extraction; similarity

0 引 言

中文網(wǎng)頁分類的主要流程有：網(wǎng)頁文本信息獲取、分詞處理、特征提取和權(quán)重設(shè)置、文本向量表示、算法處理及性能評(píng)價(jià).目前已經(jīng)有很多比較成熟的文本分類模型：K最近鄰（KNN）算法、樸素貝葉斯（NB）算法、神經(jīng)網(wǎng)絡(luò)（NN）算法、決策樹（DT）算法、支持向量機(jī)（SVM）等[1].其中，KNN算法較為成熟，數(shù)據(jù)訓(xùn)練的時(shí)間復(fù)雜度要比其他算法的低，異常點(diǎn)不敏感.

KNN算法在中文文本分類方面的應(yīng)用有很多.鄭俊飛[2]提出了一種動(dòng)態(tài)設(shè)置K值的策略.ZHANG等[3]提出學(xué)習(xí)相關(guān)矩陣重構(gòu)測試數(shù)據(jù)點(diǎn)的方案.CHEN等[4]針對(duì)傳統(tǒng)的詞頻-逆文檔頻率（TF-IDF）不能完全有效進(jìn)行文本分類的缺陷，提出詞頻-逆重力力矩（TF-IGM）特征提取方法.WANG等[5]提出一種基于內(nèi)核方法和屬性約減的分階式KNN算法，以解決分類過程中維數(shù)過高以及分類的準(zhǔn)確度受到訓(xùn)練樣本分布不均影響的問題.周慶平等[6]提出了基于聚類改進(jìn)的KNN算法，大幅減少時(shí)間復(fù)雜度.劉述昌等[7]提出了基于中心向量的多級(jí)分類KNN算法，不僅降低了算法復(fù)雜度，還提高了分類速度.邱定等[8]將Rocchio算法和KNN算法結(jié)合，根據(jù)數(shù)據(jù)集的具體數(shù)據(jù)分布，為整個(gè)分類空間建立不同個(gè)數(shù)的分類代表.肖斌等[9]提出分布式KNN算法的概念，采用Hadoop平臺(tái)實(shí)現(xiàn)基于MapReduce模型的KNN算法，并將其應(yīng)用到微信公眾號(hào)的分類中.

但KNN算法仍存在許多的缺點(diǎn)，如：在相似度的計(jì)算上，每一個(gè)待分類文本都需要和訓(xùn)練集里的每一個(gè)訓(xùn)練文本進(jìn)行距離度量的計(jì)算，并記錄度量值，時(shí)間和空間復(fù)雜度都比較大;在特征提取上，約減詞數(shù)不合理，導(dǎo)致分類的結(jié)果也不一樣;在K值的選取上，也一直沒有科學(xué)有效的結(jié)論等.

本文作者針對(duì)上述問題進(jìn)行研究與分析，提出改進(jìn)方案.在特征維數(shù)約減上，提出文檔頻率（DF）-卡方統(tǒng)計(jì)特征提取方式，快速求取文檔頻率值并進(jìn)行約減，對(duì)保留詞匯利用卡方統(tǒng)計(jì)量再次進(jìn)行特征提取，最后對(duì)留下的詞匯獲取DF值，并進(jìn)行后續(xù)的權(quán)重設(shè)置;在分類的相似度計(jì)算上，提出基于分組中心向量的改進(jìn)KNN算法，對(duì)每個(gè)類別下的文本向量進(jìn)行分組操作，求出該類別下每組向量的中心向量，重新代表訓(xùn)練集文檔在該類別下的向量，既保證了代表向量的數(shù)量，提高了分類的準(zhǔn)確度，又降低了訓(xùn)練集數(shù)量，提高了相似度量計(jì)算的效率.

1 特征提取方法

1.1 文檔頻率

DF是指計(jì)算每個(gè)特征在整個(gè)訓(xùn)練文檔集中出現(xiàn)的文檔頻數(shù)，它是衡量一個(gè)特征是否對(duì)文本的表示有貢獻(xiàn)的重要指標(biāo).在進(jìn)行特征提取時(shí)，需要設(shè)定閾值.當(dāng)特征項(xiàng)低于或高于閾值時(shí)，刪除該特征項(xiàng).DF特征提取計(jì)算簡單，時(shí)間復(fù)雜度低，非常適用于大規(guī)模的語料庫.DF計(jì)算公式如下：

1.2 卡方統(tǒng)計(jì)量

1.3 基于DF-卡方統(tǒng)計(jì)量的特征提取

在特征維數(shù)約減上，提出一種新的DF-卡方統(tǒng)計(jì)量特征提取方式.在保留一定合理數(shù)量文本特征詞的基礎(chǔ)上，使閾值盡可能小，再利用卡方統(tǒng)計(jì)方法約減詞匯，得到更加合理的最終詞匯集，將其與初始DF處理集比較，得到最終詞匯DF值.

其具體步驟如下：

1） 利用式（1）計(jì)算每一個(gè)特征的DF值;

2） 將特征項(xiàng)按DF值進(jìn)行從大到小排序;

3） 選取前p個(gè)特征作為初級(jí)特征集;

4） 對(duì)初級(jí)特征集利用式（2）計(jì)算出每一個(gè)特征的χ2;

5） 對(duì)結(jié)果集按卡方統(tǒng)計(jì)量從大到小排序;

6） 選取前q個(gè)特征，作為最終特征集.

2 基于分組中心向量的改進(jìn)KNN算法

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)

本實(shí)驗(yàn)采用的計(jì)算機(jī)系統(tǒng)為32位Win7系統(tǒng)，處理器為Core-i3，內(nèi)存為4 GB，硬盤為128 GB的固態(tài)硬盤.Java 語言的軟件開發(fā)工具包JDK的版本為jdk-7u79-windows-i586，使用的開發(fā)工具平臺(tái)IDE為MyEclipse 10.7，數(shù)據(jù)挖掘開源軟件Weka的版本為3.4.19，分詞處理使用了中科院的開源分詞工具ICTCLAS 2015.

為了實(shí)驗(yàn)方便，采用復(fù)旦大學(xué)計(jì)算機(jī)信息與技術(shù)系國際數(shù)據(jù)庫中心自然語言處理小組李榮陸老師在2013年發(fā)布的中文語料庫作為實(shí)驗(yàn)數(shù)據(jù)，共20個(gè)類別，分為訓(xùn)練集和測試集，訓(xùn)練集9804篇，測試集9833篇.選取主流常見的10個(gè)類別作為中文網(wǎng)頁文本分類實(shí)驗(yàn)數(shù)據(jù)集.為方便實(shí)驗(yàn)，對(duì)這10類文本隨機(jī)挑選合適數(shù)目的數(shù)據(jù)，按2∶1的比例隨機(jī)進(jìn)行訓(xùn)練集和測試集的劃分，得到訓(xùn)練集文檔數(shù)1740篇，測試集文檔數(shù)930篇.

3.2 實(shí)驗(yàn)結(jié)果分析

在進(jìn)行實(shí)驗(yàn)前，需要確定K參數(shù).為找到最優(yōu)K值，對(duì)930篇測試集文檔進(jìn)行多次重復(fù)實(shí)驗(yàn)，比較分類結(jié)果準(zhǔn)確率，得到如下實(shí)驗(yàn)記錄（表1）.

4 結(jié) 論

本文作者針對(duì)傳統(tǒng)KNN算法在文本分類應(yīng)用中所出現(xiàn)的問題進(jìn)行研究與分析，在維數(shù)約減上，提出使用DF-卡方統(tǒng)計(jì)量法進(jìn)行特征維數(shù)的有效約減，并提出了基于分組中心向量的方法，在類別文本內(nèi)部再分組，求出組均值向量作為中心向量.在Weka平臺(tái)上對(duì)改進(jìn)的KNN算法進(jìn)行實(shí)驗(yàn)，并和傳統(tǒng)KNN算法、 SVM算法和NB算法的實(shí)驗(yàn)結(jié)果數(shù)據(jù)進(jìn)行比較，可以看出其綜合性能上有一定的優(yōu)勢.但由于時(shí)間有限以及實(shí)驗(yàn)條件的限制，還有許多地方需要完善，如在類別文本區(qū)分度不夠明顯的情況下如何保持分類性能，還有如何保持分類結(jié)果的穩(wěn)定性等，這些都是接下來要考慮的內(nèi)容和研究的方向.

參考文獻(xiàn)：

[1] 甄志龍.文本分類中的特征選擇方法研究 [M].長春：吉林大學(xué)出版社，2016.ZHEN Z L.Research on feature selection in text categorization [M].Changchun：Jinlin University Press，2016.

[2] 鄭俊飛.文本分類特征選擇與分類算法的改進(jìn) [D].西安：西安電子科技大學(xué)，2012.ZHENG J F.Improvement of text classification feature selection and classification algorithm [D].Xi′an：Xidian University，2012.

[3] ZHANG S C，LI X.Learning K for KNN classification [J].ACM Transactions on Intelligent Systems and Technology，2017，8（3）：43.

[4] CHEN K W，ZHANG Z P，LONG L，et al.Turning from TF-IDF to TF-IGM for term weighting in text classification [J].Expert Systems with Applications，2016，66（C）：245-260.

[5] WANG X L，JIANG Z Y，YU D H.An improved KNN algorithm based on kernel methods and attribute reduction [C]//Instrumentation and Measurement Computer Communication and Control.Piscataway：IEEE，2015：567-570.

[6] 周慶平，譚長慶，王宏君，等.基于聚類改進(jìn)的KNN文本分類算法 [J].計(jì)算機(jī)應(yīng)用研究，2016，33（11）：3374-3377，3382.ZHOU Q P，TAN C Q，WANG H J，et al.Improved KNN text classification algorithm based on clustering [J].Application Research of Computers，2016，33（11）：3374-3377，3382.

[7] 劉述昌，張忠林.基于中心向量的多級(jí)分類KNN算法研究 [J].計(jì)算機(jī)工程與科學(xué)，2017，39（9）：1758-1764.LIU S C，ZHANG Z L.Research on multilevel classification KNN algorithm based on central vector [J].Computer Engineering & Science，2017，39（9）：1758-1764.

[8] 邱定，張激，王金華，等.基于Rocchio和KNN提出的新的文本分類技術(shù) [J].自動(dòng)化與儀器儀表，2017（8）：107-110.QIU D，ZHANG J，WANG J H，et al.New text categorization technology based on Rocchio and KNN [J].Automation & Instrumentration，2017（8）：107-110.

[9] 肖斌，王錦陽，任啟強(qiáng).分布式KNN算法在微信公眾號(hào)分類中的應(yīng)用 [J].計(jì)算機(jī)應(yīng)用，2017，37（增刊1）：295-299.XIAO B，WANG J Y，REN Q Q.Application of distributed KNN algorithm in WeChat public number classification [J].Journal of Computer Applications，2017，37（Suppl.1）：295-299.

[10] 張宇，劉雨東，計(jì)釗.向量相似度測度方法 [J].聲學(xué)技術(shù)，2009，28（4）：532-536.ZHANG Y，LIU Y D，JI Z.Vector similarity measure method [J].Technical Acoustics，2009，28（4）：532-536.

（責(zé)任編輯：郁 慧，包震宇）