隨機結構保形哈希信息檢索方法
2023-06-05 08:03:16
隨機結構保形哈希信息檢索方法
【專利摘要】本發明涉及一種隨機結構保形哈希信息檢索方法，其特徵在於步驟包括：一是保護高維數據的重要結構，使用提出目標函數對原始的高維數據進行降維，從而得到低維數據；二是使用已經得出的基算子U和低維數據V的更新規則，計算出原始高維數據的基和低維矩陣；三是設置門限值並且把訓練集中低維實數表現轉換成二進位碼，用概率統計分類模型邏輯回歸計算出測試樣本的哈希碼；四是計算訓練數據和測試樣本之間的漢明距即XOR運算，得出最終的結果。本發明能夠在很好地保護隨機數據的分布和高維數據的局部及總體結構的基礎上，成功地應用多變量的邏輯回歸來獲得哈希函數，可實現超越樣本的拓展，適用於計算機視覺、數據挖掘、機器學習或相似搜索領域。
【專利說明】隨機結構保形哈希信息檢索方法
【技術領域】
[0001] 本發明屬於計算機信息數據處理【技術領域】，特別是涉及一種用於計算機視覺、數 據挖掘、機器學習或相似搜索的隨機結構保形哈希信息檢索方法。
【背景技術】
[0002] 在信息檢索、機器學習、模式識別和數據挖掘中相似性搜索是一個需要解決的問 題。一般來說，有效的相似性搜索方法會在度量空間中建立索引結構，早期的關於相似性搜 索的研究可以追溯到20世紀70年代。具體的說，當維度較低< 20時，一些基於數據結構的 方法如KD-樹、VP-樹和R+樹等可以解決相似性搜索的問題。然而，隨著數據維度的增長， 在信息數據處理領域中如何有效地實現相似性搜索問題的難度不斷上升。現有採取"近似 值"的概念來解決相似性搜索問題的方法，如為了提高檢索效率，哈希算法需要得到一個從 歐幾裡德空間到漢明空間的哈希函數，利用二進位編碼的哈希算法只要包含兩個優勢：一 是二進位哈希碼節約了儲存空間；二是在相似性搜索的檢索過程中可以有效地計算訓練數 據和測試樣本之間的漢明距（X0R運算）、哈希表中的時間複雜度近似為0(1)。
[0003] 現有的哈希算法大體上可被分為基於隨機投影和基於學習的兩種。局部敏感哈希 (LSH)是廣泛應用的基於隨機線性投影的哈希算法，可以有效地把數據點從高維空間映射 到低維漢明空間；基於核的局部敏感哈希（KLSH)和加強多核的局部敏感哈希（BMKLSH)為 了更好的檢索效率可以在核空間中挖掘更多的相似性。為了尋找高維空間中測試點的相似 最近鄰，Panigrahy提出了 了一種基於熵的哈希算法。Dong提出了基於統計特性模型的多 探索局部敏感哈希，這是目前局部敏感哈希最好的變化。此外，Raginsky和Lazebnik用基 於隨機映射的自由分布的編碼方案來確保兩個向量和向量中偏移不變核的數值的二進位 碼的漢明距的關係。
[0004] 只有當二進位哈希碼足夠長的時候，基於隨機投影的哈希函數才會有效。因此，為 了獲得更加緊湊和準確的編碼，許多基於學習的哈希算法被提出。通過挖掘數據的結構，然 後表現在目標函數上，通過解決和目標函數相關的優化問題，基於學習的哈希算法可以獲 得哈希函數。譜哈希（SpH)是典型的非監督哈希算法，通過促使平衡的和不相關的約束對 學習過的碼，譜哈希可以學習到緊湊的二進位碼並且保護數據中的相似性。主成分分析哈 希（PCAH)相對於隨機映射哈希可以獲得更好的量化。此外，基於受限波爾茲曼機的語義哈 希（SH)被提出。Liu等人提出了可以自動發現數據近鄰內部結構的基於圖像的哈希算法， 同時可以學習到相應的緊湊的碼，錨狀圖可加速譜分析的過程。近來有基於超球面的二進 制植入技術球形哈希（Spherical Hashing)被提出.這個算法可以提供緊湊的數據形式和 拓展的最近鄰搜索。
[0005] 然而，以上提到的哈希方法都存在一定的缺陷。雖然基於隨機映射的哈希方法可 以產生緊湊的碼，但是簡單的線性哈希函數卻不可以映射出數據點之間潛在的關係。同時， 因為線形的公式是由高維矩陣計算而得到的，這會帶來很高的計算複雜度。另外，當碼字十 分長的時候，基於學習的哈希算法不會很有效。除此之外，那些先降低原始數據維度的哈希 方法不能獲得有著很好結構的低維數據結果。
[0006] 近年來作為可以學習物體非負部分形式的矩陣分解算法，非負矩陣分解（NMF) 在信息檢索和數據挖掘中起了重要的作用。如一個有著M個N維數據向量的非負矩陣 x=Ps^，1Vl 。可以被N1f分解成兩個非負矩陣U= [UJ GRmxd和V= [UjJ eR_， 其結果可以很好地估計原始矩陣，如X?UV。Lee和Seung也提出了兩個目標函數去評估 兩個非負矩陣X和UV之間的距離，基於差異的目標函數可以被表示成：
[0007]
【權利要求】
1. 一種隨機結構保形哈希信息檢索方法，其特徵在於它包括如下具體步驟： 步驟1 :保護高維數據的重要結構，使用提出目標函數對原始的高維數據進行降維，從 而得到低維數據； 步驟2 :使用已經得出的基算子U和低維數據V的更新規則，計算出原始高維數據的基 和低維矩陣； 步驟3 :設置門限值並且把訓練集中低維實數表現轉換成二進位碼，用概率統計分類 模型邏輯回歸計算出測試樣本的哈希碼； 步驟4 :計算訓練數據和測試樣本之間的漢明距即XOR運算，得出最終的結果。
2. 根據權利要求1所述的一種隨機結構保形哈希信息檢索方法，其特徵在於步驟1中 所述的保護高維數據的重要結構，使用提出目標函數對原始的高維數據進行降維，從而得 到低維數據，是指建立最小化高維空間的聯合概率分布和低維空間重尾分布的聯合概率分 布的KL散度： C=AKL(PllQ) (3)， 公式（3)中，P是高維空間的聯合概率分布，同時可以被表示成Pi^Q是低維空間的聯 合概率分布，同時可以被表示成qu;具體步驟包括： 步驟I. 1 :條件概率Pu表示了數據點Xi和\之間的相似性，其中Xi與它們的概率密 度成比例；只有重要的點需要去塑造成對的相似性，因此把Pii和設為〇;同時對V i，j 都有屬性Pu = Pm和％ = q# ;在高維空間中的兩兩相似性可以表示為：
步驟1. 2 :其中〇 i表示了在數據點Xi正中心的高斯分布的變量，每一個數據點Xi都有 相應的複雜度，在低維的圖上使用重尾的概率分布，聯合概率％可以被定義成：
公式（5)定義是高斯的無限混合，由於沒有指數項，會比單獨的高斯更快的估計點的 密度；建立基於KL散度的成本函數公式（6)可以有效地評估數據分布的重點； 步驟1. 3 :α;;和可以：
公式（6)中P和Q之間的KL散度的梯度可以表示為：
步驟I. 4:通過結合公式（3)中的數據結構保護部分和NMF，得到下面的新的目標函 數： of = I |x-uv| |2+akl(p| |q) (8)， 此處V e {〇, 1}DXN，X，U，V彡0, U e RMXD，X e Rmxn，同時λ可以控制新的表徵的平滑 度； 在大多數情況下，只使用NMF的低維數據對實際應用而言不是那麼有效和有意義，為 了在信息檢索中獲得更好的結果，需要引入XKL(p| IQ)去保護原始數據的結構。
3.根據權利要求1所述的一種隨機結構保形哈希信息檢索方法，其特徵在於步驟2中 所述的使用已經得出的基算子U和低維數據V的更新規則，計算出原始高維數據的基和低 維矩陣，是指包括如下優化過程的具體步驟： 步驟2. 1 :公式（8)的離散條件V e {0，1}DXN在優化過程中無法被直接計算出，為了得 到實數值，首先把數據V e {〇, 1}DXN放到域V e Rdxn上； 步驟2. 2:然後將問題中的拉格朗日函數設為：
公式（9)中的矩陣Φ和Ψ是兩個拉格朗日乘數矩陣，由此得到g的梯度： J-'
UlM; 步驟2. 3 :讓X的梯度為0去最小化Of :
步驟2. 4 :除上述外，有KKT條件：OijUij = 0和WijVij = 0, V i，j;然後，分別在公 式（11)和公式（12)的兩邊的相應位置乘上Vij和Uij，可以得到： (2 (-UTX+UTUV)+G) JjVij = 0, (13), 2 (-XVT+UVVT) JjUij = 0 (14)， 其中：
步驟2. 5 :對任意的i和j有以下的更新規則：
其中：U和V中的所有元素都是正數，且U或者V的每一次更新目標函數的單調不增性。
4.根據權利要求1所述的一種隨機結構保形哈希信息檢索方法，其特徵在於步驟3中 所述的設置門限值並且把訓練集中低維實數表現轉換成二進位碼，用概率統計分類模型邏 輯回歸計算出測試樣本的哈希碼，是指通過如下具體步驟來形成哈希函數： 步驟 3. 1 :基 U= [uid] e Rmxd 和低維矩陣 V= [ujd] e Rdxn，其中 d<< Di, i = 1，...， n，從公式（15)和公式（16)中獲得，然後需要設置門限值並且把低維實數表現V= [V1，…， vn]轉換成二進位碼，如果在向量Vn中的第f個元素比門限值大，這個實數值就設為1，否則 為 〇,其中 f=l，···，(!並且 η = 1，*··，Ν; 步驟3.2 :從信息量的原則可知，通過一個均勻的概率分布，信源可以到達一個最大的 熵；尤其的，如果在數據上的碼的熵很小，整個文件會被映射到一小部分的碼上；為確保語 義哈希的效率，使語義哈希算法做到熵最大化，並且滿足熵最大化原則，運用V p的中值作為 Vp中元素的門限值，有一半數值會被設為1，另外一半設為0,通過該方法將實數碼計算成二 進位碼； 步驟3.3 :從以上的過程，可得到訓練集中數據的二進位碼；為使一個新的樣 本，直接得到哈希函數，在所述方法中，由於二進位碼的環境，在測試樣本中使用概 率統計分類模型-邏輯回歸來計算哈希碼；在得到邏輯回歸函數之前，把二進位 碼表示成V = …，其中V,, € ?〇· 1}'並且η = 1，…，N ;由此訓練樣 本表示為?
y為1或者為O ;相關的回歸矩陣函數被定義為：
其中1是NXl的矩陣、δ I I Θ I I2為邏輯回歸中避免過擬合的正則化項； 步驟3. 4 :為了找到可以最小化J (Θ)的參數Θ，使用梯度下降和反覆更新每一個參數 的方式，更新公式如下：
更新公式會當Op1和之間的差異I I Θμ-Θ」I2到達收斂，然後得到回歸矩陣〇 ; 步驟3.5 :最後通過線形映射矩陣#7飛「廣得到實數的低維表示，因為h0是 sigmoid函數，對於新的樣本的哈希碼表示為： I "r. = [lie(Q -A )； ⑵） 其中：表示了對每一個110的輸入都取最近的整數函數，定義二進位的門限值為 0. 5;如果來自h0(Q*X)的比特大於0.5,會表示為1，否則為0;由此獲得訓練樣本和測試 樣本的SSPH碼，其中SSPH的檢索方法流程表示如下： 隨機結構保形哈希檢索方法（SSPH)，輸入： 一組訓練矩陣：X = (Xi E RdKW; d是哈希碼的目標維度； 對邏輯回歸的學習率α ; 正則化參數{ δ , λ }; 輸出：基矩陣U和回歸矩陣θ ; 一是用公式（15)和公式（16)計算基矩陣U和低維矩陣V ; 二是直到收斂； 三是從公式（20)中獲得回歸矩陣〇,對一個樣本的SSPH編碼在公式（21)中定義。
5.根據權利要求1所述的一種隨機結構保形哈希信息檢索方法，其特徵在於步驟4中 所述的計算訓練數據和測試樣本之間的漢明距即XOR運算，得出最終的結果，是指如下的 複雜度計算分析： 隨機結構保形哈希檢索方法（SSPH)的計算複雜度包含3個部分，第一部分是計算 NMF，計算複雜度為O(NMKD)，N是資料庫的大小，M和D分別是高維數據和低維數據的維 度，K是資料庫中類的個數；第二部分是計算目標函數中的成本函數（公式6)，計算複雜度 為0 (N2 D);第三部分是邏輯回歸過程，複雜度為0 (ND2);因此，SSPH的整個計算複雜度為 0(tNMKD+N2D+tND 2)，其中t為迭代的次數。
【文檔編號】G06F17/30GK104376051SQ201410604395
【公開日】2015年2月25日 申請日期:2014年10月30日 優先權日:2014年10月30日
【發明者】邵嶺, 蔡子贇, 劉力, 餘孟洋 申請人:南京信息工程大學