周于皓,張紅玲,李芳菲,祁 鵬

(1.中國(guó)石油大學(xué)(北京) 石油工程學(xué)院,北京 102249; 2.武漢紡織大學(xué) 傳媒學(xué)院,武漢 430000)(*通信作者電子郵箱951113598@qq.com)

0 引言

數(shù)據(jù)集的不均衡性是機(jī)器學(xué)習(xí)的一個(gè)重要問(wèn)題,傳統(tǒng)的機(jī)器學(xué)習(xí)算法雖然有效,但僅限于數(shù)據(jù)集相差不多的情形,一旦出現(xiàn)大比例的失衡,算法便會(huì)失效。而且在現(xiàn)實(shí)生活中，數(shù)據(jù)集不均衡的情形是更常見的,比如某一類數(shù)據(jù)較難采集、獲取周期較長(zhǎng)、獲取成本較大等問(wèn)題都會(huì)使訓(xùn)練數(shù)據(jù)產(chǎn)生非均衡性。以二分類為例,當(dāng)數(shù)據(jù)集均衡時(shí),即正負(fù)樣本基本一致時(shí),傳統(tǒng)的機(jī)器學(xué)習(xí)算法效果已經(jīng)非常好,這說(shuō)明傳統(tǒng)機(jī)器學(xué)習(xí)算法在理論上是成功的,如支持向量機(jī)(Support Vector Machine, SVM)算法、決策樹、DBSCAN(Density-Based Spatial Clustering of Applications with Noise)等；但當(dāng)正樣本遠(yuǎn)大于負(fù)樣本時(shí),再直接使用傳統(tǒng)的機(jī)器學(xué)習(xí)方法就變得基本無(wú)效了,所以解決這種訓(xùn)練集的不均衡問(wèn)題顯得格外重要。

在處理這類不均衡問(wèn)題上,主流可分為兩類：

第二類是算法層面的，包括基于集成[6]的或基于代價(jià)敏感[7]的學(xué)習(xí)改進(jìn)方法。集成算法方面如基于Boosting思想的兩個(gè)最著名的算法AdaBoost[8-9]和GBDT(Gradient Boosting Decision Tree),通過(guò)集成弱學(xué)習(xí)分類器達(dá)到強(qiáng)學(xué)習(xí)目的,雖然這類方法的主要目的并不是針對(duì)非平衡數(shù)據(jù)集,但其集成效果遠(yuǎn)好于基礎(chǔ)的單一算法。代價(jià)敏感學(xué)習(xí)主要是基于調(diào)整代價(jià)矩陣,其基本思想是對(duì)于代價(jià)高的誤分類樣本大大地提高其權(quán)重,而對(duì)于代價(jià)高的正確分類樣本適當(dāng)?shù)亟档推錂?quán)重,使其權(quán)重降低相對(duì)較小。這類方法可大致劃分為兩小類：第一類方法是直接構(gòu)建代價(jià)敏感學(xué)習(xí)模型,如為決策樹提出的代價(jià)敏感的剪枝方法、通過(guò)改進(jìn)上述集成方法中的AdaBoost而產(chǎn)生的代價(jià)敏感的Boosting算法AdaCost[10]、Geibel等[11]為SVM提出的基于Perceptron分類算法的代價(jià)敏感的學(xué)習(xí)方法等。第二類方法如Domingos等[12]提出的MetaCost,這是一種將一般分類模型轉(zhuǎn)換成代價(jià)敏感模型的方法。它通過(guò)一個(gè)“元學(xué)習(xí)”過(guò)程,根據(jù)最小期望代價(jià)修改訓(xùn)練樣本的類標(biāo)記,并使用修改過(guò)的訓(xùn)練集重新學(xué)習(xí)新的模型。

