基于熵的過采樣框架

張念蓬，吳 旭，朱 強

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

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

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

經(jīng)典的機器學習算法和模型通常是基于“數(shù)據(jù)集是平衡的”這一假設(shè)建立的，若直接將它們應(yīng)用在不平衡數(shù)據(jù)集上，性能會大幅下降。機器學習算法中的一個重要目標是最小化經(jīng)驗誤差，即一個分類模型的目標是最小化總體分類誤差，而少數(shù)類的分類結(jié)果對于總體來說影響是很小的。而且不平衡度越大，少數(shù)類對總體分類誤差的影響越小。因此，分類器會通過主動保護多數(shù)類實例的方法來提升模型的整體性能，而忽視了對少數(shù)類實例的預測，甚至會將大量少數(shù)類實例誤判為多數(shù)類。這樣顯然是不合理的。在不平衡數(shù)據(jù)的分類過程中，少數(shù)類數(shù)據(jù)的價值通常要大于多數(shù)類數(shù)據(jù)，而且隨著不平衡度的增加，少數(shù)類數(shù)據(jù)的價值會越來越高。例如，在醫(yī)療診斷的過程中，將癌癥患者誤診為健康的代價遠高于將健康的人誤診為癌癥患者的代價，該病人很可能會因此錯過最佳的治療時間，這帶來的后果是非常可怕的。

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

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

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

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

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

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

2 信息熵的介紹

一個集合D的信息熵的計算公式如下：

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

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

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

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

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

3 基于熵的過采樣框架

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

3.1 基于熵的危險集

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

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

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

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

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

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

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

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

3.2 危險集的使用策略

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

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

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

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

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

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

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

3.3 實驗結(jié)果及分析

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

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

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

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

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

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

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

4 總結(jié)與展望

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