基于区域分级航线图算法的数据检索方法

摘要

本发明公开了一种基于区域分级航线图算法的数据检索方法，包括步骤：通过迭代聚类算法对整个区间的数据进行区域划分，并主动选择分级航线图算法HNRG中每级的区域大小和整个航线图的分级数来初始化区域分级航线图，并用于构建索引；利用构建的索引来检索查询数据的近似最近邻等；本发明适用于高维大数据的快速近似检索，实现了快速、精确匹配高维数据，提高了数据检索效率。

说明书

技术领域

本发明涉及数据检索领域，更为具体的，涉及一种基于区域分级航线图算法的数据检索方法。

背景技术

随着互联网，多媒体，以及各种网络应用的高速发展，各种各样的数据影响着、服务着我们的生活，数据规模急速增长，在多个领域以及大企业内，数据规模已经积累到TB、PB甚至EB级别。数据在爆炸式增长的同时出现了一些新的特点，其中最突出的特征是数据的高维化。为了使数据能够更好的表达和记录人们生活的方方面面，许多领域的数据维数动辄成百上千。传统的数据检索方法想精确匹配高维数据难上加难，很难满足时间上的需求，最基本的数据检索过程效率低下，使得自然语言处理，机器学习等上层算法难以进行。为了解决此难题，学者们提出了很多的检索结构，各种树形结构如kd-tree，X-tree，M-tree等被提出。树形结构在数据维度低时效果优秀，但随着数据维数的增加，算法效率急剧下降，检索时间复杂度指数级上升，甚至不及线性扫描的速度，这就是许多检索算法无法克服的“维度灾难”（又称“维度诅咒”）问题。

又因为在工业上，多数应用并不需要完全精确的结果，学者们提出了近似最近邻检索（ANNS）的概念，允许查到结果与最优解存在一定的误差，以此来满足算法在实际应用中对查询效率的要求。目前，性能优秀的近似最近邻检索算法有很多，如annoy、panns、kgraph、faiss等算法和库都得到了广泛的应用。其中，分层通航小世界图（HNSW）算法被认为是近似最近邻检索算法中性能最优的算法，此算法是通航小世界图（NSW）的升级版，通过分层来实现由“粗”到“细”进行搜索，实现了对数级时间复杂度。然而，在实际应用中分层通航小世界图算法有两个明显的缺点：

（1）因为分层通航小世界图算法在构图阶段的层数选择依靠随机数来决定，所以此算法在构图阶段具有较大的随机性，导致此算法的性能有一定的波动。

（2）分层通航小世界图算法也是依靠随机函数选择插入到上层的数据，进一步加大了算法的随机性和性能波动。

发明内容

本发明的目的在于克服现有技术的不足，提供一种基于区域分级航线图算法的数据检索方法，适用于高维大数据的快速近似检索，实现了快速、精确匹配高维数据，提高了数据检索效率。

本发明的目的是通过以下方案实现的：

一种基于区域分级航线图算法的数据检索方法，包括步骤：通过迭代聚类算法对整个区间的数据进行区域划分，并主动选择区域分级航线图算法中每级的区域大小和分级数来初始化区域分级航线图，并用于构建索引；利用构建的索引来检索查询数据的近似最近邻。

进一步地，构建索引包括步骤：

S1，载入向量数据；

S2，计算区域分级航线图算法的分级数和每级的区域大小；

S3，计算区域分级航线图算法中每级的区域中的数据分布；

S4，将数据集插入到区域分级航线图算法中；

S5，保存索引文件。

进一步地，利用构建的索引检索查询数据的近似最近邻包括步骤：

S6，加载区域分级航线图算法的索引文件，获得区域分级航线图算法的索引结构；

S7，在区域分级航线图算法中，利用获得的索引结构检索查询数据的近似最近邻。

进一步地，在步骤S2中，向量数据集D作为最大区域，在数据插入阶段放在第0级，即第0级的区域大小为N，第1级的区域大小为第0级的1/T，第1级的区域大小N/T，第2级的区域大小为N/T

进一步地，步骤S3中，包括步骤：

S31，对第0级进行聚类和数据标记；

S32，对区域分级航线图算法的L级中除第0级以外的每一级各自进行聚类。

进一步地，在步骤S31中，包括步骤：

S311，将第1级的数据点作为第0级的类中心数据点，第2级的数据点作为第1级的类中 心数据点，第3级的数据点作为第2级的类中心数据点，以此类推规律，将下一级的数据点为 上一级的类中心点，记第1级的区域大小为N

S312，将第0级的第一个数据点作为第一个类中心点

S313，计算第0级其他数据点与第

计算得到的最大的

S314，在第0级分别计算每个数据点

S315，对每一个类，计算类中所有数据点的均值作为目标中心，选取类中距离目标中心最近的一个数据点作为这个类新的类中心点；

