基于EDA的加权KNN分类算法＊

谢雨寒，潘 峰,2

(1.贵州民族大学数据科学与信息工程学院，贵州 贵阳 550025；2.贵州民族大学模式识别与智能系统重点实验室)

0 引言

机器学习中的分类算法有K 近邻（K-Nearest Neighbor，KNN）算法[1]、朴素贝叶斯、决策树和支持向量机等[2]。分类算法通常假设训练样本均匀分布在不同的类别中，而实际应用中普遍是不平衡数据集，即存在部分类别对应的样本数量比另一部分类别少[3]。传统分类器应用于不平衡数据集分类时，会使得分类结果向多数类倾斜，出现多数类通常具有较高的准确率，反之少数类普遍准确率较低，从而导致分类整体性能下降[4]。尽管相较于朴素贝叶斯和支持向量机等，KNN 在处理不平衡数据集的分类问题上更具优势，但整体性能依然不好。

Songbo Tan 提出了基于权重的KNN 算法，为属于多数类的近邻样本分配较小的权重，而少数类的近邻样本分配较大的权重[4]。郝秀兰等提出了一种自适应的加权KNN分类方法，定义样本训练集临界点这一概念，考虑了各类别样本的具体数量，但是没有进一步考虑样本的分布信息。而对于分类方法来说，分布信息是影响性能的重要因素[5]。王超学等在此基础上提出一种加权KNN 算法GAK-KNN，定义了新的权重分配模型，根据不同类别间不平衡和不均匀的分布信息对各训练样本分配相应的权重，并运用基于遗传算法改进的KNN算法对样本进行分类[6]。

遗传算法通过选择、交叉和变异等操作产生下一代，但交叉、变异算子不具备学习和识别样本间连锁关系的能力，在实际的选择和重组过程中容易导致数据结构块被破坏，使得算法早熟或陷入局部最优解。而分布估计算法（Estimation of Distribution Algorithm，EDA）[7]采用了完全不同的进化模式，采用统计学习方式建立概率模型用于描述候选解的分布，再通过对概率模型进行随机采样产生新种群，取代了遗传算法传统的交叉、变异过程，因此不容易导致局部收敛的问题。

本文提出一种基于EDA 改进的加权KNN 算法，目的是克服遗传算法的不足之处，同时，利用EDA 对整个群体在宏观层面上构建概率模型的特点，进一步考虑到不平衡数据集的样本各项特征的具体信息，改进特征权重的分配方式，提高加权KNN算法分类的稳定性和准确率。

1 加权的KNN算法

1.1 基本KNN算法

KNN 算法的基本思想：对于给定的一个待分类的测试样本，先搜索最接近该测试样本的K个已知类别的训练样本，即K个最近邻；然后统计K个最近邻，如果属于某一类别的近邻数量最多，则将这个测试样本判定为该类。

新数据Y与某个训练样本的相似度通常使用如下的欧氏距离公式计算：

其中，d(Y,Xi)表示Y与Xi的欧式距离为第i个训练样本Xi的第l个特征属性值。

1.2 权重的分配

为了更加确切地描述样本间的相似度，需要进一步考虑各属性之间内在的性质和联系，并对其重要性进行区分。因此根据每个属性的重要程度赋予一个相应的权重，引入权重值wl(l=1,2,…,n)，将加权的欧氏距离表示为[8]：

加权欧氏距离能更准确地反映出各属性对于样本的不同作用，使分类算法获得更好的结果。但如何选取合适的权重涉及数据的实际意义，需要对各属性的具体效果有深入的了解，而在实际的操作中难以达到这一要求。

因此，在没有先验知识的前提下，将与样本对应的多种的权重wl取值情况视为求解内容，通过EDA多次迭代获得最优的权重向量，使加权KNN算法分类效果达到最佳。

2 EDA-KNN算法

EDA 的基本思想是从当前种群中选取部分优势群体，并利用这些优势群体估计和学习种群的分布，建立概率模型，然后对该概率模型随机采样，产生新一代种群，如此操作，逐次迭代，逐渐逼近最优解。

对于加权的KNN算法，其实际分类效果关键取决于选取的权重，而EDA 具备构建概率模型这一特点，使其能够宏观地描述样本特征的分布信息。EDAKNN 算法的目的是将不同的权重取值作为不同个体的编码构建种群，更加准确地针对测试样本分配各项特征的权重值，并通过多次迭代获得分类准确率最高的个体，提高分类算法的性能。

2.1 矩阵结构种群

本文的EDA 采用了二维关系构建矩阵结构的种群，即运用了二维数组，数组中每个元素对应种群中一个个体，代表一个可能解。这样的二维关系，使得种群可以被视为由多个一维子种群组成，便于将各个子种群进行独立的查找最优构成优势子群，无需排序操作。文献[9]采用将各行最优置于主对角线，本文将各行最优置于第一列，如图1 到图2 所示，灰度标识行中最优个体。

