花 強(qiáng)，郭欣欣，張 峰，董春茹

河北大學(xué) 河北省機(jī)器學(xué)習(xí)與計算智能重點實驗室，河北 保定 071002

1 引言

近年來，信息檢索在各個領(lǐng)域扮演著越來越重要的角色，例如商品推薦系統(tǒng)、多媒體信息檢索以及社交網(wǎng)絡(luò)分析等。最近鄰搜索（nearest neighbor search，NNS）作為實現(xiàn)信息檢索的重要機(jī)器學(xué)習(xí)方法之一而被廣泛應(yīng)用。然而，近年隨著社交媒體、互聯(lián)網(wǎng)、物聯(lián)網(wǎng)、云計算等信息科學(xué)技術(shù)的快速發(fā)展，人類社會進(jìn)入了“大數(shù)據(jù)時代”，各行業(yè)積累的數(shù)據(jù)往往呈現(xiàn)出兩個新的特征，即（1）數(shù)據(jù)量變得巨大且增長趨勢迅速；（2）常常伴隨著高維數(shù)據(jù)。海量數(shù)據(jù)和“維度災(zāi)難”兩個問題的疊加，使得精確最近鄰算法效率降低，甚至失效，此時近似最近鄰搜索（approximate nearest neighbor search，ANNS）[1]就變得越來越重要。

近似最近鄰搜索返回與其真實最近鄰半徑在c(c＞1)倍誤差之內(nèi)的對象作為結(jié)果。當(dāng)面對大規(guī)模的數(shù)據(jù)時，搜索近似最近鄰樣本的計算量要小于搜索最近鄰樣本的計算量。在常見近似最近鄰搜索算法中，哈希算法以其在存儲空間和計算時間上的優(yōu)勢受到了較多關(guān)注。哈希算法通過哈希函數(shù)將數(shù)據(jù)投影到海明空間，從而將原始空間樣本表示成二進(jìn)制哈希碼，同時盡量保持原數(shù)據(jù)空間中樣本間的近鄰關(guān)系，即在原空間相似的樣本點在海明空間中依然相似。通過將樣本使用一個緊湊的二進(jìn)制編碼表示可以節(jié)約存儲空間，提高計算速度。很多哈希算法[2-10]已經(jīng)被提出并應(yīng)用到不同問題中，例如圖像檢索[11]、視頻檢索[12]、重復(fù)圖片檢測[13]、關(guān)鍵點檢測[14]等。

隨機(jī)森林（random forest）[15-16]是一種基于隨機(jī)決策樹的集成學(xué)習(xí)方式，其已被用于處理多種學(xué)習(xí)任務(wù)，并取得了很好的效果[17]。2017年，周志華等人提出了首個基于隨機(jī)森林的自編碼器[18]，該方法利用森林中多棵樹的路徑所定義的最大相容規(guī)則來重構(gòu)原始樣本。受該文啟發(fā)，本文提出了一種基于隨機(jī)森林的哈希算法，通過將隨機(jī)森林中多棵決策樹的路徑串聯(lián)成二進(jìn)制編碼來表示原空間中的樣本，從而實現(xiàn)對樣本的哈希編碼，進(jìn)一步使用順序敏感的海明距離在哈希空間中衡量樣本間的相似性。由決策樹學(xué)習(xí)算法的特點及數(shù)值仿真實驗表明，本文的方法具有以下優(yōu)點：

（1）通過集成隨機(jī)森林中不同決策樹的路徑構(gòu)建的哈希碼可以很好地保持原特征空間中樣本的相似性，在MNIST[19]和CIFAR-10[20]數(shù)據(jù)集上的實驗結(jié)果也驗證了這一點；

（2）隨機(jī)森林中不同決策樹所使用的特征空間和學(xué)習(xí)過程是獨立的，因此可以以增量的方式靈活地確定哈希碼長度，算法學(xué)習(xí)效率較高；

