基于哈希的最近邻查找

发布时间：2017-05-06 16:04

  本文关键词：基于哈希的最近邻查找，由笔耕文化传播整理发布。

【摘要】：最近邻查找是计算机视觉和机器学习领域中的一个重要的基础性问题。近年来,基于哈希的算法在处理最近邻查找的问题上,引起了很大的关注。其基本思想是用紧凑的二值码表示高维数据点,并且用二值码之间的相似性近似数据点之间在原空间的相似性。二值码表示具有存储消耗低和计算速度快的优点,故而哈希的方法在大规模数据环境下具有很广的应用前景。 尽管哈希方法有存储和计算上的优势,但是依据二值码排序的结果依然存在着一定的误差。这样的误差目前并没有得到很好地解决,故而本论文主要从多个方面提升哈希方法在最近邻查找中的准确性。 一般而言,基于哈希的最近邻查找的方法包括两个阶段。第一个是哈希映射,用于将数据点映射为二值码；第二个是针对二值码设计近似距离从而进行排序。为了提升基于哈希的最近邻查找的准确性,本文主要从这两个方面研究如何获得更优质的二值码和更准确的度量距离。 本文主要研究内容和创新成果如下： 1.提出序列保持哈希算法。该算法通过最大化原空间排序结果和汉明空间排序结果之间的一致性学习哈希映射,从而提升基于汉明距离的哈希映射在最近邻查找的准确性。数据点根据与查询点之间的汉明距离分成不同的类别,从而可以将排序问题建模成分类问题。哈希函数通过最小化在所有训练数据点上面的分类损失而得。该方法直接最大化最近邻查找最关注的排序的一致性,大量的与已有基于汉明距离的哈希方法的对比实验结果表明,序列保持哈希可以在相同的查找时间内取得更高的排序准确率。 2.提出优化的笛卡尔K均值算法。该算法用于提升基于空间量化的哈希映射在最近邻查找的准确率。传统的方法中,码本是多个子码本的笛卡尔乘积;而本文提出的方法采用多个这样的码本联合对数据进行编码。每一个数据点用多个码字的和近似,而每一个码字来自不同的码本。码本通过最小化失真误差优化而得。这样简单有效的策略不仅在实验中同时也在理论上保证了更低的失真误差,从而提升了排序的准确性。 3.提出二值码距离优化的算法。该算法用于在二值码给定的情况下,通过距离优化的方式提升最近邻查找的准确率。具体而言,由于二值码取值范围的有限性,本文通过一个非参数的查询表存储查询点到每一个二值码之间的距离。为了解决可能带来的存储空间大的问题,本文将二值码分成多个子码,每一个子码生成一个与查询相关的较小的距离查询表,近似距离定义为多个子表对应的表项的和。查询表中的元素值通过最小化近似距离和原真实距离的误差而得。该思想成功应用到对称的二值码之间的距离以及非对称的查询点与数据库二值码之间的距离中。由于理论上保证了更准确的近似距离,大量的实验表明了对距离的优化可以很大幅度提升基于哈希的最近邻查找的准确率。 综上,本文从如何获得二值码以及如何设计针对二值码距离两个方面,提出三个新颖算法,用于提升基于哈希的最近邻查找的准确性。理论证明和大量实验结果表明了所提出方法相对于已有方法的优越性。
【关键词】：最近邻查找 哈希映射 序列保持哈希 优化的笛卡尔K均值 距离优化
【学位授予单位】：中国科学技术大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP391.41;TP181
【目录】：

