广义近邻选取的KGNN 改进算法研究
2020-12-21肖铮
肖 铮
（四川工商职业技术学院 信息工程系，成都 611830）
0 引言
K 近邻算法在选择用于分类判断的近邻时，只考虑距离输入样本足够近的那些训练样本，即只使用了输入样本的近邻信息，可以看作是一种单向选择过程。在实际应用中，训练样本的近邻信息对于分类判决同样具有重要作用，它们的近邻也可以被用来判断它们与输入样本之间的邻近性[1]。因此，为了同等地考虑输入样本和训练样本的作用，提出一种双向近邻选择方法，即K 广义近邻（KGNN，k-general nearest neighbor）算法[2]。算法的基本思想是：寻找输入样本的K 近邻训练样本，采用K 近邻包含输入样本的训练样本作为广义近邻，再通过多数表决规则对输入样本进行分类。[3]
1 算法实现
1.1 算法描述
KGNN 算法推广了传统KNN 算法中的近邻选择方法，从双向角度，以更广义的方式来看待输入样本和训练样本之间的关系[4]。只要输入样本和训练样本满足单向近邻条件，就可以将该样本选作广义近邻用来分类。也就是说，KGNN 算法综合考虑了输入样本和训练样本的近邻信息，以便选出更为可靠的近邻，提高分类效果[5]。图1 简单描述了KGNN 算法的流程。
图1 KGNN 算法流程图
同时，KGNN 算法扩大了近邻的范围，使得所选出的广义近邻可能与输入样本具有较远的距离，而这些近邻分类能力本来就比较弱。此外，由于广义近邻中的一部分是从训练样本的角度考虑所选，因此可能分布稀疏，具有任意的形状，包含很多离群点。[6]
1.2 改进算法
改进优化进行筛选的基本思路是将广义近邻划分为核心近邻与其他近邻两部分，其中核心近邻是与输入样本互为K 近邻的那部分，因此全部保留作为最终近邻以用于分类判决。同时由于这种亲密性，认为与核心近邻相似性较小的其他近邻与输入样本之间的相似性也较小，因此删去。
此算法具体的筛选规则为：保留全部m 个核心近邻，如果某个其他近邻的2m 个近邻中包含2m 个核心近邻，则将它保留，否则删除。算法的简单流程如图2 所示。
1.3 算法步骤
图2 改进算法流程图
第一步，根据GNN 规则寻找x′在当前k 值下的广义近邻，表示为GNNk（x′）。GNN 规则具体描述如下：
任意训练样本xi，若x′∈KNk（xi）或xi∈KNk（x′），则xi∈GNNk（x′）。其中KNk（xi）和KNk（x′）分别表示 xi和 x′在 T′中的 k 近邻。
第二步，将x′的广义近邻GNNk（x′）划分为核心近邻CNNk（x′）和其他近邻ONNk（x′）两部分。划分规则为：
若某广义近邻xi满足x′∈KNk（xi），且xi∈KNk（x′），即xi和x′互为近邻关系，则被选为核心近邻，即xi∈CNNk（x′）；否则被划分为其他近邻，即xi∈ONNk（x′）。
第三步，选择最终近邻 FNNk（x′）。筛选规则为：
将全部核心近邻保留作为最终近邻，即CNNk（x′）⊂FNNk（x′），并统计其数目c；对于某其他近邻xi∈ONNk（x′），如果它的2m 个近邻中包含m/2个核心近邻，则将它保留，即xi∈FNNk（x′），否则删除。
第四步，分类判决。公式为：
1.4 算法实验
为了衡量所提方法的分类性能，将其在不同k 值下的分类错误率与传统KNN 算法及KGNN算法进行对比。表1 给出了所用的6 个UCI 真实数据集的具体信息。
每次实验将数据集随机划分为训练集和测试集，训练集包含整个数据集中约30%的样本，测试集为数据集中剩余的样本，训练集的尺寸如表1所示。重复进行20 次实验，最终的实验结果为这20 次实验的平均值。
表1 实验中所用真实数据集的特征
2 实验结果
不同数据集中不同k 值下分类错误率如表2所示。括号中的值表示与KGNN 算法相比，所提方法错误率减小的百分比，即正值表示错误率下降。粗体字表示该k 值下四种方法错误率的最小值。从核心近邻的角度，考虑其他近邻与它们的近邻关系，希望能够保留聚集在核心近邻周围的部分其他近邻。
3 结果分析
筛选方案从其他近邻的角度，考虑核心近邻与其他核心近邻的近邻关系，希望能够保留与多数核心近邻距离都比较近的其他近邻。也就是说，基于KGNN 的改进算法保留了与部分核心近邻距离较近的其他近邻，而忽略了其他近邻的空间分布。实验结果表明，提出的改进方法在多个数据集上均能获得比KGNN 算法更好的效果。
KGNN 算法推广了传统KNN 算法中的近邻选择方法，提出广义近邻的概念，扩大了近邻的范围，也因此使得所选近邻中可能包含过多的离群点，影响分类性能。针对KGNN 算法中选出的广义近邻，提出了筛选方案，能够选出并删除潜在的离群点，以便进一步提高分类效果。在接下来的工作中，希望能够找到更为合理的筛选方法，以进一步提高算法的分类效果。
表2 不同数据集中不同k 值下的分类错误率（%）
续表
