一种相似性保持的线性嵌入哈希方法

王秀美，丁利杰，高新波

（西安电子科技大学电子工程学院，陕西西安 710071）

一种相似性保持的线性嵌入哈希方法

王秀美，丁利杰，高新波

（西安电子科技大学电子工程学院，陕西西安 710071）

在图像检索技术中，针对高维特性海量的图像数据检索速度慢、数据存储容量大及图像和其哈希编码之间相关性差的缺点，将相关性预测函数引入到哈希算法中，提出了一种相似性保持的线性嵌入哈希方法.该方法利用相关性预测函数保持高维数据与其编码之间的邻近关系，使边界损失代价最小化，构建线性哈希映射矩阵，获得紧致的哈希编码，提高了图像与编码间的相关性，实现了高精度的图像检索.通过与现存经典的哈希算法相对比，实验结果验证了线性嵌入哈希方法在查全率和查准率上的有效性.

相似最近邻搜索；哈希；相关性预测函数；查准率；查全率

近年来，随着互联网、云计算、移动设备和物联网的迅猛发展，全球数据量进入ZB时代，并且每年仍以指数级形式增长.如何高效收集、存储、分析处理、可视化展示并利用大数据获得效益成为现今的热点研究问题.在大数据处理检索技术中，相似最近邻搜索技术［1］被广泛应用，如基于内容的图像检索、目标识别以及分类等.

一些经典的哈希方法已经被提出用于相似最近邻搜索和图像查询.最早提出的较为经典的哈希算法是局部敏感哈希算法（Locality-Sensitive Hashing，LSH）［3］，该方法是对图像数据进行随机映射来构建随机哈希函数，可以使得相似的图像数据映射后的编码有较高的几率落在同一哈希桶中.但是这种方法需要长编码来保持数据的相似性.之后一系列基于学习的哈希方法被提出来，如基于图构建获得哈希函数的方法——有谱哈希（Spectral Hashing，SH）［2］，它是通过无向图构建获得图像数据之间相似度关系，最终通过谱图理论求解相似度矩阵特征值与特征函数问题获得哈希函数.另外，基于主成分分析方法的哈希算法［4］和迭代量化哈希算法（ITerative Quantization，ITQ）［5］是通过学习，不断地减少量化误差得到哈希函数.最近，积量化方法被应用到哈希中.如文献［6］提出一种将高维空间数据分解到低维空间，通过最小化与空间分解和码书相关的量化失真，获得有效的哈希编码.文献［7］使用K均值［8-9］量化分离的特征空间获得每个簇的标识索引，通过计算索引的汉明距离来估计原始空间的欧式距离.积量化用于哈希虽然能够得到有效的检索性能，但是优化过程困难.为了保持输入数据之间的局部结构，文献［10］提出了一种非参数流形学习的非线性嵌入方法，通过数据流形间的几何结构获得紧致的哈希代码.为了利用类标信息或数据间的相似度提高检索精度，人们提出了基于核函数的哈希方法（Supervised Hashing with Kernels，KSH）［11］.基于核的哈希方法是利用在优化代码内积和汉明距离的等值性来优化哈希函数.为了处理监督信息不足的问题，半监督学习技术被引入到哈希算法中，半监督哈希算法（Semi-Supervised Hashing，SSH）［12］通过最小化有标签数据和无标签数据的经验损失正则项优化哈希函数.

一方面，监督信息是非常有限的；另一方面，监督信息的获取需要大量的人力物力.因此，无监督哈希方法越来越受到人们的重视.但一些现存的无监督哈希方法都是在一定的限制条件下优化目标函数，限制条件势必使得哈希方法的普及性和性能受到影响.如基于图构建的无监督哈希方法［2］是假设数据分布或近邻结构已知条件下获得目标函数的近似结果.另外，很多无监督哈希方法不适应长哈希码情况，如基于主成分分析方法的哈希算法（Principal Component Analysis Hashing，PCAH）和迭代量化哈希算法的查准率和查全率随着哈希码长度增加而变化不明显.针对以上的问题，笔者提出一种线性无监督哈希方法，该算法在实现中没有过多条件限制.而且它是基于线性嵌入模型，通过该模型能够获得图像数据与其对应哈希码的相关性表征，展示图像数据与哈希码之间的内在联系.用这种相关性联系去学习哈希函数，能使得该算法性能随着哈希码位数提高而变优.

1 线性嵌入哈希

