基于特征選擇的局部敏感哈希位選擇算法

周文樺，劉華文，李恩慧

浙江師范大學數學與計算機科學學院，浙江 金華 321001

1 引言

隨著互聯網技術的高速發展，需要處理的數據的量爆炸式增長。在海量數據中檢索出所需的數據變得越來越困難。最近鄰搜索（nearest neighbor search，NNS）[1]在海量數據中尋找與查詢數據最相似的近鄰數據，在信息檢索、數據挖掘、機器視覺等領域起到了至關重要的作用。若數據集中含有N個數據，則檢索準確近鄰數據的時間復雜度為O(N)。當數據庫規模非常龐大時，計算成本迅速增加，因此通常使用近似最近鄰（approximate nearest neighbor search，ANN）搜索作為替代方案來解決最近鄰搜索問題[2]。因為在很多應用領域中，無須找到最近鄰的數據，只要找到相似的數據即可。在過去的研究中，基于樹結構（如KD tree[3]、K-means tree[4]）的算法在近鄰問題上得到廣泛應用。其主要思想是對數據空間進行劃分，從而提高檢索速度。但基于樹結構的算法僅適用于低維數據，當遇到高維數據時，其性能快速下降。基于哈希的搜索算法在數據規模與數據維度很大時仍具有高效的檢索性能，且其時間、空間復雜度較低，因此該算法成為主流的檢索算法之一[5-6]。

在基于哈希的檢索方法中，局部敏感哈希（locality-sensitive hashing，LSH）算法[6-8]是有代表性的算法之一。LSH會隨機生成一組哈希函數，每一個哈希函數生成一個對應二值哈希位，將由多個哈希位組成的編碼稱為哈希碼。LSH將原空間中的數據點映射成哈希碼，使得相似度越高的數據具有相同哈希碼的概率越高，而相似度越低的數據具有相同哈希碼的概率越低。LSH的缺點是只有哈希碼長度較長時，才能夠達到理想的檢索效果。但當哈希碼的長度較長（如1024位）時，計算的時間復雜度和數據所需的存儲空間也隨之增加。因此如何生成簡短、性能優越的哈希碼成為哈希學習中的主要問題[9]。

為了生成緊湊且信息量豐富的哈希碼，近年來提出了各種類型的哈希算法，如無監督哈希學習[5]、有監督哈希學習[10-12]、半監督哈希學習[13]、深度哈希學習[14-15]等。上述哈希算法通過優化不同模型的目標函數來生成相應哈希碼，如最小化排序損失、量化誤差、重構誤差等。但上述算法在處理不同的數據集和查詢數據時，需要不斷地調整模型結構和參數才能滿足檢索要求。

為了避免頻繁地調整不同場景下的模型結構和參數，哈希位選擇算法被提出[16-18]。該算法直接從現有的哈希位池中選取信息量最大的哈希碼。在現有的研究工作中，很少有關于哈希位選擇的研究。參考文獻[17]將哈希位選擇問題轉化為圖的二次規劃問題，從而提取哈希碼。然而，該圖的二次規劃為NP困難問題，只能得出其局部最優解；而且其時間復雜度較高，至少為O(N2)，并不適用于處理大規模數據。

特征選擇[19-20]也被稱為特征子集選擇，主要思想是從現有的M個特征中選取N個特征使得算法最優。特征選擇能夠有效減少數據的維度，降低存儲成本，同時能夠提高算法的效率。現有的特征選擇算法主要分為3類：一是過濾法，根據特征的發散性或相關性對各個特征進行評分，通過設定閾值或排序方式選取特征；二是包裹法，每次選擇若干特征并輸入設定的目標函數，選出目標函數下的最優特征子集；三是嵌入法，使用與機器學習相關的算法對模型進行訓練，得到各個特征的權值系數，根據系數從大到小選擇特征。

本文的目的并不在于設計一個新的哈希算法，而是基于特征選擇的思想，將每一個哈希位視為一個特征，從現有哈希算法生成的哈希位池中高效地提取出信息量最大的哈希位。本文使用了10種簡單且高效的基于特征選擇的方法來進行哈希位選擇。為了探索特征選擇算法在哈希位選擇上的作用，本文主要從以下兩個角度進行探究：一是通過10種選擇算法去除20%的冗余哈希位，觀察精準率和召回率等性能指標的變化；二是在保持精準率和召回率等性能指標與原長度哈希位基本一致的前提下，探究每種選擇算法能去除的最大冗余哈希位比率。

2 相關工作

2.1 局部敏感哈希

局部敏感哈希由于其原理簡單、計算成本低而被廣泛應用于各個領域，如大規模數據檢索、異常檢測、近鄰問題[5,7,21]等。

