理解非结构化数据的向量化与相似性搜索

本文大纲

非结构化数据

我们最熟悉的存储系统，比如Excel表格和关系型数据库（如 MySQL、PostgreSQL等），这些工具通过固定的格式和列来存储和管理数据，使得数据是结构化的，让数据搜索非常简单和方便。

但是，有一类数据和结构化数据很不一样，这些数据没有固定的格式或结构，如文本、图片、视频、音频和社交媒体数据。最熟悉的使用场景就是软件媒体，这些软件都有推荐机制，可以精准地向用户推送感兴趣的内容，而这个内容就是前面我们提到的“另类数据”，非结构化的数据。

非结构化数据由于缺乏固定格式，对它们的索引、搜索和分析比结构化数据复杂得多。一种实现非结构化数据的高效搜索是向量搜索。具体来讲，就是将这些数据按照一些特征进行分类，转化成向量，存储在一个索引数据库中，然后在数据库中搜索，找到 “接近 “的内容。

基本理论

向量

从数学角度出发，向量表示从一个点到另一个点的箭头。比如下面这种图的a,b点，a点向量从(100,50)到（-50,-50）, b点向量从（0,0）到(100,-50)。

简单来讲，我们倾向于定一个向量(x,y), 表示从原点(0,0)到(x,y)的箭头。

维度

在一个平面坐标系上，一个向量可以用两个维度表示。但是在更复杂的场景中，我们可以定义更多维度，向量中每个元素表示一个维度，比如$(a_1,a_2,a_3,…,a_n)$, 这样可以存储更多信息。

比如，我们可以定义一个“交通工具”的数据集，如下表所示，定义4个特征维度：车轮数量、是否有引擎、是否是陆地车、最大载客量。

所以car的向量可以用(4,yes, yes, 5)表示，实际上，我们更习惯量化（为了方便计算），所以可以另yes为1，no为0，所以car的向量为(4,1,1,5);

同理，bicycle为(2,0,1,1)。

所以对于一个向量来讲，每个维度可以看成是一个特征。

相似性

两条数据相似性越高，关联性越高，那么如何确定向量之间的相似性呢？

对于一个简单的二维坐标系中的向量，如下图所示，我们可以如何定义最相似呢？哪个向量和p最“接近”？

可以从两个角度看，

• 如果方向相同意味着相似，那显然a矢量和p矢量方向一样，b矢量和p矢量方向相反，所以从这个角度看，a和p最相似；b和p最不像；
• 如果大小相同意味着相似，那c和p相似，a和b都不像。

实际上，在向量搜索中，大小基本不会单独作为比较向量相似的权重，因为每个维度的数值区间不同，很容易找出大小相同，但是每个维度相差很大的向量。

所以，我们比较向量的相似性，可以有两种方式：单纯看方向；或者同时考虑大小和方向两个因素。在向量搜索中，我们实际上是匹配相似的向量。

相似性测量

根据上面的结论，可以有4种直接方式衡量相似性：

1. 欧氏距离 (Euclidean Distance)

• 特点：考虑了大小和方向两个因素
• 定义：计算两个向量在n维空间中的直线距离，常用于量度两个点之间的绝对距离。
• 公式：

$$
d(\mathbf{A}, \mathbf{B}) = \sqrt{\sum_{i=1}^n (A_i - B_i)^2}
$$

• 应用：在许多实际应用中，当数据的绝对大小重要时使用，如在定位服务和物理科学中。

2. 曼哈顿距离 (Manhattan Distance)

• 特点：考虑了大小和方向两个因素
• 定义：计算在标准坐标系中的两个点在矩形网格上的路径所需的最小转弯数（路线和坐标轴平行）
• 公式：

$$
d(\mathbf{A}, \mathbf{B}) = \sum_{i=1}^n |A_i - B_i|
$$

• 应用：在城市规划、计算机视觉和集群分析中使用，适合用于网格布局和离散空间。

3. 余弦相似度 (Cosine Similarity)

• 特点：考虑方向因素
• 定义：测量两个向量在方向上的接近程度，忽略它们的大小。
• 公式：

$$
\text{cosine similarity}(\mathbf{A}, \mathbf{B}) = \frac{\mathbf{A} \cdot \mathbf{B}}{|\mathbf{A}| |\mathbf{B}|}
$$

• 应用：常用于文本挖掘和信息检索，特别是在处理词频（TF-IDF）向量时，用来判断文档或文章的相似性。

向量搜索的实现

