不平衡類分類問題的邏輯判別式算法

鄔長安,鄭桂榮,郭華平

(信陽師范學(xué)院 計算機與信息技術(shù)學(xué)院, 河南 信陽 464000)

0 引言

數(shù)據(jù)不平衡問題普遍存在于現(xiàn)實世界，其特點是某些類實例明顯多于類.這種不平衡分布使得許多傳統(tǒng)機器學(xué)習(xí)[1-2]方法失效，尤其表現(xiàn)在少數(shù)類實例的預(yù)測性能上.然而，在許多實際應(yīng)用中，正確地識別少數(shù)類比正確識別多數(shù)類更有價值.例如，在癌癥檢測中，大部分病人只是患有一些正常的疾病，少數(shù)病人可能會患有癌癥，因此如何正確地識別癌癥患者就顯得十分有意義.傳統(tǒng)的分類模型(例如邏輯判別式等)以分類準(zhǔn)確率或與其相關(guān)的指標(biāo)作為代價函數(shù)監(jiān)督模型學(xué)習(xí)過程，進(jìn)而使學(xué)習(xí)到的分類器具有較高的分類準(zhǔn)確率.其做法的前提是假設(shè)數(shù)據(jù)集中所有類實例數(shù)目相當(dāng)，這有可能導(dǎo)致學(xué)習(xí)到的模型忽略了少數(shù)類實例，進(jìn)而把少數(shù)類實例誤分為多數(shù)類.然而，在不平衡類問題中準(zhǔn)確率并不是一個有效的評價標(biāo)準(zhǔn)，相反，f-measure[3]、g-mean[4]和召回率是評價不平衡類問題更合適的評估指標(biāo).傳統(tǒng)不平衡類問題處理方法大致可以分為兩大類：基于數(shù)據(jù)和基于算法的方法.前者通過抽樣技術(shù)以重新平衡數(shù)據(jù)分布進(jìn)而在平衡的數(shù)據(jù)集上學(xué)習(xí)模型，如過抽樣、欠抽樣以及SMOTE等[5-6].這些技術(shù)經(jīng)常應(yīng)用于處理不平衡類分類問題中，但是數(shù)據(jù)分布總是千差萬別，很難確定數(shù)據(jù)的實際分布情況.后者通過調(diào)整算法或目標(biāo)函數(shù)使得學(xué)習(xí)到的模型更傾向于正確分類少數(shù)類實例，如兩階段規(guī)則學(xué)習(xí)方法[7]、代價敏感方法[8-9]、one-class方法[10]等.與以上所提方法不同，本文將邏輯判別式應(yīng)用于不平衡類問題.與傳統(tǒng)邏輯判別式不同，本文同時使用似然函數(shù)和召回率構(gòu)建新的目標(biāo)函數(shù)LERM(Likelihood Estimation and Recall Metric).以LERM為基礎(chǔ)，本文提出一種LDAI(Logistic Discrimination Algorithms for Imbalance)模型來處理數(shù)據(jù)不平衡問題.16個UCI[11]數(shù)據(jù)集上的實驗結(jié)果表明，與傳統(tǒng)的邏輯判別式相比，在保持邏輯判別式高準(zhǔn)確率的前提下，LDAI有效地提高了召回率、f-measure值以及g-mean值.與基于欠抽樣和過抽樣的邏輯判別式相比，LDAI也表現(xiàn)出明顯優(yōu)勢.

1 相關(guān)工作

邏輯判別式是一種典型的概率統(tǒng)計分類模型，它通過線性函數(shù)來擬合對數(shù)似然比.對于兩類問題可以表示如下：

(1)

其中：x代表實例，w是擬合參數(shù)，所有實例的各個類的概率之和是1，如下：

(2)

結(jié)合式(1)和式(2)可以得到，

(3)

其相應(yīng)對數(shù)似然函數(shù)為：

(4)

所以目標(biāo)函數(shù)(4)可寫為：

(5)

其中，c是一個與w無關(guān)的參數(shù).

