基于改進K最近鄰算法的中文文本分類

來源:用戶上傳      作者:

　　摘 要： 針對文本分類存在的高維文本問題，提出文檔頻率（DF）-卡方統計量特征提取方式，對特征項進行有效約減，降低文本維度，提高分類精度.在K最近鄰（KNN）算法的基礎上，針對待分類文本需要和大量訓練集樣本進行相似度計算的問題，提出一種基于分組中心向量的KNN算法，對類別內的樣本集分組求出各組中心向量，使其重新代表訓練庫計算相似度，降低計算復雜度，提升算法的分類性能.通過實驗表明：相較傳統KNN算法，改進的算法在準確率、召回率及F值方面都有提升，與其他分類算法相比，具有一定的優勢.
　　關鍵詞： 文本分類; K最近鄰（KNN）算法; 特征提取; 相似度
　　中圖分類號： TP 393.092文獻標志碼： A文章編號： 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 引 言
　　中文網頁分類的主要流程有：網頁文本信息獲取、分詞處理、特征提取和權重設置、文本向量表示、算法處理及性能評價.目前已經有很多比較成熟的文本分類模型：K最近鄰（KNN）算法、樸素貝葉斯（NB）算法、神經網絡（NN）算法、決策樹（DT）算法、支持向量機（SVM）等[1].其中，KNN算法較為成熟，數據訓練的時間復雜度要比其他算法的低，異常點不敏感.
　　KNN算法在中文文本分類方面的應用有很多.鄭俊飛[2]提出了一種動態設置K值的策略.ZHANG等[3]提出學習相關矩陣重構測試數據點的方案.CHEN等[4]針對傳統的詞頻-逆文檔頻率（TF-IDF）不能完全有效進行文本分類的缺陷，提出詞頻-逆重力力矩（TF-IGM）特征提取方法.WANG等[5]提出一種基于內核方法和屬性約減的分階式KNN算法，以解決分類過程中維數過高以及分類的準確度受到訓練樣本分布不均影響的問題.周慶平等[6]提出了基于聚類改進的KNN算法，大幅減少時間復雜度.劉述昌等[7]提出了基于中心向量的多級分類KNN算法，不僅降低了算法復雜度，還提高了分類速度.邱定等[8]將Rocchio算法和KNN算法結合，根據數據集的具體數據分布，為整個分類空間建立不同個數的分類代表.肖斌等[9]提出分布式KNN算法的概念，采用Hadoop平臺實現基于MapReduce模型的KNN算法，并將其應用到微信公眾號的分類中.
　　但KNN算法仍存在許多的缺點，如：在相似度的計算上，每一個待分類文本都需要和訓練集里的每一個訓練文本進行距離度量的計算，并記錄度量值，時間和空間復雜度都比較大;在特征提取上，約減詞數不合理，導致分類的結果也不一樣;在K值的選取上，也一直沒有科學有效的結論等.
　　本文作者針對上述問題進行研究與分析，提出改進方案.在特征維數約減上，提出文檔頻率（DF）-卡方統計特征提取方式，快速求取文檔頻率值并進行約減，對保留詞匯利用卡方統計量再次進行特征提取，最后對留下的詞匯獲取DF值，并進行后續的權重設置;在分類的相似度計算上，提出基于分組中心向量的改進KNN算法，對每個類別下的文本向量進行分組操作，求出該類別下每組向量的中心向量，重新代表訓練集文檔在該類別下的向量，既保證了代表向量的數量，提高了分類的準確度，又降低了訓練集數量，提高了相似度量計算的效率.
　　1 特征提取方法
　　1.1 文檔頻率
　　DF是指計算每個特征在整個訓練文檔集中出現的文檔頻數，它是衡量一個特征是否對文本的表示有貢獻的重要指標.在進行特征提取時，需要設定閾值.當特征項低于或高于閾值時，刪除該特征項.DF特征提取計算簡單，時間復雜度低，非常適用于大規模的語料庫.DF計算公式如下：
　　1.2 卡方統計量 　　1.3 基于DF-卡方統計量的特征提取
　　在特征維數約減上，提出一種新的DF-卡方統計量特征提取方式.在保留一定合理數量文本特征詞的基礎上，使閾值盡可能小，再利用卡方統計方法約減詞匯，得到更加合理的最終詞匯集，將其與初始DF處理集比較，得到最終詞匯DF值.
　　其具體步驟如下：
　　1） 利用式（1）計算每一個特征的DF值;
　　2） 將特征項按DF值進行從大到小排序;
　　3） 選取前p個特征作為初級特征集;
　　4） 對初級特征集利用式（2）計算出每一個特征的χ2;
　　5） 對結果集按卡方統計量從大到小排序;
　　6） 選取前q個特征，作為最終特征集.
　　2 基于分組中心向量的改進KNN算法
　　3 實驗與分析
　　3.1 實驗環境與數據
　　本實驗采用的計算機系統為32位Win7系統，處理器為Core-i3，內存為4 GB，硬盤為128 GB的固態硬盤.Java 語言的軟件開發工具包JDK的版本為jdk-7u79-windows-i586，使用的開發工具平臺IDE為MyEclipse 10.7，數據挖掘開源軟件Weka的版本為3.4.19，分詞處理使用了中科院的開源分詞工具ICTCLAS 2015.
　　為了實驗方便，采用復旦大學計算機信息與技術系國際數據庫中心自然語言處理小組李榮陸老師在2013年發布的中文語料庫作為實驗數據，共20個類別，分為訓練集和測試集，訓練集9804篇，測試集9833篇.選取主流常見的10個類別作為中文網頁文本分類實驗數據集.為方便實驗，對這10類文本隨機挑選合適數目的數據，按2∶1的比例隨機進行訓練集和測試集的劃分，得到訓練集文檔數1740篇，測試集文檔數930篇.
　　3.2 實驗結果分析
　　在進行實驗前，需要確定K參數.為找到最優K值，對930篇測試集文檔進行多次重復實驗，比較分類結果準確率，得到如下實驗記錄（表1）.
　　4 結 論
　　本文作者針對傳統KNN算法在文本分類應用中所出現的問題進行研究與分析，在維數約減上，提出使用DF-卡方統計量法進行特征維數的有效約減，并提出了基于分組中心向量的方法，在類別文本內部再分組，求出組均值向量作為中心向量.在Weka平臺上對改進的KNN算法進行實驗，并和傳統KNN算法、 SVM算法和NB算法的實驗結果數據進行比較，可以看出其綜合性能上有一定的優勢.但由于時間有限以及實驗條件的限制，還有許多地方需要完善，如在類別文本區分度不夠明顯的情況下如何保持分類性能，還有如何保持分類結果的穩定性等，這些都是接下來要考慮的內容和研究的方向.
　　參考文獻：
　　[1] 甄志龍.文本分類中的特征選擇方法研究 [M].長春：吉林大學出版社，2016.ZHEN Z L.Research on feature selection in text categorization [M].Changchun：Jinlin University Press，2016.
　　[2] 鄭俊飛.文本分類特征選擇與分類算法的改進 [D].西安：西安電子科技大學，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] 周慶平，譚長慶，王宏君，等.基于聚類改進的KNN文本分類算法 [J].計算機應用研究，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] 劉述昌，張忠林.基于中心向量的多級分類KNN算法研究 [J].計算機工程與科學，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提出的新的文本分類技術 [J].自動化與儀器儀表，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] 肖斌，王錦陽，任啟強.分布式KNN算法在微信公眾號分類中的應用 [J].計算機應用，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].聲學技術，2009，28（4）：532-536.ZHANG Y，LIU Y D，JI Z.Vector similarity measure method [J].Technical Acoustics，2009，28（4）：532-536.
　?。ㄘ熑尉庉嫞河?慧，包震宇）
轉載注明來源:http://www.hailuomaifang.com/1/view-14847287.htm