改進K均值聚類的不平衡數(shù)據(jù)欠采樣算法

于艷麗 江開忠 王珂 盛靜文

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

關(guān)鍵詞：不平衡數(shù)據(jù)集;欠采樣算法;K均值聚類;粒子群算法

DOI：10.11907/rjdk.192153開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

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

0 引言

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

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

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

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

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

1 相關(guān)知識

1.1 分類基礎(chǔ)

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

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

1.2 粒子群優(yōu)化算法

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

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

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

1.3 最小距離判別法

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

1.4 K-means聚類

由MacQueen提出的K均值算法是一種經(jīng)典算法，在數(shù)據(jù)挖掘和知識發(fā)現(xiàn)領(lǐng)域應(yīng)用較廣。