[發明專利]一種基于鄰居表的KNN改進算法及其裝置

在審

• 申請號: 202211299690.6
• 申請日: 2022-10-24
• 公開（公告）號: CN115577298A
• 公開（公告）日: 2023-01-06
• 發明（設計）人: 何希;陳佳;農健;呂美妮;陳聰;王銀清;徐健;龐安隆
• 申請（專利權）人: 梧州學院
• 主分類號: G06F18/2413
• 分類號: G06F18/2413;G06F18/2431
• 代理公司: 廣州三環專利商標代理有限公司 44202
• 代理人: 楊振鵬

本發明提供一種基于鄰居表的KNN改進算法及其裝置，該方法包括判斷指定搜索區域的長寬比是否小于預設值；如是，則將指定搜索區域作為搜索范圍，根據預先設定好的閾值建立四叉樹模型；根據所建立的四叉樹模型所劃分的結點區域，通過空間位置找到每一個結點直接相鄰的所有鄰居結點，并行構建鄰居表，其中，該鄰居表用于在查找近鄰點時快速確定有效搜索范圍；確定給定點所在的葉子結點區域；基于查詢鄰居表的結點區域確定有效的搜索范圍；基于有效的搜索范圍，并行計算該范圍內所有點與給定點的距離，從而找出多個近鄰點。本發明用以解決目前現有算法中存在的復雜度高、執行效率低等各種問題，適合在GPU上大規模并行執行，執行效率高，并行性高。

技術領域

本發明涉及數據算法技術領域，具體涉及一種基于鄰居表的KNN改進算法以及應用于該算法的裝置。

背景技術

K最近鄰(K-Nearest Neighbor，KNN)分類算法，是一個理論上比較成熟的方法，其思路為：在特征空間中，如果一個樣本附近的K個最近(即特征空間中最鄰近)樣本的大多數屬于某一個類別，則該樣本也屬于這個類別。針對KNN問題或者K近鄰問題：給定一個數據集以及一個點，從數據集中找到距離給定點最近的K個數據，其在圖像分類、信息獲取、模式識別等方面有廣泛的應用價值。

然而，針對在指定的平面區域內為一個特定的點查找距離最近的K個點的問題，現有KNN算法在搜索區域中點的空間分布密度和有效搜索范圍方面欠缺考慮，導致時間復雜度高；且此類算法不適合在GPU上大規模并行執行，故執行效率低。

發明內容

本發明提供一種基于鄰居表的KNN改進算法及其裝置，用以解決現有算法中存在的復雜度高、執行效率低等各種問題。

第一方面，本發明提供的一種基于鄰居表的KNN改進算法，該方法包括：

判斷指定搜索區域的長寬比是否小于預設值；

如是，則將指定搜索區域作為搜索范圍，根據預先設定好的閾值建立四叉樹模型；

根據所建立的四叉樹模型所劃分的結點區域，通過空間位置找到每一個結點直接相鄰的所有鄰居結點，并行構建鄰居表，其中，該鄰居表用于在查找近鄰點時快速確定有效搜索范圍；

確定給定點所在的葉子結點區域；

基于查詢鄰居表的結點區域確定有效的搜索范圍；

基于有效的搜索范圍，并行計算該范圍內所有點與給定點的距離，從而找出多個近鄰點。

根據本發明提供的一種基于鄰居表的KNN改進算法，所述根據預先設定好的閾值建立四叉樹模型，包括：使用四叉樹方式逐層劃分空間區域，先將初始空間區域劃分為四個子區域，若子區域中點的數量大于預先設定好的閾值，則將該子區域進一步劃分為四個更小的子區域，并按此方式不斷遞歸，直至每個子區域中點的數量都不超過預先設定好的閾值，以確保每個葉子結點區域中點的分布密度相對均勻。

根據本發明提供的一種基于鄰居表的KNN改進算法，在建立四叉樹模型的過程中，對每個子區域的邊界點坐標進行存儲，以及對包含的所有數據點的空間位置和數量等信息進行存儲，從而將指定區域中的所有數據點相應地劃分到四叉樹模型的葉子結點對應的區域中，以確保每個葉子結點區域中點的分布密度相對均勻。

根據本發明提供的一種基于鄰居表的KNN改進算法，所述確定給定點所在的葉子結點區域，包括：根據給定點的空間位置，查找確定其所屬四叉樹中的葉子結點，即確定其所在葉子結點區域；若該葉子結點中點的個數K值，則將其作為查詢鄰居表的結點；若該葉子結點中點的個數K值，則將其父結點作為查詢鄰居表的結點。

根據本發明提供的一種基于鄰居表的KNN改進算法，所述基于查詢鄰居表的結點區域確定有效的搜索范圍，包括：