一种基于两层邻域信息的双重最近邻分类方法及系统

摘要

本发明公开了一种基于两层邻域信息的双重最近邻分类方法及系统，所述方法包括：在训练集中寻找输入样本的k个最近邻，并将它们重新命名为输入样本的直接近邻；在训练集中寻找各直接近邻的可用邻域，所有可用邻域中的样本被看作输入样本的间接近邻；各直接近邻的可用邻域中与输入样本分布较近的被整体保留，与直接近邻一起作为输入样本的候选近邻；据候选近邻与输入样本的反向近邻关系，确定双重最近邻；利用所有双重最近邻的类标签，根据多数表决规则，对输入样本进行分类判决。本发明可提高k近邻分类方法的分类性能，并通过实验验证了该方法的有效性。

说明书

技术领域

本发明属于模式识别技术领域，涉及基于k近邻的分类方法邻域，特别涉及一种基于两层邻域信息的双重最近邻分类方法及系统。

背景技术

k近邻算法是一种经典的非参数分类方法，对于给定的输入样本和训练集，k近邻算法能够从训练集中找到输入样本的k个最近邻，并通过多数表决规则对输入样本进行分类。也就是说，k近邻算法不需要获取训练集的统计特性以训练一个分类模型，而是可以根据训练集提供的信息直接对输入样本进行分类。由于k近邻算法简单、直观且易于实现，目前已被广泛应用于模式识别，特征选择，离群点检测等众多领域。

然而，k近邻算法的近邻选择方法不够成熟，影响了选出的最近邻的质量，进而制约了k近邻算法的分类性能。首先，相似性测度过于简单；k近邻算法仅用点对点的距离衡量输入样本和训练样本之间的相似性，完全放弃了关于它们分布的信息，考虑到这一问题，有研究者引入了质心最近邻的概念，提出了k质心近邻算法。受此启发，研究者们提出了更多基于质心最近邻的改进方案。其次，单边相似性不够全面；k近邻算法只从输入样本的角度考虑训练样本是否是它的k个最近邻之一，而没有从训练样本的角度考虑输入样本是否是它的k个最近邻之一。为了解决这一问题，互近邻和广义近邻的概念被相继提出，其中互近邻需要满足上述两个条件，是对最近邻的精炼，而广义近邻只需要满足任意一个条件，是对最近邻的推广。最后，邻域结构过于单一；k近邻算法只利用了输入样本的k个最近邻来帮助分类，而没有考虑这k个最近邻各自的邻域信息对分类的作用。目前尚未有研究者注意到这一问题。

发明内容

本发明的目的在于提供一种基于两层邻域信息的双重最近邻分类方法及系统，以解决现有技术中不成熟的近邻选择方法对k近邻算法分类性能限制的技术问题。本发明能够提高k近邻算法的分类性能。

为达到上述目的，本发明采用以下技术方案：

本发明的一种基于两层邻域信息的双重最近邻分类方法，用于模式识别，包括以下步骤：

步骤1，在预获取的训练集中寻找输入样本的k个最近邻，所述k个最近邻作为输入样本的直接近邻；

步骤2，在预获取的训练集中寻找各直接近邻的可用邻域，所有可用邻域中的样本作为输入样本的间接近邻；

步骤3，各直接近邻的可用邻域中与输入样本分布满足预设分布关系的被整体保留，与直接近邻一起作为输入样本的候选近邻；

步骤4，根据候选近邻与输入样本的反向近邻关系，决定双重最近邻；

步骤5，利用所有双重最近邻的类标签，根据多数表决规则，对输入样本进行分类判决。

本发明的进一步改进在于，步骤1具体包括以下步骤：

计算输入样本与所有训练样本之间的欧式距离，计算表达式为：

式中，N表示训练集中样本的总数，y

与输入样本距离最近的k个训练样本为输入样本的k个最近邻，计算表达式为：

式中，k表示最近邻的个数，

