2024年大数据最新ElasticSearch学习篇11_ANNS之基于图的NSW、HNSW算法

大家好，欢迎来到IT知识分享网。

而Lucene和ES使用的多维数据紧邻搜索是改进的BKD以及HNSW，Lucene从6.0版本引入了BKD，关于BKD原理参考往期博客，该BKD结构就是基于空间分割算法。Elasticsearch从8.0版本开始引入了向量近邻检索k-nearest neighbor（kNN）search功能，该功能支持使用HNSW（Hierarchical Navigable Small World）算法来优化向量检索的性能。下面主要了解相关算法以及学习基于图的NSW、HNSW算法。

目录

一、ANNS

1、ANNS概述

1. ANNS（Approximate Nearest Neighbor Search）:
   • 目的：ANNS旨在高维空间中快速找到与查询点近似最近的邻居，牺牲一定的精确度以换取搜索速度的提升。
   • 原理：通过构建特定的数据结构（如基于空间划分的KD-Tree、局部敏感哈希LSH等）或使用特定的算法逻辑来减少在高维空间中搜索最近邻所需的计算量。
   • 应用场景：广泛应用于推荐系统、图像检索、模式识别等领域，特别是在处理大规模高维数据时。
2. ANN（Artificial Neural Network）:
   • 目的：ANN是一种模仿生物神经网络行为的计算模型，用于识别数据中的复杂模式和关系，进行分类、回归等任务。
   • 原理：由多层神经元组成，通过前向传播和反向传播算法，调整神经元之间的连接权重，以学习输入与输出之间的映射关系。
   • 应用场景：广泛应用于图像识别、语音识别、自然语言处理等领域。
3. KNN（K-Nearest Neighbors）:
   • 目的：KNN是一种基于实例的学习方法，用于分类或回归任务，通过查找最近的K个邻居来预测新样本的类别或值。
   • 原理：不需要显式的训练过程，而是直接根据距离度量（如欧氏距离）在训练数据集中找到与新样本最近的K个样本，然后根据这些邻居的信息进行预测。
   • 应用场景：适用于小到中等规模的数据集，常用于分类问题、推荐系统等。

总结：

• ANNS关注于高维空间中的近似最近邻搜索，主要解决搜索效率问题。
• ANN是一种模拟人脑神经网络的计算模型，用于学习数据的复杂模式。
• KNN是一种简单直接的基于距离的分类或回归方法，侧重于通过最近的邻居进行预测。

2、常见的ANNS算法以及原理简单概述

大概可以分为四大类

• 基于空间分割算法：思想参考BSP，常见的结构比如KD-Tree以及BKD、BBF等优化结构算法，主要思路就是构建多维数据索引树，BKD则是基于KD-Tree、B-Tree考虑到磁盘存储利用率、更新破坏结构而提出的一种动态磁盘树结构，BBF则是利用优先队列减少KD-Tree回溯判断次数，提升检索效率。还有其他的一些结构如R-Tree、四叉树等实现KNN，都是基于这个思路。
• 基于哈希的算法：Locality-Sensitive Hashing 高维空间的两点若距离很近，他们哈希值有很大概率是一样的；若两点之间的距离较远，他们哈希值相同的概率会很小 。一般是根据具体的场景需求选取哈希函数，这种算法因为损失了大量数据，精度可能不是那么好，但是效率比较高。
• 基于量化的算法：基本思路就是向量维度分治，牺牲部分精度，提高效率。把原来的向量空间分解为若干个低维向量空间的笛卡尔积，并对分解得到的低维向量空间分别做量化（quantization），这样每个向量就能由多个低维空间的量化code组合表示 。比如PQ（Product Quantization，乘积量化）是一种常用的近似最近邻搜索算法。还有一些优化算法如IVFPQ，基于倒排的乘积量化算法，增加粗量化阶段，对样本进行聚类，划分为较小的region ，减少候选集数据量（之前是需要遍历全量的样本，时间复杂度为O(N*M)）。
• 基于图的算法：基本思路就是基于图的紧邻查找，比如NSW、HNSW算法

还有一些商业开源ANNS比如Spotify 的 ANNOY、Google 的 ScaNN、Facebook的Faiss等，性能基准参考ann-benchmarks：https://github.com/erikbern/ann-benchmarks#evaluated ，使用的算法不同，应对的业务检索场景不同，测试数据集不同，算法的表现性能就可能不同，因此性能好只是相对的。

1、ANNOY (Approximate Nearest Neighbors Oh Yeah) 特点: ANNOY使用了基于树的算法来构建索引，通过构建多棵树并在这些树上进行搜索来实现快速的近似最近邻查找。ANNOY特别适用于在内存中进行大规模搜索，因为它的数据结构可以高效地加载和查询。应用场景: 音乐推荐、图像搜索等。这个有点类似BKD，创建多颗二叉树以及使用优先队列，但是还是不太一样。它的原理基于两个关键思想：随机投影和候选筛选。

