蘇樂群，馮愛民

(南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 210016)

0 引言

傳統(tǒng)的分類算法通常在假定樣本均衡并具有相同的誤分代價(jià)的基礎(chǔ)上致力于提高分類器的泛化精度，但是在實(shí)際的數(shù)據(jù)挖掘問題中，不同的分類錯(cuò)誤往往帶來不同的損失，這種情況下應(yīng)當(dāng)致力于減少錯(cuò)誤分類帶來的代價(jià)而不是提高分類準(zhǔn)確率［1］。在數(shù)據(jù)極端不平衡或者誤分類代價(jià)存在很大差異的情況下，不考慮不同的樣本誤分類代價(jià)建立的分類模型是沒有意義的。以當(dāng)前出現(xiàn)的埃博拉病毒為例，明顯將病毒感染者劃分為健康人比將健康人劃分為病毒感染者的代價(jià)高得多，此時(shí)分類精度并不能代表分類性能，因此將代價(jià)考慮進(jìn)學(xué)習(xí)過程具有現(xiàn)實(shí)意義。

從1974 年Habbema［2］等人提出代價(jià)敏感問題開始，針對基于錯(cuò)誤分類代價(jià)的代價(jià)敏感問題已經(jīng)展開了大量的研究工作。目前代價(jià)敏感學(xué)習(xí)的方法主要分成2 大類:

1)重建訓(xùn)練集，然后使用現(xiàn)有的算法實(shí)現(xiàn)代價(jià)敏感學(xué)習(xí)，主要方法為重采樣法，重采樣方法是根據(jù)樣本不同的誤分類代價(jià)，增加高誤分代價(jià)類訓(xùn)練樣本的上采樣和減少低誤分代價(jià)類樣本的下采樣方法，代表算法有Boost 算法和Chawla［3］等人提出的SMOTE算法，由于在不平衡問題中更容易錯(cuò)分的是稀有類樣本，Boost 算法(Schapire，1999)通過在每次迭代中添加錯(cuò)分樣本使得分類器在下一次分類中更注重稀有樣本達(dá)到對非平衡數(shù)據(jù)分類有良好的效果;SMOTE方法首先為每個(gè)稀有類樣本隨機(jī)選出幾個(gè)鄰近樣本，并且在該樣本與這些鄰近的樣本的連線上隨機(jī)取點(diǎn)，生成無重復(fù)的新的稀有類樣本，將原始不平衡的訓(xùn)練樣本變得平衡，從而提高分類器對稀有類的識別率。隨后Chawla 在2003 年提出SMOTEBoost 算法，它結(jié)合了SMOTE 和Boost 算法的優(yōu)點(diǎn)，在每次迭代后為稀有類增加人工合成樣本，實(shí)驗(yàn)表明該算法能夠獲得比原始2 種算法更好的性能，但都有著增加訓(xùn)練時(shí)間或損失樣本信息的缺點(diǎn)。

2)重新設(shè)計(jì)分類器，包含閾值移動(dòng)法和樣本加權(quán)法，MetaCost［4］是一種典型的閾值移動(dòng)方法，它利用了bagging 集成方法［5］來估計(jì)后驗(yàn)概率，然后使用閾值移動(dòng)方法對訓(xùn)練集中的樣本重新標(biāo)記，最后在改變后的訓(xùn)練集上學(xué)習(xí)一個(gè)最小化錯(cuò)誤率的分類器。樣本加權(quán)法則是對不同類別中的樣本被賦予不同的權(quán)值，使得高代價(jià)樣本具有更大的權(quán)值，然后在帶有權(quán)值的數(shù)據(jù)集上利用權(quán)值信息學(xué)習(xí)的方法訓(xùn)練一個(gè)以最小化錯(cuò)誤率為目標(biāo)的標(biāo)準(zhǔn)分類器，代價(jià)敏感支持向量機(jī)［6-9］也是基于這個(gè)思想實(shí)現(xiàn)的，此外Chen 等人在2005 年提出的支持向量修剪方法，針對不平衡數(shù)據(jù)通過改變2 類在軟分類器中松弛變量前的系數(shù)來達(dá)到效果。

