微软BING搜索-SPTAG算法的原理，你搞清了嘛？ - 黑马程序员技术交流社区

近日，微软在GitHub上开源了其BING的搜索算法SPTAG，github地址：https://github.com/microsoft/SPTAG。这个算法笔者简单看了一下，的确是很有价值可以看大家介绍下，这种称为SPTAG （Space Partition Tree And Graph）目前的翻译多称为“空间分区式的树和图”，其实个人认为这种说法不太准确，其实这里的图与图论中的图意思一致，表示的是连接关系，并不是图像的意思，，而且我们一会仔细也会发现其算法中还带有平衡（balance)的概念，感觉译为”高维空间平衡树“更为准确。

微软在github上的介绍中给出的官方解释如下“This library assumes that the samples are represented as vectors and that the vectors can be compared by L2 distances or cosine distances. Vectors returned for a query vector are the vectors that have smallest L2 distance or cosine distances with the query vector. "

简单解释一下，就是微软认为图像、声音文字都能被表示为向量，而且可以用L2距离及余弦距离（cosine distances）表示其关系。这段我给读者解释一下，什么叫可以用余弦距离表示向量之间的关系。

也就是说在图片转化为向量后，向量的位置关系保留了其图片含义所代表的逻辑关系。这就是”L2距离及余弦距离（cosine distances）表示其关系“的具体解释。

不过这次微软并没有公开把图片、声音及文字转化为向量的技术，目前文字转化为向量的主要技术是word2vec算法，图片转化为文字的技术，读者也可以通过Facebook前些时候公开的Pytorch-Biggraph算法来了解，那么说到现在我们可以了解SPTAG算法工作的前提就是将已经将用户搜索的要素转化为了正确位置上的向量，SPTAG就是要找到这个向量在空间上的最近邻，说到这读者是否对SPTAG的工作方式有了更进一步的认识了呢。

对于搜索算法有了解的同学可能都会了解，搜索算法中一般有索引（index)和查寻(search)两个重要部分组成。SPTAG的索引（index)算法是基于kd-tree的。

kd-tree听起来很高大上，其实他在于一维空间上的情况就是”平衡二叉树“，在高维空间上kd-tree会用第k维的大小来决定一个元素应该插入左子树还是右子树，同时为保持tree的平衡，剩余未进入tree的元素除第k维外方差最小。SPTAG正是以此来加速算法的速度。

kmeans其实就是一种自动聚类的方法，算法先随机指定选取K个点做为初始聚集的簇心,分别计算每个样本点到 K个簇核心的余弦距离，找到距离最近的核心点，将它归属到对应的簇，所有点都归属到簇之后， M个点就分为了 K个簇。之后重新计算每个簇的重心，将其定为新的“核心”，重复上述步骤直到新核心不再改变为止或者改变距离达到一定值后中止。那么最终的K个簇就是最终的聚类结果。

SPTAG 正是集合了kd-tree 和 kmeans 两种算法的精华，才允许用户利用深度学习模型在几毫秒内搜索数十亿条信息。