從目標(biāo)函數(shù)(5)中可以發(fā)現(xiàn)，傳統(tǒng)的邏輯判別式試圖最大化正確分類實例的概率之和.這種做法同等對待每種類，而不考慮該實例是多數(shù)類還是少數(shù)類.這導(dǎo)致目標(biāo)函數(shù)忽視了不同類具有不同價值的重要事實，所以該方法不適用于數(shù)據(jù)不平衡問題中.與以上方法不同，本文同時使用似然函數(shù)和召回率構(gòu)建一個新的目標(biāo)函數(shù)來解決不平衡類的分類問題.

2 基于邏輯判別式的不平衡類學(xué)習(xí)

2.1 新的目標(biāo)函數(shù)

傳統(tǒng)的邏輯判別式使用最大似然函數(shù)監(jiān)督參數(shù)學(xué)習(xí)過程，以期獲得最高的分類準(zhǔn)確率.然而，這忽略了少數(shù)類往往比多數(shù)類更有價值的事實，導(dǎo)致少數(shù)類不能正確分類.為了解決該問題，本文使用似然函數(shù)和召回率重新定義了指導(dǎo)參數(shù)學(xué)習(xí)的目標(biāo)函數(shù).下面給出相關(guān)符號：

令類j為Cj={xi|yi=j}，又令

(6)

其中，pij=p(y=j|xi).Pj反映了類j正確分類的實例數(shù).進(jìn)一步地，定義Rj為類j的召回率，即:

(7)

基于似然函數(shù)和召回率的目標(biāo)函數(shù)構(gòu)建如下：

f(w)=L(w)+r×(R1+R2),

(8)

其中：L(w)為對數(shù)似然函數(shù)，其表達(dá)式如式(5)所示；r=qN(q[0,1]，N是實例數(shù)目).通過q，我們可以控制L(w)和召回率的作用.

定理f(w)的梯度是：

(9)

證明對f(w)求導(dǎo)，可以得到:

(10)

其中

(11)

(12)

(13)

算法1 LDAI

輸入：D—訓(xùn)練數(shù)據(jù)集

輸出：擬合參數(shù)w

1.隨機初始化w(1)，給定允許誤差ε>0;

2.設(shè)置H1=In(單位矩陣)，置k=1;

3.重復(fù);

4.用式(9)計算gk=▽f(w(k))；

5.用式(16)計算p(k)和q(k)；

6.用式(15)計算Hk+1；

7.令d(k)=-Hkgk；

8.求步長λk，使得

w(k+1)=w(k)-λkHkf(w(k));

9.令w(k+1)=w(k)+λkd(k)；

10.直到(‖▽f(w(k+1))>ε‖);

11.返回w.

2.2 算法

根據(jù)2.1提供的目標(biāo)函數(shù)，提出一種新的算法叫作LDAI.在學(xué)習(xí)階段，LDAI運用了擬牛頓算法[11]，最優(yōu)化目標(biāo)函數(shù)(9)，計算最佳擬合參數(shù)w.形式化地，該方法可以寫為如下迭代過程：

w(k+1)=w(k)-λkHkf(w(k)),

(14)

其中：λk是第k次迭代沿牛頓方向搜索的最優(yōu)步長,Hk是用BFGS公式對目標(biāo)函數(shù)Hesse矩陣的近似，Hk的計算方法為：

(15)

其中

p(k)=w(k+1)-w(k),

q(k)=f(w(k+1))-f(w(k)).

(16)

相關(guān)細(xì)節(jié)見算法1.首先，算法1隨機初始化參數(shù)w，然后用擬牛頓方法優(yōu)化f(w)，從而找到最佳擬合參數(shù)w.

3 實驗

3.1 數(shù)據(jù)集及實驗設(shè)置

16個數(shù)據(jù)集是從UCI[11]機器學(xué)習(xí)庫中隨機選取的(見表1).這些不平衡數(shù)據(jù)集使用如下方法獲得：1)如果源數(shù)據(jù)是多數(shù)類，選擇其中的兩類，一類被看作少數(shù)類，另一類被視為多數(shù)類；2)如果源數(shù)據(jù)集是二類的，且不平衡率(少數(shù)類實例數(shù)/總實例數(shù))大于0.25，則移出部分少數(shù)類樣本，否則，保持該數(shù)據(jù)不動.