图1 矩阵结构种群

图2 首列最优的矩阵结构种群

2.2 适应度评价

权重的取值范围为[0,1]，权重值为0 则表示对应的属性不影响分类结果，权重值越大则表示对应的属性越重要。本文采用十进制编码的EDA，种群个体表示为a(i,j),其基因为l=1,2,…,n，相应的公式⑴的权重值l=1,2,…,n，以此将权重值划分为10 个等级0.0,1.0/9,2.0/9,…,9.0/9。

运用加入权重{w1,w2,…,wn}的KNN 算法执行对训练样本集X的分类，并将分类准确率fi,j(w)作为个体a(i,j)的适应度，适应度越高的个体越占优。

2.3 算法步骤

Step1初始化矩阵结构种群A(t)(t=0)，由H×(H+1)的个体构成，以a(i,j)表示种群第i行第j列的个体，i=0,1,…,H−1;j=0,1,…,H；

Step2分别将个体a(i,j) 对应的权重值w={w1,w2,…,wn}用于对训练样本集X进行分类，获得每个个体的适应度fi,j(w)，i=0,1,…,H−1;j=0,1,…,H；

Step3以A0,A1,…,AH−1表示由每一行全部个体组成的规模为H+1 的子种群，依次寻找子种群Ai中最优个体a(i,jbest)(0 ≤jbest≤H+1)，并将其赋给对应的每行第一个个体a(i,0)，i=0,1,…,H−1；

Step4在选出的优势个体构成的种群{a(0,0),a(1,0),…,a(H−1,0)}中寻找最优个体abest，若满足停止条件，则输出；

Step5根据优势种群{a(0,0),a(1,0),…a(H−1,0)}中各项值的分布，获得概率矩阵P(t)=(pvu(t))n×10,v∈{0,1,...,9},u表示基因位，基于概率矩阵采样获得新一代种群A(t+1)，返回Step2。

3 实验仿真与分析

3.1 实验环境

本文程序运用Java 语言进行编写，未使用任何第三方软件包。工作计算环境为多核CPU 台式电脑，其中硬件为：Intel(R) Core(TM) i5-9400F CPU，16.0 GB RAM；软件为Windows 11（64 bit）+OpenJDK-17，使用IntelliJ IDEA 2022.3集成开发环境运行。

3.2 测试数据集

本文选择三组UCI 数据集检验EDA-KNN 算法的分类效果，各数据集的样本属性、类别数量分布如表1所示。

表1 数据集样本分布信息

3.3 实验结果

本文将EDA-KNN 算法、KNN 算法和运用矩阵遗传算法改进的GA-KNN 算法[10]用于三个数据集分类结果比较。GA-KNN 采用二进制编码，即权重的取值为{0,1}，将各属性仅判定为对于分类有影响（权重值为1）和无影响（权重值为0）。为了降低不平衡数据的影响，设定k=1。设数据集样本数为m，训练集X的样本数为n，相应测试集Y的样本数为m-n。每次随机从数据集中随机划分选择训练集和测试集，分别运用EDA-KNN、GA-KNN 和KNN 算法，对测试样本进行分类，获得样本分类的准确率作为运行结果。

从图3、图5 和图7 可以看出，使用EDA 优化的加权KNN 算法分类比普通KNN 算法分类准确率提高显著，同时EDA-KNN 也比GA-KNN 有所提高；从图4、图6 和图8 可以得出，EDA-KNN 比GA-KNN 在迭代中能够较快获得最优权重向量。

图3 Sonar分类结果

图4 Sonar分类收敛性

图5 Cleveland分类结果

图6 Cleveland分类收敛性

图7 Winequality分类结果

图8 Winequality分类收敛性

由此可见，EDA-KNN 执行数据分类的性能远优于基本KNN，并且在处理不平衡数据集时，分类的稳定性和准确率都比GA-KNN更具优势。

4 结束语

提出一种采用矩阵结构种群的EDA，运用十进制编码对加权KNN 的权重进行分级优化，构成EDAKNN 算法。通过EDA 算法学习的特征权重向量构成加权KNN 算法，提高分类性能，比GA-KNN 算法的收敛速度更快，对于不平衡数据集的分类更加稳定，不容易过早收敛。后续将考虑运用基于连续型概率模型的分布估计算法进一步优化权重的分配，使权重值更加精确，以此提升算法性能；本文主要是针对较小维度和数据量不大的数据集进行实验，下一步工作是构建并行KNN 分类器，提高对大数据集特征权重的评估响应速度，使之具有更实际和广泛的应用。