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

1、最近鄰查找是計算機(jī)視覺和機(jī)器學(xué)習(xí)領(lǐng)域中的一個重要的基礎(chǔ)性問題。近年來，基于哈希的算法在處理最近鄰查找的問題上，引起了很大的關(guān)注。其基本思想是用緊湊的二值碼表示高維數(shù)據(jù)點(diǎn)，并且用二值碼之間的相似性近似數(shù)據(jù)點(diǎn)之間在原空間的相似性。二值碼表示具有存儲消耗低和計算速度快的優(yōu)點(diǎn)，故而哈希的方法在大規(guī)模數(shù)據(jù)環(huán)境下具有很廣的應(yīng)用前景。
　　盡管哈希方法有存儲和計算上的優(yōu)勢，但是依據(jù)二值碼排序的結(jié)果依然存在著一定的誤差。這樣的誤差目前并沒有得到很

2、好地解決，故而本論文主要從多個方面提升哈希方法在最近鄰查找中的準(zhǔn)確性。
　　一般而言，基于哈希的最近鄰查找的方法包括兩個階段。第一個是哈希映射，用于將數(shù)據(jù)點(diǎn)映射為二值碼;第二個是針對二值碼設(shè)計近似距離從而進(jìn)行排序。為了提升基于哈希的最近鄰查找的準(zhǔn)確性，本文主要從這兩個方面研究如何獲得更優(yōu)質(zhì)的二值碼和更準(zhǔn)確的度量距離。
　　本文主要研究內(nèi)容和創(chuàng)新成果如下:
　　1.提出序列保持哈希算法。該算法通過最大化原空間排序結(jié)果和漢

3、明空間排序結(jié)果之間的一致性學(xué)習(xí)哈希映射，從而提升基于漢明距離的哈希映射在最近鄰查找的準(zhǔn)確性。數(shù)據(jù)點(diǎn)根據(jù)與查詢點(diǎn)之間的漢明距離分成不同的類別，從而可以將排序問題建模成分類問題。哈希函數(shù)通過最小化在所有訓(xùn)練數(shù)據(jù)點(diǎn)上面的分類損失而得。該方法直接最大化最近鄰查找最關(guān)注的排序的一致性，大量的與已有基于漢明距離的哈希方法的對比實(shí)驗(yàn)結(jié)果表明，序列保持哈?？梢栽谙嗤牟檎視r間內(nèi)取得更高的排序準(zhǔn)確率。
　　2.提出優(yōu)化的笛卡爾K均值算法。該算法用于

4、提升基于空間量化的哈希映射在最近鄰查找的準(zhǔn)確率。傳統(tǒng)的方法中，碼本是多個子碼本的笛卡爾乘積;而本文提出的方法采用多個這樣的碼本聯(lián)合對數(shù)據(jù)進(jìn)行編碼。每一個數(shù)據(jù)點(diǎn)用多個碼字的和近似，而每一個碼字來自不同的碼本。碼本通過最小化失真誤差優(yōu)化而得。這樣簡單有效的策略不僅在實(shí)驗(yàn)中同時也在理論上保證了更低的失真誤差，從而提升了排序的準(zhǔn)確性。
　　3.提出二值碼距離優(yōu)化的算法。該算法用于在二值碼給定的情況下，通過距離優(yōu)化的方式提升最近鄰查找的準(zhǔn)確

5、率。具體而言，由于二值碼取值范圍的有限性，本文通過一個非參數(shù)的查詢表存儲查詢點(diǎn)到每一個二值碼之間的距離。為了解決可能帶來的存儲空間大的問題，本文將二值碼分成多個子碼，每一個子碼生成一個與查詢相關(guān)的較小的距離查詢表，近似距離定義為多個子表對應(yīng)的表項的和。查詢表中的元素值通過最小化近似距離和原真實(shí)距離的誤差而得。該思想成功應(yīng)用到對稱的二值碼之間的距離以及非對稱的查詢點(diǎn)與數(shù)據(jù)庫二值碼之間的距離中。由于理論上保證了更準(zhǔn)確的近似距離，大量的實(shí)驗(yàn)表