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

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

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

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

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

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