本文關(guān)鍵詞：基于哈希的最近鄰查找，由筆耕文化傳播整理發(fā)布。

【摘要】：最近鄰查找是計(jì)算機(jī)視覺和機(jī)器學(xué)習(xí)領(lǐng)域中的一個(gè)重要的基礎(chǔ)性問題。近年來,基于哈希的算法在處理最近鄰查找的問題上,引起了很大的關(guān)注。其基本思想是用緊湊的二值碼表示高維數(shù)據(jù)點(diǎn),并且用二值碼之間的相似性近似數(shù)據(jù)點(diǎn)之間在原空間的相似性。二值碼表示具有存儲(chǔ)消耗低和計(jì)算速度快的優(yōu)點(diǎn),故而哈希的方法在大規(guī)模數(shù)據(jù)環(huán)境下具有很廣的應(yīng)用前景。 盡管哈希方法有存儲(chǔ)和計(jì)算上的優(yōu)勢(shì),但是依據(jù)二值碼排序的結(jié)果依然存在著一定的誤差。這樣的誤差目前并沒有得到很好地解決,故而本論文主要從多個(gè)方面提升哈希方法在最近鄰查找中的準(zhǔn)確性。 一般而言,基于哈希的最近鄰查找的方法包括兩個(gè)階段。第一個(gè)是哈希映射,用于將數(shù)據(jù)點(diǎn)映射為二值碼；第二個(gè)是針對(duì)二值碼設(shè)計(jì)近似距離從而進(jìn)行排序。為了提升基于哈希的最近鄰查找的準(zhǔn)確性,本文主要從這兩個(gè)方面研究如何獲得更優(yōu)質(zhì)的二值碼和更準(zhǔn)確的度量距離。 本文主要研究?jī)?nèi)容和創(chuàng)新成果如下： 1.提出序列保持哈希算法。該算法通過最大化原空間排序結(jié)果和漢明空間排序結(jié)果之間的一致性學(xué)習(xí)哈希映射,從而提升基于漢明距離的哈希映射在最近鄰查找的準(zhǔn)確性。數(shù)據(jù)點(diǎn)根據(jù)與查詢點(diǎn)之間的漢明距離分成不同的類別,從而可以將排序問題建模成分類問題。哈希函數(shù)通過最小化在所有訓(xùn)練數(shù)據(jù)點(diǎn)上面的分類損失而得。該方法直接最大化最近鄰查找最關(guān)注的排序的一致性,大量的與已有基于漢明距離的哈希方法的對(duì)比實(shí)驗(yàn)結(jié)果表明,序列保持哈�？梢栽谙嗤牟檎視r(shí)間內(nèi)取得更高的排序準(zhǔn)確率。 2.提出優(yōu)化的笛卡爾K均值算法。該算法用于提升基于空間量化的哈希映射在最近鄰查找的準(zhǔn)確率。傳統(tǒng)的方法中,碼本是多個(gè)子碼本的笛卡爾乘積;而本文提出的方法采用多個(gè)這樣的碼本聯(lián)合對(duì)數(shù)據(jù)進(jìn)行編碼。每一個(gè)數(shù)據(jù)點(diǎn)用多個(gè)碼字的和近似,而每一個(gè)碼字來自不同的碼本。碼本通過最小化失真誤差優(yōu)化而得。這樣簡(jiǎn)單有效的策略不僅在實(shí)驗(yàn)中同時(shí)也在理論上保證了更低的失真誤差,從而提升了排序的準(zhǔn)確性。 3.提出二值碼距離優(yōu)化的算法。該算法用于在二值碼給定的情況下,通過距離優(yōu)化的方式提升最近鄰查找的準(zhǔn)確率。具體而言,由于二值碼取值范圍的有限性,本文通過一個(gè)非參數(shù)的查詢表存儲(chǔ)查詢點(diǎn)到每一個(gè)二值碼之間的距離。為了解決可能帶來的存儲(chǔ)空間大的問題,本文將二值碼分成多個(gè)子碼,每一個(gè)子碼生成一個(gè)與查詢相關(guān)的較小的距離查詢表,近似距離定義為多個(gè)子表對(duì)應(yīng)的表項(xiàng)的和。查詢表中的元素值通過最小化近似距離和原真實(shí)距離的誤差而得。該思想成功應(yīng)用到對(duì)稱的二值碼之間的距離以及非對(duì)稱的查詢點(diǎn)與數(shù)據(jù)庫二值碼之間的距離中。由于理論上保證了更準(zhǔn)確的近似距離,大量的實(shí)驗(yàn)表明了對(duì)距離的優(yōu)化可以很大幅度提升基于哈希的最近鄰查找的準(zhǔn)確率。 綜上,本文從如何獲得二值碼以及如何設(shè)計(jì)針對(duì)二值碼距離兩個(gè)方面,提出三個(gè)新穎算法,用于提升基于哈希的最近鄰查找的準(zhǔn)確性。理論證明和大量實(shí)驗(yàn)結(jié)果表明了所提出方法相對(duì)于已有方法的優(yōu)越性。
【關(guān)鍵詞】：最近鄰查找 哈希映射 序列保持哈希 優(yōu)化的笛卡爾K均值 距離優(yōu)化
【學(xué)位授予單位】：中國(guó)科學(xué)技術(shù)大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2015
【分類號(hào)】：TP391.41;TP181
【目錄】：

