基于类别信息熵加权的MKNN算法

陈雪云*，刘艳芳，柯婷，张剑楠



基于类别信息熵加权的MKNN算法

陈雪云*，刘艳芳，柯婷，张剑楠

(龙岩学院信息工程学院，福建省龙岩市 364000)

针对MKNN算法对类属性数据处理简单的问题，引入信息熵作为处理类属性数据的相似性度量，进而引入类别信息熵的概念。对同一类型的类属性数据根据其类别信息熵权重的大小，把数据集的记录进行分类进而得到测试结果。实验结果验证了该算法的有效性。

数据挖掘；MKNN；类别信息熵；类属性

引言

数据挖掘算法有分类算法、聚类算法、回归等这几类。每一类的分析侧重点和其优势各有差异。分类是通过分析已知数据集数据特征为其标签，再通过与此标签和对未知数据集的对比从而进行分类，分类是数据挖掘中的一个必不可少的研究方向。1968年Cover和Hart[1]提出的K近邻(KNN, k-Nearest Neighbor)算法是最简单的数据挖掘分类算法之一，同样也是最好的文本算法之一。由于它的“简单”，被称为懒惰算法，因此可以改进的地方很多。比如分类速度慢，属性相同的权重影响了准确率。直到目前为止，有很多学者对它进行过研究并提出了很多改进方法。例如：张著英等[2]提出将粗糙集理论应用到KNN算法中，实现属性约简以解决KNN分类效率低的缺点；周靖[3]等提出一种采用类相关度优化距离的KNN改进算法，提高了KNN的分类性能；戚孝铭[4]通过聚类手段进行去噪处理，并且通过加快K近邻的搜索速度提高KNN算法的分类效率；肖辉辉[5]等利用属性值对类别的重要性对KNN进行改进，提高了分类准确性；耿丽娟和李星毅[6]对已知样本根据类域进行分层，大大降低了无效的计算；郝胜轩[7]等针对KNN算法对缺失数据的填补效果会因为原始数据中存在噪声而受到严重影响的问题，提出了ENN-KNN消除噪声最近邻对填补结果的影响；苏毅娟等[8]创新性地通过线性复杂度聚类方法对大数据样本进行分块，然后在测试过程中找出与待测样本距离最近的块，并将其作为新的训练样本进行K最近邻分类，大幅度地减少了K最近邻算法的测试开销，使其能在大数据集中得以应用；康丽萍[9]等提出基于加权KNN的融合分类方法以解决将语义级融合算法应用于不同分类方法时由于分类决策基准不统一导致分类结果不理想，大幅降低融合分类性能的问题；刘继宇[10]等针对粗糙集训练过程中从未遇到过的样本的分类问题进行了探讨,根据条件属性的重要性确定加权系数，采用加权KNN的方法来解决无法与决策规则精确匹配的样本分类问题。Liu和Zhang[11]提出的互K近邻算法(MKNN)很好的解决了K最近邻(KNN)存在的伪近邻问题。MKNN可以很好的消除异常数据和提高质量，因为该算法通过更好地丢弃训练样本中可能会有的噪声数据从而实现克服KNN中存在的伪近邻问题，所以说MKNN是基于在KNN的基础之上，解决了KNN伪近邻问题的干扰，而改善了算法的性能。但是两者的近邻选择都取决于相似性度量的选择，而相似性度量是数据集中分类分析的决定性因素。传统的相似性度量大多适合数值型属性，MKNN和传统的KNN一样都适合在数值型领域。对于类属性数据也有学者提出了改进的方法。陈雪云[12]等提出的GwMKNN算法引入了类别基尼系数的概念来处理类属性数据，用基尼系数统计某一类属性中不同值分布对这个类的贡献度作为此类属性的权重,并以此作为估算不同样本之间的相似性度量对MKNN进行优化,扩宽了MKNN的使用面。

根据上述研究内容的有关分析，提出的基于类别信息熵加权的MKNN算法（以下简称EwMKNN)主要研究的是类属性数据的分类，是在MKNN算法基础上衍生过来的，EwMKNN算法中引入信息熵用来作为处理类属性数据的相似性度量。现在同样也有很多关于信息熵的研究算法，例如：王磊[13]利用熵来度量新文本对于已分类文本集合的贡献度大小，并以此熵值来判断文本归属的类；甘苏婷[14]在信息熵理论的基础上利用数据挖掘技术构建决策支持系统的信息组织机制，信息熵的利用可以度量决策支持系统中信息组织的规律性程度；陈曦[15]等利用信息熵原理定义了不同类型的谣言信息熵，并通过对谣言传播计算机仿真结果的熵值分析，验证了谣言信息度量方法的可行性；Li[16]等将最大信息熵模型应用于各种自然语言的语义分析任务中，进而实现舆情分析；朱佳佳[17]等使用改进的SVM多分类器对熵值量化后的流量进行分类判决,根据分类结果捕获异常；魏琴芳[18]等将信息熵和遗传算法应用于检测过程所用比对库的训练，采用异常检测和特征检测结合方法进行入侵检测；潘瑞林[19]等提出基于α信息熵的属性重要度度量,并以此构建混合属性约简算法。

