面向不均衡數(shù)據(jù)的多分類集成算法

崔 鑫，徐 華，朱 亮

江南大學(xué) 人工智能與計(jì)算機(jī)學(xué)院，江蘇 無錫 214122

在機(jī)器學(xué)習(xí)中最為普遍的問題是分類問題。傳統(tǒng)分類算法都是建立在數(shù)據(jù)類別分布均衡的基礎(chǔ)上，然而在實(shí)際問題中并不能保證數(shù)據(jù)類別分布平衡，例如異常檢測(cè)、故障診斷、醫(yī)學(xué)數(shù)據(jù)分析等。不均衡分類問題可以分為絕對(duì)不均衡和相對(duì)不均衡。絕對(duì)不均衡指的是數(shù)據(jù)中某一類樣本數(shù)量非常少比如只有10到20個(gè)，甚至不足10個(gè)，此類樣本數(shù)量過少并不足夠用于分類器的訓(xùn)練。相對(duì)不均衡指的是雖然少數(shù)類的數(shù)量很大比如1 000或者更多，但是多數(shù)類和少數(shù)類樣本數(shù)比例卻大于1或者更大，傳統(tǒng)分類算法在處理此類數(shù)據(jù)會(huì)偏向多數(shù)類而忽略更具有分類價(jià)值的少數(shù)類。由于上述不均衡數(shù)據(jù)的特點(diǎn)，傳統(tǒng)分類算法用以解決不均衡數(shù)據(jù)分類的問題往往并不能獲得讓人滿意的效果。因此學(xué)術(shù)界有必要針對(duì)不均衡數(shù)據(jù)的特點(diǎn)尋找更加有針對(duì)性的算法。

面向不均衡數(shù)據(jù)分類的研究[1-2]是近年來機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等領(lǐng)域的熱點(diǎn)之一，針對(duì)不均衡數(shù)據(jù)的算法主要可以分為數(shù)據(jù)層面和算法層面。數(shù)據(jù)層面算法即對(duì)原數(shù)據(jù)進(jìn)行重采樣以平衡數(shù)據(jù)分布，重采樣包括過采樣和欠采樣。最簡(jiǎn)單的欠采樣方法是隨機(jī)欠采樣（random under-sampling，RUS），使用隨機(jī)算法去除部分多數(shù)類樣本以平衡數(shù)據(jù)分布，由于其實(shí)現(xiàn)簡(jiǎn)單且性能良好，該算法常被用作比較算法。但是由于采用隨機(jī)算法，隨機(jī)欠采樣的性能不穩(wěn)定且易丟失數(shù)據(jù)分布信息。2016年，Ha等人提出了基于遺傳算法的欠采樣GAUS（genetic algorithm based under-sampling）[3]，通過最小化損失以選擇最優(yōu)的多數(shù)類子集，與RUS相比采樣更加合理且性能更穩(wěn)定，但是具有更高的時(shí)間復(fù)雜度。2017年，Rayhan等人提出了基于聚類的欠采樣方法[4]，將聚類和隨機(jī)算法相結(jié)合降低了采樣的盲目性。

少數(shù)類樣本合成過采樣技術(shù)[5]（synthetic minority oversampling technique，SMOTE）是目前最流行的過采樣算法之一，該算法在少數(shù)類與其最近鄰間線性插值引入新樣本。雖然SMOTE算法一定程度上緩解了過采樣算法會(huì)引起過擬合的問題，但是卻存在使用噪聲樣本合成新樣本以及模糊類間邊界的問題。針對(duì)SMOTE算法的不足，許多研究人員提出了SMOTE的改進(jìn)算法[6-7]，例如He等人提出基于SMOTE的自適應(yīng)合成采樣[8]（adaptive synthetic sampling，ADASYN），該算法與SMOTE相比實(shí)現(xiàn)了對(duì)少數(shù)類樣本的區(qū)別對(duì)待，對(duì)難以區(qū)分的少數(shù)類合成更多的樣本，而易于區(qū)分的樣本則合成較少的樣本。2018年，趙清華等人拋棄了將正類樣本點(diǎn)分組的思想提出了最遠(yuǎn)點(diǎn)少數(shù)類樣本合成過采樣技術(shù)[9]（max distance SMOTE，MDSMOTE），在少數(shù)類質(zhì)心和距離質(zhì)心點(diǎn)最遠(yuǎn)距離的樣本點(diǎn)間合成新樣本。易未等人于2018年提出了改進(jìn)的SMOTE算法improvedSMOTE[10]，該算法增大了合成樣本的分布范圍，緩解了過擬合的問題。

