一种基于信息熵的自适应k值KNN二分类方法

谢 妙, 林泳昌, 朱晓姝

(玉林师范学院 计算机科学与工程学院,广西 玉林 537000)

0 引 言

k最近邻(k-nearest neighbor,KNN)算法是十大数据挖掘“经典算法”之一[1]。对于任意给定测试样本,KNN算法基于距离度量找出训练集中与其最靠近的k个训练样本,然后基于这k个最近“邻居”的分类属性来预测该测试样本的类型[2]。由于KNN算法的k值一般是根据经验设定或利用十折交叉法得到,使得k值存在一定的不合理性。另外,由于没有考虑样本之间的相关性,相同属性的权重也影响了分类准确率。为此,许多学者对KNN算法进行了改进;文献[3]提出了一种距离加权KNN算法,该算法在传统KNN算法基础上,考虑分类时各类近邻样本与待分类样本的平均距离,但并未考虑属性值对类别的影响;文献[4]考虑不同的特征对分类重要性的影响,通过特征选择和特征加权途径改进距离度量;文献[5]基于待分类样本的互近邻及近邻诱导待分类样本类标签的可信度,提出了一种新的k最近邻的分类算法;文献[6]提出利用数据集本身的特征预测最优k值的方法;文献[7]提出一种基于属性值信息熵的KNN改进算法,该算法首先定义2个样本间的距离为相同属性值的平均信息熵,然后根据此距离选取与待测试样本距离最小的k个近邻,最后根据各类近邻样本点的平均距离及个数判断待测试样本的类别。虽然分类准确率有所提高,但未考虑近邻样本间的相似度;文献[8]提出了一种自适应的KNN算法,自适应计算k值和每个样本点的权重向量,但需要消耗大量的计算资源;文献[9]提出一种基于高斯函数加权的自适应KNN算法,利用高斯函数计算距离权值向量,然后根据该向量计算样本点的自适应最近邻个数;文献[10]提出基于环形过滤器的k值自适应KNN算法,该算法通过环形过滤器过滤出每个测试点的内围训练集,然后通过新训练集来构建每个待测点的稀疏向量,从而得出每个测试点的动态k值,虽然分类准确率有所提高,但对不平衡数据集误判率较高。本文提出一种基于信息熵的自适应k值KNN二分类算法(adaptivek-value KNN bisecting classification algorithm based on information entropy,EAKNN)。该算法通过引入样本比例定义信息熵,加强小样本的重要性;通过计算小于预设熵阈值的最小信息熵,得到对应的k值和模型分数;在此基础上,结合提出的精度提升模型计算得到模型精度,不断迭代模型精度,直到不能提升。在客户分类预测等7个数据集上的实验表明,EAKNN算法比传统KNN算法、基于高斯函数加权的自适应KNN算法和基于属性值信息熵的KNN改进算法都有更高的分类准确率。

1 相关知识

1.1 KNN算法

KNN算法[11]是一个简单而经典的机器学习分类方法。通过度量待分类样本和已知类别样本之间的距离(通常使用欧氏距离)或相似度,对样本进行分类。其算法步骤如下所述。

(1) 使用欧氏距离[12]计算样本点到所有样本点之间的距离,其定义公式为:

(1)

其中:d(x,y)为样本x和样本y之间的距离；n为特征维数；xi为样本x的第i个属性；yi为样本y的第i个属性。

(2) 根据计算出来的欧氏距离大小对样本进行递增排序。若距离越小,则相似度越高。

(3) 选择前k个距离最近的邻居样本点。

(4) 统计k个最近的邻居样本点分别属于每个类别的个数。

(5) 采用投票法和少数服从多数的原则,将k个邻居样本点里出现频率最高的类别,作为该样本点的预测类别。

可以看出,KNN算法中只有一个超参数k,k值的确定对KNN算法的预测结果有着至关重要的作用。k值过小容易导致KNN算法的过拟合;k值过大,算法的近邻误差会偏大,容易发生欠拟合。另外,当数据样本不均衡时,KNN方法预测结果会偏向于样本数占优类,对稀有类别的预测准确率低。

1.2 信息熵

熵是对系统混乱程度的衡量。熵越小,混乱度越小,系统的不确定程度越小。信息熵用以衡量数据本身含有信息量的大小,信息量的大小随着其发生概率而递减。信息熵[13]定义为:

(2)

其中:H(X)为信息熵;X为一组随机事件x1、x2、…、xn的集合；P(xi)(0≤P(xi)≤1)为出现随机事件的概率,且P(x1)+P(x2)+…+P(xn)=1。

1.3 模型评价方法R2

模型的优劣会影响最终的分类结果,在常用的模型评估指标中,选择判定系数R2来度量预测值的总变差与真实值的总变差的比值,换言之,就是用来衡量模型的拟合程度。R2定义为:

(3)

2 EAKNN算法

2.1 基本概念与定义

定义1 数据集D的信息熵。设D={x1,x2,…,xn,L}是数据的集合,其中:xi={xi1,xi2,…,xid}；d为维度;n为数据的个数；属性L是数据的标签类别,设L={-1,1}。数据集D的信息熵表示为:

H(D)=-∑Pi(x)lbPi(x)

(4)

其中,Pi表示集合D中属于类别i的样本比例。

