鄔長安,鄭桂榮,郭華平
(信陽師范學(xué)院 計算機與信息技術(shù)學(xué)院, 河南 信陽 464000)
數(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)勢.
邏輯判別式是一種典型的概率統(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ù)來解決不平衡類的分類問題.
傳統(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.
根據(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.
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]獲得的.
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)差
首先重寫了傳統(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)勢.