算法層面包括代價(jià)敏感[11]、特征選擇[12]和集成學(xué)習(xí)方法[13]。在不均衡分類問題中少數(shù)類具有更高的分類價(jià)值，代價(jià)敏感學(xué)習(xí)通過給予錯(cuò)分的少數(shù)類樣本更高的錯(cuò)分代價(jià)，改善分類器對(duì)少數(shù)類的分類效果。如果數(shù)據(jù)集中樣本分布不均衡，特征的分布也可能會(huì)不均衡，因此選用易于區(qū)分的特征可以提高分類性能。集成學(xué)習(xí)即組合多個(gè)基分類器得到一個(gè)強(qiáng)分類器，由于其獨(dú)立性，集成學(xué)習(xí)常與抽樣方法、特征選擇方法相結(jié)合，例如Guo等人于2016年提出的集成學(xué)習(xí)方法[14]（BPSOAdaboost-KNN），該算法將特征選擇方法與Adaboost相結(jié)合，以及Liu等人提出的基于遺傳欠采樣和基于多目標(biāo)蟻群優(yōu)化的特征選擇[15]（genetic under-sampling and multiobjectie ant colony optimization based feature selection，GU-MOACOFS），該算法更是同時(shí)使用了欠抽樣、特征選擇和集成方法。

集成算法所得的多個(gè)基分類器中，有些分類器精度較差，有些分類器分類結(jié)果相似，即不具備多樣性，這些分類器不會(huì)提高集成分類的性能。因此，有研究人員將多樣性度量用于選擇性集成，試圖通過提高分類器的多樣性從而提高集成分類的性能。雖然多樣性對(duì)集成算法的性能有重大的影響，但是目前學(xué)術(shù)界未能明確多樣性與集成算法性能間的關(guān)系。所以將多樣性度量顯式地應(yīng)用在集成算法中會(huì)存在一定的爭(zhēng)議。然而，除了顯式的使用多樣性度量，通過增加數(shù)據(jù)集的多樣性來提高基分類器的多樣性也是一種行之有效方法。因此，本文提出了一種基于采樣和特征選擇的不均衡數(shù)據(jù)集成分類算法（imbalanced data ensemble classification algorithm based on sampling and feature selection，IDESF）。IDESF算法采用有放回采樣+SMOTE的兩階段采樣方法，不僅可以平衡數(shù)據(jù)分布，而且可以通過增加數(shù)據(jù)集的差異性來隱式提高基分類器的多樣性。為了降低過采樣引入噪聲樣本的風(fēng)險(xiǎn)，IDESF引入了數(shù)據(jù)清洗操作。此外，IDESF算法引入了基于SPSO的特征選擇算法，試圖降低算法的復(fù)雜度。最后，通過多個(gè)對(duì)比實(shí)驗(yàn)驗(yàn)證了IDESF算法的有效性。

1 IDESF算法

1.1 兩階段采樣

集成算法如果集成多個(gè)完全一致的分類器，那么對(duì)最終的分類效果沒有任何幫助。基分類器間存在適當(dāng)?shù)亩鄻有?，那么如果某個(gè)樣本被一個(gè)或者多個(gè)基分類器所錯(cuò)誤分類，但是通過某種規(guī)則組合基分類器的分類結(jié)果卻仍然可能獲得正確的結(jié)果。此外，Kuncheva等人的研究[16]也同樣表明設(shè)計(jì)多樣化分類器的總體動(dòng)機(jī)是正確的。因此，為了提高集成算法的分類性能，研究人員會(huì)采用一定的策略來保證基分類器間的多樣性。研究人員試圖對(duì)多樣性進(jìn)行顯式度量，并在多樣性度量的指導(dǎo)下進(jìn)行選擇性集成。但是多樣性與集成系統(tǒng)精度的關(guān)系不明確，顯式地度量分類器間的多樣性并用來構(gòu)建集成系統(tǒng)仍存在爭(zhēng)議。然而像Bagging這樣隱式地產(chǎn)生分類器間多樣性的集成算法是十分具有價(jià)值的研究方向。對(duì)原數(shù)據(jù)集按照某種策略進(jìn)行多次采樣可以獲得不同的數(shù)據(jù)集，分別在不同數(shù)據(jù)集上訓(xùn)練得到的分類器必然相互之間存在一定的差異，所以采樣策略可以保證基分類器間的差異性。常用的算法例如SMOTEBoost、Bagging都是單階段采樣，單階段采樣使用同一策略獲得了多個(gè)數(shù)據(jù)集，雖然可以保證數(shù)據(jù)集間存在一定的差異性，但是難以保證訓(xùn)練所得的分類器之間仍存在足夠的差異性。為了進(jìn)一步提高數(shù)據(jù)集間的差異性，從而提高基分類器的多樣性，提出了有放回采樣+SMOTE兩階段采樣策略。