通過(guò)研究,本文提出了一種結(jié)合了數(shù)據(jù)層面和算法層面的新型集成算法。與AdaBoost、AdaCost等這類典型的算法不同,這兩者的數(shù)據(jù)層面對(duì)于多類數(shù)據(jù)的劃分是被動(dòng)的,是根據(jù)上一輪次算法試算的效果進(jìn)行的；而本文的集成方法是一種主動(dòng)的數(shù)據(jù)集劃分策略,通過(guò)對(duì)多類數(shù)據(jù)集的內(nèi)部聚類,不僅解決了數(shù)據(jù)平衡問(wèn)題,還精確地刻畫了數(shù)據(jù)集間的相對(duì)特征。另外在主動(dòng)劃分多類數(shù)據(jù)集方面,如文獻(xiàn)[13-15]方法,與其多層次的數(shù)據(jù)劃分方法不同,本文提出的是一種建立在集成算法上的數(shù)據(jù)集主動(dòng)劃分方法,在數(shù)據(jù)集的劃分方法上僅使用原始的聚類方法,且基本不存在問(wèn)題針對(duì)性的超參數(shù)選擇,此外該方法可以進(jìn)一步泛化成一種集成算法,除以SVM為基本算法[16]外,也可以選用其他基礎(chǔ)機(jī)器學(xué)習(xí)算法來(lái)實(shí)現(xiàn)。

1 算法基本原理

本文提出的集成算法是一種雙層的SVM集成算法,類似于神經(jīng)網(wǎng)絡(luò)中的多層感知機(jī),底層擁有數(shù)個(gè)傳統(tǒng)SVM分類器,這一結(jié)構(gòu)相當(dāng)于把非均衡數(shù)據(jù)集映射到一個(gè)特殊的特征空間。每一個(gè)底層SVM的作用就是只關(guān)注訓(xùn)練數(shù)據(jù)集中數(shù)據(jù)集的一部分特征,使得其只對(duì)特定的數(shù)據(jù)敏感,而對(duì)其他特征的數(shù)據(jù)基本無(wú)效果。最后在底層SVM群上連接一個(gè)集成SVM,將每一個(gè)底層SVM對(duì)數(shù)據(jù)的判斷進(jìn)行匯總,作出最后判斷。這一集成算法的拓?fù)浣Y(jié)構(gòu)如圖1所示。

圖1 集成方法拓?fù)浣Y(jié)構(gòu)示意圖

在面對(duì)非均衡數(shù)據(jù)集問(wèn)題時(shí)總是失敗的一個(gè)重要原因就是,規(guī)模大的集合在訓(xùn)練時(shí)會(huì)湮滅小規(guī)模的集合,所以一個(gè)簡(jiǎn)單自然的想法就是將規(guī)模大的集合進(jìn)行劃分,使得每一子集數(shù)量與小規(guī)模集合數(shù)量相當(dāng),這樣一來(lái),每個(gè)底層的SVM在訓(xùn)練過(guò)程中既不會(huì)出現(xiàn)數(shù)據(jù)集不均衡的問(wèn)題,又擁有了局部特征關(guān)注的能力。

為了使底層SVM有局部特征感知能力,且不存在數(shù)據(jù)不平衡現(xiàn)象,本文提出先對(duì)數(shù)據(jù)進(jìn)行特征聚類。在子集合的劃分上采用K-means聚類方法,預(yù)先提供超參數(shù)K,即應(yīng)事先將大規(guī)模的集合分解成多少分子集合。選取K-means方法的原因有兩個(gè):1)K-means聚類子集類數(shù)量可人為規(guī)定,方便控制每個(gè)SVM接收到的正負(fù)樣本數(shù)量比例維持在一定的水平上;2)K-means計(jì)算簡(jiǎn)單,耗時(shí)低,對(duì)整個(gè)集成算法的計(jì)算復(fù)雜度增加少。

在利用K-means完成聚類后,如圖2所示,不同的符號(hào)代表不同的聚類后子集,每一子集代表著原集合的一部分特征,將這些子集與負(fù)樣本集合分別組成訓(xùn)練集,用于訓(xùn)練出相同數(shù)量的SVM分類器。每一個(gè)分類器即代表著對(duì)一個(gè)特定特征的識(shí)別器。

圖2 局部關(guān)注SVM示意圖

最后頂層的集成SVM匯總每個(gè)底層SVM,相當(dāng)于集成了一個(gè)特征分類器群,從而可以逐特征進(jìn)行分類判斷。

2 算法流程

