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

在審

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

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

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

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

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

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

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

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

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

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

2.根據權利要求1所述的基于iDistance算法的不確定數據序列K近鄰方法，其特征在于，所述步驟S2具體包括以下步驟：

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

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

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

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

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

3)計算樣本的索引鍵值key＝pid*c+dis；

4)以key為鍵值將樣本數據插入到btree中。

3.根據權利要求2所述的基于iDistance算法的不確定數據序列K近鄰方法，其特征在于，在所述步驟S3中，計算查詢序列Q與每個參考點ref_refi的距離disref_refi＝dist(Q,ref_refi)；在所述步驟S6中，構建并初始化長度為N的第一數組scanned和第二數組res，使其所有元素為0；初始化變量logp＝N*ln m；在所述步驟S7中，構建并初始化大小為k的數據結構answer；

所述步驟S8中，具體循環計算以下步驟：

S81：若堆heap1為空，更新heap1；

S82：若彈出heap1堆頂元素(i,dis)；

S83：計算當前樣本對其所屬的不確定序列的最鄰近概率P_NN(Q,X_i)的貢獻，將其更新累加到res數組的對應元素res[i]中；

S84：以(i,res[i])更新數據結構answer；

S85：更新數組scanned的對應元素使scanned[i]+＝1；

S86：判斷scanned[i]是否與m相等，若相等，則跳出循環結束掃描過程；

S87：更新變量logp+＝ln(m-scanned[i])-ln(m-scanned[i]+1)；

S88：從數據結構answer中獲取第k大與第k+1大之間的差值diff，判斷diff＞exp(logp-N*ln m)是否成立，若是，則跳出循環結束掃描過程。