張念蓬，吳 旭，朱 強(qiáng)

西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，西安710071

數(shù)據(jù)挖掘是一種在海量數(shù)據(jù)中尋找即時(shí)的、有價(jià)值的信息的技術(shù)[1]。經(jīng)過(guò)近些年的發(fā)展，數(shù)據(jù)挖掘已經(jīng)形成了很多行之有效的模型和算法，它們主要集中在分類、聚類、關(guān)聯(lián)分析等方面。其中，分類也被稱為有監(jiān)督學(xué)習(xí)，這類算法需要對(duì)數(shù)據(jù)的特征和類標(biāo)簽進(jìn)行分析處理，得到不同的特征組合與類標(biāo)簽之間存在的判別規(guī)律，并將這些規(guī)律以知識(shí)的形式保存下來(lái)。當(dāng)需要為新的數(shù)據(jù)判定類別時(shí)，分類算法能利用之前學(xué)得的知識(shí)為其貼上預(yù)測(cè)標(biāo)簽。

盡管數(shù)據(jù)挖掘與機(jī)器學(xué)習(xí)技術(shù)日益趨向成熟并且被廣泛應(yīng)用于實(shí)際問(wèn)題的處理中，但該領(lǐng)域仍面臨著諸多挑戰(zhàn)，如不平衡數(shù)據(jù)集分類問(wèn)題。顧名思義，不平衡數(shù)據(jù)集中至少有一類數(shù)據(jù)的數(shù)量明顯多于或少于其他類的數(shù)據(jù)數(shù)量[2]。這類問(wèn)題應(yīng)用十分廣泛，如VIP 用戶流失的檢測(cè)[3]、欺詐交易識(shí)別[4]、醫(yī)療診斷[5]、銀行破產(chǎn)預(yù)測(cè)和企業(yè)信用評(píng)估[6]等。

經(jīng)典的機(jī)器學(xué)習(xí)算法和模型通常是基于“數(shù)據(jù)集是平衡的”這一假設(shè)建立的，若直接將它們應(yīng)用在不平衡數(shù)據(jù)集上，性能會(huì)大幅下降。機(jī)器學(xué)習(xí)算法中的一個(gè)重要目標(biāo)是最小化經(jīng)驗(yàn)誤差，即一個(gè)分類模型的目標(biāo)是最小化總體分類誤差，而少數(shù)類的分類結(jié)果對(duì)于總體來(lái)說(shuō)影響是很小的。而且不平衡度越大，少數(shù)類對(duì)總體分類誤差的影響越小。因此，分類器會(huì)通過(guò)主動(dòng)保護(hù)多數(shù)類實(shí)例的方法來(lái)提升模型的整體性能，而忽視了對(duì)少數(shù)類實(shí)例的預(yù)測(cè)，甚至?xí)⒋罅可贁?shù)類實(shí)例誤判為多數(shù)類。這樣顯然是不合理的。在不平衡數(shù)據(jù)的分類過(guò)程中，少數(shù)類數(shù)據(jù)的價(jià)值通常要大于多數(shù)類數(shù)據(jù)，而且隨著不平衡度的增加，少數(shù)類數(shù)據(jù)的價(jià)值會(huì)越來(lái)越高。例如，在醫(yī)療診斷的過(guò)程中，將癌癥患者誤診為健康的代價(jià)遠(yuǎn)高于將健康的人誤診為癌癥患者的代價(jià)，該病人很可能會(huì)因此錯(cuò)過(guò)最佳的治療時(shí)間，這帶來(lái)的后果是非?？膳碌摹?/p>

1 不平衡數(shù)據(jù)的處理手段

用于提高不平衡數(shù)據(jù)集分類性能的技術(shù)整體上可以被分為兩類：算法級(jí)方法和數(shù)據(jù)級(jí)方法。

算法級(jí)方法包括改進(jìn)經(jīng)典算法、代價(jià)敏感方法和分類器集成。修正分類算法以處理不平衡問(wèn)題的策略是算法級(jí)技術(shù)[2]。代價(jià)敏感方法則是為不同的數(shù)據(jù)類型提供不同的錯(cuò)誤分類代價(jià)。分類器集成是需要訓(xùn)練多個(gè)不同的弱分類模型，并按照特定的方式將弱分類模型組合起來(lái)，由它們的共同決策來(lái)預(yù)測(cè)數(shù)據(jù)的類標(biāo)簽，從而提高數(shù)據(jù)預(yù)測(cè)的準(zhǔn)確性[7]。

