基于K中心点和粗糙集的KNN分类算法

文 武，李培强

(1.重庆邮电大学 通信新技术应用研究中心，重庆 400065；2.重庆信科设计有限公司，重庆 400065)

0 引 言

目前文本分类[1]的方法大多是基于统计学习的，运用机器学习领域的分类模型进行自动分类[2]，常用分类模型有：Rocchio算法[3]、朴素贝叶斯(NB)[4]、支持向量机(SVM)[5]、K近邻(KNN)[6]等。其中对KNN算法来说，由于其理论成熟，思想简单，而且对数据没有假设，准确度高，在文本分类领域得到了广泛的应用。Nirmala Devi M等[7]提出了一种将利用K-means算法去除不完整和模糊数据的方法，以此来提高分类的准确率和效率。张雪萍等[8]将K-Medoids与MapReduce平台相结合来提高文本的分类速率，提高了文本的分类效率。罗贤锋等[9]提出了一种基于K-Medoids聚类的样本裁剪方法，先通过K-Medoids算法对文本聚类，并通过计算每个样本的相似度与阀值对比，如果相似度小于设定阀值，则将该文本直接删除，然后运用KNN算法对待测样本进行判别，提高了分类速率。谢娟英等[10]提出了基于K近邻的密度峰值的搜索分类算法，通过搜索和发现样本的密度峰值，以峰值点样本作为初始类簇中心，最终利用K近邻算法对待测文本进行分类，提高了文本分类的准确性。黄贤英等[11]提出了利用文本词性相似度和KNN算法结合的方法对文本数据进行分类，通过对文本数据词性相似度的计算，分给每个词性信息的不同的权重值，最后利用KNN算法对待测文本类别进行判断，提高了短文本分类的准确率。

从上述研究发现，现在部分分类算法主要是利用文本相似度或者结合某种平台进行文本分类，只是单一考虑了文本分类的准确率，没有同时顾及到文本分类的准确率和分类速率。基于此，本文在传统的KNN算法的基础上，提出基于K中心点和粗糙集的KNN文本分类算法。该算法的主要思想是：首先通过K中心点算法对文本数据进行聚类，然后利用粗糙集理论对已分类的簇集进行分割，得到上下近似集和边界区域近似集，仅对分割得到的边界区域数据通过KNN算法进行判断最终的所属类别，并对无用信息进行了筛选，这样不仅大大减少了文本的计算量，提高了文本分类速率，同时也保证了文本分类的准确率。

1 相关工作

1.1 K最近邻算法