如圖1所示，圖（a）為原始數(shù)據(jù)集，（b）為有放回采樣處理后的數(shù)據(jù)集，（c）為在（b）的基礎(chǔ)上進(jìn)行SMOTE過采樣后的數(shù)據(jù)集，圓形為多數(shù)類，星型為少數(shù)類。假設(shè)原數(shù)據(jù)集中樣本數(shù)量為n,x為原數(shù)據(jù)集中的一個(gè)樣本，在此基礎(chǔ)上進(jìn)行有放回采樣。以樣本x為例，極端情況下樣本x可能被采樣n次也可能并未被采樣，所以（b）中與x相同的樣本數(shù)量在0到n之間。由此可知，（b）中的數(shù)據(jù)樣本皆為原數(shù)據(jù)集中采樣所得，并未對(duì)樣本本身進(jìn)行處理，保存了原數(shù)據(jù)集中樣本信息。因此，圖（a）和圖（b）中數(shù)據(jù)的分布趨勢(shì)較為一致。此外，圖（a）和圖（b）在數(shù)據(jù)密集程度上呈現(xiàn)了一定的差異，這是由于有放回采樣導(dǎo)致數(shù)據(jù)集中部分樣本被采樣多次，而部分樣本未采樣。有放回采樣是對(duì)原數(shù)據(jù)集進(jìn)行隨機(jī)采樣，所得多個(gè)數(shù)據(jù)集的樣本總數(shù)雖然相等但是某個(gè)樣本的數(shù)量卻存在差異，因此保證了數(shù)據(jù)集間的差異性。SMOTE過采樣算法用少數(shù)類與其近鄰的少數(shù)類合成新樣本，因此參與合成的樣本的合理性將直接影響新樣本的合理性。有放回采樣并未改變樣本本身的信息，并且觀察圖1可知圖（b）中的數(shù)據(jù)分布與原數(shù)據(jù)集圖（a）中數(shù)據(jù)分布保持一致，因此在有放回采樣所得的數(shù)據(jù)集上使用SMOTE算法可以保證參與合成的樣本的合理性。同時(shí)，圖（a）與圖（c）數(shù)據(jù)分布趨勢(shì)一致也表明SMOTE引入新樣本的合理性。SMOTE過采樣不僅可以獲得分布均衡且合理的數(shù)據(jù)集，在有放回采樣所得的多個(gè)數(shù)據(jù)集上分別進(jìn)行SMOTE過采樣，可以進(jìn)一步擴(kuò)大數(shù)據(jù)集間的差異。有放回采樣所得的數(shù)據(jù)集間的差異體現(xiàn)于某一樣本的數(shù)量，假設(shè)有放回采樣得到兩個(gè)數(shù)據(jù)集A和B，原數(shù)據(jù)集中某個(gè)樣本x在數(shù)據(jù)集A中存在，在數(shù)據(jù)集B不存在。如果在數(shù)據(jù)集A和B中分別進(jìn)行SMOTE過采樣，數(shù)據(jù)集A通過樣本x合成所得的新樣本必然與數(shù)據(jù)集B中所得的新樣本存在一定的區(qū)別。所以，在有放回采樣的基礎(chǔ)上進(jìn)行SMOTE過采樣會(huì)導(dǎo)致合成不同的新樣本，數(shù)據(jù)集間的差異進(jìn)一步擴(kuò)大。綜上所述，兩階段采樣可以保證所得數(shù)據(jù)集的合理性，同時(shí)也可以保證數(shù)據(jù)集間的差異性。差異化的數(shù)據(jù)集上更易獲得多樣化的基分類器。因此，兩階段采樣通過增大數(shù)據(jù)集間的差異，從而提高了基分類器的多樣性。

圖1 采樣情況Fig.1 Sample situation

1.2 IDESF算法

IDESF算法框架如圖2所示，首先使用有放回采樣獲得多個(gè)訓(xùn)練子集，每個(gè)數(shù)據(jù)子集的樣本數(shù)量均與原數(shù)據(jù)集的樣本數(shù)量保持一致，子集的個(gè)數(shù)作為超參數(shù)進(jìn)行調(diào)優(yōu)。然后在訓(xùn)練子集上依次使用SMOTE算法、數(shù)據(jù)清洗以及特征選擇方法，在每個(gè)訓(xùn)練子集上獲得一個(gè)分類器，最后使用加法法則獲得最終分類結(jié)果。下文將介紹算法相結(jié)合的具體過程，各個(gè)模塊以及模塊間的聯(lián)系。