了解一些基本理论，本章节主要讲如何实现向量搜索。什么是向量搜索，可以简单理解为“向量相似性搜索”，也就是匹配一些具有相似特征的非结构数据。

向量搜索的实现可以分为以下几步：

• 明确原始对象和目标对象（搜索对象），比如说文本、视频、图片，这些非结构数据；
• 向量嵌入Embedding：提取原始对象和目标对象的的关键特征，生成数据集，转化为数字，用向量表示；
• 计算原始向量和目标向量的相似性，比如用余弦相似度或欧几里得距离等方法
• 圈定最接近的向量集合（比如前k个），映射回原始非结构数据，确定和搜索对象最相似的原始对象

向量空间模型

这个小结对应向量搜索实现的前两个步骤。搭建向量空间模型意味着将实际数据（如文本、图片等）转化为向量空间。

可以细分成下面3个步骤：

1. 数据预处理: 对数据进行预处理。比如对于文本这类非结构数据，这一步骤可以进行文本的分词、去除停用词、词干提取等步骤。重点是提炼出最有用的信息元素。
2. 特征选择: 选择哪些特征纳入向量空间的维度。比如，文本的特征可能是单词、短语或者其他语言单位。
3. 向量表示: 一旦选择了特征，接下来的步骤是量化这个特征，最终转化为向量。

为了方便理解，我们以文本作为例子。假设我有10句话：

• “I like the new movie!”
• “I love the weather.”
• “The movie-like weather,”
• “I love the movie!”
• “The new movie is great.”
• “Watching a new film.”
• “She loves the weather.”
• “He likes the new movie!”
• “Movies, can be fun”
• “The weather is lovely.”

我要用上面3个步骤，将这10句话转化成向量。

1. 数据预处理: 可以把句子里的标点符号和冠词去掉，对于这些简单句子，标点符号和冠词其实不重要，所以经过预处理，我们得到新的10句话：

• “I like new movie”
• “I love weather”
• “movie like weather”
• “I love movie”
• “new movie is great”
• “Watching new film”
• “She loves weather”
• “He likes new movie”
• “Movies can be fun”
• “The weather is lovely”

1. 特征选择: 最简单地，我们可以将单词作为特征， 我们可以每个单词定义成向量的维度信息，在上面的10句话中，总共有18个不同的单词:

• I
• like
• new
• movie
• love
• weather
• is
• great
• watching
• film
• she
• loves
• he
• likes
• can
• be
• fun
• lovely
  所以我们定义18个特征，分别为是否有I，是否有like，是否有new，是否有movie，是否有love，是否有weather，是否有is，是否有great，是否有watching，是否有film，是否有she，是否有loves，是否有he，是否有likes，是否有can，是否有be，是否有fun，是否有lovely。未来的向量会有18个维度；

1. 向量表示:

1
2
3
4
5
6
7
8
9
10

(1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)  # "I like new movie"
(1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)  # "I love weather"
(0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)  # "movie like weather"
(1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)  # "I love movie"
(0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)  # "new movie is great"
(0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0)  # "Watching new film"
(0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0)  # "She loves weather"
(0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0)  # "He likes new movie"
(0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0)  # "Movies can be fun"
(0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1)  # "The weather is lovely"

声明：本文的方法非常简单，目的是为了让读者理解概念，目前已经有更成熟的方法将文本转化成更加精准的向量，比如说词袋模型、TF-IDF或Word2Vec。

计算相似性

有了向量后，下一步我们可以用第二章节介绍的方法计算向量之前的相似性了。比较相似性至少需要两个向量，所以我们可以定义两种向量：一个是包含原始数据集的向量，一个是要搜索的向量。

还是以上面的文本为例子，假如我要搜索的文本是“I really like the movie”，这句话的向量为E = (1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0) 我们将这个向量与上述四个向量分别计算“余弦相似度”，然后找出与其最相似的句子。相似度计算结果结果如下表格所示：

在这个表格中，我们可以看到“I like the new movie”与搜索句子“I really like the movie”的余弦相似度最高，为0.866，说明这两句话在语义上最为接近。其次是”I love movie“，余弦相似度为为0.707。

假如我们把“最接近”定义为余弦相似性最大的前两个句子，针对“I really like the movie”的搜索，最终会返回“I like the new movie”和”I love the movie“两个结果。

可视化

讲解到这里，我们已经实现了一个简单的向量搜索。本小节讲解如何讲上面这些矢量可视化，通过图形化的表达，可以让我们更容易理解矢量相似性。

