基于層次密度聚類的去噪自適應(yīng)混合采樣①

姜新盈,王舒梵,嚴(yán) 濤

(上海工程技術(shù)大學(xué) 數(shù)理與統(tǒng)計學(xué)院,上海 201620)

現(xiàn)實中的很多領(lǐng)域存在的數(shù)據(jù)集都是不平衡的,這類數(shù)據(jù)集有著不同類別數(shù)據(jù)樣本不均、數(shù)量相差較大的特點,其中大多數(shù)樣本的類別稱為多數(shù)類別,其余樣本的類別稱為少數(shù)類別.由于不平衡數(shù)據(jù)的廣泛存在,從不平衡數(shù)據(jù)中學(xué)習(xí)對于研究界及現(xiàn)實應(yīng)用都至關(guān)重要,例如疾病診斷[1]和石油儲層含油量識別[2]等.任何分類器的目標(biāo)都是最大程度地提高總體準(zhǔn)確性,但是傳統(tǒng)分類器往往更傾向于多數(shù)類樣本,這就導(dǎo)致少數(shù)類樣本分類錯誤[3].實際應(yīng)用中,從不平衡數(shù)據(jù)中學(xué)習(xí)到的分類器需要同時在不同類別樣本上均表現(xiàn)良好,因此在保證多數(shù)類別分類精度的前提下,如何處理不平衡數(shù)據(jù)以提高少數(shù)類別分類準(zhǔn)確性.

1 引言

現(xiàn)有的一些廣泛處理不平衡數(shù)據(jù)分類的方法主要分為數(shù)據(jù)預(yù)處理、算法改進及特征選擇這3 個層面,當(dāng)前沒有一種方法能夠很好地解決所有不平衡數(shù)據(jù)集分類問題,算法改進僅僅針對單一的分類器進行改進,特征選擇容易造成信息丟失,但是數(shù)據(jù)層面的抽樣方法顯示了巨大的優(yōu)越性,該方法主要是改善數(shù)據(jù)集本身而不是分類器.

欠采樣是對多數(shù)類樣本進行處理,選擇一些多數(shù)類樣本進行剔除以提高少數(shù)類樣本的分類正確率.Yen等[4]提出SBC 算法,首先將整個數(shù)據(jù)集聚類,再根據(jù)每簇采樣數(shù)量進行欠采樣,但是容易丟失關(guān)鍵信息.過采樣是通過合成少數(shù)類樣本以增加少數(shù)類樣本的算法,Barua 等[5]提出MWMOTE 算法,先選擇少數(shù)類樣本的適當(dāng)子集,根據(jù)不同類別樣本間的距離對少數(shù)類樣本分配權(quán)重,再使用聚類方法并結(jié)合SMOTE 算法合成新的少數(shù)類樣本; Nekooeimehr 等[6]提出自適應(yīng)半無監(jiān)督加權(quán)過采樣,先對少數(shù)類樣本進行分層聚類,并根據(jù)分類復(fù)雜度等自適應(yīng)地對每個子集中靠近邊界的少數(shù)類樣本進行過采樣,避免生成與多數(shù)類重疊的合成少數(shù)類樣本.石洪波等[7]研究表明使用單一的采樣算法或?qū)е逻^擬合或誤刪重要樣本,而文獻[8]表明混合采樣的分類性能比單個采樣算法好,在提高運行效率,有效避免過擬合問題的情況下,還不易丟失含有重要信息的多數(shù)類樣本.戴翔等[9]提出BCS-SK 算法,采用SMOTE 合成少數(shù)類樣本,然后采用K-means 聚類算法對多數(shù)類樣本進行欠采樣;史明華[10]對整個數(shù)據(jù)集進行聚類,根據(jù)每簇不平衡率的大小將數(shù)據(jù)集分為4 類并采取不同的采樣方法,均衡了簇內(nèi)的樣本分布.

以上算法各具優(yōu)勢,但大部分沒有解決類內(nèi)小分離及易合成低質(zhì)量樣本的問題,也沒有區(qū)分不同樣本的重要性,為解決以上問題,本文提出了基于層次密度聚類的去噪自適應(yīng)混合采樣算法(adaptive denoising hybrid sampling algorithm based on hierarchical density clustering,ADHSBHD)來有效合成高質(zhì)量樣本.

2 相關(guān)理論

2.1 HDBSCAN 聚類

