[發明專利]基于iDistance算法的不確定數據序列K近鄰方法及系統

在審

• 申請號: 202110780363.1
• 申請日: 2021-07-09
• 公開（公告）號: CN113378995A
• 公開（公告）日: 2021-09-10
• 發明（設計）人: 王文標;林瀚
• 申請（專利權）人: 中山大學
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06N20/00
• 代理公司: 廣州粵高專利商標代理有限公司 44102
• 代理人: 劉俊

本發明提出基于iDistance算法的不確定數據序列K近鄰方法及系統，結合了iDistance索引為樣本掃描算法所需讀取的不確定序列數據建立索引；索引后，本方案可以按需對樣本數據進行讀取，有效提升了現有樣本掃描算法在大規模不確定序列數據庫上進行K近鄰查詢的外存性能和速度。

技術領域

本發明涉及數據處理技術領域，具體涉及一種基于iDistance算法的不確定數據序列K近鄰方法及系統。

背景技術

隨著信息采集技術的發展進步和現實應用中需求的不斷增大，不確定數據開始大量地出現。不確定數據已經廣泛存在于各個應用領域，而傳統的針對確定數據的管理和挖掘的技術無法有效地對這些數據進行處理，也就不能滿足現實應用的要求。因此，針對不確定數據的管理和挖掘的問題開始進入人們的視野，并得到越來越多的重視。

K近鄰算法是在數據挖掘與機器學習中一種簡單而常用的監督學習算法，在解決分類問題和回歸問題中都有應用。公開號為CN1538326A的中國發明專利申請于2004年10月20日公開了一種用于視頻片段快速相似查詢的k近鄰方法，其基本步驟為：對待查詢視頻片段中的每一幀，用Ordered VA－File在視頻數據庫找出它的T×k個近鄰，即T×k個相似的視頻幀；然后，將所有查詢結果按照它們在視頻數據庫中出現的先后位置關系排序，如果數據庫中的一幀同時屬于多個查詢幀的T×k的近鄰，記錄下這些幀的幀序號；最后，對該序列進行窗口掃描，返回相似度最大的k個視頻片段。該方案雖然極大地減少了視頻片段相似查詢時磁盤訪問代價和CPU計算代價，但其并不適用于不確定序列模型的K近鄰問題，且在樣本掃描過程中缺乏堆數據集的索引，間接地影響了算法地速度。

發明內容

本發明的目的是針對現有技術存在的缺陷，提供一種能高效解決不確定序列的k近鄰問題的基于iDistance算法的不確定數據序列K近鄰方法及系統。

為解決上述技術問題，本發明的技術方案如下：

基于iDistance算法的不確定數據序列K近鄰方法，包括以下步驟：

S1：獲取待計算的數據集，包括所有不確定序列和查詢序列；

S2：基于iDistance算法選取一組參考點，為數據集建立索引；

S3：計算查詢序列與每個參考點的距離；

S4：初始化當前距離d和選取距離增量deld；

S5：新建以距離distance為鍵值的小頂堆heap1和heap2，heap1用于維護查詢序列的距離d范圍內的樣本的信息，heap2用于維護已從索引中讀取并計算與查詢序列間距離但不在距離d范圍內的樣本的信息；

S6：構建第一數組、第二數組和控制變量，并對第一數組、第二數組和控制變量進行初始化；

S7：構建數據結構并進行初始化；

S8：對heap1、heap2、第一數組、第二數組、數據結構、控制變量進行循環計算更新，最終獲取數據結構中維護的答案。

其中，所述步驟S2具體包括以下步驟：

S21：在數據空間中選取一組參考點ref₁,ref₂,…,ref_refn，用以將空間劃分成多個分區；選取一個遠大于數據點間距的常數c，用以錯開不同分區的數據點計算出的索引鍵值；

S22：基于iDistance算法新建B⁺樹btree；

S23：對數據集D中的每個不確定序列X_i∈D的每個樣本執行以下步驟：

1)計算與每個參考點的距離

2)找出與距離最近的參考點以及對應距離