基于双树的高维向量空间样本快速搜索方法及装置

技术领域

本发明涉及样本处理技术领域，具体涉及一种基于双树的高维向量空间样本快速搜索方法及装置。

背景技术

K近邻(K Nearest Neighbor，KNN)算法是指给定一个待查点，在多维向量空间样本点集合内查找与待查点最接近的K个样本点，如果这K个样本点中的大多数属于某一类别，则待查点也属于这一类别。K近邻搜索在很多数据分析问题中得到广泛应用，例如机器学习、地理信息系统、人工智能等领域。在面对高维、海量样本集合时，因需要与大量样本点计算和比较空间距离，造成计算量大，查询速度慢的问题，影响了KNN算法的实践应用。

针对KNN算法计算量大、查询效率低的问题，目前主要有以下改进方向：

第一、对样本集进行裁剪。例如现有技术中通过对样本集进行分析，从中剔除冗余元素，缩小样本集合，进而减少K近邻搜索阶段的计算量。但在面向高维、海量样本集时，样本集合缩减规模有限，仍面临计算量大的缺陷。

第二、采用并行计算架构提升K近邻查询速度。现有技术提出一种基于CUDA模型的并行KNN算法，采用通用矩阵乘提升距离计算速度，根据K值大小，分别采用两种方法对距离进行比较，这一并行计算方法有效提高了K近邻查询效率。

第三、采用空间分区数据结构，实现K近邻快速搜索。对样本点集合按照特定的几何形态进行划分，同时构造搜索二叉树，在K近邻查找阶段，通过比较空间距离，对二叉树进行剪枝处理，减少需要计算和比较距离的样本点数量，进而加快K近邻查询速度。常见的空间分区数据结构包括Metric-tree，Ball-tree，Cover-tree，VP-tree，MVP-tree，R-tree和KD-tree。

各种空间分区数据结构主要在以下三个方面存在区别，第一、分区的几何形状；第二、建立搜索树的空间划分策略；第三、利用数据结构进行搜索的策略。Ball-tree结构采用超球体对数据集进行划分，在K近邻查询方面有更多的优势，因此得到广泛应用。但是基于Ball-tree结构的K近邻算法初始K个近邻点位置固定，即Ball-tree结构最左侧K个叶节点，如待查点距离初始K个近邻点空间距离较近，则剪枝效果好，会有更多的数据点被剪枝滤除，进而获得更快的K近邻查询速度。但当待查点距离初始K个近邻点较远时，剪枝半径过大，剪枝效果差，仅有少量数据点被剪枝滤除，K近邻查询速度降低，在面对高维、海量样本集时，这一缺点尤为明显。

发明内容

为此，本发明提供一种基于双树的高维向量空间样本快速搜索方法及装置，最大限度地保留原始数据点集合在高维空间的分布形态，可以快速定位最近邻点，有效缩小了剪枝半径，改善了剪枝效果，提升K近邻查询效率。

为了实现上述目的，第一方面，本发明提供一种基于双树的高维向量空间样本快速搜索方法，包括：

步骤1、在双树结构构造过程中，对每棵子树信息进行统计，将统计结果存入节点数组，所述节点数组中每个元素对应一棵子树的统计信息，统计信息包括子树内数据点个数，子树对应的超球体半径和子树对应的数据点集合，所述节点数组中的元素按照每棵子树内数据点个数降序排列，子树内数据点个数值相同的元素，按照所述子树对应的超球体半径升序排列；

步骤2、对数据点个数大于等于最大剪枝点数的每棵子树进行过滤处理，保留每棵子树中距离质心最近的数据点，将未被保留的数据点过滤删除并存入被删点集合；全部子树处理完毕后，将所述被删点集合中的数据点按照双树构造算法组成被删树；从全部样本点集合中去除被删点集合元素后的剩余元素组成剪枝点集合，将剪枝点集合中的数据点按照双树构造算法组成剪枝树；

步骤3、先在剪枝树内调用K近邻算法查找待查点的Kg个近邻点，其中

步骤4、将原始数据集按照给定比例划分为测试集和训练集，利用随机算法生成若干组测试集和训练集，对每组测试集和训练集得到的最优查询参数计算平均值作为最终的最优参数值Kg，使给定数量的待查点在所述剪枝树和被删树内找到K个最近邻。

作为基于双树的高维向量空间样本快速搜索方法的优选方案，步骤2中，定义剪枝树为reduce_tree，定义被删树为pruned_tree；

输入参数为：待剪枝的数据点集合data；存储每棵子树统计信息的节点数组node_density，节点数组元素按照每棵子树内数据点个数point_num降序排列，point_num值相同的元素，按照子树对应的超球体半径radius升序排列；整数变量max_points表示最大剪枝点数；

输出参数为：一棵由被删除数据点构造的被删树pruned_tree，一棵由剪枝剩余数据点构造的剪枝树reduce_tree；

剪枝树reduce_tree和被删树pruned_tree构造步骤包括：