近年來許多學(xué)者在代價(jià)敏感問題上基于前人基礎(chǔ)提出了一些更加優(yōu)越的算法，如曹瑩(2012)等人針對Boost、Adacost 等算法在不平衡問題中進(jìn)行權(quán)值調(diào)整策略損壞了這些算法最重要的Boosting 特性提出了AsyB 與AsyBL［10］算法，通過對分類間隔的指數(shù)損失函數(shù)以及Logit 損失函數(shù)進(jìn)行代價(jià)敏感改造，在理想情況下，優(yōu)化這些損失函數(shù)最終收斂到代價(jià)敏感貝葉斯決策，通過實(shí)驗(yàn)證明了該2 種算法能夠合理逼近最優(yōu)代價(jià)敏感貝葉斯決策，使得錯(cuò)分類代價(jià)隨著迭代的進(jìn)行呈指數(shù)下降，最終得到具有更低錯(cuò)分類代價(jià)的代價(jià)敏感分類器。而在考慮到不同屬性存在不同代價(jià)的情況，阮曉宏(2013)等人提出異構(gòu)代價(jià)敏感決策樹分類算法［11］，充分考慮了不同代價(jià)在分裂屬性選擇中的作用，構(gòu)建了一種基于異構(gòu)代價(jià)的分裂屬性選擇模型，設(shè)計(jì)了基于代價(jià)敏感的剪枝標(biāo)準(zhǔn)，避免了基于HCAl 分裂屬性選擇中的因?qū)傩孕畔⑻卣髦颠^小而被忽略的風(fēng)險(xiǎn)和誤分類代價(jià)過大而被放大的可能，實(shí)驗(yàn)結(jié)果表明該方法在處理異構(gòu)代價(jià)問題上能夠獲得穩(wěn)健有效的性能。

2000 年，M.E.Tipping 提出一種稀疏概率模型即相關(guān)向量機(jī)(Relevance Vector Machines，RVM)［10］，它是在一種基于貝葉斯框架的稀疏學(xué)習(xí)模型。同支持向量機(jī)(SVM)相比，RVM 不僅具備由于運(yùn)用自相關(guān)決策理論(Automatic Relevance Determination，ARD)獲得的更強(qiáng)的稀疏性，而且具有極大地減少核函數(shù)的計(jì)算量、克服所選核函數(shù)必需滿足Mercer 條件的缺點(diǎn)及更強(qiáng)的泛化能力等優(yōu)點(diǎn)。

即使RVM 具有如此優(yōu)越的性能，但同其它分類算法一樣不具有代價(jià)敏感性，不能適用于代價(jià)敏感學(xué)習(xí)。為將性能優(yōu)越的RVM 用以解決代價(jià)敏感問題，本文基于上述代價(jià)敏感性學(xué)習(xí)方法中的第二類方法的樣本加權(quán)法，提出代價(jià)敏感相關(guān)向量分類算法(CSRVC)。

1 相關(guān)向量機(jī)

在模式分類中，相關(guān)向量機(jī)使用基于貝葉斯框架的稀疏學(xué)習(xí)模型，在先驗(yàn)參數(shù)的結(jié)構(gòu)下基于自相關(guān)決策理論(ARD)來移除不相關(guān)的點(diǎn)，從而獲得稀疏化的模型，具備著良好的稀疏性和泛化性能。

其中w=(w0，w1，w2，…，wn)，Φ=(1，φ1，φ2，…，φn)T為基函數(shù)，φn=K(x，xn)

RVM 核函數(shù)假設(shè)使用的是RBF 核函數(shù):

這里不要求基函數(shù)為正定的，因此核函數(shù)不必要滿足Mercer 條件。

