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

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

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

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