尹欢一 文志诚 马正见

摘要：KNN算法中各样本特征被视为等值权重，特征之间的关联因素没有考虑在分类算法中。为了解决此问题，提出一种基于皮尔森相似度和距离权重的改进KNN算法，根据训练样本和待分类样本计算皮尔森相似度和距离权重来判定特征和类别的相关度，且提出一种贡献率类别的判定方法。仿真结果表明，与KNN算法相比，提高了算法的分类精确度。

关键词：K近邻;皮尔森相似度;距离权重;相关程度

中图分类号：TP18       文献标识码：A

文章编号：1009-3044（2019）27-0208-03

Abstract：In the KNN algorithm， each sample feature is treated as an equivalent weight， and the correlation factors between the features are not considered in the classification algorithm. In order to solve this problem， an improved KNN algorithm based on Pearson similarity and distance weight is proposed. The Pearson similarity and distance weight are calculated according to the training samples and the samples to be classified to determine the correlation between features and categories， and a contribution is proposed. The method of determining the rate category. The simulation results show that compared with the KNN algorithm， the classification accuracy of the algorithm is improved.

Key words：K nearest neighbor; Pearson similarity; Distance weight; Correlation degree

1 引 言

KNN算法模型[1]易于理解，是機器学习经典算法中最容易实现的非参数的监督学习算法之一，不仅能够解决分类问题，且在回归问题上也有很好的表现。但KNN算法也存在一定的缺陷：一是计算训练样本和待分类样本特征的距离中未考虑到特征权重对分类结果的影响，不同的特征对待分类样本的分类结果的贡献是不相同的 [2];二是KNN作为一种实例学习的基本方法[3]，采用简单的样本特征间距计算方法，计算待分类样本与每一个训练样本特征距离，对距离进行排序，以投票的方式判定样本的类别，算法的计算开销较大[4];三是当训练样本类别严重切斜时，分类效果不佳，且待分类样本的分类结果严重依赖于超参数K的取值[5]。

针对上述KNN算法的不足之处，在提升算法准确度方面，有研究学者提出对样本的距离赋予权重，在分类模型中引入权重值提升了分类的准确度[6]。但是很少考虑训练样本和待分类样本的属性相关因素对分类的影响程度，当出现距离权重相近，不同类别的训练样本近邻个数相等时，则无法对待分类样本进行正确分类。

本文在上述问题的研究过程中，着重考虑了样本之间的特征的相关程度对样本分类结果的影响，提出一种基于皮尔森相似度和距离权重的改进KNN算法（Pearson Similarity and Distance Weight KNN，PSDW-KNN），将皮尔森系数作为样本特征之间的相关程度的度量方式，再结合KNN算法模型中计算的样本特征距离，最终确定待分类样本的类别。文中将PSDW-KNN算法与KNN算法、距离权重KNN算法进行了比较，经过仿真实验发现，本文PSDW-KNN算法在分类准确度上比KNN算法、距离权重KNN算法在近邻K值取较小值且训练样本数不同的情况下，分类准确度更高。

2 KNN算法

KNN算法在解决分类问题上的主要思想是：给定已知分类的数据样本作为训练样本集，将训练样本集输入到算法模型中存储，将待分类样本再输入到算法模型中计算与训练样本之间的距离，对距离进行排序，选择距离最近的K个训练样本，最后将这K个训练样本中出现次数最多的类别作为此待分类样本的类别[7]。距离权重KNN算法在KNN算法的基础上为每一个特征添加了距离权重，算法模型与KNN算法类似。

设训练样本[S={X，C} ={（X1，C1），（X2，C2），…，（Xm，Cm）}]作为训练样本集的第[i]个样本的[n]维特征向量，[p=1，2，…n]，[Ci∈TC1， C2，…，Cm]为训练样本类别，[i=1，2，3…m];待分类样本[S'= {X'，C'}={（X'1，C'1），（X'2，C'2），…，（X'm，C'm）}]，作为待分类样本集的第[j]个样本的[n]维特征向量，[k=1，2，…n]，[C'j∈TC'1， C'2， C'3，…，C'm]作为待分类样本集的类别，[j=1，2，3…m]。