數(shù)據(jù)級(jí)方法可以看作是一種獨(dú)立于分類器的技術(shù)，用于重新平衡數(shù)據(jù)分布，使標(biāo)準(zhǔn)算法以用戶的目標(biāo)為中心[8]。特別地，數(shù)據(jù)級(jí)方法可以分為欠采樣多數(shù)類實(shí)例[9]和過(guò)采樣少數(shù)類實(shí)例[10]兩種方案。欠采樣方法通過(guò)減少多數(shù)類實(shí)例的數(shù)量來(lái)創(chuàng)建原始不平衡數(shù)據(jù)集的平衡子集。過(guò)采樣方法通過(guò)增加少數(shù)類數(shù)據(jù)實(shí)例的個(gè)數(shù)來(lái)平衡數(shù)據(jù)集。Chawla 等人[11]提出一種基于線性插值的過(guò)采樣算法SMOTE。SMOTE 算法的主要思想是隨機(jī)選取一些少數(shù)類實(shí)例作為種子，并選取種子的k個(gè)最近鄰中的一個(gè)或多個(gè)少數(shù)類實(shí)例，與其結(jié)合為鄰居對(duì)適應(yīng)合成過(guò)采樣方法（ADASYN）[10]、邊界SMOTE 算法（borderline）[12]、安全級(jí)SMOTE算法（safe）[13]等。

過(guò)采樣技術(shù)通常是處理不平衡數(shù)據(jù)集的首選方法。傳統(tǒng)的衡量類不平衡的指標(biāo)是不平衡率IR，即多數(shù)類數(shù)據(jù)的數(shù)量與少數(shù)類數(shù)據(jù)的數(shù)量之比。IR反映了數(shù)據(jù)集在數(shù)量上的不平衡程度，但沒(méi)有度量分布上的不平衡程度。即使數(shù)據(jù)集是數(shù)量平衡的，類分布的不平衡仍然可能存在[14]。此外，少數(shù)類集合的分類準(zhǔn)確性與信息實(shí)例的數(shù)量有關(guān)，而與少數(shù)類實(shí)例的數(shù)量無(wú)關(guān)[15]。

因此，衡量少數(shù)類與多數(shù)類之間數(shù)據(jù)分布的不平衡程度是重要的。本文利用信息熵度量數(shù)據(jù)集的局部密度信息，從分布上考慮數(shù)據(jù)集的不平衡程度，并提出了基于熵的危險(xiǎn)集的概念和它的三種使用策略，即基于熵的危險(xiǎn)集過(guò)采樣算法（EDgS）、基于熵的安全集過(guò)采樣算法（ESS）和基于熵的自適應(yīng)過(guò)采樣算法（EAS）。基于熵的過(guò)采樣框架具體分為三個(gè)部分：首先介紹了數(shù)據(jù)集熵差的具體計(jì)算方法和危險(xiǎn)集的概念，這一部分是該框架的基礎(chǔ)和起點(diǎn)；其次介紹了危險(xiǎn)集的三種使用策略，分別是在危險(xiǎn)集上過(guò)采樣、在危險(xiǎn)集的補(bǔ)集上過(guò)采樣和自適應(yīng)的過(guò)采樣，這三種策略的側(cè)重點(diǎn)不同，特點(diǎn)和優(yōu)勢(shì)也各不相同，適用于不同分布的數(shù)據(jù)集；最后，本文在算法中加入了生成實(shí)例的檢測(cè)機(jī)制，若生成實(shí)例能通過(guò)檢測(cè)，則該實(shí)例可以在數(shù)據(jù)分布的意義下平衡數(shù)據(jù)集，反之，該實(shí)例不具備平衡數(shù)據(jù)分布的能力，將其刪掉即可。

2 信息熵的介紹

一個(gè)集合D的信息熵的計(jì)算公式如下：

其中，pi通常為第i條數(shù)據(jù)的概率，本文用基于距離的局部密度在整體密度中的權(quán)重代替。眾所周知，熵可以度量數(shù)據(jù)分布的不確定性。因此，本文利用熵差來(lái)度量數(shù)據(jù)集分布的不平衡程度，這與以往的IR完全不同。

在圖1 中，可以清楚地看到使用熵差（ED）的優(yōu)點(diǎn)。這兩個(gè)數(shù)據(jù)集具有不同的ED 和相同的IR。對(duì)于圖1的A，兩個(gè)類之間沒(méi)有重疊區(qū)域，并具有清晰的分類邊界，這使得任何一個(gè)簡(jiǎn)單的分類器都能很容易地完成識(shí)別；圖1 的B 則完全不同。顯然，IR 無(wú)法區(qū)分這兩個(gè)分布不同的數(shù)據(jù)集?？傊@些少數(shù)類的代表性實(shí)例是研究少數(shù)類分布的關(guān)鍵。以往的研究表明，固定IR時(shí)，少數(shù)類中的代表性實(shí)例越多，分類器的分類性能越好[14-15]。因此，用IR作為測(cè)量不平衡度的唯一指標(biāo)是不合適的。