設(shè)有二分類問(wèn)題,集合A代表大規(guī)模集合,集合B代表小規(guī)模集合,數(shù)量比約為n=[A/B]。為了使底層SVM不再具有數(shù)據(jù)集不均衡的問(wèn)題,先對(duì)集合A進(jìn)行K-means聚類,K值取n(下文有對(duì)該超參數(shù)的優(yōu)化與討論),共隨機(jī)聚出n類,簡(jiǎn)記為Ai(i=1,2,…,n),共組成n個(gè)子訓(xùn)練集,簡(jiǎn)記為Si(i=1,2,…,n),在n個(gè)子訓(xùn)練集上訓(xùn)練n個(gè)SVM,以線性SVM為例作n次優(yōu)化,即使得方程組(1)共同達(dá)到最大值。

(1)

其中:ωi表示每個(gè)SVM的系數(shù)矩陣,bi為偏置系數(shù),yij與xij分別表示樣本的標(biāo)簽和屬性。直觀上理解,每一個(gè)底層SVM相當(dāng)于一個(gè)線性分類器,在最優(yōu)化完成后產(chǎn)生了n條最大間隔分割超平面如圖3所示。每一個(gè)分隔超平面只關(guān)注集合A的一部分特征,最終n條分割超平面以集合B為中心將集合B包圍,形成包絡(luò)面?？梢院芮宄乜吹?無(wú)論數(shù)量相差多么懸殊,包絡(luò)面都可以精確切分。

優(yōu)化完成后,即所有底層SVM訓(xùn)練完畢,得到分類器簇SVMi(i=1,2,…,n)。然后開始訓(xùn)練頂層SVM,對(duì)于頂層SVM來(lái)說(shuō),實(shí)際上等價(jià)于普通SVM訓(xùn)練,不同的是原本訓(xùn)練數(shù)據(jù)是兩維(為了方便討論假設(shè)原始數(shù)據(jù)集是兩維的),即底層SVM接收的訓(xùn)練數(shù)據(jù)是兩維的,而經(jīng)過(guò)底層SVM群映射后,每個(gè)SVMi給出一個(gè)得分,所以原本的兩維數(shù)據(jù)映射成n維數(shù)據(jù),頂層接收的訓(xùn)練數(shù)據(jù)為n維數(shù)據(jù),最后正常訓(xùn)練一個(gè)頂層SVM即可。這種內(nèi)置的映射方式,決定了集成SVM算法最終良好的分類效果,因?yàn)槊恳痪S度代表著一個(gè)特征判斷的結(jié)果,從而這個(gè)n維空間與原數(shù)據(jù)空間相比,大小數(shù)據(jù)集中每一部分都得到了分離,實(shí)現(xiàn)了類間分隔最大化。這一集成過(guò)程,使得頂層SVM在訓(xùn)練時(shí),訓(xùn)練數(shù)據(jù)集從不均衡的集合變成不存在不均衡問(wèn)題的特征空間,不存在任何樣本、特征湮滅問(wèn)題。

圖3 線性SVM理解圖示

3 仿真實(shí)驗(yàn)

為了檢測(cè)本文提出的集成算法的有效性,本文以基礎(chǔ)SVM算法、K-SOMTE方法、AdaCost、GTB(Gradient Tree Boosting)四種算法為基準(zhǔn)進(jìn)行對(duì)比。在UCI數(shù)據(jù)庫(kù)中選取五個(gè)常用的不均衡分類數(shù)據(jù)集進(jìn)行算法測(cè)評(píng)，數(shù)據(jù)集如表1所示。

表1 實(shí)驗(yàn)中使用的UCI數(shù)據(jù)集

在測(cè)評(píng)指標(biāo)上,本文以gmean值為基礎(chǔ)對(duì)分類結(jié)果進(jìn)行評(píng)價(jià),根據(jù)部分相關(guān)文獻(xiàn)[17]介紹,將二類問(wèn)題中混淆矩陣等價(jià)改為如表2所示。

表2 混淆矩陣

表2中：TP表示預(yù)測(cè)正確的樣本中少類的數(shù)目；FP表示預(yù)測(cè)錯(cuò)誤的樣本中少類的數(shù)目；TN表示預(yù)測(cè)正確的樣本中多類的數(shù)目；FN表示預(yù)測(cè)錯(cuò)誤的樣本中多類的數(shù)目。

