高维数据的近邻搜索方法以及快速近似图像搜索方法

摘要

本发明涉及高维数据的近邻搜索技术领域，特别涉及一种高维数据的近邻搜索方法，包括以下步骤：1、利用机器学算法建立具有预定深度的搜索树；2、将数据库中的高维数据放入搜索树中；3、利用经过步骤2建立好的搜索树进行近邻搜索。还涉及一种快速近似图像搜索方法，图像的特征向量为高维数据，利用本发明的高维数据的近邻搜索方法搜索；4、建立多个步骤1中所述的搜索树，根据多个搜索树得到多个近邻搜索结果，然后选取所有结果的交集作为最终的搜索结果。本发明的高维数据的近邻搜索方法以及快速近似图像搜索方法，能够处理高维数据，真正达到次线性速度的近邻搜索，并且搜索结果稳定，正确率高。

主权项

一种高维数据的近邻搜索方法，从高维数据的数据库中搜索高维样本数据S的近邻数据，其特征在于包括以下步骤：(1)利用机器学习算法建立具有预定深度的搜索树：(a)给定N个代表数据库中的高维数据分布特性的训练样本，输入N个训练样本以及训练样本的N×N近邻关系矩阵，根据近邻关系矩阵把整个高维数据空间分割为两个子空间，使分割后的子空间包含最多的近邻数据；(b)将步骤(a)中分割后的子空间作为待分割子空间；(c)根据近邻关系矩阵把待分割子空间分割成两个新的子空间，使本次分割后的新的子空间包含最多的近邻数据；(d)判断新的子空间是否分割到预定的深度，如果是，则停止分割；否则将新的子空间作为待分割子空间，并返回步骤(c)；分割后的高维数据空间与搜索树的对应关系为：搜索树的根节点对应整个高维数据空间，每个结点的两个子节点分别对应同一次分割所得到的两个子空间；(2)将数据库中的高维数据放入搜索树中；(3)利用经过步骤(2)建立好的搜索树进行近邻搜索：输入高维样本数据S，找出高维样本数据S在搜索树中所对应的节点，所述的节点中的高维数据即为找出的近邻数据；(4)建立多个步骤(1)中所述的搜索树，根据所述的多个搜索树得到多个步骤(3)的近邻搜索结果，然后选取所有结果的交集作为最终的搜索结果。