[發明專利]一種基于哈希學習的在線高維數據最近鄰查詢方法

有效

• 申請號: 201811128413.2
• 申請日: 2018-09-27
• 公開（公告）號: CN109299097B
• 公開（公告）日: 2022-06-21
• 發明（設計）人: 胡偉;錢江波;任艷多;孫瑤
• 申請（專利權）人: 寧波大學
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/2455
• 代理公司: 寧波奧圣專利代理有限公司 33226
• 代理人: 程天鵬

1.一種基于哈希學習的在線高維數據最近鄰查詢方法，其特征在于包括以下步驟：

①圖像數據獲取和預處理：在公開的圖像領域網站獲取包含原始二維圖像的數據集，按照圖像像素信息將該數據集等價轉換成保留原始特征的數值矩陣，并對數值矩陣進行數據清洗和降維處理兩步操作，具體操作過程為：

①-1對獲取的圖像數據進行歸一化操作，維持整體數據的完整性，對離群數值使用分箱、聚類、和回歸進行人工處理，對離群圖像像素數據采用均值代替；

①-2采用SIFT算法提取原始二維圖像中的局部性特征，把圖像中關鍵點定位并確定圖像局部的梯度方向，降低原始二維圖像中的高維數據，然后將原始二維圖像數據集合分為訓練圖像數據庫X＝[x₁,x₂,...,x_i,.x_n]和查詢圖像數據庫Y＝[x₁,x₂,...,x_i,.x_q]，其中x_i為任意一張圖像的d維特征向量，i是數據庫中圖像數據的編號，n是訓練圖像個數，q是測試圖像個數，再將訓練圖像數據庫中的訓練數據設置為流式數據的形式順序傳送；

②定義處理數據的哈希模型：對于給定的原始數據X∈R^d×n，定義映射原始數據的哈希函數為：

其中R^d×n是d行n列的實數矩陣，c是樣本數據的個數，d是樣本數據的維數，W＝[w₁,...w_r]∈R^r×d是哈希投影向量，W^T是W的轉置，R^r×d是r行d列的實數矩陣，r表示投影的維度，是第i個數據的除去均值后的結果，sgn表示取符號函數兩種值{+1，-1}，F是r維度的二進制編碼；

③建立預測損失函數：對于順序收到的流式數據，根據相似或者不相似數據對的標簽，計算對應海明距離的均值，分別統計相似或者不相似數據兩類樣本的閾值，然后根據流式數據對的海明距離和閾值關系，根據任意數據經過哈希函數映射后是否仍然保持相似性的原則，建立判斷更新后的哈希向量是否合理的海明距離預測損失函數：

式中，為海明距離預測函數值，是數據對的海明距離，t為迭代次數，α_g和β_g分別是相似和不相似數據的海明距離閾值，max代表取最大值函數，為數據對的相似標簽，1代表相似，-1代表不相似；

④獲取目標函數：定義原始數據對應的哈希向量為W⁽⁰⁾，t輪次訓練的哈希向量為W^(t)：

式中，為數據對在哈希向量W^(t)的映射下的哈希編碼損失值，為F范數的平方，W^(t-1)表示前一輪訓練的哈希向量，W^(t-n)表示前n輪訓練的哈希向量，m表示選取的中間哈希向量，η為相鄰兩次更新哈希編碼損失差值，當步驟③中預測損失函數值為零時，則判斷經過哈希函數映射后的新數據與原始數據相似性保持一致，將此時的哈希向量W^(t)作為目標函數參數，當步驟③中預測損失函數值非零時，則判斷經過哈希函數映射后的新數據與原始數據相似性未保持一致，則計算下一輪次訓練的哈希向量，并判斷下一數據的相似性，直到找到符合要求的新的數據，并將此時的哈希向量作為目標函數的參數；

⑤優化目標函數：對于目標函數，用隨機梯度下降算法SGD尋找每次迭代過程中當前范圍內的極小值，每次迭代的一對數據隨機選取，從原始數據對應的哈希向量W⁽⁰⁾開始不斷迭代產生新的投影向量，對于每一個投影向量都要沿著梯度下降的方向計算更新，如此往復直至代價函數足夠小為止，即在W維度空間內，不斷向函數減小的方向逼近，直至局部最低點，找到其導數近似為零的W^(*)，即為極小值點，將對應的哈希向量作為目標函數最優值；

⑥測試數據庫查詢：對于待查詢數據點x_i，在查詢圖像數據庫Y中查找近似圖像，首先按照步驟①初步處理待查詢圖像數據，然后選取最新更新的哈希向量組成哈希函數族，把待查詢圖像數據映射到海明空間后，將查詢圖像數據庫Y中的數據集進行海明距離排序比較，根據降序排序篩選出最接近的數據點，作為待查詢圖像數據的反饋結果。