步骤2.1、令被删树数组存储被删除数据点，初值为空；令剪枝树数组存储剪枝剩余数据点，初值为空；

步骤2.2、将节点数组中数据点个数大于等于最大剪枝点数的全部元素构成集合T，T＝{T1,T2,…,Tn}；按照数据点个数将子树分类，定义实数变量avg_max_radius表示已经剪枝的每棵子树的最大半径平均值，初值为T1.radius；定义整数变量current_point_num表示当前处理的这类子树数据点个数，初值为T1.point_num；定义实数变量previous_radius表示前一棵子树对应球体的半径，初值为T1.radius；定义整数变量i，初值为2；

步骤2.3、从集合T中取出元素Ti，如果Ti.point_num！＝current_point_num，即当前这类子树处理完毕，则执行步骤2.6，否则执行步骤2.4；

步骤2.4、如果Ti.radius-previous_radius≤2或者Ti.radius

步骤2.5、令center为数据点集Ti.points的质心，min_dist_point为数据点集Ti.points中距离质心center最近的点，令pruned_tree＝pruned_tree∪(Ti.points-min_dist_point)，即将Ti.points中除min_dist_point之外的数据点并入pruned_tree数组；令previous_radius＝Ti.radius，同时更新avg_max_radius值；令i＝i+1，如果i≤len(T)，则执行步骤2.3，否则执行步骤2.7；

步骤2.6、令current_point_num＝Ti.point_num，更新当前处理的这类子树的数据点计数current_point_num，执行步骤2.5；

步骤2.7、令reduce_tree＝data-pruned_tree，执行步骤2.1至步骤2.6构建全部被删数据点构成的被删树和全部剪枝剩余数据点构成的剪枝树。

作为基于双树的高维向量空间样本快速搜索方法的优选方案，步骤3中包括：

步骤3.1、调用单树结构K近邻搜索算法，确定待查点target在剪枝树内的Kg个近邻点，找到的Kg个近邻点存储在reduce_tree.KNN_result数组内；

步骤3.2、将待查点target在剪枝树内的最近邻点预置到被删除树的K近邻数组内，确定待查点target在被删树内的K个近邻点，当定位的近邻点个数num≥K时，查找结束，否则执行步骤3.3；

步骤3.3、将待查点target在剪枝树内的最远近邻点预置到被删树的K近邻数组内，确定待查点target在被删树内的K个近邻点，当定位的近邻点个数num≥K，查找结束，否则执行步骤3.4；

步骤3.4、将完整树的K近邻数组预置为空，使用单树结构K近邻搜索算法在完整树内查找K近邻点，查找结束。

作为基于双树的高维向量空间样本快速搜索方法的优选方案，步骤4中，定义输入参数为：用于训练的数据点集合train_data；用于测试的数据点集合test_data；存储每棵子树统计信息的节点数组node_density；待查最近邻个数K；剪枝数上限值max_len；

输出参数为：最佳剪枝数max_points；最佳剪枝树的近邻点个数Kg；起始近邻点begin_point；结束近邻点end_point；

确定最优查询参数的步骤包括：

步骤4.1、按照train_data集合构成Ball-tree结构；定义实数变量T1、T2用于时间统计，T

步骤4.2、按照train_data集合，构造剪枝树reduce_tree和被删树pruned_tree，剪枝数设定为Len，定义整数变量i，初值为1；

步骤4.3、如果i≤len(test_data)，执行步骤4.4，否则，令Len＝Len+1，如果Len

步骤4.4、定义整数变量j，初值为2,如果j≤K，执行步骤4.5，否则令i＝i+1，执行步骤4.3；

步骤4.5、查询test_data[i]在剪枝树中的j个近邻点，T

步骤4.6、定义整数变量n，初值为1，如果n≤j–1，执行步骤4.7，否则，令j＝j+1，如果j≤K，执行步骤4.5，否则令i＝i+1，执行步骤4.3；

步骤4.7、令begin_point_＝n，end_point_＝j，查询test_data[i]在双树结构内的K近邻点，限定剪枝树内查询的近邻点个数Kg＝j，限定被删树的两个初始近邻点为reduce_tree.KNN_result[j-1]和reduce_tree.KNN_result[n-1]，T

步骤4.8、按照时间统计结果，升序排列result数组元素，排序之后result[0]元素各字段值即为最优参数值。

作为基于双树的高维向量空间样本快速搜索方法的优选方案，用于信息检索、文本分类、模式识别、数据挖掘和图像处理过程中的样本搜索。

第二方面，提供一种基于双树的高维向量空间样本快速搜索装置，采用第一方面或其任意实现方式的基于双树的高维向量空间样本快速搜索方法，包括：

初始统计模块，用于在双树结构构造过程中，对每棵子树信息进行统计，将统计结果存入节点数组，所述节点数组中每个元素对应一棵子树的统计信息，统计信息包括子树内数据点个数，子树对应的超球体半径和子树对应的数据点集合，所述节点数组中的元素按照每棵子树内数据点个数降序排列，子树内数据点个数值相同的元素，按照所述子树对应的超球体半径升序排列；

