[發(fā)明專利]一種基于哈希學(xué)習(xí)的在線高維數(shù)據(jù)最近鄰查詢方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201811128413.2
• 申請(qǐng)日: 2018-09-27
• 公開（公告）號(hào): CN109299097B
• 公開（公告）日: 2022-06-21
• 發(fā)明（設(shè)計(jì)）人: 胡偉;錢江波;任艷多;孫瑤
• 申請(qǐng)（專利權(quán)）人: 寧波大學(xué)
• 主分類號(hào): G06F16/22
• 分類號(hào): G06F16/22;G06F16/2455
• 代理公司: 寧波奧圣專利代理有限公司 33226
• 代理人: 程天鵬

本發(fā)明公開了一種基于哈希學(xué)習(xí)的在線高維數(shù)據(jù)最近鄰查詢方法，首先設(shè)計(jì)了分別根據(jù)樣本相似或不相似性的預(yù)測(cè)損失函數(shù)并且擴(kuò)寬了損失函數(shù)的范圍，進(jìn)一步設(shè)置了相似或不相似范圍，然后結(jié)合哈希模型需要保持歷史信息同時(shí)需要當(dāng)前數(shù)據(jù)對(duì)損失最小的原則，提出新的目標(biāo)函數(shù)，通過對(duì)在線哈希算法的收斂性進(jìn)行分析，找到目標(biāo)函數(shù)最優(yōu)值。在此基礎(chǔ)上，對(duì)于待查詢數(shù)據(jù)點(diǎn)，能夠快速地查詢到最接近的數(shù)據(jù)點(diǎn)，平均準(zhǔn)確率結(jié)果穩(wěn)定收斂，迭代學(xué)習(xí)過程中哈希函數(shù)的更新大大減少。

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

本發(fā)明涉及一種在線最近鄰查詢方法，尤其是涉及一種基于哈希學(xué)習(xí)的在線高維數(shù)據(jù)最近鄰查詢方法。

背景技術(shù)

近鄰查詢(Nearest Neighbor Search)是信息檢索領(lǐng)域一個(gè)重要的研究方向，在圖像檢索和數(shù)據(jù)挖掘方面均有廣泛應(yīng)用。近鄰查詢常用的技術(shù)主要有基于樹和基于哈希的兩類方法。但是當(dāng)數(shù)據(jù)維度變大時(shí)，基于樹的近鄰檢索的效率會(huì)受到較大限制。而基于哈希的方法則是將原始數(shù)據(jù)通過哈希函數(shù)壓縮成低維的二進(jìn)制編碼，然后在海明距離下排序檢索，因此該方法具有快速高效且維度不敏感的優(yōu)勢(shì)。目前研究較多的哈希方法是將所有數(shù)據(jù)統(tǒng)一訓(xùn)練的批處理方法，這種方法無法處理實(shí)時(shí)的流式數(shù)據(jù)。盡管學(xué)術(shù)界有少量針對(duì)流式數(shù)據(jù)的實(shí)時(shí)在線哈希學(xué)習(xí)方法，但這些方法較多討論的僅僅如何提高平均準(zhǔn)確率。

目前在線哈希學(xué)習(xí)所采用的方法主要包括在線核哈希(Online hashing)、監(jiān)督哈希(Online Supervised hashing)和在線互信息哈希(MIHash Online Hashing)等，新數(shù)據(jù)訓(xùn)練后會(huì)自動(dòng)更新哈希函數(shù)。但是哈希函數(shù)變化會(huì)導(dǎo)致數(shù)據(jù)集映射后的海明編碼發(fā)生改變。為了使得新數(shù)據(jù)和原有數(shù)據(jù)哈希編碼匹配，則需要通過新的哈希函數(shù)計(jì)算重新計(jì)算哈希編碼。但是重新計(jì)算哈希編碼時(shí)的更新迭代過程頻繁，以致隨著數(shù)據(jù)增大計(jì)算開銷需求過大。且上述方法在在線迭代學(xué)習(xí)過程中哈希模型還存在哈希函數(shù)更新頻率較快和哈希模型穩(wěn)定性較弱的問題。原因在于：(1)設(shè)計(jì)損失函數(shù)，在整個(gè)數(shù)據(jù)集上把相似和不相似樣本設(shè)置成統(tǒng)一閾值；(2)僅根據(jù)相鄰兩次投影向量差別盡可能小來更新哈希函數(shù)，無法保證模型的穩(wěn)定性。而在實(shí)際應(yīng)用中，哈希模型更重要的是在何時(shí)能快速迭代出最優(yōu)哈希函數(shù)，以及是否能夠達(dá)到穩(wěn)定收斂的狀態(tài)，而且更新哈希模型過程中也需要更新頻率盡可能少。

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

本發(fā)明所要解決的技術(shù)問題是提供一種基于哈希學(xué)習(xí)的在線高維數(shù)據(jù)最近鄰查詢方法，該方法具有在線最近鄰查詢平均準(zhǔn)確率結(jié)果穩(wěn)定收斂，能夠減少迭代學(xué)習(xí)過程中哈希函數(shù)過于頻繁的更新。

本發(fā)明解決上述技術(shù)問題所采用的技術(shù)方案為：一種基于哈希學(xué)習(xí)的在線高維數(shù)據(jù)最近鄰查詢方法，包括以下步驟：

①圖像數(shù)據(jù)獲取和預(yù)處理：獲取包含原始二維圖像的數(shù)據(jù)集，按照?qǐng)D像像素信息將該數(shù)據(jù)集等價(jià)轉(zhuǎn)換成保留原始特征的數(shù)值矩陣，并對(duì)數(shù)值矩陣進(jìn)行數(shù)據(jù)清洗和降維處理兩步操作；

②定義處理數(shù)據(jù)的哈希模型；；

③建立預(yù)測(cè)損失函數(shù)：對(duì)于順序收到的流式數(shù)據(jù)，根據(jù)相似或者不相似數(shù)據(jù)對(duì)的標(biāo)簽，計(jì)算對(duì)應(yīng)海明距離的均值，分別統(tǒng)計(jì)相似或者不相似數(shù)據(jù)兩類樣本的閾值，然后根據(jù)流式數(shù)據(jù)對(duì)的海明距離和閾值關(guān)系，根據(jù)任意數(shù)據(jù)經(jīng)過哈希函數(shù)映射后是否仍然保持相似性的原則，建立判斷更新后的哈希向量是否合理的海明距離預(yù)測(cè)損失函數(shù)；

④獲取目標(biāo)函數(shù)：當(dāng)步驟③中預(yù)測(cè)損失函數(shù)值為零時(shí)，將此時(shí)的哈希向量作為目標(biāo)函數(shù)參數(shù)，當(dāng)步驟③中預(yù)測(cè)損失函數(shù)值非零時(shí)，則計(jì)算下一輪次訓(xùn)練的哈希向量，并判斷下一數(shù)據(jù)的相似性，直到找到符合要求的新的數(shù)據(jù)，并將此時(shí)的哈希向量作為目標(biāo)函數(shù)的參數(shù)；

⑤優(yōu)化目標(biāo)函數(shù)：對(duì)于目標(biāo)函數(shù)，用隨機(jī)梯度下降算法SGD尋找每次迭代過程中當(dāng)前范圍內(nèi)的極小值，不斷向函數(shù)減小的方向逼近，直至局部最低點(diǎn)，找到其導(dǎo)數(shù)近似為零的極小值點(diǎn)，將對(duì)應(yīng)的哈希向量作為目標(biāo)函數(shù)最優(yōu)值；