K近邻算法(K-nearest neighbor，KNN)是分类算法中的一种，是基于空间向量模型[12](VSM)的分类算法之一。KNN通过计算待测样本数据与训练样本数据中不同类别数据点间的相似度，然后根据相似度大小对待测样本进行分类。即通过与待测样本点最邻近的K个样本点来对待测样本进行分类和预测。对一文本训练集S，该训练集有m个类别，S的总文本数为N。C1,C2，…,CN，S的总文本数为N。在训练阶段对训练集S进行分词降维，然后将训练集文本表示为特征向量：Di={X1，X2，…,Xn}T(0

KNN算法的具体步骤可描述为：

(1)对文本训练集进行分词。

(2)提取特征词并降维。

(3)利用VSM将训练样本向量化。

(4)对待测文本进行(1)～(3)处理。

(5)利用余弦相似度公式计算待测文本与训练文本的相似度，公式为

(1)

(6)选出与待测文本D相似度最大的K个文本组成样本集。

(7)根据(6)中得到的K个最近邻样本集，计算测试样本D属于每个类别Cm的权重W，计算过程如公式所示

(2)

其中，类别属性函数如公式所示

(3)

(8)将待测样本D归入到权重最大的类别Cm中。

1.2 K中心点样本剔除算法

在文本分类中，当对较大的数据样本进行聚类时，传统的聚类算法如K-Means算法虽然聚类精度高，但只能在簇的平均值确定的情况下才能使用，而且通过均值得到的中心点存在偏差，准确性较低[13]。而K中心点算法[14]不采用簇中对象的平均值作为参照点，而是选用簇中位置最中心的对象，即中心点作为参照点，在分类过程中具有较强的鲁棒性。

K中心点算法的主要思想是：对于样本训练集S，首先将其划分K个不同的类簇，为每个簇随机选择选择一个样本对象作为初始簇心Oi(0

(4)

1.3 粗糙集理论

粗糙集(rough set)理论是波兰学者Z.Pawlak提出的处理模糊不清和不确定性问题的新型数学理论。该理论能够在浩瀚的数据中找出有用的信息,将信息去粗取精,在缩减计算量的同时,也能提高分类的准确率,这也是本文选用粗糙集理论来进行文本分类的价值所在，具体粗糙集理论请参见文献[15]。

定义IND(P)是数据库P=(U,R)中所有等价关系的簇，对于一个子集对象集合X⊆U和等价关系R⊆IND(P),可得出集合X关于等价关系R的下近似集R下(X)和上近似集R上(X)的定义分别为式(5)和式(6)所示

R下(X)=U{Y⊆U/R|Y⊆X}

(5)

R上(X)=U{Y⊆U/R|Y∩X≠φ}

(6)

其中，下近似集R下(X)表示由关系R得出的U中一定属于集合X的所有对象的集合；上近似集R上(X)表示由关系R得出的U中可能属于集合X的所有对象的集合。下近似集R下(X)和上近似集R上(X)可以定义3个概念，即集合X的正域、负域和边界域，计算公式分别为式(7)～式(9)所示

POSR(X)=R下(X)

(7)

NEGR(X)=U-R下(X)

(8)

BNR(X)=R上-R下

(9)

其中，正域POSR(X)即下近似集R下(X)；负域NEGR(X)表示在U中肯定不属于集合X的所有对象集合；边界域BNR(X)表示在U中不能明确判断是否一定属于或者一定不属于集合X的所有对象集合。

2 KRS-KNN文本分类算法

2.1 模型表示-向量空间模型(VSM)

空间向量模型(vector space model，VSM)，VSM是一种简便、高效的文本表示模型[16]。VSM的关键在于怎样选取较大相似度的特征词和有效的计算权重值。在向量空间模型中，一篇文档由提取出的特征词和该词权重由向量的形式表示出来，权重的大小，反映了特征词在一篇文档中的地位；而在分类阶段之前，一个文档数据集的类别都是由带有权重的特征词所表示。本文采用权重计算公式TF-IDF[17](term frequency-inverse document frequency)，在文本分类中TF-IDF是一种经典的特征词权重值计算方法，且一直受到人们欢迎。

根据TF-IDF的基本思想，在待测文本D中，特征词ti的权重计算公式如公式所示

(10)

(11)

其中，特征词ti在文档中出现的频率用tfi表示，训练集中所有文档的数目用N表示，包含特征词ti的文档出现的频率用dfti表示。

2.2 KRS-KNN算法

KRS-KNN算法的主要思想是：对于一批新的文本数据，首先对该数据集进行预处理，利用K中心点算法算法对其进行聚类，然后调用粗糙集理论聚类的簇集进行上下分割，根据粗糙集理论的判断原理对分割得到的数据进行判断，对于边界区域的文本数据需要通过KNN算法进一步判断其所属类别。KRS-KNN算法的分类流程如图1所示。

图1 KRS-KNN算法分类流程

(1)首先将数据集分为测试集和训练集，并采用中科院分词系统ICTCLAS对中文文档进行分词、去停用词。

(2)采用文档频率方法对特征降维。

(3)利用TF-IDF权重公式计算特征词的权重值，进而由VSM对特征词向量化。

(4)将(3)中处理过的数据集通过K中心点算法对其聚类为簇，并将最后每个簇类中心的代价值设为阀值Ei。

(5)将(4)中每个簇类的非簇心样本计算它们在各自类簇的相异度并与最后设定的阀值比较，将相异度大于阀值的数据样本点从其所属类别中剔除。

(6)对于(5)中得到的每个簇，通过式(5)、式(6)分别计算这些簇的上下近似集，并运用式(7)、式(8)、式(9)计算每簇的正域、负域和边界域。

(7)对于已经分割好的簇，根据粗糙集理论判断数据样本i属于哪一域。

1)如果数据样本i出现在K-Medoids类簇正域即下近似集，则该样本一定属于该类簇，无需再判断。

2)如果数据样本i出现在K-Medoids类簇负域，则直接将数据样本i从其所属类簇中删除。

3)如果数据样本i出现在K-Medoids类簇边界，则转到步骤(8)执行。

(8)运用式(1)计算数据样本i与K-Medoids的簇类中心Oi的余弦相似度，并有相似度大小计算出数据样本i与所有类簇中心Oi的K个最近邻。

(9)根据数据对象i的K个最近邻，由式(2)计算待测文本数据对象i属于K-Medoids类簇的权重W，并将数据样本i分到权重最大的类别Cm中。

KRS-KNN算法的优势：在基于K-Medoids算法的基础上，保证了文本分类的准确性，将代价值较大的数据样本剔除降低了文本的数据规模，减少了计算量，同时在运用粗糙集理论时对已经确定类别的数据样本不再对其判断其所属类别再一次减少了文本数据的计算规模，缩减了文本的处理的计算时间，有效提高了文本的分类效率。

3 实验结果分析