局部敏感哈希將數據向量投影到隨機超平面上，再進行二值化處理生成對應的二值碼（哈希位），使數據在歐氏空間中的相似性在漢明空間中得以保存。設數據集，為LSH中的函數族，F中的每一項為隨機生成。則數據的哈希位定義如下：

數據點x與L個哈希函數f經過式（1）投影后生成長度為L的二值向量。整個數據集表示為二進制編碼B。

其中，hi∈{0,1}n×1表示編碼B的第i列，即整個數據集第i個哈希位組成的二值向量。

2.2 圖模型哈希位選擇

在現有的文獻中，很少有關于哈希位選擇的工作。僅有的基于圖模型算法有參考文獻[16-17]。在參考文獻[17]中，圖中節點權重表示每個哈希位保留原數據相似性的能力，邊權重表示哈希位之間的獨立性。一個好的哈希碼能夠保留數據在原空間中的相似性，且哈希碼之間要互相獨立，這使得哈希碼包含的信息量最大。因此在進行哈希位選擇時，應選取圖中節點權重大且節點與節點之間的邊權重也足夠大的節點集合。此時，哈希位選擇問題便轉化為圖的二次規劃問題。然而該問題為NP困難問題。參考文獻[17]采用模仿者動態理論求解，但是該解為局部最優解，而且需要調整節點權重與邊權重之間的權值參數才能得到較優的哈希碼。

在參考文獻[18]中，使用馬爾可夫過程求解上述圖的二次規劃問題。將節點權重（保留相似性的能力）轉化為自我轉移概率，將邊權重（獨立性）轉化為節點之間的狀態轉移概率。通過馬爾可夫過程，選取訪問次數最多的節點來進行哈希位選擇。然而使用馬爾可夫過程求解的訓練代價大、復雜度高。

3 哈希位選擇算法

本節詳細介紹10種哈希位選擇算法，包括去除高相似性哈希位、低評分哈希位和隨機選擇3種類型。

3.1 去除高相似性哈希位

使用皮爾遜相關系數、余弦相似度、Jaccard相似度等來描述哈希位之間的相似性程度。哈希位的相似性程度越高，其某種特定距離越小，如歐氏距離、漢明距離等。

設S∈RL×L表示L個哈希位之間的相似度矩陣，其中Sij= sim(hi,hj)，sim(hi,hj)表示哈希位hi與hj之間的相似性大小。分別使用以下方式計算sim(hi,hj)。

（1）皮爾遜相關系數（高相關濾波）[22]。皮爾遜相關系數描述了兩個向量之間變化趨勢的相似性程度。

其中，cov(hi,hj)表示hi與hj之間的協方差，D(hi)表示hi的標準差。

（2）余弦相似度[23]。特征之間的相似性用特征向量的夾角余弦來度量。

（3）Jaccard相似度。Jaccard相似度通過兩個向量集合的交集與并集之比來刻畫向量之間的相似性。

（4）基于歐氏距離的相似度。特征向量之間的歐氏距離是一種Ld范數，當d=2時，使用歐氏距離描述特征向量之間的相似性。

當d=1時，L1表示曼哈頓距離。由于哈希碼均為二值向量，哈希位之間的歐氏距離等于曼哈頓距離。

（5）基于漢明距離的相似度。漢明距離描述了兩個集合之間的重合程度。重合程度越高，兩個特征向量越相似。其中，⊕表示異或運算，若hik與hjk相同則結果為1，不同則為0。

（6）基于互信息的相似度[24]。互信息描述了兩個變量之間包含的信息量大小。互信息越大，則兩個向量之間包含的信息越大，兩個向量越相似。

其中，p(hi)表示hi的概率分布，p(hi,hj)表示hi、hj的聯合概率分布。

上述6種方式刻畫了哈希位之間的相似性程度，通過去除高相似性哈希位選擇出獨立且信息量豐富的哈希位。具體算法RHSHB（remove high similarity hashing bit）如下。

算法1RHSHB算法

輸入：數據集X，哈希碼長度L，選擇后的哈希碼長度k。

輸出：數據集哈希碼B′。

① 使用式（1）得到數據集X的哈希碼B。

② 分別使用式（3）～式（8）計算哈希位之間的相似度矩陣S。

③ 將S的上三角陣按從大到小排序，將前L-k個數值（具有高相似度）所在的列號作為需要去除的哈希位，記為集合D。

④ 去除哈希碼B中集合D記錄的哈希位，得到去除冗余哈希位后的哈希碼B′。

3.2 去除低評分哈希位

通過計算每個哈希位的方差、拉普拉斯分數、信息熵等屬性來評定每個哈希位的好壞，每個哈希位給予相應的評分score(hi)，去除其中評分低的哈希位。score(hi)的計算方式如下。