• 摘要5-7
• ABSTRACT7-9
• 目錄9-12
• 表格索引12-13
• 插圖索引13-14
• 算法索引14-15
• 第一章 緒論15-23
• 1.1 研究背景和意義15-16
• 1.2 技術(shù)概述和研究現(xiàn)狀16-18
• 1.2.1 樹形結(jié)構(gòu)16
• 1.2.2 哈希方法16-18
• 1.3 基于哈希的最近鄰查找的關(guān)鍵問題18-19
• 1.3.1 高維數(shù)據(jù)如何映射成二值碼18-19
• 1.3.2 二值碼之間的距離如何衡量19
• 1.3.3 如何對(duì)二值碼數(shù)據(jù)進(jìn)行排序19
• 1.3.4 本論文關(guān)注的研究問題19
• 1.4 研究?jī)?nèi)容和創(chuàng)新點(diǎn)19-21
• 1.4.1 序列保持哈希20
• 1.4.2 優(yōu)化的笛卡爾K均值20
• 1.4.3 二值檢索中的距離優(yōu)化20-21
• 1.5 論文組織結(jié)構(gòu)21-23
• 第二章 序列保持哈希23-43
• 2.1 引言23-24
• 2.2 相關(guān)工作24-26
• 2.2.1 概率性相似度保持24-25
• 2.2.2 確定性相似性保持25-26
• 2.3 序列保持哈希26-27
• 2.4 目標(biāo)優(yōu)化27-30
• 2.4.1 函數(shù)松弛28-29
• 2.4.2 二次懲罰29-30
• 2.5 聯(lián)系與討論30-31
• 2.6 實(shí)驗(yàn)驗(yàn)證31-41
• 2.6.1 實(shí)驗(yàn)設(shè)置31-32
• 2.6.2 代碼實(shí)現(xiàn)32-33
• 2.6.3 實(shí)驗(yàn)結(jié)果33-41
• 2.7 本章總結(jié)41-43
• 第三章 優(yōu)化的笛卡爾K均值43-67
• 3.1 引言43-44
• 3.2 相關(guān)工作44-47
• 3.2.1 漢明投影44-45
• 3.2.2 空間量化45-47
• 3.3 擴(kuò)展的笛卡爾K均值47-49
• 3.3.1 參數(shù)學(xué)習(xí)48-49
• 3.4 優(yōu)化的笛卡爾K均值49-54
• 3.4.1 參數(shù)學(xué)習(xí)50-54
• 3.5 算法討論54-60
• 3.5.1 與相關(guān)工作的聯(lián)系54-56
• 3.5.2 不等式約束與等式約束56-57
• 3.5.3 代碼實(shí)現(xiàn)57-58
• 3.5.4 最近鄰檢索中的距離近似58-60
• 3.6 實(shí)驗(yàn)驗(yàn)證60-66
• 3.6.1 實(shí)驗(yàn)設(shè)置60-62
• 3.6.2 實(shí)驗(yàn)結(jié)果62-66
• 3.7 本章總結(jié)66-67
• 第四章 二值檢索中的距離優(yōu)化67-91
• 4.1 引言67-68
• 4.2 相關(guān)工作68-69
• 4.2.1 二值碼排序68-69
• 4.3 方法概述69-72
• 4.4 優(yōu)化的對(duì)稱距離72-76
• 4.4.1 目標(biāo)問題73
• 4.4.2 參數(shù)優(yōu)化73-76
• 4.5 優(yōu)化的非對(duì)稱距離76-78
• 4.5.1 目標(biāo)問題76-77
• 4.5.2 參數(shù)優(yōu)化77-78
• 4.6 算法討論78-83
• 4.6.1 分段個(gè)數(shù)78-81
• 4.6.2 與相關(guān)工作的聯(lián)系81-83
• 4.7 實(shí)驗(yàn)驗(yàn)證83-88
• 4.7.1 實(shí)驗(yàn)設(shè)置83-85
• 4.7.2 實(shí)驗(yàn)結(jié)果85-87
• 4.7.3 分段個(gè)數(shù)對(duì)性能的影響87-88
• 4.8 本章總結(jié)88-91
• 第五章 總結(jié)和展望91-93
• 5.1 總結(jié)91
• 5.2 展望91-93
• 參考文獻(xiàn)93-99
• 致謝99-101
• 在讀期間發(fā)表的學(xué)術(shù)論文與取得的研究成果10

