一种改进的局部均值伪近邻算法

2024-03-12 08:58张德生
计算机工程与应用 2024年5期
关键词:集上均值准确率

李 毅,张德生,张 晓

西安理工大学理学院,西安 710054

分类[1]是数据挖掘中最重要的任务之一,它是通过对已知训练集进行学习,建立分类器预测未知样本标签的一种方法,在模式识别领域属于监督学习。目前,分类算法主要包括支持向量机[2]、决策树[3]、人工神经网络[4]、贝叶斯分类器[5]和KNN算法[6]等,其中KNN算法因具有较高的分类精度和易于实现等优点,在人脸识别[7]、故障检测[8]和医学研究[9]等领域得到了广泛应用。

KNN 算法的基本思想[10]是将待分类样本与训练样本之间的欧氏距离按升序排列,选取距离最小的k个近邻,将待分类样本分配给标签频率最高的类别。尽管KNN算法有许多优点,但仍有一些不足:KNN算法对近邻参数k比较敏感;选取近邻时未考虑样本的分布信息;采用单一的多数投票原则或最短距离原则进行分类决策。

针对KNN 算法存在的不足,研究学者提出了不同的改进方法[11-15]。文献[11]提出了一种新的基于距离加权最近邻规则的双加权投票方法(DWKNN),该算法降低了参数k的敏感性。文献[12]提出了利用距离加权来进行局部学习的伪最近邻规则,同时提出了基于局部平均向量和类统计量的非参数分类器(PNN),该方法减少了异常值对分类性能的影响。文献[13]对于PNN 算法中距离加权系数主观确定的问题,提出了一种基于BP神经网络的自适应伪最近邻分类算法(BPANN),降低了分类过程中主观因素带来的不确定性。文献[14]提出了一种基于局部均值的伪近邻算法(LMPNN),该算法使用k个局部均值向量代替k个最近邻,减少了KNN算法中异常值和维数对分类性能的影响。基于互近邻的思想,文献[15]提出了一种基于双向选择的伪近邻分类算法(BS-PNN),降低了噪声点对分类的影响。

不同于文献[11],LMPNN 算法计算各类的局部均值向量,使用伪近邻规则进行分类决策;文献[12]和[13]利用每类的k个最近邻计算伪近邻进行分类决策,而LMPNN 算法搜索每类的k个最近邻作为类原型,利用最近邻集合的k个局部均值向量找到各类基于局部均值的伪近邻,根据待测样本与新的伪近邻之间的加权距离进行分类,能够更加准确地找到伪近邻,提高了算法的分类准确率。LMPNN 算法虽取得了较好的分类效果,但仍存在以下不足:(1)在选取k个近邻时,只考虑待测样本到训练样本的距离,没有考虑样本的分布信息,并且没有从训练样本的角度确定待测样本是否为其k近邻;(2)对于分类测试样本,不同的多局部均值应该有不同的权重,但LMPNN 算法对每类的第i个局部均值向量主观赋予相同的权重1/i;(3)使用欧氏距离进行分类决策,不能较好地反映局部均值对分类的作用。

针对LMPNN 算法的上述不足,本文进行了改进,提出了一种改进的局部均值伪近邻算法(ⅠPLMPNN)。

(1)引入了双层搜索规则查找待测样本的双层近邻集,提高了近邻集的选择质量;

(2)引入了注意力机制计算局部均值点与待测样本之间的距离加权系数,体现了局部均值向量对待测样本的重要程度;

(3)提出了新的多调和平均距离进行分类决策,降低了噪声点的影响和近邻参数k的敏感性。

1 预备知识

1.1 符号说明

本文常用的符号见表1。

表1 符号说明Table 1 Symbol description

1.2 LMPNN算法

在P维特征空间中,假定有训练样本集T={y1,y2,…,yN},其类标签为,给定一个待测样本x,LMPNN算法的步骤如下:

算法1LMPNN算法

输入:待测样本x,训练集T={y1,y2,…,yN},类标号,类cj对应的训练集Tj={y|l(y)=cj},近邻个数k。

输出:待测样本x的类标号。

步骤1计算待测样本x到Tj中每个样本y的欧氏距离:

将得到的距离按升序排列,取前k个近邻记为y(1),y(2),…,y(k)。

