提升近邻检索性能的二值编码算法

发布时间：2018-02-27 02:04

本文关键词： 近邻检索哈希算法二进制编码后验证距离表　出处：《吉林大学》2017年博士论文　论文类型：学位论文

【摘要】：近邻检索技术旨在返回与查询样本较相似的数据点,其在机器学习和计算机视觉领域中有着广泛的应用。近年来,随着网络技术的快速发展和多媒体设备的迅速普及,我们已经步入了多媒体大数据时代,并且多媒体特征一般为高维浮点型向量。因此,实时响应海量高维浮点向量的近邻检索请求,已经成为当前学术界和商业界的热点问题。哈希算法可将高维浮点型向量表示成紧凑二进制编码,并根据汉明距离关系查询近邻点。二进制编码所占用的存储空间较少,并且汉明距离的计算复杂度较低。因此,在海量数据库中,可采用基于二值编码的近邻检索算法快速得到近邻样本。然而,有限长度的二进制编码的区分性较弱,并且一些哈希算法自身也存在一些问题,使得在汉明空间内得到的近邻检索结果与原空间内的近邻检索结果之间存在偏差,而且这些问题还没有得到很好的解决。本论文从基于二值编码的近邻检索的不同阶段,探索提升近邻检索性能的方案,并力求两个空间内的检索结果之间具有较高的一致性。近邻检索一般包含初始检索阶段和后验证两个过程。在初始检索阶段中,决定近邻检索结果的主要因素是数据集的二进制编码,其与相似性保持目标函数以及算法的收敛情况相关。在后验证阶段中,近邻检索性能的提升幅度取决于距离表的区分性。本文以上述研究方向为切入点,探索如何快速获取具有较优近邻检索性能的二进制编码,以及如何在后验证阶段中进一步提升近邻检索性能。本文中的主要研究内容和创新成果如下:1.提出了归一化距离相似性保持哈希算法,通过最小化数据点对在两种不同空间内的归一化距离差别来保证数据点对在不同空间内拥有相近的相似度。为了能够通过比较数据点对在不同空间内的距离值来判断它们是否具有相同的相似度,本文采用了归一化处理,使得数据点对在不同空间内拥有相同的距离取值范围,而且这一做法能够避免距离比例参数的引入。当训练数据集或目标编码长度发生变化时,无需人为交叉验证使得算法性能最优的距离比例参数,有效降低了算法的训练复杂度,算法性能相对稳定。算法的原目标函数中包含数据点的二值编码过程,其为离散型函数,直接优化该目标函数较困难。为此,本文采用S型符号函数松弛处理二值编码过程,使得目标函数连续化。当训练数据集为海量数据库时,本文采用随机批量梯度下降算法优化目标函数,使得算法能够快速收敛。2.提出了排序一致性哈希算法,在欧式空间和汉明空间内,分别根据数据点对的不同种类的距离值对其排序,并要求两种不同排序之间的区别最小,符合近邻检索的本质要求,属于相对相似性保持哈希算法。同时,还引入了量化误差,要求被映射为相同编码的数据点在原空间内互为近邻关系,从而保证所生成的二进制编码符合空间分布特性。在训练阶段中,学习同时满足上述两种约束条件的编码中心点时,本文分别探索利用分层编码机制和子空间划分方法降低训练时间复杂度。根据所生成的编码中心点,可采用基于查找的方式编码新数据点,但其编码时间复杂度较高,不适应于海量数据库。为此,本文构建了类似于两步机制的算法框架,监督学习线性哈希映射函数,使得编码时间复杂度从指数级降为线性级。本文中的强哈希映射函数是由自适应提升算法组合多个弱哈希函数形成的,能够最大程度地保留数据点之间的原始局部敏感信息。3.提出了适应空间分布的多重编码算法和距离表。哈希算法学习数据集的二进制编码时,常采用梯度下降算法优化目标函数。但梯度下降算法具有局部最优性,若目标编码长度有限,数据点在汉明空间内的区分性较弱。为了解决上述问题,本文提出自适应多重编码算法,根据数据集的空间分布和目标编码长度,采用经验学习算法,自适应生成一组或多组数据点作为初始输入,从而保证算法能够快速得到完备解。多重编码算法将数据点映射成多重二进制编码,并根据平均汉明距离返回初始近邻检索结果。在汉明空间内的近邻查询结果中存在许多与查询数据点共享相同汉明距离的数据点,但它们与查询数据点在原空间内的相似度是不同的。为了进一步区分拥有相同汉明距离的数据点对之间的相似度,本文建立了适应空间分布特性的距离表。一般距离表将拥有相同编码的数据点的坐标均值作为中心点,若编码长度有限,多个聚类数据集可能共享相同的中心点,使得中心点之间的距离值不能精确表达数据点之间的相似关系。本文根据数据集的空间密度分布,自适应学习符合聚类分布特性的中心点,并且中心点的数量与编码长度无关,也不同于K均值聚类算法,不需要人为确定聚类数量。本文将不同中心点之间的距离值,按照中心点的二值索引存入到不同的位置中,从而得到区分性较强的距离表。若编码长度较短,编码种类数将少于中心点数,将有多个中心点对共享相同的二值索引,它们之间的距离值会被存储在距离表中的相同位置。但是,多个中心点对拥有相同的多重索引的概率较小。在后验证阶段中,可根据数据点对的多重索引从距离表中得到多个距离集合,并通过计算它们之间的交集来确定最终距离值。在本文中,根据数据点之间的汉明距离得到初始检索结果之后,将根据适应空间分布特性的距离表,重新判断拥有相同汉明距离的数据点对之间的相对相似性,并对它们重新排序,从而进一步提升近邻检索性能。
[Abstract]:In recent years , with the rapid development of network technology and the rapid popularization of multimedia devices , we have entered the multi - media data era . In order to solve the above - mentioned problems , this paper proposes an adaptive multi - coding algorithm , which is based on the spatial distribution of the data set and the length of the target .

【学位授予单位】：吉林大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：TP391.41

【相似文献】