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

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

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

1 引言

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

欠采樣是對(duì)多數(shù)類樣本進(jìn)行處理,選擇一些多數(shù)類樣本進(jìn)行剔除以提高少數(shù)類樣本的分類正確率.Yen等[4]提出SBC 算法,首先將整個(gè)數(shù)據(jù)集聚類,再根據(jù)每簇采樣數(shù)量進(jìn)行欠采樣,但是容易丟失關(guān)鍵信息.過采樣是通過合成少數(shù)類樣本以增加少數(shù)類樣本的算法,Barua 等[5]提出MWMOTE 算法,先選擇少數(shù)類樣本的適當(dāng)子集,根據(jù)不同類別樣本間的距離對(duì)少數(shù)類樣本分配權(quán)重,再使用聚類方法并結(jié)合SMOTE 算法合成新的少數(shù)類樣本; Nekooeimehr 等[6]提出自適應(yīng)半無監(jiān)督加權(quán)過采樣,先對(duì)少數(shù)類樣本進(jìn)行分層聚類,并根據(jù)分類復(fù)雜度等自適應(yīng)地對(duì)每個(gè)子集中靠近邊界的少數(shù)類樣本進(jìn)行過采樣,避免生成與多數(shù)類重疊的合成少數(shù)類樣本.石洪波等[7]研究表明使用單一的采樣算法或?qū)е逻^擬合或誤刪重要樣本,而文獻(xiàn)[8]表明混合采樣的分類性能比單個(gè)采樣算法好,在提高運(yùn)行效率,有效避免過擬合問題的情況下,還不易丟失含有重要信息的多數(shù)類樣本.戴翔等[9]提出BCS-SK 算法,采用SMOTE 合成少數(shù)類樣本,然后采用K-means 聚類算法對(duì)多數(shù)類樣本進(jìn)行欠采樣;史明華[10]對(duì)整個(gè)數(shù)據(jù)集進(jìn)行聚類,根據(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 等人研究提出的一種基于層次聚類的最新算法,是對(duì)DBSCAN 密度聚類算法的優(yōu)化,能處理不同密度和任意形狀的聚類[12],一方面是不再將Eps值作為樹狀圖的切割線,而是通過查看分裂來壓縮樹狀圖,使用該樹選擇最穩(wěn)定的簇,并以不同的高度來切割樹,這樣可以根據(jù)簇的穩(wěn)定性選擇密度不同的簇; 另一方面是不再需要人工設(shè)置Eps參數(shù),只需要設(shè)置集群最小樣本數(shù)量min_samples來確定樣本是離群點(diǎn)還是分裂為兩個(gè)新集群即可.

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

2.2 Random-SMOTE 算法

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

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

3 ADHSBHD 算法

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

3.1 基于HDBSCAN 的去噪方法

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

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

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

定義1 (平均距離).對(duì)于數(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)各簇的平均距離越小時(shí),說明簇內(nèi)樣本更密集,反之,則更稀疏.相應(yīng)的,簇內(nèi)樣本越密集時(shí),需要合成的樣本越少,即采樣權(quán)重就越小,反之,需要合成的樣本就越多.

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

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

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

根據(jù)HDBSCAN 對(duì)多數(shù)類樣本聚類,得到若干個(gè)簇和離群點(diǎn),相應(yīng)的得到每個(gè)簇的概率值矩陣,當(dāng)概率值較低時(shí)說明樣本點(diǎn)越在簇的邊緣,過多的邊緣樣本會(huì)使分類器發(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ù)類樣本集且且,并識(shí)別噪聲.C(1)xkk Nt Step 1.1.計(jì)算中各個(gè)樣本,計(jì)算其近鄰,若近鄰均為多數(shù)類樣本,則將該添加到全局離群點(diǎn)集 中.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 對(duì)聚類,得到 個(gè)相互獨(dú)立且不同規(guī)模的簇和若干個(gè)離群點(diǎn),并且得到每個(gè)簇的樣本概率值矩陣,而離群點(diǎn)的概率值為0,將其添加到局部離群點(diǎn)集 中,則噪聲集群.從原始數(shù)據(jù)集 中刪去噪聲集群 ,得到 ,其樣本量.for i=1 to■■■C(1i)■■■Step 2.,計(jì)算每個(gè)簇需要合成的新的樣本數(shù)量并自適應(yīng)合成.Step 2.1.計(jì)算每個(gè)簇中樣本之間的歐氏距離,并得到各簇的平均距離.Meandist(C(1k))W(C(1k))Step 2.2.計(jì)算每簇的采樣權(quán)重.■■■■C(1k)new■■■■x Step 2.3.計(jì)算每簇新的樣本數(shù)量,并選中簇內(nèi)樣本做目標(biāo)樣本,從它的近鄰中隨機(jī)選擇兩個(gè)樣本 、 ,先通過 、 隨機(jī)生成一個(gè)輔助樣本,再在目標(biāo)樣本和輔助樣本之間線性插值隨機(jī)生成新樣本,即采用Random-SMOTE 在三角形區(qū)域內(nèi)隨機(jī)合成樣本,將合成樣本添加到中,直到新樣本數(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.對(duì)多數(shù)類樣本進(jìn)行處理.C(0)n C(01),C(02),C(03),···,C(0n) t pij,0＜i≤n,0＜j≤■■■C(0i)■■■Step 3.1.對(duì)用HDBSCAN 聚類,得到個(gè)相互獨(dú)立且不同規(guī)模的簇和個(gè)離群點(diǎn),并且得到每個(gè)簇的樣本概率值矩陣.t＜■■■C(0)■■■-|C|2C(0)Step 3.2.當(dāng)時(shí),將中的樣本按照概率值從小到大排序,刪去離群點(diǎn)和部分概率值小的點(diǎn),共個(gè)樣本; 當(dāng)時(shí),對(duì)刪除個(gè)離群點(diǎn),剩余的多數(shù)類樣本添加到新的數(shù)據(jù)集中.Cnew=C(0)new∪C(1)new Step 4.并對(duì)分類器進(jìn)行訓(xùn)練.■■■C(0)■■■-|C|■■■C(0)■■■-|C|2 t≥■■■C(0)■■■-|C|2 C(0)2 C(0)new

4 實(shí)驗(yàn)結(jié)果與分析

4.1 評(píng)價(jià)指標(biāo)

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

表1 混淆矩陣

各定義的公式如下:

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

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

為了驗(yàn)證ADHSBHD 的有效性,本文從國際機(jī)器學(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 實(shí)驗(yàn)分析

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

此外,SVM 中核函數(shù)為高斯核函數(shù),其他超參數(shù)均為imbalanced-learn 中的默認(rèn)值,為了直觀驗(yàn)證上述各對(duì)比采樣算法的有效性,設(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)算法對(duì)應(yīng)指標(biāo)值,avg 表示不同數(shù)據(jù)集在不同組合形式的算法下的平均值.從各表中可以看出,雖然對(duì)Haberman 數(shù)據(jù)集使用Random-SMOTE 算法的結(jié)果優(yōu)于本文算法結(jié)果,這是由于本文在引入聚類算法后,在如何選擇最佳樣本參與合成時(shí)存在不足,而Random-SMOTE 算法的合成方法更符合Haberman 數(shù)據(jù)集.但是從整體性能上看,ADHSBHD 算法應(yīng)用到SVM 分類器后提升了整體分類精度,在F-value、G-mean、AUC這幾種性能指標(biāo)方面均優(yōu)于文中所提其他4 種對(duì)比算法.

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

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

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

5 結(jié)論

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