基于哈希算法的海量多媒體數(shù)據(jù)檢索研究.pdf

1、近鄰檢索問題是機器學(xué)習(xí)領(lǐng)域的一個基礎(chǔ)問題，在信息檢索、計算機視覺、數(shù)據(jù)挖掘等領(lǐng)域中都有著廣泛的應(yīng)用，例如以圖搜圖、人臉識別、k-means聚類等。近年來，隨著互聯(lián)網(wǎng)的快速發(fā)展，海量多媒體數(shù)據(jù)隨之而來。從多媒體數(shù)據(jù)中抽取出來的特征一般維度較高且稠密。如何對此類特征進行高效檢索，成為了當(dāng)前學(xué)術(shù)界和工業(yè)界炙手可熱的研究內(nèi)容。目前，主流的近鄰檢索方法包括基于樹的方法和基于哈希的方法這兩種。其中，許多基于樹的近鄰檢索方法對特征空間進行樹結(jié)構(gòu)的劃分

2、，其時間復(fù)雜度和空間復(fù)雜度都以維度d作為指數(shù)，所以當(dāng)維度d變大時，這些方法的效率就受到了限制。相反地，基于哈希算法的近鄰檢索方法是通過哈希函數(shù)（具有相似性保持的特性，即在原始特征空間中相似的兩個特征數(shù)據(jù)在映射到漢明空間后漢明距離也近）將一個d維的特征編碼成一個c位（一般地，c＜＜d）的二進制串，并通過漢明排序或者哈希表來進行檢索。其中，漢明排序可以使用硬件(XOR)來進行加速，而基于哈希表的檢索時間復(fù)雜度是O(1)，與維度d無關(guān)。由于哈

3、希算法具有高計算效率與維度不敏感的優(yōu)勢，其已經(jīng)引起了眾多學(xué)者和專家的研究興趣。圍繞基于哈希算法的海量多媒體數(shù)據(jù)近鄰檢索方法這一重要問題，本論文開展了以下工作:
　　(1)面向高效檢索的哈希函數(shù)學(xué)習(xí):基于哈希的近鄰檢索方法是以哈希函數(shù)為基礎(chǔ)的，一個好的哈希函數(shù)應(yīng)該能使用盡可能短的哈希編碼得到相對較高的準(zhǔn)確率?；陔S機投影的哈希算法不考慮數(shù)據(jù)的分布，需要較長位數(shù)的二進制串才能獲得較好的近似性能。而基于學(xué)習(xí)的哈希算法從數(shù)據(jù)的分布中學(xué)習(xí)出

4、投影向量，能在較短位數(shù)的二進制串下獲得較好的性能。我們從衡量哈希函數(shù)的優(yōu)劣標(biāo)準(zhǔn)出發(fā)，提出了一種基于學(xué)習(xí)的哈希算法——互補投影哈希算法。其是一個既保持數(shù)據(jù)的近鄰性質(zhì)（保證檢索準(zhǔn)確率），又考慮哈希桶均衡性（保證檢索速度）的哈希函數(shù)學(xué)習(xí)方法。該算法的提出為基于哈希的高效檢索奠定了基礎(chǔ)。
　　(2)跨媒體數(shù)據(jù)的哈希函數(shù)學(xué)習(xí):海量多媒體（文本、圖像、視頻、音頻等）數(shù)據(jù)的出現(xiàn)，使得面向跨媒體數(shù)據(jù)的哈希函數(shù)學(xué)習(xí)變得尤為重要。其要求學(xué)習(xí)出的哈希函

5、數(shù)能夠使不同媒體之間的關(guān)聯(lián)體現(xiàn)在哈希編碼中，即具有相同概念的多媒體數(shù)據(jù)在編碼后應(yīng)具有相同的二進制串。為此，我們提出了迭代多視角(Multi-View)哈希算法。其是一個同時保持同模態(tài)相似性和跨模態(tài)相似性的跨媒體哈希函數(shù)學(xué)習(xí)方法。其中，相似性的保持不止體現(xiàn)在對于相似數(shù)據(jù)要擁有相似的哈希編碼，也體現(xiàn)在不相似數(shù)據(jù)要擁有不相似的哈希編碼（獨特性）。該算法的提出為跨媒體數(shù)據(jù)的哈希函數(shù)學(xué)習(xí)提供了一個良好的優(yōu)化框架。
　　(3)優(yōu)化的基于哈希表

6、結(jié)構(gòu)的快速近鄰檢索:目前，相比基于樹結(jié)構(gòu)的近鄰檢索方法，基于哈希表的近鄰檢索方法未能展現(xiàn)出明顯的優(yōu)勢。其主要原因在于目前的哈希算法為了達到高準(zhǔn)確率和高召回率，通常需要擴展?jié)h明半徑來進行搜索，這使得檢索時間大大增加。為了消除這個瓶頸，我們提出了迭代擴展哈希算法，其在線上使用一個輔助索引來對使用小漢明半徑檢索到的點做迭代擴展，以此來保證高準(zhǔn)確率、高召回率和低檢索時間。該算法從本質(zhì)上提升了基于哈希表的近鄰檢索性能，為線上海量數(shù)據(jù)的實時搜索提供