【相似文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫 前10條

1 周屹;楊澤雪;邢傳軍;曲天偉;;一種連續(xù)最近鄰查詢的優(yōu)化方法[J];黑龍江工程學(xué)院學(xué)報(bào)(自然科學(xué)版);2013年04期

2 張奮;黃鐵;潘梅森;;不同維數(shù)下空間對(duì)象的反最近鄰查詢[J];湖南城市學(xué)院學(xué)報(bào)(自然科學(xué)版);2007年01期

3 李松;郝忠孝;;球面上最近鄰空間關(guān)系處理方法[J];計(jì)算機(jī)工程;2010年06期

4 王恒;;路網(wǎng)中基于預(yù)計(jì)算的跳躍式查詢最近鄰的算法[J];天津理工大學(xué)學(xué)報(bào);2011年02期

5 閔尋優(yōu);郝忠孝;;三維空間中的連續(xù)最近鄰查詢[J];軟件;2011年02期

6 劉彬;王建國(guó);;范圍最近鄰查詢方法研究[J];泰山學(xué)院學(xué)報(bào);2011年03期

7 李進(jìn);余建橋;;空間對(duì)象的反最近鄰查詢處理技術(shù)研究[J];計(jì)算機(jī)工程與應(yīng)用;2011年33期

8 劉艷;郝忠孝;;高維主存的反向K最近鄰查詢及連接[J];計(jì)算機(jī)工程;2011年24期

9 楊澤雪;郝忠孝;;空間數(shù)據(jù)庫中連續(xù)可視反向最近鄰查詢[J];西南交通大學(xué)學(xué)報(bào);2012年03期

10 吳昊;;最近鄰分類的改良模型[J];廣西大學(xué)學(xué)報(bào)(自然科學(xué)版);2012年06期

中國(guó)重要會(huì)議論文全文數(shù)據(jù)庫 前10條

1 張曉峰;王麗珍;肖清;趙麗紅;;基于概念劃分的連續(xù)最近鄰查詢研究[A];NDBC2010第27屆中國(guó)數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集(B輯)[C];2010年

2 管猛;張剡;柏文陽;;基于地表的連續(xù)可見最近鄰查詢方法[A];NDBC2010第27屆中國(guó)數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集(B輯)[C];2010年

3 陳璐;高云君;柳晴;陳剛;;受限相互最近鄰查詢處理[A];第29屆中國(guó)數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集（B輯）（NDBC2012）[C];2012年