如圖2所示，首先對(duì)原數(shù)據(jù)集進(jìn)行n次有放回的采樣獲得n個(gè)數(shù)據(jù)子集，此階段獲得數(shù)據(jù)子集的特點(diǎn)：（1）改變了某一個(gè)樣本的數(shù)量，所以子集間存在一定的差異。（2）并未改變某一個(gè)樣本自身的內(nèi)容，所以又保存了原數(shù)據(jù)的信息。由于上述特點(diǎn)，在此階段數(shù)據(jù)子集上進(jìn)行SMOTE過采樣可以保證獲得的子集不會(huì)偏離原數(shù)據(jù)分布，又可以進(jìn)一步擴(kuò)大數(shù)據(jù)子集間的差異。少數(shù)類樣本數(shù)量過少是不均衡分類中最為突出的問題：（1）分類器在訓(xùn)練過程中會(huì)追求正確率的最大化，少數(shù)類數(shù)量過少會(huì)導(dǎo)致分類偏向多數(shù)類，可能會(huì)將部分少數(shù)類當(dāng)作噪聲數(shù)據(jù)。如果少數(shù)類有多個(gè)子集且分布稀疏，則更易被當(dāng)作噪聲數(shù)據(jù)。（2）少數(shù)類數(shù)量少，則原數(shù)據(jù)集中所包含的分類信息自然就較少，信息的欠缺可能會(huì)導(dǎo)致分類器對(duì)訓(xùn)練集和測(cè)試集中的少數(shù)類樣本都難以保證可靠的分類效果。SMOTE合成少數(shù)類的過采樣技術(shù)，在少數(shù)類樣本與其近鄰的少數(shù)類樣本間隨機(jī)線性插值引入新樣本，增加少數(shù)類樣本數(shù)量獲得均衡的數(shù)據(jù)集。SMOTE算法引入的新樣本與原數(shù)據(jù)集中的樣本存在一定差異，所以可以豐富少數(shù)類的分布，降低了過擬合的風(fēng)險(xiǎn)。有放回采樣+SMOTE的兩階段采樣方法可以獲得分布均衡的數(shù)據(jù)集，同時(shí)在1.1節(jié)中也表明了其可以保證數(shù)據(jù)集的差異性和合理性，所以IDESF算法可以在不同的數(shù)據(jù)集上訓(xùn)練得到多樣化的分類器。本文實(shí)驗(yàn)部分選用的數(shù)據(jù)集為多類別數(shù)據(jù)集，假設(shè)數(shù)據(jù)集中樣本數(shù)量最多的類為y,y類的樣本數(shù)量為N，IDESF算法在每個(gè)數(shù)據(jù)子集上分別使用SMOTE算法將所有類的樣本數(shù)量擴(kuò)充到N，得到各個(gè)類別分布均衡的數(shù)據(jù)子集。

圖2 IDESF算法框架Fig.2 IDESF algorithm framework

由于實(shí)際情況的復(fù)雜性，在數(shù)據(jù)的獲取和記錄過程中難免發(fā)生錯(cuò)誤而引入噪聲樣本。此外，目前所提出的過采樣算法雖已獲得較好的分類性能，但是都存在一定的局限性，例如有放回采樣可能多次采樣噪聲樣本，增加所得數(shù)據(jù)子集中噪聲樣本數(shù)量；SMOTE算法可能使用噪聲樣本參與合成新樣本，難以保證所得新樣本的合理性?？紤]到采樣策略的局限性以及原數(shù)據(jù)集中存在的噪聲樣本，過采樣算法難以保證引入的新樣本都符合原數(shù)據(jù)分布，所以兩階段采樣后的數(shù)據(jù)集中必然含有一定數(shù)量的噪聲樣本。分布于邊界的噪聲樣本可能會(huì)模糊類間邊界，降低數(shù)據(jù)的可分性。噪聲樣本數(shù)量過多甚至?xí)淖償?shù)據(jù)集原有的數(shù)據(jù)分布，導(dǎo)致分類器對(duì)測(cè)試數(shù)據(jù)出現(xiàn)大量的錯(cuò)誤分類。噪聲樣本的存在嚴(yán)重?fù)p害了分類性能，所以保證新樣本的合理性是十分必要的。為了提高采樣算法所引入新樣本的合理性，提高各類之間的可分性，IDESF算法在兩階段采樣后使用了數(shù)據(jù)清洗操作。IDESF算法所采用的數(shù)據(jù)清洗操作是去除數(shù)據(jù)中互為最近異類的樣本對(duì)，多類別數(shù)據(jù)集需對(duì)每對(duì)類組合進(jìn)行清洗操作。例如對(duì)a類和b類進(jìn)行數(shù)據(jù)清洗，樣本點(diǎn)xi屬于a類，以歐氏距離為評(píng)價(jià)標(biāo)準(zhǔn)，分別計(jì)算每個(gè)b類樣本與樣本點(diǎn)xi的歐氏距離，若b類樣本xj與xi之間的距離最小，則xj為xi最近鄰的b類樣本。然后分別計(jì)算每個(gè)a類樣本與樣本xj間的歐氏距離，若xi為xj最近鄰的a類樣本，則xi與xj構(gòu)成了互為最近異類的樣本對(duì)，去除樣本對(duì)xi和xj。分別對(duì)每個(gè)a類樣本按照上述規(guī)則進(jìn)行清洗，則完成了a和b類組合的數(shù)據(jù)清洗操作。