• 首先，ANNOY使用随机投影来降低向量的维度。它将高维向量映射到低维空间，以减少计算和存储的开销。随机投影是一种快速的降维方法，它通过随机选择一组投影向量来将原始向量映射到低维空间。通过降低维度，ANNOY能够在保持搜索质量的同时，显著减少计算和存储的成本。
• 其次，ANNOY使用候选筛选来加速搜索过程。在搜索时，ANNOY首先使用随机投影将查询向量映射到低维空间。然后，它使用一种快速的候选筛选方法，如局部敏感哈希（Locality Sensitive Hashing）或随机k-d树（Random k-d Tree），来找到一组候选近邻。最后，ANNOY对候选集进行精确的距离计算，以找到最近的邻居。

2、ScaNN (Scalable Nearest Neighbors) 开发者: Google 特点: ScaNN是一种用于向量相似性搜索的库，它通过优化量化和树搜索的结合来提高搜索效率和准确性。ScaNN旨在提供高效的搜索能力，特别是在处理超大规模数据集时。应用场景: 大规模图像检索、文本相似性搜索等。ScaNN（Scalable Nearest Neighbors）是一种用于高效近邻搜索的算法。它的原理基于两个关键思想：分层索引和候选筛选。

• 首先，ScaNN使用分层索引来组织数据。它将数据集划分为多个层级，每个层级都有一个索引结构。这些索引结构可以是传统的索引方法，如KD-Tree或LSH（Locality Sensitive Hashing），也可以是近似索引方法，如HNSW（Hierarchical Navigable Small World）。通过使用分层索引，ScaNN可以将搜索空间分解为多个子空间，从而减少搜索的复杂度。
• 其次，ScaNN使用候选筛选来加速搜索过程。在搜索时，ScaNN首先使用索引结构找到一组候选近邻。然后，它使用一种快速的候选筛选方法，如乘积量化（Product Quantization）或局部敏感哈希（Locality Sensitive Hashing），来进一步缩小候选集。最后，ScaNN对缩小后的候选集进行精确的距离计算，以找到最近的邻居。

3、Faiss (Facebook AI Similarity Search) 开发者: Facebook 特点: Faiss是一个高效的相似性搜索库，专注于密集向量的快速检索和聚类。Faiss使用了先进的向量量化技术，能够支持在大规模数据集上进行高效的相似性搜索。 应用场景: 图像检索、聚类分析、大规模机器学习等。Faiss的原理基于两个关键思想：索引结构和量化编码。

• 首先，Faiss使用索引结构来组织向量数据。它支持多种索引结构，包括平面索引（Flat Index）、倒排索引（IVF Index）、乘积量化索引（PQ Index）等。这些索引结构可以根据数据集的特点和需求进行选择。例如，倒排索引适用于高维数据集，乘积量化索引适用于低维数据集。通过使用索引结构，Faiss能够将搜索空间划分为多个子空间，从而加速相似度搜索。
• 其次，Faiss使用量化编码来减少向量的维度。它将高维向量映射到低维空间，以降低计算和存储的成本。Faiss支持多种量化编码方法，如乘积量化（Product Quantization）、向量量化（Vector Quantization）等。这些方法可以将向量划分为多个子向量，并对每个子向量进行编码。通过使用量化编码，Faiss能够在保持搜索质量的同时，显著减少计算和存储的开销。

4、HNSW (Hierarchical Navigable Small World) 特点: HNSW是一种基于图的近似最近邻搜索算法，通过构建一个分层的图结构来实现高效的搜索。HNSW能够在大规模数据集上实现快速且准确的近似最近邻搜索，具有较低的内存消耗和较快的查询速度。应用场景: 推荐系统、图像检索、文本搜索等。

5、QSG-NGT：该算法在当前业界最权威的ANN-Benchmarks中荣获第一。NGT是一种结合了图和树结构的算法，用于高效地进行最近邻搜索。它主要由两个组成部分构成：Neighborhood Graph（邻域图）和Tree（树结构，如VP-Tree、KD-Tree等）。NGT的核心思想是利用邻域图进行精确或近似的最近邻搜索，同时使用树结构加速搜索过程。

2.1、乘积量化PQ概述

乘积量化（Product Quantization）简称 PQ。是和VLAD算法由法国INRIA实验室一同提出来的，为的是加快图像的检索速度，所以它是一种检索算法。现有的检索算法存在一些弊端，如 kd树不适合维度高的数据，哈希（LSH）适用中小数据集，而乘积量化这类方法，内存占用更小、数据动态增删更方便。基本思路就是聚类、量化压缩向量维度，提升检索速率。

k-means聚类

先看k-means聚类，k-means聚类算法是一种常用的无监督学习算法，用于将数据集划分为k个不重叠的簇。其基本思想是通过迭代优化的方式，将数据点分配到最近的聚类中心，并更新聚类中心的位置，直到满足停止准则。k-means聚类算法的步骤如下：

