基于局部表示系数的最近邻分类装置

摘要

一种基于局部表示系数的最近邻分类装置，所述装置包括：获取单元，适于获取包括查询样本在内的样本池；选取单元，适于基于所述样本池中的样本特征的空间分布，从所述样本池中选取所述查询样本的相似样本构成所述查询样本的邻居域；分类单元，适于基于所述查询样本的邻居域对所述查询样本进行分类。上述的方案，可以对查询样本进行分类时，提高分类的准确性和效率。

权利要求

1.一种基于局部表示系数的最近邻分类装置，其特征在于，包括：

获取单元，适于获取包括查询样本在内的样本池；

选取单元，适于基于所述样本池中的样本特征的空间分布，从所述样本池中选取所述查询样本的相似样本构成所述查询样本的邻居域；

分类单元，适于基于所述查询样本的邻居域对所述查询样本进行分类。

2.根据权利要求1所述的基于局部表示系数的最近邻分类装置，其特征在于，所述选取单元，适于根据预设的平均局部密度占比范围，求得样本池中任意样本的局部密度；基于求得的任意样本的局部密度，得到所述样本池中任意样本的局部簇中心；将与所述查询样本具有相同局部簇中心的样本添加至所述查询样本的邻居域中，构成所述查询样本的邻居域。

3.根据权利要求2所述的基于局部表示系数的最近邻分类装置，其特征在于，所述平均局部密度占比范围为所有样本的平均局部密度 占样本总数的比例。

4.根据权利要求3所述的基于局部表示系数的最近邻分类装置，其特征在于，所述平均局部密度占比范围为[2％,3％]。

5.根据权利要求2所述的基于局部表示系数的最近邻分类装置，其特征在于，所述选取单元，适于从所述样本池中选取局部密度大于所述任意样本的局部密度的样本；将所选取的样本中与所述任意样本之间的距离最小的样本，作为所述任意样本的局部簇中心。

6.根据权利要求2所述的基于局部表示系数的最近邻分类装置，其特征在于，所述选取单元，还适于当与所述查询样本具有相同局部簇中心的样本的数量小于所述查询样本的邻居域中样本的预设需求数量时，从所述样本池中剩余的训练样本中选取与所述查询样本距离最近的对应数量的样本加入所述查询样本的邻居域中。

7.根据权利要求1至6任一项所述的基于局部表示系数的最近邻分类装置，其特征在于，所述分类单元，适于利用所述邻居域中的所有样本稀疏地表示所述查询样本，求解得到对应的稀疏系数向量；所述稀疏系数向量中对应位置的稀疏系数为所述邻居域中对应样本的权重；从所述邻居域中选取权重大于平均权重的样本，构成所述查询样本的最近邻；采用所述最近邻中的样本对所述查询样本进行投票，确定所述查询样本的最终分类结果。

8.根据权利要求7所述的基于局部表示系数的最近邻分类装置，其特征在于，所述分类单元，适于采用L1正则化方法求解得到对应的稀疏系数向量。

说明书

基于局部表示系数的最近邻分类装置

技术领域

[0001] 本发明属于分类技术领域，特别是涉及一种基于局部表示系数的最近邻分类装置。

背景技术

[0002] K近邻算法是数据挖掘的十大算法之一。由于该算法具有简单高效的优点，自提出以来，它在模式识别中得到了广泛的应用。但它仍然存在两个关键问题，即对邻居域大小的敏感性和在邻居域中简单多数投票对分类决策的敏感性。

[0003] 一般情况下，对邻居域大小的敏感性是由不同的邻居域选择准则和离群点产生的，这种敏感性在小样本的情况下更为明显。通常的邻居域选择只考虑样本间的相似性，往往容易忽视所有样本特征的空间分布。此外，在存在噪声和不平衡数据的小样本情况下，基于K近邻的非参数分类器的性能更是严重下降，对邻居域大小的敏感性也更加明显。K近邻算法的分类决策通常由近邻简单多数投票决定，若存在离群值，其性能很容易退化，因为对于简单多数投票，k个邻居在分类决策中得到的权重是均等的。而理论上，更近的近邻在决策时，应该被给予更大的权重。

[0004] 为了改进简单多数投票，目前存在一些基于稀疏表示的最近邻分类方法，但存在着准确性和效率低下的问题。