相關(guān)向量機(jī)［12］的分類模型就是計(jì)算輸入屬于期望類別的后驗(yàn)概率，實(shí)際上，相關(guān)向量機(jī)的分類模型將f(x，w)通過logistic Sigmoid 函數(shù):

轉(zhuǎn)換線性模型，則似然估計(jì)概率可寫為(伯努利分布)［13］，假設(shè)樣本獨(dú)立同分布情況下，有:

為了保證模型的稀疏性，相關(guān)向量機(jī)提出了通過在參數(shù)w 上定義受超參數(shù)α 控制的Gaussian 先驗(yàn)概率，在貝葉斯框架下進(jìn)行機(jī)器學(xué)習(xí)，利用自相關(guān)決策理論(Automatic Relevance Determination，ARD)［14］來移除不相關(guān)的點(diǎn)，從而實(shí)現(xiàn)稀疏化。即假設(shè)權(quán)重向量w 的第i 個(gè)分量wi服從均值為0，方差為的Gaussian 分布。

定義權(quán)重的高斯先驗(yàn):

其中α 為N+1 維參數(shù)。這樣為每一個(gè)權(quán)值(或基函數(shù))配置獨(dú)立的超參數(shù)是稀疏貝葉斯模型最顯著的特點(diǎn)，也是導(dǎo)致模型具有稀疏性的根本原因。由于這種先驗(yàn)概率分布是一種自動(dòng)相關(guān)判定(Automatic Relevance Determination，ARD)先驗(yàn)分布，模型訓(xùn)練結(jié)束后，許多權(quán)值為0，與它對應(yīng)的基函數(shù)將被刪除，實(shí)現(xiàn)了模型的稀疏化。而非零權(quán)值的基函數(shù)所對應(yīng)的樣本向量被稱為相關(guān)向量，這種學(xué)習(xí)機(jī)被稱為相關(guān)向量機(jī)。

2 代價(jià)敏感相關(guān)向量分類

2.1 模型的提出

盡管標(biāo)準(zhǔn)RVM 是一種強(qiáng)大的模式分類算法，但它依然是基于精度的，不能直接用于代價(jià)敏感問題。鑒于不同樣本的誤分類具有不同的代價(jià)，本文把每類樣本的不同誤分類代價(jià)集成到RVM 的設(shè)計(jì)中，以最小化平均誤分類代價(jià)為目的設(shè)計(jì)CS-RVC 算法。

假設(shè)樣本的誤分代價(jià)是基于類別的代價(jià)，即正類樣本和負(fù)類樣本的誤分類代價(jià)不同，誤分類代價(jià)只與類別有關(guān)。CS-RVC 通過樣本加權(quán)方法在2 類樣本上集成不同的代價(jià)敏感因子c+和c-，樣本標(biāo)記tn重新表示為:

由于不同誤分類代價(jià)的引入，式(3)所表示RVM中使用λ(fn)和1 -λ(fn)來表示正確分類為正類和正確分類為負(fù)類的概率的Sigmoid 函數(shù)不能直接用于代價(jià)敏感問題。因此CS-RVC 使用了一種改進(jìn)的Sigmoid 函數(shù):

相應(yīng)的誤分類代價(jià)似然函數(shù)表示為:

其中fn=f(xn，w)，求解最小誤分類代價(jià)似然即為解決代價(jià)敏感分類問題的關(guān)鍵。

改進(jìn)后的Sigmoid 函數(shù)可用性可用圖1 來說明，虛線表示負(fù)類樣本，y 軸左側(cè)為負(fù)類面，同理實(shí)線表示正類樣本，y 軸右側(cè)圍正類面，從圖中可以看到當(dāng)樣本代價(jià)因子相同時(shí)，改進(jìn)后的σ(y)與λ(y)等價(jià)適用到解決平衡分類問題，當(dāng)負(fù)類的誤分代價(jià)高于正類誤分代價(jià)時(shí)，錯(cuò)誤地分類負(fù)類樣本將帶來更高的誤分代價(jià)，抑制了負(fù)類樣本錯(cuò)誤分類的概率，達(dá)到了代價(jià)敏感分類的目的。