（3）可以處理數(shù)值型屬性、符號型屬性及混合型屬性的數(shù)據(jù)集，此外在隨機(jī)子空間上構(gòu)建隨機(jī)決策樹也可以有效降低“維數(shù)災(zāi)難”問題的影響。

2 相關(guān)工作

常用的近似最近鄰搜索方法主要包括哈希算法和基于樹型的檢索算法[21]。

哈希算法可以分為數(shù)據(jù)獨立的哈希算法和數(shù)據(jù)依賴的哈希算法[22]。數(shù)據(jù)獨立的哈希算法中哈希函數(shù)的生成不考慮數(shù)據(jù)的分布，例如局部敏感哈希（locality-sensitive Hashing，LSH）方法[2]數(shù)據(jù)獨立哈希算法沒有學(xué)習(xí)過程，不依賴于樣本的任何先驗知識，編碼過程快捷，但是這些方法不能捕捉數(shù)據(jù)的分布特性，通常需要較長的哈希碼才可以包含更多數(shù)據(jù)信息。數(shù)據(jù)依賴哈希算法是基于學(xué)習(xí)的哈希算法，在得到哈希函數(shù)的時候會學(xué)習(xí)數(shù)據(jù)本身的結(jié)構(gòu)，從而選擇更有利于保持?jǐn)?shù)據(jù)相似性的維度，學(xué)習(xí)到對數(shù)據(jù)具有較強(qiáng)劃分能力的哈希函數(shù)，因此在滿足同樣檢索精度的情況下，其編碼位數(shù)會大大降低，同時降低了存儲成本。數(shù)據(jù)依賴的哈希算法包括早期的無監(jiān)督學(xué)習(xí)算法，例如迭代量化哈希（iterative quantization，ITQ）[3]、譜哈希（spectral Hashing，SH）[4]、等方差哈希（isotropic Hashing，IsoHash）[5]和離散圖哈希（discrete graph Hashing，DGH）[6]等。后來，研究者將類標(biāo)簽信息合理地應(yīng)用于哈希算法中，提出了各種監(jiān)督哈希算法，使得后者的檢索性能和精度要遠(yuǎn)遠(yuǎn)高于前者。有監(jiān)督的哈希算法利用原始數(shù)據(jù)的真實類標(biāo)簽信息來輔助哈希算法的學(xué)習(xí)過程，保證原始空間中相近的或同一類的樣本學(xué)習(xí)到相同或更相似的哈希碼，反之則反。一些典型的監(jiān)督學(xué)習(xí)哈希算法包括最小損失哈希（minimalloss Hashing，MLH）[7]、二值重建嵌入哈希（binary reconstruction embedding，BRE）[8]、監(jiān)督離散哈希（supervised discrete Hashing）[9]和核化的有監(jiān)督哈希算法（kernel-based supervised Hashing，KSH）[10]等。

基于樹型的近似最近鄰搜索是一種廣泛應(yīng)用的數(shù)據(jù)檢索方式，它的本質(zhì)原理是對數(shù)據(jù)特征空間區(qū)域進(jìn)行層次劃分，搜索數(shù)據(jù)時在劃分好的層次空間上進(jìn)行檢索。這種方法可以縮小搜索的范圍，加快搜索的速度?；跇涞慕平徦阉魉惴ò↘D樹[23]和R樹[24]等。KD樹在搜索空間中不斷將父節(jié)點包含的區(qū)域分為相鄰的兩部分，每部分包含原來區(qū)域中的一半點。檢索時從根節(jié)點開始在每個分叉點上對目標(biāo)點進(jìn)行計算，直到葉節(jié)點。R樹將數(shù)據(jù)分成不同層次的數(shù)據(jù)區(qū)，每個數(shù)據(jù)區(qū)表示為區(qū)內(nèi)所有數(shù)據(jù)的最小外接矩陣。在進(jìn)行高維數(shù)據(jù)索引時，首先根據(jù)R樹的分層結(jié)構(gòu)查找到可以包含目標(biāo)數(shù)據(jù)的葉子節(jié)點，然后再遍歷葉子節(jié)點中的數(shù)據(jù)，獲取相似的節(jié)點。在低維空間時，基于樹的方法可以很高效地獲取相似的數(shù)據(jù)，取得很好的檢索速度和檢索精度。但是隨著數(shù)據(jù)維度的增加，基于樹的檢索速度越來越慢，甚至退化為暴力搜索。