上面11个矢量具有18个维度，很难用二维或者三维的空间坐标散点图来表示。所以我们需要降维，将18维度的信息打成二维或者三维。可以使用PCA(Primary Component Analysis 主成分分析)方法实现降维。主要步骤如下：

1. 降维处理:

   • 我们将18维的向量使用PCA方法降维到2维或3维，以便于在二维或三维空间中可视化。
   • PCA通过寻找数据中最主要的两个或三个方向，将高维数据压缩到较低维度，并尽可能保留原始数据的方差信息。

2. 可视化:

   • 如果我们选择降维到二维，可以使用散点图来可视化这些向量。
   • 如果我们选择降维到三维，可以使用三维散点图。

3. 标签与标注:

   • 在可视化中，可以标注每个点对应的句子，以帮助理解每个点在向量空间中的具体含义。
   • 搜索的句子”I really like the movie”可以使用不同颜色或形状来区分。

上述过程对应的python代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

import numpy as np
import matplotlib.pyplot as plt
from sklearn.decomposition import PCA

# 特征向量列表
vectors = np.array([
    [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],  # "I like new movie"
    [1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],  # "I love weather"
    [0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],  # "movie like weather"
    [1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],  # "I love movie"
    [0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],  # "new movie is great"
    [0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],  # "Watching new film"
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0],  # "She loves weather"
    [0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0],  # "He likes new movie"
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0],  # "Movies can be fun"
    [0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],  # "The weather is lovely"
    [1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],  # "I really like the movie" (搜索文本)
])

# 句子标签
labels = [
    "I like new movie",
    "I love weather",
    "movie like weather",
    "I love movie",
    "new movie is great",
    "Watching new film",
    "She loves weather",
    "He likes new movie",
    "Movies can be fun",
    "The weather is lovely",
    "I really like the movie"  # 目标文本
]

# 使用PCA将18维数据降维到2维
pca = PCA(n_components=2)
reduced_vectors = pca.fit_transform(vectors)

# 获取目标句子的位置 (红色点)
target_point = reduced_vectors[-1]

# 绘制二维散点图
plt.figure(figsize=(10, 8))
plt.scatter(reduced_vectors[:, 0], reduced_vectors[:, 1], c='blue', label="Other Sentences")

# 区别目标文本的标记
plt.scatter(target_point[0], target_point[1], c='red', label="Target Sentence (I really like the movie)")

# 添加标签
for i, label in enumerate(labels):
    plt.annotate(label, (reduced_vectors[i, 0] + 0.02, reduced_vectors[i, 1] + 0.02))

# 添加圆圈，半径可以根据需要调整
circle = plt.Circle(target_point, 0.5, color='red', fill=False, linestyle='--', linewidth=2)
plt.gca().add_patch(circle)

# 添加标题和图例
plt.title("2D PCA Visualization of Sentence Vectors with Target Circle")
plt.xlabel("PCA Component 1")
plt.ylabel("PCA Component 2")
plt.gca().set_aspect('equal', adjustable='box')
plt.legend()
plt.grid(True)
plt.show()

you can run this script on jupyter notebook。

在PCA降维后的二维可视化图的结果如下：

图中，每个点代表一个句子的向量，并且这些点的相对位置展示了它们在高维空间中的关系。如果两个点在图中靠得很近，这意味着它们在高维空间中的向量相似度较高。换句话说，这些句子在语义上可能比较接近。如果某个点距离其他点较远，这意味着它与其他句子的相似度较低，表示在向量空间中它们之间的差异较大。

另外，图中的横纵坐标轴可以无需过多关注，具体来讲涉及到PCA的底层原理，本文不重点讲述。

在这张图中，目标句子 “I really like the movie” 被用红色点标注。蓝色的点为原始数据。可以发现，离这个点最近的句子是“I really like the movie”，说明这两个句子的语言最接近。在红色点附近还标注了一条半径为0.5点红色线状圆圈，这是我们自己圈定的范围，意思是，命中这个圈内的句子，称得上是和目标语句语义接近的句子。

讲到这里，你已经进一步理解了前面介绍的向量搜索的实现的第4步：圈定最接近的向量集合，中“圈定”的含义。

搜索算法

在上面这张可视化的图形中，我们一眼就能看出哪个点离搜索向量最近，哪些点在圆圈里面。但是对于计算机来讲确不容易，在这方面，有一个命题是寻找一组数据中离某个目标点最近的k个点的算法，也就是所谓的k-Nearest-Neighbors （kNN） 算法。以下是几种常见的 k-NN 索引算法的实现方式：