HDBSCAN 聚類算法[11]是McInnes 等人研究提出的一種基于層次聚類的最新算法,是對DBSCAN 密度聚類算法的優(yōu)化,能處理不同密度和任意形狀的聚類[12],一方面是不再將Eps值作為樹狀圖的切割線,而是通過查看分裂來壓縮樹狀圖,使用該樹選擇最穩(wěn)定的簇,并以不同的高度來切割樹,這樣可以根據(jù)簇的穩(wěn)定性選擇密度不同的簇; 另一方面是不再需要人工設(shè)置Eps參數(shù),只需要設(shè)置集群最小樣本數(shù)量min_samples來確定樣本是離群點還是分裂為兩個新集群即可.

相比于K-means、DBSCAN 等常用聚類具有對參數(shù)設(shè)置不敏感的優(yōu)勢,通常設(shè)置兩個參數(shù): 最小集群數(shù)量min_cluster_size,集群最小樣本數(shù)量min_samples.此外,HDBSCAN 具有噪聲感知能力,-1 表示該樣本點不在任何簇內(nèi),并且聚類結(jié)果會給數(shù)據(jù)集中的每個樣本都賦予一個0.0-1.0 的概率值,用于代表屬于某個簇的可能性,概率值為0.0 則表示該樣本點不在集群中(所有的離群點都是這個值),概率值為1.0 則表示該樣本點位于簇的核心.

2.2 Random-SMOTE 算法

由于SMOTE 算法存在合成樣本區(qū)域有限、易產(chǎn)生噪聲等問題,董燕杰[13]提出Random-SMOTE 算法,可以提高算法效率并更符合原數(shù)據(jù)集樣本空間.該算法的核心思想是根據(jù)3 個樣本點構(gòu)成三角區(qū)域,在區(qū)域內(nèi)生成新樣本,首先從少數(shù)類數(shù)據(jù)集中選擇樣本x作為根樣本,并且隨機選擇y1、y2這兩個樣本作為間接樣本,根據(jù)式(1)在y1、y2間線性插值,根據(jù)設(shè)置的采樣倍率N,生成N個臨時樣本pj,j=1,2,···,N.

其次根據(jù)式(2)在pj和x之間線性插值得到新樣本mj.

3 ADHSBHD 算法

文獻[6]表明,聚類是不錯的解決類內(nèi)不平衡及小分離問題的方法.為了更深入研究解決噪聲、類內(nèi)不平衡和小分離問題,提出了基于層次密度聚類的去噪自適應(yīng)混合采樣算法(ADHSBHD).

3.1 基于HDBSCAN 的去噪方法

在很多情形之下,噪聲樣本會使分類器性能損失,聚類作為潛在的噪聲檢測算法,為識別噪聲提供了另一研究思路.為了有效識別噪聲點,提出了一種基于HDBSCAN 的去噪方法,首先對少數(shù)類樣本集中的每個樣本計算其k近鄰,若該樣本k近鄰全部是多數(shù)類樣本,則把該樣本點視為全局離群點.然后引入HDBSCAN聚類,將少數(shù)類樣本集進行聚類,得到若干個簇,將概率值為0 的樣本視為局部離群點,取全部離群點集和局部離群點集的交集為噪聲集,這樣可以較全面地識別出噪聲點,也避免直接刪除處于小分離狀態(tài)的樣本,為接下來提出的ADHSBHD 算法在安全區(qū)域內(nèi)生成樣本做準(zhǔn)備.

3.2 對少數(shù)類樣本的處理

若每個簇內(nèi)都合成同樣數(shù)量的樣本,那么容易造成類重疊,也無益于類內(nèi)不平衡的解決,因此,在對少數(shù)類樣本聚類并去除噪聲之后,需要根據(jù)每簇的密集稀疏程度,確定每個簇所需合成的樣本數(shù)量,分配給每個簇一個0 到1 的采樣權(quán)重,這樣可以使稀疏區(qū)域的樣本增添有益信息,密集區(qū)域的樣本盡可能地減少類重疊,不會忽略對小規(guī)模集群的學(xué)習(xí).為了表示每簇的密集稀疏程度,用平均距離來表示.

定義1 (平均距離).對于數(shù)據(jù)集C和少數(shù)類樣本的任意簇C(1k),1 ≤k≤m,簇C(1k)的平均距離記為Meandist(C(1k)),即:

其中,dij為簇內(nèi)各樣本之間的歐式距離,n為簇內(nèi)樣本數(shù)量.

定義2 (采樣權(quán)重).任意簇C(1k),1 ≤k≤m的采樣權(quán)重為某簇的平均距離與所有簇的平均距離之和的比值,即:

當(dāng)各簇的平均距離越小時,說明簇內(nèi)樣本更密集,反之,則更稀疏.相應(yīng)的,簇內(nèi)樣本越密集時,需要合成的樣本越少,即采樣權(quán)重就越小,反之,需要合成的樣本就越多.

其中,|C|表示原始數(shù)據(jù)集C的樣本數(shù)量,表示少數(shù)類樣本的個數(shù).

每簇C(1k),1 ≤k≤m需要合成的樣本數(shù)量定義如下:

3.3 對多數(shù)類樣本的處理

根據(jù)HDBSCAN 對多數(shù)類樣本聚類,得到若干個簇和離群點,相應(yīng)的得到每個簇的概率值矩陣,當(dāng)概率值較低時說明樣本點越在簇的邊緣,過多的邊緣樣本會使分類器發(fā)生偏向而降低少數(shù)類的分類精度.為此,將所有多數(shù)類樣本的概率值按照從小到大的順序排列,按照一定規(guī)則,刪減的多數(shù)類樣本數(shù)量定義如下:

3.4 ADHSBHD 算法流程

ADHSBHD 算法的具體步驟描述如算法1.

算法1.ADHSBHD 算法輸入: 原始數(shù)據(jù)集 ,近鄰參數(shù),最小集群數(shù)量min_cluster_size,集群最小樣本數(shù)量min_samples Cnew C k輸出: 均衡數(shù)據(jù)集C(0)C(1)C=C(0)∪C(1)C(0)∪C(1)=? Step 1.將原始數(shù)據(jù)集劃分為多數(shù)類樣本集和少數(shù)類樣本集且且,并識別噪聲.C(1)xkk Nt Step 1.1.計算中各個樣本,計算其近鄰,若近鄰均為多數(shù)類樣本,則將該添加到全局離群點集 中.C(1)m C(11),C(12),C(13),···,C(1m)pij,0＜i≤m,0＜j≤■■■C(1i)■■■NlN=Nt∩NlC NC′■■■■C′■■■■=|C|-|N|Step 1.2.用HDBSCAN 對聚類,得到 個相互獨立且不同規(guī)模的簇和若干個離群點,并且得到每個簇的樣本概率值矩陣,而離群點的概率值為0,將其添加到局部離群點集 中,則噪聲集群.從原始數(shù)據(jù)集 中刪去噪聲集群 ,得到 ,其樣本量.for i=1 to■■■C(1i)■■■Step 2.,計算每個簇需要合成的新的樣本數(shù)量并自適應(yīng)合成.Step 2.1.計算每個簇中樣本之間的歐氏距離,并得到各簇的平均距離.Meandist(C(1k))W(C(1k))Step 2.2.計算每簇的采樣權(quán)重.■■■■C(1k)new■■■■x Step 2.3.計算每簇新的樣本數(shù)量,并選中簇內(nèi)樣本做目標(biāo)樣本,從它的近鄰中隨機選擇兩個樣本 、 ,先通過 、 隨機生成一個輔助樣本,再在目標(biāo)樣本和輔助樣本之間線性插值隨機生成新樣本,即采用Random-SMOTE 在三角形區(qū)域內(nèi)隨機合成樣本,將合成樣本添加到中,直到新樣本數(shù)量為.k y1y2y1y2 a x a C(1k)new■■■■C(1k)new■■■■C(1k)C(1k)new Step 2.4.合并每簇的與,各簇原始的少數(shù)類樣本集與合成樣本組成新的數(shù)據(jù)集中.C(1)new C(0)Step 3.對多數(shù)類樣本進行處理.C(0)n C(01),C(02),C(03),···,C(0n) t pij,0＜i≤n,0＜j≤■■■C(0i)■■■Step 3.1.對用HDBSCAN 聚類,得到個相互獨立且不同規(guī)模的簇和個離群點,并且得到每個簇的樣本概率值矩陣.t＜■■■C(0)■■■-|C|2C(0)Step 3.2.當(dāng)時,將中的樣本按照概率值從小到大排序,刪去離群點和部分概率值小的點,共個樣本; 當(dāng)時,對刪除個離群點,剩余的多數(shù)類樣本添加到新的數(shù)據(jù)集中.Cnew=C(0)new∪C(1)new Step 4.并對分類器進行訓(xùn)練.■■■C(0)■■■-|C|■■■C(0)■■■-|C|2 t≥■■■C(0)■■■-|C|2 C(0)2 C(0)new

4 實驗結(jié)果與分析

4.1 評價指標(biāo)

