[發明專利]一種基于聚類的分層最近鄰欠采樣方法

在審

• 申請號: 201811233719.4
• 申請日: 2018-10-23
• 公開（公告）號: CN109522936A
• 公開（公告）日: 2019-03-26
• 發明（設計）人: 高欣;梁躍;何楊;劉鑫;井瀟;刁新平
• 申請（專利權）人: 北京郵電大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明實施例提出了一種基于聚類的分層最近鄰欠采樣方法，包括：利用Kmeans聚類算法得到多數類樣本的肘圖，根據簇數與各個簇畸變程度之和的關系選擇最優聚類的簇數k；使用Kmeans聚類算法將多數類樣本聚為k簇，從而得到各個簇的中心點及簇內樣本點個數；根據每個簇內樣本點的數量，進行分層采樣，選取每個簇中心點的最近鄰與少數類樣本合并作為采樣結果。本發明實施例提供的技術方案，充分利用了多數類樣本的分布特征，較好地保留了多數類樣本的有用信息，且能有效提高后續分類算法的分類效果。

【技術領域】

本發明涉及機器學習領域欠采樣方法，尤其涉及一種基于聚類的分層最近鄰欠采樣方法。

【背景技術】

在利用機器學習方法解決分類問題時，存在數據集不平衡即某一類樣本的數量遠遠少于其他類樣本數量的現象。根據合適的重采樣算法解決數據集類間不平衡問題，以提高分類模型對少數類樣本的識別率，是當今研究的熱點之一。目前對于解決不平衡數據集分類問題，常用技術主要分為基于算法的方法和基于數據的方法。基于算法的方法是指根據分類算法在解決不平衡數據分類問題時的缺陷，適當修改算法，使之適應不平衡分類問題，常用的策略有代價敏感方法和集成學習方法。代價敏感方法通過引入代價敏感因子，對分類錯誤的少數類樣本進行懲罰，如代價敏感決策樹，代價敏感支持向量機等。集成學習方法使用一系列分類器進行學習，并將各個學習結果進行整合從而獲得比單個分類器更好的學習效果，如bagging，AdaBoost，AdaCost等。基于算法的方法通過改變算法自身的計算過程來適應不平衡數據集，但是沒有從根本上改變數據集類間的不平衡性，這大大降低了算法的泛化性能，而基于數據的方法將采樣階段與訓練階段獨立，便于將不同的采樣方式與不同的分類方法相結合，所以在實際使用中，較多使用基于數據的方法。基于數據的方法是指通過重采樣過程，對數據集本身進行重構的一種簡單有效的方式，可以使不平衡的樣本分布變得比較平衡，從而提高分類器對少數類的識別率。重采樣的方法主要分為增加少數類樣本的數量(過采樣)與減少多數類樣本的數量(欠采樣)兩種。過采樣方法是通過有放回抽樣、對少數類樣本進行復制、生成少數類的相似樣本等方法來增加少數類樣本的個數，從而達到平衡數據集的目的，包括對樣本進行隨機復制以及SMOTE算法等。SMOTE算法是通過插值生成新的人造樣本，該算法在對少數類樣本進行采樣時存在一定的盲目性，所以許多學者提出了Borderline-SMOTE、ASMOTE、OSLDDSMOTE等改進方法。以上過采樣方法通過復制或人工生成的方式來增加少數類樣本，使得分類器過分注重這部分樣本，從而導致過擬合現象。并且過采樣會增加訓練時間，提高計算的復雜度，這種方式不能從本質上解決少數類樣本的稀缺性和數據表示的不充分性。欠采樣方法是通過舍棄部分樣本，減少多數類樣本的個數，從而降低數據集不平衡的程度。隨機欠采樣可以通過減少多數類樣本的數量來提高計算效率，但是具有一定的盲目性，并且會損失多數類樣本的有用信息。所以欠采樣方法要改進的重點是在平衡類間比例的基礎上盡量保留原始數據集的有用信息。

【發明內容】

有鑒于此，本發明實施例提出了一種基于聚類的分層最近鄰欠采樣方法，以提高分類模型對少數類樣本的識別率。

本發明實施例提出的一種基于聚類的分層最近鄰欠采樣方法，包括：

利用Kmeans聚類算法得到多數類樣本的肘圖，根據簇數與各個簇畸變程度之和的關系選擇最優聚類的簇數k；

使用Kmeans聚類算法將多數類樣本聚為k簇，從而得到各個簇的中心點及簇內樣本點個數；

根據每個簇內樣本點的數量，進行分層采樣，選取每個簇中心點的最近鄰與少數類樣本合并作為采樣結果。

上述方法中，利用Kmeans聚類算法得到多數類樣本的肘圖，根據簇數與各個簇畸變程度之和的關系選擇最優聚類的簇數k的方法為：使用Kmeans算法對多數類樣本進行聚類，計算各個簇畸變程度之和dist：