數(shù)據(jù)集中特征可以分為：相關(guān)特征，對(duì)分類問題有幫助，可以提高分類性能；無關(guān)特征，對(duì)分類器的訓(xùn)練沒有幫助，不能提高分類性能；冗余特征，不能為分類器的訓(xùn)練帶來新的信息，或者該特征的信息可以由其他的特征推斷出。冗余特征和無關(guān)特征的存在會(huì)增加算法的時(shí)間復(fù)雜度，同時(shí)也會(huì)耗費(fèi)過多的內(nèi)存空間。特征選擇算法可以去除冗余特征和無關(guān)特征，從而降低時(shí)間復(fù)雜度和空間消耗，并且提高分類效果。IDESF算法采用基于簡(jiǎn)化粒子群算法（simple particle swarm optimization，SPSO）的特征選擇算法。SPSO基于群體隨機(jī)搜索機(jī)制，利用群體中個(gè)體間信息交互與合作實(shí)現(xiàn)尋優(yōu)。在迭代過程中每個(gè)粒子不斷更新位置信息，最終得到滿足終止條件的最優(yōu)解。特征選擇可以看作0-1組合優(yōu)化問題，解為一個(gè)由0和1組成的向量為1表示第i個(gè)粒子在t次迭代的第d維特征被選中，為0則未選中。借鑒于文獻(xiàn)[17]，通過設(shè)定閾值δ將粒子的位置信息轉(zhuǎn)換為解向量，如公式（1）所示：

SPSO算法使用粒子的位置、個(gè)體極值以及種群極值獲得下次迭代粒子的位置。表示第i個(gè)粒子在t次迭代的第d維分量，w為慣性因子，c1和c2是學(xué)習(xí)因子，r1和r2是服從U(0,1)的隨機(jī)數(shù)，pgd表示種群極值的第d維分量，pid表示第i個(gè)粒子個(gè)體極值的第d維分量，進(jìn)化公式如公式（2）所示：

IDESF采用的特征選擇算法——SPSO算法：

輸入：訓(xùn)練集(xi,yi),i=1,2,…,N，種群大小M，最大迭代次數(shù)T，閾值δ。

輸出：特征子集。

（1）初始化種群，隨機(jī)生成M個(gè)粒子，粒子的每維分量都是服從U(0,1)的隨機(jī)數(shù)。

（2）將每個(gè)粒子的位置信息根據(jù)公式（1）轉(zhuǎn)化為特征向量，根據(jù)特征向量從原訓(xùn)練集中選取各自的訓(xùn)練子集，在訓(xùn)練子集上可得一個(gè)分類器H，根據(jù)分類器H所預(yù)測(cè)的結(jié)果可得一組ROC曲線下的面積（area under the curve，AUC），然后根據(jù)公式（4）得到AUCarea[18]并將其作為適應(yīng)度，用粒子的位置信息初始化對(duì)應(yīng)粒子的個(gè)體極值pi，最高適應(yīng)度對(duì)應(yīng)的位置信息作為種群極值pg。

（3）判斷是否達(dá)到停止條件（最大迭代次數(shù)T或者最大適應(yīng)度），如果達(dá)到停止條件則轉(zhuǎn)步驟（5），否則轉(zhuǎn)到步驟（4）。

（4）使用公式（2）更新所有粒子的位置，計(jì)算其適應(yīng)度值，如果出現(xiàn)更優(yōu)的pi和pg，則更新其值，然后轉(zhuǎn)到步驟（3）。

（5）將pg轉(zhuǎn)換為特征向量并輸出，算法結(jié)束。

