鄔長(zhǎng)安,鄭桂榮,郭華平

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

0 引言

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

1 相關(guān)工作

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

(1)

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

(2)

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

(3)

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

(4)

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

(5)

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

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

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

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

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

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

(6)

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

(7)

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

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

(8)

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

定理f(w)的梯度是：

(9)

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

(10)

其中

(11)

(12)

(13)

算法1 LDAI

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

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

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

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

3.重復(fù);

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

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

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

7.令d(k)=-Hkgk；

8.求步長(zhǎng)λ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運(yùn)用了擬牛頓算法[11]，最優(yōu)化目標(biāo)函數(shù)(9)，計(jì)算最佳擬合參數(shù)w.形式化地，該方法可以寫為如下迭代過程：

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

(14)

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

(15)

其中

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

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

(16)

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

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

3.1 數(shù)據(jù)集及實(shí)驗(yàn)設(shè)置

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

為了評(píng)估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模型.對(duì)于每一個(gè)數(shù)據(jù)集，采用10折交叉驗(yàn)證分析算法的性能.另外，在算法公式(9)中，設(shè)置平衡參數(shù)r=0.55.相關(guān)實(shí)驗(yàn)結(jié)果都是使用數(shù)據(jù)挖掘工具洛陽鏟(LySpoon)[12]獲得的.

3.2 實(shí)驗(yàn)結(jié)果

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

表1 實(shí)驗(yàn)數(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個(gè)數(shù)據(jù)集上優(yōu)于LD，與US-LD和OS-LD相比，LDAI也表現(xiàn)出明顯優(yōu)勢(shì).在平均值上，LDAI提升LD的g-mean指標(biāo)高達(dá)16.2個(gè)百分點(diǎn).

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

表5顯示LDAI在f-measure上表現(xiàn)出明顯優(yōu)勢(shì)，具體地，LDAI在12個(gè)數(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ù)類和多數(shù)類上的性能.在此基礎(chǔ)上，提出了一個(gè)LDAI(Logistic Discrimination Algorithms for Imbalance)方法用以解決不平衡分類問題.在16個(gè)UCI數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)的邏輯判別式相比，在保持LD高準(zhǔn)確率的前提下，LDAI有效地提高了召回率、f-measure以及g-mean.與基于欠抽樣和過抽樣的邏輯判別式相比，LDAI也表現(xiàn)出明顯優(yōu)勢(shì).