圖1 ED相同、IR不同的兩個(gè)數(shù)據(jù)集

熵通常用來(lái)度量數(shù)據(jù)分布的不確定性，它可以看作是信息分布的反義詞。換句話說(shuō)，數(shù)據(jù)分布的隨機(jī)性越強(qiáng)，它包含的信息就越少[16]。對(duì)于不平衡數(shù)據(jù)來(lái)說(shuō)，更分散的類內(nèi)分布和更少的數(shù)據(jù)量將意味著更高的熵。在這種情況下，熵被引入到輸入空間中作為數(shù)據(jù)分布的度量方式。

另外，本文基于信息熵將少數(shù)類數(shù)據(jù)集分為危險(xiǎn)集和安全集。如果一個(gè)少數(shù)類實(shí)例屬于危險(xiǎn)集，則表示這個(gè)實(shí)例周圍的少數(shù)類分布比較稀疏，在這些區(qū)域過(guò)采樣，可以有效擴(kuò)大數(shù)據(jù)集中少數(shù)類的范圍，反之則表示實(shí)例周圍的少數(shù)類分布比較密集，在這些區(qū)域過(guò)采樣，會(huì)降低錯(cuò)分多數(shù)類實(shí)例的風(fēng)險(xiǎn)。

3 基于熵的過(guò)采樣框架

本章的主要內(nèi)容是基于熵的過(guò)采樣框架，具體可以分為以下三個(gè)部分：第一部分是數(shù)據(jù)集的熵的計(jì)算方法和計(jì)算過(guò)程中涉及到的統(tǒng)計(jì)量的含義，并在此基礎(chǔ)上形成基于熵的危險(xiǎn)集，討論了危險(xiǎn)集的意義；第二部分為危險(xiǎn)集的使用策略和不同的使用策略所對(duì)應(yīng)的含義，并給出不同策略對(duì)應(yīng)的具體算法流程；第三部分通過(guò)實(shí)驗(yàn)驗(yàn)證了算法的有效性。

3.1 基于熵的危險(xiǎn)集

本節(jié)介紹熵差的具體計(jì)算過(guò)程，并形成相應(yīng)的算法流程。

給定一個(gè)訓(xùn)練數(shù)據(jù)集D，包含實(shí)例X={xi|x∈Rn,i=1,2,…,m}，實(shí)例所屬類別為C={cl|l=1,2}，相應(yīng)的實(shí)例數(shù)量表示為m1、m2。數(shù)據(jù)集D中的任意兩個(gè)實(shí)例表示為xi=(xi1,xi2,…,xin) 和xj=(xj1,xj2,…,xjn)，這兩個(gè)實(shí)例的距離計(jì)算公式通常定義為歐氏距離，如下：

使用公式（3）為給定數(shù)據(jù)集的第i個(gè)實(shí)例定義一個(gè)基于密度的實(shí)例位置統(tǒng)計(jì)量：

其中Qk(xi)表示xi的k近鄰集合，sim(?,?)為相似度度量公式，通常使用歐氏距離。因此，μk(xi)是一個(gè)局部密度度量公式，用于測(cè)量xi距離其k近鄰的平均距離，同時(shí)表達(dá)了實(shí)例xi附近的密度信息。第i個(gè)樣本的基于密度的類位統(tǒng)計(jì)量由下式給出：

式中，ωi是xi在cl總密度度量中的比例。因此，每個(gè)實(shí)例的類內(nèi)密度可以通過(guò)基于密度的類位統(tǒng)計(jì)來(lái)測(cè)量。xi附近的密度越高，μk(xi)和ωi就越小。換句話說(shuō)，ωi的大小反映了xi的類內(nèi)密度。

每一類的熵由公式（5）計(jì)算。令c1和c2分別代表少數(shù)類和多數(shù)類，容易得到E1≥E2>0。眾所周知，熵是由信息量的多少和信息對(duì)稱性決定的。實(shí)驗(yàn)結(jié)果表明，在不平衡數(shù)據(jù)集上，多數(shù)類和少數(shù)類的熵的大小通常依賴于信息量的多少。也就是說(shuō)，少數(shù)類的類內(nèi)熵通常大于多數(shù)類的類內(nèi)熵。在此基礎(chǔ)上，信息對(duì)稱性影響類內(nèi)熵的大小。為了度量數(shù)據(jù)集分布的不平衡程度，本文提出了一種新的度量方法：