根据这些算法的分析，得知信息熵有着很好避免噪声数据的干扰的效果，可用来作为处理类属性数据的相似性度量，以更好地优化MKNN算法,提高其对类属性数据处理的效率。为研究类属性型的数据提供了更加准确的分析方法。

1 基本概念和定义

1.1 伪近邻

K近邻是根据测量不同特征值之间的距离分类，首先需要在训练数据集中找到K个最近邻的样本，类别由这K个近邻中占最多的样本的类别决定，若k值取得较大就会出现很多干扰的样本，影响了分类准确率。通过引入互近邻的概念，获取更加真实的样本，去除掉干扰的或者“假”的邻居，即伪近邻，依据真实邻居的标签信息分类，丢弃噪声数据，从而提高了预测结果的准确性，以及分类模型的预测性能。

1.2 信息熵

熵可以说是个物理单位因为最早是表示热力学，其值表示的是一个系统的混乱程度，然而在信息理论中的这个熵也可称信息熵，可用来表示某个随机变量的不稳定性程度。可以有效避免噪声数据的干扰。

定义1信息熵

假定X是一个随机变量，p(x)表示变量X取值为x的概率，那么它的不确定性程度可以表示为信息熵E(X)形式，则：

定义2集合D的信息熵Entropy(D)[13]

公式中Pi表示集合D中属于Ci的比例。

定义3类别信息熵[12]

在文献[12]中已经提出过类别信息熵的概念，类别信息熵就是在香农信息熵的概念上对其延伸和扩展，使其适应对多维类属性数据的处理，设定现有一个多维的类属性数据集，D表示一个多维的样本数据集，即，是一个r维的数据集合，其中表示的是的数据集的已定义的标签类别，，q是指样本集中的类别数，代表中的样本数，表示在类中第个属性上的不同取值的次数，其中。那么类别信息熵的公式可表示为:

其中，（1-4）

将计算得到的信息熵与公式3-5的结果相乘后得到一个规范化的结果。

经过以上的分析，可以了解到，关于样本中的某一个属性，通过对其有着一样的类别标识，再通过类别信息熵的统计和计算：若其中某一个类别在这个属性的对于一样的属性值的越大，那么其通过类别信息熵处理的权重越大，则属于该类别的机率就越大。如果类别信息熵越小，则其计算所得的权重越小，属于该类别的机率就会更大。

2 EwMKNN的算法步骤和基本实现

通过在MKNN算法的基础之上引入类别信息熵的概念，并将类别信息熵作为一种新的权重，进而对样本进行分类。

EwMKNN的算法实现：

算法1：计算类别信息熵（CaculateCategory’s Entorpy）

输入：训练样本集C

输出：当j属性属于Nominal类型时，其不同类别信息熵E(k,j)；

Begin

Step 1：声明训练样本数据集trainIns,不妨选取数据集C中标号为k的样本集；

Step 2: 遍历所有训练样本数据集，再对其进行操作；

Step 3: 计算出训练数据样本trainIns中Xjl在第k类样本中出现的次数，即fk(Xjl)的值对样本集trainIns进行统计，即nk的值；

Step 4：依据公式（4）和fk(Xjl)的值，nk的值，算出Pjl(k)的值，表示trainIns中某个属性的某个值Pjl(k)出现的概率；

Step 5：依据公式（3）计算出类别信息熵E(i,j),最后通过和相乘得到规范化的结果；

Step 6:返回E(i,j)的值作为权重；

End

算法2：计算样本和样本之间在j属性上的距离（CaculteEntoryDistance）；

输入：两个样本集例如：Dt（Dt为测试样本）和Di,属性j,权重E(k,j)；

输出：两个样本在j属性上的距离EnDis(Djt,Dji)；

Begin

Step 1:初始化EnDis(Djt,Dji)=0；

Step 2:遍历样本中的所有属性，若属性是Nominal型，则接着判断样本Dt和样本Di是否相等，如果相等则返回EnDis(Djt,Dji)=0；反之则返回Di所在的类别信息熵，且EnDis(Djt,Dji)=EnDis(yi,j)；

Step 3:若数据类型不是类属性数据则EnDis(Djt,Dji)=（Djt-Dji）2