输入样本的k个最近邻作为输入样本的直接近邻，表达式为：

式中，y

本发明的进一步改进在于，步骤2具体包括以下步骤：

步骤2.1，在训练集中寻找直接近邻各自的k个最近邻；

步骤2.2，确定各直接近邻的可用邻域；

步骤2.3，确定输入样本的间接近邻；

其中，直接近邻各自的k个最近邻为，表达式为：

式中，

对于每个直接近邻，其k个最近邻中，与输入样本的距离小于等于直接邻域半径2倍的部分被选作该直接近邻的可用邻域，表达式为：

式中，y

所有直接近邻的可用近邻共同组成输入样本的间接近邻，表达式为：

式中，IN(x)表示x的间接近邻集合。

本发明的进一步改进在于，步骤3具体包括以下步骤：

分析各直接近邻的可用邻域与输入样本的分布关系，包括：

(1)计算各直接近邻的可用邻域质心与输入样本的距离

(2)将直接近邻的可用邻域质心与输入样本的距离

确定输入样本的候选近邻，包括:保留下来的可用邻域和直接近邻一起组成输入样本的候选近邻，表达式为：

式中，y

本发明的进一步改进在于，步骤4具体包括以下步骤：

分析候选近邻与输入样本的反向近邻关系，包括：如果候选近邻和输入样本的距离小于此候选近邻和它的第k

确定输入样本的双重最近邻，包括：满足反向近邻关系的候选近邻作为输入样本的双重最近邻，表达式为：

式中，y

其中，双重最近邻中的一部分来自直接近邻，称作第一层近邻，表示为DNN

本发明的进一步改进在于，步骤5中，根据双重最近邻的类标签和多数表决规则，对输入样本进行分类判决，表达式为：

式中，c

本发明的进一步改进在于，步骤4中，分析候选近邻与输入样本的反向近邻关系，所用的k

本发明的一种基于两层邻域信息的双重最近邻分类系统，用于模式识别，包括：

直接近邻获取模块，用于在预获取的训练集中寻找输入样本的k个最近邻，所述k个最近邻作为输入样本的直接近邻；

间接近邻获取模块，用于在预获取的训练集中寻找各直接近邻的可用邻域，所有可用邻域中的样本作为输入样本的间接近邻；

候选近邻获取模块，各直接近邻的可用邻域中与输入样本分布满足预设分布关系的被整体保留，与直接近邻一起作为输入样本的候选近邻；

双重最近邻获取模块，用于根据候选近邻与输入样本的反向近邻关系，确定双重最近邻；

判决模块，用于利用所有双重最近邻的类标签，根据多数表决规则，对输入样本进行分类判决。

与现有技术相比，本发明具有以下有益效果：

通过对k近邻算法的研究，总结出k近邻算法中用到的邻域结构过于单一，由于k近邻中可能会存在离群点，因此只使用它们进行分类容易产生错误的分类结果，如果能进一步考虑这k个最近邻各自的邻域信息，就能更有效地排除其中存在的离群点的影响，从而提高分类性能；本发明将注意力集中在丰富邻域结构上，同时考虑到分布关系和反向近邻关系，能够选出质量更高的近邻对输入样本进行分类，可提高k近邻算法的分类性能。具体地，通过实施例证明，尽管添加间接近邻的操作可能会导致分类性能的下降，但经过一步步的筛选，近邻的分类性能会不断提高，最终优于k近邻算法的分类性能。另外，本发明证明了第一层近邻和第二层近邻在分类能力上的确具有互补性，综合使用两层近邻能够减少被分类错误的样本数。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面对实施例或现有技术描述中所需要使用的附图做简单的介绍；显而易见地，下面描述中的附图是本发明的一些实施例，对于本领域普通技术人员来说，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1是本发明实施例的一种基于两层邻域信息的双重最近邻分类方法的流程示意图；