1. 初始化：选择要聚类的数据集和要划分的簇的数量k。随机选择k个数据点作为初始的聚类中心。
2. 分配数据点：对于每个数据点，计算其与每个聚类中心的距离，并将其分配给距离最近的聚类中心。
3. 更新聚类中心：对于每个聚类，计算其所有分配给它的数据点的平均值，并将该平均值作为新的聚类中心。这种的叫做平均聚类，平均值就代表当前聚类簇ID
4. 重复步骤2和步骤3，直到聚类中心不再发生变化或达到预定的迭代次数。
5. 输出结果：最终的聚类中心即为聚类结果，每个数据点被分配到一个簇中。

需要注意的是，k-means算法对初始聚类中心的选择敏感，可能会得到不同的结果。因此，可以多次运行算法，选择最优的结果。另外，k-means算法对于非凸形状的数据集效果可能不佳，此时可以考虑使用其他聚类算法。

ps：凸形数据集：如果一个数据集D是凸的，简单来说，数据集D中任意两点的连线上的点，也会在数据集D内，那么数据集D就是一个凸集。

简单的k-means代码demo

package org.example.kmeans; import java.util.ArrayList; import java.util.List; /\*\* \* @author sichaolong \* @createdate 2024/3/29 10:20 \*/ public class SimpleKMeansDemo { private int k; // 聚类的个数 private List<Point> points; // 数据集 private List<Cluster> clusters; // 聚类结果 public SimpleKMeansDemo(int k, List<Point> points) { this.k = k; this.points = points; this.clusters = new ArrayList<>(); } public void run() { // 初始化聚类中心, 随机选取k个数据点作为初始聚类中心 for (int i = 0; i < k; i++) { Cluster cluster = new Cluster(); cluster.setCentroid(points.get(i)); clusters.add(cluster); } // 循环直到收敛 boolean converged = false; while (!converged) { // 清空聚类结果 for (Cluster cluster : clusters) { cluster.clearPoints(); } // 将每个数据点分配到最近的聚类中心 for (Point point : points) { Cluster nearestCluster = null; double minDistance = Double.MAX\_VALUE; // 遍历每个聚类中心，找到最近的 for (Cluster cluster : clusters) { double distance = point.distanceTo(cluster.getCentroid()); if (distance < minDistance) { minDistance = distance; nearestCluster = cluster; } } nearestCluster.addPoint(point); } // 更新聚类中心 converged = true; // 遍历每个聚类中心，如果聚类中心没有发生变化，则收敛 for (Cluster cluster : clusters) { Point oldCentroid = cluster.getCentroid(); Point newCentroid = cluster.calculateCentroid(); if (!oldCentroid.equals(newCentroid)) { cluster.setCentroid(newCentroid); converged = false; } } } } public List<Cluster> getClusters() { return clusters; } public static void main(String[] args) { // 创建数据集 List<Point> points = new ArrayList<>(); points.add(new Point(1, 1)); points.add(new Point(1, 2)); points.add(new Point(2, 2)); points.add(new Point(5, 5)); points.add(new Point(6, 6)); points.add(new Point(7, 7)); // 创建K-means对象并运行算法 SimpleKMeansDemo kMeans = new SimpleKMeansDemo(2, points); kMeans.run(); // 输出聚类结果 List<Cluster> clusters = kMeans.getClusters(); for (int i = 0; i < clusters.size(); i++) { System.out.println("Cluster " + (i + 1) + ":"); for (Point point : clusters.get(i).getPoints()) { System.out.println("(" + point.getX() + ", " + point.getY() + ")"); } System.out.println(); } } } class Point { private double x; private double y; public Point(double x, double y) { this.x = x; this.y = y; } public double getX() { return x; } public double getY() { return y; } /\*\* \* 计算两个点之间的距离,使用欧几里徳距离 \* @param other \* @return \*/ public double distanceTo(Point other) { double dx = x - other.x; double dy = y - other.y; return Math.sqrt(dx \* dx + dy \* dy); } @Override public boolean equals(Object obj) { if (this == obj) { ![img](https://img-blog.csdnimg.cn/img_convert/4e4406ed5ef69e7b500bdebd9d68870c.png) ![img](https://img-blog.csdnimg.cn/img_convert/e86a3ca49f3906f56c3623bdfd.png) 网上学习资料一大堆，但如果学到的知识不成体系，遇到问题时只是浅尝辄止，不再深入研究，那么很难做到真正的技术提升。 [需要这份系统化资料的朋友，可以戳这里获取](https://bbs.csdn.net/topics/) 一个人可以走的很快，但一群人才能走的更远！不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人，都欢迎加入我们的的圈子（技术交流、学习资源、职场吐槽、大厂内推、面试辅导），让我们一起学习成长！ 1P-91)] 网上学习资料一大堆，但如果学到的知识不成体系，遇到问题时只是浅尝辄止，不再深入研究，那么很难做到真正的技术提升。 [需要这份系统化资料的朋友，可以戳这里获取](https://bbs.csdn.net/topics/) 一个人可以走的很快，但一群人才能走的更远！不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人，都欢迎加入我们的的圈子（技术交流、学习资源、职场吐槽、大厂内推、面试辅导），让我们一起学习成长！