準(zhǔn)確率作為分類器評價指標(biāo)對于非平衡數(shù)據(jù)有失公平,為了客觀評價分類算法性能好壞,研究學(xué)者常常根據(jù)混淆矩陣引入的概念來評估算法性能.根據(jù)表1的混淆矩陣,引入查全率(Recall)、查準(zhǔn)率(Precision)、F-value值、G-mean值、AUC等定義.

表1 混淆矩陣

各定義的公式如下:

此外,AUC作為可視化指標(biāo),是根據(jù)引入的ROC曲線下的面積來表示,值越大,說明分類器性能越好.ROC曲線則是以真正例率為縱軸,以假正例率為橫軸繪制的.

4.2 數(shù)據(jù)集描述

為了驗證ADHSBHD 的有效性,本文從國際機器學(xué)習(xí)標(biāo)準(zhǔn)庫UCI 中選取了Ionosphere、Glass、Abalone、Haberman、Vehicle、Ecoli、Yeast 這7 組不平衡數(shù)據(jù)集,其中,Glass 的少數(shù)類特征為“1”; Abalone 的少數(shù)類特征為“F”; Vehicle 數(shù)據(jù)集中,將第一類視為少數(shù)類;Ecoli 的少數(shù)類特征為 “om”“omL”和“pp”; Yeast 數(shù)據(jù)集中將“MIT”視為少數(shù)類.7 組數(shù)據(jù)集的具體信息如表2所示.

表2 數(shù)據(jù)集信息

4.3 實驗分析

為了驗證本節(jié)所提出的ADHSBHD 算法表現(xiàn)良好,ADHSBHD 算法分別與SMOTE 算法、ADASYN算法、Random-SMOTE 算法(以下簡稱R-SMOTE)、SVMSOMTE 算法在這7 組數(shù)據(jù)集上做重采樣的對比實驗,用F-value、G-mean、AUC作為評價指標(biāo),實驗環(huán)境均在Jupyter Notebook 中運行,所使用的對比算法除R-SMOTE 外均調(diào)用imbalanced-learn 程序包實現(xiàn).

此外,SVM 中核函數(shù)為高斯核函數(shù),其他超參數(shù)均為imbalanced-learn 中的默認(rèn)值,為了直觀驗證上述各對比采樣算法的有效性,設(shè)置k=5,相應(yīng)的算法中的其他超參數(shù)也均為默認(rèn)值,而ADHSBHD 算法中使用到的HDBSCAN 算法設(shè)置最小集群數(shù)量min_cluster_size=2,集群最小樣本數(shù)量min_samples=4.

表3、表4 和表5 展示了7 組數(shù)據(jù)集6 種不同采樣算法下的F-value值、G-mean值和AUC值以此來衡量算法分類結(jié)果,黑體加粗的數(shù)值表示同一數(shù)據(jù)集的最優(yōu)算法對應(yīng)指標(biāo)值,avg 表示不同數(shù)據(jù)集在不同組合形式的算法下的平均值.從各表中可以看出,雖然對Haberman 數(shù)據(jù)集使用Random-SMOTE 算法的結(jié)果優(yōu)于本文算法結(jié)果,這是由于本文在引入聚類算法后,在如何選擇最佳樣本參與合成時存在不足,而Random-SMOTE 算法的合成方法更符合Haberman 數(shù)據(jù)集.但是從整體性能上看,ADHSBHD 算法應(yīng)用到SVM 分類器后提升了整體分類精度,在F-value、G-mean、AUC這幾種性能指標(biāo)方面均優(yōu)于文中所提其他4 種對比算法.

表3 不同數(shù)據(jù)集在支持向量機下的F-value 性能對比

表4 不同數(shù)據(jù)集在支持向量機下的G-mean 性能對比

表5 不同數(shù)據(jù)集在支持向量機下的AUC 性能對比

5 結(jié)論

本文提出了基于層次密度聚類的去噪自適應(yīng)混合采樣算法(ADHSBHD),以層次密度聚類為基礎(chǔ),考慮到不同類別樣本的樣本空間分布,為了驗證ADHSBHD的有效性及穩(wěn)定性,將該算法與SVM 分類器結(jié)合在一起,并與4 種采樣算法進行實驗對比,實驗結(jié)果表明,該算法與不同的分類器的組合有較好的泛化性,Fvalue、G-mean、AUC這3 個評價指標(biāo)在上述大部分?jǐn)?shù)據(jù)集上都有所提升.由于該算法是基于聚類算法展開,后續(xù)可以研究其他的聚類技術(shù)能否為該算法帶來更高性能.