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

周文樺，劉華文，李恩慧

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

1 引言

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

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

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

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

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

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

2 相關(guān)工作

2.1 局部敏感哈希

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

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

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

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

2.2 圖模型哈希位選擇

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

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

3 哈希位選擇算法

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

3.1 去除高相似性哈希位

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

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

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

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

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

（3）Jaccard相似度。Jaccard相似度通過(guò)兩個(gè)向量集合的交集與并集之比來(lái)刻畫向量之間的相似性。

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

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

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

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

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

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

算法1RHSHB算法

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

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

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

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

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

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

3.2 去除低評(píng)分哈希位

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

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

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

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

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

將每個(gè)哈希位視為一個(gè)特征，則哈希位rh的評(píng)分為：

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

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

3.3 隨機(jī)選擇

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

算法3隨機(jī)選擇算法

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

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

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

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

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

4 實(shí)驗(yàn)與分析

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

通過(guò)上述3種方式計(jì)算每個(gè)哈希位的評(píng)分，選擇評(píng)分高的哈希位。具體算法SHHBS（select high hashing bit score）如下。

算法2SHHBS算法

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

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

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

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

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

4.1 數(shù)據(jù)集與實(shí)驗(yàn)設(shè)置

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

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

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

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

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

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

4.2 評(píng)價(jià)指標(biāo)

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

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

其中， =Q{10,50,100,200,400,600,800,1000} 表示返回?cái)?shù)據(jù)點(diǎn)的個(gè)數(shù)。

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

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

4.3 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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