S316，重复执行步骤S315，直到所有的类中心点不变为止；

S317，对第0级的

步骤S32中，包括步骤：

S321，对被标记能插入到第1级的数据点即第0级的类中心点，进行聚类，计算出第1级的类中心点，标记这些数据点f=2；对标记f=2的数据点即第1级的类中心点，进行聚类，计算出第2级的类中心点，标记这些数据点f=3；以此类推，直到计算完能插入到第L-1级的数据点即第L-2级的类中心点，将其标记为f=L-1。

进一步地，在步骤S4中，包括步骤：

S41，插入第一个数据，在向量数据集D插入之前，区域分级航线图算法的分级数有L级，每级的数据为空，第一个数据没有邻居，直接插入到第0级；

S42，插入所有的数据。

进一步地，在步骤S42中，包括步骤：

S421，设不为空的最大级为第Y级，令l=Y，随机选择一个数据点作为第l级的起始节点

S422，遍历

S423，重复步骤S422，直到

S424，重复执行步骤S422~S423，直到l=0，找到第0级的起始节点

S425，在第r级计算数据点

S426，遍历m个候选节点的邻居节点，计算这些邻居节点与

S427，重复执行步骤S426，直到m个候选节点不再变化为止；

S428，将数据点

S429，重复执行步骤S425~S428，直到数据点

其中，dist表示欧式距离函数。

进一步地，步骤S7中，包括步骤：

S71，从区域分级航线图算法的第l=L-1级开始，随机选择一个起始节点

S72，计算查询向量

S73，重复步骤S72，直到距离

S74，重复步骤S72~S73，直到l=0，计算出第0级的起始节点

S75，在第0级计算查询向量

S76，遍历m个候选节点的邻居节点，计算这些邻居节点与

S77，重复步骤S76，直到m个候选节点不再变化为止；

S78，返回m个候选节点的前n个作为近似最近邻检索的数据检索结果，n为能够指定的数据值，通过指定n的大小来改变近似最近邻检索的返回结果个数；

其中，dist表示欧式距离函数。

本发明的有益效果是：

本发明适用于高维大数据的快速近似检索，实现了快速、精确匹配高维数据，提高了数据检索效率。具体的，通过设计区域分级航线图算法HNRG，并将设计好的算法应用于索引构建和数据检索查询，通过主动选择航线图的分级数和每级的区域大小及数据分布，与应用HNSW的数据检索效果相比，解决了在近似最近邻检索领域中各种应用基于图的算法的方案都存在的随机性大，性能不稳定的问题，使近似最近邻检索的性能更稳定，更高效。其中，索引构建的过程每一步都没有使用随机选择，加上迭代聚类算法使用了距离判断的方法主动选择初始类中心，这些处理步骤使改进后的算法性能十分稳定，尤其适用于高维大数据的快速近似检索，同时，通过分级将每级的数据规模极大减小，搜索时可以快速从顶级向下找到最需要的数据区域，极大的加速了数据查找过程，提高了数据查找精度。

附图说明

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

图1为本发明实施例利用区域分级航线图算法构建索引的流程图；

图2为使用区域分级航线图算法进行近似最近邻检索的流程图。

具体实施方式

本说明书中所有实施例公开的所有特征，或隐含公开的所有方法或过程中的步骤，除了互相排斥的特征和/或步骤以外，均可以以任何方式组合和/或扩展、替换。

如图1，2所示，一种基于区域分级航线图算法的数据检索方法，包括步骤：通过迭代聚类算法对整个区间的数据进行区域划分，并主动选择区域分级航线图算法中每级的区域大小和分级数来初始化区域分级航线图，并用于构建索引；利用构建的索引来检索查询数据的近似最近邻。

进一步地，构建索引包括步骤：

S1，载入向量数据；

S2，计算区域分级航线图算法的分级数和每级的区域大小；

S3，计算区域分级航线图算法中每级的区域中的数据分布；

S4，将数据集插入到区域分级航线图算法中；

S5，保存索引文件。

进一步地，利用构建的索引检索查询数据的近似最近邻包括步骤：

S6，加载区域分级航线图算法的索引文件，获得区域分级航线图算法的索引结构；

S7，在区域分级航线图算法中，利用获得的索引结构检索查询数据的近似最近邻。

进一步地，在步骤S2中，向量数据集D作为最大区域，在数据插入阶段放在第0级，即第0级的区域大小为N，第1级的区域大小为第0级的1/T，第1级的区域大小N/T，第2级的区域大小为N/T

进一步地，步骤S3中，包括步骤：

S31，对第0级进行聚类和数据标记；

S32，对区域分级航线图算法的L级中除第0级以外的每一级各自进行聚类。

进一步地，在步骤S31中，包括步骤：