3.1 实验环境与评估指标

针对提出的KRS-KNN文本分类算法进行了实验验证，本实验平台采用Windows 7 64位操作系统、CPU为Intel(R)-i5-4210M-2.6 GHz、物理内存为4 G和Eclipse集成开发环境，实验数据来自于搜狗实验室，选取其分类语料库的标准数据集-SogouC作为样本数据，其中包括财经、互联网、健康、教育、军事、旅游、体育、文化、招聘9个类别，各1990篇共17 910篇文档。对分类效果的评价采用精确率(precision)、召回率(recall)和综合评价指标(F1-measure)。定义如下

(12)

(13)

(14)

其中，TP表示分类时将正类预测为正类的数目，FN表示将正类预测为负类数，FP将负类预测为正类数，TN为将分类预测为负类数，精确率衡量的是类别的查准率，召回率衡量的是类别的查全率，F1-measure对查准率、召回率进行综合考察，以及对它们的偏向程度，且F1综合了P和R的结果，所以当F1越高则越能说明实验方法比较有效，和分类器具有较强的分类能力。

3.2 K值的确定

K值的大小对分类准确率和分类速率的有较大影响，为保证分类器具有最大的分类能力，对K值的选取进行了实验。在文献[18]中，先设定K值为9依次递增来选取最优，最后通过平均值来确定K值，本文通过交叉验证的方法得出由最优K值，同时F1值综合了精确率、召回率，所以本文选取F1值与K值的关系进行实验验证。

由图2可以看出F1值与K值选取的关系：

(1)当0

(2)当K≥20时，F1值随着K值的递增而降低。

由此次实验结果可以得出最优K值，即K值取19时，分类器的分类效果最优。

图2 K值与F1值关系

3.3 实验结果分析

为验证本文提出的KRS-KNN算法的有效性，在保证同样数据集的情况下进行了10次实验，与传统的KNN分类算法和基于K-Medoids聚类改进的KNN文本分类算法进行了比较，表1给出了在同一数据集下3种不同算法分类耗时时间。利用式(12)、式(13)、式(14)分别计算出精确率、召回率和F1值，见表2。

通过表1可以看出在同一数据集下提出的KRS-KNN算法的时间消耗比传统的KNN算法和基于K-Means的KNN算法要少的多，与传统的KNN算法相比平均减少了274 s，与基于K-Means的KNN算法相比均值上减少了116 s，发现提出的KRS-KNN算法与基于K-Means的KNN算法时间减少的幅度没有比传统的KNN算法的大，这是因为在聚类完成后为了保证分类的准确性，在粗糙集上下割分时还需要对样本对象进行类别的划分，区分样本对象的正负域和计算边界域，这需要消耗一定时间，但从总体上来说分类速率得到了明显的提升，说明了本文提出的算法的有效性。

表1 3种算法的消耗时间对比

从表2对3种算法进行对比可以看出，KRS-KNN分类算法在精确率、召回率、F1值上都有明显的提升。其中，提出的KRS-KNN算法相比于传统的KNN算法和基于K-Means的KNN算法分别在准确率上平均提高了4.19%、3.36%，除了在军事、体育、财经少数类别上，召回率都得到了提高，平均值上相比于其它两个算法召回率分别提高了1.74%和3.06%。从F1值上来看，KRS-KNN算法在财经上比传统的KNN算法降低了0.57%,在文化上降低了9.63%，这主要是因为文化、财经类内容广泛，特征词权重值相差无几不易于区分，而体育类则内容相对集中，具有较高的区分度，所以相比于两个算法KRS-KNN算法在体育类的F1值上提升效果明显，但从总体上来说F1值相比于其它两个算法来说都得到了一定提高，分别提高了0.15%、1.43%，总体上提高了文本的分类效率。

表2 实验结果对比

4 结束语

本文针对KNN算法在文本分类中，分类效率受计算相似度时间消耗大导致分类效率低下的问题，提出了基于K-Medoids和粗糙集的KRS-KNN文本分类算法。该算法首先通过K-Medoids算法对文本数据集聚类成簇，然后利用粗糙集理论对已分好的簇进行上下近似分割，对分割得到的类簇进行判断处理，最后利用KNN算法对处理后的样本数据做最后的类别判断。通过实验结果可知本文提出的KRS-KNN算法在保证较高的准确性和鲁棒性前提下，能有效提高分类模型对文本数据的分类效率。然而，通过对比实验发现，分类效率虽然能得到有效提高，但在对数据对象运用代价函数对相异度较大的数据样本剔除和利用粗糙集理论进行数据处理时，会导致一定的数据信息丢失，怎样在保证数据信息不丢失的情况下更有效地提高文本分类速率是下一步的工作重点。