局部敏感哈希图像检索参数优化方法

吴家皋，王永荣，邹志强，胡 斌

(1.南京邮电大学 计算机学院，江苏 南京 210023;2.江苏省大数据安全与智能处理重点实验室，江苏 南京 210023;3.南京师范大学 虚拟地理环境教育部重点实验室，江苏 南京 210046)

0 引 言

大数据时代的多媒体数据正在迅速增长，例如高清摄像机生成的数据量已达到约3.6 GB/小时，并且由如此大量的摄像机生成的视频数据量将达到EB级别[1]。高维数据(如图像和视频)的特征维度通常可以达到数百维甚至数千维[2-3]，这些高维数据通常表现出非结构化特征，因此传统的处理数据方法不能很好地满足高维数据的处理要求，相似性数据检索等任务正面临着巨大的困难。

由于在实际检索数据的时候，用户对于检索效率要比检索质量的要求更高，这也就是说，允许一定的误差存在于查找结果和真实值之间[4]，基于该理念而提出了近似近邻(approximate nearest neighbor，ANN)算法[5]。现在，在低维数据检索方面，基于树结构的近邻查找的效果很好，它的分类主要是基于数据的划分[6]和基于空间划分。虽然树索引算法在处理较低维数据时效果很好，但是近邻搜索在处理高维数据时遇到了“维度诅咒”问题[7]：树索引结构算法的效率随着特征维度的增加而快速下降。在高维数据索引方面，基于哈希的索引技术一直受到国内外研究人员的广泛关注[8-9]。与基于树的索引技术相比，哈希索引技术在高维数据索引上具有显著的优势：时间复杂度低，内存占用少。

在众多哈希索引技术中，由Indyk和Motwani在1998年提出的局部敏感哈希(locality sensitive hash，LSH)[10]算法是最具代表性的算法之一。它的基本思想是通过一组哈希函数对特征数据建立多张哈希表，使得映射后相似的点冲突的概率大，而不相似的点冲突的概率小，从而将相似和不相似的数据能够进行很好的区分。局部敏感哈希的性能对几个参数非常敏感，而如何选择这些参数是算法实现时必须考虑的问题。

针对上述问题，文中提出了一种基于二分查找的LSH参数优化方法。首先根据局部敏感哈希函数族和图像检索的目标建立局部敏感哈希优化模型，明确指出算法优化参数和优化目标函数，然后分析图像特征数据的距离分布特点，得出参数之间的关系，最后结合数值微分和二分查找提出相应的参数优化算法。实验结果表明，该方法可以大幅降低算法的复杂度，提高运行效率，同时保持较高的精确值和召回率的调和均值F1。

1 相关工作

1.1 局部敏感哈希算法

局部敏感哈希对数据点集利用一组哈希函数建立多张哈希表，使得经过哈希映射后相似的点冲突的概率大，而不相似的点冲突的概率小。自LSH提出以来，与其有关的各种哈希索引方法相继被提出。P-Stable LSH[11]将LSH的空间距离计算由海明空间转移到欧氏空间；Entropy-based LSH[12]在查询项的周围随机产生扰动对象作为查询项集合，这种算法是以时间为代价来减少空间的消耗；Multi-probe LSH[13]通过大量实验指出几乎所有候选查询结果与查询对象在相同或者相邻的映射桶内，并据此提出有效的索引方案；Dynamic Collision Counting(C2LSH)[14]利用一组由多个单独的LSH函数组成的函数基底构造“动态”的组合哈希函数，并且提出了一个新的LSH方案；文献[15]提出的方法证明至少在汉明空间，与传统的基于LSH的方法相比可以减少误报率问题。

1.2 局部敏感哈希参数优化

局部敏感哈希的性能对几个参数非常敏感，而这些参数必须在算法实现时选择。算法中需要确定的参数有：区间大小w、哈希函数族维度k、哈希表个数L等。局部敏感哈希森林[16]通过固定其中一个参数部分解决了这个问题。然而，算法实现仍然留下了为其他参数寻找最优值的问题。参数调整过程既单调乏味又严重阻碍算法的应用，而目前对这些参数值的选取提供的指导又很少。文献[17]中优化的最佳参数有：映射区间大小w，形成的复合哈希函数中哈希函数的数量k，哈希表的数量L，以及每张表中探测到的哈希桶数量T。先对召回率和选择性建模并且将其应用到参数优化中，这两个性能度量被定义为数据分布的函数，而由真实数据得到的分布满足伽马分布。然后，在召回率满足要求的前提下，通过最小化选择性来计算最佳参数。相似的更加完整的参数优化分析由文献[18]给出。首先将距离分布函数转变成映射区间w的冲突概率函数，然后假设w和k的值来估计表的最佳数量L。鉴于L的估计，找到最小化搜索时间成本的k。最后根据k和L的最佳值找到最好的w。