被删树和剪枝树构造模块，用于对数据点个数大于等于最大剪枝点数的每棵子树进行过滤处理，保留每棵子树中距离质心最近的数据点，将未被保留的数据点过滤删除并存入被删点集合；全部子树处理完毕后，将所述被删点集合中的数据点按照双树构造算法组成被删树；从全部样本点集合中去除被删点集合元素后的剩余元素组成剪枝点集合，将剪枝点集合中的数据点按照双树构造算法组成剪枝树；

递归搜索模块，用于先在剪枝树内调用K近邻算法查找待查点的Kg个近邻点，其中1≤Kg≤K；之后分别用第1个和第Kg个近邻点作为被删树的初始近邻点，在被删树内查找所述待查点的K个近邻点，当找到的近邻个数不足K个时，将最近邻数组置空，在双树结构内查找所述待查点的K个近邻点；

最优查询参数确定模块，用于将原始数据集按照给定比例划分为测试集和训练集，利用随机算法生成若干组测试集和训练集，对每组测试集和训练集得到的最优查询参数计算平均值作为最终的最优参数值Kg，使给定数量的待查点在所述剪枝树和被删树内找到K个最近邻。

第三方面，提供一种计算机可读存储介质，所述计算机可读存储介质中存储用于基于双树的高维向量空间样本快速搜索的程序代码，所述程序代码包括用于执行第一方面或其任意实现方式的基于双树的高维向量空间样本快速搜索方法的指令。

第四方面，提供一种电子设备，所述电子设备包括处理器，所述处理器与存储介质耦合，当所述处理器执行存储介质中的指令时，使得所述电子设备执行第一方面或其任意实现方式的基于双树的高维向量空间样本快速搜索方法。

本发明从原始数据点集合中过滤出极少量数据点组成剪枝点集合，过滤剩余数据点组成被删点集合，剪枝点集合中数据点最大限度地保留原始数据点集合在多维空间中的分布形态，这样待查点在剪枝点集合中的最近邻点与待查点在完整集合中的第K个近邻点非常接近。利用剪枝点集合构成剪枝树，利用被删点集合构成被删树，由于剪枝点集合中数据点个数很少，因此可以在剪枝树内快速定位最近邻点，再利用这个近邻点作为初始近邻点，在被删树和完整树内搜索K近邻，由于初始近邻点位置不在固定，而是位于待查点附近，有效缩小了剪枝半径，因剪枝距离缩短，将有更多的子树被剪枝滤除，减少空间距离计算和大小比较次数，改善了剪枝效果，提高整体查询效率。

附图说明

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

图1为现有技术中Ball-tree内Node节点的分裂过程示意图；

图2为现有技术中二维空间内44个样本点构成的一棵Ball-tree结构示意图；

图3为理想情况下待查点target在二维空间内5近邻搜索过程示意图；

图4为非理想情况下待查点target在二维空间内5近邻搜索过程示意图；

图5为本发明实施例1中提供的基于双树的高维向量空间样本快速搜索方法流程图；

图6为调整剪枝数max_points值对剪枝效果的影响示意图；

图7为图2中样本点按照算法2构造成的reduce-tree结构；

图8为按照算法2构造成的reduce-tree结构；

图9为按照算法2的一段局部剪枝过程示意图；

图10为基于双树的K近邻搜索实例过程示意图；

图11为最佳查询参数统计示意图；

图12为在最佳参数和最差参数作用下，对400个查询点近邻距离统计示意图；

图13为基于双树的高维向量空间样本快速搜索装置示意图。

具体实施方式

以下由特定的具体实施例说明本发明的实施方式，熟悉此技术的人士可由本说明书所揭露的内容轻易地了解本发明的其他优点及功效，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

周知的，以下知识为本领域技术人员知悉的现有技术：

双树(Ball-tree)结构，由Moore提出。Ball-tree的构造过程如下，初始条件下，多维向量空间内全部样本点构成一个最小超球体(对于二维空间，即是最小圆)，这个超球体就是Ball-tree的根节点root。之后按照一定原则将全部样本点划分为两部分，构造成两个最小子超球体，这两个子超球体分别是root节点的左右子树根节点，这个分裂过程持续进行下去，直至每个子超球体内只包含1个样本点或半径极小时停止分裂，Ball-tree构建成功。通常采用加权空间欧氏距离作为多维向量空间内样本点之间的距离计算公式。

Ball-tree内每个根节点包括五个重要属性，质心pivot(即子超球体的圆心)；半径radius，满足公式(1)；样本点集合points(即子超球体内全部样本点数据集)；Child1和Child2分别是根节点的左右子树根节点，如果根节点是非叶节点，则满足公式(2)和(3)。

Node.Child1.points∪Node.Child2.points＝Node.points (3)

Ball-tree内每个Node节点的分裂原则如下：首先计算子超球体内距离质心最远的样本点point1，再计算距离point1最远的样本点point2，将全部样本点集合points划分为两个子集Child1和Child2，其中距离point1更近的样本点被划分到Child1集合，距离point2更近的样本点被划分到Child2集合，节点分裂原则可用公式(4)描述。

