[發明專利]一種基于學習索引的KNN查詢方法

有效

• 申請號: 202211701214.2
• 申請日: 2022-12-28
• 公開（公告）號: CN115858629B
• 公開（公告）日: 2023-06-23
• 發明（設計）人: 黎玲利;韓奧
• 申請（專利權）人: 黑龍江大學
• 主分類號: G06F16/2458
• 分類號: G06F16/2458;G06F16/22;G06N3/08;G06F18/214;G06F18/2413;G06N3/0464
• 代理公司: 哈爾濱市松花江聯合專利商標代理有限公司 23213
• 代理人: 岳昕

一種基于學習索引的KNN查詢方法，為解決計算機數據在進行KNN查詢時，學習索引具有局限性，靈活性低的問題，按照Zipfian分布將計算機數據劃分為訓練集和測試集；利用傳統索引將數據集的數據空間劃分為y個不重疊的分區，并得到所有訓練數據及其對應的分區；利用所有訓練數據及其對應的分區訓練深度學習模型，得到模型；選取訓練數據對應的概率最大的T個分區，并獲得與訓練數據真實K近鄰的k個點，在訓練數據和每個點與每個分區之間分別建立一條帶權重的邊；根據權重大小先對點排序，再對每個點的邊排序，得到精化分區；將測試集中某條測試數據執行上述操作，找到距離測試集中某條測試數據最近的K個點，即為某條測試數據的KNN結果。

技術領域

本發明涉及一種KNN查詢方法，具體涉及一種基于學習索引和深度學習的KNN查詢方法，屬于計算機領域。

背景技術

處理高維空間中海量數據的KNN搜索是一個經典的值得研究的問題。在計算機的海量數據中，設D是d維空間中容量為n的數據集，給定一個d維空間中的查詢數據點q，KNN問題返回給定距離度量下在數據集D中到q最近的K個數據。KNN算法一般分為兩類：精確查詢和近似查詢。精確查詢顧名思義查詢準確率為百分百，前人也提出過許多經典的基于樹的索引結構：K-D?tree,M?Tree,R?tree等。在d很小的時候(如d20),可以使用樹形索引(如K-D樹)進行計算機的數據查詢，但是在實踐中，近似鄰搜索問題通常在高維向量中進行，維度一般在100-1000，然而隨著維度的增加，這些傳統的索引結構會出現“維度詛咒”現象。

為了獲得理想的數據檢索效果與可接受的檢索時間，學者們提出近似最近鄰搜索方法，以降低查詢精度為代價，加快查詢時間，并在一定程度上緩解了“維度詛咒”問題。方法主要分為兩類：一類是基于提升搜索結構性能的方法，方法大多基于樹形結構；另一類主要基于對數據本身的處理，包括哈希算法、矢量量化方法等。

最近，利用機器學習處理問題已成為一個新興的研究方向。谷歌的研究表明，在某種程度上，機器學習模型的使用可以取代一些傳統的索引結構，并可以學習數據分布。機器學習在處理特征向量時具有更快的運行速度，同時傳統的索引結構可以被視為分類問題，在本質上這與神經網絡可以完成的工作沒有區別。但是當前的學習索引主要關注于某種特定索引結構的點和范圍查詢，導致學習索引具有局限性，靈活性低。

發明內容

本發明為了解決計算機數據在進行KNN查詢時，當前的學習索引主要關注某種特定索引結構的點和范圍查詢，導致學習索引具有局限性，靈活性低的問題，進而提出了一種基于學習索引的KNN查詢方法。

它包括以下步驟：

S1、獲取一定數量的計算機數據作為數據集，按照Zipfian分布將計算機數據劃分為訓練集和測試集；

S2、利用傳統索引將數據集的數據空間劃分為y個不重疊的分區，并得到訓練集中每個訓練數據的KNN所在的分區，如果當前分區有KNN結果，則當前分區標簽對應位置置為1，否則置為0，得到所有訓練數據及其對應的分區；

S3、建立深度學習模型，利用所有訓練數據及其對應的分區對深度學習模型進行訓練，輸入訓練數據，輸出訓練數據在對應分區的概率，得到訓練好的深度學習模型；

S4、選取訓練數據對應的概率最大的T個分區，并獲得與訓練數據真實K近鄰的k個點，在訓練數據和每個分區之間建立一條帶權重的邊，在每個點與每個分區之間建立一條帶權重的邊；

將訓練數據與對應的k個點作為一個集合，得到集合中每個點到各個分區的邊的權重，以及每個點的總權重，根據每個點的總權重從大到小對集合中的點進行排序，得到排序后的點，根據排序后的點，將與每個點相連的各個邊按照邊的權重從大到小進行排序，根據邊的排序結果將點分配到權重最大的分區內，如果權重最大的分區內數據容量達到給定閾值，則將點分配到權重次大的分區內，直到所有點分配到分區內，得到精化后的分區；