基于隨機森林的哈希檢索算法*

花 強，郭欣欣，張 峰，董春茹

河北大學 河北省機器學習與計算智能重點實驗室，河北 保定 071002

1 引言

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

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

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

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

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

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

2 相關工作

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

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

基于樹型的近似最近鄰搜索是一種廣泛應用的數據檢索方式，它的本質原理是對數據特征空間區域進行層次劃分，搜索數據時在劃分好的層次空間上進行檢索。這種方法可以縮小搜索的范圍，加快搜索的速度。基于樹的近似近鄰搜索算法包括KD樹[23]和R樹[24]等。KD樹在搜索空間中不斷將父節點包含的區域分為相鄰的兩部分，每部分包含原來區域中的一半點。檢索時從根節點開始在每個分叉點上對目標點進行計算，直到葉節點。R樹將數據分成不同層次的數據區，每個數據區表示為區內所有數據的最小外接矩陣。在進行高維數據索引時，首先根據R樹的分層結構查找到可以包含目標數據的葉子節點，然后再遍歷葉子節點中的數據，獲取相似的節點。在低維空間時，基于樹的方法可以很高效地獲取相似的數據，取得很好的檢索速度和檢索精度。但是隨著數據維度的增加，基于樹的檢索速度越來越慢，甚至退化為暴力搜索。

3 基于隨機森林的哈希碼生成

本章主要介紹隨機森林的構建過程以及如何將隨機森林轉化成哈希碼。

3.1 隨機森林的構建

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

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

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

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

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

CART算法構建決策樹的過程中，計算每個特征t劃分數據集獲得的基尼系數，找到使劃分后基尼系數最小的特征作為節點的屬性創建節點，然后在樹的每個分枝上重復該過程，直到達到決策樹設定的最大深度即停止生長，完成決策樹的構建。算法流程可歸納如下：

算法1構建CART樹

輸入：訓練集X，隨機選擇屬性的個數T，決策樹最大深度D。

輸出：CART樹。

步驟1隨機選擇含T個屬性的訓練樣本子集?；

步驟2計算當前數據集基尼系數Gini()；

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

步驟4按照劃分屬性將當前數據集進行劃分；

步驟5對每個子節點遞歸地調用步驟2、3、4，直到樹深度為D或樣本子集中的數據類別相同。

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

3.2 基于隨機森林生成哈希碼

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

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

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

算法2由隨機森林生成哈希碼

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

輸出：全哈希碼。

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

步驟2每棵樹返回一條路徑對應的二進制碼；

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

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

4 順序敏感的海明距離

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

海明距離是度量二進制編碼相似性的常用方法。設兩個D位二進制編碼為，則傳統海明距離的計算方法如下式：

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

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

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

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

5 實驗與結果

5.1 數據集

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

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

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

5.2 性能度量指標

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

Precision表現的是任一查詢樣本對算法返回檢索結果的正確率的一種評價指標，其計算公式如下：

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

mAP指標可以看作是Precision指標的一種加強形式，不僅考察k個檢索結果的正確率，而且考慮了k個結果檢索相似性排序對檢索優劣的影響，其計算公式如式（8）：

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

5.3 實驗和結果

在本節中，進行3組實驗來驗證本文提出的基于隨機森林的哈希算法的性能。

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

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

Fig.2 Results on MNIST and CIFAR-10圖2 MNIST和CIFAR-10上結果

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

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

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檢索結果示例

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檢索結果示例

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

6 總結

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