最近邻和K近邻及其优化算法LSH（局部敏感哈希，Locality Sensitive Hashing） Kd-Tree

爱被打了一巴掌 2021-09-15 15:36 334阅读 0赞

## 引言 ##

在处理大量高维数据时，如何快速地找到最相似的数据是一个比较难的问题。如果是低维的小量数据，线性查找（Linear Search）就可以解决，但面对海量的高维数据集如果采用线性查找将会非常耗时。因此，为了解决该问题通常采用些优化算法。称之为近似最近邻查找（Approximate Nearest Neighbor），例如kd-tree with best bin first,locality sensitive hashing。最近邻算法思想很简单：以整个训练样本作为代表点，计算未知样本与所有训练样本的距离，并以最近邻的类别作为决策未知样本类别的唯一依据。但显然以一个训练样本作为判断标准，很容易受到噪声点的影响。因此引出K近邻，对与测试样本最近的k（k一般奇数）个训练样本类别进行投票判断测试样本类别。

## 常用相似性度量 ##

皮尔森相关度  
原理：用来反映两个变量线性相关程度的统计量  
范围：\[-1,1\]，绝对值越大，说明相关性越强，负相关对于推荐的意义小。  
说明：1、 不考虑重叠的数量；2、 如果只有一项重叠，无法计算相似性（计算过程被除数有n-1）；3、 如果重叠的值都相等，也无法计算相似性（标准差为0，做除数）。

欧式距离相似度  
原理：利用欧式距离d定义的相似度s，s=1 / (1+d)。  
范围：\[0,1\]，值越大，说明d越小，也就是距离越近，则相似度越大。  
说明：同皮尔森相似度一样，该相似度也没有考虑重叠数对结果的影响，同样地，Mahout通过增加一个枚举类型（Weighting）的参数来使得重叠数也成为计算相似度的影响因子。

余弦相似度  
原理：多维空间两点与所设定的点形成夹角的余弦值。  
范围：\[-1,1\]，值越大，说明夹角越大，两点相距就越远，相似度就越小。  
说明：在数学表达中，如果对两个项的属性进行了数据中心化，计算出来的余弦相似度和皮尔森相似度是一样的，在mahout中，实现了数据中心化的过程，所以皮尔森相似度值也是数据中心化后的余弦相似度。另外在新版本中，Mahout提供了UncenteredCosineSimilarity类作为计算非中心化数据的余弦相似度。

Spearman秩相关系数  
原理：Spearman秩相关系数通常被认为是排列后的变量之间的Pearson线性相关系数。  
范围：\{-1.0,1.0\}，当一致时为1.0，不一致时为-1.0。  
说明：计算非常慢，有大量排序。针对推荐系统中的数据集来讲，用Spearman秩相关系数作为相似度量是不合适的。

曼哈顿距离  
原理：曼哈顿距离的实现，同欧式距离相似，都是用于多维数据空间距离的测度  
范围：\[0,1\]，同欧式距离一致，值越小，说明距离值越大，相似度越大。  
说明：比欧式距离计算量少，性能相对高。

Tanimoto系数  
原理：又名广义Jaccard系数，是对Jaccard系数的扩展，等式为  
范围：\[0,1\]，完全重叠时为1，无重叠项时为0，越接近1说明越相似。  
说明：处理无打分的偏好数据。

对数似然相似度  
原理：重叠的个数，不重叠的个数，都没有的个数  
范围：具体可去百度文库中查找论文《Accurate Methods for the Statistics of Surprise and Coincidence》  
说明：处理无打分的偏好数据，比Tanimoto系数的计算方法更为智能。

## LSH局部敏感哈希 ##

算法流程如下：  
![这里写图片描述][70]  
[详细可了解][Link 1]  
LSH存在的问题是：如果数据稀疏（spread out）那么表现很好，但如果数据稠密（clumpy data），就会导致许多数据点在同一个bucket里面，而有些bucket里面数据较少。

## Kd-Tree ##

[详细可了解][Link 2]  
对于Kd-tree标准算法不好用于高维数据，因为需要太多backtracking。但是我们修剪至一定数量叶子，并且使用best bin first heuristic，那么该算法就较好适用于稠密数据（clumpy data）。

[70]: /images/20210520/dcc6a1dd89464b4e864f48f4ee7625ed.png
[Link 1]: https://blog.csdn.net/guoziqing506/article/details/53019049/
[Link 2]: https://blog.csdn.net/qing101hua/article/details/53228668