参见图1，为Node1节点的分裂过程，二维空间内7个样本点A-G构成一个最小圆，即Ball-tree中的Node1节点。距离质心最远的是A点，距离A最远的是B点，A和B点之间的超平面将全部7个样本点划分为两个子集Child1和Child2，这两个子集又构成两个最小子圆，即Node1节点的左右子树根节点。

K近邻搜索算法，多维空间内待查点p与Node节点内任意样本点x的空间距离满足公式(5)和(6)。根据三角不等式可以得到:

|x-p|≥|p-Node.pivot|-|x-Node.pivot|

给定x∈Node.points，满足|x-Node.pivot|≤Node.radius，因此可证明公式(5)成立，同理可证明公式(6)成立。

|x-p|≥|p-Node.pivot|-Node.radius (5)

|x-p|≤|p-Node.pivot|+Node.radius (6)

公式(7)中root为Ball-tree结构根节点，

dist＝|p-Node.pivot|-Node.radius

在查询阶段，利用公式(7)可实现对子树的快速剪枝，加快检索进程。如图1所示，当前距离待查点p的最近邻点是H，由于

基于Ball-tree结构的K近邻递归搜索算法1：search_KNN(KNN_result,node,target,K)：

输入参数：当前最近邻数组KNN_result，首次调用时为空数组；当前处理节点node，首次调用时为Ball-tree根节点；待查点target；待查最近邻个数K。

输出参数：待查点target的K个最近邻数据点。

T1.如果当前处理节点node为空，则执行T7，否则执行T2。

T2.如果当前处理节点node为叶子节点，则执行T3，否则执行T4。

T3.令node节点的全部n个数据点组成集合S，S＝{S1,S2,…,Sn}，其中Si为node节点的第i个数据点。依次取出集合S中的每个数据点Si，计算待查点target与数据点Si之间的空间距离distance；令整数变量len为最近邻数组KNN_result的元素个数，如果len＝K，则比较distance与KNN_result[0][1]的大小，KNN_result[0][1]为KNN_result数组首个元组的distance值，如果distance＝KNN_result[0][1]，则不更新KNN_result数组。

T4.令当前处理node节点对应的球半径为radius，对应的质心点为center，质心点center与待查点target的空间距离为distance_c，如果|distance_c|>radius+KNN_result[0][1]，则执行T7，即当前节点内不可能存在待查点target的K近邻数据点，当前节点node对应的整棵子树被剪枝过滤。如果|distance_c|<＝radius+KNN_result[0][1]，则执行T5，即当前节点内可能存在待查点target的K近邻数据点，需要分别处理node节点的左右子树。

T5.令当前节点node的左子树根节点为node.child1，递归调用K近邻搜索算法search_KNN(KNN_result,node.child1,target,K)处理node节点的左子树。

T6.令当前节点node的右子树根节点为node.child2，递归调用K近邻搜索算法search_KNN(KNN_result,node.child2,target,K)处理node节点的右子树，

T7.算法结束，返回当前KNN_result。

根据K近邻递归搜索算法1可知，无论待查点在多维空间什么位置，KNN_result数组的初始值均为Ball-tree结构最左侧K个叶节点。这导致当待查点距离初始K个叶节点较近时，剪枝效果好，查询效率高，反之剪枝效果差，查询效率低，

图2显示的是二维空间内44个样本点构成的一棵Ball-tree结构,待查点target在二维空间内的坐标位置为(80,400)，图3显示的是待查点target在二维空间内5近邻搜索过程。初始条件下Ball-tree最左侧5个叶节点(即20，8，39，41，44)被填入KNN_result数组，数组元素按照distance值降序排列。之后算法从左至右，逐个计算叶节点与target的空间距离，并与KNN_result数组首个元素的distance值比较大小关系，动态更新KNN_result数组元素值，使其始终保存当前的5个最近邻。由于待查点target距离初始5近邻空间距离较近，剪枝效果好，查询过程中Ball-tree整个右分枝子树被剪枝，其包含33个样本点。整个查询过程只比较了11个样本点与target的距离值即完成5近邻搜索，查询效率较高。

图4所示例子中，待查点target在二维空间的位置为[66,212]，这个位置距离Ball-tree结构最左侧5个叶节点，即初始5近邻较远，整个查询过程中剪枝效果较差，只进行了两次剪枝操作，共包括10个样本点。经过与34个叶节点比较空间距离，完成5近邻搜索，查询效率较低。

造成原始Ball-tree结构K近邻搜索算法查询效率较低的原因如下：

当KNN_result数组中元素个数不足K个时，将最先处理的叶节点存入KNN_result数组，使其元素个数尽快达到K个，之后不断用更优的近邻点更新KNN_result数组，直至算法结束。这个原始算法的主要缺点在于不论待查点target位于多维空间什么位置，KNN_result数组中初始K个数据点均是固定的，即Ball-tree结构最左侧K个叶子节点。在多维空间内，待查点target的位置是随机变化的，而每个target点的初始K个近邻点均是固定的，这K个初始近邻点很可能距离目标target较远，使用这K个初始近邻点对Ball-tree进行剪枝，因剪枝距离过大，很难达到理想的剪枝效果。