步骤2计算待测样本x在Tj中的第i个局部均值向量:

步骤3在Tj中,对k个近邻点所对应的局部均值点按照到待测样本x的距离升序排列,并为第i个局部均值点赋予对应的权值:

步骤4查找x在Tj中的伪近邻点,x到的距离d()被定义为k个局部均值点到x的欧氏距离的加权总和,即:

步骤5预测待测样本x所属类:

2 本文算法

2.1 双层搜索规则

LMPNN算法采用式(1)确定待测样本的近邻集,仅考虑了待测样本和训练样本之间的距离,对噪声点仍然敏感。针对这一问题,本文引入双层搜索规则查找待测样本的近邻集合,提高近邻集的选择质量,降低噪声点的影响。根据步骤1至步骤4查找待测样本的双层近邻集[16]。

步骤1对于待测样本x,其在训练样本集Tj的第一层近邻集为:

即,用传统的近邻规则在Tj中查找待测样本x的k近邻所形成的集合。

步骤2对于待测样本x,其在训练样本集Tj的第二层近邻集为:

其中,rNN1st(x)是NN1st(x)的半径,即x到NN1st(x)中第k个近邻的距离。

步骤3对于待测样本x,其在训练样本集Tj的扩展近邻集为:

其中,c是NN2nd(x)的质心。

步骤4对于待测样本x,其在训练样本集Tj的双层近邻集为:

其中,(y)代表集合T*=Tj∪{x} 中y的kb个近邻形成的集合,kb一般不小于k。计算(x)中的k*个近邻与x的欧氏距离,按照升序排列记为y͂(1),y͂(2),…。需要指出的是表示集合的基数。k*一般受kb取值影响,其值可能大于k,也可能不超过k。由双层近邻集(x)计算x在Tj中的第i个局部均值向量:

2.2 注意力机制

LMPNN 算法式(4)中的由权值Wi和局部均值点到x的距离两部分的乘积组成。然而,由式(3)计算的权值Wi对任意的k个近邻点均是固定的,使得LMPNN 算法不能得到较优的距离加权值。由此本文引入注意力机制对其进行改进,考虑每个局部均值向量对待测样本分类的影响。

注意力机制模型[17]能够根据信息的重要程度赋予相应的权重。注意力机制的步骤主要分为以下三步:首先,使用评分函数计算两样本点的相似度;其次,利用softmax 函数归一化,使其成为一个和为1 的概率分布,得到注意力系数;最后,根据注意力系数和相应点的加权和得到注意力值。根据注意力机制,设置Tj中第i个局部均值点(见式(10))对应的权值为:

其中

反映局部均值点和待测样本x的相似度。

2.3 多调和平均距离

针对LMPNN算法式(4)中距离对近邻参数k以及噪声点均敏感的问题,本文在已有的调和平均距离[18]基础上,提出一种新的多调和平均距离,定义如下。

Tj中第i个局部均值向量到待测样本x的多调和平均距离为:

其中,表示Tj中第r(r=1,2,…,i)个局部均值向量,表示待测样本x与的欧氏距离。

式(14)中用替代式(13)中的d(x,y),将每类中的k*个近邻用k*个局部均值向量替代。具体分析如下:

其中,y͂(1),y͂(2),…,y͂(k*)为使用双层搜索规则得到x在Tj中的k*个近邻。

d(x,y)易受到单个近邻的影响,若近邻集合中有噪声点,分类结果因噪声点的影响可能导致待测样本的误分类。由式(15)可知,考虑了x与的差分向量,并且使用u͂rj代替近邻点,在进行分类决策时受单个近邻点的影响较小,降低了噪声点的影响。另外,式(14)的i相较于式(13)中的k是变化的,从而能降低近邻参数k的敏感性。

2.4 IPLMPNN算法

本文算法的基本思想为:首先,在Tj中通过双层搜索规则选取待测样本x的双层近邻集。使用筛选后的近邻计算局部均值向量。其次,引入注意力机制计算注意力系数,利用式(11)为多局部均值向量分配不同的权重。最后,使用新的多调和平均距离式(14)进行分类决策。由此,提出了ⅠPLMPNN算法,具体步骤见算法2。

算法2ⅠPLMPNN算法