图2是本发明实施例中k＝4时，输入样本的直接近邻的选取示意图；

图3是本发明实施例中k＝4时，输入样本的间接近邻的选取示意图；

图4是本发明实施例中k＝4时，输入样本的候选近邻的选取示意图；

图5是本发明实施例中k

图6是本发明实施例中，用直接近邻、直接近邻和间接近邻、候选近邻、双重最近邻分别进行分类判决时的分类错误率随k值变化曲线示意图；其中，图6中的(a)为Ionosphere数据集上的结果，图6中的(b)为Optdigits数据集上的结果；

图7是本发明实施例中，第一层近邻和第二层近邻的分类能力互补性分析示意图。

具体实施方式

为使本发明实施例的目的、技术效果及技术方案更加清楚，下面结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述；显然，所描述的实施例是本发明一部分实施例。基于本发明公开的实施例，本领域普通技术人员在没有做出创造性劳动的前提下所获得的其它实施例，都应属于本发明保护的范围。

请参阅图1至图7，本发明实施例的一种基于两层邻域信息的双重最近邻分类方法，包括以下步骤：

步骤一：在训练集中寻找输入样本的k个最近邻，并将它们重新命名为输入样本的直接近邻，如图2所示。

直接近邻的选取过程如下：

(1)在训练集中寻找输入样本的k个最近邻，包括：输入：训练集T，输入样本x；例如将本发明的方法用于手写体数字光学识别分类时，训练集是采集到的不同人手写的0到9的数字，输入样本是用户手写的某数字；

1)计算输入样本与所有训练样本之间的欧式距离：

公式(1)中，N表示训练集中样本的总数，y

2)与输入样本距离最近的k个训练样本，即为输入样本的k个最近邻：

公式(2)中，k表示最近邻的个数，

输出：输入样本x的k个最近邻NN

(2)将输入样本的k个最近邻重新命名为输入样本的直接近邻：

公式(3)中，y

步骤二：在训练集中寻找各直接近邻的可用邻域，所有可用邻域中的样本被看作输入样本的间接近邻，如图3所示。

间接近邻的选取过程如下：

(1)在训练集中寻找直接近邻各自的k个最近邻：

公式(4)中，y

(2)确定各直接近邻的可用邻域。对于每个直接近邻来说，它的k个最近邻中，与输入样本的距离不超过直接邻域半径2倍的那部分被选作这个直接近邻的可用邻域：

公式(5)中，y

(3)确定输入样本的间接近邻。所有直接近邻的可用近邻共同组成了输入样本的间接近邻：

公式(6)中，y

步骤三：各直接近邻的可用邻域中与输入样本分布较近的被整体保留，与直接近邻一起作为输入样本的候选近邻，如图4所示。

候选近邻的选取过程如下：

(1)分析各直接近邻的可用邻域与输入样本的分布关系：

1)计算各直接近邻的可用邻域质心与输入样本的距离

2)将直接近邻的可用邻域质心与输入样本的距离

(2)确定输入样本的候选近邻。保留下来的可用邻域和直接近邻一起组成了输入样本的候选近邻：

公式(7)中，y

步骤四：根据候选近邻与输入样本的反向近邻关系，决定双重最近邻，如图5所示。

双重最近邻的选取过程如下：

(1)分析候选近邻与输入样本的反向近邻关系。如果候选近邻和输入样本的距离小于此候选近邻和它的第k

(2)确定输入样本的双重最近邻。满足反向近邻关系的候选近邻就被选作输入样本的双重最近邻：

公式(8)中，y

双重最近邻中的一部分来自直接近邻，被称作第一层近邻，表示为DNN

步骤五：利用所有双重最近邻的类标签，根据多数表决规则，对输入样本进行分类判决。

输入样本类别的预测结果：

公式(9)中，c

最终方法的性能可以用分类错误率来衡量，即被分错的样本数占总样本数的比例。

