隨著計算機的快速發(fā)展以及互聯(lián)網(wǎng)的迅速普及,信息在互聯(lián)網(wǎng)上爆發(fā)式增長,文本、圖像、音頻、視頻等的發(fā)展導致表達數(shù)據(jù)需要更高的維度。為了更快速地對用戶做出反應,如何在短時間內(nèi)快速地在海量的數(shù)據(jù)庫內(nèi)進行匹配搜索并進行反饋,成為目前巨大的挑戰(zhàn)�；诖吮尘跋�,近似最近鄰（ANN）相關的算法被相繼提出。其中,基于量化的搜索技術由于搜索性能高,表達能力強,占用內(nèi)存空間小等優(yōu)點取得了巨大的成功。但是,大多數(shù)現(xiàn)有的量化方法都是基于批次的模型,不適合處理流式數(shù)據(jù),且現(xiàn)有的在線乘積量化模型沒有對空間分解進行優(yōu)化。為了解決上述問題,本文提出了一種在線優(yōu)化的乘積量化（Online OPQ）模型。該模型可以動態(tài)更新量化碼本和旋轉矩陣,在模型更新階段對空間分解進行優(yōu)化,降低了量化誤差,提高了搜索性能。由于在線OPQ本質上是一個在線模型,故在更新過程中只需用到新數(shù)據(jù)而不需要歷史數(shù)據(jù)。在參數(shù)初始化階段,采用優(yōu)化的乘積量化（OPQ）算法,對碼書、旋轉矩陣以及計數(shù)器進行初始化,在后續(xù)參數(shù)更新過程中,當學習新數(shù)據(jù)時,在線OPQ會先將數(shù)據(jù)旋轉到最優(yōu)空間上,隨后利用Kmeans算法的計算過程對碼書進行更新,更新后便可以得到相鄰的兩... 

【文章來源】：電子科技大學四川省 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：64 頁

【學位級別】：碩士

【部分圖文】：

k-d樹特征空間劃分對于一般低維的情況下，k-d樹在近似最近鄰上搜索較為高效

電子科技大學碩士學位論文10言，用二進制表示的話只需要4bits即可。即通過將整個空間劃分為16份以后，原始空間上的每個數(shù)據(jù)都可以用4bits大小的存儲空間表示，而原始的若干個數(shù)據(jù)點，在進行矢量量化后，可以僅存儲16個中心點的向量以及每個數(shù)據(jù)點的索引即可，大大減小了存儲空間。圖2-1矢量量化空間中心點根據(jù)這樣劃分的子空間中每個子空間均有若干個數(shù)據(jù)，便可以計算每個子空間的中心點，在圖中用黑色圓圈標注，中心點的坐標可以用對應子空間的數(shù)據(jù)點的期望得到。則在量化空間中，對于任意一個原始數(shù)據(jù)，都可以用中心點代替原數(shù)據(jù)，但顯然，中心點畢竟不是原始數(shù)據(jù)，在計算任意兩點之間的距離時，如果只用中心點代替進行計算的話，會存在一定誤差。但同樣的，這樣量化的優(yōu)點是可以只保存中心點的坐標以及子空間的編號，而不用保存所有的數(shù)據(jù)點。那么無論有多大的數(shù)據(jù)集，均可以用這16個中心點的坐標以及4bits的索引代替，這樣便大大減少了存儲空間，在計算任意兩個數(shù)據(jù)點之間的距離的時候，可以通過預先計算任意兩個中心點之間的距離來生成一個查詢表，隨后在計算距離的時候可以通過查詢該表快速的獲得結果。計算中心點的方法便是利用K-means聚類得到。但是在海量數(shù)據(jù)的情況下，原始數(shù)據(jù)與量化后中心點之間仍然存在一些距離，這樣的距離便是損失誤差，即量化后的數(shù)據(jù)與真實數(shù)據(jù)之間的差距。矢量量化便是以優(yōu)化損失誤差為目標函數(shù)所提出的量化方法。矢量量化的目標函數(shù)為：

電子科技大學碩士學位論文12min1",1#,…,1$?H!IJ1(!)KH#&,2.3. I∈S=S"×S#×…×S,(2-2)其中，C為M個子碼書S",…,S,的笛卡爾乘積。同樣的，1()為編碼函數(shù)，表示將數(shù)據(jù)量化到相應的中心點上，并返回中心點的索引值。I()為解碼函數(shù)，即將中心點的索引值作為輸入，返回對應子空間上中心點的具體向量。上式目標函數(shù)將原始數(shù)據(jù)的子向量和相應子碼書中心點之間的損失。而該式的解決方法為：對原始數(shù)據(jù)x，按照預先規(guī)定的M，將數(shù)據(jù)切分成維數(shù)相等的子向量，隨后對每個子空間上做K-means后得到M個子碼書，根據(jù)編碼函數(shù)和解碼函數(shù)，可以計算出原始數(shù)據(jù)對應的中心點。M個子碼書保存了M個空間上的中心點，原始數(shù)據(jù)對應的中心點可以用索引表示。同樣的，假設每個子空間上聚類為k個中心點，則可以用log#Lbits表示k個索引，在大大減少了存儲空間的基礎上，與矢量量化相比，乘積量化通過子碼書之間的笛卡爾乘積，可以得到L,個中心點，大大減小了量化誤差損失。圖2-2矢量量化子空間聚類為了方便理解乘積量化的定義式，現(xiàn)將利用碼書將定義式進行改寫：min1,4%?‖!-SW-‖#-∈!(2-3)


本文編號：3066157