為了評估LDAI(提出的方法)的有效性，把LD、US-LD(欠抽樣邏輯判別式)和OS-LD作為比較參照，其中LD為邏輯判別式，US-LD首先將欠抽樣技術(shù)應(yīng)用于數(shù)據(jù)集，然后在抽樣后的數(shù)據(jù)集上學(xué)習(xí)LD模型.與US-LD類似，OS-LD首先將過抽樣技術(shù)應(yīng)用于數(shù)據(jù)集，然后在抽樣后的數(shù)據(jù)集上學(xué)習(xí)LD模型.對于每一個數(shù)據(jù)集，采用10折交叉驗證分析算法的性能.另外，在算法公式(9)中，設(shè)置平衡參數(shù)r=0.55.相關(guān)實驗結(jié)果都是使用數(shù)據(jù)挖掘工具洛陽鏟(LySpoon)[12]獲得的.

3.2 實驗結(jié)果

LDAI、LD、US-LD和OS-LD在16個數(shù)據(jù)集的實驗結(jié)果如表2至5所示(括號里表示標(biāo)準(zhǔn)差)，其中*、?(○)表明在算法相當(dāng)?shù)臄?shù)據(jù)集上LDAI顯著優(yōu)于其他算法，其中，使用配對t測試(顯著水平為0.05)測試算法優(yōu)劣的顯著性.表的最后一行為算法在所有數(shù)據(jù)集上性能的平均值.

表1 實驗數(shù)據(jù)集信息

表2 LDAI、LD、US-LD和OS-LD的準(zhǔn)確率及標(biāo)準(zhǔn)差

表2顯示，在準(zhǔn)確度上LDAI僅次于LD，但又比US-LD和OS-LD顯著好.US-LD和OS-LD的低準(zhǔn)確率是由抽樣改變了數(shù)據(jù)集類分布導(dǎo)致的.

表3顯示了4種算法在g-mean上的性能.LDAI在8個數(shù)據(jù)集上優(yōu)于LD，與US-LD和OS-LD相比，LDAI也表現(xiàn)出明顯優(yōu)勢.在平均值上，LDAI提升LD的g-mean指標(biāo)高達(dá)16.2個百分點.

表4顯示，在召回率上，LDAI在5個數(shù)據(jù)集上明顯優(yōu)于其他算法.與US-LD相比，LDAI在7個數(shù)據(jù)集上表現(xiàn)稍差，類似地，與OS-LD相比，LDAI在8個數(shù)據(jù)集上表現(xiàn)稍差.該結(jié)果是可以接受的，因為，即使LDAI在某些數(shù)據(jù)集上表現(xiàn)稍差，但該差距并不明顯.總體上，LDAI在召回率上的性能接近OS-LD，而略輸于US-LD.在平均水平上，OS-LD提升LD在召回率的性能高達(dá)21.4%.

表5顯示LDAI在f-measure上表現(xiàn)出明顯優(yōu)勢，具體地，LDAI在12個數(shù)據(jù)集上獲得最好結(jié)果.在平均結(jié)果上，LDAI提升LD的f-measure值到14.1，提升US-LD和OS-LD分別高達(dá)30.2%和25.4%.

以上結(jié)果表明，LDAI能有效提升邏輯判別式在非平衡分類問題中的性能，值得進(jìn)一步研究.

表3 LDAI、LD、US-LD和OS-LD的g-mean值及標(biāo)準(zhǔn)差

表4 LDAI、LD、US-LD和OS-LD的召回率及標(biāo)準(zhǔn)差

表5 LDAI、LD、US-LD and OS-LD的f-measure值及標(biāo)準(zhǔn)差

4 結(jié)論

首先重寫了傳統(tǒng)邏輯判別式的損失函數(shù)，該損失函數(shù)同時考慮模型在少數(shù)類和多數(shù)類上的性能.在此基礎(chǔ)上，提出了一個LDAI(Logistic Discrimination Algorithms for Imbalance)方法用以解決不平衡分類問題.在16個UCI數(shù)據(jù)集上的實驗結(jié)果表明，與傳統(tǒng)的邏輯判別式相比，在保持LD高準(zhǔn)確率的前提下，LDAI有效地提高了召回率、f-measure以及g-mean.與基于欠抽樣和過抽樣的邏輯判別式相比，LDAI也表現(xiàn)出明顯優(yōu)勢.