（1）低方差濾波。數據取值變化小的哈希位所包含的信息量越少，該哈希位的方差越低。將每個哈希位的方差作為評分。

其中，var(hi)表示hi的方差。

（2）拉普拉斯分數[25]。拉普拉斯分數描述了各個特征保留數據局部結構的能力。對于原始空間中的兩個近鄰點Xi和Xj，一個好的特征能夠保持這種近鄰關系，這在拉普拉斯分數上體現為數值變小。哈希位hr的拉普拉斯分數定義為：

其中，Tij表示樣本i與樣本j之間的權重，

將每個哈希位視為一個特征，則哈希位rh的評分為：

（3）信息熵[26]。哈希位的信息熵值越大，該哈希位的不確定性程度越高，包含的信息量越大。使用信息熵作為哈希位的評分：

④ 提取哈希碼B中集合D記錄的哈希位，得到去除冗余哈希位后的哈希碼B′。

3.3 隨機選擇

隨機選擇是一種直接的選擇方式，即不考慮哈希位的屬性或哈希位之間的關系，從現有的哈希位集合中隨機選取哈希位子集。隨機哈希位選擇的具體算法如下。

算法3隨機選擇算法

輸入：數據集X，哈希碼長度L，選擇后的哈希碼長度k。

輸出：數據集哈希碼B′。

① 使用式（1）得到數據集X的哈希碼B。

② 從1至L中隨機均勻生成k個隨機數，記為集合D。

③ 提取哈希碼B中集合D記錄的哈希位，得到去除冗余哈希位后的哈希碼B ′。

4 實驗與分析

其中，p(hi)表示hi取值的概率分布，m表示hi取值的個數。在哈希位中，m=2，即hi中元素的取值只能為0或1。

通過上述3種方式計算每個哈希位的評分，選擇評分高的哈希位。具體算法SHHBS（select high hashing bit score）如下。

算法2SHHBS算法

輸入：數據集X，哈希碼長度L，選擇后的哈希碼長度k。

輸出：數據集哈希碼′B。

① 使用式（1）得到數據集X的哈希碼B。

② 分別使用式（9）～式（12）計算每個哈希位的分數，記為score∈RL。

③ 將score從大到小排序，將前k個數值所在的列號作為選取的哈希位，記為集合D。

4.1 數據集與實驗設置

本文使用兩個有標簽數據集和兩個無標簽數據集進行實驗驗證。其中有標簽數據集分別為CIFAR-10[27]和MNIST[28]，將具有相同標簽的數據作為真實近鄰點；無標簽數據集分別為LabelMe[29]和Corel[30]，將其歐氏空間下的近鄰點作為真實近鄰點。下面簡要描述上述4個常用數據集。

MNIST：MNIST數據集為整數0～9的手寫數字圖片，包含70000張28×28像素的灰度圖片。

CIFAR-10：CIFAR-10包含60000張32×32像素的彩色圖片。所有圖片被分為10個種類，每類圖片中含有6000張圖片。

LabelMe：LabelMe數據集包含22000張彩色圖片，圖片均為生活中的場景與實體。

Corel：Corel數據集包含10000張192×128像素的彩色圖片。其中多為風景類圖片，如日落、山脈等。

對于MNIST和CIFAR-10兩個數據集，分別從每個類別中隨機抽取1000張圖片作為查詢集（共計10000張圖片），剩余的所有圖片作為數據庫。對于LabelMe和Corel數據集，分別從中隨機抽取3000張圖片作為查詢集，余下的所有圖片作為數據庫。MNIST數據集直接使用圖片的像素值作為特征向量（786=28×28），其他3個數據集則提取每張圖片512維的GIST特征作為特征向量。

4.2 評價指標

本文采用文獻中廣泛使用的精準度（precision）、召回率（recall）、平均精度均值（mean average precision，MAP）3個性能指標來衡量實驗結果。將測試數據的真實近鄰點集合定義為R，假設測試數據返回的數據集合為′R，則定義精準度和召回率分別為：

為了描述哈希位選擇前后性能的變化，取返回不同數據點個數下的平均精準度（mean precision，MP）和平均召回率（mean recall，MR）進行對比，定義MP與MR為：

其中， =Q{10,50,100,200,400,600,800,1000} 表示返回數據點的個數。

根據平均精準度可以得到廣泛使用的MAP：

其中，M表示查詢數據集。

4.3 實驗結果

為了清晰地展示圖片中的內容，將第2.2節中基于圖模型的哈希位選擇和本文使用的10種哈希位選擇算法分別命名為：NDomSet（圖模型）、HCF（高相關濾波）、Cosine（余弦相似度）、Hamming（漢明距離）、Euc（歐氏距離）、MI（互信息）、Jaccard（Jaccard相似度）、LCV（低方差濾波）、LS（拉普拉斯分數）、IE（信息熵）、Random（隨機）。

