局部敏感哈希在高维向量K近邻搜索中的应用

张 亮,谢晓尧

(1.贵州大学 计算机科学与信息学院,贵州 贵阳 550001;2.贵州省信息与计算科学重点实验室,贵州 贵阳 550001)

前言

局部敏感哈希是一种对高维度数据通过概率方法降维的一种方法,基本的想法是将输入的数据进行哈希,使得相似的数据的哈希值映射到同一个哈希桶的概率非常高。由于在局部敏感哈希中,哈希桶的数量远远小于输入数据的穷举数量,它的实现方法和传统的哈希函数较不一样,通常用于数据的聚簇和最近邻搜索[1-3]。

在图片的相似性搜索的应用中[4],给定一张参考图片,来从图片数据库中进行搜索,以得到和参考图片最相似的若干图片。搜索的过程通常经过2个步骤,首先通过特征点提取算法将图片中的特征点和特征向量提取出来,然后将提取特征点的特征向量在数据库中进行搜索,取得最相似的向量,再进行匹配。而特征向量在数据库中的相似性搜索实际上是一个K近邻的问题,这就是本论文所研究的问题。在K近邻的搜索方面,传统的做法有线性搜索和空间分割,空间分割通常用的是KD-Tree和R-Tree的方法。线性搜索的时间复杂度为O(Nd),N为样本空间大小,d为维度。在低维度情况下,KD-Tree和R-Tree的平均时间复杂度为O(logN◦d),最坏时间复杂度为O(Nd)。而在高维度的情况下,KD-Tree和R-Tree的平均时间复杂度为O(Nd)。局部敏感哈希方法通过降低结果的精度,将K近邻问题转化为近似K近邻问题,通过常数的时间复杂度就可以得到一个粗糙的样本集合,再从这个样本集合中去糙取得更为精确的结果。

1 基本概念和理论基础介绍

定义1:哈希函数

把任意长度的输入,变成固定长度的输出的一种映射称为哈希,这个映射关系称为哈希函数。

哈希函数通常用来做文件校验,数字签名,搜索。在搜索中,通过哈希函数可以用常数的时间从原来的搜索集中取得一个集合,再从这个集合中进行搜索。取得的这个集合的大小如果比原来的搜索集小的多,便可以大大降低算法复杂度。使用哈希方法来搜索关键在于哈希函数的质量。

定义2:1近邻问题[5]

在一个n个点(向量)的集合P中,用d(p,q)表示点p到q之间的距离函数(计算距离的方法按照实际应用而定)。给一个点p,返回一个不同于p的点 q,对任意r∈P且r≠p,使得 d(p,q)≤d(p,r)。

定义3:K近邻问题

在n个点(向量)的集合P中,给一个点p,返回K个离p最近的点集。

定义4:近似K近邻

在很多搜索的应用中,所求的解并不要求是绝对的K近邻的解,可以是K个近似于K近邻的解,这样的话,我们找到了可以用于求近似解的哈希方法:局部敏感哈希(Locality-sensitive hashing)。

2 局部敏感哈希算法的介绍

局部敏感哈希是对高维数据的一种概率降维的方法。基本的思想是将数据hash,使得相似的数据将高概率的映射到同一个hash桶中。

在一个度量空间(M,d)中,给定一个阈值R＞0,和一个大约因子c＞1。

F为一个函数集合h:M-＞S.对任意点p,q∈M,从这个函数集合中任意选择一个函数h,使得

如果d(p,q)≤R,那么h(p)=h(q)的概率至少为P1。

如果d(p,q)≥cR,那么h(p)=h(q)的概率最多为P2。

当P1＞P2时,函数集合F称之为(R,cR,P1,P2)敏感。

实现:[6]

假设有n个维度为d的向量需要通过局部敏感哈希的方法哈希。

a)将n个维度为d的向量,转换为每个向量的坐标都为正整数的向量。

只要选好一定的A和w,即可将所有的向量按照同一个公式转化为坐标都为正整数的向量。

b)假设所有向量中最大的坐标值为C。将每一个向量做如下的变换。假设r为向量v的一个坐标,u(r)=000…0111…1(其中左端全为0,右端全为1,除中间位置并无01交错的情况)。其中1的个数为r的值的大小。如最大值C为10,r=4,那么u(r)=0000001111。再假设运算符|连接2个数,如0011|0001=00110001。每个向量v通过f(v)做转换:f(v)=u(v1)|u(v2)|u(v3)|…|u(vd);v1,v2,…vd为向量的坐标。那么每一个向量v都会转化为一个Cd长度的01串。

c)从0到Cd-1的整数中随机选取k个数为:n1,n2,n3,…,nk(一次性预处理选定常数),设h(v,n)为v中第n个坐标,g(v)=h(v,n1)|h(v,n2)|…|h(v,nk)。

d)g(v)便为向量v的一个hash值。