如果能在待查点target附近快速找到一组相对近邻点，并用这组数据点作为初始近邻点对Ball-tree进行剪枝，因剪枝距离缩短，将有更多的子树被剪枝滤除，减少空间距离计算和大小比较次数，进而提高整体查询效率。

基于上述的现有技术基础及存在的问题，本发明的具体实施过程如下：

实施例1

参见图5，提供一种基于双树的高维向量空间样本快速搜索方法，用于信息检索、文本分类、模式识别、数据挖掘和图像处理过程中的样本搜索，包括：

S1、在双树结构构造过程中，对每棵子树信息进行统计，将统计结果存入节点数组，所述节点数组中每个元素对应一棵子树的统计信息，统计信息包括子树内数据点个数，子树对应的超球体半径和子树对应的数据点集合，所述节点数组中的元素按照每棵子树内数据点个数降序排列，子树内数据点个数值相同的元素，按照所述子树对应的超球体半径升序排列；

S2、对数据点个数大于等于最大剪枝点数的每棵子树进行过滤处理，保留每棵子树中距离质心最近的数据点，将未被保留的数据点过滤删除并存入被删点集合；全部子树处理完毕后，将所述被删点集合中的数据点按照双树构造算法组成被删树；从全部样本点集合中去除被删点集合元素后的剩余元素组成剪枝点集合，将剪枝点集合中的数据点按照双树构造算法组成剪枝树；

S3、先在剪枝树内调用K近邻算法查找待查点的Kg个近邻点，其中1≤K≤K；之后分别用第1个和第Kg个近邻点作为被删树的初始近邻点，在被删树内查找所述待查点的K个近邻点，当找到的近邻个数不足K个时，将最近邻数组置空，在双树结构内查找所述待查点的K个近邻点；

S4、将原始数据集按照给定比例划分为测试集和训练集，利用随机算法生成若干组测试集和训练集，对每组测试集和训练集得到的最优查询参数计算平均值作为最终的最优参数值Kg，使给定数量的待查点在所述剪枝树和被删树内找到K个最近邻。

在原始Ball-tree构造算法中增加一步处理，对每棵子树信息进行统计，统计结果存入node_density数组。node_density数组中每个元素对应一棵子树的统计信息，统计信息包括这棵子树内数据点个数，即叶节点个数point_num，这棵子树对应的超球体半径radius，这棵子树对应的数据点集合points。数组元素按照每棵子树内数据点个数point_num降序排列，point_num值相同的元素，按照半径radius升序排列。

具体的，步骤S2中，定义剪枝树为reduce_tree，定义被删树为pruned_tree；

输入参数为：待剪枝的数据点集合data；存储每棵子树统计信息的节点数组node_density，节点数组元素按照每棵子树内数据点个数point_num降序排列，point_num值相同的元素，按照子树对应的超球体半径radius升序排列；整数变量max_points表示最大剪枝点数；

输出参数为：一棵由被删除数据点构造的被删树pruned_tree，一棵由剪枝剩余数据点构造的剪枝树reduce_tree；

定义剪枝树和被删树构造算法2：

reduce_and_pruned_tree(node_density,data,max_points)

剪枝树reduce_tree和被删树pruned_tree构造步骤包括：

S2.1、令被删树数组存储被删除数据点，初值为空；令剪枝树数组存储剪枝剩余数据点，初值为空；

S2.2、将节点数组中数据点个数大于等于最大剪枝点数的全部元素构成集合T，T＝{T1,T2,…,Tn}；按照数据点个数将子树分类，定义实数变量avg_max_radius表示已经剪枝的每棵子树的最大半径平均值，初值为T1.radius；定义整数变量current_point_num表示当前处理的这类子树数据点个数，初值为T1.point_num；定义实数变量previous_radius表示前一棵子树对应球体的半径，初值为T1.radius；定义整数变量i，初值为2；

S2.3、从集合T中取出元素Ti，如果Ti.point_num！＝current_point_num，即当前这类子树处理完毕，则执行S 2.6，否则执行S2.4；

S2.4、如果Ti.radius-previous_radius≤2或者Ti.radius

S2.5、令center为数据点集Ti.points的质心，min_dist_point为数据点集Ti.points中距离质心center最近的点，令pruned_tree＝pruned_tree∪(Ti.points-min_dist_point)，即将Ti.points中除min_dist_point之外的数据点并入pruned_tree数组；令previous_radius＝Ti.radius，同时更新avg_max_radius值；令i＝i+1，如果i≤len(T)，则执行S2.3，否则执行S2.7；

S2.6、令current_point_num＝Ti.point_num，更新当前处理的这类子树的数据点计数current_point_num，执行S2.5；