然而上述优化方法的性能指标考虑仍不够周全。为了同时保证较高的查询效率和查询质量，并且由于精确率和召回率的加权调和平均值F1综合考虑了精确率和准确率对图像检索算法的影响，所以性能指标采用F1，提出使F1取得最大值的局部敏感哈希图像检索参数优化方法。为了取得最优的F1，可以采用数值微分结合二分查找得出参数之间的关系。

2 算法描述

2.1 局部敏感哈希优化模型

在对局部敏感哈希算法进行实验时发现，当进行算法实现的时候，其中的一些参数需要用户自己选择。针对这一问题，文中提出一种局部敏感哈希参数快速选择的方法。该方法能根据局部敏感哈希理论模型和图像数据的距离分布函数，快速计算得到最优的精确率和召回率的调和平均F1。

设任一图像都能表示为d维特征向量空间Rd中的一个点，则所有图像构成d维特征向量数据集D，DRd；定义局部敏感哈希函数族H={h|D→U}为从数据集D到整数域U的映射：

(1)

其中，v∈D是任一图像的特征向量；a是d维正态分布随机向量；b是[0,w]上均匀分布的随机实数；w是映射区间大小的整数。

首先计算两点经过哈希之后的冲突概率。使用fp(t)表示正态分布的绝对值的概率密度函数，对于两点v1和v2，r=|v1-v2|为两点的欧氏距离。当w=w0时，经过哈希函数映射之后两点的冲突概率为[11]：

(2)

从H中取k个函数，定义k维局部敏感哈希函数族G={g|DUk}为从数据集D到k维整数域U的映射：

g(v)=(h1(v),…,hk(v))

(3)

其中，hi(v)∈H,i∈[1,k]。

从G中取L个哈希函数：gi(v)G，l[1,L]。对于所有vD，利用gi(v)建立L张哈希索引表。经过哈希函数映射之后得到的冲突概率为：

q(r,k,L)=1-[1-p(r)k]L

(4)

图像检索的目标是从图像数据集中找出所有与查询点的欧氏距离不大于查询范围r0的所有图像，在求得冲突概率q(r,k,L)和图像数据的距离分布概率密度函数f(r)之后，精确率和召回率分别为：

(5)

(6)

F1为精确率和召回率的调和平均，即：

(7)

定义参数最优化问题如下：

(8)

L≤L0

其中，L0为哈希表数的上限。

2.2 两点间的距离分布

下面分析图像特征数据两点间距离分布的概率密度f(r)。两点的欧氏距离的平方曲线可以用伽马分布进行拟合[17]，伽马分布的概率密度函数为：

(9)

其中，β是形状参数；θ是尺度参数；α是使函数积分为1的归一化系数。

伽马分布的参数可以用最大似然估计进行计算，仅仅和样本的算术平均E和几何平均G相关，而E和G可以通过采样获得。给出E和G，则β和θ可由以下方程组求得：

(10)

其中，ω(β)=Γ(β)Γ(β)为双伽马函数。

图1显示的是典型的图像数据集任意两点的距离平方的概率密度曲线，可以从图中看出距离平方分布基本符合伽马分布。

图1 距离平方的概率密度直方图

2.3 局部敏感哈希参数优化算法

当r0=4,w0=10,L0=100且两点距离平方的概率密度分布为伽马分布时，采用枚举算法得到F1和k、L的关系如图2所示。从图中可知，F1随着L的增加单调增加，因此，最优的L应取其约束上限L0，即Lopt=L0。又因为，对于给定的L，F1为k单峰函数，所以可采用二分查找算法快速确定最优的k值。

图2 F1和k、L的关系示意

采用数值微分的方法求F1对k的偏导数，即求：

(11)

其中h为一个微小的数值。因为F1为单峰函数，所以偏导数为零的点两边异号，可以对数值微分计算得到的数组采用二分查找算法，从而求得k的最优值。设置k取值范围为1≤k≤kmax，其中kmax为设置的一个越过峰值的较大的整数。由于采用了二分查找算法，所以参数优化算法时间复杂度为O(logkmax)。

