1、最近鄰搜索是機器學(xué)習(xí)、計算機視覺和信息檢索里一個重要的基礎(chǔ)性問題。然而，在大規(guī)模高維數(shù)據(jù)環(huán)境下，給定查詢點，找到其精確的最近鄰需要大量的計算及存儲空間。近似最近鄰搜索算法由于其存儲空間少、查找效率高等優(yōu)點引起了人們的廣泛關(guān)注。而如何快速、高效、準確地進行近似最近鄰搜索是目前學(xué)術(shù)研究的一個熱點和難點。
　　一般來說，近似最近鄰搜索的算法在盡可能保證其準確性的情況下主要從兩個方面提高搜索速度。第一個是利用特殊的數(shù)據(jù)結(jié)構(gòu)來減少查詢點與數(shù)

2、據(jù)點的比較次數(shù);第二個是利用緊湊碼來加速計算查詢點與數(shù)據(jù)點之間的距離，比如通過哈希算法或量化算法將數(shù)據(jù)點映射為緊湊碼。本文主要從第二個方面—基于量化的近似最近鄰搜索算法—研究如何獲得更優(yōu)質(zhì)的緊湊碼來提高查找準確率和查找效率。
　　本文主要研究內(nèi)容和創(chuàng)新成果如下:
　　1.針對無監(jiān)督的近似最近鄰搜索，本文提出一種組合量化方法。其主要思想是用若干個子中心點之和作為重構(gòu)點來近似數(shù)據(jù)點，其中每個子中心點來自不同的子字典，數(shù)據(jù)點用這些

3、子中心點在各自子字典中的索引值來表示。同時，我們引入近似正交約束條件，使得計算查詢點與重構(gòu)點的距離可以用查詢點和這幾個子中心點的距離之和來代替進而加速距離計算。與已有的量化方法的對比實驗結(jié)果表明，近似正交的組合量化可以獲得更高的查找準確率。
　　2.本文提出一種稀疏組合量化算法，用以減少組合量化中創(chuàng)建查閱表所需的時間。大規(guī)模數(shù)據(jù)的近似最近鄰搜索通常結(jié)合倒排表進一步加速搜索。而組合量化在對倒排表返回的數(shù)據(jù)點進行排序的時候，創(chuàng)建查閱表

4、所需的時間變得不可忽視。針對這一問題，本文提出的稀疏組合量化方法，引入了一個稀疏條件，使得重構(gòu)字典里的每一個子中心點是一個稀疏向量。其好處是，當(dāng)創(chuàng)建查閱表需要計算查詢點與子中心點的歐氏距離的時候，由于子中心點是一個稀疏向量，可以加速距離計算。在大規(guī)模數(shù)據(jù)集上的近似最近鄰搜索表明，稀疏組合量化相比較于組合量化，可以獲得更快的查找速度。
　　3.本文提出基于量化的近似最近鄰搜索算法用于跨模態(tài)最近鄰搜索領(lǐng)域中。所謂跨模態(tài)最近鄰搜索，指的

5、是查詢點和數(shù)據(jù)點來自不同的數(shù)據(jù)模態(tài)，例如用圖像查詢點去搜索相似的文本數(shù)據(jù)點，或用文本查詢點去搜索相似的圖像數(shù)據(jù)點。本文提出的算法只假設(shè)一幅圖像和一段文本是一對應(yīng)的，而不需要已知圖像和文本的類別。該算法首先將來自不同模態(tài)的一對數(shù)據(jù)映射到同一空間中，之后在這個映射后的空間對不同模態(tài)的數(shù)據(jù)通過組合量化進行近似，同時使來自不同模態(tài)的一對數(shù)據(jù)的近似表示盡可能相同。大量的實驗比較表明，本文提出的算法在跨模近似態(tài)最近鄰搜索中可以獲得更高的查找準確率。

6、
　　4.針對有監(jiān)督近似最近鄰搜索，本文提出了一種新的量化方法。不同于無監(jiān)督近似最近鄰搜索，量化算法直接在數(shù)據(jù)庫上進行量化，本文提出的算法是使數(shù)據(jù)點首先通過一個線性變換，之后在線性變換后的數(shù)據(jù)點上進行組合量化。其優(yōu)化的目的不僅要使得量化后的近似表達能準確地代表線性變換后的數(shù)據(jù)點，同時也使得數(shù)據(jù)點在線性變換后具有類別可分離性，即相同類別的數(shù)據(jù)點在線性變換后距離很近，不同類別的數(shù)據(jù)點在線性變換后的空間內(nèi)相距很遠。與現(xiàn)有的有監(jiān)督近似最近