S2.7、令reduce_tree＝data-pruned_tree，执行S2.1至S2.6构建全部被删数据点构成的被删树和全部剪枝剩余数据点构成的剪枝树。

参见图6，本发明可以保证reduce-tree集合中元素尽可能少，且最大限度地保留原始样本点的空间形态。在原始样本点集合中，离群数据点数量相对较少，但对保持原始样本点的空间形态有重要作用，这类样本点应最大限度地予以保留。算法2的S2.4计算子超球体半径差，当半径递增幅度过大且半径大于已经过滤处理的全部子超球体半径均值时，认为该子超球体内所包含的样本点对保留空间形态有重要作用，停止对该子超球体内数据点的剪枝处理。

整数变量max_points用于限定剪枝力度，增大该值将有更多的数据点被剪枝删除，这一数值的确定需要经过精确计算，以达到最佳效果。图6显示了对二维空间内3960个样本点进行剪枝处理，调整剪枝数max_points的剪枝效果比较，可见剪枝剩余样本点密度不同，但均最大限度保留原始样本点的基本形态，且离群点得到最大限度地保留。

参见图7，显示的是图2所示44个样本点按照算法2构造成的reduce-tree结构，max_points值设置为10，剪枝剩余16个样本点，图8是按照算法2构造的pruned-tree结构。图9显示的是一段局部剪枝过程，前三棵子树均有五个叶节点，且都符合剪枝条件，每棵子树只保留距离子球体质心最近的数据点，其余四个数据点被删除。第四棵子树与前一棵子树球体半径差为6.258964，大于临界值，且球体半径大于全部已剪枝子树球体半径均值，因此不予剪枝处理，这棵子树全部5个叶节点(2,4,10,11,33)予以保留。但在后面处理过程中，这棵子树的左右孩子，即叶节点数分别为3和2的两棵子子树符合剪枝处理条件，最终只有(11，2)两个叶节点予以保留，其余三个叶节点(4,10,33)被剪枝删除。这个过程体现了最大限度保留原始样本点空间形态这一思想。

定义双树结构K近邻递归搜索算法3：

search_KNN_IN_double_tree(ball_tree,pruned_tree,reduce_tree,target,K,K_g)

输入参数：原始ball_tree根节点；被删树pruned_tree根节点；剪枝树reduce_tree根节点；待查点target；待查最近邻个数K；剪枝树内待查最近邻个数K_g。

输出参数：待查点的K个最近邻数据点。

具体的，步骤S3中包括：

S3.1、调用单树结构K近邻搜索算法，确定待查点target在剪枝树内的Kg个近邻点，找到的Kg个近邻点存储在reduce_tree.KNN_result数组内；

S3.2、将待查点target在剪枝树内的最近邻点预置到被删除树的K近邻数组内，确定待查点target在被删树内的K个近邻点，当定位的近邻点个数num≥K时，查找结束，否则执行S3.3；

S3.3、将待查点target在剪枝树内的最远近邻点预置到被删树的K近邻数组内，确定待查点target在被删树内的K个近邻点，当定位的近邻点个数num≥K，查找结束，否则执行S3.4；

S3.4、将完整树的K近邻数组预置为空，使用单树结构K近邻搜索算法在完整树内查找K近邻点，查找结束。

参见图10，显示了在图7、图8所示“双树”结构内的5近邻搜索实例。待查点target在二维空间内的位置是(66,212),采用原始Ball-tree结构K近邻算法时，仅有10个叶节点被剪枝过滤，经过与34个叶节点计算比较空间距离，才完成5近邻搜索，查询效率较低。采用双树结构K近邻算法后，在剪枝树内经过与10个叶节点比较空间距离，确定剪枝树内的3个近邻点，将待查点与编号36叶节点的空间距离24.08设置为被删树的初始近邻值，而原始算法的初始近邻值为238.13，双树结构的初始近邻值更接近待查点的第5个近邻点，有更好的剪枝效果，在被删树内经过7次比较，即确定5近邻点。整个查询过程计算比较了17个叶节点的空间距离，共有27个叶节点被剪枝滤除，与原始算法相比，查询效率得到明显提升。实验结果表明剪枝数max_points和剪枝树内近邻点个数Kg对整体查询效率影响很大，例如max_points取值区间为[2,11]，Kg的取值区间为[2,5]，则共可得到10×10＝100组可选参数，不同参数的查询效率差别很大。

将原始数据集按照8:2比例划分，随机选择20％数据点作为测试集，随机性保证测试数据点分布比较均匀，其余80％数据点作为训练集。利用随机算法，共生成10组测试和训练数据集，对每组数据集得到的最优参数计算平均值，作为最终的最优参数值。

定义确定最优查询参数算法4：

determine_optimal_parameters(node_density,train_data,test_data,K,max_len)：

具体的，定义输入参数为：用于训练的数据点集合train_data；用于测试的数据点集合test_data；存储每棵子树统计信息的节点数组node_density；待查最近邻个数K；剪枝数上限值max_len；

