介绍下K近邻

K 近邻算法（KNN）是一种基本分类与回归方法，其思想非常简单 —— KNN 对新样本进行预测的方法是：根据其k个最近邻的训练实例类别，通过多数表决等方式进行预测。从 KNN 算法的基本思想可以看出，KNN 算法本身不具有显示的学习过程，仅仅是将训练数据中与待预测样本最邻近 k 个点的占多数的类作为待预测样本的类。

由此可得出 KNN 三要素：

• k 值的选择
• 距离度量
• 决策规则

1. 距离度量方法

为了找到最近邻的k个训练实例，我们需要对这一条件进行度量。特征空间中两个实例点的距离是两个实例点相似程度的反应。

K近邻模型的特征空间一般是 $n$ 维实数向量空间 $R^n$，使用的距离是欧氏距离，但也可以是其他距离。

机器学习中常见的距离度量方式有：

1.1 欧氏距离定义

欧几里得距离是我们最为熟悉也最容易理解的一种距离度量方式。在欧几里得空间中，点 [公式] 和 [公式] 之间的欧氏距离为：

它是一个纯数值，体现数值上的绝对差异。

1.2 余弦距离定义

首先引入余弦相似性的定义：

两个向量间的余弦值可以通过使用欧几里得点积公式求出：
$$a\cdot b=||a||||b||cos\theta$$

给定两个属性向量 A 和 B，其余弦相似性由点积和向量长度给出：

可以看出余弦相似性的取值范围是：$[-1,1]$。即余弦相似性可能取到负值，但距离通常不可能取负数，所以余弦距离定义为：

余弦距离的取值范围是：$[0,2]$，非负。

注意，余弦距离并不是一个严格定义的距离，虽然满足正定性和对称性但不满足三角不等式，相关示例解释参考Hulu机器学习问题与解答系列 | 第五弹：余弦距离。

1.3 余弦距离与欧氏距离

从上图可以看出，欧氏距离衡量的是空间各点的绝对距离，跟各个点所在的位置坐标直接相关；而余弦距离衡量的是空间向量的夹角，更加体现在方向上的差异。

1.4 曼哈顿距离

我们可以定义曼哈顿距离的正式意义为L1-距离或城市区块距离，也就是在欧几里得空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。

例如在平面上，坐标 $(x_1,x_2)$ 的点 $P_1$ 与坐标 $(x_2,y_2)$ 的点 $P_2$ 的曼哈顿距离为：

1.5 曼哈顿与欧几里得距离

下图中红、蓝与黄线分别表示所有曼哈顿距离都拥有一样长度（12），而绿线表示欧几里得距离有 $6\times \sqrt{2}\approx 8.48$ 的长度：

2. K 值的选择

k 值的选择会对 KNN 算法的结果产生重大影响：

• 选择太小的 k 值，近似误差会减小，只有与输入实例较近的训练实例才会预测结果起作用，缺点是估计误差会增大。意味着整体模型变得复杂，容易发生过拟合现象。
• 选择较大的 k 值，可以减少估计误差，但是近似误差会增大，这是与输入实例较远的训练实例也会对预测起作用，使预测发生错误。意味着模型变得简单，容易发生欠拟合现象。
• 在实际应用中，通常采用交叉验证法来选取最优 k 值(较小)。

3. 分类决策规则

k 近邻算法中的分类决策规则一般是多数表决：由输入实例的k个邻近的训练实例中的多数类决定输入实例的类。

多数表决规则等价于经验风险最小化，具体解释可参考机器学习算法 | K近邻算法 (KNN) 与近邻搜索算法 K-D 树 (K-D Tree)。

优缺点总结

优点

• 算法简单，理论成熟，易于实现；
• 既可以用来做分类（可用于线性和非线性分类）也可以用来做回归；
• 对数据没有假设，准确度高，对 outlier 不敏感；
• KNN 是一种在线技术，新数据可以直接加入数据集而不必进行重新训练，没有明显的训练过程，所以训练时间复杂度为 $O(n)$；（在程序开始运行时，把数据集加载到内存后，不需要进行训练，直接进行预测）
• 由于 KNN 方法主要靠周围有限的邻近的样本，对于类域的交叉或重叠较多的待分类样本集来说，KNN 方法较其他方法更为适合；

