海量数据最近邻数据查找

2020-11-23 本文已影响0人一个菜鸟的自我修养

LSH算法

我们要计算最近邻数据，首先我们必须定义自己的评价函数，也就是相似度量函数。一般有 $\cos,pearson, jaccard$ ，可以参考这篇文章https://www.cnblogs.com/belfuture/p/5871452.html
常规求解思路，是拿所有数据和要求近邻点的数据求度量距离，再从结果中取topN。如果数据量是 $m$ ，维度是 $n$ ，我们的时间复杂度是： $O(m^2\times n)$ 。具体见如下代码。

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，时间复杂度是极其高的。尤其数据量很大时， $m$ 很大，时间复杂度是无法忍受的。这也是问题优化的突破点，实际上很多运算是不必要的，试想如果已经有两个数差距悬殊摆在那，你还会去求这两个数的相似度吗？当然不会。
这时候就有人在想，我能不能找一种映射关系，把数据分成好几个桶，每个桶里的数据都很大概率相似？我们把这种映射关系称为hash映射，也叫做LSH（局部敏感哈希）。给出hash函数的定义：假设原始集合为 $S$ ，映射后的集合为 $U$ ， $O_1, O_2$ 为 $S$ 中任意两个对象，我们称一族hash函数
$H={h:S \Rightarrow U}$
是 $(r_1,r_2,p_1,p_2)$ 敏感的，则对任意的 $h$ , 它要满足如下两个条件：
1.若 $d(O_1,O_2)<r_1$ ，则 $p(h(O_1)=h(O_2))>=p_1$
2.若 $d(O_1,O_2)>r_2$ ，则 $p(h(O_1)=h(O_2))<=p_2$
接下来给出两类hash函数及其对应的度量函数。这里有个点一定要注意，LSH是概率性的，也就是说存在一定的概率，原本很相似的两个对象经过hash后值不一样。
下面介绍两种hash方法：

1、使用Jaccard系数度量数据相似度时的min-hash

回顾一下Jaccard系数度量的公式，两个对象 $O_1,O_2$ 的Jaccard系数为：
$Jaccard(O_1,O_2)=\frac{|O_1 \bigcap O_2|}{|O_1 \bigcup O_2|}$
简记为交集个数比并集个数。借用这篇文章https://blog.csdn.net/guoziqing506/article/details/53019049的一个例子来理解。假设我们对一篇文章已经做了分词，并且选取了7个词汇构成了我们的词典 $\{w_1,w_2,…,w_7\}$ ,四个文档 $\{ D_i \}_{i=1}^4$ 用最简单的one-hot编码表示为：

其实min-hash很简单，就是统计每个文档第一个不为0的值，对于上图中的min-hash后的结果为[1,2,1,2]。当我们把词典顺序做一次调整后，比如将第一个和第二个词的顺序换一下，变为：

这样min-hash后的结果为：[1,1,2,1]。注意此处有一个重要的结论，经过min-hash后两个对象相等的概率和这两个对象的Jaccard系数一样，即

p(minHash(O_1)=minHash(O_2))=Jaccard(O_1,O_2)

，此处不做详细证明，直观地可以这样理解，经过一次置换后，第一个不为0的元素相等的可能有

|O_1 \bigcap O_2|

种可能，最简单的将相等的那行移到第一个位置，而总共置换的情形有

|O_1 \bigcup O_2|

种。
这样经过r次置换后，对象

O_1,O_2

的签名或者称min-hash后的结果为：

H(O_1)=\{hash_i(O_1)\}_{i=1}^r

H(O_2)=\{hash_i(O_2)\} _{i=1}^r

这样处理后，我们将原来的

n

维降低到了

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

海量数据最近邻数据查找

LSH算法

1、使用Jaccard系数度量数据相似度时的min-hash

猜你喜欢

热点阅读