(2)

其中:

為了使實(shí)驗(yàn)結(jié)果更加平滑,不具偶然性,實(shí)驗(yàn)采用5折交叉驗(yàn)證方法,在最終的5次結(jié)果中取平均值作為算法在該數(shù)據(jù)集上的最終得分。測(cè)評(píng)結(jié)果如表3所示。

表3 gmean 測(cè)評(píng)結(jié)果匯總

從表3可以看出：本文提出的局部關(guān)注SVM算法大體表現(xiàn)優(yōu)良,無(wú)論與基于采樣的K-SOMTE，還是基于集成、代價(jià)敏感的AdaCost和GTB,都表現(xiàn)出了一定程度的優(yōu)勢(shì),尤其是在Abal這個(gè)不平衡問(wèn)題嚴(yán)重的數(shù)據(jù)集上,本文方法表現(xiàn)突出,gmean分?jǐn)?shù)可以達(dá)到0.825 5。主要是因?yàn)楫?dāng)數(shù)據(jù)集不平衡性達(dá)到一定程度后,基于采樣的方法和基于代價(jià)敏感的方法的機(jī)制不能從根本上跨越不平衡性問(wèn)題,大量的過(guò)采樣和較大的代價(jià)敏感反而會(huì)產(chǎn)生過(guò)擬合等問(wèn)題；而本文提出的局部關(guān)注SVM算法以簡(jiǎn)單的方式繞過(guò)了不平衡性,且保持了原有數(shù)據(jù)集的數(shù)據(jù)利用率,使得預(yù)測(cè)效果優(yōu)于其他算法。

4 算法的優(yōu)化與討論

4.1 關(guān)于SVM核函數(shù)

通過(guò)大量的實(shí)驗(yàn)發(fā)現(xiàn),一般頂層SVM選用徑向基核函數(shù)(Radial Basis Function, RBF)為佳,底層SVM視情況而定。比如對(duì)Segm數(shù)據(jù)集,采用線性核時(shí)gmean評(píng)分可達(dá)到0.989 0的效果；如果將線性核改為高斯核,效果卻只能達(dá)到0.919 9左右,這說(shuō)明底層特征分類器不一定越復(fù)雜越好。從圖3可以看出，對(duì)于這種數(shù)據(jù)分布較為簡(jiǎn)單的集合,線性核就可以起到很好的效果,如果使用高斯核可能會(huì)出現(xiàn)過(guò)擬合等現(xiàn)象,反而影響效果。

4.2 關(guān)于聚類超參數(shù)K的選取

由于本文選取的K-means聚類方法迭代起始點(diǎn)的選擇為任意選擇,所以理論上講即使使用同一訓(xùn)練集合,因?yàn)榈讓犹卣骷系膭澐纸Y(jié)果略有不同,每次訓(xùn)練結(jié)果也會(huì)不同,但結(jié)果相差不大,相對(duì)偏差經(jīng)計(jì)算只有1%左右。在此基礎(chǔ)上本文對(duì)超參數(shù)K進(jìn)行優(yōu)化,如圖4所示,以Glass、Car、Abal三個(gè)數(shù)據(jù)集為例,均從K=2開始,循環(huán)訓(xùn)練并檢測(cè)gmean得分。

從圖4可看出，曲線局部震蕩得比較厲害,主要原因就是上面提到的聚類有一定的隨機(jī)性,從數(shù)值上可以看出,這一震蕩相對(duì)范圍很小,可以忽略。從圖4(a)可以看出,對(duì)于這種非均衡性差別不是很大的分類問(wèn)題(不均衡比例為6.38),只要K值不是過(guò)小(在小于6時(shí),gmean得分顯著下降),最終結(jié)果基本穩(wěn)定在0.95上下,正負(fù)誤差不超過(guò)0.005,且只要超過(guò)6.38這一原本不均衡比例,表現(xiàn)都不錯(cuò)。圖4(b)與圖4(a)情形差不多,Car數(shù)據(jù)集的不平衡比例為24.04,K小于10時(shí)gmean得分顯著下降,當(dāng)K在80附近,得分最高。Abal實(shí)驗(yàn)如圖4(c)所示,相對(duì)于其他實(shí)驗(yàn)而言,Abal數(shù)據(jù)集最難,不平衡度為129.53?？梢钥闯?隨著K的增大,gmean得分持續(xù)提高,在K=120處,取得最大gmean得分為0.825 5,基本也和不平衡度吻合,但經(jīng)后續(xù)實(shí)驗(yàn)觀測(cè),隨著K繼續(xù)增加到200左右,gmean得分依然有輕微提升,但模型訓(xùn)練及整體算法的計(jì)算復(fù)雜度則大大提升。所以實(shí)際應(yīng)用中可先選取一個(gè)大于原始數(shù)據(jù)集的不平衡度的值作為初始K值,隨后可適當(dāng)增大K來(lái)提升效果。