KNN算法的具体分类步骤如下[8]：

输入：训练样本XTrain和类别CTrain。

输出：待分类样本Xj的类别Cj。

1） 均值方差归一化，将训练样本和待分类样本数据归一到均值为0，方差为1的分布。

2） 计算训练样本Xi与待分类样本Xj之间的欧拉距离，n为样本的特征维度，p=1，2，3…n。

3） 对距离d进行排序，通过穷举的方法取前k个距离d对应的训练样本，查看这k个训练样本的分类，统计结果中最多的类别作为[X'（j）]的所属类别。

4） 遍历[S']待分类样本集中的所有样本，重复上述2，3步骤，获得[S']待分类样本集的类别向量。

3 PSDW-KNN算法

本文在PSDW-KNN算法中通过引入超参数的方式，动态调整皮尔森相关系数和距离权重值两个类别的判定因素在分类问题上的比重，提出了一种新的类别判定方法：贡献率判定法。贡献率作为待分类样本的判定方法，不仅考虑到纵向距离权重对分类的影响，还顾及到了特征之间的横向的特征相关性。

3.1 皮尔森相关系数

皮尔森相关系数多数应用场景都是用来描述两个样本的线性相关的度量[9]，对于两个样本X={x1，x2，…，xn}，Y={y1，y2，…，yn}，皮尔森相关系数定义如下：

式（3）中，n为特征维度，[xi]、[yi]分别是X，Y的均值，[rX，Y∈[-1，1]]表示相关程度，当r取值为-1或1时，表示两个样本完全相关，当r取值为0时，表示两个样本完全无关。

为了方便對样本相关程度的度量，对式（3）中皮尔森系数进行适当变形如下：

其中ρ（X，Y）的取值为0～1，例如计算X1={3，5，1，3}，Y1={4，3，1，9}时，ρ（X1，Y1）=0.2399。X2{3，50，23，3}，Y2={4，3，1，9}时，ρ（X1，Y1）=0.5444。

3.2 贡献率

对比于KNN算法和距离权重的KNN算法优劣研究表明，当出现距离权重相近，不同类别的训练样本近邻个数相等时，可能导致分类精确度不高或分类错误，因此本文将距离权重和皮尔森相关系数都作为影响分类结果的一部分，提出一种特征贡献率的分类判定方法。

设XTrain=（x（1），x（2），…，x（m））为训练样本集，CTrain={c1，c2，…，cm}为训练样本集类别，x（j）为待分类样本，训练样本集XTrain的特征维度维n，样本数为m，特征B的距离权重可定义如下：

其中m为样本个数，n为样本的特征维度，C为皮尔森相关系数的超参数，用于调整纵向距离与横向特征相关性对分类结果的影响比重。

PSDW-KNN算法步骤如下：

输入：待分类样本XTrain的类别CTrain。

输出：待分类样本x（j）的类别Cj。

1） 均值方差归一化，将训练样本和待分类样本数据归一到均值为0，方差为1的分布。

2） 根据式（4）计算训练样本与待分类样本的皮尔森相关系数ρ（x（i），x（j）），根据式（5）和式（6）计算特征的距离权重向量[θ]。

3） 根据式（7）计算训练样本的贡献率G（x（i），x（j）），且选取最优的超参数C。

4） 对贡献率G（x（i），x（j））进行排序，通过投票的方式，再次选择前K个训练样本，查看这K个训练样本的分类，统计结果中最多的类别作为x（j）的所属类别。

下面使用UCI的Optical Recognition of Handwritten Digits数据集对PSDW-KNN算法进行验证：

Digits 数据集有5620个样本，64个特征，10个类别。为了测试方便，在Digits 数据集中随机挑选15个样本作为训练样本集，选1个样本作为待分类样本，表1是随机挑选的15个训练样本和1个待分类样本，由于样本的特征为64，为了便于展示，选择前6个特征。

（3） 取K的值为3，选取最优的超参数C=1000，根据式（7）计算训练样本的贡献率G（x（i），x（j）），选取前K个样本的类别为：{7，7，1}，因此最后判定X待分类样本的类别Cj=7。

4 实验结果与分析

为了方便操作和验证算法的有效性，本文实验选择在Mac OS操作系统上完成，选用UCI数据集上的Optical Recognition of Handwritten Digits数据集，将Anaconda的Jupyter Notebook作为实验仿真开发环境。将Digits数据集随机切割为训练数据样本和待分类数据样本。为了验证PSDW-KNN算法的分类准确度，将KNN算法与距离权重的KNN算法进行对比实验。

实验1 测试不同k 值对分类结果的影响。测试数据集占总数据集的20%，训练数据集和测试数据集经过均值方差归一化处理，在Anaconda的Jupyter Notebook将Nearest Neighbor k作为因变量，k值每次递增的幅度为1，直到k的值为99，仿真得到不同k值下KNN、DW-KNN、PSDW-KNN的算法准确率，仿真结果如图1所示。

在k值为[1～60]区间范围内，PSDW-KNN的算法在样本分类的准确率均高于KNN算法和DW-KNN算法。在k值大于60以后，PSDW-KNN的算法准确率与DW-KNN算法的准确率大体一致，且趋于平稳。从算法仿真结果的整体趋势来看，PSDW-KNN的算法和DW-KNN算法在分类准确度均高于KNN算法。

实验2 测试样本的大小对分类结果的影响。将k值设定为40，实验中训练样本数占总样本集的比率从[10%～80%]， 递增的幅度为5%。在训练样本数不断递增的情况下，算法的分类准确率如图2所示。

从图2可以看出，当训练样本逐步递增的情况下，PSDW-KNN的算法分类准确率不断提高，虽然训练样本数占总样本数的[55%～60%]的区间内，DW-KNN算法的准确率略高于PSDW-KNN算法的准确率，但是从这三种算法整体的准确率趋势看，PSDW-KNN算法明显优于KNN算法和DW-KNN算法。

5 结论

本文针对KNN算法和距离权重KNN算法未考虑训练样本和待分类样本的属性相关因素对分类的影响程度，提出一种基于皮尔森相似度和距离权重的改进KNN算法，该算法考虑到特征的相关性和特征的距离权重两个方面对分类的影响因素，使用贡献率的分类方法对待分类样本进行分类。从仿真结果来看，该算法提高了KNN算法的分类准确率和分类稳定性。由于PSDW-KNN算法主要目的是在原有KNN算法的基础上，提高分类的准确率，但是算法计算效率上还有待提高，下一步的研究重点会放在时间复杂度的优化上，提高算法的计算效率。

参考文献：

[1] 郝岩，白艳萍，张校非.基于KNN的合成孔径雷达目标识别[J].火力与指挥控制，2018，43（9）：111-113.

[2] Yong Xu，QiZhu，Zizhu Fan，Minna Qiu，Yan Chen，Hong Liu.Coarse to fine K nearest neighbor classifier[J].Pattern Recognition Letters，2013，34（9）：980-986.

[3] 陸微微，刘晶.一种提高K_近邻算法效率的新算法[J].计算机工程与应用，2008，44（4）：163-165.

[4] Yong Xu，QiZhu，Zizhu Fan，Minna Qiu，Yan Chen，Hong Liu.Coarse to fine K nearest neighbor classifier[J].Pattern Recognition Letters，2013，34（9）：980-986.

[5] Serpen，Gursel Aghaei，Ehsan.Host-based misuse intrusion detection using PCA feature extraction and kNN classification algorithms [J].2018，22（5）：1101-1114.

[6] 严晓明.基于类别平均距离的加权KNN分类算法[J].计算机系统应用，2014，23（2）：128-132.

[7] 刘磊，初秀民，蒋仲廉，等.基于KNN的船舶轨迹分类算法[J].大连海事大学学报，2018，44（3）：15-21.

[8] 戴璞微，潘斌，王玉铭，等.一种基于层次分析法的改进KNN算法[J].辽宁石油化工大学学报，2018，38（4）：87-92.

[9] 张峰，谢振华，程江涛，等.基于向量皮尔森相关系数的组合赋权法[J].火力与指挥控制，2015，40（5）：83-86.

【通联编辑：唐一东】