圖1 改進(jìn)Sigmoid 函數(shù)

利用自相關(guān)決策理論(ARD)，定義權(quán)重的高斯先驗(yàn)為:

根據(jù)貝葉斯理論推導(dǎo)出，w 的后驗(yàn)概率表示為:

2.2 模型的求解

對w 和α 求解時(shí)，使用Mackay［15］提出的高斯二次逼近方法，當(dāng)α 一定時(shí)，要找到最大后驗(yàn)概率值wMP，即要找到高斯近似分布的眾數(shù)位置μMP，因此后驗(yàn)概率最大估計(jì)等同于:

式中fn=f(xn，w)。

求得后驗(yàn)概率函數(shù)關(guān)于w 的梯度向量及海塞因(Hessian)矩陣:

式中A=diag(α1，α2，…，αn)。

通過牛頓方法(Newton’s Method)可以較快找到wMP，計(jì)算如下:

Gauss 正態(tài)分布來逼近后驗(yàn)概率分布的Laplace方法，是對后驗(yàn)概率分布的眾數(shù)位置uMP處的函數(shù)的二次逼近。在IRLS 迭代收斂后，得到以權(quán)值向量μMP≈wMP為中心的近Gauss 分布，均值uMP，方差Σ=(ΦTBΦ+A)-1。

同樣地，使用Laplace 逼近方法可以將邊緣似然函數(shù)近似表示為:

近似的邊緣似然函數(shù)對數(shù)的形式為:

式中C=B+ΦA(chǔ)-1ΦT

2.3 超參數(shù)優(yōu)化

將權(quán)重向量w 看作成一個(gè)隱藏變量，用EM 算法［16］來估計(jì)超參數(shù)α 的值，表達(dá)為:

直接對式(15)求偏導(dǎo)有:

式中，μi=0 是后驗(yàn)概率p(w|R，α)的均值向量μ 的第i 個(gè)后驗(yàn)概率，Σii是后驗(yàn)概率，p(w|R，α)的方差Σ的第i 個(gè)對角元素。

2.4 模型求解步驟

模型的求解步驟如圖2 所示。

圖2 模型的求解步驟

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

3.1 二維人工數(shù)據(jù)實(shí)驗(yàn)

為觀察相關(guān)向量分類算法(RVC)和代價(jià)敏感相關(guān)向量分類算法(CS-RVC)分類邊界的位置，在隨機(jī)生成的二維樣本上實(shí)驗(yàn)。設(shè)類1 樣本的誤分代價(jià)為1，類2 的誤分類代價(jià)為5，代價(jià)矩陣如表1 所示，使用高斯核函數(shù)，高斯核帶寬參數(shù)width 搜索范圍取2t，其中t∈{-2，-1，0，1，2}，搜索步長為1。

表1 代價(jià)矩陣

從表2 中可以很清晰地看到核帶寬參數(shù)的選擇對代價(jià)敏感分類帶來的影響，選擇一個(gè)合適核帶寬同樣顯得很為重要。通過查資料可知SVM 的稀疏性為20%左右，由此可以看到CS-RVC 優(yōu)越的稀疏性。

表2 核帶寬參數(shù)選擇對RVC 與CS—RVC 的分類性能影響

由圖3 可以清晰地看到，相對于RVC 而言，CSRVC 的分類邊界明顯趨向于盡量分對誤分類代價(jià)高的2 類樣本，盡管分類精度下降，但是分類代價(jià)較高的類2 樣本的分類正確率明顯提高，使誤分類的代價(jià)大大降低。

3.2 UCI 數(shù)據(jù)集實(shí)驗(yàn)

