在线密度敏感哈希算法研究

王 星,于江旭,唐晓亮,闫慧斌

1(辽宁工程技术大学 电子与信息工程学院,辽宁 葫芦岛 125105)2(辽宁工程技术大学 研究生院,辽宁 阜新 123000)3(辽宁工程技术大学 软件学院,辽宁 葫芦岛 125105)

1 引 言

随着网络设备和信息技术的飞速发展,数据在社会生活的方方面面起着越来越重要的作用,如何更快更准确地对大规模数据进行处理一直是人们的研究热点,近邻搜索[1]是最常见的数据处理方式之一.近邻搜索算法可以分为精确最近邻搜索[2,3]和近似最近邻ANNs[4](Approximate Nearest Neighbors)搜索.k最近邻[5]是比较经典的精确近邻搜索算法,许多精确近邻搜索算法都是基于树结构(比如说KD树[6],R树[7]等)的近邻搜索,但是在高维数据的检索中,这些算法效率会直线下降,因此近似最近邻搜索的研究得到了人们的关注,越来越多基于哈希的ANNs算法[8,9]被提了出来.ANNs的特点是在损失少量精度的条件下实现快速的近邻搜索,提高效率的同时也可以得到精度相对较高的搜索结果.基于哈希的方法是ANN搜索的代表之一.按照其产生哈希函数的原理,哈希算法大致可以分为基于随机映射的哈希算法和基于学习的哈希算法.前者不考虑数据分布[8],而后者根据数据分布形成哈希函数[9].

上述的精确最近邻搜索算法和基于哈希的搜索算法都是基于静态数据的搜索算法,其处理数据的量总体上是不变的.但在实际应用中,遇到动态的数据,或者数据量比较大,无法一次性放入内存时,这些算法就无法使用.比如在数据库中进行数据搜索,当有新的数据加入数据库时重新对数据进行一次近邻搜索是不现实的,浪费大量的时间和内存,于是许多处理动态数据的技术[10,11]被提了出来.在线k均值聚类算法[11]可以在保持原来数据样本不变的情况下对新的数据样本进行快速聚类.

针对现阶段的哈希算法无法有效处理大规模动态数据的问题,本文提出一种新的在线k均值聚类算法,并将其与密度敏感哈希算法[12]结合,形成一种基于在线学习[13]的哈希算法,即在线密度敏感哈希ODSH (Online Density Sensitive Hash),该算法首先使用在线k均值聚类对数据进行预处理量化,然后根据产生的量化结果生成动态的超平面,根据超平面求出哈希方程,求出对应的投影向量和截距,最后使用投影向量对数据进行映射,得到哈希编码,并使用汉明距离进行对比,获得需要的近邻结果.实验证明,ODSH不仅具有基于学习哈希算法的特点,可以返回精确的结果,而且还可以快速地处理大规模动态数据.

2 相关工作

本节介绍哈希算法的基本概念和常见的哈希算法.

2.1 哈希算法的基本概念

哈希算法是一种可以将原始数据样本快速映射到新的数据空间并生成二值编码,可以实现高效数据检索的搜索算法.各种哈希算法之间的主要区别在于采用了不同的哈希函数,根据哈希函数得到投影向量,再对数据进行映射获取哈希编码,哈希算法中最基本的哈希函数如公式(1)所示:

y=h(x)

(1)

h(·)是哈希函数,y是经过哈希函数映射后的哈希编码,通常情况会使用多个哈希函数来组成一族哈希函数,产生多组哈希编码,即,Y=[y1y2…ym]=[h1(x)h2(x)…hm(x)].哈希算法将任意长度的二进制值映射为较短的二进制值,广泛地应用于快速检索.基于映射的线性哈希搜索,第k个哈希函数定义如公式(2)[14]所示:

(2)

x是任意的一个数据点,wk是投影向量,tk是一个阈值,也可以称为投影向量对应的截距,而f(·)表示的是一个目标函数.定义中的sgn函数只会返回{-1,1},经过哈希函数映射后的二进制编码可以表示为bk=(1+Hk(x))/2.下面总结一下比较常见的哈希算法.

2.2 基于随机映射的哈希

局部敏感哈希LSH[8](Locality Sensitive Hash)是最常用的哈希算法之一,它的基本思路是将原来空间中相邻的数据点通过映射或者投影到新的数据空间中,其仍然相邻的概率较大,而不相邻的数据点映射到同一个数据空间的概率很小.LSH通过生成大量的随机映射,生成较长的哈希表来保证数据检索的准确率,其哈希函数比较简单,容易实现,且速度较快,但是较长的哈希表会占用较大的内存,而较短的哈希编码会导致检索的准确率降低.

平移不变核哈希算法SKLSH[15](shift-invariant kernels Locality Sensitive Hash),平移不变核哈希算法利用了平移不变的核方法来产生随机投影,原理近似于LSH.