假设给定一个包含n个d维数据点的数据集X=［x1，x2，…，xn］∈Rd×n，yi∈｛1，-1｝c，i=1，2，…，n，表示高维图像数据xi所对应的哈希码，设哈希映射函数H（x）=｛hk（x）｝ck=1，并且获得哈希码表Y=［y1，y2，…，yn］∈｛1，-1｝c×n，能够保存数据的相似度信息，其中c为哈希码的长度.哈希函数通过阈值化得到，即对于每一位哈希码，哈希编码函数被定义为

其中，wk是超平面参数的列向量，W∈Rc×n，W是列向量wk组成的矩阵.阈值化编码一般是通过符号函数y（x）=sgn（v）（如果v＞0，那么，y=1；否则，y=-1）获得，那么整个训练数据的编码过程为Y= sgn（WX）.

为了表征图像数据与编码的相关性关系，受文献［13］启发，提出相关性预测函数模型，即

该函数返回一个可以估计图像数据x与编码b1之间相关性的值.假设图像数据x与编码串b1之间的相关性高于图像数据x与编码串b2之间的相关性，那么得到的相关性预测函数值f（x，b1）＞f（x，b2）.

线性嵌入哈希算法没有任何监督信息，为获得预设的哈希编码，首先运用K均值聚类，得到k个聚类中心C=［c1，c2，…，ck］T∈Rk×d，然后，把初始的模型参数矩阵与聚类中心的乘积φi（C，W）=CW进行阈值化处理得到预设编码B=［b1，b2，…，bk］T∈Rk×c.预设编码列bi∈｛1，-1｝c，i=1，2，…，k的第i编码行的第j个元素bij为1时，对应的φij必为正数；反之，bij为-1时，对应的φij必为负数.从而可得某一图像数据x和其相关的预设编码b1所对应的相关性预测函数的返回值高，图像数据x和其不相关的预设编码b2之间的相关性预测函数的返回值小.进而保证在原始空间中相近的图像数据点映射到汉明空间后所对应的汉明距离接近.

对于通过式（2）去学习最优的权重W，为了保证相关对（x，b1）的相关性大于不相关对（x，b2）的相关性，即要使得x W（b1）T＞x W（b2）T，引入边界损失函数，即

其中，γ≥0是测试函数边界，Bx表示图像数据x的相关预设编码集.分析上式可知，只有满足条件x Wbj＞γ+x Wbk时，才能使得某一图像数据x与它的相关预设编码和不相关预设编码之间的边界损失为0，进而保证最终边界损失函数达到最小.在边界损失函数达到最小时，同时保证了相关对（x，bj）之间的相关性高于不相关对（x，bk）之间的相关性.运用梯度下降算法去优化边界损失函数，在每次迭代中，随机选择一个图像数据相关对，然后对此图像数据不相关点去做一次梯度分析.在训练线性嵌入模型时，选择最小化训练误差的固定学习步长为λ，用N（0，1）高斯分布初始化训练模型参数W.

线性嵌入哈希算法步骤如下:

输入:一个训练样本集X=｛xi∈Rd｝in=1，哈希编码位数为c，聚类数目k.

初始化:模型参数W（用均值为0、方差为1的高斯分布），损失函数边界γ，随机梯度下降学习步长λ，循环迭代次数N.

第1步 K均值聚类.对训练样本数据集进行K均值聚类，得到样本数据集的k个聚类中心，并存储每个簇中各样本对应类别标号.

第二，基准站。基准站的作用是完成了数据的接收、处理和生成这些流程，对于后续工作起到推进的作用。与此同时，还能减少工作人员获取到控制点时的处理难度，基准站可以直接记录点位数据，避免了人工操作可能出现的失误。另外，在实际应用中，人们可以利用伪距差分技术导航位点数据，且极为精准，一般误差不超过五米。[1]同时，测绘更新的时效性也给人们的出行定位带来了便利，工作人员可以在一定的时间范围内将测得的数据信息上传，经过整合处理后生成三维坐标，相比于传统的测绘技术耗时少且流程简单。

第2步 线性映射得到预设码表.对所得到的k个聚类中心线性映射到低维的汉明空间，得到聚类中心所对应的预设码表，并且把预设码表中的每一个码行作为所对应类中各样本的正项预设编码，其他码行则作为这个类中各样本的负项预设编码.

第3步 模型训练过程.步骤如下:

FOR i=1 to N