實(shí)驗(yàn)使用了2 個(gè)UCI 數(shù)據(jù)集Heart Disease 和German Credit，2 個(gè)數(shù)據(jù)集的符號屬性轉(zhuǎn)化成整型，Heart 數(shù)據(jù)集中標(biāo)記為‘健康人’的樣本為正例，‘病人’和‘欺詐’為負(fù)例，Heart 數(shù)據(jù)集包含139 個(gè)正例與164 個(gè)負(fù)例。German 數(shù)據(jù)集中包含300 正例和700 負(fù)例，2 個(gè)數(shù)據(jù)集的代價(jià)矩陣同為圖3 所示，在每個(gè)數(shù)據(jù)集上取10 次實(shí)驗(yàn)的平均值，每次遞增的選擇一定數(shù)目的樣本組成訓(xùn)練集，其余樣本為測試集，圖4 和圖5 為實(shí)驗(yàn)結(jié)果。

如圖4 中所示的RVC 和CS-RVC 在2 個(gè)UCI 數(shù)據(jù)集上的平均誤分類代價(jià)，可以很清晰的看到由于引入了代價(jià)敏感因子使得CS-RVC 比RVC 相比有著小得多的平均分類代價(jià)，實(shí)現(xiàn)了代價(jià)敏感挖掘。

圖3 隨機(jī)樣本上的分類超平面

圖4 RVC 和CS-RVC 測試集上平均誤分類代價(jià)

圖5 RVC 和CS-RVC 在測試集上的分類性能

與RVC 相比，雖然CS-RVC 獲得了更小的平均誤分類代價(jià)，為了考證它們在分類錯(cuò)誤率上的比較，圖5 給出了基于不同尺度訓(xùn)練集(每個(gè)訓(xùn)練集在原樣本集上隨機(jī)采樣得到)的CS—RVC 和RVC 的分類準(zhǔn)確率，TP—RVC、TN—RVC 和AC—RVC 分別表示基于RVC 的正例分類精度(正確分類正例數(shù)/正例數(shù))、反例分類精度和全局精度.TP—CS—RVC、TN—CS—RVC 與AC—CS—RVC 分別表示基于CS—RVC的正例、反例分類精度和全局精度。從中可見，AC—CS—RVC 低于AC—RVC，即CS—RVC 較于RVC 誤差率有所提高，但在誤分類代價(jià)較高的正例樣本上獲得較高的分類精度，在誤分類代價(jià)較低的反例樣本上獲得相對低的分類精度，符合了代價(jià)敏感挖掘的需求。

4 結(jié)束語

當(dāng)樣本的誤分類代價(jià)不相等時(shí)，傳統(tǒng)的基于分類精度的分類器不能滿足數(shù)據(jù)挖掘中最小化錯(cuò)誤分類代價(jià)的需求。通過將代價(jià)敏感的思想集成于相關(guān)向量分類器上，使用樣本加權(quán)方法使得誤分類代價(jià)較高的樣本具有較大的分類錯(cuò)誤代價(jià)，提出代價(jià)敏感相關(guān)向量機(jī)的設(shè)計(jì)方法。它具有相關(guān)向量機(jī)基于稀疏概率模型下強(qiáng)大的稀疏性及泛化能力和最小化平均誤分類代價(jià)2 個(gè)優(yōu)點(diǎn)。

二維人工數(shù)據(jù)實(shí)驗(yàn)和UCI 數(shù)據(jù)實(shí)驗(yàn)共同驗(yàn)證了CS-RVC 良好的稀疏性和分類性能，當(dāng)每類樣本的誤分類代價(jià)不相等時(shí)，和RVC 相比，雖然CS—RVC 損失了一部分的全局分類精度，但由于提高了誤分代價(jià)較高的樣本的正確分類率，使得分類超平面偏向于誤分代價(jià)較小的樣本簇，大大降低了平均誤分類代價(jià)。很好地實(shí)現(xiàn)了代價(jià)敏感的數(shù)據(jù)挖掘。

