本文關(guān)鍵詞： 近鄰檢索 哈希算法 二進(jìn)制編碼 后驗(yàn)證 距離表　出處：《吉林大學(xué)》2017年博士論文　論文類型：學(xué)位論文

【摘要】：近鄰檢索技術(shù)旨在返回與查詢樣本較相似的數(shù)據(jù)點(diǎn),其在機(jī)器學(xué)習(xí)和計(jì)算機(jī)視覺領(lǐng)域中有著廣泛的應(yīng)用。近年來,隨著網(wǎng)絡(luò)技術(shù)的快速發(fā)展和多媒體設(shè)備的迅速普及,我們已經(jīng)步入了多媒體大數(shù)據(jù)時(shí)代,并且多媒體特征一般為高維浮點(diǎn)型向量。因此,實(shí)時(shí)響應(yīng)海量高維浮點(diǎn)向量的近鄰檢索請求,已經(jīng)成為當(dāng)前學(xué)術(shù)界和商業(yè)界的熱點(diǎn)問題。哈希算法可將高維浮點(diǎn)型向量表示成緊湊二進(jìn)制編碼,并根據(jù)漢明距離關(guān)系查詢近鄰點(diǎn)。二進(jìn)制編碼所占用的存儲空間較少,并且漢明距離的計(jì)算復(fù)雜度較低。因此,在海量數(shù)據(jù)庫中,可采用基于二值編碼的近鄰檢索算法快速得到近鄰樣本。然而,有限長度的二進(jìn)制編碼的區(qū)分性較弱,并且一些哈希算法自身也存在一些問題,使得在漢明空間內(nèi)得到的近鄰檢索結(jié)果與原空間內(nèi)的近鄰檢索結(jié)果之間存在偏差,而且這些問題還沒有得到很好的解決。本論文從基于二值編碼的近鄰檢索的不同階段,探索提升近鄰檢索性能的方案,并力求兩個(gè)空間內(nèi)的檢索結(jié)果之間具有較高的一致性。近鄰檢索一般包含初始檢索階段和后驗(yàn)證兩個(gè)過程。在初始檢索階段中,決定近鄰檢索結(jié)果的主要因素是數(shù)據(jù)集的二進(jìn)制編碼,其與相似性保持目標(biāo)函數(shù)以及算法的收斂情況相關(guān)。在后驗(yàn)證階段中,近鄰檢索性能的提升幅度取決于距離表的區(qū)分性。本文以上述研究方向?yàn)榍腥朦c(diǎn),探索如何快速獲取具有較優(yōu)近鄰檢索性能的二進(jìn)制編碼,以及如何在后驗(yàn)證階段中進(jìn)一步提升近鄰檢索性能。本文中的主要研究內(nèi)容和創(chuàng)新成果如下:1.提出了歸一化距離相似性保持哈希算法,通過最小化數(shù)據(jù)點(diǎn)對在兩種不同空間內(nèi)的歸一化距離差別來保證數(shù)據(jù)點(diǎn)對在不同空間內(nèi)擁有相近的相似度。為了能夠通過比較數(shù)據(jù)點(diǎn)對在不同空間內(nèi)的距離值來判斷它們是否具有相同的相似度,本文采用了歸一化處理,使得數(shù)據(jù)點(diǎn)對在不同空間內(nèi)擁有相同的距離取值范圍,而且這一做法能夠避免距離比例參數(shù)的引入。當(dāng)訓(xùn)練數(shù)據(jù)集或目標(biāo)編碼長度發(fā)生變化時(shí),無需人為交叉驗(yàn)證使得算法性能最優(yōu)的距離比例參數(shù),有效降低了算法的訓(xùn)練復(fù)雜度,算法性能相對穩(wěn)定。算法的原目標(biāo)函數(shù)中包含數(shù)據(jù)點(diǎn)的二值編碼過程,其為離散型函數(shù),直接優(yōu)化該目標(biāo)函數(shù)較困難。為此,本文采用S型符號函數(shù)松弛處理二值編碼過程,使得目標(biāo)函數(shù)連續(xù)化。當(dāng)訓(xùn)練數(shù)據(jù)集為海量數(shù)據(jù)庫時(shí),本文采用隨機(jī)批量梯度下降算法優(yōu)化目標(biāo)函數(shù),使得算法能夠快速收斂。2.提出了排序一致性哈希算法,在歐式空間和漢明空間內(nèi),分別根據(jù)數(shù)據(jù)點(diǎn)對的不同種類的距離值對其排序,并要求兩種不同排序之間的區(qū)別最小,符合近鄰檢索的本質(zhì)要求,屬于相對相似性保持哈希算法。同時(shí),還引入了量化誤差,要求被映射為相同編碼的數(shù)據(jù)點(diǎn)在原空間內(nèi)互為近鄰關(guān)系,從而保證所生成的二進(jìn)制編碼符合空間分布特性。在訓(xùn)練階段中,學(xué)習(xí)同時(shí)滿足上述兩種約束條件的編碼中心點(diǎn)時(shí),本文分別探索利用分層編碼機(jī)制和子空間劃分方法降低訓(xùn)練時(shí)間復(fù)雜度。根據(jù)所生成的編碼中心點(diǎn),可采用基于查找的方式編碼新數(shù)據(jù)點(diǎn),但其編碼時(shí)間復(fù)雜度較高,不適應(yīng)于海量數(shù)據(jù)庫。為此,本文構(gòu)建了類似于兩步機(jī)制的算法框架,監(jiān)督學(xué)習(xí)線性哈希映射函數(shù),使得編碼時(shí)間復(fù)雜度從指數(shù)級降為線性級。本文中的強(qiáng)哈希映射函數(shù)是由自適應(yīng)提升算法組合多個(gè)弱哈希函數(shù)形成的,能夠最大程度地保留數(shù)據(jù)點(diǎn)之間的原始局部敏感信息。3.提出了適應(yīng)空間分布的多重編碼算法和距離表。哈希算法學(xué)習(xí)數(shù)據(jù)集的二進(jìn)制編碼時(shí),常采用梯度下降算法優(yōu)化目標(biāo)函數(shù)。但梯度下降算法具有局部最優(yōu)性,若目標(biāo)編碼長度有限,數(shù)據(jù)點(diǎn)在漢明空間內(nèi)的區(qū)分性較弱。為了解決上述問題,本文提出自適應(yīng)多重編碼算法,根據(jù)數(shù)據(jù)集的空間分布和目標(biāo)編碼長度,采用經(jīng)驗(yàn)學(xué)習(xí)算法,自適應(yīng)生成一組或多組數(shù)據(jù)點(diǎn)作為初始輸入,從而保證算法能夠快速得到完備解。多重編碼算法將數(shù)據(jù)點(diǎn)映射成多重二進(jìn)制編碼,并根據(jù)平均漢明距離返回初始近鄰檢索結(jié)果。在漢明空間內(nèi)的近鄰查詢結(jié)果中存在許多與查詢數(shù)據(jù)點(diǎn)共享相同漢明距離的數(shù)據(jù)點(diǎn),但它們與查詢數(shù)據(jù)點(diǎn)在原空間內(nèi)的相似度是不同的。為了進(jìn)一步區(qū)分擁有相同漢明距離的數(shù)據(jù)點(diǎn)對之間的相似度,本文建立了適應(yīng)空間分布特性的距離表。一般距離表將擁有相同編碼的數(shù)據(jù)點(diǎn)的坐標(biāo)均值作為中心點(diǎn),若編碼長度有限,多個(gè)聚類數(shù)據(jù)集可能共享相同的中心點(diǎn),使得中心點(diǎn)之間的距離值不能精確表達(dá)數(shù)據(jù)點(diǎn)之間的相似關(guān)系。本文根據(jù)數(shù)據(jù)集的空間密度分布,自適應(yīng)學(xué)習(xí)符合聚類分布特性的中心點(diǎn),并且中心點(diǎn)的數(shù)量與編碼長度無關(guān),也不同于K均值聚類算法,不需要人為確定聚類數(shù)量。本文將不同中心點(diǎn)之間的距離值,按照中心點(diǎn)的二值索引存入到不同的位置中,從而得到區(qū)分性較強(qiáng)的距離表。若編碼長度較短,編碼種類數(shù)將少于中心點(diǎn)數(shù),將有多個(gè)中心點(diǎn)對共享相同的二值索引,它們之間的距離值會被存儲在距離表中的相同位置。但是,多個(gè)中心點(diǎn)對擁有相同的多重索引的概率較小。在后驗(yàn)證階段中,可根據(jù)數(shù)據(jù)點(diǎn)對的多重索引從距離表中得到多個(gè)距離集合,并通過計(jì)算它們之間的交集來確定最終距離值。在本文中,根據(jù)數(shù)據(jù)點(diǎn)之間的漢明距離得到初始檢索結(jié)果之后,將根據(jù)適應(yīng)空間分布特性的距離表,重新判斷擁有相同漢明距離的數(shù)據(jù)點(diǎn)對之間的相對相似性,并對它們重新排序,從而進(jìn)一步提升近鄰檢索性能。
[Abstract]:In recent years , with the rapid development of network technology and the rapid popularization of multimedia devices , we have entered the multi - media data era . In order to solve the above - mentioned problems , this paper proposes an adaptive multi - coding algorithm , which is based on the spatial distribution of the data set and the length of the target .