缺点

• 当训练集较大时，计算量相当大，时间复杂度高（需要算每个测试点与训练集的距离，特别是特征数量比较大的时候）；
• 需要大量的内存，空间复杂度高；
• 样本不平衡（即有些类别的样本数量很多，而其它样本的数量很少）时，预测偏差较大，对稀有类别的预测准确度低；
• 是lazy learning方法，基本上不学习，导致预测速度较慢。

KNN 算法应用领域比较广泛，在文本分类、模式识别、聚类分析，多分类领域中处处有 KNN 算法的身影。

参考文章

• 机器学习算法 | K近邻算法 (KNN) 与近邻搜索算法 K-D 树 (K-D Tree)
• Hulu机器学习问题与解答系列 | 第五弹：余弦距离

介绍下KD-Tree

1. KD-Tree简介

kd树（k-dimensional树的简称），是一种分割k维数据空间的数据结构，主要应用于多维空间关键数据的近邻查找(Nearest Neighbor)和近似最近邻查找(Approximate Nearest Neighbor)。

其实KDTree就是二叉查找树（Binary Search Tree，BST）的变种。二叉查找树的性质如下：
1）若它的左子树不为空，则左子树上所有结点的值均小于它的根结点的值；
2）若它的右子树不为空，则右子树上所有结点的值均大于它的根结点的值；
3）它的左、右子树也分别为二叉排序树；

如果我们要处理的对象集合是一个K维空间中的数据集，我们首先需要确定是： 怎样将一个K维数据划分到左子树或右子树？

和构造1维BST树类似，只不过对于Kd树，在当前节点的比较并不是通过对K维数据进行整体的比较，而是选择某一个维度d，然后比较两个K维数据在该维度 d上的大小关系，即每次选择一个维度d来对K维数据进行划分，相当于用一个垂直于该维度d的超平面将K维数据空间一分为二，平面一边的所有K维数据 在d维度上的值小于平面另一边的所有K维数据对应维度上的值。也就是说，我们每选择一个维度进行如上的划分，就会将K维数据空间划分为两个部分，如果我 们继续分别对这两个子K维空间进行如上的划分，又会得到新的子空间，对新的子空间又继续划分，重复以上过程直到每个子空间都不能再划分为止。

以上就是构造 Kd-Tree的过程，上述过程中涉及到两个重要的问题：1）每次对子空间的划分时，怎样确定在哪个维度上进行划分；2）在某个维度上进行划分时，怎样确保建立的树尽量地平衡。树越平衡代表着分割得越平均，搜索的时间也就越少。

1.1 在哪个维度上进行划分？

一种选取轴点的策略是median of the most spread dimension pivoting strategy，统计样本在每个维度上的数据方差，挑选出对应方差最大值的那个维度。数据方差大说明沿该坐标轴方向上数据点分散的比较开（后面会发现，选择方差大的维度主要是为了减少回溯时的代价，减少子树的访问）。这个方向上，进行数据分割可以获得最好的平衡。

1.2 怎样确保建立的树尽量地平衡？

给定一个数组，怎样才能得到两个子数组，这两个数组包含的元素 个数差不多且其中一个子数组中的元素值都小于另一个子数组呢？方法很简单，找到数组中的中值（即中位数，median），然后将数组中所有元素与中值进行 比较，就可以得到上述两个子数组。同样，在维度d上进行划分时，划分点（pivot）就选择该维度d上所有数据的中值，这样得到的两个子集合数据个数就基本相同了。

2. KD-Tree构建

1）在K维数据集合中选择具有最大方差的维度k，然后在该维度上选择中值m为pivot对该数据集合进行划分，得到两个子集合；同时创建一个树结点node，用于存储；
2）对两个子集合重复步骤1的过程，直至所有子集合都不能再划分为止；
可以看出，KD-Tree的构建是一个递归的过程。

KD-Tree构建示例图：

