基于多級索引的高維數據近似最近鄰搜索

楊鳳麗，李 娜，劉仁芬

(石家莊鐵道大學四方學院，河北 石家莊051132)

1 引言

當前網絡平臺上的文本、視頻等多媒體數據量持續上升，例如雅虎網站的日交換信息量高達30億條，某相簿共享網站包含超過50億張的圖片，且每日仍保持較高的圖片上傳速率。這些數據包含很多具有科學價值與應用價值的信息。在此背景下，網絡海量數據的安全維護極為重要。但是由于此類數據具有高維、異構等特點，使數據的最近鄰查詢成為難點問題[1，2]。

關于高維數據近似最近鄰搜索，很多專家學者已經得到了一些研究成果，例如劉恒等人[3]通過量化編碼實現高維數據近似最近鄰搜索，該算法搜索性能優越，且時間成本低，但內存消耗較大；劉晨赫等人[4]通過動態網格子空間實現高維數據近似最近鄰搜索，該算法復雜度較低，能有效避免有效數據丟失，但數據維數較高時的搜索性能仍不夠理想。

哈希搜索的精確、高效性，使其逐步發展為近似最近鄰查詢問題的有效方法之一，對于高維數據近似最近鄰搜索，距離敏感哈希算法運用廣泛，為優化該算法存在的搜索穩定性較差問題，引入能將若干索引方法組合使用的多級索引方法，提出基于多級索引的高維數據近似最近鄰搜索算法，通過二級距離敏感哈希，實現高維數據近似最近鄰搜索。

2 基于多級索引的高維數據近似最近鄰搜索算法

2.1 近似最近鄰查詢

近似最近鄰查詢在高維數據處理中運用廣泛，數據集和查詢點定義同上，近似比率用c描述，且c大于1，該查詢將向量p∈D作為返回結果，可使dist(p，q)≤c×dist(p*，q)成立，q的最近鄰用p*描述。

2.2 LSH算法

距離敏感哈希(Locality-Sensitive Hashing，LSH)算法是高維數據近似最近鄰搜索方面極具代表性的算法，若要檢測出相似數據點，可通過任意哈希函數值使其以極高的幾率出現沖突[5，6]。

哈希函數在該算法中符合式(1)所示條件，它屬于單向映射函數

Prh∈H[h(u)=h(v)]=sim(u，v)

(1)

式中，相似度函數用sim(u，v)∈[0，1]描述；哈希函數簇用H描述；哈希函數用h描述，其以均勻方式自H內選擇；兩個不同數據點用u、v描述；

式(2)描述了利用隨機投影法獲得的哈希函數表達式

(2)

式內，矢量用r描述，其各元素符合正態分布[7]，在超平面內，數據點u的位置決定著哈希函數取值，設定u1、u2表示數據點，兩者滿足式(3)所示表達式

(3)

任意方向矢量用ai描述，以p平穩分布為基礎的哈希函數用{h：Rd→Z}描述，關于數據庫內矢量點，通過該哈希函數將其投影至ai上，該矢量的各元素符合p平穩分布，其中，若呈現柯西分布，那么p值為1，若呈現標準高斯分布，那么p值為2。對于兩個變量，如果其線性組合滿足p平穩分布，則是在兩者均滿足p平穩分布的條件下。{h：Rd→Z}的計算過程用式(4)描述

(4)

式內，位于ai上，數據點v的投影用ai·v描述；投影窗口的量化寬度用w描述；參數用b描述，其值符合[0，w]的均勻分布，能極大地提高哈希函數的隨機性[8]；取整處理用? 」描述。設定v1、v2表示數據點，兩者滿足式(5)所示表達式

p(c)=Pr(ha，b(v1)=ha，b(v2))

(5)

設定hi為單個哈希函數，由于hi不具備較強的區分能力，建立如式(6)描述的第二級哈希函數：

gj(v)={hj，1(v)，…，hj，k(v)}j=1，…，l

(6)

式內，對于數據點v，其哈希碼為利用k個整數組建的矢量，LSH函數簇用G={g：Rd→Zk}描述。

2.3 基于M2LSH的高維數據近似最近鄰搜索算法

處理分布不均勻的高維數據時，易造成索引文件中的哈希桶所存儲的數據出現數量不均衡現象，導致返回結果個數過多或過少，從而影響LSH算法的搜索穩定性，因此使用二級距離敏感哈希(M2LSH)實現高維數據近似最近鄰搜索，使候選集盡量減少，提升算法的搜索精度和效率。

將索引創建在單個哈希表內的步驟用圖1描述。

圖1 創建索引過程

組合哈希向量代表哈希桶，用于放置原始高維數據，設定對象o，對其實施組合哈希處理，并放進與gi(o)=〈h1(o)，h2(o)，…，hk1(o)〉匹配的哈希桶內。桶寬用w描述，其值較小，將計數器Counter設定于各組合哈希桶內，能對桶內對象數量進行記錄[9，10]。

1)索引創建。

(a)使用哈希桶存儲高維數據，以(h1(o)，h2(o)，…，hk1(o)，1)描述各數據對象o完成gi(·)操作的形式，通過AND過程，對象o需放置的組合哈希桶號用o′描述，表示為(h1(o)，h1(o)，…，hk1(o))，計數器用1描述。

(b)若想為合并上步中獲取的組合哈希桶號做準備，可以通過二次哈希對其進行處理并投影至一條線上，利用該操作，能夠重新排列桶號，分配鄰近的哈希桶號至鄰近地點。