S311，将第1级的数据点作为第0级的类中心数据点，第2级的数据点作为第1级的类中 心数据点，第3级的数据点作为第2级的类中心数据点，以此类推规律，将下一级的数据点为 上一级的类中心点，记第1级的区域大小为N

S312，将第0级的第一个数据点作为第一个类中心点

S313，计算第0级其他数据点与第

计算得到的最大的

S314，在第0级分别计算每个数据点

S315，对每一个类，计算类中所有数据点的均值作为目标中心，选取类中距离目标中心最近的一个数据点作为这个类新的类中心点；

S316，重复执行步骤S315，直到所有的类中心点不变为止；

S317，对第0级的

步骤S32中，包括步骤：

S321，对被标记能插入到第1级的数据点即第0级的类中心点，进行聚类，计算出第1级的类中心点，标记这些数据点f=2；对标记f=2的数据点即第1级的类中心点，进行聚类，计算出第2级的类中心点，标记这些数据点f=3；以此类推，直到计算完能插入到第L-1级的数据点即第L-2级的类中心点，将其标记为f=L-1。

进一步地，在步骤S4中，包括步骤：

S41，插入第一个数据，在向量数据集D插入之前，区域分级航线图算法的分级数有L级，每级的数据为空，第一个数据没有邻居，直接插入到第0级；

S42，插入所有的数据。

进一步地，在步骤S42中，包括步骤：

S421，设不为空的最大级为第Y级，令l=Y，随机选择一个数据点作为第l级的起始节点

S422，遍历

S423，重复步骤S422，直到

S424，重复执行步骤S422~S423，直到l=0，找到第0级的起始节点

S425，在第r级计算数据点

S426，遍历m个候选节点的邻居节点，计算这些邻居节点与

S427，重复执行步骤S426，直到m个候选节点不再变化为止；

S428，将数据点

S429，重复执行步骤S425~S428，直到数据点

其中，dist表示欧式距离函数。

进一步地，步骤S7中，包括步骤：

S71，从区域分级航线图算法的第l=L-1级开始，随机选择一个起始节点

S72，计算查询向量

S73，重复步骤S72，直到距离

S74，重复步骤S72~S73，直到l=0，计算出第0级的起始节点

S75，在第0级计算查询向量

S76，遍历m个候选节点的邻居节点，计算这些邻居节点与

S77，重复步骤S76，直到m个候选节点不再变化为止；

S78，返回m个候选节点的前n个作为近似最近邻检索的数据检索结果，n为能够指定的数据值，通过指定n的大小来改变近似最近邻检索的返回结果个数；

其中，dist表示欧式距离函数。

在实施例中，可以通过指定n的大小来改变近似最近邻检索返回结果的个数，通过HNRG算法，实现了更高效，更稳定的检索效果。

在本发明的其他实施例中，可以提供一种基于区域分级航线图算法的数据检索方法，图1利用区域分级航线图算法构建索引的流程图，图2表示使用区域分级航线图算法进行近似最近邻检索的流程图。该方案的索引构建过程中，可以通过迭代聚类主动选择航线图的分级数和每一级的区域大小以及数据值，每一步都没有使用随机选择，迭代聚类算法使用了距离判断的方法主动选择初始类中心，这些方法使基于区域分级航线图算法的数据检索方法的性能十分稳定。同时，在进行近似最近邻数据检索过程中，基于区域分级航线图算法的数据检索方法通过分级将每级的数据规模极大减小，搜索时可以快速从顶级向下找到最需要的区域，极大的加速了查找过程，提高了查找精度等，此处不再赘述。

本发明中的区域分级航线图算法为自定义名称，其主要原理为通过区域划分将图分为不同数据区域，类比为国家的不同省份，分级将数据量逐级减小，级之间的关系类比于省份和市，基以此命令区域分级，在区域分级航线图中检索类似飞机航线一样，可以先定位到某个区域，在深入下一级搜索，即类似航线先飞到某一个省，再定位市，再定位县，基以此为思路命令航线图算法，综上提出的一种区域分级航线图算法，以及具体所提出区域分级航线图算法的数据检索方法的具体实施步骤。

本发明功能如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读存储介质中。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，在一台计算机设备（可以是个人计算机，服务器，或者网络设备等）以及相应的软件中执行本发明各个实施例所述方法的全部或部分步骤。而前述的存储介质包括：U盘、移动硬盘、或者光盘等各种可以存储程序代码的介质，进行测试或者实际的数据在程序实现中存在于只读存储器（Random Access Memory，RAM）、随机存取存储器（Random Access Memory，RAM）等。

除以上实施例以外，本领域技术人员根据上述公开内容获得启示或利用相关领域的知识或技术进行改动获得其他实施例，各个实施例的特征可以互换或替换，本领域人员所进行的改动和变化不脱离本发明的精神和范围，则都应在本发明所附权利要求的保护范围内。