发明内容

[0005] 本发明解决的技术问题是如何对查询样本进行分类时，提高分类的准确性和效率。

[0006] 为了达到上述目的，本发明提供一种基于局部表示系数的最近邻分类装置，所述装置包括：

[0007] 获取单元，适于获取包括查询样本在内的样本池；

[0008] 选取单元，适于基于所述样本池中的样本特征的空间分布，从所述样本池中选取所述查询样本的相似样本构成所述查询样本的邻居域；

[0009] 分类单元，适于基于所述查询样本的邻居域对所述查询样本进行分类。

[0010] 可选地，所述选取单元，适于根据预设的平均局部密度占比范围，求得样本池中任意样本的局部密度；基于求得的任意样本的局部密度，得到所述样本池中任意样本的局部簇中心；将与所述查询样本具有相同局部簇中心的样本添加至所述查询样本的邻居域中，构成所述查询样本的邻居域。

[0011] 可选地，所述平均局部密度占比范围为所有样本的平均局部密度 占样本总数的比例。

[0012] 可选地，所述平均局部密度占比范围为[2％,3％]。

[0013] 可选地，所述选取单元，适于从所述样本池中选取局部密度大于所述任意样本的局部密度的样本；将所选取的样本中与所述任意样本之间的距离最小的样本，作为所述任意样本的局部簇中心。

[0014] 可选地，所述选取单元，还适于当与所述查询样本具有相同局部簇中心的样本的数量小于所述查询样本的邻居域中样本的预设需求数量时，从所述样本池中剩余的训练样本中选取与所述查询样本距离最近的对应数量的样本加入所述查询样本的邻居域中。

[0015] 可选地，所述分类单元，适于利用所述邻居域中的所有样本稀疏地表示所述查询样本，求解得到对应的稀疏系数向量；所述稀疏系数向量中对应位置的稀疏系数为所述邻居域中对应样本的权重；从所述邻居域中选取权重大于平均权重的样本，构成所述查询样本的最近邻；采用所述最近邻中的样本对所述查询样本进行投票，确定所述查询样本的最终分类结果。

[0016] 可选地，所述分类单元，适于采用L1正则化方法求解得到对应的稀疏系数向量。

[0017] 与现有技术相比，本发明的有益效果为：

[0018] 上述的方案，通过获取包括查询样本在内的样本池，并基于所述样本池中的样本特征的空间分布，从所述样本池中选取所述查询样本的相似样本构成所述查询样本的邻居域，再基于所述查询样本的邻居域对所述查询样本进行分类，由于邻居域中的样本为从所述样本池中选取的所述查询样本的相似样本，故可以提高查询样本分类的准确性；同时，仅通过邻居域中的样本实现对查询样本的分类，而无需采用样本池中的所有样本对所述查询样本进行分类，故也可以提高查询样本分类的速度和效率，节约计算资源。

附图说明

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

[0020] 图1是本发明实施例的一种基于局部表示系数的最近邻分类方法的流程示意图；

[0021] 图2是本发明实施例的一种基于局部表示系数的最近邻分类装置的结构示意图。

具体实施方式

[0022] 下面将结合本申请实施例中的附图，对本申请实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本申请一部分实施例，而不是全部的实施例。基于本申请中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本申请保护的范围。本发明实施例中有关方向性指示(诸如上、下、左、右、前、后等)仅用于解释在某一特定姿态(如附图所示)下各部件之间的相对位置关系、运动情况等，如果该特定姿态发生改变时，则该方向性指示也相应地随之改变。

[0023] 如背景技术所述，现有技术中的一种最近邻分类方法，利用训练集中所有样本稀疏地表示查询样本，如果某个样本与查询样本相似，则就会被赋予较大的稀疏系数。但是，利用所有训练样本将大幅增加求取稀疏系数的代价，存在效率低下，浪费计算资源的问题。

[0024] 本发明的技术方案通过获取包括查询样本在内的样本池，并基于所述样本池中的样本特征的空间分布，从所述样本池中选取所述查询样本的相似样本构成所述查询样本的邻居域，再基于所述查询样本的邻居域对所述查询样本进行分类，由于邻居域中的样本为从所述样本池中选取的所述查询样本的相似样本，故可以提高查询样本分类的准确性；同时，仅通过邻居域中的样本实现对查询样本的分类，而无需采用样本池中的所有样本对所述查询样本进行分类，故也可以提高查询样本分类的速度和效率，节约计算资源。