3 基于隨機(jī)森林的哈希碼生成

本章主要介紹隨機(jī)森林的構(gòu)建過程以及如何將隨機(jī)森林轉(zhuǎn)化成哈希碼。

3.1 隨機(jī)森林的構(gòu)建

隨機(jī)森林由多棵決策樹組成，是一種強(qiáng)大的集成學(xué)習(xí)方式，對于多種任務(wù)都有著很好的表現(xiàn)。在森林中，每棵決策樹的每條路徑都是對空間的一種劃分，越相似的樣本劃分到的空間越相近。隨機(jī)森林的基本單元是隨機(jī)決策樹。構(gòu)造一棵隨機(jī)決策樹，首先以隨機(jī)方式選擇一定數(shù)量的特征作為候選特征，然后根據(jù)節(jié)點分裂的衡量標(biāo)準(zhǔn)和相應(yīng)的策略構(gòu)建決策樹。決策樹由根節(jié)點、內(nèi)部節(jié)點和葉子節(jié)點組成。每一個非葉子節(jié)點上的數(shù)據(jù)都會按照當(dāng)前屬性劃分為兩個或多個數(shù)據(jù)集，并分別交由下一級的節(jié)點處理。構(gòu)建隨機(jī)樹過程中，常使用的經(jīng)典的決策樹算法有ID3算法[25]、C4.5算法[26]和CART（classification and regression tree）算法[27]等。

ID3算法只能處理離散值，使用信息增益（information gain）作為非葉子節(jié)點特征屬性的劃分標(biāo)準(zhǔn)。構(gòu)建決策樹的過程中每次在當(dāng)前屬性集中選擇數(shù)據(jù)集劃分之后信息增益最大的特征屬性作為非葉子節(jié)點的特征屬性來創(chuàng)建非葉子節(jié)點，直到達(dá)到?jīng)Q策樹停止生長的條件。C4.5算法可以處理離散值也可以處理連續(xù)值，使用信息增益比作為特征屬性選擇的標(biāo)準(zhǔn)。每次從當(dāng)前特征集中選擇信息增益比最大的特征作為屬性進(jìn)行節(jié)點創(chuàng)建,直到達(dá)到?jīng)Q策樹停止生長的條件完成整棵決策樹的構(gòu)建。CART算法既可以處理連續(xù)值也可以處理離散值，將基尼系數(shù)作為選擇最優(yōu)候選屬性的衡量標(biāo)準(zhǔn)。CART算法在構(gòu)建決策樹的過程中，無論當(dāng)前屬性在數(shù)據(jù)集中有幾種類型，數(shù)據(jù)集總是被分割成兩部分，即CART算法構(gòu)建的決策樹是二叉樹。CART樹每個節(jié)點將空間劃分為兩部分，而哈希碼的每一位同樣將空間劃分為兩部分，因此本文將采用CART算法構(gòu)建決策樹。

對于樣本集X的基尼系數(shù)定義如下：

其中，pi代表第i類樣本在該子集中出現(xiàn)的概率（實際計算時用第i類在該樣本子集中出現(xiàn)的頻率代替）。若樣本集按屬性t劃分得到m個子數(shù)據(jù)集，則劃分后得到的基尼系數(shù)為：

其中，ni為第i個樣本子集的樣本數(shù)，n為X中樣本總數(shù)，的基尼系數(shù)。