e)为了提高相似碰撞率,采取多张hash表的方式,每张hash表的处理方法一样,只是每张hash表中选取的k个数不一样。

f)由于g(v)是一个长度为k的2进制数,即hash表的值有2k可能性。当k的值很大时,可采用二次hash的方法。设(v1v2v3…vk)为g(v)的值,每一个vi为一个二进制位,h(v1,v2,v3,…vk)=a1v1+a2v2+…+akvkmod M,M为hash表的大小,ai为[0…M-1]中的随机正整数。

3 通过局部敏感哈希在高维向量K近邻搜索

在图片的相似性搜索的应用中,特征向量的搜索部分可以这样来处理。

总步骤:

(1)样本库的预处理:将n个d维的向量的样本库存放在L个哈希表中,对于每一个向量,通过上述的方法,分别放入L个哈希表中对应的键值的桶中。

(2)对于某个向量p在样本库中的搜索。通过上述的方法计算出向量p在每一个哈希表中对应的哈希值:h1,h2,…,hL。再从L个哈希表中取出L个向量的集合取并集。再从得到的并集中,选取离向量p最近的K个点。

通过局部敏感哈希搜索的正确率的分析[7]:

由于汉明距离实际上就是转换成正整数坐标的L1范数距离。下面的分析忽略2次哈希的效果,实际上2次哈希只会增加正确率,因为在1次哈希中碰撞的向量在第2次哈希中必然碰撞,当然2次哈希增加了搜索时候的时间复杂度。

(1)1张哈希表中的碰撞概率的分析。

假设两向量p,q的L1距离为x,d'=Cd,那么两向量碰撞的概率为:

那么距离在a以内的两向量p,q的碰撞概率为:

这表明两向量p,q的碰撞概率除了和p,q之间的距离有关,而且和向量的分布情况有关。

(2)L张哈希表中碰撞概率的分析。

很明显,哈希表越多,碰撞的概率越大,但同时也增加了时间复杂度。

时间复杂度的分析:

(1)样本库预处理的时间复杂度分析。

样本库的插入的时间主要在哈希函数的计算上,哈希函数计算的时间复杂度为O(k),由于原向量转换成的2进制表示方式有着特殊的形式:都是由一段一段的111…00构成的。可以将每一段使用查表的方式进行哈希计算,这样哈希函数的计算将会缩短成为O(d)。

总的时间复杂度为O(ndL)。哈希表的存储方式也将是决定最后的时间消耗的重要因素。

(2)单个向量搜索的时间复杂度分析。

由于向量搜索分为两个步骤,首先提取出每个哈希表中对应键值的向量集取并集,然后对取得的向量集做距离的筛选。

总的时间复杂度为O(dL)+O(Lmd),m为哈希表中平均每个桶中的向量个数。

4 结语

在高维度的搜索中,用到的常见方法有KD-Tree,R-Tree等,这些方法能对K-NN(k近邻)问题搜索到精确解,但是当维度到达一定大小后,耗时使得算法不能用于实际应用。当要求的K-NN问题为近似解的时候,我们可以引入局部敏感哈希的方法来进行索引和搜索,算法的难点在于调节哈希表的参数(包括哈希表的大小和哈希表的数目,汉明空间中k的选取等)和用于实现哈希表的软件方法。

[1]P.Indyk and R.Motwani.Approximate nearest neighbors:towards removing the curse of dimensionality[A].InSTOC'98:Proceedings of the thirtieth annual ACM symposium on Theory of computing,New York,USA:ACM Press,1998:604～613.

[2]Aristides Gionis,Piotr Indyk,and Rajeev Motwani.Similarity search in high dimensions via hashing[A].InVLDB'99:Proceedings of the 25th International Conference on Very Large Data Bases[C],San Francisco,CA,USA:Morgan KaufmannPublishers Inc.1999:518～529.

[3]曹玉东,刘福英,蔡希彪.基于局部敏感哈希算法的图像高维数据索引技术的研究[J].辽宁工业大学学报(自然科学版),2013,(1):1～4.

[4]夏宇,朱欣焰.高维空间数据索引技术研究[J].测绘科学,2009,(1):60～62.

[5]Alexandr Andoni.Nearest Neighbor Search:the Old,the New,and the Impossible[D].Massachusetts Institute of Technology,2009.

[6]M.Datar,N.Immorlica,P.Indyk,and V.S.Mirrokni.Locality-sensitive hashing scheme based on p-stable distributions[A].In SCG'04:Proceedings of the twentieth annual symposium on Computational geometry[C],New York,USA:ACM Press,2004:253～262.

[7]Wei Dong,Zhe Wang,William Josephson,Moses Charikar,Kai Li.Modeling LSH for Performance Tuning[A].Proceedings of the 17th Conference on Information and Knowledge Management[C].Napa Valley,CA,USA:Information Retrieval Facility,2008:669～678.