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

在審

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

1.一種基于鄰居表的KNN改進算法，其特征在于，包括：

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

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

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

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

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

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

2.根據權利要求1所述的方法，其特征在于：

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

3.根據權利要求2所述的方法，其特征在于：

在建立四叉樹模型的過程中，對每個子區域的邊界點坐標進行存儲，以及對包含的所有數據點的空間位置和數量等信息進行存儲，從而將指定區域中的所有數據點相應地劃分到四叉樹模型的葉子結點對應的區域中。

4.根據權利要求3所述的方法，其特征在于：

所述確定給定點所在的葉子結點區域，包括：根據給定點的空間位置，查找確定其所屬四叉樹中的葉子結點，即確定其所在葉子結點區域；若該葉子結點中點的個數K值，則將其作為查詢鄰居表的結點；若該葉子結點中點的個數K值，則將其父結點作為查詢鄰居表的結點。

5.根據權利要求4所述的方法，其特征在于：

所述基于查詢鄰居表的結點確定有效的搜索范圍，包括：

初步確定搜索范圍；基于查詢鄰居表的結點到鄰居表中進行查詢，查找與該結點直接相鄰的鄰居結點，將這些結點作為初步的第一搜索范圍。

6.根據權利要求5所述的方法，其特征在于：

在初步確定第一搜索范圍后，基于給定點到查詢鄰居表的結點邊界的最遠距離作為搜索半徑，基于第一搜索范圍內的結點到鄰居表中進行查詢，查找與這些結點直接相鄰的鄰居結點，并將處于或部分處于搜索半徑內的結點作為第二搜索范圍；

基于第一搜索范圍和第二搜索范圍，從而確定有效搜索范圍。

7.根據權利要求6所述的方法，其特征在于：

基于有效搜索范圍，采用多個線程并行計算該范圍內所有點與給定點的距離，即可按照距離排序找到距離給定點最近的K個點。

8.根據權利要求1至7任一項所述的方法，其特征在于：

在針對在指定的平面區域內為一個特定的點查找距離最近的K個點時，設置四叉樹模型結點閥值大于K值，當按照搜索半徑確定有效搜索范圍時，若給定點的所在結點區域包含的數據點數量小于K，則以其父結點作為查詢鄰居表的結點，以確保給定點的K個最近鄰點都已包含在有效搜索范圍中。

9.根據權利要求1至7任一項所述的方法，其特征在于：

所述判斷指定搜索區域的長寬比是否小于預設值，包括：假設某個葉子結點所代表區域的長與寬分別為x，y，則搜索半徑最長為該葉子結點所代表區域的斜邊長，即由于搜索半徑不大于該葉子結點的兩倍長或者兩倍寬，即不等式表示為或者化簡后可以得到3*x²≥y²或者3*y²≥x²，也就是y:或者x:

10.一種基于鄰居表的KNN改進算法裝置，其特征在于，包括：

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

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

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

結點區域確定單元，用于確定給定點所在的葉子結點區域；

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

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