[發明專利]一種基于聚類和特征匹配的改進kNN算法

在審

• 申請號: 201811376522.6
• 申請日: 2018-11-19
• 公開（公告）號: CN109508747A
• 公開（公告）日: 2019-03-22
• 發明（設計）人: 孫善寶;羅清彩;于治樓
• 申請（專利權）人: 濟南浪潮高新科技投資發展有限公司
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 濟南信達專利事務所有限公司 37100
• 代理人: 姜明

本發明公開了一種基于聚類和特征匹配的改進kNN算法，屬于機器學習和數據挖掘技術領域。本發明的基于聚類和特征匹配的改進kNN算法，計算全部已知樣本特征Hash值作為標識，生成索引用于快速檢索，實現待分類樣本的快速匹配分類；確定影響分類結果的主要特征，將樣本特征空間進行劃分，并通過聚類算法形成已知樣本簇，生成Hash作為樣本簇特征，計算待分類樣本的特征Hash值，完成特征匹配以縮小近鄰樣本范圍，減少計算已知樣本與待分類樣本間距離的計算。該發明的基于聚類和特征匹配的改進kNN算法能夠提升執行效率和準確性，具有很好的推廣應用價值。

技術領域

本發明涉及機器學習和數據挖掘技術領域，具體提供一種基于聚類和特征匹配的改進kNN算法。

背景技術

隨著社會的經濟，社會經濟飛速發展，各種高科技技術也順勢發展起來。近年來，人工智能技術發展迅速，其商業化速度超出預期，人工智能將會給整個社會帶來顛覆性的變化，已經成為未來各國重要的發展戰略。隨著云計算和大數據的發展，特別是海量數據的出現，從大數據中進行學習，打破了傳統的方式，對各個領域產生了顛覆性的變革。產生了海量的數據，也迫切需要將這些數據轉換成有用的信息和知識，而云中心強大的計算力和不斷演進的機器學習算法使得數據挖掘的效率不斷提升，挖掘出更有價值的信息和知識，廣泛用于各類應用中。

kNN算法即k-Nearest Neighbor，為K最近鄰算法是數據挖掘分類技術中的經典算法，是一種用于分類和回歸的非參數統計方法。其核心是計算測試樣本與樣本特征空間的樣本之間的距離，得到k個最相鄰的樣本，如果這k個最近鄰樣本大多數屬于某一類別，則該樣本也屬于這個類別，并具有該類別樣本的特性。kNN算法廣泛用于文本分類，模式識別，圖像處理等領域。kNN算法具有簡單、易理解、以實現的特點，然而其缺點也非常明顯，例如樣本不平衡，一個類的樣本容量很大，而其他類樣本容量很小時，會影響最終的判斷精度，另外計算量需求較大，尤其是存在海量已知樣本的情況，需要計算帶分類樣本與全體已知樣本之間的距離，分類速度和效率大大降低。在這種情況下，如何有效的對已知樣本進行優化處理，提升kNN算法的精度和效率成為亟須解決的問題。

發明內容

本發明的技術任務是針對上述存在的問題，提供一種能夠提升執行效率和準確性的基于聚類和特征匹配的改進kNN算法。

為實現上述目的，本發明提供了如下技術方案：

一種基于聚類和特征匹配的改進kNN算法，計算全部已知樣本特征Hash值作為標識，生成索引用于快速檢索，實現待分類樣本的快速匹配分類；確定影響分類結果的主要特征，將樣本特征空間進行劃分，并通過聚類算法形成已知樣本簇，生成Hash作為樣本簇特征，計算待分類樣本的特征Hash值，完成特征匹配以縮小近鄰樣本范圍，減少計算已知樣本與待分類樣本間距離的計算。

該基于聚類和特征匹配的改進kNN算法，計算全部已知樣本特征Hash值作為其標識，生成索引用于快速檢索，實現了待分類樣本的快速匹配分類；通過特征分析確定樣本特征對于分類結果的影響程度，根據主要影響特征利用聚類算法將樣本特征空間進行劃分，找到有代表性的已知樣本簇，生成Hash作為樣本簇特征；設置已知樣本的數據存儲，選定有效的k值，完成算法的預處理；分類過程是將待分類測試元組計算其全部特征和主要特征的Hash值。分類過程通過計算待分類樣本的特征Hash值，完成特征匹配以縮小近鄰樣本范圍，特別是當已知樣本空間的樣本數量足夠大時，極大的減少了已知樣本與待分類樣本間距離的計算次數，同時充分考慮到樣本特征對分類結果影響的差異性，能夠有效的提高效率和精確。

作為優選，該基于聚類和特征匹配的改進kNN算法主要包括以下步驟：

S01、計算所有已知樣本的特征向量的Hash值作為標識；

S02、將所有已知樣本的Hash值標識生成索引，用于搜索；

S03、通過特征分析確定樣本特征對于分類結果的影響程度；