基于哈希的最近邻查找.pdf

《基于哈希的最近邻查找.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、UniversityofScienceandTechnologyofChina博士学位论义论文题目基于合希的最改邻去我作者姓名王抖学科专业信号与导师姓名二〇一五年六月完成时间中神§雀本大篸博士学位论文基于哈希的最近邻查找作者姓名：王建峰学科专业信号与信息处理导师姓名：李世鹏教授俞能海教授完成时间：二零一五年六月UniversityofScienceandTechnologyofChinaAdissertationfordoctor'sdegreeandHashing-basedNearestNeighborS

2、earchAuthor:JianfengWangSpeciality:SignalandInformationProcessingSupervisor:Prof.ShipengLiProf.NenghaiYuFinishedTime:June,2015中国科学技术大学学位论文原创性声明本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人己经发表或撰过的研宂成。上我同：；作的志对木研允所做的丑献均已在论文屮作丫叨确的说。作者签名签宁中国科学技

3、术大学学位论文授权使用声明作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技木大学拥有学位论文的部分使用权，卩：学校有权按有关规定向国家有关部门或机构送交论文的复印件和电子版，允许论文被査阅和借阅，可以将学位论文编入《中国学位论文全文数据库》等有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相一致。保密的学位论文在解密后也遵守此规定。“开口保密年作者签名：导师签名签字日期：签字曰期摘要摘要最近邻查找是计算机视觉和机器学习领域中的一个重要

4、的基础性问题。近年来，基于哈希的算法在处理最近邻查找的问题上，引起了很大的关注。其基本思想是用紧凑的二值码表示高维数据点，并且用二值码之间的相似性近似数据点之间在原空间的相似性。二值码表示具有存储消耗低和计算速度快的优点，故而哈希的方法在大规模数据环境下具有很广的应用前景。尽管哈希方法有存储和计算上的优势，但是依据二值码排序的结果依然存在着一定的误差。这样的误差目前并没有得到很好地解决，故而本论文主要从多个方面提升哈希方法在最近邻查找中的准确性。一般而言，基于哈希的最近邻查找的方法包括两个阶段。第一个是哈希映

5、射，用于将数据点映射为二值码；第二个是针对二值码设计近似距离从而进行排序。为了提升基于哈希的最近邻查找的准确性，本文主要从这两个方面研宄如何获得更优质的二值码和更准确的度量距离。本文主要研宄内容和创新成果如下：提出序列保持哈希算法。该算法通过最大化原空间排序结果和汉明空间排序结果之间的一致性学习哈希映射，从而提升基于汉明距离的哈希映射在最近邻查找的准确性。数据点根据与查询点之间的汉明距离分成不同的类别，从而可以将排序问题建模成分类问题。哈希函数通过最小化在所有训练数据点上面的分类损失而得。该方法直接最大化最近

6、邻查找最关注的排序的一致性，大量的与己有基于汉明距离的哈希方法的对比实验结果表明，序列保持哈希可以在相同的查找时间内取得更高的排序准确率。提出优化的笛卡尔均值算法。该算法用于提升基于空间量化的哈希映射在最近邻查找的准确率。传统的方法中，码本是多个子码本的笛卡尔乘积；而本文提出的方法采用多个这样的码本联合对数据进行编码。每一个数据点用多个码字的和近似，而每一个码字来自不同的码本。码本通过最小化失真误差优化而得。这样简单有效的策略不仅在实验中同时也在理论上保证了更低的失真误差，从而提升了排序的准确性。提出二值码距

7、离优化的算法。该算法用于在二值码给定的情况下，通过距离优化的方式提升最近邻查找的准确率。具体而言，由于二值码取值范围的有限性，本文通过一个非参数的查询表存储查询点到每一个二值码之间的距离。为了解决可能带来的存储空间大的问题，本文将二值码分成多个子码，每一个子码生成一个与查询相关的较小的距离查询表，近似距离定义为多个子表对应的表项的和。查询表中的元素值通过最小化近似距离和原真实距离的误差而得。该思想成功应用到对称的二值码之间的距离以及摘要非对称的查询点与数据库二值码之间的距离中。由于理论上保证了更准确的近似距离

8、，大量的实验表明了对距离的优化可以很大幅度提升基于哈希的最近邻查找的准确率。综上，本文从如何获得二值码以及如何设计针对二值码距离两个方面，提出三个新颖算法，用于提升基于哈希的最近邻查找的准确性。理论证明和大量实验结果表明了所提出方法相对于己有方法的优越性。关键词：最近邻查找，哈希映射，序列保持哈希，优化的笛卡尔均值，距离优化ABSTRACTABSTRACTRecently,hashing-based