圖4 超參數(shù)K對(duì)分類結(jié)果影響曲線

4.3 改進(jìn)工作

正如前文所述局部關(guān)注SVM算法的效果得益于這種數(shù)據(jù)集的局部聚類劃分和訓(xùn)練,這種結(jié)構(gòu)賦予了局部關(guān)注SVM算法局部精細(xì)的能力。基于此啟發(fā),本文提出一個(gè)計(jì)算框架,框架分為數(shù)據(jù)聚合層、局部分類器層、集成層三部分。數(shù)據(jù)聚合層可使用K最近鄰(K-Nearest Neighbors, KNN)、基于密度的聚類(Density-Based Spatial Clustering of Applications with Noise, DBSCAN)等基礎(chǔ)無(wú)監(jiān)督聚類算法,而局部分類器層和集成層兩部分可以使用SVM、多層感知機(jī)、決策樹等一系列基礎(chǔ)算法,底層和頂層算法可以相同也可以不同。

5 結(jié)語(yǔ)

針對(duì)非均衡數(shù)據(jù)集的分類問(wèn)題。本文提出了一種新型集成算法,以SVM為基礎(chǔ)算法建立了兩步集成的拓?fù)浣Y(jié)構(gòu),先將訓(xùn)練數(shù)據(jù)集按KNN進(jìn)行非監(jiān)督聚類,然后用得到的K個(gè)集合分別訓(xùn)練K個(gè)底層SVM,這樣一來(lái)每一個(gè)底層SVM只關(guān)注特定的數(shù)據(jù)特征,從而有效避免了大規(guī)模數(shù)據(jù)集湮滅小規(guī)模數(shù)據(jù)集特征的問(wèn)題。在五組實(shí)驗(yàn)中局部關(guān)注SVM算法效果較傳統(tǒng)SVM算法顯著提升,對(duì)比流行的一些集成算法也略占優(yōu)勢(shì),可以說(shuō)在一定程度上提升了訓(xùn)練數(shù)據(jù)集非均衡的問(wèn)題下分類的準(zhǔn)確度。

參考文獻(xiàn)(References)

[1] BLAGUS R, LUSA L. SMOTE for high-dimensional class-imbalanced data[J]. Bmc Bioinformatics, 2013, 14(1): 106.

[2] ZIEBA M, TOMCZAK J M, GONCZAREK A. RBM-SMOTE: restricted Boltzmann machines for synthetic minority oversampling technique[M]// ACIIDS 2015: Proceedings of the 7th Asian Conference on Intelligent Information and Database Systems. Berlin: Springer, 2015: 377-386.