• 摘要5-7
• ABSTRACT7-9
• 目录9-12
• 表格索引12-13
• 插图索引13-14
• 算法索引14-15
• 第一章 绪论15-23
• 1.1 研究背景和意义15-16
• 1.2 技术概述和研究现状16-18
• 1.2.1 树形结构16
• 1.2.2 哈希方法16-18
• 1.3 基于哈希的最近邻查找的关键问题18-19
• 1.3.1 高维数据如何映射成二值码18-19
• 1.3.2 二值码之间的距离如何衡量19
• 1.3.3 如何对二值码数据进行排序19
• 1.3.4 本论文关注的研究问题19
• 1.4 研究内容和创新点19-21
• 1.4.1 序列保持哈希20
• 1.4.2 优化的笛卡尔K均值20
• 1.4.3 二值检索中的距离优化20-21
• 1.5 论文组织结构21-23
• 第二章 序列保持哈希23-43
• 2.1 引言23-24
• 2.2 相关工作24-26
• 2.2.1 概率性相似度保持24-25
• 2.2.2 确定性相似性保持25-26
• 2.3 序列保持哈希26-27
• 2.4 目标优化27-30
• 2.4.1 函数松弛28-29
• 2.4.2 二次惩罚29-30
• 2.5 联系与讨论30-31
• 2.6 实验验证31-41
• 2.6.1 实验设置31-32
• 2.6.2 代码实现32-33
• 2.6.3 实验结果33-41
• 2.7 本章总结41-43
• 第三章 优化的笛卡尔K均值43-67
• 3.1 引言43-44
• 3.2 相关工作44-47
• 3.2.1 汉明投影44-45
• 3.2.2 空间量化45-47
• 3.3 扩展的笛卡尔K均值47-49
• 3.3.1 参数学习48-49
• 3.4 优化的笛卡尔K均值49-54
• 3.4.1 参数学习50-54
• 3.5 算法讨论54-60
• 3.5.1 与相关工作的联系54-56
• 3.5.2 不等式约束与等式约束56-57
• 3.5.3 代码实现57-58
• 3.5.4 最近邻检索中的距离近似58-60
• 3.6 实验验证60-66
• 3.6.1 实验设置60-62
• 3.6.2 实验结果62-66
• 3.7 本章总结66-67
• 第四章 二值检索中的距离优化67-91
• 4.1 引言67-68
• 4.2 相关工作68-69
• 4.2.1 二值码排序68-69
• 4.3 方法概述69-72
• 4.4 优化的对称距离72-76
• 4.4.1 目标问题73
• 4.4.2 参数优化73-76
• 4.5 优化的非对称距离76-78
• 4.5.1 目标问题76-77
• 4.5.2 参数优化77-78
• 4.6 算法讨论78-83
• 4.6.1 分段个数78-81
• 4.6.2 与相关工作的联系81-83
• 4.7 实验验证83-88
• 4.7.1 实验设置83-85
• 4.7.2 实验结果85-87
• 4.7.3 分段个数对性能的影响87-88
• 4.8 本章总结88-91
• 第五章 总结和展望91-93
• 5.1 总结91
• 5.2 展望91-93
• 参考文献93-99
• 致谢99-101
• 在读期间发表的学术论文与取得的研究成果10

【相似文献】

中国期刊全文数据库 前10条

1 周屹;杨泽雪;邢传军;曲天伟;;一种连续最近邻查询的优化方法[J];黑龙江工程学院学报(自然科学版);2013年04期

2 张奋;黄铁;潘梅森;;不同维数下空间对象的反最近邻查询[J];湖南城市学院学报(自然科学版);2007年01期

3 李松;郝忠孝;;球面上最近邻空间关系处理方法[J];计算机工程;2010年06期

4 王恒;;路网中基于预计算的跳跃式查询最近邻的算法[J];天津理工大学学报;2011年02期

5 闵寻优;郝忠孝;;三维空间中的连续最近邻查询[J];软件;2011年02期

6 刘彬;王建国;;范围最近邻查询方法研究[J];泰山学院学报;2011年03期

7 李进;余建桥;;空间对象的反最近邻查询处理技术研究[J];计算机工程与应用;2011年33期

8 刘艳;郝忠孝;;高维主存的反向K最近邻查询及连接[J];计算机工程;2011年24期