输入:待测样本x,训练集T={y1,y2,…,yN},类标号,类cj对应的训练集Tj={y|l(y)=cj},第一层近邻个数k。

输出:待测样本x的类标号。

步骤1根据双层搜索规则查找待测样本x在Tj中的k*近邻,表示为。计算中的k*个近邻到x的欧氏距离,按照升序排列为y͂(1),y͂(2),…,y͂(k*)。

步骤2根据(10)式计算待测样本x在Tj中的第i个局部均值向量,令形成的集合为

步骤3在Tj中,根据式(11)和式(12)计算每个局部均值向量对待测样本x的影响权重。

步骤4在Tj中,根据式(14)计算待测样本x到局部均值向量的多调和平均距离。

步骤5查找x在Tj中的伪近邻点,x到的距离被定义为k*个局部均值点到x的调和平均距离的加权和,即:

步骤6预测待测样本x的类标号:

ⅠPLMPNN 算法的流程图如图1 所示。首先,将样本数据预处理,查找待测样本的双层近邻集;然后,由局部均值向量和待测样本计算注意力系数,得到距离权重系数;最后,由新的多调和平均距离计算得到伪近邻点,对待测样本进行分类。

图1 ⅠPLMPNN算法流程图Fig.1 ⅠPLMPNN algorithm flow chart

2.5 算法复杂度分析

假设数据集的规模为N,特征维数为P,近邻个数为k,类别个数为M。ⅠPLMPNN算法的时间复杂度主要来源于以下5 个方面:(1)计算待测样本到每类训练样本的欧氏距离,找到k个近邻,时间复杂度为O(NP+Nk);(2)使用双层搜索规则查找待测样本的双层最近邻,时间复杂度为O((k2+k)M);(3)计算每类的k个局部均值向量,得到k个局部均值向量与待测样本之间的多调和平均距离,时间复杂度为O(MPk+M(1+k)k);(4)将注意力权重分配给每类的局部均值向量,得到每个类的伪近邻点,时间复杂度为O(Mk+MPk);(5)使用决策函数确定待测样本的类别,时间复杂度为O(M) 。因此,ⅠPLMPNN 算法总的时间复杂度为O(NP+Nk+MPk+Mk2)。

3 实验与分析

3.1 数据集

为了验证ⅠPLMPNN 算法的有效性,选择UCⅠ和KEEL 中的14 个数据集(如表2 所示)进行实验。所有实验均在MATLAB R2017b环境下完成。

表2 数据集Table 2 Data sets

3.2 实验结果与分析

实验以分类准确率为评价标准。对样本数量较小的数据集采用10次3折或5折交叉验证法,对样本数量较大的数据集采用10 次10 折交叉验证法,最终将实验得到的准确率平均值作为分类结果。对近邻参数k逐一取值1,2,…,15,采用交叉验证法得到每个k值所对应的平均准确率,将最高的平均准确率所对应的k值选择为最优k值。

3.2.1 实验参数设置

实验1对于ⅠPLMPNN算法步骤1中的参数kb,不同于传统近邻规则中的近邻参数k,kb一般大于k需通过实验确定。这里,取kb=k,kb=1.2k,kb=1.4k,kb=1.6k,kb=1.8k,kb=2.0k,利用ⅠPLMPNN算法对表2的数据集进行实验,实验结果如表3 所示,加粗数字表示各数据集的最优值。

表3 k 与kb 在不同关系下的分类准确率Table 3 Classification accuracy under different relationships of k and kb单位:%

表3 的实验结果表明kb在6 种相应取值下,ⅠPLMPNN 算法分别在4 个,7 个,5 个,4 个,3 个,2 个数据集上得到了最高的分类准确率。并且kb=1.2k在14个数据集上的平均准确率为86.72%,在6种取值中排名第一。实验结果表明kb=1.2k有最好的分类性能,所以在实验2 和实验3 中设置kb=1.2k,以实现更好的分类效果。

3.2.2 IPLMPNN算法在最优k 值下的性能分析

实验2为了评估ⅠPLMPNN算法在最优k值下的分类性能,将KNN[8]、DWKNN[11]、PNN[12]、MLM-KHNN[18]、KGNN[19]、RCKNCN[20]、DC-LAKNN[21]和LMPNN[14]算法与ⅠPLMPNN算法的平均准确率进行对比。得到的平均分类准确率如表4 所示,加粗数字表示9 种算法的最优值。需要说明的是,其他8种算法的平均准确率也是最优k值下对应的结果(k=1,2,…,15)。

