Skip to main content

局部敏感哈希算法简介

局部敏感哈希算法简介

00:00/00:00

今天是教师节,家里从爷爷到爸爸妈妈、姑姑姑爷都是老师,所以深知老师们的辛苦和不易。一路走来,也遇到了非常多耐心负责、可爱的老师。谨借此机会在这里,祝愿天下所有的老师:身体健康、工作顺利、桃李满天下!
哈哈,接下来开始正题。

背景介绍

在很多情况下,我们都希望能在海量/高维的情况下快速找到与目标数据相似的数据。在数据量较小的情况下,一般可以直接通过比较常见的查找算法进行计算。然而,随着数据量的快速增长,性能和容量限制成为了很大的瓶颈。为了解决这个问题,我们需要采用一些算法能够快速过滤掉大量无关的数据,减少候选集数量。通常,这种方法成为最近邻查找(Nearest Neighbor,NN)。对于准确度要求不那么高的情况,也可以使用近似最近邻查找(Approximate Nearest Neighbor, ANN)。其中,局部敏感哈希算法就属于第二类。

应用场景

海量/高维数据中快速定位到相似的数据。例如,网页去重/协同过滤/新闻去重/图像检索/指纹匹配等等,感觉只要与寻找邻居数据相关的应用场景都可以考虑使用LSH。

基本原理

局部敏感哈希(Locality Sensitive Hashing, LSH)的基本原理是:对原始数据使用相同的方式进行映射和投影

离线建立索引(Hash Table)

  • 选取满足(d_1,d_2,p_1,p_2)-sensitive的LSH哈希函数
  • 基于对查找结果召回率(即相似数据被查找到的概率)的要求确定哈希表的个数L,每个哈希表内的哈希函数个数为K,以及与LSH哈希函数自身相关的参数
  • 将所有数据经过LSH哈希函数哈希到相应的桶中,构成一个或多个哈希表

在线查找

  • 将需要查找的关键词输入哈希函数得到相应的桶号
  • 将相应桶中对应的数据取出
  • 计算查询数据与候选数据之间的相似度,返回最近邻的数据

一般说来,LSH在线查找时间由两个部分组成:

  • 通过LSH哈希函数获得桶号的时间
  • 将查询数据与桶内数据进行比较计算的时间

可以通过建立索引的方式来加快第二部分所花时间。

LSH Family

接下来会介绍一些满足不同距离度量方式下的LSH哈希函数。

Jaccard距离和minHash