求解最优参数k的算法如下：

算法：局部敏感哈希参数优化算法

输入：kmax，r0，w0，L0

输出：最优参数kopt

1.low=1

2.high=kmax

3.whilelow≤high do

4.mid=⎣(low+high)/2」

5.if dF1(mid)=0 then

6.break

7.else if dF1(mid)<0 then

8.high=mid-1

9.else

10.low=mid+1

11.end if

12.end while

13.kopt=mid

3 测试与性能分析

文中采用GitHub开源项目JorenSix/TarsosLSH自带的数据集，一共有4 764条图像特征数据，提取到的图像特征的维度为256维，因此实验的数据集是基于真实的特征数据，实验用到的数据集大小为3.96 M。

当r0=4,w0=10,L0=100且两点距离平方的概率密度分布为伽马分布时，若使用枚举法求F1最大值对应的k，得到kopt=16。若采用数值微分计算偏导数，然后再对偏导数计算结果采用二分查找，则能够和枚举法得到相同的最优结果，从而验证了上述算法的有效性。

为了讨论不同的数据分布对算法结果的影响，令r0=4,w0=10，设两点距离分布为均匀分布和伽马分布，取不同的L0，最优的k所对应的曲线如图3所示。可以看出，kopt随着L0的增加而增加。当L0确定时，伽马分布取的kopt比均匀分布的大。

图3 不同分布时最优的k和L0的关系示意

下面针对伽马分布和均匀分布分别讨论不同的参数对算法的影响。

(1)当r0=4，取不同的w0，分别针对伽马分布和均匀分布，得到L0与最优的k所对应的曲线，如图4(a)和(b)所示。可以看出，最优的k随着w0的增加而增加。这是因为w0越大哈希桶的粒度就越粗，要达到同等的检索精准度，k值也要增加。在当w0和L0相同时，伽马分布kopt取值比均匀分布的要大。

(a)伽马分布

(b)均匀分布

(2)当w0=10，取不同的r0，分别针对伽马分布和均匀分布，得到L0与最优的k所对应的曲线，如图5(a)和(b)所示。可以看出，最优的k随着r0增加而减小。因为较大的r0对应检索条件也较宽，需要的k值也较小。同样，当r0和L0相同时，伽马分布kopt取值比均匀分布的要大。

(a)伽马分布

(b)均匀分布

(3)当r0=4，L0[1,100]，取不同的w0，分别针对伽马分布和均匀分布，得到最优的k与最优F1所对应的曲线，如图6(a)和(b)所示。可以看出，F1opt随kopt的增加而增加，同时，随着w0增大，最优的k和F1也在增大。另外，在相同参数条件下，均匀分布的最优F1明显高于伽马分布的F1，说明不同分布对检索性能的影响是比较明显的。

(a)伽马分布

(b)均匀分布

(4)当w0=10，L0[1,100]，取不同的r0，分别针对伽马分布和均匀分布，得到最优的k与最优F1所对应的曲线，如图7(a)和(b)所示。同样可以看出，F1opt随kopt的增加而增加，同时随着r0增大，最优的k在减小，F1则增大。而均匀分布的F1opt仍明显比伽马分布的高。

(a)伽马分布

最后，将提出的二分查找算法和枚举法进行比较，以验证局部敏感哈希参数优化算法求解参数最优化问题的高效性。当r0=4,w0=10,L0[1,100]，kmax设置为固定的较大的整数r0，针对伽马分布，得到不同算法的运行时间T与L0所对应的曲线，如图8所示。可以看出，枚举法的运行时间随着L0的增大显著增加，而提出的二分查找算法的运行时间比较稳定，随着L0的增大变化不大，且明显小于枚举法。这是因为局部敏感哈希参数优化算法直接取最优的L=L0，同时采用二分法搜索最优参数kopt，从而使其运行时间与枚举法相比有显著优势。

图8 算法运行时间T和L0的关系曲线

4 结束语

提出了一种基于局部敏感哈希的参数优化方法，提高了图像检索的计算效率。实验结果表明，局部敏感哈希算法在参数优化后运行，能够加快图像检索的运行效率。在当今图像数据爆炸性增长的背景下，在图像检索上采用高效的参数计算方法实现局部敏感哈希算法具有深远的意义。后期将对局部敏感哈希采用分布式方式加快图像检索，并在此基础上进行基于分布式的参数选择模型相关的分析。