對于CS—RVC，雖然其取得了較低的平均誤分類代價(jià)，但損失的分類精度也比較高，設(shè)計(jì)一個(gè)兼顧分類精度與平均誤分類代價(jià)的算法是很有意義的進(jìn)一步研究工作。

［1］葉志飛，文益民，呂寶糧.不平衡分類問題研究綜述［J］.智能系統(tǒng)學(xué)報(bào)，2009，4(2):148-156.

［2］Habbema J D F，Hermans J，Van Der Burgt A T.Cases of doubt in allocation problems［J］.Biometrika，1974，61(2):313-324.

［3］Chawla N V，Bowyer K W，Hall L O，et al.SMOTE:Synthetic minority over-sampling technique［J］.Journal of Artificial Intelligence Research，2002，16:321-357.

［4］Domingos P Metacost.A general method for making classi-fiers cost-sensitive［C］// Proceedings of the fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM，1999:155-164.

［5］Breiman L.Bagging predictors［J］.MachineLearning，1996，24(2):123-140.

［6］Brefeld U，Geibel P，Wysotzki F.Support vector machines with example dependent costs［M］// Machine Learning:ECML 2003.Springer Berlin Heidelberg，2003:23-34.

［7］劉胥影，姜遠(yuǎn)，周志華.類別不平衡性對代價(jià)敏感學(xué)習(xí)的影響［C］// 人工智能學(xué)會(huì)第12 屆學(xué)術(shù)年會(huì)，中國人工智能進(jìn)展.2007:45-50.

［8］鄭恩輝，李平，宋執(zhí)環(huán).代價(jià)敏感支持向量機(jī)［J］.控制與決策，2006，21(4):473-476.

［9］Fumera G，Roli F.Cost-sensitive learning in support vector machines［C］// Workshop on Machine Learning，Methods and Applications，Held in the Context of the 8th Meeting of the Italian Association of Artificial Intelligence.2002.

［10］曹瑩，苗啟廣，劉家辰，等.具有Fisher 一致性的代價(jià)敏感Boosting 算法［J］.軟件學(xué)報(bào)，2013，24(11):2584-2596.

［11］阮曉宏，黃小猛，袁鼎榮，等.基于異構(gòu)代價(jià)敏感決策樹的分類器算法［J］.計(jì)算機(jī)科學(xué)，2013，40(11A):140-142.

［12］Bishop C M，Tipping M E.Variational relevance vector machines［C］// Proceedings of the Sixteenth Conference on Uncertainty in Artificial Intelligence.2000:46-53.

［13］Vapnik V N，Vapnik V.StatisticalLearning Theory［M］.New York:Wiley，1998.

［14］Li Y，Campbell C，Tipping M.Bayesian automatic relevance determination algorithms for classifying gene expression data［J］.Bioinformatics，2002，18(10):1332-1339.

［15］Mackay D.The evidence framework applied to classification networks［J］.Neural Computation，1992，4(5):720-736

［16］Thayananthan A.Relevance Vector Machine based Mixture of Experts［D］.Department of Engineering，University of Cambridge，2005.

［17］Platt J C.Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods［M］//Advances in Large Margin Classifiers.MIT Press，1999:61-74.

［18］Chen H，Tino P，Yao X.Probabilistic classification vector machines［J］.IEEE Transactions on Neural Networks，2009，20(6):901-914.

［19］Han J，Kamber M.Data Mining，Southeast Asia Edition:Concepts and Techniques［M］.Morgan Kaufmann，2006.

［20］周志華.普適機(jī)器學(xué)習(xí)［EB/OL］.http://wenku.baidu.com/link?url=ZhAh423i0RLQfcCUKaTPk0ojoV5765Zu-7O0vWxCkLlgjF8YmJGzmNKkoiP1hjhD6zeOmXvmaag0we-MRwHbbPYHBEAlVooCRLBfeL3EVhDa，2014-11-12.