在實驗過程中，分別使用局部敏感哈希生成的128、256、512、1024位哈希池進行哈希位選擇。每個哈希碼長度均約簡（即去除冗余哈希位）20%，則約簡后的哈希碼長度為102、205、410、819位。

局部敏感哈希約簡20%的哈希位后與原哈希碼在MP和MR上的對比分別如圖1、圖2所示。在LabelMe和Corel數據集上，當原哈希碼為128、256位時，約簡后的哈希碼與原碼在平均精準度和平均召回率上的誤差在1%～2%之間；當原哈希碼為512、1024位時，除了基于Cosine的選擇算法，大部分選擇算法誤差在0～1%之間。這一現象表明，原哈希碼越長，約簡相同比例的哈希碼對其性能影響越小。

圖1 數據集LabelMe上不同編碼長度下的MP

圖2 數據集Corel上不同編碼長度下的MR

表1給出了在有標簽數據集CIFAR-10和MNIST上約簡20%哈希位后，MAP的前后對比。在CIFAR-10數據集上，不同長度的哈希碼約簡后的MAP均與原碼的MAP保持一致（誤差小于2%）；在MNIST數據集上，當原哈希碼為128位時，基于歐氏距離（Euc）、低方差濾波（LCV）、拉普拉斯分數（LS）、信息熵（IE）的哈希位選擇算法與原哈希碼的性能誤差在2%～3%之間。其他長度的哈希碼基本與原碼保持一致（誤差小于2%）。

表1 MAP在CIFAR-10和MNIST數據集上不同編碼長度下的MAP

在MP、MR和MAP均與原哈希碼基本保持一致的前提下（誤差小于2%），探究128、256、512、1024位局部敏感哈希在11種哈希位選擇算法下能約簡的最大比率。從圖3和圖4中可以發現，隨著原哈希碼長度的增加，使用不同哈希位選擇算法能約簡的哈希位比率也在增加。該現象說明雖然隨著哈希碼長度的增加，原局部敏感哈希的檢索性能有所提升，但其中冗余的哈希位也相應增多。

在MNIST數據集上，基于歐氏距離、低方差濾波、拉普拉斯分數、信息熵的哈希位選擇算法能約簡的哈希位比率較少。而其他哈希位選擇算法均能約簡20%以上。當原哈希碼為1024位時，使用基于圖模型、余弦相似度、高相關濾波等選擇算法的約簡比率高達60%以上。在CIFAR-10數據集上，所有哈希位選擇算法均能約簡20%以上的哈希碼，且哈希碼長度較長（如512、1024）時，約簡比率為30%～70%。

表2給出了不同哈希碼長度下，對于給定的查詢數據，檢索3000個近鄰數據所需時間。從表2可以看出，檢索所需時間隨著哈希碼長度的增加而增加。例如，哈希碼長度從256位增加至512位時，檢索時間增加近一倍。結合圖3與圖4可以看出，本文使用的哈希位選擇算法能夠將原哈希碼約簡30%～70%，使用約簡后的哈希碼進行信息檢索，不僅能夠充分減少檢索所需時間，還可以降低數據（圖片、文本等）轉換后的哈希碼所需存儲空間。

表2 不同哈希碼長度下檢索3000個近鄰數據所需時間

圖3 數據集MNIST上11種算法的約簡比率對比

圖4 數據集CIFAR-10上11種算法約簡的比率對比

表3給出了11種哈希位選擇算法的時間復雜度和將512位哈希碼約簡20%后的MAP和實際運行時間。其中，n表示數據個數，d表示數據維度，k表示哈希碼長度（k?n）。從表3可以看出，雖然基于NDomSet的哈希位選擇算法的MAP最高，但是其時間復雜度也最大。基于NDomSet的哈希位選擇算法的MAP高于基于Cosine、HCF、Jaccard、Hamming、LCV、IE、Random的哈希位選擇算法0～0.002，然而其運行時間為這幾種算法的20～100倍（除了基于IE的哈希位選擇算法）。因此，在處理小規模數據集和追求高精度的場景下可以使用基于NDomSet的哈希位選擇算法，但當處理大規模數據時，基于特征選擇的哈希位選擇算法更加高效，同時不會嚴重損失哈希碼的精度。

表3 數據集CIFAR-10上11種算法的時間復雜度、MAP與運行時間

5 結束語

本文首次將特征工程中的10種降維算法應用于哈希位選擇中。在保證約簡后的哈希碼與原碼性能基本一致的前提下，盡可能約簡較多的哈希碼，使得約簡后的哈希碼更加緊湊、高效，包含的冗余信息更少。約簡后的哈希碼不僅提高了檢索效率，且減少了基于哈希碼表示的數據集所需的存儲空間。