输出参数为：最佳剪枝数max_points；最佳剪枝树的近邻点个数Kg；起始近邻点begin_point；结束近邻点end_point；

确定最优查询参数的步骤包括：

S4.1、按照train_data集合构成Ball-tree结构；定义实数变量T1、T2用于时间统计，T

S4.2、按照train_data集合，构造剪枝树reduce_tree和被删树pruned_tree，剪枝数设定为Len，定义整数变量i，初值为1；

S4.3、如果i≤len(test_data)，执行S4.4，否则，令Len＝Len+1，如果Len

S4.4、定义整数变量j，初值为2,如果j≤K，执行S4.5，否则令i＝i+1，执行S4.3；

S4.5、查询test_data[i]在剪枝树中的j个近邻点，T

S4.6、定义整数变量n，初值为1，如果n≤j–1，执行S4.7，否则，令j＝j+1，如果j≤K，执行S4.5，否则令i＝i+1，执行S4.3；

S4.7、令begin_point_＝n，end_point_＝j，查询test_data[i]在双树结构内的K近邻点，限定剪枝树内查询的近邻点个数Kg＝j，限定被删树的两个初始近邻点为reduce_tree.KNN_result[j-1]和reduce_tree.KNN_result[n-1]，T

S4.8、按照时间统计结果，升序排列result数组元素，排序之后result[0]元素各字段值即为最优参数值。

对图6中a所示二维空间内3960个样本点按照8:2比例划分训练和测试集，待查找的近邻数K为5，将剪枝数范围限定为[6,29]，将剪枝树近邻点个数Kg限定为[2,5]，利用算法4得到的最优参数如图11所示，对10组训练和测试结果计算均值后，得到最优max_points＝14，最优K_g＝2，在这组参数作用下，全部测试点平均查询时间为3.2秒；同时得到最差参数为max_points＝6，最差Kg＝2，使用这组参数，平均查询时间为10.8秒。

图12显示的是在最佳参数和最差参数作用下，对400个测试点与剪枝树起始近邻点距离reduce_min_radius，结束近邻点距离reduce_max_radius和完整树第K个近邻点距离all_max_radius进行了统计分析。图12中(a)是按照reduce_min_radius降序排列的最佳参数测试结果，可见在最佳参数作用下，绝大部分测试点与第K个近邻点的距离值all_max_radius小于reduce_min_radius，可在被删树内进行一次检索即可命中K近邻点，只有极少量测试点的all_max_radius大于reduce_max_radius，因此整体查询效率最高。图12中(b)是按照all_max_radius降序排列的最差参数测试结果，可见在最差参数作用下，绝大部分测试点与第K个近邻点的距离值all_max_radius大于reduce_min_radius，但是小于reduce_max_radius，即需要两次检索被删树才能确定K近邻点，极个别测试点需要检索完整树才能确定K近邻。

本发明在训练阶段，将原始数据集按照8:2比例划分为训练集和测试集,利用随机选择方法共生成10组训练和测试集合，通过统计分析，得到最优双树构造参数。利用最优参数从原始数据点集合中过滤出极少量数据点构成剪枝树，过滤剩余数据点构成被删树，剪枝树需要最大限度地保留原始数据点集合在高维空间的分布形态。在查询阶段，由于剪枝树内数据点个数很少，可以快速定位最近邻点，再利用这个近邻点作为被删树的初始近邻点，在被删树内搜索K近邻。实验结果表明，由于初始近邻点位置不在固定，而是位于待查点附近，有效缩小了剪枝半径，改善了剪枝效果，提升了K近邻查询效率。

实施例2

参见图13，提供一种基于双树的高维向量空间样本快速搜索装置，采用实施例1或其任意实现方式的基于双树的高维向量空间样本快速搜索方法，包括：

初始统计模块1，用于在双树结构构造过程中，对每棵子树信息进行统计，将统计结果存入节点数组，所述节点数组中每个元素对应一棵子树的统计信息，统计信息包括子树内数据点个数，子树对应的超球体半径和子树对应的数据点集合，所述节点数组中的元素按照每棵子树内数据点个数降序排列，子树内数据点个数值相同的元素，按照所述子树对应的超球体半径升序排列；

被删树和剪枝树构造模块2，用于对数据点个数大于等于最大剪枝点数的每棵子树进行过滤处理，保留每棵子树中距离质心最近的数据点，将未被保留的数据点过滤删除并存入被删点集合；全部子树处理完毕后，将所述被删点集合中的数据点按照双树构造算法组成被删树；从全部样本点集合中去除被删点集合元素后的剩余元素组成剪枝点集合，将剪枝点集合中的数据点按照双树构造算法组成剪枝树；

递归搜索模块3，用于先在剪枝树内调用K近邻算法查找待查点的Kg个近邻点，其中1≤Kg≤K；之后分别用第1个和第Kg个近邻点作为被删树的初始近邻点，在被删树内查找所述待查点的K个近邻点，当找到的近邻个数不足K个时，将最近邻数组置空，在双树结构内查找所述待查点的K个近邻点；