具体解释可参考机器学习算法 | K近邻算法 (KNN) 与近邻搜索算法 K-D 树 (K-D Tree)，通俗易懂。

3. KD-Tree的最近邻查找

1）将查询数据Q从根结点开始，按照Q与各个结点的比较结果向下访问Kd-Tree，直至达到叶子结点。

• 其中Q与结点的比较指的是将Q对应于结点中的k维度上的值与中值m进行比较，若Q(k) < m，则访问左子树，否则访问右子树。达到叶子结点时，计算Q与叶子结点上保存的数据之间的距离，记录下最小距离对应的数据点，记为当前最近邻点nearest和最小距离dis。

2）进行回溯操作，该操作是为了找到离Q更近的“最近邻点”。即判断未被访问过的分支里是否还有离Q更近的点，它们之间的距离小于dis。

• 如果Q与其父结点下的未被访问过的分支之间的距离小于dis，则认为该分支中存在离P更近的数据，进入该结点，进行（1）步骤一样的查找过程，如果找到更近的数据点，则更新为当前的最近邻点nearest，并更新dis。
• 如果Q与其父结点下的未被访问过的分支之间的距离大于dis，则说明该分支内不存在与Q更近的点。
• 回溯的判断过程是从下往上进行的，直到回溯到根结点时已经不存在与P更近的分支为止。

注：判断未被访问过的树分支中是否还有离Q更近的点，就是判断"Q与未被访问的树分支的距离|Q(k) - m|“是否小于"Q到当前的最近邻点nearest的距离dis”。从几何空间上来看，就是判断以Q为中心，以dis为半径超球面是否与未被访问的树分支代表的超矩形相交。

总结

因为 k-d 树是二叉搜索树的变种，所以在 k-d 树上进行搜索与在二叉搜索树上搜索的过程是一致的，故 k-d 树上搜索的平均时间也是： $O(logn)$ 。

Kd树在维度较小时（比如20、30），算法的查找效率很高，然而当数据维度增大（例如：K≥100），查找效率会随着维度的增加而迅速下降。假设数据集的维数为D，一般来说要求数据的规模N满足N>>2的D次方，才能达到高效的搜索。

另外，推荐阅读knn基础与优化1–kd-tree这篇文章的相关介绍，表达更加简洁。

参考文章

• KD-Tree算法
• 详解KDTree
• k-d tree算法
• KNN的核心算法kd-tree和ball-tree
• knn基础与优化1–kd-tree
• k-d tree算法原理及实现
• kNN里面的两种优化的数据结构：kd-tree和ball-tree，在算法实现原理上有什么区别？
• 相似度性能比较-kd-tree、kd-ball、faiss、annoy、线性搜索
• 机器学习算法 | K近邻算法 (KNN) 与近邻搜索算法 K-D 树 (K-D Tree)

介绍下Ball Tree

Ball Tree Algorithm (球树算法），用超平面Circle(2D)或Sphere(3D)将所有的数据点分解到两个簇（cluster)，这个平面经常被称为超平面（hypersphere)，而每个簇表示树的两个节点。.

Ball tree algorithm* 的实现过程：

• 1）找到整个数据的中心centroid1。
• 2）找到离centroid1 最远的点centroid2
• 3）找到离centroid2最远的点centroid3
• 4）对每个点，按离centroid2, centroid3距离远近，分为两组（簇）
• 重复以上1234步骤， 直至到达树的预定层级（最多个簇）
  

空间点的分簇过程和树的长成过程，如图所示。

另外，推荐阅读文章Ball Tree对Ball Tree的介绍，以及文章knn基础与优化2–ball tree、LSH对Ball Tree的总结。

参考文章

• kNN里面的两种优化的数据结构：kd-tree和ball-tree，在算法实现原理上有什么区别？
• Ball Tree
• knn基础与优化2–ball tree、LSH

Brute Force、KD Tree和Ball Tree比较