Jaccard Distance = 1 – Jaccard Similarity ,其中Jaccard Similarity(x,y) = \frac{|x\bigcap y|}{|x\bigcup y|},一般用于判定两个集合直接按的相似性,其对应的哈希函数为minHash。((d_1,d_2,1-d_1,1-d_2)-sensitive

minHash的大致思路是:采用一种哈希函数,将元素的位置均匀打乱,然后将新顺序下每个集合的第一个元素作为该集合的特征值。
举个例子,假设x_1={a,b,c}, x_2={c, d},假设全集为U={a,b,c,d},集合可以表示为:

元素 x_1 x_2
a 1 0
b 1 0
c 1 1
d 0 1

上表中每一行表示集合是否包含该元素,每一列代表该集合的所有元素。假设哈希函数为h_1(i)=(i+1)%4,其中i为行号,那么针对集合x_1x_2,我们有如下结果:

元素 x_1 x_2
d 0 1
a 1 0
b 1 0
c 1 1
minHash a d

论证:
P(MinHash(x_1)=MinHash(x_2))=Jac(x_1,x_2)
在哈希函数均匀分布的情况下,集合x_1x_2的MinHash值相等的概率等于这两个集合的Jaccard相似度。

x_1x_2的每一行可能有以下三种情况:
– a类:均为1
– b类:一个为0,一个为1
– c类:均为0
由于第c类对于求两个集合哈希相等的情况没有任何影响,并且假设哈希函数将原始的行号均匀分布到新的行号中,那么我们可以得到出现a类情况的概率为:\frac{|a|}{|a|+|b|}=Jac(x_1,x_2)

在随机排列次数较多情况下,一一比较数据之间的相似度也需要较长的时间,可以使用分桶的方式进行,在将数据输入哈希函数之后得到其签名,将签名分为b段,每个段有r个签名,假设两条数据之间的Jaccard相似度s等于两条数据minHash相等的概率。假定某两条数据在某个段上完全相同,那么则将该数据加入候选集合,分析如下:

  • 两条数据在一个段中完全一样的概率为s^r
  • 两条数据在一个段中不完全一样的概率为1-s^r
  • 两条数据在b段都不完全一样的概率为(1-s^r)^b
  • 两条数据在b段中至少有一段完全一样的概率为1-(1-s^r)^b

当然,为了减少候选集的数量,我们也可以将进入候选集的条件设定为同时在1+个段中。在得到候选集之后,我们可以将待查找的数据与候选集中的数据计算精确的相似度。

汉明距离和simHash

Hamming distance 为两个具有相同长度的向量中对于位置处值不同的次数。
minHash的哈希函数是:h(v)=向量v在第i位上的值 。( (d_1,d_2,1-\frac{d_1}{d},1-\frac{d_2}{d})-sensitive

余弦相似度

\cos(\theta)=\frac {AB}{|A||B|} ,一般来说,两条数据之间越相似,那么这两条线之间的夹角就会越小,其余弦值越大。

其对应的LSH哈希函数为h(v)=sign(vr),其中r是一个随机向量,vr可以看做是向量vr上的投影操作。((d_1,d_2,\frac{180-d_1}{d_1}, \frac{180-d_2}{180})-sensitive

其原理在于:可以假设我们利用随机的超平面对原始的数据空间进行划分,每一个数据被投影之后都有可能被划分到超平面的某一侧,经过多个随机的超平面划分之后,原始空间就被划分为了很多块,而位于每个块中的数据被认为有很大概率是相邻的。

普通欧式距离

eud(x_1,x_2)=\sqrt{\sum{(x_1[i]-x_2[i])}^2},其中i=1,2,3..n,其主要用于度量n维空间中两个点之间的真实距离,或者向量的自然长度(即该点到原点的距离)。

其对应的LSH哈希函数为h(v)=|vr+b|/a,其中,r是一个随机向量,a是桶宽,b是一个在[0,a]之间均匀分布的随机变量。((a/2,2a,1/2,1/3)-sensitive

其原理在于:将原始数据空间中的数据投影到一条随机的直线上,并且该直线由许多长度为a的线段组成,每一个数据被投影之后会落入该直线的某一个线段上,将所有数据都投影到直线上之后,位于同一个线段内的数据将会被认为具有很大可能是相邻的。

代码示例(Java)

minHash

下面看一段怎么实现minHash的java代码:

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Random;
import java.util.Set;
public class MinHash<T>
{
    private int hash[];
    private int numHash;
    public MinHash(int numHash)
    {
        this.numHash = numHash;
        hash = new int[numHash];
        Random r = new Random(11);
        for (int i = 0; i < numHash; i++)
        {
            int a = (int) r.nextInt();
            int b = (int) r.nextInt();
            int c = (int) r.nextInt();
            int x = hash(a * b * c, a, b, c);
            hash[i] = x;
        }
    }

    public double similarity(Set<T> set1, Set<T> set2)
    {
        int numSets = 2;
        Map<T, boolean[]> bitMap = buildBitMap(set1, set2);
        int[][] minHashValues = initializeHashBuckets(numSets, numHash);
        computeMinHashForSet(set1, 0, minHashValues, bitMap);
        computeMinHashForSet(set2, 1, minHashValues, bitMap);
        return computeSimilarityFromSignatures(minHashValues, numHash);
    }
    private static int[][] initializeHashBuckets(int numSets,
                                                 int numHashFunctions)
    {
        int[][] minHashValues = new int[numSets][numHashFunctions];
        for (int i = 0; i < numSets; i++)
        {
            for (int j = 0; j < numHashFunctions; j++)
            {
                minHashValues[i][j] = Integer.MAX_VALUE;
            }
        }
        return minHashValues;
    }
    private static double computeSimilarityFromSignatures(
            int[][] minHashValues, int numHashFunctions)
    {
        int identicalMinHashes = 0;
        for (int i = 0; i < numHashFunctions; i++)
        {
            if (minHashValues[0][i] == minHashValues[1][i])
            {
                identicalMinHashes++;
            }
        }
        return (1.0 * identicalMinHashes) / numHashFunctions;
    }
    private static int hash(int x, int a, int b, int c)
    {
        int hashValue = (int) ((a * (x >> 4) + b * x + c) & 131071);
        return Math.abs(hashValue);
    }
    private void computeMinHashForSet(Set<T> set, int setIndex,
                                      int[][] minHashValues, Map<T, boolean[]> bitArray)
    {
        int index = 0;
        for (T element : bitArray.keySet())
        {
            /*
             * for every element in the bit array
             */
            for (int i = 0; i < numHash; i++)
            {
                /*
                 * for every hash
                 */
                if (set.contains(element))
                {
                    /*
                     * if the set contains the element
                     */
                    int hindex = hash[index];
                    if (hindex < minHashValues[setIndex][index])
                    {
                        /*
                         * if current hash is smaller than the existing hash in
                         * the slot then replace with the smaller hash value
                         */
                        minHashValues[setIndex][i] = hindex;
                    }
                }
            }
            index++;
        }
    }
    public Map<T, boolean[]> buildBitMap(Set<T> set1, Set<T> set2)
    {
        Map<T, boolean[]> bitArray = new HashMap<T, boolean[]>();
        for (T t : set1)
        {
            bitArray.put(t, new boolean[] { true, false });
        }
        for (T t : set2)
        {
            if (bitArray.containsKey(t))
            {
                // item is not present in set1
                bitArray.put(t, new boolean[] { true, true });
            }
            else if (!bitArray.containsKey(t))
            {
                // item is not present in set1
                bitArray.put(t, new boolean[] { false, true });
            }
        }
        return bitArray;
    }
}

simHash

再来一段simHash的:

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class SimHash {
    private String tokens;
    private BigInteger intSimHash;
    private String strSimHash;
    private int hashbits = 64;
    public SimHash(String tokens) {
        this.tokens = tokens;
        this.intSimHash =this.simHash();
    }
    public SimHash(String tokens, int hashbits) {
        this.tokens = tokens;
        this.hashbits = hashbits;
        this.intSimHash =this.simHash();
    }
    /**
     * get the simHash value of String tokens
     * @return simHash value
     */
    private BigInteger simHash() {
        // 定义特征向量/数组
        int[] v =new int[this.hashbits];
        // 1、将文本去掉格式后, 分词.
        StringTokenizer stringTokens =new StringTokenizer(this.tokens);
        while(stringTokens.hasMoreTokens()) {
            String temp = stringTokens.nextToken();
            // 2、将每一个用户ID hash为一组固定长度的数列.比如 64bit 的一个整数.
            BigInteger t =this.hash(temp);
            for(int i = 0; i < this.hashbits; i++) {
                BigInteger bitmask =new BigInteger("1").shiftLeft(i);
                // 3、建立一个长度为64的整数数组(假设要生成64位的数字指纹,也可以是其它数字),
                // 对每一个分词hash后的数列进行判断,如果是1000...1,那么数组的第一位和末尾一位加1,
                // 中间的62位减一,也就是说,逢1加1,逢0减1.一直到把所有的分词hash数列全部判断完毕.
                if(t.and(bitmask).signum() != 0) {
                    // 这里是计算整个文档的所有特征的向量和
                    // 这里实际使用中需要 +- 权重,而不是简单的 +1/-1,
                    v[i] +=1;
                }else {
                    v[i] -=1;
                }
            }
        }
        BigInteger fingerprint =new BigInteger("0");
        StringBuilder simHashBuffer =new StringBuilder();
        for(int i = 0; i < this.hashbits; i++) {
            // 4、最后对数组进行判断,大于0的记为1,小于等于0的记为0,得到一个 64bit 的数字指纹/签名.
            if(v[i] >= 0) {
                fingerprint = fingerprint.add(new BigInteger("1").shiftLeft(i));
                simHashBuffer.append("1");
            }else {
                simHashBuffer.append("0");
            }
        }
        this.strSimHash = simHashBuffer.toString();
        System.out.println(this.strSimHash +" length " + this.strSimHash.length());
        return fingerprint;
    }
    /**
     * get the hash code  of the string(source)
     * @param source string
     * @return hash code
     */
    private BigInteger hash(String source) {
        if(source == null|| source.length() == 0) {
            return new BigInteger("0");
        }else {
            char[] sourceArray = source.toCharArray();
            BigInteger x = BigInteger.valueOf(((long) sourceArray[0]) << 7);
            BigInteger m =new BigInteger("1000003");
            BigInteger mask =new BigInteger("2").pow(this.hashbits).subtract(new BigInteger("1"));
            for(char item : sourceArray) {
                BigInteger temp = BigInteger.valueOf((long) item);
                x = x.multiply(m).xor(temp).and(mask);
            }
            x = x.xor(new BigInteger(String.valueOf(source.length())));
            if(x.equals(new BigInteger("-1"))) {
                x =new BigInteger("-2");
            }
            return x;
        }
    }
    /**
     * calculate the hamming distance between two hashes
     * hamming distance: change times from current str to target str
     * @param other another str
     * @return hamming distance
     */
    public int hammingDistance(SimHash other) {
        BigInteger x =this.intSimHash.xor(other.intSimHash);
        int tot = 0;
        // 统计x中二进制位数为1的个数
        // 我们想想,一个二进制数减去1,那么,从最后那个1(包括那个1)后面的数字全都反了,对吧,然后,n&(n-1)就相当于把后面的数字清0,
        // 我们看n能做多少次这样的操作就OK了。
        while(x.signum() != 0) {
            tot +=1;
            x = x.and(x.subtract(new BigInteger("1")));
        }
        return tot;
    }
    public int getDistance(String str1, String str2) {
        System.out.println(str1);
        System.out.println(str2);
        int distance;
        if(str1.length() != str2.length()) {
            distance = -1;
        }else {
            distance =0;
            for(int i = 0; i < str1.length(); i++) {
                if(str1.charAt(i) != str2.charAt(i)) {
                    distance++;
                }
            }
        }
        return distance;
    }
    //the larger the distance is , the probability of two objects being divided to a single band
    //is larger.
    public List<BigInteger> subByDistance(SimHash simHash, int distance) {
        // split the hash code into |distances|+1 pieces
        int numEach = this.hashbits / (distance +1);
        List<BigInteger> characters =new ArrayList<>();
        StringBuilder buffer =new StringBuilder();
        for(int i = 0; i < this.intSimHash.bitLength(); i++) {
            // returns true if the ith bit is 1, else false
            boolean sr = simHash.intSimHash.testBit(i);
            if(sr) {
                buffer.append("1");
            }else {
                buffer.append("0");
            }
            if((i + 1) % numEach ==0) {
                // 将二进制转为BigInteger
                BigInteger eachValue =new BigInteger(buffer.toString(),2);
                //System.out.println("----"+ eachValue);
                buffer.delete(0, buffer.length());
                characters.add(eachValue);
            }
        }
        return characters;
    }
}

参考文献

打赏
微信扫一扫支付
微信logo微信扫一扫, 打赏作者吧~

mickey

记录生活,写给几十年后的自己。