CART算法構(gòu)建決策樹的過程中，計算每個特征t劃分?jǐn)?shù)據(jù)集獲得的基尼系數(shù)，找到使劃分后基尼系數(shù)最小的特征作為節(jié)點的屬性創(chuàng)建節(jié)點，然后在樹的每個分枝上重復(fù)該過程，直到達(dá)到?jīng)Q策樹設(shè)定的最大深度即停止生長，完成決策樹的構(gòu)建。算法流程可歸納如下：

算法1構(gòu)建CART樹

輸入：訓(xùn)練集X，隨機(jī)選擇屬性的個數(shù)T，決策樹最大深度D。

輸出：CART樹。

步驟1隨機(jī)選擇含T個屬性的訓(xùn)練樣本子集?；

步驟2計算當(dāng)前數(shù)據(jù)集基尼系數(shù)Gini()；

步驟3選擇基尼系數(shù)最小的屬性作為劃分屬性；

步驟4按照劃分屬性將當(dāng)前數(shù)據(jù)集進(jìn)行劃分；

步驟5對每個子節(jié)點遞歸地調(diào)用步驟2、3、4，直到樹深度為D或樣本子集中的數(shù)據(jù)類別相同。

得到隨機(jī)決策樹后，將決策樹從根節(jié)點到每個葉節(jié)點的路徑進(jìn)行編碼。由于CART構(gòu)建的決策樹都是二叉樹，則設(shè)定樹的左分支編碼為0，右分支編碼為1，從而可得到一棵帶有0-1編碼路徑的決策樹，訓(xùn)練好的每一棵決策樹，等價于一個哈希函數(shù)，它將原始空間的每個樣本唯一映射到了海明空間中的二進(jìn)制哈希碼。

3.2 基于隨機(jī)森林生成哈希碼

在3.1節(jié)中構(gòu)建了隨機(jī)森林，并將森林中每棵決策樹的路徑自頂?shù)较逻M(jìn)行了0-1編碼。此時，對給定一個樣本，隨機(jī)森林中的每棵決策樹都會將該樣本劃分到其某個葉子節(jié)點上，也即在森林中的每棵樹中都可以得到一條從根節(jié)點到該葉子節(jié)點的路徑。由決策樹的性質(zhì)可知，在原空間中相近的樣本會以很大的概率劃分到?jīng)Q策樹的同一個分支上，從而其對應(yīng)的哈希碼也會相同或近似。此外，單棵決策樹使用了較少的特征信息，對于空間的劃分不夠精確，而森林中的多棵決策樹產(chǎn)生的多個哈希碼包含了更多的屬性信息，可以得到更加精細(xì)的空間劃分，因此采用順序鏈接的方式集成森林中多棵決策樹產(chǎn)生的哈希碼信息。這一過程可形式化描述如下：

設(shè)森林中一棵決策樹生成的哈希碼為B=b1b2…bD，其中D表示樹的深度，bi∈{0,1}，其對應(yīng)第i層決策樹某一節(jié)點的分支編碼。若由根到葉節(jié)點的路徑長度小于D，則在哈希碼后補(bǔ)0，直到擁有相同的碼長D。假設(shè)森林中有N棵決策樹，則樣本通過森林后得到的哈希碼，稱之為全哈希碼（total Hash code），記為B=[B1,B2,…,BN]，全哈希碼長度為N×D。圖1演示了由隨機(jī)森林構(gòu)建哈希碼的過程。其具體流程由算法2給出。

Fig.1 Generating Hash code from random forest(with maximum tree depth of 3)圖1 由隨機(jī)森林生成哈希碼（決策樹最大深度為3）

算法2由隨機(jī)森林生成哈希碼

輸入：隨機(jī)森林forest(N,D)，樣本x。

輸出：全哈希碼。

步驟1樣本輸入隨機(jī)森林forest的決策樹中；

