2019年5月计算机工程与设计May2019第40卷第5期COMPUTER ENGINEERING AND DESIGN Vol.40No.5变精度粗糙集的加权KNN文本分类算法 刘发升，董清龙+，李文静
（江西理工大学信息工程学院，江西赣州341000）
摘要：针对训练样本较大时KNN算法（K最近邻算法）的分类效率较低和训练样本不均衡时算法的分类性能受到影响这两个问题，提出变精度粗糙集的加权KNN文本分类算法。利用变精度粗糙集上下近似的概念，将各个类别的训练集分为P正区域和P边界域。分类过程中根据测试样本与样本中心的相似度，得到样本的归属区域。其中属于p正区域的样本可以直接判断其类别，其它区域的样本用基于数量加权的KNN算法判断其类别。实验结果表明，该算法能有效提高分类的性能和效率。 关键词：K最近邻；文本分类；变精度粗糙集；上近似；下近似；数量加权
中图法分类号：TP391.1文献标识号：A文章编号：1000-7024（2019）05-1339-04
doi：10.16208/j.issnl000-7024.2019.05.026
Weighted KNN text classfication algorithm for
variable precision rough sets
LIU Fa-sheng,DONG Qing-long+,LI Wen-ing
(School of Information Engineering,Jiangxi University of Science and Technology,Ganzhou341000,China) Abstract:Aiming at the two problems that the classification efficiency of KNN algorithm(K-nearest neighbor algorithm)is low when the training sample scale is large and the classification performance of the algorithm is affected when the training samples are unbalanced,a weighted KNN text classification algorithm based onvariable precision rough set(VRSW-KNN)waspro-posed.The concepts of upper and lower approximations of variable precision rough sets were used to classify the training sets of each category into p positive and p bounding domains.The classification process was based on the similarity between the test sample and the sample center,and the area of the sample was obtained.The categories of samples belonging to the positive region of the beta were directly judged,and the samples in the other regions were judged using the KNN algorithm based on the quantitative weighting.Experimental results show that this algorithm can effectively improve the performance and efficiency of classification.
Key words：K-nearest neighbor(KNN);text classification；variable precision rough set；upper approximation；lower approxi-mation#quantityweighting
0引言
KNN算法在文本分类方面有着良好的应用，但也存在 一些缺陷。针对这些缺陷，诸多学者做了大量的改进研究。该算法的第一个缺陷是当训练样本的数量较大时，算法的分类效率较低14。针对该问题，周庆平等先采用改进的0统计量方法对文本进行特征选取，再使用聚类的方法将训练集聚成几个簇，最后利用改进的KNN方法对簇类文本
收稿日期：2018-03-12；修订日期：2018-04-20
基金项目：江西省研究生创新专项基金项目（YC2017-S314）进行分类。罗贤锋等聞使用K-Medoids算法对训练集进行聚类，将训练集分成相似度较高的簇，然后根据簇与分类文本的相对位置对训练集进行裁剪。上诉的两种基于聚类改进的算法可以提高分类的效率，但都不可避免地带来样本信息的损失，从而导致算法的性能受到影响。杨帅华等口提出了粗糙集近似集的KNN文本分类算法，通过引入集似集方高了，
分类性能没有得到改进。
作者简介：刘发升（1963-），男，江西赣州人，博士，教授，CCF高级会员，研究方向为数据挖掘、不确定信息处理；+通讯作者：董清龙（1994-），男，江西景德镇人，硕士，研究方向为数据挖
掘、粗糙集；李文静（1993-），女，河南郑州人，硕士，研究方向为数据挖掘。E-mail:1227384625@qq
•1340•计算机工程与设计2019年
KNN算法的第二个缺陷是当训练样本分布不均衡时，算法的分类性能会受到影响+1i,（针对该缺陷，Shi等+幻提出了基于密度的改进KNN文本分类算法，通过文本密度对传统的KNN决策函数进行修改。刘海峰等+3〕提出一种基于位置的文本分类样本裁剪及加权的方法。先通过聚类的算法对样本进行裁剪，然后根据样本空间的位置对样本加权。上诉两种算法有效的提升了分类的性能，但时间效率都没有得到很大的提高。
从以上的研究现状出发，本文提出了变精度粗糙集加权KNN文本分类算法。首先利用变精度粗糙集上下近似的概念对样本空间进行划分，以此提高分类效率。然后在此基础上对样本数量的研究，通过样本加权的方式提高分类的性能。实验结果表明，相比传统KNN算法，改进后的算法不仅能提高分类的效率，而且也可以有效削弱样本分布不均衡对分类性能的影响。
1相关概念
1.1基于KNN的文本分类算法
疫情下的奥运会如何举办?
传统KNN文本分类算法思想为：首先计算测试样本与各个训练样本之间的距离，然后排序选出与测样本最相似的K个训练样本，根据这K个训练样本计算各个类别的权值，最后将该样本分给权值最大的类别。其具体步骤如下：步骤1根据训练集的文本特征项集合将训练文本和测试文本表示为向量空间内的向量6={W,i,W2,--,W m}T（步骤2计算测试文本向量与每一个训练文本向量之间的相似度，计算公式如式（1）所示。式（1）中6,6；分别代表测试文本和训练文本，皿代表向量空间的维数，W*代表文件6，的第*维
simCdt,6,）=—,（1）
J—W"F W*-W*X W*
中国土布网
槡"=1槡"=1
步骤3根训练本与本间似'从训练文本中选出与测试文本相似度最大的K个文本。然后根据式（2）计算每一个类别的权值。式（2）中的c，代别
+=—1—$6，6,）（,，c,）（2）
,=1
（06,#c,
%$6,c）=仁
16,P c,
步骤4个别权值本权值大的类别。
1.2变精度粗糙集的基本概念
Ziarko提出了不对称边界变精度粗糙集模型。该模型通过引进一个精度p，将集合的上、下近似变为任意精度水 平，其中上下近似的P值可以不同，p#［0,0.5）。
设X，丫表示有限论域U的非空子集，如果对于任意元素>#X可得到e#Y，则X<；丫。很明显，从这个定义中不会出现错误的分类。因此在此引进一个测量值c（X，Y）来表示集合X属于集合Y的分类错误率
21—?6（［）〉0 c（［，Y）=1car6（X）
0car6（.X）=0
其中，c ar6（、X）为集合的势。显然，c（X，Y）Q X<Y。多数包含关系为：Y R X Q c（X，Y）/p（
设（U，R）为近似空间，其中U为非空有限集合，R为U上等价关系，R$为R的等价类。
对于X<U，定义X的p的下近似
R P X=U{#R*:c（E，X）4p}
RX称为p的正区域。
定义X的p的上近似
RX=U E#R$:c（E，X）41—p}会泽信息港
R p X称为p的上近似区域。
X p边界域为
BNR p X=U E#R$:p<c（E，X）41—p}
当p=0时，p的正区域和p的上近似域即为经典粗糙集上、下近似的定义。
2变精度粗糙集加权KNN文本分类算法
2.1基于文本数量加权的KNN修正算法
当训练集分布不均衡时，每个测试样本在寻K个最近邻时会更趋向于语料库中文本较大的类别。如果使用传统的KNN决策规则对这些样本进行分类，这些测试样本更可能被判断为训练集中数量较大的类别。在训练集中数量较大类别的文本有着较高的准确率，但其它类别文本的准确率将会降低。因此KNN算法的整体性能将不可避免的受到影响。本文通过基于K近邻内文本数量对文本进行加权的方式来降低文本分布不均衡对分类效率的影响。
测试样本的K个最近邻中有"个类别，用式（3）对K 中个本进行加权
-reight,=--------------------1--------------------丄@〉0（3）
（1十Nu—（Ci）/Avgnu—（,Ci））~t
电信网技术式中：Nu—（C）为K近邻中属于G的文本数量（Avgnu—C&是指K近邻中类别的平均文本数。修正后KNN策为
+（6,c）=^^Weight,$si—（d,，6；）$y（d；，c,）（4）
,=i
{06；#c ,
第40卷第5期刘发升，董清龙！李文静：变精度粗糙集的加权KNN文本分类算法・1341・
2.2上下近似区域的计算方法
设训练集中共有-个类，分别用X#,X2,0X-表
示，各个类别的质心为0(&)。
计&的上下近似半径的算法步骤如下：
步骤1计算训练集中类别中心为0(&)。
步骤2计别中心O(X)与别样本所有样本的相似度，小值作为上近似半径。
步骤3计别中心O(X Q与所有样本的相似度计
螳螂捕蝉教学设计算，将样本相似度大于门的样本降序存放在中。
步骤4从D的第一个元素始，前*个元素。如果Num()>"，则下近似半径为中心点与第*—1个*
元素之间距离。
算法中Num
*)表示前*个对象中不属于类别X i 的对象。
2.3变精度粗糙集加权KNN文本分类算法
本用不对称变精度粗糙集型来描述各个类的
上下近似区域，文本类别的下近似区域是该类的核心区域，
了别大形状。而边界域中本归
，是对文本类别个补充。当训练样本属
于某个类别的下近似区域时，直本属于别。
否则，判断该文本在哪些类别上近似区域内，在这些类别
中使用基于数加权KNN得本别。如
本在别上似区域，在别中
使用基于本数KNN得本别。
整个如图1。
图1变精度粗糙集加权KNN文本分类算法步骤1计个本别上下似区域。
步骤2根据式(1)计算测试样本与各类中心点之间
似，本。
步骤3当对某类文本进行分类的时候，首先判断该文本是否属于各个类别的"近似区域，如于，则直：本归于别。束。
步骤4如本于某些别上似区域，在这些别中使用式4)本别。
步骤5如本于别上似区域，在
别中使用式4)本别。
3实验结果与分析
本文采用复旦大学中文语料库作为数据来源，选取其中的1500篇作为数据集，其中包括艺术、、计算机等8个类别。其中本数量最少100篇，教育本数300篇。数集中1000篇本作为训练本
500篇作为本。本文采用jieba分词对文本进行分词，在词、用词、IG特征选择提取过程后得到一个训练集的特征词集合。本文特征词的个数为2806个。采取TF-IDF特征词加权方式将文本变成特征向量。
能评价指标采用F#值，为了排除随机因素所带来的影响，本别对 进行 行，最终采用行时间为行平均值。
能价指标，但这两个指标在上。考虑查与查全率，可以得到新价指标F#，也称为。它的计算式为
9=2$precision$recall
precision+recall
precision=”
D i
recall=P(5)式中：precision代表准确率，指的是分类正确的文本数N 与本数G之间。recall
本数P与本M之间。
为两个，第通过调整参数"的值来观察本变化。本文算法与传统KNN进行。因为本时间与参数f没有关系，选取i=1o同时实验统计结果见表1。
从表1可得，误差"从0・1逐渐减小到0时，算法的下近似空间逐渐减小，相似度计作逐渐增加，时间逐渐增大。当"减小到0时，时间变为最大。但时计传统KNN计小。因此，引入变集理论能高KNN文本分。
第二阶段通过调整f值来观察本文算法的性能变化。并将本别与没有加权的变集KNN算法和传统KNN别进行，数据统计2
。
表1P取不同值时算法耗时对比
传统KNN算法-"
=O1
VRSW-KNN（本文改进算法）
"=O08"=O06"=004"=002"=0
总耗时/s1203.2564.6661.2696.3753.2812.8850.5平均耗时/s16O75O88O93 1.0 1.08 1.13
表2f取不同值时候算法的91值对比
类别KNN 变精度粗糙集
KNN
VRSW-KNN（变精度粗糙集加权KNN算法）
f=0.5f=1.0f=1.5f=2.0f=2.5f=3.0f=3.5f=4.0
艺术0.790.770.650.700.750.820.840.820.820.82经济0.720.770.700.740.740.800.820.800.780.77教育0.890.850.750.780.860.880.880.870.870.87环境0.780.810.660.840.840.850.850.830.820.83政治0.770.750.720.750.780.810.830.800.810.80育0.820.800.640.810.840.870.870.840.850.84计0.830.700.670.80.830.850.850.850.840.85军事0.810.820.70.720.770.840.850.830.840.81平0.800.780.700.760.790.830.840.820.820.82
从表2可知，使用变精度粗糙集对训练集进行类别的划分虽然加快了分类的效率，但分类的性能降低了2%。当i=0.5时，本文算法的91值比传统KNN算法和变精度粗糙集KNN算法的91值小，但随着f值的增大，本文算法的9#值逐渐变大。到f=2.5时，本文算法的9#值达到最大，此时本文算法91值相对传统的KNN算法提高了将近4%，相对与变精度粗糙KNN算法提高了将近6%。虽然之后算法9#值随着f值的增大会有所降低，但依旧高于传统的KNN算法和变精度粗糙集KNN算法。
综上所诉，在参数P和r取值合理的情况下，本文算法能有效提高分类的效率和性能。
4结束语
针对训练样本较大时KNN算法的分类效率较低和训练样本不均衡时算法的分类性能受到影响这两个问
题，提出变精度粗糙集的加权KNN文本分类算法。通过引进变精度粗糙模型和对文本进行加权的方式有效提高了分类的效率和性能。实验结果表明了该算法的可行性，并且和理论分析结果相互一致。但是本算法也存在一定的不足，将来的研究考虑如何在保证目前分类精度的情况下，进一步利用粗糙集理论更加准确的刻画各个类别的分布情况，使分类的效率变得更高。
参考文献：
[1,Jaderberg M，Simonyan K，Vedaldi A，et al.Reading text in
the wild with convolutional neural networks[J,.International Journal of Computer Vision，2014，116⑴：1-20
[2,Zadrozny S，Kacprzyk J，Gajewski M.A new approach to the multiaspect text categorization by using the support vector machines[M,//C hallenging Problems and Solutions in Intelligent Systems.Springer International Publishing，2016：261-271.
[3,Bfalwan V，Kumafi P，Pascual J，et al.KNN based machine learning approach for text and document mining[J,.Interna-tionalJournalof Database Theoryand Application，2014，7
(I)：6-70
[4,Al-Salemi B，Aziz MJA，Noah SA.LDA-AdaBoost.MH"
AcceleratedAdaBoost.MH basedonlatentDirichleta l ocation for text categorization[M,.Sage Publications，Inc,2015：27-40.
[5,ZHOU Qingping，TAN Changgeng，WANG Hongjun，etal.
KNNtextcategorizationalgorithmbasedonimprovedclustering [J,.Application Reasearch ofComputers，2016，33(11：：3374-3377(in Chinese).[周庆平，谭长庚，王宏君，等.基于聚类改进的KNN文本分类算法[J,.计算机应用研究, 2016，33(11)：3374-3377..
[6,LUO Xianfeng,ZHU Shenglin，CHENG Zejian,et al.Improved KNN text categorization algorithm based on K-Medoids clustering[J,.Computer Engineering and Design，2014,35 (II) ：3864-3867(in Chinese).[罗贤锋，祝胜林，陈泽健，等.基于K-Medoids聚类的改进KNN文本分类算法[J,.计算机工程与设计，2014,35(11)：3864-3867..
(下转第1364页)
金水翠峰
outage using RB-UKF[J*.Optics and Precision Engineering, 2016,24(4)：198-204(in Chinese).[张百强"储海容"孙婷婷"等.应用RB无迹卡尔曼滤波组合导航提高GPS重获信号后的导航精度[J*.光学精密工
程"2016,24⑷：198-204..
[2*ZHAO Wenjun,MAO Xuchu.Adaptive filter-based tracking method for weak GPS signal[J*.Computer Simulation,2013, 30(8)：88-91(in Chinese).[赵文俊"茅旭初.基于自适应滤波的微弱GPS信号跟踪方法[J*.计算机仿真,2013,30
8)：88-91X*
[3*LU Qiao,MA Guoliang,ZHANG Ping,et al.Application of SR-CDKFindirectfilteringofintegratednavigation[J*XJour-nalofBa l istics"2017"29(4)：29-34(inChinese)X["
马国梁，张平，等.SR-CDKF在组合导航直接法滤波中的应用[*.弹道学报，2017,29(4)：29-34..
[4*REN Jianxin,ZHOU BingchengX High-precision navigation systemsimulation[J*XComputerSimulation,2012,29(6)：304-307(in Chinese).[任建新，周秉成.高精度组合导航系统仿真[J*.计算机仿真,2012,29(6)：304-307..
[5*SHEN Kai"GUAN Xueyuan"$I Wensheng Application of EKFin integrated navigation system[J*Transducer and Microsystem Technologies,2017,36(8)：158-160(in Chi-nese).[沈凯，管雪
元，李文胜.扩展卡尔曼滤波在组合导航的应用[J*微系统"2017"36(8)：158-160*
[6*SUN Hongwei,CHU Yuxiao.Adaptive extended Kalman filter in SINS/GPS navigation system[J*.Computer Engineering
and Design,2014,35(12)：4375-4379(in Chinese).[孙洪伟，褚玉晓.SINS/GPS组合导航系统自适应扩展Kalman滤波[J*计算机程计,2014,3512)：4375-4379* [7*XU Genyuan,WANG Zhi,WANG Zhiqiang.GPS/INS pos--tionintegratednavigationbasedonadaptiveKalmanfilter[J* ElectronicDesign Engineering"2017"2521)：100-103(in Chinese).[许根源，王直，王志强.基于自适应卡尔曼滤波的GPS/INS位置组合导航[J*.电子设计工程，2017,25
21)：100-103*
[8*$INing"DING Wei"ZHANG Yonggang Integratednaviga-tionsystem simulation platform[J*Computer Engineering and Design,2014,35(3)：981-985(in Chinese).[李宁，丁薇，张勇刚.组合导航系统仿真平台的设计与实现[J*.计算机程计,2014,353)：981-985*
[9*YANG Chun,ZHANG$ei Fault-tolerantintegratednaviga-tion algorithm using chi-square test with two state propagators and fuzzy adaptive filter[J*.Control Theory&Applications, 2016,33(4)：1217-1
220(in Chinese).[杨春，张磊.采用双状态传播卡方检验和模糊自适应滤波的容错组合导航算法[J*.控制理论与应用，2016,33(4)：1217-1220..
[10*ZHANG Henghao,SHIJingXIntegratednavigationalgorithm withposteriorvarianceandasynchronousfusion[J*XControl Theory&Applications,2017,34(12)：1561-1567(in Chi-nese).[张恒浩，史静.组合导航后验方差异步融合算法[J*理应用,2017,34(12)：1561-1567*
(上接第1342页)
[7*YANG Shuaihua,ZHANG Qinghua Researchon KNN text categorizationalgorithm basedonroughsetapproximationset [J*JournalofChinese Mini-MicroComputerSystems,2017, 38(10)：2192-2196(in Chinese).[杨帅华，张清华.粗糙集近似集的KNN文本分类算法研究[J*.小型微型计算机系统，2017,3810)：2192-2196*
[8*Guo H,$iY,$iY,etal BPSO-Adaboost-KNN ensemble learningalgorithmformulti-classimbalanceddataclassification [J*Engineering ApplicationsofArtificialInte l igence,2016, 49%C)：176-193
[9*Geler Z,Kurbalija V Comparison of di f erent weighting schemesfortheKNNclassifierontime-seriesdata[J*Knowledge&Information Systems,2016,48(2)：331-378.
[10
*Fernandez A,Lopez V,Galar M,et al.Analysing the class--ficationofimbalanceddata-setswithmultipleclasses：Binariza-tiontechniquesandadhocapproaches[J*Knowledge-Based Systems,2013,422)：97-110
[11*KrawczykB,SchaeferG Animprovedensembleapproachfor imbalancedclassification problems[C*//InternationalSym-
posiumonAppliedComputationalInte l igenceandInformatics
IEEE,2013：423-426
[12*PengY,Fan W,DongX,etal AniterativeweightedKNN (IW-KNN)basedindoorlocalization methodinbluetoothlow energy(BLE)environment[C*//Ubiquitous Intelligence& Computing,AdvancedandTrustedComputing,ScalableCom-putingandCommunications,CloudandBigDataComputing, InternetofPeople,andSmartWorldCongress
IEEE,2017：794-800
[13*ShiK,$i$,$iu H,etal Animproved KNN textclassi-ficationalgorithmbasedondensity[C*//IEEEInternational ConferenceonCloudComputingandInte l igenceSysterms,2011 [14*$IU Haifeng,$IU Shousheng,SU Zhan Sample clipping andweightingmethodfortextcategorizationbasedonlocation [J*ComputerEngineeringand Application,2015,512)：131-135(in Chinese).[刘海峰，刘守生，苏展.基于位置的文本分类样本剪裁及加权方法[J*.计算机工程与应用, 2015,512)：131-135*
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议