（1）在训练样本集中随机选择一个样本图像数据x，对于样本数据x，找到它所对应的类别标号，并通过类别标号，选择它对应的正项b1∈Bx；

（2）通过式（2），计算样本图像数据x与其对应的正项b1之间的相关性预测数f（x，b1）；

（4）如果f（x，b1）＜f（x，b2）+γ，那么运用随机梯度下降方法进行一次梯度步骤最小化边界损失函数: max（0，γ+f（x，b2）-f（x，b1）），去优化模型参数W，然后，继续跳到步骤（1），进行迭代循环.

END FOR

第4步 阈值化编码.模型训练后得到最优的模型参数W，然后通过式（1），将训练样本进行阈值化得到哈希编码codec（xi）←［h1（xi），…，hc（xi）］.

输出:n个哈希编码H=｛codec（xi）｝in=1.

2 实验结果与分析

测试提出的线性嵌入哈希（Linear Embedded Hashing，LEH）算法对相似最近邻查询的有效性，在Label Me和CIFAR10两个图像数据库上进行评估.CIFAR10数据库是8千万个小图像的子集，它包含60 000个32×32彩色图像，总共分为10类，每类有6 000个图像样本.Label Me数据库是多标签数据库，包含22 000个图像，在数据库中，每个图像都是由一个512维的GIST特征矢量所代表.

对比线性嵌入哈希算法，使用了现今比较成熟的无监督哈希方法.它们分别是谱哈希方法、平移不变核局部敏感哈希方法［14］、迭代量化、基于主成分分析的哈希方法.

实验过程中，从CIFAR10、Label Me两个数据集中选择5 000个数据点，并把每个数据集分为两部分，4 000数据点作为训练集，另外1 000数据点作为测试集.画出数据点检索的查准率-查全率曲线和平均准确率曲线（MAP）等分别去评估图像检索性能.其中，查准率为在某具体汉明距离中查询到的与查询点相关的图像数据个数和此汉明距离中所有的图像数据点个数之比.查全率为在某具体汉明距离中查询到的与查询点相关的图像数据个数和整个数据集中与查询点相关的全部图像数据个数之比.

2.1LabelMe实验结果

在Label Me数据集上得到的实验结果曲线如图1所示，图1（a）和图1（b）为Label Me数据库下各哈希函数在哈希码为32位、64位下查准率-查全率曲线.从图中可知，线性嵌入哈希方法（LEH）的查准率-查全率比迭代量化（ITQ）增加将近18%.并且谱哈希（SH）、迭代量化（ITQ）、PCAH这3种哈希方法查准率-查全率随哈希编码长度变化不明显.平移不变核局部敏感哈希方法（SKLSH）的查准率-查全率随着哈希编码长度变长而变的更优，但仍低于迭代量化（ITQ）.图1（c）为平均准确率曲线，从图中可知，一定的哈希码长度范围，线性嵌入哈希方法（LEH）的平均准确率（MAP）优于其他哈希方法的，并且平均准确率随位数的增加而增加.

图1　Label Me结果曲线

2.2ClFAR10实验结果

图2为CIFAR10数据库下各哈希函数分别在48位、64位下查准率-查全率曲线和平均准确率曲线.由图2可看到，线性嵌入哈希方法在各哈希代码长度下的查准率-查全率优于其他所有的哈希方法.在高于一定的哈希码位数下，平均准确率（MAP）优于其他哈希方法的，并且平均准确率随位数的增加而增加.另外，对于谱哈希、迭代量化、PCAH这3种哈希方法性能随哈希编码长度变化性不明显.平移不变核局部敏感哈希方法和线性嵌入哈希方法的性能随着哈希编码长度变长而变的更优.但是平移不变核局部敏感哈希方法在代码很长时性能仍旧低于迭代量化，所以，这种方法如果要达到好的精确度必须增加哈希代码长度，增加代码长度会造成存储空间的增大与查全率的下降.对于线性嵌入哈希方法，在较短的哈希码长度下，已经达到比较好地效果.

图2　CIFAR10结果曲线图

3 结束语

笔者提出了一种相似性保持的线性嵌入哈希方法，并对其基本思想、实现步骤进行了叙述和分析.在不同数据集上的实验结果显示，线性嵌入哈希方法的性能随着哈希码的长度增加而变优.在哈希码高于一定长度，线性嵌入哈希方法的性能优于现存的经典的无监督哈希算法的性能.但是该方法在较短的哈希码长度内，其性能达不到理想的效果，这是由于初始化过程中预设编码无法充分表征原始图像数据间的相似性关系所致.该方法对于大代码长度图像检索问题是有效的，并提供了一种解决相似最近邻搜索问题的实用而有效的方案.

