基于改进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.
　　（责任编辑：郁 慧，包震宇）
转载注明来源:https://www.xzbu.com/1/view-14847287.htm