暴力搜索 (Brute Force Search)

这是最简单的实现方式。对于每个查询点，计算该点与数据集中所有点的距离，然后排序找到最近的 k 个点。

• 优点: 实现简单，不需要复杂的数据结构。
• 缺点: 当数据集很大时，查询速度会很慢，因为每次查询都需要计算所有点的距离。

KD 树 (KD-Tree)

KD 树是一种适用于低维空间的树状数据结构，可以帮助加速 k-NN 查询。KD 树通过将数据分割成多维空间中的超平面，逐步构建出一棵树，使得每个查询只需要访问部分节点，从而加快查询速度。

• 优点: 对于低维数据集（通常少于20维），查询速度比暴力搜索快得多。
• 缺点: 随着数据维度的增加，KD 树的效率下降，可能会退化为暴力搜索。

实现步骤:

1. 构建KD树：递归地将数据按照不同维度进行分割，构建出一棵树。
2. 进行查询：在树中进行深度优先搜索，找到最近的 k 个点。

Ball Tree

Ball Tree 是另一种空间分割树结构，类似于 KD 树，但适用于高维数据。Ball Tree 的思想是将数据集划分成一系列的球形区域，并且在每次查询时只访问与查询点距离较近的区域。

• 优点: 比 KD 树更适合高维数据集。
• 缺点: 构建树的时间比 KD 树更长。

实现步骤:

1. 构建 Ball Tree：递归地将数据集分割成球形区域。
2. 进行查询：搜索与查询点相交的球形区域，找到最近的 k 个点。

使用库实现 k-NN 索引

不管你是否了解机器学习，KNN算法你肯定听过，讲到这里你已经大概知道的基本原理，但是本文并不侧重讲解实现具体的KD树和Ball树的具体原理，而是实践和理解之上，因此，为了最快体验到KNN算法的时候，我们可以使用一些开源库实现。还是以上面的文本案例，我们使用Scikit-learn计算与输入文本相近的前2个句子。

python代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

import numpy as np
import matplotlib.pyplot as plt
from sklearn.decomposition import PCA
from sklearn.neighbors import NearestNeighbors

# 特征向量列表
vectors = np.array([
    [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],  # "I like new movie"
    [1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],  # "I love weather"
    [0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],  # "movie like weather"
    [1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],  # "I love movie"
    [0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],  # "new movie is great"
    [0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],  # "Watching new film"
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0],  # "She loves weather"
    [0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0],  # "He likes new movie"
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0],  # "Movies can be fun"
    [0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],  # "The weather is lovely"
    [1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],  # "I really like the movie" (搜索文本)
])

# 句子标签
labels = [
    "I like new movie",
    "I love weather",
    "movie like weather",
    "I love movie",
    "new movie is great",
    "Watching new film",
    "She loves weather",
    "He likes new movie",
    "Movies can be fun",
    "The weather is lovely",
    "I really like the movie"  # 目标文本
]

# 使用PCA将18维数据降维到2维
pca = PCA(n_components=2)
reduced_vectors = pca.fit_transform(vectors)

# 获取目标句子的位置 (红色点)
target_point = reduced_vectors[-1]

# 使用 KD Tree 进行 k-NN 索引
knn = NearestNeighbors(n_neighbors=2, algorithm='kd_tree')
knn.fit(reduced_vectors[0:-1])

# 查询最近的 2 个邻居
distances, indices = knn.kneighbors([target_point])


print("最近邻的索引：", indices)
print("最近邻的标签：", [labels[i] for i in np.array(indices).flatten()])
print("距离：", distances)

代码运行的结果：

1
2
3

最近邻的索引： [[3 0]]
最近邻的标签： ['I love movie', 'I like new movie']
距离： [[0.30877828 0.5662625 ]]

可以看到结果和我们从可视化图形看到的结果、以及首次计算余弦相似度的结果相吻合。

总结

本文通过一个文本搜索的案例，介绍了向量搜索的基本原理，包括数据预处理、特征选择和相似性计算，同时展示了PCA降维后的可视化结果。进一步，我们探讨了多种搜索算法，如暴力搜索、KD树和Ball树，以及如何使用Scikit-learn实现K-NN搜索。我们最终发现，不管是使用余弦相似性、可视化，还是kNN算法，我们得到的结论都是互相吻合的。

参考资料

1. An exploration of vector search
2. 向量数据库的崛起：从矢量搜索到深度学习 (一)

License

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

Share