[0025] 为使本发明的上述目的、特征和有益效果能够更为明显易懂，下面结合附图对本发明的具体实施例做详细的说明。

[0026] 图1是本发明实施例的一种基于局部表示系数的最近邻分类方法的流程示意图。参见图1，一种基于局部表示系数的最近邻分类方法，具体可以包括如下的步骤：

[0027] 步骤S101：获取包括查询样本在内的样本池。

[0028] 在具体实施中，所述样本池包含带标签信息的训练样本集T和不带标签信息的查询样本集U。

[0029] 步骤S102：基于所述样本池中的样本特征的空间分布，从所述样本池中选取所述查询样本的相似样本构成所述查询样本的邻居域。

[0030] 在本发明一实施例中，在基于所述样本池中的样本特征的空间分布，从所述样本池中选取所述查询样本的相似样本构成所述查询样本的邻居域时，具体包括：

[0031] 首先，根据给定的平均局部密度占比范围[r1,r2]求得在样本池中任意样本xi∈T∪U的局部密度ρi；其中，任意样本xi的局部密度ρi，是指与任意样本xi的距离在截断距离dc范围内的样本数量；平均局部密度占比，是指所有样本的平均局部密度 占样本总数的比例；截断距离dc由平均局部密度占比[r1,r2]决定，即在截断距离dc的条件下，平均局部密度占比应在[r1,r2]范围内。在本发明一实例中，平均局部密度占比[r1,r2]设置为[2％,3％]，距离计算使用欧式距离，即：

[0032]

[0033] 其中，dij表示样本xi和样本xj之间的欧式距离， 表示在样本池中第i个样本的第p个维度。

[0034] 接着，当求得样本池中任意样本xi∈T∪U的局部密度ρi时，基于在样本池中任意样本xi∈T∪U的局部密度ρi，计算得到选取任意样本xi∈T∪U的局部簇中心δi。样本池中，搜索其局部密度高于ρi的样本，然后在这些样本中选择与样本xi距离最近的样本作为其簇中心δi。

[0035] 最后，将与所述查询样本具有相同局部簇中心的样本添加至所述查询样本的邻居域中，构成所述查询样本的邻居域。具体而言，在为池中的查询样本y∈U选取邻居域Ny时，先选取所有与查询样本y拥有相同局部簇中心的训练样本加入到邻居域Ny。这里需要指出的是，当训练样本集中的与查询样本y拥有相同局部簇中心的训练样本的数量大于预设的需求数量K时，则将所有与查询样本y拥有相同局部簇中心的训练样本加入到邻居域Ny；若邻居域Ny中的样本数量小于事先给定的数值K，则再从(T-Ny)训练集中选取与查询样本y距离最近的样本加入到邻居域Ny，直至将Ny样本数量补足至K。

[0036] 步骤S103：基于所述查询样本的邻居域对所述查询样本进行分类。

[0037] 在具体实施中，当确定查询样本的邻居域Ny时，基于所述查询样本的邻居域对所述查询样本进行分类。具体而言：

[0038] 首先，采用邻居域Ny内所有样本稀疏地表示查询样本y：

[0039] y＝Xβ     (2)

[0040] 其中，邻居域Ny＝{x1,x2,…,xK}内样本X＝[x1,x2,…,xK]，y表示所述查询样本，β表示待求的稀疏系数向量，其表示邻居域Ny内样本对查询样本y的贡献，邻居域中的样本xi与查询样本y越相似，贡献就越大。

[0041] 接着，根据公式(1)求解稀疏系数向量。在本发明一实施例中，采用L1正则化方法求解稀疏系数向量，即：

[0042]

[0043] 通过公式(3)求得的稀疏系数向量 中的各稀疏系数被视为邻居域Ny＝{x1,x2,…,xK}内样本X＝[x1,x2,…,xK]中对应样本的权重。

[0044] 从 中选取满足如下条件的稀疏系数：

[0045]

[0046] 满足公式(4)的稀疏系数邻居域Ny＝{x1,x2,…,xK}内样本X＝[x1,x2,…,xK]对应的样本即为要想寻找的查询样本y的最近邻。

