肖 铮

（四川工商职业技术学院 信息工程系，成都 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 近邻的那部分，因此全部保留作为最终近邻以用于分类判决。……