基于量化的近似最近鄰搜索技術(shù)研究.pdf

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

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

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

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