局部敏感哈希改進(jìn)算法研究.pdf

1、“大數(shù)據(jù)”時(shí)代給數(shù)據(jù)檢索帶來了新的挑戰(zhàn)，相似性檢索顯得尤為重要。局部敏感哈希算法是相似性檢索中最流行的一種，該算法是建立在哈希的基礎(chǔ)上的一種近似最近鄰算法，它能將檢索時(shí)間復(fù)雜度縮減到線性。與其它基于Tree的數(shù)據(jù)結(jié)構(gòu)相比，局部敏感哈希算法能較好的處理數(shù)據(jù)在高維空間中的檢索問題。注意到高維數(shù)據(jù)利用該算法檢索得到候選集后需要進(jìn)行相似度計(jì)算，而這一部分所耗費(fèi)時(shí)間的占整個(gè)數(shù)據(jù)檢索時(shí)間的比重非常大，所以該算法在處理大規(guī)模數(shù)據(jù)時(shí)的性能仍然需要提高。

2、
　　針對(duì)局部敏感哈希算法，考慮到數(shù)據(jù)維數(shù)和數(shù)據(jù)量的急劇增加而檢索時(shí)間還不能滿足需求情況下，提出了在不同場(chǎng)合下兩種改進(jìn)的局部敏感哈希算法并應(yīng)用于圖像，本文在局部敏感哈希算法的基礎(chǔ)上做了以下工作:
　　1.對(duì)利用局部敏感哈希算法查找前k個(gè)最相似(Top-k)的問題，提出了一種基于次數(shù)排序的局部敏感哈希算法(ST-LSH)。該算法將唯一化前的索引號(hào)按出現(xiàn)次數(shù)進(jìn)行排序來輸出，避免了相似度計(jì)算花費(fèi)大量時(shí)間的問題。實(shí)驗(yàn)結(jié)果顯示，與改進(jìn)

3、前的算法相比，在保證識(shí)別率基本不變的情況下，改進(jìn)后的算法大大減少了數(shù)據(jù)檢索時(shí)間。
　　2.在利用局部敏感哈希算法進(jìn)行數(shù)據(jù)類別的查找過程中，為了彌補(bǔ)容易受噪聲點(diǎn)的影響，提出了一種基于k近鄰分類(k-nearest neighbor)局部敏感哈希算法（KNN-LSH）。KNN-LSH充分利用了唯一化后的候選集的信息，利用候選集唯一化后的索引號(hào)所屬的類別進(jìn)行k近鄰分類。即統(tǒng)計(jì)當(dāng)前候選集所屬類別的信息，將查詢對(duì)象歸為所屬類別最多的那一類，