表4 最优k 值下ⅠPLMPNN算法与其他8种算法的平均准确率Table 4 Average accuracy of ⅠPLMPNN and other eight algorithms corresponding to optimal k value 单位:%

表4 的结果表明,除Heart、Ⅰris、Letter 和Thyroid 数据集外,ⅠPLMPNN算法在其他10个数据集上得到了最高的平均分类准确率。特别在Glass、Ⅰonosphere、Seeds和Sonar 这4 个数据集上的分类准确率较LMPNN 算法有了明显提升。在Letter 和Thyroid 数据集上取得最高准确率的是RCKNCN算法,其结果为96.37%和95.40%,分别比ⅠPLMPNN 算法高0.05 个百分点和0.22 个百分点。在Heart 和Ⅰris 数据集上取得最高准确率的分别是MLM-KHNN 算法和LMPNN 算法,其准确率分别为80.16%、95.13%,比ⅠPLMPNN 算法高0.13 个百分点和0.12 个百分点。虽然ⅠPLMPNN 算法在这4 个数据集上的准确率略低,但仍高于大多数对比算法。并且ⅠPLMPNN 算法在14 个数据集中获得了最高的平均准确率86.37%,与其他8种算法相比有明显的优势。

3.2.3 IPLMPNN算法在不同k 值下的性能分析

实验3为了验证ⅠPLMPNN 算法在不同k值下的分类性能,将8 种对比算法与ⅠPLMPNN 算法在10 次交叉验证中得到的平均分类准确率进行比较。利用表2的Ⅰonosphere、Seeds、Segment、Glass4 个数据集进行仿真实验。图2为9种算法的平均分类准确率折线图。

图2 不同算法在4个数据集上随着变化的k 值的平均分类准确率Fig.2 Average accuracy of each algorithm with variation of k values for four data sets

从图2可以看出,当k <5 时,ⅠPLMPNN算法较其他对比算法更为陡峭,准确率增长趋势更大。当k在5到10之间时,ⅠPLMPNN算法在Ⅰonosphere、Segment、Glass数据集上呈现出较为平稳的变化趋势,在Seeds 数据集上呈现增长趋势。当k >10 时,KNN、DWKNN、PNN、KGNN算法的准确率随着k值的增大而减小,LMPNN、MLM-KHNN、DC-LAKNN、ⅠPLMPNN 算法的准确率较为平稳,且略有增长,RCKNCN 算法在Ⅰonosphere 和Glass数据集上变化较为平稳,在Segment数据集上准确率随着k值的增大而增大,而在Seeds 数据集上准确率呈现下降趋势。说明了9种算法中ⅠPLMPNN算法在不同近邻参数k下的分类性能是具有优势的,降低了参数k的敏感性。

4 结束语

针对LMPNN算法存在的不足,本文对其进行了改进,提出了一种改进的局部均值伪近邻算法(ⅠPLMPNN)。ⅠPLMPNN算法首先通过引入新的近邻选取规则选取待测样本的高质量近邻点,然后基于注意力机制计算各类的距离加权系数,最后使用改进的多调和平均距离作为新的分类决策规则,降低了近邻参数k对算法的影响。实验结果表明,ⅠPLMPNN 算法在分类准确率上取得了令人满意的结果。由于ⅠPLMPNN算法的时间复杂度较高,因此,下一步的研究工作将提高ⅠPLMPNN算法的计算效率,并将改进的算法应用到实际问题中。

猜你喜欢
集上均值准确率
乳腺超声检查诊断乳腺肿瘤的特异度及准确率分析
不同序列磁共振成像诊断脊柱损伤的临床准确率比较探讨
2015—2017 年宁夏各天气预报参考产品质量检验分析
Cookie-Cutter集上的Gibbs测度
链完备偏序集上广义向量均衡问题解映射的保序性
高速公路车牌识别标识站准确率验证法
复扇形指标集上的分布混沌
均值不等式失效时的解决方法
均值与方差在生活中的应用
关于均值有界变差函数的重要不等式