[0047] 最后，由查询样本y的最近邻中的样本根据对应权重进行加权投票决定查询样本y的最终分类结果，即将每个类别中的样本对应的权重进行相加，将权重之和最大的样本所属的类别，作为所述查询样本所在的类别。

[0048] 上述对本发明实施例中的基于局部表示系数的最近邻分类方法进行了详细的描述，下面将对上述方法对应的装置进行介绍。

[0049] 图2示出了本发明实施例中的一种基于局部表示系数的最近邻分类装置的结构示意图。参见图2，所述基于局部表示系数的最近邻分类装置20可以包括获取单元201、选取单元202和分类单元203，其中：

[0050] 所述获取单元201，适于获取包括查询样本在内的样本池；

[0051] 所述选取单元202，适于基于所述样本池中的样本特征的空间分布，从所述样本池中选取所述查询样本的相似样本构成所述查询样本的邻居域；在本发明一实施例中，所述选取单元202，适于根据预设的平均局部密度占比范围，求得样本池中任意样本的局部密度；基于求得的任意样本的局部密度，得到所述样本池中任意样本的局部簇中心；将与所述查询样本具有相同局部簇中心的样本添加至所述查询样本的邻居域中，构成所述查询样本的邻居域。其中，所述平均局部密度占比范围为所有样本的平均局部密度 占样本总数的比例，其可以根据实际的需要进行设置，如设置为[2％,3％]等。在本发明又一实施例中，所述选取单元202，适于从所述样本池中选取局部密度大于所述任意样本的局部密度的样本；将所选取的样本中与所述任意样本之间的距离最小的样本，作为所述任意样本的局部簇中心。在本发明另一实施例中，所述选取单元202，还适于当与所述查询样本具有相同局部簇中心的样本的数量小于所述查询样本的邻居域中样本的预设需求数量时，从所述样本池中剩余的训练样本中选取与所述查询样本距离最近的对应数量的样本加入所述查询样本的邻居域中。

[0052] 所述分类单元203，适于基于所述查询样本的邻居域对所述查询样本进行分类。在本发明一实施例中，所述分类单元203，适于利用所述邻居域中的所有样本稀疏地表示所述查询样本，求解得到对应的稀疏系数向量；所述稀疏系数向量中对应位置的稀疏系数为所述邻居域中对应样本的权重；从所述邻居域中选取权重大于平均权重的样本，构成所述查询样本的最近邻；采用所述最近邻中的样本对所述查询样本进行投票，确定所述查询样本的最终分类结果。在本发明另一实施例中，所述分类单元203，适于采用L1正则化方法求解得到对应的稀疏系数向量。

[0053] 本发明实施例还提供了一种计算机可读存储介质，其上存储有计算机指令，所述计算机指令运行时执行所述的基于局部表示系数的最近邻分类方法的步骤。其中，所述基于局部表示系数的最近邻分类方法请参见前述部分的介绍，不再赘述。

[0054] 本发明实施例还提供了一种终端，其特征在于，包括存储器和处理器，所述存储器上储存有能够在所述处理器上运行的计算机指令，所述处理器运行所述计算机指令时执行所述的基于局部表示系数的最近邻分类方法的步骤。其中，所述基于局部表示系数的最近邻分类方法请参见前述部分的介绍，不再赘述。

[0055] 采用本发明实施例中的上述方案，通过获取包括查询样本在内的样本池，并基于所述样本池中的样本特征的空间分布，从所述样本池中选取所述查询样本的相似样本构成所述查询样本的邻居域，再基于所述查询样本的邻居域对所述查询样本进行分类，由于邻居域中的样本为从所述样本池中选取的所述查询样本的相似样本，故可以提高查询样本分类的准确性；同时，仅通过邻居域中的样本实现对查询样本的分类，而无需采用样本池中的所有样本对所述查询样本进行分类，故也可以提高查询样本分类的速度和效率，节约计算资源。

[0056] 以上显示和描述了本发明的基本原理、主要特征和本发明的优点。本行业的技术人员应该了解，本发明不受上述实施例的限制，上述实施例和说明书中描述的只是说明本发明的原理，在不脱离本发明精神和范围的前提下，本发明还会有各种变化和改进，本发明要求保护范围由所附的权利要求书、说明书及其等效物界定。