在 C# 中实现向量数据库（带 kd 树）
4.33/5 (9投票s)
如何在 C# 中实现 kd 树？
引言
之前的文章已经讨论过向量数据库，我们鼓励读者参考这些文章以获得基础知识。在本系列文章中，我们将深入探讨其内部工作原理，揭示 kd 树等底层数据结构。
以下书籍对本系列的总结有所助益。
算法导论 (Cormen, Leiserson, Rivest, Stein)
本文最初发布于：使用 kd 树在 C# 中实现向量数据库
什么是向量数据库？
向量数据库是专门设计的数据库，用于高效地存储和查询高维向量数据。与针对表格数据进行优化的传统关系数据库不同，向量数据库专门用于处理作为主要数据类型的向量。
它们提供了存储、索引和查询向量的机制，这些机制能够保留其高维结构并实现高效的相似性搜索和其他基于向量的操作。向量数据库的例子包括 Milvus、Faiss 和 Pinecone。
好的，但我们为什么要存储向量？
我们已经有了关系数据库和其他存储数据的范例。那么，为什么还要费心使用这些新型数据库呢？
好吧，传统数据库非常适合存储传统数据。例如，电子商务网站处理的交易和产品可以用具有属性的表格对象来表示，从而可以使用简单的 SQL 语法轻松查询这些数据。
然而，随着人工智能的出现以及处理大量数据的需求，这种方法变得不太实用。
因此，需要一种预处理方式来转换数据，例如文档或图像，将其转换为可查询的对象。这种转换称为嵌入，它包括将抽象数据表示为传统向量空间中的向量。
重要
设计这种嵌入更像是一门艺术而非科学，它取决于我们要表示的特定对象（例如，文档可以使用 TF-IDF 范式进行建模）。最终，嵌入构成了真正的附加值，并且很可能是人工智能应用中最具挑战性的方面。
一旦数据存储在向量空间中，一切都变得简单了：通过计算两个向量之间的相似度，可以轻松找到相似的对象，并且可以对对象执行算术运算。例如，我们可以从一个文档向量中减去另一个文档向量，并探索生成的文档向量。
但是如何存储所有这些向量呢？
现在我们已经了解了向量的重要性，一个自然的问题出现了：我们如何有效地存储和查询这些向量？我们当然可以利用现有的平台，如关系数据库或 NoSQL 数据库，但很快就会发现它们的底层基础并不适合此目的。为什么？因为向量本质上是多维数据，而传统数据库缺乏能够操作它们的原生数据结构。
摘要
向量数据库是专门设计用于高效存储和查询向量（向量是抽象对象（如文档或图像）的数学表示）的数据库。
本文的其余部分旨在探讨适合此目的的潜在数据结构，观察它们的工作原理，并实现简化版本以理解如何对其进行增强。
向量数据库的应用有哪些？
如前所述，向量本质上表示多维数据，它封装了抽象对象。在下面的图像中，我们的嵌入函数表示为 f。
与这些数据相关的需求是什么？换句话说，向量数据库的应用有哪些？
考虑一个场景，我们在其中存储描述产品的文档（例如，在电子商务网站上），并且我们已经为文本数据表示定义了一个嵌入模型。
由此，我们可以开发一个推荐系统：对于目录中的每个产品，识别出推荐的 5 个最佳产品。在数学上，这涉及到为代表目录中产品的每个向量找到向量空间中的 5 个最近邻。
重要
很明显，嵌入模型至关重要，必须精心设计：现实世界中距离最近的文档在向量空间中也应该彼此接近，以便提供有意义的推荐。
那么，我们如何进行高效搜索呢？
为了使本文不那么抽象，现在让我们实现一些 C# 代码来探索最近邻搜索的一个非常基础的实现。此实现将作为我们接下来将要探索的更复杂数据结构的基准。
首先，我们将定义一个 Embedding 类，作为双精度数组的一个简单模型。
public class Embedding
{
public double[] Records { get; set; }
public Embedding(double[] records)
{
Records = records;
}
}
接下来，我们将定义一个接口，允许我们存储和查询嵌入。我们将从探索此接口的朴素实现开始，然后是更复杂的实现。
public interface IEmbeddingStorer
{
void LoadEmbeddings(List<Embedding> embeddings);
List<Embedding> FindNearestNeighbours(IDistance distance, Embedding embedding, int n);
}
此接口很简单，包含两个方法：一个用于加载一组初始嵌入，另一个用于查找目标嵌入的最近邻。
为了完成实现，我们还将引入一个接口来表示两个嵌入之间的距离。
public interface IDistance
{
double DistanceBetween(Embedding e1, Embedding e2);
double DistanceBetween(double d1, double d2);
}
具体的实现可以是欧几里得距离。值得注意的是，其他实现也是可能的，具体取决于特定应用程序的要求。
public class EuclidianDistance : IDistance
{
public double DistanceBetween(Embedding e1, Embedding e2)
{
var dimension = e1.Records.Length; var distance = 0.0;
for (var i = 0; i < dimension; i++)
{
distance = distance + Math.Pow(e1.Records[i]-e2.Records[i], 2);
}
return distance;
}
public double DistanceBetween(double d1, double d2)
{
return Math.Pow(d1-d2, 2);
}
}
有了这些基础之后，我们现在可以实现 FindNearestNeighbours 方法的第一个朴素版本。这种直接的方法涉及遍历所有嵌入以找到 5 个最近的嵌入。
public class ListEmbeddingStorer : IEmbeddingStorer
{
private List<Embedding> _embeddings;
public void LoadEmbeddings(List<Embedding> embeddings)
{
_embeddings = embeddings;
}
public List<Embedding> FindNearestNeighbours(IDistance distance, Embedding embedding, int n)
{
var res = new List<EmbeddingWithDistance>();
foreach (var e in _embeddings)
{
var dist = distance.DistanceBetween(e, embedding);
if (res.Count < n) res.Add(new EmbeddingWithDistance(dist, e));
else
{
var max = res.OrderByDescending(i => i.Distance).First();
if(dist < max.Distance)
{
res.Remove(max);
res.Add(new EmbeddingWithDistance(dist, e));
}
}
}
return res.Select(t => t.Embedding).ToList();
}
}
public class EmbeddingWithDistance
{
public double Distance { get; set; }
public Embedding Embedding { get; set; }
public EmbeddingWithDistance(double distance, Embedding embedding)
{
Distance = distance;
Embedding = embedding;
}
}
重要
事实上，这种实现是朴素的，因为其时间复杂度与项目数量成线性关系：必须访问每个记录才能生成结果。因此，它不能扩展到包含只有几千个项目的较小数据集。
现代人工智能应用处理海量数据，通常达到数亿条记录。因此，依赖于线性时间搜索操作是不可行的，向量数据库能够高效地查找最近邻，或者换句话说，能够快速执行搜索至关重要。我们的挑战是优先考虑一个为高效多维搜索而设计的数据结构。
现在，我们将通过引入 kd 树数据结构来探索如何高效地存储多维数据。我们的目标是有效地处理多维搜索。
什么是二叉搜索树？
在计算机科学中，当处理搜索操作时，从业人员经常求助于树结构。虽然我们在此不会深入探讨这个话题，但我们将从这些数据结构中汲取灵感来实现 kd 树。
信息
树的详尽介绍请参阅以下权威教科书。
算法导论 (Cormen, Leiserson, Rivest, Stein)
二叉搜索树 (BST) 是一种二叉树数据结构，具有以下特性：
- 二叉搜索树中的每个节点最多可以有两个子节点，分别称为左子节点和右子节点。
- 左子树中的所有节点的值都小于节点的值。
- 右子树中的所有节点的值都大于节点的值。
此属性确保 BST 是有序的，使得对于任何节点，其左子树中的所有节点的值都小于节点的值，其右子树中的所有节点的值都大于节点的值。
这是一个二叉搜索树的简要示例。
5
/ \
3 8
/ \ \
2 4 10
- 根节点的值为 5。
- 根节点的左子树（根为 3）包含值小于 5 的节点（即 3、2、4）。
- 根节点的右子树（根为 8）包含值大于 5 的节点（即 8、10）。
BST 在搜索操作方面表现出色，这使其非常适合数据库索引等任务。因此，为我们的需求从中汲取灵感是很自然的。但是，与处理一维数据（通过比较每个节点的值并选择方向）的二叉搜索树不同，kd 树旨在在树结构内管理多维数据。然而，这需要对该方法进行一些根本性的更改。
什么是 kd 树？
kd 树是一种空间划分数据结构，用于组织 k 维空间中的点。
-
kd 树是二叉树，其中每个节点代表 k 维空间中的一个点。
-
在树的每个级别，都使用不同的维度来分割空间。根节点根据第一个维度进行分割，下一级别根据第二个维度进行分割，依此类推，依次遍历维度。
-
kd 树中的每个节点都包含一个 k 维点（在之前的讨论中称为嵌入）以及对其左子节点和右子节点的引用。
以下是二维数据点 (k=2) 的 kd 树结构的示例。
level 0 (split on first dimension):
(5, 3)
/ \
level 1 (split on second dimension):
(2, 4) (9, 6)
/ \ / \
level 2 (split on first dimension):
(3, 1) (1, 7) (8, 5) (10, 8)
- 根节点根据第一个维度进行分割。
- 第二级根据第二个维度进行分割。
- 第三级再次根据第一个维度进行分割，依此类推。
信息 1
在实际用例中，数据点会分布在更多维度上，但从视觉上表示它们会变得很困难。因此，kd 树的图示通常使用 k=2 以简化。
信息 2
kd 树由 Jon Bentley 于 1975 年引入（原始论文可以在这里找到）。虽然我们此处提出的定义在术语上与原始定义略有不同，但它最终实现了相同的目标并执行高效的搜索。
信息 3
kd 树是通过根据维度的中值递归地分割数据点来构建的。这确保了树的平衡，从而优化了搜索性能。
我们的定义规定 kd 树本质上是二叉树。因此，嵌入是按特定顺序插入的：将对应于分割维度的值与沿同一轴的当前节点的值进行比较。如果该值更大，则我们将嵌入递归地插入到右节点；否则，则将其插入到左节点。此过程一直持续到到达叶节点。
例如，如何将 (4,11) 插入到前面的树中？以下是执行此操作的详细步骤。
-
根节点的第一个维度是 5，要插入的嵌入的第一个维度是 4，因此我们向下遍历到左侧（4 < 5）。
-
我们现在与节点 (2,4) 进行比较。由于我们在第二个级别，我们根据第二个维度进行比较。要插入的嵌入的第二个维度是 11，因此我们向下遍历到右侧（11 > 4）。
-
我们现在与节点 (1,7) 进行比较。由于我们在第三个级别，我们再次根据第一个维度进行比较。要插入的嵌入的第一个维度是 4，因此我们向下遍历到右侧（1 < 4）。
level 0 (split on first dimension):
(5, 3)
/ \
level 1 (split on second dimension):
(2, 4) (9, 6)
/ \ / \
level 2 (split on first dimension):
(3, 1) (1, 7) (8, 5) (10, 8)
\
(4, 11)
有了这个理论基础，我们现在将探讨如何进行高效搜索。前面，我们讨论了为什么在某些应用程序中查找特定嵌入的最近邻至关重要。我们现在的目标是演示如何使用 kd 树有效地实现此操作。
该方法涉及类似于传统二叉树的操作，我们遍历整个树来定位目标对应的子空间。与经典的 BST 不同，该过程并没有就此结束，因为最近邻可能存在于其他子树中。为了说明我们的讨论，我们将依赖于以下示例。
第一种情况
我们将从一个简单的情况开始，即通过遍历树最初找到的嵌入确实是最近邻：假设我们要查找 (25,70) 的最近邻。
在这里，最近的点不可能存在于其他子空间中，因为到边界（数学上的超平面）的距离大于到子树中任何点的距离。
信息
在数学上，如果沿当前分割轴的正交投影大于目标嵌入沿同一轴的正交投影，则我们可以跳过子树中的所有点并向上移动到父级别。
第二种情况
现在，让我们考虑一个更有趣的场景：我们要查找 (52,72) 的最近邻。
通过向下遍历树最初找到的最近嵌入是 (60,80)，但很明显，这不是我们目标的最近点。
事实上，到另一个子空间（包含点 (55,1) 的子空间）的距离小于到最初找到的点 (60,80) 的距离。因此，这个子空间中的一个点很可能就是最近的，我们需要对其进行调查。访问完这个子空间后，我们继续向根方向进行，并探索根的左子树中是否存在最近的嵌入。在此特定情况下，我们可能会访问整个树，从而无法与朴素实现相比获得任何性能提升。
非常重要
为了进行搜索，我们从最可能的子空间开始，然后向上遍历树直到到达根。需要注意的是，我们必须检查所有级别，不能过早停止。我们的目标是在此过程中访问最少的子树。
信息
kd 树中的搜索通常以对数时间复杂度进行操作，这使其非常受欢迎。
现在我们对 kd 树的含义及其如何高效执行多维数据搜索有了全面的了解，让我们通过在 C# 中实现它来付诸实践。但是，为了避免使本文过于冗长，有兴趣了解此实现的读者可以在此处找到续篇。