Step 4:最后返回EnDis(Djt,Dji)

End

算法3:类别信息熵分类算法(EwMKNN)

Begin

输入：训练样本集C,样本和样本之间在j属性上的距离EnDis(Djt,Dji)，待分类样本Dt,近邻数K

输出：预测待分类样本Dt的类别St

Step 1:声明训练样本Di和测试样本Dt,并初始化Dt的近邻集合为空；

Step 2：用CaculteEnDis计算待测试样本Dt与各训练样本Di之间的距离CaluteEnDis(Djt,Dji)，i={1,...,n}；

Step 3:依据上一步骤的计算结果作为判定数据集中样本是否为Dt的K近邻的标准，获得近邻集Nk(Dt),k即近邻数；

Step 4: 重复上面两步操作，然后找出Dt的互k近邻：先设Dt近邻集合Nk(Dt)中的一个近邻为Di，再从数据集C中找出Di的近邻集合Nk(Di)，接着判断Dt∈Nk(Di)是否为真，若为真则将Di的类别信息Si添加到Dt的类别信息集合Y(Dt)中；

Step 5：最后对上一步骤的结果进行统计，将最大类别数作为待测样本Dt的类别标签；

Step 6:返回最后的结果St，即Dt的类别标。

End

3 实验的结果与分析

3.1 实验数据的基本信息

为了验证算法的性能，选择在UCI[20]的数据集中选取10个数据集进行检测，数据集的详细信息如表1所示。

表1 数据集基本信息表

3.2 实验结果

为了验证EwMKNN的可靠性，将它与KNN，MKNN，EwKNN，GwMKNN这几个算法一同进行对比检验，其中EwKNN是只把类别信息熵应用于KNN上的处理方法。主要用了10-折交叉检验法，10-折交叉检验是通过将数据集分成10个小的子集，然后将这些子集中挑选一个出来做测试样本集，10个子集轮流做测试样本集，最终得到的结果取均值做最终测试结果，要保证上述几个算法检验过程中用的是同一数据集和测试样本集。测试时，k值选择可以是20以内的质数，这里k取3。检测分析的结果如表2所示。

表2 分类精度对比

根据表2的数据可以很好的看出，MKNN的准确率是比KNN的要高，在16个数据集中有12个数据集都显示其优越性，然而在对MKNN算法加以改进的基于类别信息熵加权的MKNN算法EwMKNN在7个数据集的测试中都显示出在所有算法中最高的准确率，GwMKNN算法的准确率也是比较好的，文献[9]中非常清楚的提出GwMKNN算法是引入的基尼系数的概念，通过对距离加权来进行对数据集分类的算法，在处理hayes-roth，labor，promoters数据集时，还显示出更加好的准确率。从数据集的角度来看，在数据集audiology，dermatology，zoo上都可以体现出EwMKNN算法在处理多类别数据时比EwKNN，GwMKNN这两种算法有更高的准确率。在处理类别较少类属性较多的数据集时，虽然EwMKNN算法的准确率没有比MKNN算法高出很多，也证明该算法还需要经过改善，但也在总体方面说明了MKNN改进后的EwMKNN算法是有效的。

4 结束语

提出的基于类别信息熵加权的MKNN算法是首先要在已经解决了KNN算法伪近邻问题的MKNN算法上，进行对权重的改进，互k近邻算法（MKNN）准确率在KNN基础上本来就有提高，但在处理类属性数据仍表现出有些不足之处。引入类别信息熵后，用信息熵加权的方式提高类属性数据分类的准确率。在数据集上的检测结果说明了EwMKNN相比较一同检测的几种算法而言有相对较好的对类属性数据的分类准确率。也就验证了EwMKNN算法的改进是有效的。EwMKNN算法的优点是：有较好的分类准确性；可以针对类属性数据的分类；引入了类别信息熵的概念，易于改进和实现；同样易于结合，可以同许多其他分类算法结合，例如KNN算法等。基于类别信息熵加权的MKNN算法（EwMKNN）仍存在着不足之处，对于有高维数据集时准确率会下降，在多类别的类属性数据集的处理上可以进一步的开拓，更好增强其使用程度。

[1] Cover, T.M., Hart, P.E.. Nearest Neighbor Pattern Classific. IEEE Trans on Information Theory, 1967, 13( 1) : 21－27.

[2] 张著英, 黄玉龙, 王翰虎. 一个高效的KNN分类算法[J]. 计算机科学, 2008, 03: 170-172.

[3] 周靖, 刘晋胜. 一种采用类相关度优化距离的KNN算法[J]. 微计算机应用,2010, 11: 7-12.

