周文樺，劉華文，李恩慧

浙江師范大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院，浙江 金華 321001

1 引言

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

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

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

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

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

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

2 相關(guān)工作

2.1 局部敏感哈希

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

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

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

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

2.2 圖模型哈希位選擇

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

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

3 哈希位選擇算法

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

3.1 去除高相似性哈希位

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

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

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

其中，cov(hi,hj)表示hi與hj之間的協(xié)方差，D(hi)表示hi的標(biāo)準(zhǔn)差。

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

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

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

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

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

（6）基于互信息的相似度[24]?；バ畔⒚枋隽藘蓚€變量之間包含的信息量大小。互信息越大，則兩個向量之間包含的信息越大，兩個向量越相似。

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

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

算法1RHSHB算法

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

輸出：數(shù)據(jù)集哈希碼B′。

① 使用式（1）得到數(shù)據(jù)集X的哈希碼B。

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

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

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

3.2 去除低評分哈希位

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

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

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

（2）拉普拉斯分?jǐn)?shù)[25]。拉普拉斯分?jǐn)?shù)描述了各個特征保留數(shù)據(jù)局部結(jié)構(gòu)的能力。對于原始空間中的兩個近鄰點Xi和Xj，一個好的特征能夠保持這種近鄰關(guān)系，這在拉普拉斯分?jǐn)?shù)上體現(xiàn)為數(shù)值變小。哈希位hr的拉普拉斯分?jǐn)?shù)定義為：

其中，Tij表示樣本i與樣本j之間的權(quán)重，

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

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

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

3.3 隨機選擇

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

算法3隨機選擇算法

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

輸出：數(shù)據(jù)集哈希碼B′。

① 使用式（1）得到數(shù)據(jù)集X的哈希碼B。

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

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

4 實驗與分析

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

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

算法2SHHBS算法

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

輸出：數(shù)據(jù)集哈希碼′B。

① 使用式（1）得到數(shù)據(jù)集X的哈希碼B。

② 分別使用式（9）～式（12）計算每個哈希位的分?jǐn)?shù)，記為score∈RL。

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

4.1 數(shù)據(jù)集與實驗設(shè)置

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

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

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

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

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

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

4.2 評價指標(biāo)

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

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

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

根據(jù)平均精準(zhǔn)度可以得到廣泛使用的MAP：

其中，M表示查詢數(shù)據(jù)集。

4.3 實驗結(jié)果

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

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

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

圖1 數(shù)據(jù)集LabelMe上不同編碼長度下的MP

圖2 數(shù)據(jù)集Corel上不同編碼長度下的MR

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

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

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

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

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

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

圖3 數(shù)據(jù)集MNIST上11種算法的約簡比率對比

圖4 數(shù)據(jù)集CIFAR-10上11種算法約簡的比率對比

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

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

5 結(jié)束語

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