【學(xué)位授予單位】：吉林大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2017
【分類號】：TP391.41

【相似文獻(xiàn)】

相關(guān)期刊論文 前8條

1 何琳;黃水清;徐彩琴;;基于重要句群檢索性能比較研究[J];中國圖書館學(xué)報(bào);2009年04期

2 李友良;常用中文搜索引擎檢索性能比較分析[J];江西圖書館學(xué)刊;2005年02期

3 喬亞男;齊勇;;查詢語義圖輔助的信息檢索性能預(yù)測模型[J];電子學(xué)報(bào);2011年S1期

4 金光赫;王興偉;曲大鵬;;提高檢索性能的朝鮮語布爾查詢詞生成及擴(kuò)展[J];小型微型計(jì)算機(jī)系統(tǒng);2013年05期

5 翟擁華;;基于檢索實(shí)例的Scirus檢索性能的研究[J];科技情報(bào)開發(fā)與經(jīng)濟(jì);2011年10期

6 王立遠(yuǎn);;基于lucene的AutoMatching公共控件的設(shè)計(jì)與實(shí)現(xiàn)[J];計(jì)算機(jī)光盤軟件與應(yīng)用;2012年03期

7 朱佳鳴;;Google Scholar Beta檢索性能的初步分析[J];圖書情報(bào)工作;2005年12期

8 解玉潔,吳 梅;搜索引擎的檢索性能及應(yīng)用[J];山東電子;2000年01期

相關(guān)博士學(xué)位論文 前1條

1 王振;提升近鄰檢索性能的二值編碼算法[D];吉林大學(xué);2017年

相關(guān)碩士學(xué)位論文 前1條

1 楊哲;提高信息檢索性能的有效機(jī)制與算法研究[D];中國科學(xué)院研究生院（計(jì)算技術(shù)研究所）;2004年

，

本文編號：1540623