［1］INDYK P，MOTWANI R.Approximate Nearest Neighbors:Towards Removing The Curse Of Dimensionality［C］// Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing.New York:ACM，1998:604-613.

［2］WEISS Y，TORRALBA A，FERGUS R.Spectral Hashing［C］//Proceedings of the Conference on Advances in Neural Information Processing Systems.New York:NIPS，2009:1753-1760.

［3］DATAR M，IMMORLICA N，INDYK P，et al.Locality-sensitive Hashing Scheme Based on p-stable Distributions ［C］//Proceedings of the Twentieth Annual Symposium On Computational Geometry.New York:ACM，2004:253-262.

［4］WANG X J，ZHANG L，JING F，et al.Annosearch:Image Auto-annotation by Search［C］//Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Washington:IEEE Computer Society，2006: 1483-1490.

［5］GONG Y，LAZEBNIK S.Iterative Quantization:a Procrustean Approach to Learning Binary Codes［C］//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Washington:IEEE Computer Society，2011:817-824.

［6］GE T，HE K，KE Q，et al.Optimized Product Quantization for Approximate Nearest Neighbor Search［C］// Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Washington:IEEE Computer Society，2013:2946-2953.

［7］HE K，WEN F，SUN J.K-means Hashing:an Affinity-preserving Quantization Method for Learning Binary Compact Codes［C］//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Washington:IEEE Computer Society，2013:2938-2945.

［8］HARRINGTON P.机器学习实战［M］.李锐，李鹏，曲亚东，译.北京:人民邮电出版社，2013:184-199.

［9］伍忠东，高新波，谢维信.基于核方法的模糊聚类方法［J］.西安电子科技大学学报，2004，31（4）:533-537. WU Zhongdong，GAO Xinbo，XIE Weixin.A Study of a New Fuzzy Clustering Algorithm Based on the Kernel Method ［J］.Journal of Xidian University，2004，31（4）:533-537.

［10］SHEN F，SHEN C，SHI Q，et al.Inductive Hashing on Manifolds［C］//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Washington:IEEE Computer Society，2013:1562-1569.

［11］WANG J，KUMAR S，CHANG S F.Semi-supervised Hashing for Large-scale Search［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，34（12）:2393-2406.

［12］LIU W，WANG J，JI R，et al.Supervised Hashing with Kernels［C］//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Washington:IEEE Computer Society，2012:2074-2081.

［13］WESTON J，WEISS R，YEE H.Affinity Weighted Embedding［C］//Proceedings of the International Conference on Machine Learning.Washington:International Machine Learning Society，2014:2958-2966.

［14］RAGINSKY M，LAZEBNIK S.Locality-sensitive Binary Codes from Shift-invariant Kernels［C］//Proceedings of the Conference on Advances in Neural Information Processing Systems.New York:NIPS，2009:1509-1517.

（编辑:王 瑞）

Linear embedding Hashing method in preserving similarity

WANG Xiumei，DING Lijie，GAO Xinbo
（School of Electronic Engineering，Xidian Univ.，Xi’an 710071，China）

In order to implement quick and effective search，save the storage space and improve the poor performance of affinity relationshaps between high dimensional data and its codes in image retrieval，a new linear embedding hashing is proposed by introducing the preserving similarity.First，the whole data set is clustered into several classes，and then the similarity predicted function is used to maintain affinity relationships between high dimensional data and its codes so as to establish the objective function.By minimizing the margin loss function，the optimal embedded matrix can be obtained.Compared with the existing classic hashing algorithm，experimental results show that the performance of the linear embedding hash algorithm is superior to the other binary encoding strategy on precision and recall.

approximate nearest neighbor search；hashing；similarity predicted function；precision；recall

TP391

A

1001-2400（2016）01-0094-05

10.3969/j.issn.1001-2400.2016.01.017

2014-09-26 网络出版时间：2015-04-14

国家杰出青年科学基金资助项目（61125204）；国家自然科学基金重点资助项目（61432014）；国家自然科学基金资助项目（6147230）；国家自然科学基金青年基金资助项目（61100158）

王秀美（1978-），女，副教授，博士，E-mail:wangxm@xidian.edu.cn.

网络出版地址：http://www.cnki.net/kcms/detail/61.1076.TN.20150414.2046.014.html