步驟2每棵樹返回一條路徑對應(yīng)的二進(jìn)制碼；

步驟3若返回二進(jìn)制碼長度小于D，在二進(jìn)制碼后補(bǔ)0直至D位，生成哈希碼；

步驟4將N棵樹哈希碼順序連接生成全哈希碼。

4 順序敏感的海明距離

在本章中，根據(jù)3.2節(jié)得到的哈希碼，詳細(xì)介紹順序敏感的海明距離，從而給出海明空間中樣本之間的相似性度量。

海明距離是度量二進(jìn)制編碼相似性的常用方法。設(shè)兩個D位二進(jìn)制編碼為，則傳統(tǒng)海明距離的計算方法如下式：

其中，⊕表示異或運算。在海明空間中計算機(jī)可以用機(jī)器指令來計算海明距離，運算速度極快，極大提高算法運算速度，因此基于傳統(tǒng)海明距離的相似性度量在哈希算法中有著關(guān)鍵作用[3-4]。但是，計算傳統(tǒng)海明距離，二進(jìn)制編碼的位與位之間是相互獨立的。而本文中，基于隨機(jī)森林生成的哈希碼，位與位之間具有由根節(jié)點到葉節(jié)點的生成順序關(guān)系，即：設(shè)決策樹生成的哈希碼為B=b1b2…bD，其中bi∈{0,1}，bi對應(yīng)第i層決策樹某一節(jié)點的分支編碼，由于樹形結(jié)構(gòu)的特點，bi與bi+1所處節(jié)點是父子節(jié)點關(guān)系，由此哈希碼B在b1至bD的生成過程中具備了順序生成的特征。因此，定義的哈希碼距離應(yīng)具有順序敏感性的特點[28]，也就是說，順序逐位比較哈希碼時要保證祖先位編碼相同（也可稱為哈希碼的公共前綴）才有繼續(xù)比較的意義。而兩個哈希碼公共前綴越長則相似度越高。那么，哈希碼B1和B2的順序敏感的相似性公式可形式化定義如式（4）：

若森林中有N棵樹，經(jīng)由森林生成的任意兩個全哈希碼分別記為則兩個全哈希碼的相似性定義如下：

全哈希碼間順序敏感的海明距離可定義如式（6）：

注意到，原始空間的數(shù)據(jù)樣本經(jīng)由決策樹生成哈希碼的過程中，可能出現(xiàn)哈希碼長度不等的情況，為規(guī)范化哈希表示。將深度小于D的路徑對應(yīng)的哈希碼用0或1進(jìn)行后綴補(bǔ)齊。事實上，依據(jù)本章提出的算法易知這種操作不影響順序敏感的相似性的判斷結(jié)果。

5 實驗與結(jié)果

5.1 數(shù)據(jù)集

MNIST數(shù)據(jù)集由28×28像素的灰度手寫數(shù)字 圖片組成，數(shù)字范圍從0到9，共10類。訓(xùn)練集包含60 000張圖片，測試集為10 000張圖片。實驗中，784位像素值作為原始空間的樣本特征表示。

CIFAR-10數(shù)據(jù)集由32×32像素的彩色圖片組成，分為10個類。訓(xùn)練集中有50 000張圖片，測試集中有10 000張圖片。實驗中，對CIFAR-10提取512維GIST特征作為原始空間的樣本表示[29]。

實驗過程中，為了統(tǒng)一測試標(biāo)準(zhǔn)，方便同其他流行算法進(jìn)行公平比較，訓(xùn)練數(shù)據(jù)和測試數(shù)據(jù)按照大部分選定比較方法的標(biāo)準(zhǔn)進(jìn)行如下規(guī)范：訓(xùn)練集直接使用數(shù)據(jù)集給定的訓(xùn)練樣本；測試集包括查詢樣本集和被查詢樣本集，前者從數(shù)據(jù)集給定的測試樣本中隨機(jī)選擇1 000張（每類100張，共10類）作為查詢樣本，后者從剩余測試樣本中隨機(jī)選擇5 000張圖片（每類500張，共10類）作為被查詢樣本集。

