基于中心向量KNN算法的改进

王兆龙

(安徽文达信息工程学院)

基于中心向量KNN算法的改进

王兆龙

(安徽文达信息工程学院)

针对KNN算法在中文文本分类时计算开销大的问题，在已有改进算法的基础上进行了更深入的研究，提出改进的基于中心向量KNN算法.算法首先引入基于密度的思想对训练样本进行调整，同时计算各类别的类中心向量.在保证类中心向量准确性的前提条件下，使分类阶段的复杂计算提前到分类器的训练过程中.实验结果表明，该算法在不损失精确度的情况下，提高了分类实时性.

文本分类;多级分类器;类中心向量

0 引言

随着信息技术和社交媒体的快速发展，各类文本信息之间边界模糊、类域交叉,判断信息属性的难度日益增加，因此人们渴望有效的工具对所拥有的文本信息快速准确分类.文本分类作为一种处理海量信息的关键技术，是在既定的训练模型下，根据内容自动地将新得到的、未知类别属性的目标文本划归到所属的一个或多个类别中[1]，由此提取的知识在提高企业合作兴趣和突显商业优势方面有重要的意义.

目前国内外关于文本分类算法的研究已取得一定成果，国内学者也相继提出了许多实用的文本分类改进算法，并通过实验验证了其有效性.文献[2]通过增加逼近向量的个数建立了基于SVM的级联结构分类器进行人脸的检测；文献[3]为了提高处理大规模数据的速度，提出了聚簇消减大规模数据的支持向量分类算法；文献[4]利用Z-order曲线和多重Hilbert曲线，将d维点集映射到一维空间，然后沿着曲线进行一定范围内的比较查询来找到最近邻的K个邻居；文献[5]针对KNN算法在处理大数据时的不足提出了多层差分分类算法.该文在学习相关算法的基础上，提出改进的基于中心向量KNN算法[6]，并通过仿真实验证明该文提出的算法.

1 KNN算法和基于密度的训练集调整方法

1.1 KNN算法原理

KNN分类算法是一种思想简单、容易操作且应用比较成熟的方法.其基本过程描述如下：将训练样本映射于向量空间中的点，在给定训练样本集D和遇到待分类文本x的情况下，通过相似度计算并排序，从训练集D中找到与x距离最近的K个文本，最后根据这K个文本所属的类别来判定x的类别归属.

虽然KNN分类算法是经典的文本分类算法，具有诸多优点，但是KNN算法也存在不足之处：①若训练样本分布不均匀，包括样本数目不等或样本影响范围不同，都会造成分类准确率的下降[7].在实际应用中，大类别样本在密度上的优势容易影响分类的准确率[8].②因为KNN算法具有很强的“懒惰性”特征[9]，如果遇到训练样本规模较大的情况，那么在分类阶段就会造成很高的计算开销和系统负荷，严重影响分类器的整体性能.

1.2基于密度的KNN训练集调整方法

在经过了类内样本密度的相关计算后，根据样本的分布密度及数目，对训练样本进行调整时，分别对处于类边界区域和类内区域的样本进行处理.由于裁减训练集规模是以减少分类计算复杂度为主要目标，因此对样本调整时主要对高密度区域的样本进行裁减.具体方法如下：

①类边界区域：对任意一个处于类边界区域的样本X，通过计算分析判断X所处的密度区域，如果X处于高密度区域，就裁减掉从样本X是高密度可达的样本，使其降为均匀密度区域；若是处于均匀密度或低密度区域则保留不变.

②类内区域：对任意一个处于类内区域的样本X，若样本密度高于类内期望密度，需裁减掉从样本X是高密度可达的样本，直到|Nε(x)|=LowPts；否则，样本X所处区域已符合标准，故不作处理.

类边界区域的划分是分类中的关键性问题，在此讨论该区域的划分方法：

(1)该文用整个训练集的平均密度来确定给定的平均样本数AvgPts，即对于样本集D和给定的领域半径ε，即:

(1)

(2)设DK(X)表示样本X的第K个近邻到X的距离，把D在平均样本数为AvgPts下的平均领域半径定义为ε，即：

(2)

一般情况下取AvgPts的值为6%～8%的AvgPtsε(0)时效果较好，由于样本向量的产生过程不同，因此ε值的差异较大.结合训练集的规模和特点，最终确定合适大小的类边界区域和类内区域.但是如果处于类内区域且处于高密度区域的样本太少，这样也会丢失待分类文本类别判定的部分信息，因此，在对类内区域样本裁减时，使用了一个小于AvgPts的样本数LowPts来作为类内区域的样本期望密度，从而使裁减后的类内区域密度低于类边界区域密度，最终在不影响分类精度的情况下，减少了分类的计算量.

