[發(fā)明專(zhuān)利]一種面向高維大數(shù)據(jù)集的加權(quán)量化哈希檢索方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201811316883.1
• 申請(qǐng)日: 2018-11-07
• 公開(kāi)（公告）號(hào): CN109634953B
• 公開(kāi)（公告）日: 2021-08-17
• 發(fā)明（設(shè)計(jì)）人: 孫瑤;錢(qián)江波;胡偉;任艷多
• 申請(qǐng)（專(zhuān)利權(quán)）人: 寧波大學(xué)
• 主分類(lèi)號(hào): G06F16/22
• 分類(lèi)號(hào): G06F16/22;G06F16/2458;G06K9/62
• 代理公司: 寧波奧圣專(zhuān)利代理有限公司 33226
• 代理人: 程天鵬

本發(fā)明公開(kāi)了一種面向高維大數(shù)據(jù)集的加權(quán)量化哈希檢索方法，特點(diǎn)是首先利用主成份分析算法分別對(duì)原始高維數(shù)據(jù)和給定查詢數(shù)據(jù)降維，然后根據(jù)成對(duì)保相似性原則并采用松弛后的正交約束條件構(gòu)造損失函數(shù)，通過(guò)最小化該損失函數(shù)得到最終二進(jìn)制編碼矩陣和最終權(quán)重矩陣，根據(jù)最終權(quán)重矩陣和最終二進(jìn)制編碼矩陣獲得加權(quán)后的二進(jìn)制編碼矩陣和與給定查詢數(shù)據(jù)對(duì)應(yīng)的二進(jìn)制編碼，再在加權(quán)后的二進(jìn)制編碼矩陣中查找與給定查詢數(shù)據(jù)對(duì)應(yīng)的二進(jìn)制編碼的加權(quán)海明距離最近的行向量數(shù)據(jù)，完成對(duì)給定查詢數(shù)據(jù)的哈希檢索過(guò)程；優(yōu)點(diǎn)是在構(gòu)造損失函數(shù)時(shí)采用松弛后的正交約束條件，利用加權(quán)海明距離進(jìn)行哈希檢索，能夠更好的提高哈希檢索方法的檢索效率和準(zhǔn)確性。

技術(shù)領(lǐng)域

本發(fā)明涉及一種數(shù)據(jù)檢索方法，尤其是一種面向高維大數(shù)據(jù)集的加權(quán)量化哈希檢索方法。

背景技術(shù)

最近鄰查找一直是計(jì)算機(jī)學(xué)科中的一個(gè)基礎(chǔ)研究問(wèn)題。一般情況下，哈希檢索技術(shù)是能夠解決大規(guī)模高維數(shù)據(jù)檢索的一種有效方法，基于哈希的相似性查詢方法具有良好的查詢性能以及存儲(chǔ)效率，但是現(xiàn)有的大部分哈希方法都認(rèn)為哈希編碼的各維度權(quán)重相同，也就是說(shuō)，直接利用海明距離來(lái)對(duì)兩數(shù)據(jù)之間的相似性進(jìn)行度量；然而在實(shí)際情況中，不同的映射方向選擇能夠?qū)е虏煌姆诸?lèi)效果，對(duì)應(yīng)到哈希編碼上，每一個(gè)維度都攜帶有不同的信息，因此編碼不同維度對(duì)于數(shù)據(jù)之間相似性的影響也不同。

若采用海明距離作為度量標(biāo)準(zhǔn)，雖然對(duì)于數(shù)據(jù)相似性有一定的判斷作用，但不能夠充分的說(shuō)明數(shù)據(jù)之間的距離遠(yuǎn)近，有待改進(jìn)。

發(fā)明內(nèi)容

本發(fā)明所要解決的技術(shù)問(wèn)題是提供一種能夠有效提高哈希檢索方法的檢索效率和準(zhǔn)確性的面向高維大數(shù)據(jù)集的加權(quán)量化哈希檢索方法。

本發(fā)明解決上述技術(shù)問(wèn)題所采用的技術(shù)方案為：一種面向高維大數(shù)據(jù)集的加權(quán)量化哈希檢索方法，包括以下步驟：

①獲取由n個(gè)原始高維數(shù)據(jù)組成的原始高維數(shù)據(jù)集X并給定查詢數(shù)據(jù)q，X為n×d維的矩陣，q為1×d維的向量，使用主成份分析算法對(duì)X進(jìn)行降維，得到與X對(duì)應(yīng)的低維向量集V，其中，V為n×c維的矩陣，c＜d，v_ij表示原始高維數(shù)據(jù)中第i個(gè)數(shù)據(jù)第j維度在V中對(duì)應(yīng)的低維向量元素，1≤i≤n，1≤j≤c，再使用主成份分析算法對(duì)q進(jìn)行降維，得到與q對(duì)應(yīng)的1×c維的低維向量q'；

②通過(guò)迭代獲取最終二進(jìn)制編碼矩陣B″和最終權(quán)重矩陣W”，具體過(guò)程如下：

②-1設(shè)定最大迭代次數(shù)，隨機(jī)給定初始二進(jìn)制編碼矩陣B，B∈{-1,1}^n×c，隨機(jī)給定初始權(quán)重矩陣W，W＝diag(w₁，w₂，…w_j…，w_c)，其中，w_j表示第j維度的維度權(quán)重，diag()表示對(duì)角矩陣；

②-2根據(jù)哈希函數(shù)構(gòu)造原理中的成對(duì)保相似性原則構(gòu)造損失函數(shù)，再引入完全正交約束條件，將完全正交約束條件進(jìn)行松弛化操作，從而構(gòu)造出損失函數(shù)其中，|| ||_F為取矩陣的F-范數(shù)符號(hào)，中的2為平方符號(hào)，B^T表示B的轉(zhuǎn)置矩陣，I表示單位矩陣；

②-3開(kāi)始迭代過(guò)程，在當(dāng)前一次迭代過(guò)程中，首先保持W不變，對(duì)進(jìn)行最小化求解，利用梯度下降法對(duì)B進(jìn)行更新，將最小時(shí)更新得到的B記為B′，b_ij表示X中第i個(gè)原始高維數(shù)據(jù)第j維度的元素在當(dāng)前一次迭代過(guò)程中對(duì)應(yīng)的更新后的二進(jìn)制編碼值；

再保持B'不變，通過(guò)對(duì)進(jìn)行最小化求解對(duì)W進(jìn)行更新，將最小時(shí)更新得到的W記為W'；

②-4判斷當(dāng)前迭代過(guò)程的迭代次數(shù)是否達(dá)到設(shè)定的最大迭代次數(shù)，若未達(dá)到最大迭代次數(shù)，則令W＝W'，B＝B′，返回步驟②-3開(kāi)始下一次迭代過(guò)程，同時(shí)迭代次數(shù)加1，其中W＝W'和B＝B′中的“＝”為賦值符號(hào)；若達(dá)到最大迭代次數(shù)，則將當(dāng)前一次迭代過(guò)程中更新得到的W'作為最終權(quán)重矩陣W”，將當(dāng)前一次迭代過(guò)程中更新得到的B′作為最終二進(jìn)制編碼矩陣B″；