在數(shù)據(jù)子集上根據(jù)其各自的特征子集訓(xùn)練得到一組基分類器，最后采用加法法則組合基分類器得到最終的強(qiáng)分類器。加法法則即對(duì)每個(gè)類求得n個(gè)基分類器的分類概率和，預(yù)測(cè)結(jié)果即為分類概率和中最大的類別。設(shè)n為基分類器的個(gè)數(shù)，m為類別的個(gè)數(shù)，類標(biāo)簽為{C1,C2,…,Cm},Pij為第i個(gè)基分類器將預(yù)測(cè)樣本預(yù)測(cè)為Cj類的概率，RCj為Cj類上n個(gè)基分類器的概率之和，pre為最終的預(yù)測(cè)結(jié)果，則pre=arg max{RC1,。

1.3 算法復(fù)雜度分析

定義n為數(shù)據(jù)集中樣本數(shù)量，m為數(shù)據(jù)集類別數(shù)量，k為基分類器的數(shù)量。有放回采樣的時(shí)間復(fù)雜度為O(n)，有放回采樣后樣本數(shù)量仍為n。在此基礎(chǔ)上進(jìn)行SMOTE過采樣，假設(shè)采樣的倍率為t，則時(shí)間復(fù)雜度為O(n(n+t))。由于t一般遠(yuǎn)小于n，所以SMOTE的時(shí)間復(fù)雜度可以簡(jiǎn)化為O(n2)。數(shù)據(jù)清洗操作的時(shí)間復(fù)雜度為。假設(shè)迭代次數(shù)為t，粒子數(shù)為p，以決策樹為分類器為例，基于SPSO算法的特征選擇算法的時(shí)間復(fù)雜度為O(tp(n+m2))=O(n)。綜上，IDESF算法的時(shí)間復(fù)雜度為O(k(n+n2+n2+n))，即O(n2)。IDESF算法的空間復(fù)雜度取決于有放回采樣中所存儲(chǔ)的多個(gè)數(shù)據(jù)集。因此，IDESF算法的空間復(fù)雜度為O(n)。

2 實(shí)驗(yàn)

2.1 數(shù)據(jù)集和評(píng)價(jià)指標(biāo)

實(shí)驗(yàn)所選用的數(shù)據(jù)集均來自于KEEL（http：//www.keel.es/datasets.php），源于不同的實(shí)際應(yīng)用領(lǐng)域。數(shù)據(jù)集的詳細(xì)信息見表1，其中IR表示多數(shù)類與少數(shù)類的數(shù)目之比。

不均衡分類實(shí)驗(yàn)中常用的度量指標(biāo)是AUC，越大的AUC代表分類的效果越好。AUC可以定量比較不同分類器的性能，但是AUC是針對(duì)于二分類問題所設(shè)計(jì)的，而對(duì)于多分類問題AUC不能直接使用需對(duì)其進(jìn)行擴(kuò)展，常用的兩種擴(kuò)展方法：（1）一對(duì)一方法；（2）一對(duì)多方法。假設(shè)數(shù)據(jù)類標(biāo)簽集合Y={y1,y2,…,ym}，第一種方法，計(jì)算每對(duì)類組合(yi,yj)(i≠j)的AUC。第二種方法，為每個(gè)類yi∈Y創(chuàng)建一個(gè)二分類問題，其中屬于yi類樣本為正類，其他樣本為負(fù)類，然后為每個(gè)二分類問題計(jì)算AUC。以上兩種方法都可以得到一組AUC值，取其平均值avgAUC作為多分類問題的評(píng)價(jià)指標(biāo)。

兩種擴(kuò)展方法都易于理解和計(jì)算，但是平均值avgAUC并不能反映極端情況，例如一組AUC值中一個(gè)值較差只有0.5，其他的AUC值較高0.9以上，而avgAUC可能反映分類效果良好。這種情況在不均衡分類中更加有可能出現(xiàn)，從而錯(cuò)誤判斷少數(shù)類的分類效果。此外對(duì)于不同分類器，可能每個(gè)AUC值都不同，但是avgAUC卻相等，此時(shí)就無法判斷哪種分類器更優(yōu)。

為此，Hassan等人提出了基于一對(duì)一的新的評(píng)價(jià)指標(biāo)AUCarea，將一組AUC值在極坐標(biāo)上表示，將極坐標(biāo)上所覆蓋的面積作為評(píng)價(jià)指標(biāo)AUCarea，面積越大越好。假設(shè)數(shù)據(jù)類標(biāo)簽集合Y={y1,y2,…,ym}，計(jì)算每對(duì)類組合(yi,yj)(i≠j)的AUC，可得一組AUC值{r1,r2,…,rq},q=C2m。坐標(biāo)圖的角度設(shè)置為2π，圖中每個(gè)等角線代表一個(gè)AUC，所以圖中有q個(gè)等角線。等角線的長(zhǎng)度代表AUC的值，所以其長(zhǎng)度最大為1。此外，{r1,r2,…,rq}在圖中的表示需按照：r2為r1的近鄰，r3為r2的近鄰，…，rq為r1的近鄰。連接近鄰點(diǎn)所形成的圖形面積即評(píng)價(jià)指標(biāo)AUCarea。如圖3所示，是一個(gè)三分類的AUCarea極坐標(biāo)圖示，虛線圍成的三角形面積就是AUCarea。AUCarea的計(jì)算公式如公式（3）所示：

當(dāng)所有AUC值為1時(shí)，可得AUCarea的最大值A(chǔ)UCarea_max=(q/2)sin(2π/q)，為了AUCarea在[0，1]范圍內(nèi)取值對(duì)其進(jìn)行歸一化操作，如公式（4）所示：

為了書寫方便，公式（4）所得的值仍記為AUCarea。與avgAUC相比，AUCarea除了可視化之外，AUCarea對(duì)于單個(gè)差的AUC更加敏感。假設(shè)ri變?yōu)閞i-l，avgAUC和AUCarea的變化分別為：。因?yàn)閱蝹€(gè)AUC值都是大于等于0.5，所以如果某個(gè)AUC值下降，則AUCarea降低的幅度會(huì)更大。在不均衡分類問題中，少數(shù)類與其他類的AUC可能會(huì)較低，所以AUCarea更加適用于不均衡分類問題。

2.2 分類器類別及數(shù)量對(duì)分類性能的影響

