[發(fā)明專利]位置敏感哈希隨機(jī)性減弱方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201210170014.9
• 申請(qǐng)日: 2012-05-28
• 公開(kāi)（公告）號(hào): CN102722554A
• 公開(kāi)（公告）日: 2012-10-10
• 發(fā)明（設(shè)計(jì)）人: 高毫林;郭志剛;李弼程;藺博宇
• 申請(qǐng)（專利權(quán)）人: 中國(guó)人民解放軍信息工程大學(xué)
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 鄭州大通專利商標(biāo)代理有限公司 41111
• 代理人: 陳大通

（一）、技術(shù)領(lǐng)域：本發(fā)明涉及一種檢索方法，特別是涉及一種位置敏感哈希隨機(jī)性減弱方法。

（二）、背景技術(shù):相似性搜索在許多方面有著非常重要的作用，如數(shù)據(jù)壓縮、數(shù)據(jù)挖掘、信息檢索、圖像和視頻檢索、機(jī)器學(xué)習(xí)、模式識(shí)別、統(tǒng)計(jì)和數(shù)據(jù)分析等等。這些研究中的對(duì)象一般能用相關(guān)特征的集合或高維空間中的點(diǎn)表示。這些點(diǎn)的維數(shù)范圍很大，會(huì)從幾十到幾千。當(dāng)維數(shù)較低的時(shí)候，這類問(wèn)題比較容易，但當(dāng)維數(shù)比較高時(shí)，解決起來(lái)會(huì)比較困難，也就是所謂的“維數(shù)災(zāi)難”。盡管經(jīng)過(guò)了幾十年的努力，現(xiàn)在的解決方案仍然不能讓人十分滿意。因?yàn)閷?duì)于高維向量搜索，這些方法和線性窮盡搜索相比幾乎沒(méi)有什么優(yōu)勢(shì)甚至?xí)嘶骄€性搜索。這種情況嚴(yán)重影響了相似性搜索的效果。

位置敏感哈希(LSH，Locality?Sensitive?Hashing)是當(dāng)前解決高維空間近似最近鄰(ANN，Approximate?Nearest?Neighbor)搜索問(wèn)題的速度最快的方法。其中，LSH在漢明空間進(jìn)行搜索，E2LSH(Exact?Euclidean?Locality?Sensitive?Hashing)是對(duì)LSH的改進(jìn)之一，在歐氏空間進(jìn)行搜索。與基于樹(shù)的索引方法相比，它們不但復(fù)雜度低、支持維數(shù)高，而且檢索時(shí)間大大縮短，在圖像檢索、復(fù)制檢測(cè)等方向都有應(yīng)用。

LSH和E2LSH作為ANN解決方案的基礎(chǔ)在于相似性搜索并不一定要得出精確的最近鄰，在許多情況下，近似最近鄰提供的結(jié)果已經(jīng)比較讓人滿意了，關(guān)鍵在于它能以更小的代價(jià)完成目標(biāo)。但這是這個(gè)基礎(chǔ)使得LSH不可避免的存在一定的隨機(jī)性。這樣的隨機(jī)性如果得不到好的控制，就會(huì)影響算法的性能。如在基于視覺(jué)詞典的圖像和視頻搜索工作中，可以用它來(lái)產(chǎn)生視覺(jué)詞典，而視覺(jué)詞典本身就存在著不確定性，如果對(duì)LSH聚類產(chǎn)生詞典過(guò)程中不加以控制，它的隨機(jī)性會(huì)加劇這種不確定性傳播，嚴(yán)重影響最終結(jié)果。

LSH的基本思想是：如果兩個(gè)點(diǎn)相距很近，那么在進(jìn)行映射操作后，這兩個(gè)點(diǎn)仍然相距很近。為了對(duì)這些點(diǎn)進(jìn)行映射，要先建立哈希表。好的哈希表可以使一個(gè)點(diǎn)的查詢?cè)贠(1)時(shí)間內(nèi)和O(N)內(nèi)存空間上完成查詢，N是數(shù)據(jù)點(diǎn)的數(shù)目。

在實(shí)現(xiàn)時(shí)，LSH用一系列哈希函數(shù)對(duì)數(shù)據(jù)點(diǎn)進(jìn)行哈希，使那些比較接近的點(diǎn)對(duì)于每個(gè)哈希函數(shù)發(fā)生沖突的概率比距離遠(yuǎn)的點(diǎn)要大，也就是把比較相近的點(diǎn)哈希到同一個(gè)桶。這樣，通過(guò)對(duì)查詢點(diǎn)進(jìn)行哈希并獲取它所在桶中的標(biāo)志就可以進(jìn)一步得到比較近的鄰居。哈希運(yùn)算需要定義位置敏感哈希(LSH)函數(shù)。對(duì)于點(diǎn)域S，LSH函數(shù)族定義如下：

函數(shù)族是位置敏感(locality?sensitive)的,如果對(duì)于任何q，函數(shù):||q-v||=t]與t呈嚴(yán)格遞減關(guān)系。也就是說(shuō)，點(diǎn)q和v沖突概率隨著它們之間的距離的增加而減少。

這樣，對(duì)于點(diǎn)v∈B(q,R)和點(diǎn)就有p(||q-v||)>p(||q-u||)。LSH函數(shù)族把點(diǎn)集S中的點(diǎn)哈希到某個(gè)域U，然后計(jì)算點(diǎn)q的哈希值，據(jù)此找到與它沖突的點(diǎn)。為減少運(yùn)行時(shí)間，需增大[0,R]和[R,∞]之間沖突概率的差距，可將多個(gè)函數(shù)連接起來(lái)。例如，定義一個(gè)函數(shù)族g(v)=(h₁(v),…h(huán)_k(v))，其中并從中選擇獨(dú)立且分不一致的L個(gè)函數(shù)g₁,…g_L組成哈希函數(shù)族。在預(yù)處理過(guò)程中，算法把每個(gè)點(diǎn)存儲(chǔ)在桶g_j(v)中。給出查詢點(diǎn)q后，算法搜索所有的桶g₁,…g_L，并對(duì)某個(gè)桶中發(fā)現(xiàn)的每個(gè)點(diǎn)v計(jì)算q到v的距離，如果||q-v||≤R，則認(rèn)為v就是算法要得到的點(diǎn)。