[3] 張永, 李卓然, 劉小丹. 基于主動(dòng)學(xué)習(xí)SMOTE的非均衡數(shù)據(jù)分類[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2012, 29(3): 91-93.(ZHANG Y, LI Z R, LIU X D. Active learning SMOTE based imbalanced data classification[J]. Computer Applications and Software, 2012, 29(3): 91-93.)

[4] 楊智明, 喬立巖, 彭喜元. 基于改進(jìn)SMOTE的不平衡數(shù)據(jù)挖掘方法研究[J]. 電子學(xué)報(bào), 2007, 35(增刊2): 22-26.(YANG Z M, QIAO L Y, PENG X Y. Research on datamining method for imbalanced dataset based on i mproved SMOTE[J]. Acta Electronica Sinica, 2007, 35(S2): 22-26.)

[5] 曾志強(qiáng), 吳群, 廖備水, 等. 一種基于核SMOTE的非平衡數(shù)據(jù)集分類方法[J]. 電子學(xué)報(bào), 2009, 37(11): 2489-2495.(ZENG Z Q, WU Q, LIAO B S, et al. A classfication method for imbalance data set based on kernel SMOTE[J]. Acta Electronica Sinica, 2009, 37(11): 2489-2495.)

[6] 大勇. 基于非平衡數(shù)據(jù)的適應(yīng)性采樣集成分類器的研究[D]. 長(zhǎng)沙: 中南大學(xué), 2010: 1-42.(DA Y. An adaptive sampling ensemble classifier for learning from imbalanced data sets[D]. Changsha: Central South University, 2010: 1-42.)

[7] 谷瓊, 袁磊, 熊啟軍, 等. 基于非均衡數(shù)據(jù)集的代價(jià)敏感學(xué)習(xí)算法比較研究[J]. 微電子學(xué)與計(jì)算機(jī), 2011, 28(8): 146-149.(GU Q, YUAN L, XIONG Q J, et al. A comparative study of cost-sensitive learning algorithm based on imbalanced data sets[J]. Microelectronics and Computer, 2011, 28(8): 146-149.)

[8] ZHU J, ZOU H, ROSSET S, et al. Multi-class AdaBoost[J]. Statistics & its Interface, 2006, 2(3): 349-360.

[9] 李正欣, 趙林度. 基于SMOTEBoost的非均衡數(shù)據(jù)集SVM分類器[J]. 系統(tǒng)工程, 2008, 26(5): 116-119.(LI Z X, ZHAO L D. A SVM classifier for imbalanced datasets based on SMOTEBoost[J]. Systems Engineering, 2008, 26(5): 116-119.)

[10] ZHANG J. AdaCost: misclassification cost-sensitive boosting[EB/OL]. [2017- 05- 10]. https: //pdfs.semanticscholar.org/9ddf/bc2cc5c1b13b80a1a487b9caa57e80edd863.pdf.

[11] GEIBEL P, BREFELD U, WYSOTZKI F. Perceptron and SVM learning with generalized cost models[J]. Intelligent Data Analysis, 2004, 8(5): 439-455.

[12] DOMINGOS P. MetaCost: a general method for making classifiers cost-sensitive[C]// KDD 1999: Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 1999: 155-164.

[13] 王金婉. 面向在線不均衡數(shù)據(jù)分類的極限學(xué)習(xí)機(jī)算法研究[D]. 新鄉(xiāng): 河南師范大學(xué), 2016: 13-25.(WANG J W. Research on extreme learning machine for online swquential imbalanced data classification[D]. Xinxiang: Henan Normal University, 2016: 13-25.)

[14] 毛文濤, 王金婉, 何玲, 等. 面向貫序不均衡數(shù)據(jù)的混合采樣極限學(xué)習(xí)機(jī)[J]. 計(jì)算機(jī)應(yīng)用, 2015, 35(8): 2221-2226.(MAO W T, WANG J W, HE L, et al. Hybrid sampling extreme learning machine for sequential imbalanced data[J]. Journal of Computer Applications, 2015, 35(8): 2221-2226.)

[15] 毛文濤, 田楊陽(yáng), 王金婉, 等. 面向貫序不均衡分類的粒度極限學(xué)習(xí)機(jī)[J]. 控制與決策, 2016, 31(12): 2147-2154.(MAO W T, TIAN Y Y, WANG J W, et al. Granular extreme learning machine for sequential imbalanced data[J]. Control and Decision, 2016, 31(12): 2147-2154.)

[16] ADANKON M M, CHERIET M. Support vector machine[J]. Computer Science, 2002, 1(4): 1-28.

[17] 谷瓊, 袁磊, 寧彬, 等. 一種基于混合重取樣策略的非均衡數(shù)據(jù)集分類算法[J]. 計(jì)算機(jī)工程與科學(xué), 2012, 34(10): 128-134.(GU Q, YUAN L, NING B, et al. A noval classification algorithm for imbalanced datasets based on hybrid resampling strategy[J]. Computer Engineering and Science, 2012, 34(10): 128-134.)