另外，本文將少數(shù)類實(shí)例按ωi排序，截取較大的一半，用來(lái)形成危險(xiǎn)集Dg。由此將少數(shù)類數(shù)據(jù)集分為危險(xiǎn)集和安全集。如果一個(gè)少數(shù)類實(shí)例屬于危險(xiǎn)集，則表示這個(gè)實(shí)例周圍的少數(shù)類分布比較稀疏，在這些區(qū)域過(guò)采樣，可以有效擴(kuò)大數(shù)據(jù)集中少數(shù)類的范圍，但是也會(huì)提高錯(cuò)分多數(shù)類實(shí)例的風(fēng)險(xiǎn)；反之則表示這個(gè)實(shí)例周圍的少數(shù)類分布比較密集，在這些區(qū)域過(guò)采樣，雖然生成的實(shí)例的多樣性有所下降，但同時(shí)也會(huì)降低錯(cuò)分多數(shù)類實(shí)例的風(fēng)險(xiǎn)。

數(shù)據(jù)集的基于熵的危險(xiǎn)集算法（EDg）的具體細(xì)節(jié)見算法1。

3.2 危險(xiǎn)集的使用策略

EDg 算法為每個(gè)少數(shù)類實(shí)例計(jì)算出基于密度的類位統(tǒng)計(jì)量，也就是數(shù)據(jù)分布意義下的權(quán)重，權(quán)重越大，說(shuō)明該實(shí)例周圍的類內(nèi)分布越稀疏。因此，本節(jié)提出三種基于熵的過(guò)采樣策略，分別是在危險(xiǎn)集上過(guò)采樣、在安全集上過(guò)采樣和自適應(yīng)的過(guò)采樣策略。這三種過(guò)采樣的策略在合成過(guò)程中都采用線性插值的辦法，只是在選取種子對(duì)時(shí)有所不同。

基于熵的危險(xiǎn)集過(guò)采樣算法（EDgS）首先利用EDg算法求出危險(xiǎn)集，其次在危險(xiǎn)集上隨機(jī)的選擇種子對(duì)，并使用公式（7）實(shí)現(xiàn)線性插值：

其中δ∈U[0,1]，是均勻分布的隨機(jī)數(shù)。最后檢測(cè)整個(gè)數(shù)據(jù)集中ED的變化，若ΔED<0，則說(shuō)明新實(shí)例在數(shù)據(jù)分布上平衡了數(shù)據(jù)集，是有價(jià)值的，應(yīng)該保留；否則，刪除新生成的實(shí)例。這樣生成的新實(shí)例不僅可以在數(shù)據(jù)分布上平衡數(shù)據(jù)集，也可以有效擴(kuò)大數(shù)據(jù)集中少數(shù)類的范圍和多樣性。EDgS的實(shí)現(xiàn)過(guò)程見算法2。

基于熵的安全集過(guò)采樣算法（ESS）首先利用EDg算法求出危險(xiǎn)集，在Cmin上求Dg的補(bǔ)集，得到安全集Ds，其次在Ds上隨機(jī)的選擇種子對(duì)，并使用公式（7）實(shí)現(xiàn)線性插值；其余的步驟與EDgS 算法相同。但相較于EDgS 算法，ESS 算法生成的新實(shí)例的多樣性會(huì)有所下降，錯(cuò)分多數(shù)類實(shí)例的風(fēng)險(xiǎn)也會(huì)顯著降低。ESS的實(shí)現(xiàn)過(guò)程見算法3。

基于熵的自適應(yīng)過(guò)采樣算法（EAS）首先為每個(gè)少數(shù)類實(shí)例賦權(quán)，權(quán)重為ωi；然后在考慮權(quán)重的基礎(chǔ)上隨機(jī)選擇少數(shù)類實(shí)例xp，在Q(xp)中隨機(jī)選擇xq，并使用公式（7）實(shí)現(xiàn)線性插值；其余的步驟與EDgS算法相同。

與EDgS 算法和ESS 算法相比，EAS 算法可以有效增加生成的少數(shù)類數(shù)據(jù)的多樣性，減小錯(cuò)分多數(shù)類實(shí)例的風(fēng)險(xiǎn)。EAS的實(shí)現(xiàn)過(guò)程見算法4。

本節(jié)利用危險(xiǎn)集的思想，給出了一個(gè)基于熵的過(guò)采樣策略的框架，并在此框架下得到EDgS、ESS和EAS算法，這3 個(gè)算法在理論上各有側(cè)重。如EDgS 在危險(xiǎn)集上生成新實(shí)例，會(huì)顯著增加少數(shù)類數(shù)據(jù)的多樣性；ESS在安全集上生成新實(shí)例，更加注重生成實(shí)例的安全性；EAS則在整個(gè)少數(shù)類數(shù)據(jù)集上自適應(yīng)的生成少數(shù)類，是前兩種算法折中的結(jié)果。

