改進K均值聚類的不平衡數據欠采樣算法

于艷麗 江開忠 王珂 盛靜文

摘要：傳統欠采樣方法在處理不平衡數據問題時只考慮多數類樣本的絕對位置而忽略了其相對位置，從而使產生的平衡數據集存在邊界模糊問題。提出一種改進K均值聚類的不平衡數據欠采樣算法（UD-PK）。該算法首先利用改進的PSO算法迭代尋找全局最優解作為K-means聚類所需初始值，然后通過K-means進行聚類，再按照每個類別中多數類與少數類的比例定義所取多數類樣本個數，并根據多數類樣本與簇心距離擇優選擇參與平衡數據集構造。在UCI數據集上的對比試驗表明，該算法在少數類準確率上較一些經典算法有很大提升。

關鍵詞：不平衡數據集;欠采樣算法;K均值聚類;粒子群算法

DOI：10.11907/rjdk.192153開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP312文獻標識碼：A 文章編號：1672-7800（2020）006-0205-05

0 引言

在機器學習中，不平衡數據集指不同類別的樣本分布不均衡，即出現某一類別的樣本遠遠多于另一類別的樣本。這在現實生活中隨處可見，如醫療領域、征信領域、信息安全領域等。其中，醫療領域患重大疾病的人、征信領域中信用不良的人、信息安全領域中的不安全信息等樣本因其數量明顯少于其它類別，因而都屬于少數類樣本。錯分少數類樣本的代價遠大于多數類樣本，因此提高少數類分類精度是不平衡數據的研究重點。

現有不平衡數據處理方法主要有兩類：一是算法層面的處理，通過改變算法，如在分類算法中加入代價敏感因子，從而提高少數類的識別效果，如代價敏感決策樹、代價敏感支持向量機等，集成學習算法使用一系列弱分類器進行學習，通過整合各分類器，從而產生很好的性能，如Adaboos算法等;二是數據層面的處理，通過改變兩類數據樣本數量構造平衡數據集，主要有過采樣和欠采樣方法，過采樣就是增加少數類數量，欠采樣就是減少多數類數量，都能達到平衡數據集的作用。

過采樣算法如Smote算法，主要通過兩點連線中插值以增加樣本。Borderline-SMOTE算法主要根據K近鄰中異類樣本數目，確定出邊界集，對邊界集樣本進行插值。還有很多在兩者基礎上的一些算法，如Random-smote、R-smote、SD-Ismote、CB-Smote等。

欠采樣算法如US_DD算法，主要是將數據分成高密度簇和低密度簇，對兩者采取不同的欠采樣策略。KACbag算法將Adacost權重放人樣本更新中，最后根據權重選擇樣本與少數類進行組合;One-side-selection算法主要是去除多數類中的干擾樣本;SBC算法根據聚類后正負樣本比例確定抽樣比例參數;USCL算法是對多數類樣本采用聚類方法，用聚類中心作為多數類樣本。Lin提出了兩種基于聚類的欠采樣方法：①使多數類聚類數量等于少數類樣本數量;②用每一個聚類中心附近的樣本作為多數類樣本。上述算法大多只對多數類樣本進行處理，找出多數類樣本中心，排除噪聲樣本，從而獲取更多的多數類信息，但是沒有考慮多數類相對于少數類的位置問題，因此容易選擇邊界多數類樣本，使構造的平衡數據集產生模糊邊界問題，導致少數類精度下降。

根據以上研究，本文提出一種改進的K均值聚類的不平衡數據欠采樣算法（Improved Unbalanced Data Undersampiing Algorithm for K-means Clustering，UD-PK）。首先，通過PSO適應度函數尋找周圍多數類樣本點密集少數類樣本點稀疏的聚類簇心，對靜態的慣性權重進行動態調整，加快收斂速度，并提高尋優精度，通過計算每個粒子的適應度值更新粒子速度與位置，尋找全局最優解的聚類簇心;然后，將全局最優解作為K-means的初始聚類中心進行聚類;再根據每個類中多數類樣本與少數類樣本比例確定選取多數類樣本數量;最后，根據樣本與簇心距離，從中選擇靠近簇心的多數類樣本點加入最后平衡數據集。

1 相關知識

1.1 分類基礎

即分類器的超平面法向量和常數是使得F₁（F-Score值）取最大值時的（w₁，w₂，…，W_p，c）。

在實際問題中，往往兩類C^（0）/與C^（1）的個體數量極度不平衡，將個體數量多的一類，比如C^（0），稱為多數類，另一類C^（1）則稱為少數類。

1.2 粒子群優化算法

粒子群優化算法（PSO）是一種基于群體智能的進化方法。優化問題的每一個潛在解都是搜索空間中的粒子，每一個粒子有其相應的速度、位置和一個由目標函數決定的適應度，算法通過適應度評價粒子優劣。

PSO算法流程：①算法首先隨機挑選n個粒子作為初始位置;②通過適應度函數計算每個粒子的適應度值;③尋找并更新每個粒子的個體極值pBest_i和全局最優值gBest，以及它們對應的粒子位置xBest_i和xgBest;④根據每個粒子的個體極值位置與全局最優值位置，按式（4）、式（5）更新粒子當前速度和位置;⑤如果滿足終止條件，則算法結束，否則轉向步驟②。

其中，w、c₁和c₂分別是慣性權重與約束因子，p₁和p₂為[0，1]之間的隨機數，式（4）中第2部分為認知分量（即自身作用），第3部分為社會分量（群體中其它粒子的作用），式（5）中T通常取l。

1.3 最小距離判別法

已知類C及其中心u，個體x到類C的距離定義為：

1.4 K-means聚類

由MacQueen提出的K均值算法是一種經典算法，在數據挖掘和知識發現領域應用較廣。