關于索引創建過程，需構建的g(·)數量用i描述，且i=1，2，…，L，各g(·)和索引文件相匹配。

以下為桶合并實現過程：

Input Line (the second hashes)

Compute the AC

Set flag=0

Foreach i=1，…，k2

For j=1，…，length of Sortedlinei

If((count+=getCount(bucketID of linei))/(average count)<ρ&&dist(bucketID of current bucketID)

Flagi[bucketID]=flag

Else

在上述桶合并過程中，AC為高維數據總數與組合哈希桶數量的比值；待合并桶數量和AC的比值用ρ描述，通常取值為1.5；待合并桶距離限制用cs描述；二級哈希內各線的桶號標記用Flagi描述；在0-1范圍中，flag的變動形式用flag描述。

2)搜索階段。

搜索對象用q描述，組合哈希向量用q′描述，可通過一次哈希形成，q′投影到直線的地點，可在實現二次哈希的基礎上獲得，查找直線中和q′擁有同樣標記的桶號，并將桶內數據當作搜索對象的候選搜索集合[12]。

(b)桶號o′(〈5，7，3，1〉，100)，表示通過AND過程后q的所得結果，則無須實現二次哈希，可將該桶內數據直接當作搜索對象的候選集。

(c)如果搜索對象完成一次哈希后，所得桶號內僅存在極少的數據，且實現二次哈希后，未找到擁有同樣標記的其余桶，則是哈希函數出現問題，利用OR過程即可彌補。

3 結果分析

高維數據一般由視頻、圖片等非結構化數據生成，選擇五個大小與維度均存在差異的實際高維數據集，以及一個人造數據集作為實驗對象，使用本文算法實現高維數據近似最近鄰搜索，以驗證該算法的搜索性能，數據集詳情用表1描述。

表1 數據集詳情

使用近似比率(Ratio)評價搜索算法的性能，它表示近似和真實最近鄰的比值，其值與1越貼近，表明算法的搜索性能越優異。

將合并哈希桶數量設定成5，哈希桶寬設定成1，測試不同相鄰桶距離(閾值ρ)下，傳統LSH算法和改進的M2LSH算法的高維數據近似最近鄰搜索效果，所得Ratio結果用圖2描述。

分析圖2可以看出，LSH算法和M2LSH算法的近似比率均隨著相鄰桶距離增加而降低；LSH算法的近似比率下降趨勢明顯，最大近似比率約為0.75，當相鄰桶距離增加至20時，近似比率已降低至0.21；當相鄰桶距離小于等于16時，M2LSH算法的近似比率保持在1左右，當相鄰桶距離增加至20時，其最小近似比率與LSH算法的最大近似比率較為接近。對比以上結果可得，相鄰桶距離對算法的搜索性能影響較大，本文算法優化后的高維數據近似最近鄰搜索效果大幅度提升，且穩定性較好。

選取報表數據集完成搜索測試，將其規模設定為100，哈希桶寬度設置為1、2、3、4，分析不同哈希函數數量下，各哈希桶寬度對數據集搜索近似比率的影響，結果如圖3。

圖3 哈希函數數量和哈希桶寬度對搜索近似比率的影響

分析圖3可以看出，隨著哈希函數數量增加，不同哈希桶寬度對應的近似比率均呈上升趨勢；在哈希函數數量小于12的情況下，近似比率上升速率較快，在超過12后逐漸趨于固定值；當哈希函數數量為2時，不同哈希桶寬度的近似比率較為接近，當哈希函數數量小于8時，哈希桶寬度為1的近似比率始終保持最高，當哈希函數數量大于8時，哈希桶寬度為3的近似比率處于最高數值，且仍有上升跡象。對比這些數據表明，哈希函數數量和哈希桶寬度對高維數據近似最近鄰搜索具有較大影響，將兩參數分別設置為12、3，不僅能獲得更優異的搜索效果，還能極大地節省時間開銷，無需持續增加哈希函數數量。

引入實際搜索代價評價本文算法的搜索能力，其值越低，表明算法的搜索效果越理想。將哈希表數量分別設定成2、4、6、8，測試本文算法搜索表1中不同數據集獲得的實際搜索代價，結果用圖4描述。

圖4 不同數據集的實際搜索代價

分析圖4可以發現，在哈希表數量不斷增長的情況下，使用本文算法搜索不同數據集獲得的實際搜索代價均隨之降低，表明增加哈希表數量能夠提升高維數據近似最近鄰搜索效果；當哈希表數量從2增長至6時，各數據集對應的實際搜索代價下降幅度較大，當哈希表數量從6增長至8時，實際搜索代價下降速率顯著減緩，表明在哈希表數量增長至一定程度后，對本文算法搜索效果的促進作用會逐步減小。

4 結論

研究基于多級索引的高維數據近似最近鄰搜索算法，在原有距離敏感哈希算法的基礎上，提出二級距離敏感哈希算法，實現高維數據近似最近鄰精確、穩定搜索。

為驗證所提算法的有效性，設計仿真驗證其應用有效性。通過不同參數的設定，驗證該算法的搜索效果，以便采取針對性方案優化算法整體性能。根據所得的實驗結果可知，該算法優化后的搜索效果大幅度提升，且穩定性較高。且該算法適用性極強，可為各類檢測、辨識、預警等技術領域提供借鑒。