資源描述：
《基于哈希的最近鄰查找.pdf》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在學術論文-天天文庫。
1、UniversityofScienceandTechnologyofChina博士學位論義論文題目基于合希的最改鄰去我作者姓名王抖學科專業(yè)信號與導師姓名二〇一五年六月完成時間中神§雀本大篸博士學位論文基于哈希的最近鄰查找作者姓名：王建峰學科專業(yè)信號與信息處理導師姓名：李世鵬教授俞能海教授完成時間：二零一五年六月UniversityofScienceandTechnologyofChinaAdissertationfordoctor'sdegreeandHashing-basedNearestNeighborS
2、earchAuthor:JianfengWangSpeciality:SignalandInformationProcessingSupervisor:Prof.ShipengLiProf.NenghaiYuFinishedTime:June,2015中國科學技術大學學位論文原創(chuàng)性聲明本人聲明所呈交的學位論文，是本人在導師指導下進行研究工作所取得的成果。除已特別加以標注和致謝的地方外，論文中不包含任何他人己經(jīng)發(fā)表或撰過的研宂成。上我同：；作的志對木研允所做的丑獻均已在論文屮作丫叨確的說。作者簽名簽寧中國科學技
3、術大學學位論文授權使用聲明作為申請學位的條件之一，學位論文著作權擁有者授權中國科學技木大學擁有學位論文的部分使用權，卩：學校有權按有關規(guī)定向國家有關部門或機構送交論文的復印件和電子版，允許論文被査閱和借閱，可以將學位論文編入《中國學位論文全文數(shù)據(jù)庫》等有關數(shù)據(jù)庫進行檢索，可以采用影印、縮印或掃描等復制手段保存、匯編學位論文。本人提交的電子文檔的內(nèi)容和紙質(zhì)論文的內(nèi)容相一致。保密的學位論文在解密后也遵守此規(guī)定?！伴_口保密年作者簽名：導師簽名簽字日期：簽字曰期摘要摘要最近鄰查找是計算機視覺和機器學習領域中的一個重要
4、的基礎性問題。近年來，基于哈希的算法在處理最近鄰查找的問題上，引起了很大的關注。其基本思想是用緊湊的二值碼表示高維數(shù)據(jù)點，并且用二值碼之間的相似性近似數(shù)據(jù)點之間在原空間的相似性。二值碼表示具有存儲消耗低和計算速度快的優(yōu)點，故而哈希的方法在大規(guī)模數(shù)據(jù)環(huán)境下具有很廣的應用前景。盡管哈希方法有存儲和計算上的優(yōu)勢，但是依據(jù)二值碼排序的結果依然存在著一定的誤差。這樣的誤差目前并沒有得到很好地解決，故而本論文主要從多個方面提升哈希方法在最近鄰查找中的準確性。一般而言，基于哈希的最近鄰查找的方法包括兩個階段。第一個是哈希映
5、射，用于將數(shù)據(jù)點映射為二值碼；第二個是針對二值碼設計近似距離從而進行排序。為了提升基于哈希的最近鄰查找的準確性，本文主要從這兩個方面研宄如何獲得更優(yōu)質(zhì)的二值碼和更準確的度量距離。本文主要研宄內(nèi)容和創(chuàng)新成果如下：提出序列保持哈希算法。該算法通過最大化原空間排序結果和漢明空間排序結果之間的一致性學習哈希映射，從而提升基于漢明距離的哈希映射在最近鄰查找的準確性。數(shù)據(jù)點根據(jù)與查詢點之間的漢明距離分成不同的類別，從而可以將排序問題建模成分類問題。哈希函數(shù)通過最小化在所有訓練數(shù)據(jù)點上面的分類損失而得。該方法直接最大化最近
6、鄰查找最關注的排序的一致性，大量的與己有基于漢明距離的哈希方法的對比實驗結果表明，序列保持哈希可以在相同的查找時間內(nèi)取得更高的排序準確率。提出優(yōu)化的笛卡爾均值算法。該算法用于提升基于空間量化的哈希映射在最近鄰查找的準確率。傳統(tǒng)的方法中，碼本是多個子碼本的笛卡爾乘積；而本文提出的方法采用多個這樣的碼本聯(lián)合對數(shù)據(jù)進行編碼。每一個數(shù)據(jù)點用多個碼字的和近似，而每一個碼字來自不同的碼本。碼本通過最小化失真誤差優(yōu)化而得。這樣簡單有效的策略不僅在實驗中同時也在理論上保證了更低的失真誤差，從而提升了排序的準確性。提出二值碼距
7、離優(yōu)化的算法。該算法用于在二值碼給定的情況下，通過距離優(yōu)化的方式提升最近鄰查找的準確率。具體而言，由于二值碼取值范圍的有限性，本文通過一個非參數(shù)的查詢表存儲查詢點到每一個二值碼之間的距離。為了解決可能帶來的存儲空間大的問題，本文將二值碼分成多個子碼，每一個子碼生成一個與查詢相關的較小的距離查詢表，近似距離定義為多個子表對應的表項的和。查詢表中的元素值通過最小化近似距離和原真實距離的誤差而得。該思想成功應用到對稱的二值碼之間的距離以及摘要非對稱的查詢點與數(shù)據(jù)庫二值碼之間的距離中。由于理論上保證了更準確的近似距離
8、，大量的實驗表明了對距離的優(yōu)化可以很大幅度提升基于哈希的最近鄰查找的準確率。綜上，本文從如何獲得二值碼以及如何設計針對二值碼距離兩個方面，提出三個新穎算法，用于提升基于哈希的最近鄰查找的準確性。理論證明和大量實驗結果表明了所提出方法相對于己有方法的優(yōu)越性。關鍵詞：最近鄰查找，哈希映射，序列保持哈希，優(yōu)化的笛卡爾均值，距離優(yōu)化ABSTRACTABSTRACTRecently,hashing-based
