01 总体流程简介
havenask中向量索引服务使用的是阿里自研的proxima，proxima相比于faiss无论在性能和召准率等方面均有很大优势。
在日益发展的深度学习背景下，各类结构化&非结构化数据均可通过数学上的各类空间(如度量空间)映射为多维度向量，向量之间的相似性可通过距离获余弦相似度等方式比较方便的衡量。
向量索引构建&检索的流程：词句转成向量->向量通过聚类算法进行构建索引->通过较优的检索算法进行检索。下面会从这三个步骤细化为词句转成向量、向量聚类算法、向量检索优化算法及aitheta源码解析四个部分进行阐述。
02 词句转向量(embedding)
Embedding的定义：离散实例连续化的映射。用一个低维稠密向量来表示一个对象，使得这个向量能够表达相应对象的某些特征，同时向量之间的距离能反应对象之间的相似性。
搜索推荐应用：User维度的数据 及 商品维度的数据
主流的Embedding技术：经典的矩阵分解方法(SVD)、基于内容的embedding方法及基于Graph的embedding 方法
基于内容的embedding 方法：静态向量embedding和动态向量embedding
静态向量含义：一旦训练完成后，对应的向量便不再发生改变，比如一个词经过向量化之后，在后续的场景中该词对应的向量不会发生改变
动态向量含义：在对词进行向量表示时，能结合当前语境对多义词进行理解，实现不同上下文，其向量会有所改变
静态向量embedding方法：word2vec、GloVe和FastText
动态向量embedding方法：ELMo、GPT和BERT
各类算法的发展图鉴：
目前，使用较多的是通过BERT算法进行的向量生成，所以下面只介绍word2vec(静态)和BERT(动态)
2.1 word2vec算法
该算法将句子转换成词+数量并倒排，然后根据倒排词典构建哈夫曼树，然后应用最大似然估算概率
2.1.1 预备知识
2.1.1.1 哈夫曼树
定义：当用 n 个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小，称这棵树为“最优二叉树”，有时也叫“赫夫曼树”或者“哈夫曼树”
构建过程：
- 在 n 个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树，且新二叉树的根结点的权值为左右孩子权值的和；
- 在原有的 n 个权值中删除那两个最小的权值，同时将新的权值加入到 n–2 个权值的行列中，以此类推；
- 重复 1 和 2 ，直到所以的结点构建成了一棵二叉树为止，这棵树就是哈夫曼树。
2.1.1.2 CBOW模型
2.1.1.3 SKIP模型
2.1.2 算法流程
1. 读取一个单词对应代码
2. 计算单词对应的hash值
3. 通过hash值得到word在词汇表中索引
4. 将word加入到词汇表
5. 对词汇表进行排序
6. 保存训练好的词汇表
7. 初始化网络参数
8. 构建哈夫曼树
9. 初始化负采样概率表
10. 模型训练(采用CBOW或SKIP)
11. 保存结果
2.2 BERT算法
BERT模型的全称是：BidirectionalEncoder Representations from Transformer
BERT算法的输入输出如下图：输入文本，输出向量
其中，
文本向量：该向量的取值在模型训练过程中自动学习，用于刻画文本的全局语义信息，并与单字/词的语义信息相融合
位置向量：由于出现在文本不同位置的字/词所携带的语义信息存在差异，因此，BERT模型对不同位置的字/词分别附加一个不同的向量以作区分
了解了BERT模型的输入/输出和预训练过程之后，我们来看一下BERT模型的内部结构。
前面提到过，BERT模型的全称是：BidirectionalEncoder Representations from Transformer，也就是说，Transformer是组成BERT的核心模块，而Attention机制又是Transformer中最关键的部分，因此，下面我们从Attention机制开始，介绍如何利用Attention机制构建Transformer模块，在此基础上，用多层Transformer组装BERT模型。
2.2.1 Attention机制
Attention机制的中文名叫“注意力机制”，顾名思义，它的主要作用是让神经网络把“注意力”放在一部分输入上，即：区分输入的不同部分对输出的影响。这里，我们从增强字/词的语义表示这一角度来理解一下Attention机制
Attention机制主要涉及到三个概念：Query、Key和Value。目标字及其上下文的字都有各自的原始Value，Attention机制将目标字作为Query、其上下文的各个字作为Key，并将Query与各个Key的相似性作为权重，把上下文各个字的Value融入目标字的原始Value中。如下图所示
2.2.2 Self-Attention
对于输入文本，我们需要对其中的每个字分别增强语义向量表示，因此，我们分别将每个字作为Query，加权融合文本中所有字的语义信息，得到各个字的增强语义向量，如下图所示。在这种情况下，Query、Key和Value的向量表示均来自于同一输入文本，因此，该Attention机制也叫Self-Attenti on。
2.2.3 Multi-head Self-Attention
为了增强Attention的多样性，文章作者进一步利用不同的Self-Attention模块获得文本中每个字在不同语义空间下的增强语义向量，并将每个字的多个增强语义向量进行线性组合，从而获得一个最终的与原始字向量长度相同的增强语义向量，如下图所示。
2.2.4 Transformer Encoder
在Multi-headSelf-Attention的基础上再添加一些“佐料”，就构成了大名鼎鼎的Transformer Encoder。实际上，Transformer模型还包含一个Decoder模块用于生成文本，但由于BERT模型中并未使用到Decoder模块，因此这里对其不作详述。下图展示了Transformer Encoder的内部结构，可以看到，Transformer Encoder在Multi-head Self-Attention之上又添加了三种关键操作：
● 残差连接（ResidualConnection）：将模块的输入与输出直接相加，作为最后的输出。这种操作背后的一个基本考虑是：修改输入比重构整个输出更容易（“锦上添花”比“雪中送炭”容易多了！）。这样一来，可以使网络更容易训练。
● Layer Normalization：对某一层神经网络节点作0均值1方差的标准化。
● 线性转换：对每个字的增强语义向量再做两次线性变换，以增强整个模型的表达能力。这里，变换后的向量与原向量保持长度相同。
2.2.5 BERT model
组装好TransformerEncoder之后，再把多个Transformer Encoder一层一层地堆叠起来，BERT模型就大功告成了
03 向量聚类算法
聚类分析简称聚类，是一个把数据对象(或观测)划分成子集的过程。每个子集都是一个簇(cluster)，使得簇中的对象彼此相似，但与其他簇中的对象不相似。由聚类分析产生的簇的集合称做一个聚类。
聚类分析已经广泛用于许多应用领域，包括商务智能、图像模式识别、WEB搜索、生物学和安全。在1688的搜索场景，目前尚未使用到聚类。猜想有个可尝试的地方是：反作弊异常检测、召回后做聚类去重&打散。
聚类算法简单的说，可以分为四类，包括基于划分的算法、基于层次的算法、基于密度的算法及基于网格的算法。下面会分别对这四类算法做简单的介绍。
3.1 基于划分的聚类算法
划分方法：给定一个n个对象的集合，划分方法构建数据的k个分区，其中每个分区表示一个簇，并且k<=n。也就是说它把数据划分为k个组，使得每个组至少包含一个对象。
一般特点：发现球形互斥的簇，基于距离，可以用均值或中心点代表簇中心，对中小规模数据集有效
典型算法：K-means，k-modes，k-medoids，CLARA，CLARANS
K-means算法描述：
选择K个点作为初始质心
repeat
将每个点指派到最近的质心，形成K个簇
重新计算每个簇的质心
until 簇不发生变化或达到最大迭代次数
k-modes是解决标称数据的聚类问题
k-medoids则是用具体的代表对象取代均值
CLARA（Clustering LARge Applications）基于抽象的方法来处理大大规模的数据聚类问题
CLARANS（Clustering Large Application based upon RANdomized Search）基于随机搜索的聚类大型应用的随机算法可以在使用样本得到聚类的开销和有效性之间权衡。
3.2 基于层次的聚类算法
层次方法：层次方法创建给定数据对象集的层次分解。根据层次分解如何形成，层次方法可以分为凝聚的或分裂的方法。
凝聚的方法，也称自底向上的方法，开始将每个对象作为单独的一个组，然后主次合并相近的对象或组，直到所有组合并为一个组，或者满足某个终止条件。
分裂的方法，也称自顶向下的方法，开始将所有的对象置于一个簇中，每次相继迭代中，一个簇被划分成更小的簇，直到最终每个对象在单独的一个簇中，或者满足某个终止条件。
一般特点：聚类是一个层次分解（即多层），不能纠正错误的合并或划分，可以集成其他技术，如微聚类或考虑对象连接
典型算法：AGNES，DIANA，BIRCH，Chameleon，概率层次聚类
3.2.1 AGNES算法
AGNES(Agglomerative Nesting) 是凝聚的层次聚类算法，如果簇C1中的一个对象和簇C2中的一个对象之间的距离是所有属于不同簇的对象间欧式距离中最小的，C1和C2可能被合并。这是一种单连接方法，其每个簇可以被簇中的所有对象代表，两个簇之间的相似度由这两个簇中距离最近的数据点对的相似度来确定。
算法描述：
输入：包含n个对象的数据库，终止条件簇的数目k
输出：k个簇
（1） 将每个对象当成一个初始簇
（2） Repeat
（3） 根据两个簇中最近的数据点找到最近的两个簇
（4） 合并两个簇，生成新的簇的集合
（5） Until达到定义的簇的数目
3.2.2 DIANA算法
DIANA（Divisive Analysis）算法属于分裂的层次聚类，首先将所有的对象初始化到一个簇中，然后根据一些原则（比如最邻近的最大欧式距离），将该簇分类。直到到达用户指定的簇数目或者两个簇之间的距离超过了某个阈值。
算法描述：
输入：包含n个对象的数据库，终止条件簇的数目k
输出：k个簇，达到终止条件规定簇数目
（1） 将所有对象整个当成一个初始簇
（2） For ( i=1;i!=k;i++) Do Begin
（3） 在所有簇中挑选出具有最大直径的簇；
（4） 找出所挑出簇里与其他点平均相异度最大的一个点放入splinter group，剩余的放入old party中。
（5） Repeat
（6） 在old party里找出到splinter group中点的最近距离不大于old party中点的最近距离的点，并将该点加入splinter group
（7） Until 没有新的old party的点被分配给splinter group；
（8） Splinter group 和old party为被选中的簇分裂成的两个簇，与其他簇一起组成新的簇集合
（9） END
BIRCH（Balanced Iterative Reducing and Clustering using Hierarchies）使用聚类特征树的多阶段聚类，克服了上述方法的可伸缩性及不能撤销先前步骤所做的工作的缺点
Chameleon（变色龙）使用动态建模的多阶段层次聚类，以k-最近邻图的方法来进行划分
概率层次聚类旨在通过使用概率模型度量簇之间的距离
3.3 基于密度的聚类算法
大部分划分方法基于对象间的距离进行聚类，这样的方法只能发现球状簇，而在发现任意形状的簇时遇到了困难。
基于密度的聚类算法的主要思想是：只要“领域”中的密度(对象或数据点的数目)超过某个阈值，就继续增长给定的簇。也就是说，对给定簇中的每个数据点，在给定半径的领域中必须至少包含最少数目的点。这样的方法可以用来过滤噪声或离群点，发现任意形状的簇。
一般特点：可以发现任意形状的簇，簇是对象空间中被低密度区域分隔的稠密区域，可能过滤离群点
典型算法：DBSCAN，OPTICS，DENCLUE
DBSCAN算法描述如下：
OPTICS（Ordering Points To Identify the Clustering Structure）则是在DBSCAN的基础上优化了Eps和MinPts的选择
DENCLUE（Density Clustering）则是在DBSCAN和OPTICS的基础上优化了Eps敏感的问题，引入了密度估计的概念，基于密度分布函数来聚类。
3.4 基于网格的聚类算法
基于网格的方法把对象空间量化为有限个单元，形成一个网格结构、所有的聚类操作都在这个网格结构（即量化的空间）上进行。这种方法的主要优点是处理速度快，其处理时间独立于数据点的个数，而仅依赖于量化空间中的每一维的单元数。
一般特点：使用一种多分辨率网格数据结构，快速处理
典型算法：STING，CLIQUE
STING(Statistical Information Grid-based method)是一种基于网格的多分辨率聚类技术，它将空间区域划分为矩形单元。针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层的单元。关于每个网格单元属性的统计信息（例如平均值、最大值和最小值）被预先计算和存储。这些统计信息用于回答查询。
STING有几个优点：
1. 由于存储在每个单元中的统计信息提供了单元中的数据不依赖于查询的汇总信息，所以基于网格的计算是独立于查询的；（ii）网格结构有利于并行处理和增量更新；
2. 该方法的主要优点是效率很高：STING扫描数据库一次来计算单元的统计信息，因此产生聚类的时间复杂度是O(n)，其中n是对象的数目。在层次结构建立后，查询处理时间是O(g)，这里g是最低层网格单元的数目，通常远远小于n。该算法的缺点：由于STING采用了一个多分辨率的方法进行聚类分析，STING聚类的质量取决于网格结构的最低层的粒度。如果粒度比较细，处理的代价会显著增加；但是，如果网格结构最低层的力度太粗，将会降低聚类分析的质量；而且，STING在构建一个父亲单元时没有考虑孩子单元和其相邻单元之间的关系，因此，结果簇的形状是isothetic，即所有的聚类边界或者是水平的，或者是竖直的，没有对角的边界。尽管该技术有快速的处理速度，但可能降低簇的质量和精确性。
CLIQUE(Clustering In QUEst)算法综合了基于密度和基于网格的聚类方法,它的中心思想是:首先，给定一个多维数据点的集合，数据点在数据空间中通常不是均衡分布的。CLIQUE区分空间中稀疏的和“拥挤的”区域（或单元），以发现数据集合的全局分布模式。接着，如果一个单元中的包含数据点超过了某个输入模型参数，则该单元是密集的。在CLIQUE中，簇定义为相连的密集单元的最大集合。
CLIQUE算法能自动发现最高维中所存在的密集聚类；它对输入数据元组顺序不敏感；也不需要假设（数据集中存在）任何特定的数据分布；它与输入数据大小呈线性关系；并当数据维数增加时具有较好的可扩展性。但是，在追求方法简单化的同时往往就会降低聚类的准确性。
04 向量检索优化算法
向量检索时，用到了优化算法BBF(Best Bin First)，而BBF算法和KD Tree联系紧密，所以一并阐述下
4.1 KD树的创建
KD树其实就是一种树形的数据结构，但是在创建这棵树时有一些固定的规则。下面来讲一下KD树的创建过程
输入：一组数据点集，n个数据点，每个点有m维
输出：KD树的根结点指针
过程：
1. 分别计算这n个数据点在m维中各个维度的方差，取方差最大的维度dim作为分割维度；
2. 把数据点集按照该维度中值的大小进行排列，选择具有中间值的点作为该树的根结点；
3. 前半部分点进行如1、2所示的递归操作，选出的递归子树的根节点作为（2）中得到的根节点的左孩子；同理，后半部分也这样操作。如此一直递归，直到各个递归子树的数据点集为空则算法截止。
4.2 KD树的查询
KD树建立好以后，需要查询它的最近邻，方法如下：
1. 查询点与k-d树的根节点进行比较，比较两者在根节点划分时的维度的值的大小，若查询点在该维的值小，则进入根节点的左子树，否则进入右子树。依次类推，进行查找，直到到达树的叶子节点。
2. 设当前到达的叶子节点为目前的最近邻（注意：可能并非真正的最近邻），并且记录目前的最近邻距离。沿着来时的路向前回溯，让目前的最近邻距离与查找点与当前叶子节点的父节点形成的分割超平面的距离进行比较，若当前最近邻比较小，则不用遍历当前叶子节点的父节点的另一边，否则需要遍历查找以更新最近邻距离和最近邻节点。
3. 按照2中所说依次遍历，直到到达根节点为止，查询结束。
4.3 BBF算法
根据前面KD树的搜索过程我们可以知道，在搜索时首先沿着KD树找到叶子节点，然后依次回溯，而回溯的路程就是前面我们查找叶子节点时逆序，因此进行回溯时并没有利用这些点的信息。我们接下来介绍的算法就是利用这些信息，回溯时给各个需要回溯的结点以优先级，这样找到最近邻会更快。接下来详细介绍BBF（Best Bin First）算法的流程。
其实BBF算法的思想比较简单，通过对回溯可能需要的路过的结点加入队列，并按照查找点到该结点确定的超平面的距离进行排序，然后每次首先遍历的是优先级最高（即距离最短的结点），直到队列为空算法结束。同时BBF算法也设立了一个时间限制，如果算法运行时间超过该限制，不管是不是为空，一律停止运行，返回当前的最近邻点作为结果。
BBF的算法流程如下：
输入：KD树，查找点x
输出：KD树种距离查找点最近的点以及最近的距离
流程：
1. 若KD树为空，则设定两者距离为无穷大，返回；如果KD树非空，则将KD树的根节点加入到优先级队列中；
2. 从优先级队列中出队当前优先级最大的结点，计算当前的该点到查找点的距离是否比最近邻距离小，如果是则更新最近邻点和最近邻距离。如果查找点在切分维坐标小于当前点的切分维坐标，则把他的右孩子加入到队列中，同时检索它的左孩子，否则就把他的左孩子加入到队列中，同时检索它的右孩子。这样一直重复检索，并加入队列，直到检索到叶子节点。然后在从优先级队列中出队优先级最大的结点；
3. 重复1和2中的操作，直到优先级队列为空，或者超出规定的时间，返回当前的最近邻结点和距离。
05 Aitheta解析
aitheta是基于proxima来开发的一套向量构建&检索服务，在havenask的配置中名称为aitheta_indexer，故先来简单了解下proxima
5.1 proxima
随着 AI 技术的广泛应用，以及数据规模的不断增长，对非结构化数据处理的需求也日益增多。向量检索也逐渐成了 AI 技术链路中不可或缺的一环，同时也是对传统搜索技术的补充。
Proxima 是阿里巴巴达摩院系统 AI 实验室自研的向量检索内核。目前，其核心能力广泛应用于阿里巴巴和蚂蚁集团内众多业务，如淘宝搜索和推荐、蚂蚁人脸支付、优酷视频搜索、阿里妈妈广告检索等。同时，Proxima 还深度集成在各式各类的大数据和数据库产品中，如阿里云 Hologres、搜索引擎 Elastic Search 和 ZSearch、离线引擎 MaxCompute (ODPS) 等，为其提供向量检索的能力。
Proxima BE，全称 Proxima Bilin Engine，是 Proxima 团队开发的服务化引擎，实现了对大数据的高性能相似性搜索。支持 RESTful HTTP 接口访问，同时也支持多种语言的 SDK 以 GRPC 协议访问。
5.2 aitheta
aitheta代码包括了 向量索引构建 和 向量索引检索 两部分，简化版的流程图如下所示，其中indexer、indexReducer、indexRetriever、indexSegmentRetriever、segmentReader、indexModuleFactory等均来自于indexlib，也说明了aitheta是在indexlib的基础上通过插件化的方式支持了向量索引
5.3 索引构建&检索
向量索引的配置示例如下：
{
"index_name" : "aitheta_recall_index",
"index_type" : "CUSTOMIZED",
"index_fields":
[
{"field_name" : "DUP_nid", "boost" : 1},
{"field_name" : "DUP_category", "boost" : 1},
{"field_name" : "DUP_recall_fullcate_item_recall_emb_excellent_c2c", "boost" : 1}
],
"indexer" : "aitheta_indexer",
"parameters" : {
"dimension": "128",
"index_type": "hc",
"build_metric_type": "l2",
"search_metric_type": "l2",
"proxima.hc.builder.num_in_level_1": "100",
"proxima.hc.builder.num_in_level_2": "100",
"proxima.hc.common.leaf_centroid_num": "10000",
"proxima.hc.searcher.scan_num_in_level_1": "40",
"proxima.hc.searcher.scan_num_in_level_2": "1000",
"proxima.hc.searcher.max_scan_num": "35000",
"proxima.hc.common.basic_block_size": "8",
"use_linear_threshold":"10000",
"embedding_separator": "",
"use_dynamic_params": "1"
}
}aitheta的核心代码
初始化->创建Builder->模型训练->索引构建->dump到磁盘
参考文献
[1]用万字长文聊一聊 Embedding 技术
https://blog.csdn.net/Tencent_TEG/article/details/109792115
[2]word2vec 中的数学原理详解
https://www.cnblogs.com/peghoty/p/3857839.html
[3]word2vec源码详解
https://blog.csdn.net/jeryjeryjery/article/details/80245924
[4]图解BERT模型：从零开始构建BERT
https://cloud.tencent.com/developer/article/1389555
[5]pytorch_transformers使用之获取bert词向量
https://blog.csdn.net/qq_38880498/article/details/99867033
[6]k-d树+bbf算法的介绍与实现
https://blog.csdn.net/lhanchao/article/details/52535694
[7]哈夫曼树（赫夫曼树、最优树）详解
http://c.biancheng.net/view/3398.html
[8]聚类算法
https://blog.csdn.net/chen_shiqiang/article/details/52121864
[9]《数据挖掘概念与技术》
[10]havanask代码：git@github.com:alibaba/havenask.git
[11]proxima代码：git@github.com:alibaba/proxima.git