假设二分类后得到数据集的2个分类子集是不均衡的,数据样本少的分类有时在一定程度上也能起到关键作用。为了提高小样本的重要性,平衡大小样本的作用,在数据集信息熵中引入类别样本比例参数α。α为总样本数与该类中样本数的比例,计算公式为:

(5)

其中:n为总样本数;nci为分类中属于某类的样本数。例如,总样本数为100、标签为1的样本数为30,则标签为1的该类样本的α1=100/30。因此,改进后的信息熵公式为:

H(D)=-∑αiPi(x)lbPi(x)

(6)

定义2 精度提升模型。设G(x)为模型精度,βi为模型i的分数,gi为模型i的分类结果。为了提升模型总分类精度,利用分类结果乘以该模型分数得到该模型分类结果,迭代计算,将分类结果累加,得到模型精度。精度提升模型为:

(7)

2.2 算法描述

在EAKNN算法中,输入数据集(分为训练集、验证集和测试集)、最大k值kmax、最小k值kmin、熵阈值HT、训练集样本采样比例和特征采样比例、循环变量i、最小迭代次数m。算法流程如图1所示,具体实现步骤如下:

图1 EAKNN算法流程

(1) 根据样本采样比例和特征采样比例随机抽取训练集,遍历kmin到kmax之间的k值,利用定义的信息熵公式(6)求得最小信息熵及对应的k值。

(2) 判断所求最小信息熵是否小于熵阈值HT。若不小于,则利用步骤(1)求得的k值和共享近邻[14]方法进行分类;若小于,则利用则步骤(1)求得的k值和KNN方法进行分类,得到验证集分类结果和由(3)式计算得到模型分数。

(3) 将验证集分类结果乘以该模型分数得到该模型分类结果,迭代计算,将分类结果累加,得到模型精度,与前一次累加得到的总模型精度进行比较。若精度有所提升,则保留该训练集作为模型一部分。

(4) 迭代步骤(1)～步骤(3),直到迭代m次模型精度不再提升,则终止。

(5) 输出测试样本的分类结果。

EAKNN方法将数据集分为有标签的训练集和验证集,以及无标签的测试集,获取数据集每个类别的样本比例,并根据样本采样比例和特征采样比例随机抽取训练集,利用定义的信息熵公式(6)求得最小信息熵时的k值,实现自适应选择k值。

3 实 验

3.1 实验数据来源

本文实验数据集为疝气病症预测病马是否死亡数据集、收入分类数据集、银行电话营销数据集、银行贷款分类数据集、存款有无预测数据集、客户分类数据集和个人贷款建模数据集,其中疝气病症预测病马是否死亡数据集来源于百度百科网,其余6个数据集均来源于kaggle比赛官网(https://www.kaggle.com/)。数据集的具体描述见表1所列。

表1 实验数据集具体描述

3.2 实验环境

本实验使用notebook编译软件、Python3.6语言编程,分别使用sklearn里的KNN方法、高斯函数方法。计算机硬件配置为:内存8 GiB,64位操作系统,i5-6300HQ处理器。

3.3 评价指标

在机器学习的分类方法中,常常使用准确率来衡量模型的分类效果。

正负样本混淆矩阵见表2所列,实验评价指标基于表2。

表2 正负样本的混淆矩阵

其中:TP和TN分别表示正确分类的正类和负类的样本数量;FN和FP分别表示错误分类的正类和负类的样本数量。

准确率越高模型分类效果越好[15]。准确率计算公式为：

(8)

3.4 实验参数设置

训练集、验证集和测试集划分比例为6∶2∶2,随机种子设置为0;kmin=3,kmax=21,entropy=0.5,最小迭代次数m=5,特征和样本采样比例使用高斯分布函数在[0.5,0.8]中随机选取。

3.5 实验结果与分析

将本文提出的EAKNN方法分别与传统KNN、基于高斯函数加权的自适应 KNN算法和基于属性值信息熵的KNN改进算法相比较。基于7个数据集测试这4种方法的准确率指标,结果见表3所列。

表3 4种方法的分类准确率

从表3可以看出,EAKNN方法在7个数据集上准确率值都大于其他3种方法,即EAKNN的分类性优于其他3种方法,特别是银行电话营销和银行贷款分类数据集,比KNN方法提高了50%以上,主要原因如下:① 使用改进的信息熵作为KNN分类指标,不仅能刻画出数据集少量样本的重要性,还能找出最纯的k个近邻点集合,使样本分类更准确;② 使用随机属性、随机样本思想,挖掘数据特征组合潜在特点,自适应地选取特征构建多个KNN模型,并对模型进行加权融合,进一步使样本分类更准确;③ EAKNN方法引入了共享近邻方法,当k个近邻点的样本特征相似,并无法以信息熵指标进行类别划分时,使用邻居相同数量最多作为其分类指标,避免信息熵无法区分样本属性相近的不足,更进一步提升了模型的分类准确率。

4 结 论

针对传统KNN方法k值需要设定和对样本不均衡数据集的预测偏差问题,本文提出了一种基于信息熵的自适应k值KNN二分类算法。通过引入样本比例定义信息熵,刻画出小样本的重要性,同时找出最纯的k个近邻点集合,使样本分类更准确。实验结果表明,EAKNN算法的模型精度提升明显,分类准确率比KNN算法平均提高20%。