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

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

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

【學(xué)位級(jí)別】：碩士

【部分圖文】：

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

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

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


本文編號(hào)：3066157