為了研究分類器類別對(duì)分類性能的影響，實(shí)驗(yàn)固定基分類器個(gè)數(shù)為10，在決策樹（decision tree，DT）、最近鄰（k-nearest neighbor，KNN）以及邏輯回歸（logistic regression，LR）三個(gè)不同的分類器中進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如圖4所示，不同分類器的分類效果各有不同。在balance數(shù)據(jù)集上，LR優(yōu)勢(shì)十分明顯可以比DT和KNN分別高出0.087 6、0.098 4，且在dermatology和wine數(shù)據(jù)集上同樣取得了較高的分類性能。但是在contraceptive和hayes-roth數(shù)據(jù)集上LR分類效果很差，特別在hayes-roth數(shù)據(jù)集上所得AUC比DT和KNN低了0.4左右。分類器DT和KNN在五個(gè)數(shù)據(jù)集上的分類效果相近，但是DT在contraceptive、dermatology、hayes-roth和wine數(shù)據(jù)集上均取得了最高的AUC。從五個(gè)數(shù)據(jù)集上的均值來看，DT、KNN和LR所得平均AUCarea分別為0.899 3、0.891 7、0.814 8，DT仍然取得了最高值。綜上所述，下文的實(shí)驗(yàn)均采用DT作為基分類器。

為了研究分類器數(shù)量對(duì)分類性能的影響，實(shí)驗(yàn)設(shè)置決策樹為基分類器，并設(shè)置分類器的數(shù)量為5、10、15、20、25、30。IDESF算法不同分類器數(shù)量的分類性能以及均值如圖5所示。在dermatology數(shù)據(jù)集，基分類器數(shù)量達(dá)到10之后分類性能便趨于穩(wěn)定。wine數(shù)據(jù)集上分類性能并未隨著基分類器個(gè)數(shù)變化而產(chǎn)生波動(dòng)，而是一直保持著最高的分類性能。balance數(shù)據(jù)集在基分類器數(shù)量為5和30時(shí)分類性能較低，而基分類器數(shù)量在10~25時(shí)分類性能較高且在小范圍內(nèi)波動(dòng)。在contraceptive數(shù)據(jù)集上，分類性能隨著基分類器數(shù)量的增加而增加，在基分類器數(shù)量達(dá)到20時(shí)性能趨于穩(wěn)定。hayes-roth數(shù)據(jù)集，基分類器數(shù)量在5~20時(shí)分類性能保持上升且波動(dòng)，在數(shù)量為20時(shí)性能達(dá)到峰值，之后隨著基分類器數(shù)量增加，性能有所下降。基分類器數(shù)量為20和25時(shí)整體的分類性能均較高且相近，但基分類器數(shù)量為25僅在contraceptive數(shù)據(jù)集取得了最高的AUCarea，而基分類器數(shù)量為20在balance、dermatology、hayes-roth、wine以及均值取得了最高的AUCarea。綜上所述，考慮到算法的分類性能和復(fù)雜度，下文實(shí)驗(yàn)將基分類器數(shù)量設(shè)置為20。

圖5 基分類器數(shù)量對(duì)分類性能的影響Fig.5 Influence of base classifier number on classification performance

2.3 閾值對(duì)分類性能的影響

IDESF的特征選擇算法通過設(shè)定閾值將粒子的位置信息轉(zhuǎn)換為解向量，所以閾值設(shè)定必然會(huì)影響特征選取，進(jìn)一步影響算法的分類性能。為了研究其對(duì)分類性能的影響，本文選擇-0.2、-0.1、0、0.1、0.2、0.3、0.4、0.5、0.6、0.7、0.8、0.9這12個(gè)數(shù)值作為閾值，對(duì)比研究不同閾值下算法的性能。IDESF算法不同閾值的分類性能以及均值如圖6所示。在balance數(shù)據(jù)集上閾值為0時(shí)AUCarea達(dá)到最大值，而閾值為其他值時(shí)AUCarea差別較小，性能曲線較為平滑。在contraceptive數(shù)據(jù)集上，在-0.2~0.1之間性能曲線略有上升，在0.1之后性能曲線劇烈波動(dòng)，而在0.7之后性能曲線又急劇下降。dermatology數(shù)據(jù)集上，在-0.2~0.2和0.4~0.6區(qū)間內(nèi)曲線較為平穩(wěn)，而在0.3和0.8處曲線出現(xiàn)了凹點(diǎn)。hayes-roth數(shù)據(jù)集上，性能曲線在-0.2~0間小幅度上升，在0之后曲線波動(dòng)且呈下降趨勢(shì)。wine數(shù)據(jù)集上，性能曲線十分平穩(wěn)且保持著最高的AUCarea。閾值為0時(shí)，在balance、dermatology、hayes-roth以及wine數(shù)據(jù)集上均獲得了最高的AUCarea。此外，平均值曲線在閾值為0時(shí)取得了峰值，閾值為0與其他值相比優(yōu)勢(shì)較為明顯?；谏鲜鰧?shí)驗(yàn)結(jié)果，下文實(shí)驗(yàn)中閾值選擇為0。