9 杨泽雪;郝忠孝;;空间数据库中连续可视反向最近邻查询[J];西南交通大学学报;2012年03期

10 吴昊;;最近邻分类的改良模型[J];广西大学学报(自然科学版);2012年06期

中国重要会议论文全文数据库 前10条

1 张晓峰;王丽珍;肖清;赵丽红;;基于概念划分的连续最近邻查询研究[A];NDBC2010第27届中国数据库学术会议论文集(B辑)[C];2010年

2 管猛;张剡;柏文阳;;基于地表的连续可见最近邻查询方法[A];NDBC2010第27届中国数据库学术会议论文集(B辑)[C];2010年

3 陈璐;高云君;柳晴;陈刚;;受限相互最近邻查询处理[A];第29届中国数据库学术会议论文集（B辑）（NDBC2012）[C];2012年

4 盛梅红;沙朝锋;宫学庆;嵇晓;周傲英;;道路网络环境中的多对象最近邻查询[A];第二十三届中国数据库学术会议论文集（研究报告篇）[C];2006年

5 刘月清;章勇;;一种改进的动态最近邻聚类算法[A];全国自动化新技术学术交流会会议论文集（一）[C];2005年

6 李传文;谷峪;李芳芳;于戈;;一种障碍空间中不确定对象的连续最近邻查询方法[A];NDBC2010第27届中国数据库学术会议论文集A辑一[C];2010年

7 刘星毅;;基于欧式距离的最近邻改进算法[A];广西计算机学会2010年学术年会论文集[C];2010年

8 刘先康;梁菁;任杰;蒋光庆;;修正最近邻模糊分类算法在舰船目标识别中的应用[A];全国第4届信号和智能信息处理与应用学术会议论文集[C];2010年

9 刘俊岭;孙焕良;;多维度量空间中发现相互kNN(英文)[A];NDBC2010第27届中国数据库学术会议论文集A辑二[C];2010年

10 余小高;;P2P环境中k最近邻搜索算法研究[A];2009年全国开放式分布与并行计算机学术会议论文集(下册)[C];2009年

中国博士学位论文全文数据库 前7条

1 杨泽雪;空间连接及最近邻变体查询研究[D];哈尔滨理工大学;2014年

2 孙冬璞;时空数据库多类型最近邻查询的研究[D];哈尔滨理工大学;2010年

3 王建峰;基于哈希的最近邻查找[D];中国科学技术大学;2015年

4 张得天;时间依赖路网高效k最近邻查询混搭机制的研究[D];中国科学技术大学;2014年

5 杜钦生;高维空间的K最近邻查询及连接问题研究[D];吉林大学;2015年

6 张军旗;支持最近邻查找的高维空间索引[D];复旦大学;2007年

7 李艳红;路网中移动对象最近邻及反向最近邻查询处理研究[D];华中科技大学;2011年

中国硕士学位论文全文数据库 前10条

1 韩冬柏;基于R-树的最近邻查询研究[D];哈尔滨理工大学;2011年

2 王恒;基于路网的最近邻查询方法的研究[D];天津理工大学;2012年

3 宋娜;连续可视最近邻查询研究[D];哈尔滨理工大学;2014年

4 赵海宇;连续最近邻查询研究[D];哈尔滨理工大学;2014年

5 郭小发;空间对象的连续可视最近邻查询处理研究[D];浙江大学;2008年

6 曾令智;多类型反向最近邻查询的研究[D];广西大学;2013年

7 张佳佳;最近邻查询和反最近邻查询算法研究[D];哈尔滨理工大学;2009年

8 朱曼龙;最近邻方法在填充和分类中应用的新技术[D];广西师范大学;2010年

9 张晓峰;一种基于概念划分的不确定连续最近邻查询[D];云南大学;2010年

10 喻荣超;最近邻搜索方法在大可视目标识别中的应用[D];电子科技大学;2013年

  本文关键词：基于哈希的最近邻查找，，由笔耕文化传播整理发布。

本文编号：348686