LSH算法
我们要计算最近邻数据，首先我们必须定义自己的评价函数，也就是相似度量函数。一般有，可以参考这篇文章https://www.cnblogs.com/belfuture/p/5871452.html
常规求解思路，是拿所有数据和要求近邻点的数据求度量距离，再从结果中取topN。如果数据量是，维度是
，我们的时间复杂度是：
。具体见如下代码。
int m=arr.length, n= arr[0].length;
int[][] res = new int[m][m];
//求上三角的元素
for (int i=0;i<m;i++){
//当前求最近邻的基点是arr[i]
int[] curCheck = arr[i];
for (int j=0;j<m;j++) {
//自己和自己的距离为0
if (j == i) {
res[i][i] = 0;
} else if (j < i) {
res[i][j] = res[j][i];
} else {
int[] waitCheck = arr[j];
for (int k = 0; k < n; k++) {
//求欧式距离
res[i][j] += (curCheck[k] - waitCheck[k]) * (curCheck[k] - waitCheck[k]);
}
}
}
}
到此为止，我们还只是算了两两间的距离，还需要排序求TOPN，时间复杂度是极其高的。尤其数据量很大时，很大，时间复杂度是无法忍受的。这也是问题优化的突破点，实际上很多运算是不必要的，试想如果已经有两个数差距悬殊摆在那，你还会去求这两个数的相似度吗？当然不会。
这时候就有人在想，我能不能找一种映射关系，把数据分成好几个桶，每个桶里的数据都很大概率相似？我们把这种映射关系称为hash映射，也叫做LSH（局部敏感哈希）。给出hash函数的定义：假设原始集合为，映射后的集合为
，
为
中任意两个对象，我们称一族hash函数
是敏感的，则对任意的
, 它要满足如下两个条件：
1.若，则
2.若，则
接下来给出两类hash函数及其对应的度量函数。这里有个点一定要注意，LSH是概率性的，也就是说存在一定的概率，原本很相似的两个对象经过hash后值不一样。
下面介绍两种hash方法：
1、使用Jaccard系数度量数据相似度时的min-hash
回顾一下Jaccard系数度量的公式，两个对象的Jaccard系数为：
简记为交集个数比并集个数。借用这篇文章https://blog.csdn.net/guoziqing506/article/details/53019049的一个例子来理解。假设我们对一篇文章已经做了分词，并且选取了7个词汇构成了我们的词典,四个文档
用最简单的one-hot编码表示为：
其实min-hash很简单，就是统计每个文档第一个不为0的值，对于上图中的min-hash后的结果为[1,2,1,2]。当我们把词典顺序做一次调整后，比如将第一个和第二个词的顺序换一下，变为：
这样min-hash后的结果为：[1,1,2,1]。注意此处有一个重要的结论，经过min-hash后两个对象相等的概率和这两个对象的Jaccard系数一样，即
这样经过r次置换后，对象
这样处理后，我们将原来的
SPARK代码实现如下：
LSH框架
假设我们有M个商品，每个商品用一个32维向量表示。
Step1：用一个随机高斯矩阵A（32*N，其中N>>M）乘以32维的向量，得到一个N维的向量
Step2：对上述的N维向量取符号函数，得到一个取值为0和1的向量
Step3：对上述向量排序，排序的规则是将向量中前面为1的排在前面
Step4：分桶，直接按顺序依次分桶，在桶内部求TOPN
参考文献
[1]LSH Algorithm and Implementation (E2LSH)
[2]Jeffrey D. Ullman Anand Rajaraman, Jure Leskovec. Mining of massive datasets
网友评论