2.3 基于学习的哈希

以上算法是非数据驱动的哈希算法,在哈希编码长度较长的时候效果较好,但是有占用内存大,复杂度较高等限制,因此基于学习的数据驱动型哈希算法被提了出来.基于学习的哈希算法一般会通过分析数据点之间的关系和性质来指导哈希方程的产生,进而获得投影向量对数据进行哈希映射,获得需要的哈希编码,主成分分析哈希算法PCAH[16](Principal Component Analysis Hash)通过主成分分析获得数据的主要成分,将主要成分作为投影向量产生哈希编码.

谱哈希算法SH[9](Spectral Hash)是比较常用的基于数据学习的哈希算法.它通过对原始数据集进行PCA降维获得相似图拉普拉斯矩阵的特征向量,然后对特征向量进行阈值化产生最后需要的二值编码,谱哈希可以较好地提升检索精度,但是谱哈希对多维数据的要求必须是均匀分布的,且不同维度上的哈希编码相互独立.

基于核的监督哈希KSH[17](Kernel-based Supervised Hash)使用带标签的数据进行学习得到哈希函数,将各数据再输入到各哈希函数中得到数据对应的哈希编码,实验表明该基于核的监督哈希算法在度量距离和语义相似的搜索中表现出良好的性能.相比小规模的低维数据,大规模高维数据本身会存在某些结构特性,所以基于学习的数据驱动型哈希技术可以较好地实现数据(图像,文本等)的快速检索.本文提出的在线密度敏感哈希算法,可以有效地处理动态数据,并通过数据之间的密度特性来指导哈希函数的生成,可以有效地解决普通哈希方法无法对数据库里中不断增加的数据以及新抓取的网页进行近邻搜索的问题.

3 在线密度敏感哈希

本节将对ODSH算法分为三小节进行详细阐述,首先给出在线k均值聚类算法的推导公式,然后描述投影向量的获取过程,最后根据信息熵值对获得的投影向量进行筛选.

3.1 在线k均值聚类

给出固定聚类个数的在线k均值聚类的调整公式:在某一段时间内,(t-1)和(t)表示时间的前后,N表示数据点的个数,K为固定好的分类结果组数.

(3)

(4)

(5)

下面列出时间(t)下的在线k均值聚类的误差平方和.

(6)

(7)

(8)

(9)

结合上式(7)(8)(9)可得公式(10)

(10)

公式(10)是在线更新的在线k均值聚类方程,通过它可以在不断有新的数据点加入到原数据集的时候,快速而准确地获得新的聚类结果.关于在线k均值聚类算法的组数k的确定将在实验部分给出.

3.2 投影向量的获取

经过在线k均值聚类获得不同时间下的k个聚类结果,表示为{S1,S2…,Sk},(k的数已经固定),然后根据聚类结果来指导投影向量的产生.首先定义一下需要的变量,聚类结果将使用[12]中的n-最近邻矩阵进行表示:

定义1.分类结果数据组的n最近邻矩阵M

Nn(μj)代表了中心点μj的n个最近中心点集合,继而得到n-相邻组对的定义.

定义2.n-相邻组对

当Mij=1的时候,组Si和组Sj为n-相邻组对.

通过上一步得到的n-相邻组对,下面通过这些相邻组对来生成对应的投影向量,根据3.1得到的动态kmeans量化结果,对于相邻组的表示点μi和μj,构建表示点的中垂面(假设三维空间,三维以上用超平面来表示)来对相邻组进行切分.根根据文献[12]的中垂面定义和公式(10)推导出动态超平面公式,见公式(11),公式等号左面的公式表示的是时间(t)下的超平面,等号右边为时间(t-1)下的超平面表示公式.

(11)

(12)

再根据超平面推得动态的哈希函数:

(13)

w(t)=w(t-1)+φ2

(14)

(15)

3.3 投影向量的筛选

4 实验结果

4.1 数据集

该实验使用以下三个公用数据集:

•Sift_128d数据集:该数据集是从ANN_SIFT1M中截取出来的,因受设备的限制,只使用其中的60000个sift特征,每个特征128维度.

•Gist_320d_CIFAR-10:CIFAR-10数据集是从Alex Krizhevsky等人收集的8千万小图片数据集中取到的子数据集,该数据集包含了60000个彩色图片的gist特征,维度为320维,数据集以及实验中对比的哈希算法相关代码可以在*https://github.com/willard-yuan/hashing-baseline-for-image-retrieval处下载.

•Gist_960d:该数据集从ANN_GIST1M中截取,同样含有60000个sift特征,维度为960维.ANN_SIFT1M和ANN_GIST1M可在*http://corpus-texmex.irisa.fr/处下载.