• Brute Force（暴力算法）， 两两比较，得到所有点最均衡的结果。小数据集可行，大数据集不可行。
• 低维数据，KD Tree是最好的算法，但按轴分解，不适用复杂曲线，可能导致性能不好（poor performance).
• 高维数据，Ball Tree合适高维和大数据集情况，不过如果噪声数据过多，也会导致性能不好。

参考文章

• kNN里面的两种优化的数据结构：kd-tree和ball-tree，在算法实现原理上有什么区别？

介绍下Faiss

1. 背景介绍

推荐系统中，在使用Embedding进行召回的时候，由于直接进行for循环计算的时间复杂度巨高，因此需要采用一些技术进行快速计算，其中主要有两种解决方案。解决方案如下:

Faiss向量检索库
局部敏感哈希技术(可以参考书籍 深度学习与推荐系统 王喆)
其中Faiss是一个搜索工具库，Faiss中也有包含LSH(局部敏感哈希)技术进行搜索。

2. Faiss技术介绍

Faiss是FaceBook的AI团队开源的一套用于做稠密向量聚类和相似性搜索的软件库，它包含在任意大小向量上的搜索算法，也支持评估和参数调节。一些非常有用的算法也可以在GPU上使用,支持c++和python调用。

Faiss工具包可以使用在推荐系统的向量召回部分，在做向量召回的时候要么是u2u,u2i或者i2i，这里的u和i分别指user和item。我们知道在实际场景中user和item数量是海量的，我们最容易想到的基于向量相似度的召回就是使用两层循环遍历user列表或者item列表计算两个向量的相似度，但是这样做在面对海量数据是不切实际的，faiss就是用来加速计算某个查询向量最相似的Topk个索引向量。

Faiss所有软件库中对应的搜索技术都有与之对应的索引建立方法，其中PQ(乘积量化)就是其中的一个方法，该方法可以加快搜索并且减少空间。

3. Faiss原理介绍

Faiss包含多种相似度检索方法，它认为向量可以表达距离，可以通过整数来确定距离。向量距离可以通过L2(欧氏距离)和点积确定，同时也支持余弦相似度。它主要是通过向量压缩进行计算，而不是通过使用原型向量进行比较，这种方法虽然降低精度，但是可以极大缩小存储空间以及检索速度，可以达到近似检索。

Faiss本质是：使用PCA、K-means、PQ等算法对数据进行操作，对数据进行分群，每一个群都有一个Index，根据要查找数据的与每个Index距离大小，定位要查找的那个群，也就是缩小了数据查找范围，进而加速。

参考文章

• Faiss在推荐系统中的应用
• 搜索召回 | Facebook: 亿级向量相似度检索库Faiss原理+应用
• faiss-on-mr：推荐系统大规模离线向量检索工具
• 一文入门Facebook开源向量检索框架Faiss
• Faiss入门及应用经验记录
• 一文搞懂faiss计算

介绍下LSH（局部敏感哈希）

• 原理：哈希对大家再熟悉不过，向量也可以采用哈希来加速查找，我们这里说的哈希指的是局部敏感哈希（Locality Sensitive Hashing，LSH），不同于传统哈希尽量不产生碰撞，局部敏感哈希依赖碰撞来查找近邻。高维空间的两点若距离很近，那么设计一种哈希函数对这两点进行哈希值计算，使得他们哈希值有很大的概率是一样的；若两点之间的距离较远，他们哈希值相同的概率会很小。不同距离度量的哈希函数不同，不是所有距离度量（如内积）都能找到对应局部敏感哈希。摘自文章一文纵览KNN（ANN）向量检索。
• 优点：训练非常快，支持分批导入，index占内存很小，检索也比较快
• 缺点：召回率非常拉垮。在候选语料比较多的时候（百万级别），检索也不是特别快，大概是秒级别的。
• 使用情况：候选向量库非常大，离线检索，内存资源比较稀缺的情况
• 构建方法：

dim, measure = 64, faiss.METRIC_L2  
param =  'LSH'
index = faiss.index_factory(dim, param, measure) 
print(index.is_trained)  # 此时输出为True
index.add(xb)       

参考文章

• Faiss在推荐系统中的应用
• 一文纵览KNN（ANN）向量检索