通过图6和图7可以看出基于两层邻域信息的双重最近邻分类方法能有效提高k近邻算法的分类性能。图6通过对比直接近邻、直接近邻和间接近邻、候选近邻、双重最近邻分别进行分类判决时的分类错误率随k值变化曲线，证明了双重最近邻的有效性，其中直接近邻的分类结果即为k近邻算法的分类结果。从图6中可以看到，尽管添加间接近邻的操作可能会导致分类性能的下降，但经过一步步的筛选，近邻的分类性能会不断提高，最终优于k近邻算法的分类性能。

图7通过对k＝5时第一层近邻，第二层近邻，双重最近邻的分类错误率，以及第一层近邻和第二层近邻都分错的样本比例进行对比，证明了第一层近邻和第二层近邻在分类能力上的确具有互补性。从图7中可以看到，第二层近邻的分类能力在大多数情况下比第一层近邻的差，但是将两层近邻相结合得到的双重最近邻往往具有更好的分类性能。此外，两层近邻都分类错误的样本比例小于用任意一层近邻单独分类时的错误率，这意味着用第一层近邻被分类错误的样本与用第二层近邻被分类错误的样本具有很大的差异。因此，综合使用两层近邻能够减少被分类错误的样本数，也就是说，第一层近邻和第二层近邻具有互补性。

本发明实施例的一种基于两层邻域信息的双重最近邻分类系统，包括：

直接近邻获取模块，用于在预获取的训练集中寻找输入样本的k个最近邻，所述k个最近邻作为输入样本的直接近邻；

间接近邻获取模块，用于在预获取的训练集中寻找各直接近邻的可用邻域，所有可用邻域中的样本作为输入样本的间接近邻；

候选近邻获取模块，各直接近邻的可用邻域中与输入样本分布满足预设分布关系的被整体保留，与直接近邻一起作为输入样本的候选近邻；

双重最近邻获取模块，用于根据候选近邻与输入样本的反向近邻关系，确定双重最近邻；

判决模块，用于利用所有双重最近邻的类标签，根据多数表决规则，对输入样本进行分类判决。

综上，本发明的目的在于提供一种基于两层邻域信息的双重最近邻分类方法，以解决现有技术中不成熟的近邻选择方法对k近邻算法分类性能的限制问题。本发明通过对k近邻算法的研究，总结出k近邻算法中用到的邻域结构过于单一。因此本发明将注意力集中在丰富邻域结构上，同时考虑到分布关系和反向近邻关系，以选出质量更高的近邻对输入样本进行分类，提高k近邻算法的分类性能。本发明公开的基于两层邻域信息的双重最近邻分类方法，包括：步骤一：在训练集中寻找输入样本的k个最近邻，并将它们重新命名为输入样本的直接近邻。步骤二：在训练集中寻找各直接近邻的可用邻域，所有可用邻域中的样本被看作输入样本的间接近邻。步骤三：各直接近邻的可用邻域中与输入样本分布较近的被整体保留，与直接近邻一起作为输入样本的候选近邻。步骤四：根据候选近邻与输入样本的反向近邻关系，决定双重最近邻。步骤五：利用所有双重最近邻的类标签，根据多数表决规则，对输入样本进行分类判决。本发明提出了一种有效的近邻选择方法来提高k近邻算法的分类性能，并通过实验验证了该方法的有效性。

本领域内的技术人员应明白，本申请的实施例可提供为方法、系统、或计算机程序产品。因此，本申请可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本申请可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、CD-ROM、光学存储器等)上实施的计算机程序产品的形式。

本申请是参照根据本申请实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。

这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。

这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。

以上实施例仅用以说明本发明的技术方案而非对其限制，尽管参照上述实施例对本发明进行了详细的说明，所属领域的普通技术人员依然可以对本发明的具体实施方式进行修改或者等同替换，这些未脱离本发明精神和范围的任何修改或者等同替换，均在申请待批的本发明的权利要求保护范围之内。