3.3 實(shí)驗(yàn)結(jié)果及分析

為驗(yàn)證提出的算法的有效性，本節(jié)選取來(lái)自UCI[17]和KEEL-dataset repository[18]中的6 個(gè)二分類數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)仿真，它們的詳細(xì)介紹見表1。每個(gè)數(shù)據(jù)集分別通過(guò)7 種過(guò)采樣算法（SMOTE、borderline、EDgS、safe、ESS、ADASYN、EAS）進(jìn)行處理，且選擇SVM 作為基分類器。評(píng)價(jià)指標(biāo)選擇AUC和召回率，因?yàn)锳UC能客觀地反映分類器對(duì)不平衡數(shù)據(jù)集的綜合預(yù)測(cè)能力，召回率能反映出分類器對(duì)少數(shù)類實(shí)例的分類準(zhǔn)確度。顯然，AUC和召回率的值越大，算法的性能就越好。

表1 二分類數(shù)據(jù)集的描述信息

表2 和表3 分別列出了8 個(gè)算法在6 個(gè)數(shù)據(jù)集上的AUC和召回率的得分和排名的詳細(xì)信息。

表2 8個(gè)算法在6個(gè)數(shù)據(jù)集上的AUC得分和排名

表3 8個(gè)算法在6個(gè)數(shù)據(jù)集上的召回率得分和排名

對(duì)于基于線性插值的算法來(lái)說(shuō)，borderline 和EDgS都是在危險(xiǎn)集上進(jìn)行過(guò)采樣，safe和ESS都是在安全集上進(jìn)行過(guò)采樣，ADASYN 和EAS 都是在整個(gè)少數(shù)類數(shù)據(jù)集上進(jìn)行自適應(yīng)的過(guò)采樣。因此，將上述算法兩兩之間進(jìn)行對(duì)比是比較合理的。可以看出，提出的EDgS、ESS和EAS的AUC得分均強(qiáng)于borderline、safe 和ADASYN。特別是EAS 算法，在對(duì)ADASYN 算法進(jìn)行提升的同時(shí)，也在多個(gè)數(shù)據(jù)集上取得了很好的名次，如數(shù)據(jù)集abalone17vs78910、alocks0 和ecoli0vs1。這體現(xiàn)了本文提出的算法在綜合預(yù)測(cè)能力上的優(yōu)勢(shì)。

不平衡數(shù)據(jù)分類問(wèn)題中少數(shù)類實(shí)例通常更加珍貴，因此少數(shù)類被正確分類的比例是很重要的。本文算法在召回率得分上顯示出非常強(qiáng)的競(jìng)爭(zhēng)力。用于實(shí)驗(yàn)的6個(gè)數(shù)據(jù)集中，基于熵差的過(guò)采樣算法只在ecoli0vs1上表現(xiàn)一般，這可能是由于該數(shù)據(jù)集的ED很小，而IR較大，相較于傳統(tǒng)的不平衡度量方法，本文算法不能很好地識(shí)別少數(shù)類和多數(shù)類。

4 總結(jié)與展望

本文利用熵信息來(lái)度量數(shù)據(jù)集的不平衡程度，為各種變量賦予實(shí)際意義，并給出用熵差計(jì)算數(shù)據(jù)分布不平衡度的具體方法；另外，利用熵信息計(jì)算出每個(gè)點(diǎn)周圍的局部密度，得到了基于熵的危險(xiǎn)集。隨后給出了危險(xiǎn)集的使用策略和對(duì)應(yīng)的算法，即EDgS、ESS 和EAS 算法。實(shí)驗(yàn)證明，本文的研究?jī)?nèi)容可以有效提升經(jīng)典過(guò)采樣算法的性能。但不可否認(rèn)的是，該理論和模型也存在一定的局限性，即對(duì)熵差較小的數(shù)據(jù)集的識(shí)別能力較差。針對(duì)這個(gè)問(wèn)題，可以將IR和ED相結(jié)合，在利用ED檢測(cè)數(shù)據(jù)分布的不平衡度的同時(shí)，使用IR 來(lái)體現(xiàn)數(shù)據(jù)集數(shù)量上的不平衡度，從而進(jìn)一步提高對(duì)數(shù)據(jù)集的綜合識(shí)別能力。這也是接下來(lái)的研究?jī)?nèi)容和方向。