CDN笔记一 Locality Sensitive Hashing算法
本篇笔记基于文章Similarity search in high dimensions via hashing。
历史
locality-sensetive hashing 局部敏感哈希,简称为LSH,最早由Indyk于1998年提出,1999年被用于解决高维度海量数据的近似查找。
近邻查找
先来看看什么是k-NN和-NN问题。
k-NN问题指对于一个点集P和一个特定点q,寻找点集P中距点q最近的k个点。
-NN问题指对于一个点集P和一个特定点q,假定点集P距离点q最近的点为p,寻找点集P中所有与点q距离在d(p,q)到的点。
LSH算法
我们知道哈希算法目标是减少冲突方便快速查找。当维度很高,数据量很大的情况下,对于kNN问题,尽管一一匹配查找是线性的时间复杂度,计算成本也相当高。后续有人提出了KD tree,SR tree等等基于树形结构的搜索方案,但只能适用于低维度数据。
LSH算法可以快速有效地近似查找高维度海量数据。原理很简单,如果两个数据在高维空间中距离相近,则他们的哈希值有很大概率是一样的,反之如果两个数据在高维空间中距离较远,则他们的哈希值一样的概率非常小。
LSH哈希函数的定义如下:
B(q,r) 表示以q为圆心,半径为r的空间,且,。
哈曼顿距离下的LSH哈希函数
一般我们用欧式距离作为距离,也即l2 norm。这篇文章中用哈曼顿距离,l1 norm。作者解释实验两者kNN的结果差不多(据说其实是当时欧式距离下的哈希函数还不知道)。作者做了两个假设:使用L1 norm进行度量,所有坐标被正整数化。
这里做了一个取巧,将哈曼顿距离转化为汉明距离后,求的实际上是汉明距离下的LSH。真正针对曼哈顿距离和欧式距离的LSH会在几年后提出。
汉明距离的定义是两个相同长度字符串不同的位数,比如说011和010,不同为一位,距离为1。
先将哈曼顿距离转化为汉明距离,令C为坐标中最大的坐标值,n为空间维度。对于点,转化为一个长度为nC的一元二进制向量:Unary(x)是一串长度为C的二进制汉明码,前x位为1,后C-x位为0,比如C=4,x=2,Unary(2) =1100。
定义一族哈希函数H:
对于,如果第r位为1,则h(p,r) = 1,如果第r位为0,则h(p,r) = 0。
其中r是1到nC之前随机产生的正整数。
例子:
对于某一族,抽取第一位,抽取第四位,那么这一个哈希表中总共有4个哈希堆,00,01,10,11,则点P属于10这一个bucket。
来看看这族哈希函数是否满足LSH:
考虑两个长度为nl的一元向量p和q,汉明距离为d,则它们被哈希成相同哈希值的概率为,转化为概率与距离的关系是一条下降的线段,满足LSH哈希函数的定义。
Reference:
[1] Approximate nearest neighbors: towards removing the curse of dimensionality
[2] Similarity search in high dimensions via hashing