圖6 閾值對(duì)分類性能的影響Fig.6 Influence of thresholds on classification perform

2.4 IDESF算法性能研究

為了進(jìn)一步研究IDESF算法的有效性，將IDESF算法與BPSO-Adaboost-KNN[14]、基于聚類欠采樣的集成不均衡數(shù)據(jù)分類算法[19]（imbalanced data ensemble classification based on cluster-based under-sampling algorithm，ECUA）、文獻(xiàn)[20]所提出的兩種算法與bagging結(jié)合（分別簡(jiǎn)記為Centers和Centers_NN）以及有效不平衡分類的代價(jià)敏感決策樹集成算法[21]（cost-sensitive decision tree ensembles for effective Imbalanced classification，CS-MCS）進(jìn)行對(duì)比?；谏衔膶?shí)驗(yàn)，IDESF選擇DT作為基分類器，基分類器數(shù)量設(shè)置為20，閾值設(shè)置為0。SPSO算法的參數(shù)設(shè)置：種群粒子數(shù)為50，最大迭代次數(shù)為40，學(xué)習(xí)因子c1=c2=2，慣性因子w=0.8。采用AUCarea和另外一個(gè)廣泛使用的不平衡分類評(píng)價(jià)指標(biāo)GM（G-Mean）對(duì)算法進(jìn)行評(píng)價(jià)，實(shí)驗(yàn)結(jié)果列于表2、3。

在表2中可以看出在所有數(shù)據(jù)集以及平均值上，IDESF與對(duì)比算法相比均獲得了更高AUCarea。其中在balance數(shù)據(jù)集上IDESF的優(yōu)勢(shì)最為明顯，與對(duì)比算法相比平均可以高出0.176。在contraceptive和hayes-roth數(shù)據(jù)集上，IDESF依然優(yōu)勢(shì)明顯。contraceptive數(shù)據(jù)集上，IDESF比對(duì)比算法平均高出0.163。在hayes-roth數(shù)據(jù)集上，IDESF比對(duì)比算法平均高出0.097。dermatology和wine數(shù)據(jù)集上，六個(gè)算法均取得了較高的AUCarea。IDESF在dermatology數(shù)據(jù)集上AUCarea達(dá)到了1，Centers、Centers_NN、CS-MCS和IDESF在wine數(shù)據(jù)集上AUCarea達(dá)到了1，表明這些算法在對(duì)應(yīng)的數(shù)據(jù)集中完全正確分類所有的測(cè)試數(shù)據(jù)，達(dá)到了最好的效果。從均值來看IDESF依然優(yōu)勢(shì)明顯，IDESF比BPSO-Adaboost-KNN、ECUA、Centers、Centers_NN和CS-MCS分別高出了0.112、0.117、0.06、0.063、0.143。同時(shí)根據(jù)表3可知，IDESF同樣在GM指標(biāo)上獲得了較好的結(jié)果，在contraceptive、dermatology和wine數(shù)據(jù)集上排在第一位，在hayes-roth數(shù)據(jù)集上排在第二位。從均值來看，IDESF比BPSOAdaboost-KNN、ECUA、Centers、Centers_NN和CS-MCS分別高出了0.016、0.116、0.056、0.033、0.024。

表2 六種算法的AUCarea值對(duì)比Table 2 AUCarea value comparison of six algorithms

表3 六種算法的GM值對(duì)比Table 3 Comparison of GM values of six algorithms

綜上所述，通過一系列實(shí)驗(yàn)可知IDESF算法在評(píng)價(jià)指標(biāo)AUCarea和GM上均獲得較為可靠的性能，表明針對(duì)不均衡數(shù)據(jù)分類問題提出的IDESF算法是有效的。

3 結(jié)束語

針對(duì)不均衡分類問題，本文提出了一種集成分類算法IDESF，該算法融合了有放回采樣+SMOTE的兩階段采樣、去除互為最近異類樣本對(duì)的數(shù)據(jù)清洗操作以及基于SPSO的特征選擇方法。放回采樣+SMOTE的兩階段采樣通過增加數(shù)據(jù)集間的差異性，達(dá)到隱式提高分類器間多樣性的目的。此外，放回采樣+SMOTE的兩階段采樣可以平衡數(shù)據(jù)分布，避免分類器傾向于多數(shù)類。數(shù)據(jù)清洗方法去除過采樣引入的噪聲樣本，提高數(shù)據(jù)的可分性。特征選擇可以去除冗余特征和無關(guān)特征，降低算法復(fù)雜度并提高分類性能。多個(gè)對(duì)比實(shí)驗(yàn)表明，IDESF算法與對(duì)比算法相比具有更好的分類效果，可以有效解決數(shù)據(jù)集中樣本分布不均衡的問題。IDESF算法效率較低，所以下一步將試圖在不降低性能的前提下提高其分類效率。