4.2 实验中对比的哈希算法

局部敏感哈希算法LSH[8]是通过生成大量的随机映射来生成哈希编码的哈希算法.

平移不变核哈希算法SKLSH[15](shift-invariant kernels Locality Sensitive Hash),它是LSH的一种改进算法.

主成分分析哈希算法PCAH[16]通过主成分分析来获得数据主要成分来指导投影向量的产生.

谱哈希SH[9],该算法基于上述的PCA哈希算法,对PCA后的特征向量进行阈值化产生最后需要的二值哈希编码.

主成分分析-随机旋转矩阵哈希算法[18]PCA-RR(Principal Component Analysis- Random Rotation),该算法在PCAH算法的基础上融入随机旋转矩阵,相比PCAH算法性能有较大提升.

在线密度敏感哈希算法ODSH(Online Density Sensitive Hash),这是本文提出的哈希算法.

4.3 实验设计与分析

首先对实验参数进行设置,哈希编码的位数l设置为ln=8,16,32,64,128位编码,通过不同的哈希编码位数来测试哈希算法的性能.

本文的在线k均值聚类算法需要预先固定好聚类的个数,k的值由哈希编码的位数决定,因为哈希编码的位数越大,需要的投影向量就越多,对应的超平面也越多,所以需要的数据组的个数也越多,所以组数k的个数与哈希编码的位数有关,故设置一个参数A来确定组数k,令k=A*ln,后续实验中,通过固定哈希编码的位数,以及固定的A和n-相邻组对中的参数n,会发现当A=2,n=3的时候,在各位哈希编码下在线密度敏感哈希算法的性能最好.下面会给出图示和分析.

为了更好地与其他的哈希算法对比,本文使用同样的数据集进行测试.针对本文提出的哈希算法,在程序中固定一部分数据集,然后通过迭代的方式将数据逐批次地导入到工作空间中,以此来实现数据的动态导入,根据每一批次数据导入后获得的聚类结果构建超平面,训练得到在线密度敏感哈希算法的哈希方程,求得投影向量和截距,最后获得多组投影向量和截距.使用同样的训练数据集获得其他哈希算法的哈希方程,通过投影向量获得测试和训练数据集对应的二值哈希编码,计算训练数据集与测试数据集之间的海明距离并排序,最后计算得到precision-recall值,以及平均准确率的平均值mAP(mean Average Precision),来衡量算法的性能.对本文提出的在线密度敏感哈希算法,根据多批次的结果计算得到多组precision-recall值和mAP值,取其平均值来与其他哈希算法进行对比.

4.3.1 参数选择

实验中使用mAP作为标准来进行参数的选择,将哈希编码长度设置为64位.首先将参数A固定,改变参数n的值来对本文的在线密度敏感哈希算法进行测试,并将数据可视化展现出来,然后再将参数n固定,改变参数A的值进行测试,结果如图1、图2所示.

图1 64位哈希编码:不同参数n下的mAP 图2 64位哈希编码:不同参数A 下的mAP

如图1所示,首先将参数A设置为2,固定不变,横坐标n为选取的相邻组参数,n从1到8取值,纵坐标为mAP的值.三条折线表示mAP在三个数据集下的变化.根据图示可以看出随着n-相邻组的参数n取3到6时,mAP是比较理想的,考虑到n的取值不需要太大,算法里的超平面只需要切割比较近的数据簇,因此选n=3作为后续的实验测试参数.

如图2所示,这里将参数n设置为3,参数A从1到3取值,从图2可以看出,三个数据集对应的三条折线,mAP的值在参数A=2时比较理想,在保证相对较高的准确度和较低的时间消耗情况下,选择A=2作为实验测试参数.

4.3.2 测试结果

图3到图5表示的是各哈希算法在三个数据集下,32位,64位,128位哈希编码的precision-recall曲线图,可以看出在不同维度的数据,不同位数的哈希编码下,本文提出的在线密度敏感哈希均具有较好的性能.

图6表示不同的哈希算法在三种数据集下,哈希编码从8位到128位的平均准确率的平均值,SKLSH和LSH属于非数据驱动型的哈希算法,可以看出他们在哈希编码位数较少的情况下性能较差,但随着哈希编码位数的增加,其准确率增长幅度较大.基于数据驱动型的哈希算法如SH随着哈希编码位数的准确率增长幅度相比LSH等算法较小,特别是PCAH算法随着哈希编码的位数增长性能反而下降了,其原因是PCAH算法里的主成分分析得到的数据主成分分布比较集中,只能在有限位数的哈希编码中起作用,随着哈希编码位数的增长,在后面的哈希编码中识别最近邻数据的性能会下降,PCA-RR算法引入了随机旋转矩阵,随着哈希编码位数的增加,平均准确率的增长比较明显.分析本文提出的ODSH算法在三个不同维度的数据集中的表现可以发现,在线密度敏感哈希算法在不同编码不同维度的性能都要好于上述哈希算法,也可以看出随着维度的增加,其平均准确率的平均值会更高一些,可以看出在线密度敏感哈希算法同样适合于高维数据的检索.