5.2 性能度量指標(biāo)

在實驗中，使用Precision和mAP（mean average precision）度量指標(biāo)來評價常見哈希算法的效果，并同本文提出的方法進(jìn)行比較。

Precision表現(xiàn)的是任一查詢樣本對算法返回檢索結(jié)果的正確率的一種評價指標(biāo)，其計算公式如下：

其中，k表示返回k個結(jié)果；Rel(i)∈{0，,1}當(dāng)Rel(i為)1時表示檢索到的數(shù)據(jù)點與查詢樣本相似，即標(biāo)簽相同；當(dāng)Rel(i)為0時表示檢索到的數(shù)據(jù)點與查詢數(shù)據(jù)點不相似，即標(biāo)簽不同。

mAP指標(biāo)可以看作是Precision指標(biāo)的一種加強(qiáng)形式，不僅考察k個檢索結(jié)果的正確率，而且考慮了k個結(jié)果檢索相似性排序?qū)z索優(yōu)劣的影響，其計算公式如式（8）：

其中，Q表示查詢樣本集合，|Q|表示集合元素個數(shù)。ni表示第i個查詢樣本的檢索結(jié)果個數(shù)，該取值為經(jīng)驗值，常見兩種方式：（1）設(shè)定固定值，此時ni與查詢樣本i無關(guān)；（2）根據(jù)式（6）設(shè)定海明距離的閾值，同查詢樣本距離小于等于閾值的樣本個數(shù)，通常由于查詢樣本不同ni取值不同。Rik表示同第i個查詢樣本按照式（6）計算順序敏感的海明距離，并從小到大排序后的前k個被檢索測試樣本。

5.3 實驗和結(jié)果

在本節(jié)中，進(jìn)行3組實驗來驗證本文提出的基于隨機(jī)森林的哈希算法的性能。

第一個實驗在MNIST和CIFAR-10數(shù)據(jù)集上進(jìn)行。分別使用最大深度為6的森林產(chǎn)生12 bit的哈希碼，最大深度為8的森林產(chǎn)生24 bit的哈希碼，最大深度為16的森林產(chǎn)生32 bit和48 bit的哈希碼。返回同查詢樣本海明距離小于等于2的檢索結(jié)果。將本文提出的基于隨機(jī)森林的哈希算法和其他哈希算法，包括局部敏感哈希LSH、迭代量化算法ITQ、譜哈希SH、二值重建嵌入算法BRE、最小損失哈希MLH、ITQ-CCA（iterative quantization-canonical correlation analysis）、核化的有監(jiān)督哈希算法KSH進(jìn)行mAP指標(biāo)比較。檢測測試精度mAP結(jié)果如表1所示。實驗結(jié)果表明，本文方法擁有較好的檢索性能，碼長為32 bit和48 bit時性能最優(yōu)。尤其對于更加復(fù)雜的CIFAR-10數(shù)據(jù)集，性能較其他方法有明顯的提升。圖2中，（a）圖為在MNIST數(shù)據(jù)集上隨著哈希碼長的增加，mAP性能指標(biāo)的變化趨勢，（b）圖為在CIFAR-10數(shù)據(jù)集上隨著哈希碼長的增加，mAP性能指標(biāo)的變化趨勢?？梢灾庇^地看到，本文方法在兩個數(shù)據(jù)集上，都隨哈希碼長的增加逐漸顯示出檢索性能優(yōu)勢，在碼長為32 bit和48 bit時mAP指標(biāo)高于其余算法。值得指出的是，對于本文的方法，是通過增量的方式，獨立添加可預(yù)先訓(xùn)練的決策樹方式增加哈希碼碼長，這是一個代價很低的過程，并可通過增加計算節(jié)點這種并行化處理方式來實現(xiàn)。況且，生成較長的二進(jìn)制哈希碼后，對于機(jī)器指令級別的海明距離計算來說，數(shù)據(jù)檢索的運算時間不會增加太大。因此本文提出的算法具有較高效率與性能。