[4] 戚孝铭. 基于蜂群算法和改进KNN的文本分类研究[D]. 上海交通大学, 2013.

[5] 肖辉辉, 段艳明. 基于属性值相关距离的KNN算法的改进研究[J]. 计算机科学, 2013, S2: 157-159+187.

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

[7] 郝胜轩, 宋宏, 周晓锋. 基于近邻噪声处理的KNN缺失数据填补算法[J]. 计算机仿真, 2014, 07: 264-268.

[8] 苏毅娟, 邓振云, 程德波, 等. 大数据下的快速KNN分类算法[J]. 计算机应用研究, 2016, 33(4): 1003-1006.

[9] 康丽萍, 孙显, 许光銮. 加权KNN的图文数据融合分类[J]. 中国图象图形学报, 2016, 21(7): 854-864.

[10] 刘继宇, 王强, 罗朝晖,等. 基于粗糙集的加权KNN数据分类算法[J]. 计算机科学, 2015, 42(10): 281-286.

[11] Liu, H., Zhang,S.. Noisy data elimination using mutual k-nearest neighbor for classification mining. The Journal of Systems and Software, 2012, 85: 1067–1074.

[12] 陈雪云, 郭躬德, 陈黎飞, 卢伟胜. GwMKNN:针对类属性数据加权的MKNN算法[J]. 计算机系统应用, 2013, 08:103-108 +158.

[13] 王磊. 基于信息熵的中文文本分类算法研究[D]. 西北师范大学, 2007.

[14] 甘苏婷. 基于信息熵的数据挖掘算法在决策支持系统中的改进研究[D]. 吉林大学, 2015.

[15] 陈曦, 翔晨, 李炜, 楼宗元. 基于信息熵的谣言信息度量方法[J]. 华中科技大学学报(自然科学版), 2013, S1: 413-417.

[16] Li, R., Tao, X., Tang, L., Hu, Y. Using Maximum Entropy Model for Chinese Text Categorization. Computer Science, 2004, 3007: 578-587.

[17] 朱佳佳, 陈佳. 基于熵和SVM多分类器的异常流量检测方法[J]. 计算机技术与发展, 2016, 26(3): 31-35.

[18] 魏琴芳, 成勇, 胡向东. 基于信息熵的无线传感网入侵检测遗传算法[J]. 重庆邮电大学学报(自然科学版), 2016(1): 107-112.

[19] 潘瑞林, 李园沁, 张洪亮, 伊长生, 樊杨龙, 杨庭圣. 基于α信息熵的模糊粗糙属性约简方法[J]. 控制与决策, 2017(2): 340-348.

[20] UCI Repository of Machine Learning Databases [DB /OL]. [2012-12-12].

[21] ZHANG Zhen Jie, ZUO Ren Guang, XIONG Yi Hui. A comparative study of fuzzy weights of evidence and random forests for mapping mineral prospectivity for skarn-type Fe deposits in the southwestern Fujian metallogenic belt, China [J]. Science China (Earth Sciences), 2016, 03:556-572.

[22] Data Mining: Concepts and Techniques, 2nd ed., Jiawei Han and Micheline Kamber, Morgan Kaufmann, 2006. P P383-464.

MKNN Algorithm Based on the Weight of Category's Entropy

CHEN Xueyun *, LIU Yanfang, KE Ting, ZHANG Jiannan

(Institute of Information Engineering, Longyan University, Longyan Fujian 364000, China)

Since the process of the mutual k-nearest neighbor (MKNN) dealing with nominal data is simple, we introduce the entropy to deal with the similarity measure of the nominal data, and then the concept of Category's entropy is introduced. We can obtain the entropy weight of the same type of nominal data, and then get experimental results through the classification of the data set. The experimental results demonstrate the effectiveness of the proposed algorithm.

data mining; mutual k-nearest neighbor; category's entropy; nominal data

10.19551/j.cnki.issn1672-9129.2017.01.03

TP18

A

1672-9129(2017)01-0010-05

2017-01-23；

2017-02-09。

国家自然科学基金面上项目（61379049和61379089），福建省大学生创新创业训练计划项目（S20141004）；龙岩学院协同创新项目（张凌）。

陈雪云(1976-)，女，福建省漳平市，龙岩学院副教授，硕士，主要研究方向：数据挖掘技术及其应用、计算机应用技术；刘艳芳(1987-)，女，河南省濮阳市，龙岩学院教师，研究生，主要研究方向：粗糙集与粒计算、人工智能和机器学习；柯婷(1995-)，女，安徽省安庆市，龙岩学院学生，主要研究方向：软件工程；张剑楠(1994-)，男，广东省梅州市，龙岩学院学生，主要研究方向：软件工程。E-mail：cxy2165254@163.com