图3 Sift _128维数据集Fig.3 Sift_128 dimension data set

图4 Gist _320维数据集Fig.4 Gist _320 dimension data set

图5 Gist_960维数据集Fig.5 Gist_960 dimension data set

图6 三种数据集下的平均准确率的平均值Fig.6 Average of the average accuracy of the three datasets

5 结论与未来工作

本文提出的基于在线k均值聚类的密度敏感哈希算法可以较好地应对动态数据搜索的情况,可以解决普通哈希算法无法解决的在线学习问题,通过大量的实验对比,可以发现该算法具有较好的准确度和速度,但是该算法在超高维的数据下,比如说4096维度的数据下性能略低,故本文的下一步工作是对在线k均值聚类算法以及密度敏感哈希算法进行一系列参数优化,使其能更快速地对超高维数据进行处理,并在云平台上测试算法性能.

：

[1] Brin S.Near neighbor search in large metric spaces [C].Proceedings of the 21th International Conference on Very Large Data Bases,1996:574-584.

[2] Dasgupta S,Sinha K.Randomized partition trees for nearest neighbor search [J].Algorithmica,2015,72(1):237-263.

[3] Tao Y F,Papadias D,Shen Q M.Continuous nearest neighbor search [C].Proceedings of the 28th International Conference on Very Large Data Bases,2002:287-298.

[4] Indyk P,Motwani R.Approximate nearest neighbors:towards removing the curse of dimensionality [C].Proceedings of the 30th Annual ACM Symposium on Theory of Computing,2000:604-613.

[5] Zhang Xu,He Xiang-nan,Jin Che-qing,et al.Processing K-nearest neighbors query over uncertain graphs [J].Journal of Computer Research and Development,2011,48(10):1871-1878.

[6] Friedman J H.An Algorithm for finding best matches in logarithmic expected time [J].ACM Transactions on Mathematical Software,1977,3(3):209-226.

[7] Guttman A.R-trees:a dynamic index structure for spatial searching [C].Proceedings of the 10th ACM SIGMOD International Conference on Management of Data,ACM,1984:47-57.

[8] Datar M,Immorlica N,Indyk P,et al.Locality-sensitive hashing scheme based on P-stable distributions [C].Proceedings of the 20th Annual Symposium on Computational Geometry,ACM,2004:253-262.

[9] Weiss Y,Torralba A,Fergus R.Spectral hashing [C].Proceedings of the 21th International Conference on Neural Information Processing Systems,2008:1753-1760.

[10] Li Song,Zhang Li-ping,Hao Zhong-xiao.Strong neighborhood pair query in dynamic dataset [J].Journal of Computer Research and Development,2015,52(3):749-759.

[11] Liberty E,Sriharsha R,Sviridenko M.An algorithm for online K-means clustering [J].Computer Science,2014:81-89.

[12] Jin Z,Li C,Lin Y,et al.Density sensitive hashing [J].IEEE Transactions on Cybernetics,2014,44(8):1362-1371.

[13] Mairal J,Bach F,Ponce J,et al.Online learning for matrix factorization and sparse coding[J].Journal of Machine Learning Research,2010,11(1):19-60.

[14] Wang J,Kumar S,Chang S.Sequential projection learning for hashing with compact codes [C].Proceedings of the 27th International Conference on Machine Learning,2010:1127-1134.

[15] Raginsky M,Lazebnik S.Locality-sensitive binary codes from shift-invariant kernels [C].Proceedings of the 22th International Conference on Neural Information Processing Systems,2009:1509-1517.

[16] Zhou X,Huang Z,Ng WWY.Weighted grid principal component analysis hashing [C].Proceedings of the 13th International Conference on Machine Learning and Cybernetics,2015:200-205.

[17] Liu W,Wang J,Ji R,et al.Supervised hashing with kernels [C].Proceedings of the 25th International Conference on Computer Vision and Pattern Recognition,2012:2074-2081.

[18] Gong Y,Lazebnik S,Gordo A,et al.Iterative quantization:a procrustean approach to learning binary codes [C].Proceedings of the 24th International Conference on Computer Vision and Pattern Recognition,2011:817-824.

附中文参考文献：

[5] 张 旭,何向南,金澈清,等.面向不确定图的k最近邻查询[J].计算机研究与发展,2011,48(10):1871-1878.

[10] 李 松,张丽平,郝忠孝.动态数据集环境下的强邻近对查询[J].计算机研究与发展,2015,52(3):749-759.