4 盛梅紅;沙朝鋒;宮學(xué)慶;嵇曉;周傲英;;道路網(wǎng)絡(luò)環(huán)境中的多對(duì)象最近鄰查詢[A];第二十三屆中國(guó)數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集（研究報(bào)告篇）[C];2006年

5 劉月清;章勇;;一種改進(jìn)的動(dòng)態(tài)最近鄰聚類算法[A];全國(guó)自動(dòng)化新技術(shù)學(xué)術(shù)交流會(huì)會(huì)議論文集（一）[C];2005年

6 李傳文;谷峪;李芳芳;于戈;;一種障礙空間中不確定對(duì)象的連續(xù)最近鄰查詢方法[A];NDBC2010第27屆中國(guó)數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集A輯一[C];2010年

7 劉星毅;;基于歐式距離的最近鄰改進(jìn)算法[A];廣西計(jì)算機(jī)學(xué)會(huì)2010年學(xué)術(shù)年會(huì)論文集[C];2010年

8 劉先康;梁菁;任杰;蔣光慶;;修正最近鄰模糊分類算法在艦船目標(biāo)識(shí)別中的應(yīng)用[A];全國(guó)第4屆信號(hào)和智能信息處理與應(yīng)用學(xué)術(shù)會(huì)議論文集[C];2010年

9 劉俊嶺;孫煥良;;多維度量空間中發(fā)現(xiàn)相互kNN(英文)[A];NDBC2010第27屆中國(guó)數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集A輯二[C];2010年

10 余小高;;P2P環(huán)境中k最近鄰搜索算法研究[A];2009年全國(guó)開放式分布與并行計(jì)算機(jī)學(xué)術(shù)會(huì)議論文集(下冊(cè))[C];2009年

中國(guó)博士學(xué)位論文全文數(shù)據(jù)庫 前7條

1 楊澤雪;空間連接及最近鄰變體查詢研究[D];哈爾濱理工大學(xué);2014年

2 孫冬璞;時(shí)空數(shù)據(jù)庫多類型最近鄰查詢的研究[D];哈爾濱理工大學(xué);2010年

3 王建峰;基于哈希的最近鄰查找[D];中國(guó)科學(xué)技術(shù)大學(xué);2015年

4 張得天;時(shí)間依賴路網(wǎng)高效k最近鄰查詢混搭機(jī)制的研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2014年

5 杜欽生;高維空間的K最近鄰查詢及連接問題研究[D];吉林大學(xué);2015年

6 張軍旗;支持最近鄰查找的高維空間索引[D];復(fù)旦大學(xué);2007年

7 李艷紅;路網(wǎng)中移動(dòng)對(duì)象最近鄰及反向最近鄰查詢處理研究[D];華中科技大學(xué);2011年

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 韓冬柏;基于R-樹的最近鄰查詢研究[D];哈爾濱理工大學(xué);2011年

2 王恒;基于路網(wǎng)的最近鄰查詢方法的研究[D];天津理工大學(xué);2012年

3 宋娜;連續(xù)可視最近鄰查詢研究[D];哈爾濱理工大學(xué);2014年

4 趙海宇;連續(xù)最近鄰查詢研究[D];哈爾濱理工大學(xué);2014年

5 郭小發(fā);空間對(duì)象的連續(xù)可視最近鄰查詢處理研究[D];浙江大學(xué);2008年

6 曾令智;多類型反向最近鄰查詢的研究[D];廣西大學(xué);2013年

7 張佳佳;最近鄰查詢和反最近鄰查詢算法研究[D];哈爾濱理工大學(xué);2009年

8 朱曼龍;最近鄰方法在填充和分類中應(yīng)用的新技術(shù)[D];廣西師范大學(xué);2010年

9 張曉峰;一種基于概念劃分的不確定連續(xù)最近鄰查詢[D];云南大學(xué);2010年

10 喻榮超;最近鄰搜索方法在大可視目標(biāo)識(shí)別中的應(yīng)用[D];電子科技大學(xué);2013年

  本文關(guān)鍵詞：基于哈希的最近鄰查找，，由筆耕文化傳播整理發(fā)布。

本文編號(hào)：348686