Table 1 Results of Hash methods on MNIST and CIFAR-10表1 常見哈希方法在MNIST和CIFAR-10上的實驗結(jié)果比較

Fig.2 Results on MNIST and CIFAR-10圖2 MNIST和CIFAR-10上結(jié)果

為了直觀地觀察檢索錯誤的樣本，在MNIST和CIFAR-10數(shù)據(jù)集上還原了檢索Top 10樣本。表2、表3分別顯示了MNIST和CIFAR-10數(shù)據(jù)集下，分別對原始空間樣本映射至24 bit哈希碼和48 bit哈希碼，并分別對某一查詢樣本測試得到的Top 10檢索結(jié)果。其中紅框標(biāo)示的為檢索錯誤的樣本。從結(jié)果可以直觀地看出，錯誤的檢索樣本的確是難于辨認(rèn)類別的模糊樣本。同時，在兩個數(shù)據(jù)集上也都表現(xiàn)出隨著哈希碼長度的增加，返回的檢索結(jié)果逐漸變好，對模糊樣本的辨識能力增強(qiáng)的趨勢。

接下來的實驗中，對本文方法的敏感性進(jìn)行了分析，在MNIST數(shù)據(jù)集上測試了不同參數(shù)下準(zhǔn)確率Precision的變化情況。如圖3所示，（a）圖表示在構(gòu)造隨機(jī)決策樹過程中，選擇不同數(shù)量的隨機(jī)屬性對測試精度的影響，可以看到選擇屬性空間大小將影響檢索精度的變化，總體上說，選擇屬性的空間和哈希碼長對于檢索精度來說呈現(xiàn)正相關(guān)關(guān)系，提示在資源允許的條件下，適當(dāng)放大備選屬性空間并提高哈希碼的長度，都是增強(qiáng)數(shù)據(jù)表示能力和提高檢索精度的正確做法。（b）圖表示決策樹不同深度設(shè)置下，測試精度Precision的變化。實驗結(jié)果顯示構(gòu)建決策樹時選擇不同的特征數(shù)量和深度對結(jié)果有較大的影響，尤其對于較小深度的數(shù)，在空間映射過程需要更多的哈希碼長來增強(qiáng)數(shù)據(jù)的表示能力，才能有更好的檢索精度。

Table 2 Illustration of Top 10 images retrieved by using 24 bit and 48 bit Hash codes on MNIST表2 MNIST上分別使用24 bit、48 bit哈希碼獲得的Top 10檢索結(jié)果示例

Table 3 Illustration of Top 10 images retrieved by using 24 bit and 48 bit Hash codes on CIFAR-10表3 CIFAR-10上分別使用24 bit、48 bit哈希碼獲得的Top 10檢索結(jié)果示例

Fig.3 Sensitivity analysis of proposed method on MNIST圖3 MNIST數(shù)據(jù)集上本文方法的敏感性分析

6 總結(jié)

本文提出了一種基于隨機(jī)森林的哈希算法。利用隨機(jī)森林的性質(zhì)生成具有良好表示能力哈希碼。通過順序敏感的海明距離衡量哈希碼間的相似性，返回檢索結(jié)果。本文算法不僅能夠處理連續(xù)值數(shù)據(jù)，還可以處理離散值數(shù)據(jù)，隨機(jī)森林可以并行部署，極大加快訓(xùn)練和檢索速度，提高了算法效率。實驗結(jié)果表明，本文提出的基于隨機(jī)森林的哈希算法在效率和準(zhǔn)確率上均取得了滿意的結(jié)果。