最优查询参数确定模块4，用于将原始数据集按照给定比例划分为测试集和训练集，利用随机算法生成若干组测试集和训练集，对每组测试集和训练集得到的最优查询参数计算平均值作为最终的最优参数值Kg，使给定数量的待查点在所述剪枝树和被删树内找到K个最近邻。

需要说明的是，上述装置各模块/单元之间的信息交互、执行过程等内容，由于与本申请实施例1中的方法实施例基于同一构思，其带来的技术效果与本申请方法实施例相同，具体内容可参见本申请前述所示的方法实施例1中的叙述。

实施例3

提供一种计算机可读存储介质，所述计算机可读存储介质中存储用于基于双树的高维向量空间样本快速搜索的程序代码，所述程序代码包括用于执行实施例1或其任意实现方式的基于双树的高维向量空间样本快速搜索方法的指令。

计算机可读存储介质可以是计算机能够存取的任何可用介质或者是包含一个或多个可用介质集成的服务器、数据中心等数据存储设备。所述可用介质可以是磁性介质，(例如，软盘、硬盘、磁带)、光介质(例如，DVD)、或者半导体介质(例如固态硬盘(SolidStateDisk、SSD))等。

实施例4

提供一种电子设备，所述电子设备包括处理器，所述处理器与存储介质耦合，当所述处理器执行存储介质中的指令时，使得所述电子设备执行实施例1或其任意实现方式的基于双树的高维向量空间样本快速搜索方法。

具体的，处理器可以通过硬件来实现也可以通过软件来实现，当通过硬件实现时，该处理器可以是逻辑电路、集成电路等；当通过软件来实现时，该处理器可以是一个通用处理器，通过读取存储器中存储的软件代码来实现，该存储器可以集成在处理器中，可以位于所述处理器之外，独立存在。

在上述实施例中，可以全部或部分地通过软件、硬件、固件或者其任意组合来实现。当使用软件实现时，可以全部或部分地以计算机程序产品的形式实现。所述计算机程序产品包括一个或多个计算机指令。在计算机上加载和执行所述计算机程序指令时，全部或部分地产生按照本发明实施例所述的流程或功能。所述计算机可以是通用计算机、专用计算机、计算机网络、或者其他可编程装置。所述计算机指令可以存储在计算机可读存储介质中，或者从一个计算机可读存储介质向另一个计算机可读存储介质传输，例如，所述计算机指令可以从一个网站站点、计算机、服务器或数据中心通过有线(例如同轴电缆、光纤、数字用户线(DSL))或无线(例如红外、无线、微波等)方式向另一个网站站点、计算机、服务器或数据中心进行传输。

具体的，中央处理单元(CPU)根据只读存储器(ROM)中存储的程序或从存储部分加载到随机存取存储器(RAM)的程序执行各种处理。在RAM中，还根据需要存储当CPU执行各种处理等等时所需的数据。CPU、ROM和RAM经由总线彼此连接。输入/输出接口也连接到总线。

下述部件连接到输入/输出接口：输入部分(包括键盘、鼠标等等)、输出部分(包括显示器，比如阴极射线管(CRT)、液晶显示器(LCD)等，和扬声器等)、存储部分(包括硬盘等)、通信部分(包括网络接口卡比如LAN卡、调制解调器等)。通信部分经由网络比如因特网执行通信处理。根据需要，驱动器也可连接到输入/输出接口。可拆卸介质比如磁盘、光盘、磁光盘、半导体存储器等等可以根据需要被安装在驱动器上，使得从中读出的计算机程序根据需要被安装到存储部分中。

在通过软件实现上述系列处理的情况下，从网络比如因特网或存储介质比如可拆卸介质安装构成软件的程序。

本领域的技术人员应当理解。可拆卸介质的例子包含磁盘(包含软盘(注册商标))、光盘(包含光盘只读存储器(CD-ROM)和数字通用盘(DVD))、磁光盘(包含迷你盘(MD)(注册商标))和半导体存储器。或者，存储介质可以是ROM、存储部分中包含的硬盘等等，其中存有程序，并且与包含它们的设备一起被分发给用户。

显然，本领域的技术人员应该明白，上述的本发明的各模块或各步骤可以用通用的计算装置来实现，它们可以集中在单个的计算装置上，或者分布在多个计算装置所组成的网络上，可选地，它们可以用计算装置可执行的程序代码来实现，从而，可以将它们存储在存储装置中由计算装置来执行，并且在某些情况下，可以以不同于此处的顺序执行所示出或描述的步骤，或者将它们分别制作成各个集成电路模块，或者将它们中的多个模块或步骤制作成单个集成电路模块来实现。这样，本发明不限制于任何特定的硬件和软件结合。

虽然，上文中已经用一般性说明及具体实施例对本发明作了详尽的描述，但在本发明基础上，可以对之作一些修改或改进，这对本领域技术人员而言是显而易见的。因此，在不偏离本发明精神的基础上所做的这些修改或改进，均属于本发明要求保护的范围。