[發明專利]一種針對K-NN算法臨近點查找的優化方法及裝置

在審

• 申請號: 202011203337.4
• 申請日: 2020-11-02
• 公開（公告）號: CN112464988A
• 公開（公告）日: 2021-03-09
• 發明（設計）人: 周培爍
• 申請（專利權）人: 蘇州浪潮智能科技有限公司
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 濟南舜源專利事務所有限公司 37205
• 代理人: 張營磊

本發明提供一種針對K?NN算法臨近點查找的優化方法及裝置，所述方法步驟：獲取已有數據集合中確定元素數量及待分類元素，所述確定元素數量為已有數據集合中元素總數量減去待分類元素的數量；根據已有數據集合中確定元素數量及應用需求定義臨近數量K，并創建一個長度為臨近數量K的數組；計算已有數據集合中K個確定元素與待分類元素的距離，并將K個距離值依次存儲到創建的數組中；獲取已有數據集合中剩余確定元素，計算剩余確定元素與待分類元素的距離，將距離值依次與數組中最大距離值進行比較，進行數值替換；統計數組中距離值對應確定元素所屬類別及各類別對應確定元素數量，并設定確定元素數量最大的類別為待分類元素的類別。

技術領域

本發明屬于數據分類統計處理技術領域，具體涉及一種針對K-NN算法臨近點查找的優化方法及裝置。

背景技術

隨著大數據的廣泛應用以及機器學習技術的迅速發展，對數據的分類統計處理效率要求也越來越高，在此背景下，K-NN歸類算法因其精度高、對異常值不敏感、無數據輸入假定等優點被各個領域廣泛應用。應用K-NN算法的主要目的是對一個基準值進行歸類預測，例如，目前共有n個數據分為Ⅰ，Ⅱ兩類，要對基準值A進行歸類，此時便可應用該算法對數據進行處理。具體歸類思想如下：找出K(Kn)個與基準值A臨近的點(以下簡稱臨近點)，在這K個值中，Ⅰ，Ⅱ哪類數據占比較大，即將A歸為哪類。相當于一個通過周圍大多數的數值特性來預測某個基準值特性的算法。但該算法在實現時具有一定缺陷。目前這一過程的實現需要計算出當前所有點與基準值A的距離并存儲在一個數組D[]_n內，通過排序的方式選舉出K個最小值確定為臨近點，再通過比較臨近點中屬于哪一類的數據多來推斷出A值的屬性，這就相當于需要對所有計算出的距離進行存儲以及排序，當數據量稍大時，會占用大量內存和時間去進行數據存儲及排序，這也是該算法計算復雜度高、空間復雜度高的顯著缺點。

例如需要對基準值A進行分類，數據中除A外還有n個值，需要首先確定K(Kn)值，之后創建長度為n的數組distance[]_n，分別計算當前除了需要判斷的基準值A外其余n個點到A點的距離(dis1-disn)并插入數組，之后對distance[dis₁,dis₂,…,dis_n]數組進行排序，選出K個最小值，最后對K個最小值進行分析，K個臨近值中占多數的類型即判斷為A的類型。

現有方法的缺陷是需要將n個值與A的距離都存在數組中再進行比較并排序，首先，對長度為n的數組進行排序時，平均時間復雜度達到O(nlog₂n)，需要處理排序的數據較多。另一方面，在數據量稍大時，會占用較大的內存來存儲數組，空間復雜度較高。在現如今大數據蓬勃發展的趨勢下，該算法在分類稍大規模的數據時，對空間和時間都會存在大量的浪費。

此為現有技術的不足，因此，針對現有技術中的上述缺陷，提供一種針對K-NN算法臨近點查找的優化方法及裝置，是非常有必要的。

發明內容

針對現有技術的上述現有K-NN算法在分類稍大規模的數據時，對空間和時間都會存在大量的浪費的缺陷，本發明提供一種針對K-NN算法臨近點查找的優化方法及裝置，以解決上述技術問題。

第一方面，本發明提供一種針對K-NN算法臨近點查找的優化方法，包括如下步驟：

S1.獲取已有數據集合中確定元素數量N及待分類元素，所述確定元素數量N為已有數據集合中元素總數量減去待分類元素的數量；

S2.根據已有數據集合中確定元素數量N及應用需求定義臨近數量K，并創建一個長度為臨近數量K的數組；

S3.計算已有數據集合中K個確定元素與待分類元素的距離，并將K個距離值依次存儲到創建的數組中；