2 改进中心向量KNN算法

类中心向量法[10-11]基本思想描述：在训练分类器时，首先计算训练集中所有类别的中心向量.在测试文本分类时，直接计算待分类文本向量与每个类中心向量的相似度，然后将其归入与之相似度最大的那个类中.计算公式为：

(3)

其中，Nk表示第k类中文本的数目，wij为特征词tj在文本dj中的TFIDF权重[12-13].

在此，对类中心向量法进行更深入的计算研究，把类别判定向前推进一步，在得到待分类文本向量与每个类中心向量的相似度值后，对其按从大到小进行排序，选取前m(参数m由实验确定)个类别中的样本组成新的小规模训练样本集，然后使用K近邻算法对待分类文本进行二次类别判定，以确保最终分类结果的准确性.算法具体步骤为：

(1)计算训练集中各类的中心向量,保存计算结果并建立初级分类器.如图1所示中的训练集共有5个类，且把各类的中心向量分别记为C1、C2、C3、C4、C5.

图1 类中心向量

(2)计算待分类文本X与步骤(1)所得结果的各个类中心向量的相似度，并将这些值按从大到小进行排序.然后进一步选择前m(1

图2 取类C1和类C2中的文本作为新训练集

(3)在上述所得的结果集上，使用传统KNN算法对待分类文本X进行最终类别的判定.假设K=4，则X属于类C1，如图3所示.

图3 在新训练集上使用KNN算法

上述算法是以单个待分类文本为例对算法思想进行描述，在实际进行中文文本分类时，待分类文本数量很多，其算法思想与上文描述一致，不过具体的分类计算过程会复杂很多.

3 实验结果与分析

采用2013年李教授发布的中文语料库[14]作为实验数据.共20个类别，answer.rar为测试语料，9833篇文本；train.rar为训练语料，9804篇文本.采用中科院研发的汉语分词系统ICTCLAS 3.0对实验文本数据进行处理，还用到Weka工具的部分功能.具体仿真实验结果及分析如下.

3.1训练集调整前后裁减比例及分类性能

(1)训练集调整

为了验证不同分布密度的类别样本的调整效果，该文选取了两个分别取自train.rar和answer.rar的训练集A和B，共9个类别2160篇文本.为了能够很好的验证训练集的调整效果并形成明显的对比，此处采用控制变量的方法来选择另一个训练集B，训练集B与A有相同的类别总数和文本总数，但是训练集B的每个类别都有240篇文本，因此训练集B的分布很均匀，而训练集A中样本在各个类的分布差别较大.训练集A见表1.

表1 A训练集信息

使用上述的训练集调整算法进行实验.取AvgPts=10，分别取LowPts的值为 1～10，调整训练集实验以裁减训练集中的高密度区域从而降低分类计算复杂度为主.使得样本分布不均匀的训练集A的裁减比例大于样本分布均匀的训练集B，但是训练集B也有较低比例的裁减.

(2)训练集调整前后分类性能

为了评估整体的分类效果，该文仿真实验采用宏平均准确率和召回率，对训练集调整前后的分类性能进行了测试，随机选取answer.rar测试语料中的1360篇文本，通过多次实验，K=23、LowPts=7、8时分类效果最好.实验数据见表2.

表2 训练集调整前后分类准确率和召回率对比

实验数据表明，在使用调整后的训练集进行分类时，确实降低了分类的计算复杂度而且没有牺牲分类的准确率，如果LowPts取合适的值，还能小幅度的提高分类的准确率.这就保证了下一步计算类中心向量的准确性，进而能够保证在初级分类后保留下来的训练集是基本准确的，才能保证进一步使用KNN分类算法的正确性，减少分类阶段的时间开销.

3.2算法实时性

为了讨论在最好改进效果条件下，改进分类算法在时间开销上的节省情况.在以下实验中，改进的分类算法分别与传统的KNN算法和文献[5]中提出的差分多层KNN算法(DM-KNN)进行了比较，为了保证比较的准确性，选择在相同的数据集上进行分类并记录其分类用的时间.其中取m=4，K=16，得到以下实验数据,见表3.

表3 三种分类模型的分类时间比较

由表3中的数据可得，多级分类KNN算法比传统KNN算法在时间开销上节省了89635ms，即节省了52.86%.如果训练集中有n个样本点，经数据清洗后取s个特征项，假如有t个文本要被分类，则KNN算法的时间复杂度为O(nst).本实验中训练集的类别数N=9，当m=4时，舍去的类别数为5N/9，平均裁减掉的文本总数为5N/9，时间复杂度降为O(4nst/9)，时间节省应该为55.6%，而实际的实验结果为52.86%.深入分析误差原因，算法在训练阶段增加了训练集的调整和类中心向量的计算过程；这些过程所花费的时间致使实际节省的时间低于理论值.另一方面，多级分类KNN算法比DM-KNN算法多用了220ms，相差不大，分析原因也如上所述，这也间接的体现了多级分类算法的先进性和前沿性.

4 结束语

KNN分类算法的时间复杂度由训练集规模决定.该文由于建立了类中心向量初始分类器，因此随着调整后的训练集规模的减小，时间复杂度也会随之减小，分类速度就会得到提高.在计算训练集的类中心向量之前，引入了基于密度的思想对训练集进行了有效的均匀性调整，保证了类中心向量的基本准确性，进而使KNN改进算法能够实现二级分类的目标，在不损失分类精度的同时，显著提高了分类器的分类速度.因此，该文在保证KNN算法分类性能的基础上，不仅使分类的计算复杂度有一定程度的缩减，说明了对KNN算法的改进是有实际意义的.

[1] Fabrizio S.Machine learning in automated text categorization[J].ACM Computing Surveys,2002,34(1):1-47.

[2] Romdhani S,Torr P,Scholkopf B,et al.Efficient face detection by a cascaded support-vector machine expansion[J].Pattern Recognition,2004,3175:62-70.

[3] 陈光喜,徐建,成彦.一种聚簇消减大规模数据的支持向量分类算法[J].计算机科学,2009,36( 3) :184-188.

[4] Hanan Samet.Depth-first k-nearest neighbor finding using the maxnearestdist estimator[C]//Proceedings of the 12th International Conference on Image Analysis and Proceeding,2003:486-491.

[5] 耿丽娟,李星毅.用于大数据分类的KNN算法研究[J].计算机应用研究,2014,31(5):1342-1344.

[6] Chakrabarti S,Joshi M,Tawde V.Enhanced topic distillation using text markup tags and hyperlinks[C]//ACM SIGIR,2001.

[7] García V,Alejo R,Sánchez J S,et al.Combined effects of class imbalance and class overlap on instance-based classification [A] // Intelligent Data Engineering and Automated Learning-IDEAL 2006 [M].Berlin,Heidelberg:Springer,2006:371-378.

[8] Xia Zhan-guo,Xia Shi-xiong,Cai Shi-yu,et al.Semi-Supervised gaussian process classification algorithm addressing the class imbalance [J].Journal on Communications,2013,34(5):42-51.

[9] 曹勇.中文Web文本分类技术研究[D].厦门:厦门大学,2007.

[10] 郭茂.基于类中心向量的文本分类模型研究与实现[D].大连：大连理工大学,2010.

[11] Ling Jie,Zou Li-na.An improved KNN algorithm for text classification based on clustering center vector[C].IEEE International conference on Cyber Technology in Automation,Control,and Intelligent Systems(CYBER),2012.

[12] 李媛媛,马永强.基于潜在语义索引的文本特征词权重计算方法[J].计算机应用,2008,28(6):1461-1466.

[13] Zhu Shan-zong,Liu Yuan-chao,Liu Ming.Research on feature extraction from chinese text for opinion mining[C].International Conference on Asian Languages Processing,2009.

[14] Li Rong-lu.Computer information and technology department of fudan university center for international database natural language processing group.[EB/OL].[2013-5-23],[2015-6-10].(in Chinese)

Abstract:In order to solve the problem of high computational cost in Chinese text classification,a deep research on the improved algorithm based on KNN algorithm is made,and an improved algorithm is proposed based on KNN algorithm.Firstly,the density of the training samples is adjusted,and the class center vectors are calculated.Under the premise of ensuring the accuracy of the center vector,the complex computation in the classification stage is advanced to the training process of the classifier.The experimental results show that the proposed algorithm improves the classification performance without losing the accuracy.

Keywords:Text classification; Multi-stage classifier; Class center vector

(责任编辑：李家云)

TheImprovementofKNNAlgorithmBasedonCenterVector

Wang Zhaolong

(Anhui Wenda Information Engineering College)

TP391

A

1000-5617(2017)02-0018-04

2017-01-01