一種基于廣義極值分布的非平衡數(shù)據(jù)分類算法

付俊杰 劉功申

(上海交通大學(xué)電子信息與電氣工程學(xué)院 上海 200240) (tianzhiyinyi@sjtu.edu.cn)

二分類是在不同領(lǐng)域的諸多應(yīng)用中的一項非常常見的任務(wù)，如欺詐檢測、疾病預(yù)測、風(fēng)險管理、文本分類等.在這些應(yīng)用中，其中一個類別的數(shù)據(jù)數(shù)量遠超出另一個類別，使得傳統(tǒng)的機器學(xué)習(xí)方法難以得到理想的結(jié)果[1].除了直接預(yù)測數(shù)據(jù)對應(yīng)的分類標(biāo)簽，許多應(yīng)用還可能關(guān)心這個預(yù)測的準(zhǔn)確性有多少，也就是想知道數(shù)據(jù)屬于某個分類的概率[2].相對直接得到分類標(biāo)簽，分類概率的預(yù)測往往能為人們的決策判斷提供額外的幫助.比如在醫(yī)療領(lǐng)域，醫(yī)生經(jīng)常會通過聲學(xué)成像得到的圖像數(shù)據(jù)來判斷病人是否患有某種疾病，比起直接診斷病人是否患病，能說出病人有百分之幾的可能性患病將更有說服力[3].

非平衡數(shù)據(jù)分類的常用方法包括過采樣/欠采樣方法[4]、代價敏感學(xué)習(xí)[5]和集成學(xué)習(xí)，比如boosting方法[6].其中，采樣方法比較簡單且適應(yīng)性較強，該方法的出發(fā)點簡單清晰，既然2個類別的數(shù)據(jù)量差異懸殊，就想辦法將它們拉近，然后用經(jīng)典的分類算法解決問題；代價敏感學(xué)習(xí)與直接考慮數(shù)據(jù)數(shù)量的采樣方法不同，它考慮的是數(shù)據(jù)分錯類別時的代價，使分類器能更看重少類數(shù)據(jù)；集成學(xué)習(xí)先將原數(shù)據(jù)集劃分為多個子集，然后分別對每個子集訓(xùn)練得到多個子分類器，最后將這些子分類器集成得到一個分類器，提高少類的分類準(zhǔn)確性.然而到現(xiàn)在為止，關(guān)注分類概率預(yù)測的研究還較少.為了解決這個問題，一個自然的選擇便是廣義線性模型[7].眾所周知，廣義線性模型具有模型簡單、魯棒性強、泛用性廣等優(yōu)點，在不同的鏈接函數(shù)下，廣義線性模型展現(xiàn)出了其良好的靈活性，更重要的是，該模型能直接給出分類的概率預(yù)測.然而，廣義線性模型中通常使用的鏈接函數(shù)對非平衡數(shù)據(jù)的適應(yīng)性不佳[8]，因為大多數(shù)鏈接函數(shù)的曲線形狀是對稱的，從而導(dǎo)致它們對不同的錯分給予了相同的代價.因此，有研究表明，用非對稱的鏈接函數(shù)將更有利于非平衡數(shù)據(jù)分類[9-10]，而其中一種非對稱鏈接函數(shù)便是廣義極值(generalized extreme value, GEV)分布的累積分布函數(shù).由于形狀參數(shù)ξ的存在， GEV鏈接函數(shù)能以不同的曲線斜率提供豐富多樣的曲線類型，可以適應(yīng)現(xiàn)實生活中的各種不同平衡度的數(shù)據(jù).

GEV分布廣泛應(yīng)用于金融、氣象、計算機視覺等領(lǐng)域.近年來，將GEV分布作為鏈接函數(shù)運用在線性模型中的做法受到了一定的關(guān)注：Wang等人[9]將GEV鏈接函數(shù)運用到B2B電子支付系統(tǒng)的二分類問題中，得到了很好的結(jié)果；Calabrese等人[10]則在信貸領(lǐng)域的稀有事件分類中運用了GEV分布，通過最大化似然概率得到了模型的解；Agarwal等人[11]更是根據(jù)GEV分布的形式求得了對應(yīng)的標(biāo)準(zhǔn)優(yōu)化函數(shù)，使整個問題化為凸優(yōu)化問題，在精確的分類概率預(yù)測問題上給出了一種解決方案.在這些研究中所用到的數(shù)據(jù)均是非平衡數(shù)據(jù)，而且均采用了GEV鏈接函數(shù)，這表明GEV分布在解決非平衡數(shù)據(jù)分類問題中具有一定潛力.

1 GEV線性回歸

1.1 廣義線性模型與GEV分布

令y∈{0,1}表示數(shù)據(jù)的分類標(biāo)簽，x=(1,α1,α2,…,αd)T∈d+1表示輸入的數(shù)據(jù)，給定x的條件下y的期望為

E[y|x]=P(y=1|x)=g(βTx)，

(1)

其中,β是權(quán)重參數(shù)，g的逆函數(shù)被稱為鏈接函數(shù).鏈接函數(shù)可以是任意的嚴(yán)格遞增函數(shù)，其定義域與值域符合g-1:[0,1]→，常用的有Logit鏈接、Probit鏈接和Cloglog鏈接等，前兩者是對稱鏈接函數(shù)，而Cloglog鏈接則是非對稱的.

GEV鏈接函數(shù)也是非對稱函數(shù)，與Cloglog不同的是，GEV鏈接函數(shù)具有可以調(diào)節(jié)非對稱程度的形狀參數(shù).當(dāng)均值為0、方差為1時，GEV分布的累積分布函數(shù)為

(2)

其中(·)+表示max(0,·);ξ是形狀參數(shù)，控制著函數(shù)曲線形狀以及定義域.GEV鏈接函數(shù)和其他的鏈接函數(shù)有2個主要區(qū)別：1)GEV鏈接函數(shù)具有可調(diào)的形狀參數(shù)，使得GEV鏈接函數(shù)可以通過改變曲線形狀來適應(yīng)不同的數(shù)據(jù)，尤其是具有不同非平衡程度的數(shù)據(jù)；2)GEV鏈接函數(shù)族中的大多數(shù)曲線都是非對稱的，圖1展示了在不同的形狀參數(shù)下GEV分布的累積分布函數(shù)(CDF)和概率密度函數(shù)曲線(PDF).曲線的非對稱性意味著GEV鏈接函數(shù)對不同的分類錯誤會給予不同的錯分代價，而這正是處理非平衡數(shù)據(jù)分類問題的一個有效策略.

Fig. 1 CDF and PDF of GEV distribution with different values of ξ圖1 不同ξ值的GEV分布的累積分布函數(shù)和概率密度函數(shù)

1.2 GEV線性回歸

在廣義線性模型框架下，為了求得權(quán)重參數(shù)β，通常會以最大化似然概率為目標(biāo).假設(shè)有n個獨立同分布的數(shù)據(jù)樣本，那么廣義線性模型的目標(biāo)優(yōu)化函數(shù)即是：

(3)

但是當(dāng)形狀參數(shù)ξ處在特定的區(qū)間時，上面的目標(biāo)優(yōu)化函數(shù)并非凸函數(shù)，也即無法求得全局最優(yōu)解.為了解決這個問題，Agarwal等人[11]利用組合損失函數(shù)的方法求得了GEV鏈接函數(shù)對應(yīng)的標(biāo)準(zhǔn)損失函數(shù)，使其配對形成凸函數(shù)優(yōu)化.該方法在小數(shù)據(jù)集上有較好的表現(xiàn)，但由于其每輪運算中都需要計算海森矩陣的逆矩陣，該方法在大數(shù)據(jù)集上有計算性能問題.

為了在保證凸函數(shù)優(yōu)化的基礎(chǔ)上進一步提升運算性能，本文運用了校準(zhǔn)損失函數(shù)作為目標(biāo)優(yōu)化函數(shù)，該目標(biāo)優(yōu)化函數(shù)能以更通用的形式支持許多鏈接函數(shù)，使其能組合成為凸函數(shù)[12].校準(zhǔn)損失函數(shù)為

l(β)=G(βTx)-yβTx，

(4)

其中，G為逆鏈接函數(shù)g的原函數(shù).在這里g必須是單調(diào)遞增的以保證原函數(shù)的存在以及該函數(shù)的凸性.而原函數(shù)G不必直接求出，因為在算法迭代中需要計算的是梯度和海森矩陣，它們分別是：

(5)

(6)

因為g是單調(diào)遞增的，也即g′(βTx)≥0，容易證明海森矩陣是半正定的，因此最小化上面的校準(zhǔn)損失函數(shù)可以轉(zhuǎn)換成凸優(yōu)化問題.

如果函數(shù)g滿足利普希茨連續(xù)性，那么迭代算法的效率就能通過近似計算海森矩陣而得到提升.利普希茨連續(xù)性意味著存在一個常數(shù)L≥0，使得對于所有u，v∈，以下關(guān)系成立：

|g(u)-g(v)|≤L|u-v|，

(7)

式(7)表明函數(shù)g的斜率有最大值L.如果這個斜率最大值L能計算出來，那么我們可以簡單地將其替換到g′(βTx)的位置，使得牛頓法的迭代過程簡化為

βnew=βold-(LxxT)-1·(g(βTx)-y)x|β=βold.

(8)

此處用斜率最大值L替換精確的梯度，相當(dāng)于在梯度更新方向正確的前提下提供了最小步長，而各維的實際更新步長仍受原始數(shù)據(jù)xxT的影響，保證了一定的參數(shù)更新效率.在替換過后，每輪的迭代計算中逆矩陣的運算與β無關(guān)，逆矩陣的計算可以放在循環(huán)開始前，這樣就能大大提高計算的效率.這種利普希茨優(yōu)化既保留了牛頓法中的原始數(shù)據(jù)二階信息結(jié)構(gòu)，還能像梯度下降法那樣有效率地更新，繼承了兩者的優(yōu)點.

對于GEV鏈接函數(shù)，其符合利普希茨連續(xù)性，斜率最大值L為

L=exp(-(1+ξ))(1+ξ)1+ξ，

(9)

其中，形狀參數(shù)ξ≥-1，否則g′(βTx)會趨向無窮，有意義的L值將不存在.雖然這限制了ξ的取值，但有研究表明，ξ的取值在[-0.5,0.5]之間就能提供足夠的曲線形狀來使GEV鏈接函數(shù)具有高度的靈活性[9].

完整的算法如算法1所示.為避免過擬合，算法1中添加了L-2正則項.形狀參數(shù)ξ是一個重要的參數(shù)，它直接影響模型對非平衡數(shù)據(jù)的擬合程度，所以關(guān)于它的選取方法將放到第2節(jié)單獨介紹.β的初始值可以隨機設(shè)為接近0的值，或通過第2節(jié)介紹的方法設(shè)置.

算法1. GEV線性回歸算法.

輸入：XT=(x0,x1,…,xn)，xi∈k，Y=(y1,y2,…,yn)T，yi∈{0,1}，使用概率模型選優(yōu)得到GEV形狀參數(shù)ξ∈[-1,+∞)，正則參數(shù)λ>0；

輸出：權(quán)重參數(shù)β.

初始化：

通過式(9)計算L.

步驟1. 計算近似海森矩陣的逆矩陣Σ-1=(L·XTXn+λI)-1，設(shè)置迭代下標(biāo)t=0；

步驟2. 重復(fù)步驟2.1～2.4直到β收斂：

步驟2.3.βt+1=βt-Σ-1·zt；

步驟2.4.t=t+1.

2 形狀參數(shù)求取

為了能更好地發(fā)揮GEV鏈接函數(shù)的性能，形狀參數(shù)的選取尤為重要.交叉驗證可以作為一種備選方法，然而當(dāng)需要選優(yōu)的參數(shù)較多時，交叉驗證將變得非常耗時，因此這里使用概率模型對形狀參數(shù)選優(yōu).

2.1 最大化后驗概率

模型主要有2個參數(shù)待求解：權(quán)重參數(shù)β和形狀參數(shù)ξ.觀察到實際中形狀參數(shù)合適值在0附近，所以假設(shè)其服從標(biāo)準(zhǔn)正態(tài)分布，即P(ξ)=N(ξ|0,1).而權(quán)重參數(shù)各維數(shù)值不應(yīng)過大，假設(shè)其各維度也服從標(biāo)準(zhǔn)正態(tài)分布，即P(βi)=N(βi|0,1)，并假設(shè)權(quán)重參數(shù)與形狀參數(shù)互相獨立.因此整個模型的后驗概率為

P(β,ξ|X,Y)∝P(Y|X,β,ξ)·P(β)·P(ξ)，

(10)

其中P(Y|X,β,ξ)是模型的似然概率，其單個yi在廣義線性模型框架下服從伯努利分布.對式(10)取對數(shù)后有：

(11)

Wang等人[9]在他們的研究中也用了類似的模型并通過最大化后驗概率(MAP)求得解，所不同的是他們還研究了其他的先驗概率分布，并且求解算法用的是馬爾可夫鏈蒙特卡羅方法.本文運用MAP方法是為了根據(jù)輸入數(shù)據(jù)自動選擇較優(yōu)的形狀參數(shù)ξ.因此，模型中對權(quán)重參數(shù)β的求解不是必須的，權(quán)重參數(shù)是利用本文提出的GEV線性回歸算法來求解的.考慮到這一步驟的主要目標(biāo)，本文對MAP的求解將采用迭代類算法，如牛頓法或梯度下降法，在每輪迭代中輪流更新權(quán)重參數(shù)和形狀參數(shù).MAP目標(biāo)優(yōu)化函數(shù)分別對β和ξ求一階偏導(dǎo)數(shù)有：

(12)

(13)

其中,ai=1+ξηi.有了一階偏導(dǎo)數(shù)后就可以采用梯度下降法求取MAP目標(biāo)優(yōu)化函數(shù)的最大值，或繼續(xù)計算各自的二階偏導(dǎo)數(shù)利用牛頓法更新參數(shù).得益于ξ的低維度，只需要很少的迭代次數(shù)就可以使形狀參數(shù)收斂到一個可接受的范圍.算法運行完后的副產(chǎn)物β參數(shù)可以看作是尋優(yōu)過程的“中途解”，將之用作GEV線性回歸算法的初始值，可以進一步減少讓β參數(shù)收斂所需的迭代次數(shù)，改進回歸算法的效率.

2.2 貝葉斯分析

在MAP概率模型中，目標(biāo)優(yōu)化函數(shù)是后驗概率，我們假設(shè)GEV線性回歸算法中的形狀參數(shù)ξ和權(quán)重參數(shù)β都服從于一個確定的標(biāo)準(zhǔn)正態(tài)分布，這有時會變得不合適.貝葉斯分析中，我們依舊假設(shè)形狀參數(shù)ξ和權(quán)重參數(shù)β都服從正態(tài)分布，但是正態(tài)分布的2個關(guān)鍵參數(shù)——均值和方差，可以是未知的.為了方便計算，假設(shè)P(ξ|μξ)=N(ξ|μξ,1),P(β|μβ)=N(β|μβ,I),其中μξ和μβ分別是ξ的均值和β的均值，I是單位矩陣.通過證據(jù)近似法最大化邊緣似然概率P(Y|μξ,μβ)可以得到ξ和β.在計算中，ξ和β可以看作是隱變量，通過EM算法迭代求解.M步驟中需要最大化的目標(biāo)函數(shù)Q為

Q(μξ,μβ|μξ,μβ)=

(14)

然而式(14)涉及對GEV分布的積分，直接計算很困難，所以這里通過Metropolis-Hastings采樣方法對此積分進行近似計算:

(15)

(16)

得到求和形式的函數(shù)Q后即可通過求導(dǎo)計算更新后的μξ和μβ,最優(yōu)形狀參數(shù)ξ直接取μξ的均值即可.像MAP方法一樣，副產(chǎn)物μβ可以用于GEV線性回歸算法的初始化中.

3 實 驗

本節(jié)實驗主要分為3個部分：1)通過人工數(shù)據(jù)集驗證形狀參數(shù)求取方法的準(zhǔn)確性；2)在真實數(shù)據(jù)集上橫向?qū)Ρ缺疚乃惴ê推渌€性回歸算法，在分類準(zhǔn)確性和概率預(yù)測準(zhǔn)確性上分別做出評價；3)對本文算法的運行效率進行實驗.

3.1 數(shù)據(jù)集與評價標(biāo)準(zhǔn)

人工數(shù)據(jù)集方面，數(shù)據(jù)維度為2維，采用互相獨立的標(biāo)準(zhǔn)正態(tài)分布隨機生成數(shù)據(jù)點xi，并固定權(quán)重參數(shù)β=(1,1)T，通過GEV逆鏈接函數(shù)生成分類概率值yi.本次實驗用的生成數(shù)據(jù)集使用了3個形狀參數(shù)值ξ，分別是-0.1，0.2，0.5；生成數(shù)據(jù)集的大小也有3種：100個、500個和1 000個，共9個生成數(shù)據(jù)集.真實數(shù)據(jù)集來源于Keel數(shù)據(jù)倉庫中的非平衡數(shù)據(jù)集[13].本次實驗根據(jù)數(shù)據(jù)所屬領(lǐng)域以及非平衡程度，從中挑出了17個真實數(shù)據(jù)集，它們均來自不同領(lǐng)域并具有不同的非平衡程度(IR)，IR等于負類數(shù)量正類數(shù)量.數(shù)據(jù)集名稱、數(shù)據(jù)量、特征維度數(shù)以及非平衡程度如表1所示.

在分類準(zhǔn)確性評價上，本文采用AUC指標(biāo)作為評價標(biāo)準(zhǔn).AUC是公認的對非平衡數(shù)據(jù)分類評價較為合適的指標(biāo)，AUC越大表示分類器的性能越好[14].為了評價算法的概率預(yù)測準(zhǔn)確性，采用Brier指標(biāo)和標(biāo)度損失來評價分類結(jié)果，它們的定義如下：

Table 1 Description of Datasets Used in Our Experiments表1 真實數(shù)據(jù)集概況

3.2 形狀參數(shù)求取實驗

在形狀參數(shù)尋優(yōu)實驗中，測試的方法是最大化后驗概率和貝葉斯分析.2種方法的初始ξ值均為0.1.圖2展示最大化后驗概率在9組生成數(shù)據(jù)集下ξ值隨迭代次數(shù)的變化圖像.

從圖2可以看到，9組生成數(shù)據(jù)集下的ξ值在最大化后驗概率方法下基本收斂，且ξ值變化的方向與其正確值一致，這說明最大化后驗概率方法對于形狀參數(shù)尋優(yōu)的有效性.最終搜尋到的ξ值如表2所示.

(a) N=100, real ξ=-0.1 (b) N=500, real ξ=-0.1 (c) N=1000, real ξ=-0.1 (d) N=100, real ξ=0.2 (e) N=500, real ξ=0.2 (f) N=1000, real ξ=0.2 (g) N=100, real ξ=0.5 (h) N=500, real ξ=0.5 (i) N=1000, real ξ=0.5

Fig. 2 Convergence of ξ under MAP method圖2 最大化后驗概率方法下ξ值的收斂情況

Table 2 Estimation of the Shape Parameter Under MAP Method

觀察表2可知，最大化后驗概率方法最終搜尋到的ξ值基本正確，但當(dāng)數(shù)據(jù)量為100時ξ值離正確值最遠，數(shù)據(jù)量為1 000時最近.這表明最大化后驗概率的參數(shù)尋優(yōu)性能隨數(shù)據(jù)量的增大而提高，數(shù)據(jù)量過少時ξ值有較大偏差，但仍在可以接受的范圍內(nèi).

接下來是貝葉斯分析對參數(shù)尋優(yōu)的實驗.實驗中，EM算法的迭代次數(shù)為10，每次迭代調(diào)用MH算法采樣的樣本數(shù)量為10 000～20 000均勻遞增.圖3為貝葉斯分析下對數(shù)似然概率值以及ξ值的收斂過程.

從圖3可以看到，采樣方法下的參數(shù)收斂過程并不平滑，細微的抖動情況非常多.ξ值基本朝正確的方向收斂，表示目標(biāo)函數(shù)優(yōu)化正確.貝葉斯分析方法最終搜尋到的ξ值如表3所示.

(a) Log Probability when N=100, real ξ=-0.1 (b) Log Probability when N=500, real ξ=-0.1 (c) Log Probability when N=1000, real ξ=-0.1

(d) ξ value when N=100, real ξ=-0.1(e) ξ value when N=500, real ξ=-0.1(f) ξ value when N=1000, real ξ=-0.1(g) Log Probability when N=100, real ξ=0.2(j) ξ value when N=100, real ξ=0.2(h) Log Probability when N=500, real ξ=0.2(k) ξ value when N=500, real ξ=0.2(i) Log Probability when N=1000, real ξ=0.2(l) ξ value when N=1000, real ξ=0.2(m) Log Probability when N=100, real ξ=0.5(p) ξ value when N=100, real ξ=0.5(n) Log Probability when N=500, real ξ=0.5(q) ξ value when N=500, real ξ=0.5(o) Log Probability when N=1000, real ξ=0.5(r) ξ value when N=1000, real ξ=0.5

Fig. 3 Convergence of ξ and Log Likelihood under Bayesian analysis圖3 貝葉斯分析方法下的ξ值和對數(shù)似然的收斂情況

Table 3 Estimation of the Shape Parameter Under Bayesian Analysis

從最終參數(shù)尋優(yōu)結(jié)果來看，數(shù)據(jù)量為100時貝葉斯分析有一個徹底錯誤的數(shù)據(jù)，其他結(jié)果基本正確.還可以發(fā)現(xiàn)數(shù)據(jù)量的多少對結(jié)果的影響沒有像最大化后驗概率方法那樣明顯，數(shù)據(jù)量為500和1 000的參數(shù)尋優(yōu)結(jié)果相差并不大.

3.3 對比實驗

本節(jié)實驗測試GEV線性回歸算法在真實數(shù)據(jù)集上的表現(xiàn)，包括分類準(zhǔn)確性和概率預(yù)測準(zhǔn)確性.

對比的其他算法為Logit回歸、Probit回歸和Cloglog回歸算法，還包括用SMOTE技術(shù)預(yù)處理數(shù)據(jù)的版本[16]，其中用SMOTE技術(shù)預(yù)處理后數(shù)據(jù)的非平衡度大約為1.數(shù)據(jù)集隨機劃分為70%的訓(xùn)練集和30%的測試集，實驗結(jié)果取10次分類的均值.本文的GEV線性回歸算法使用最大化后驗概率方法來選取最優(yōu)的形狀參數(shù)ξ，形狀參數(shù)尋優(yōu)的迭代次數(shù)和線性回歸的迭代次數(shù)分別為20次和100次.各算法在各數(shù)據(jù)集上的AUC指標(biāo)、Brier指標(biāo)和標(biāo)度損失分別如表4～6所示，其中最優(yōu)結(jié)果用粗體表示.所使用的統(tǒng)計顯著性檢驗方法為雙側(cè)Wilcoxon檢驗，結(jié)果后的符號“*”和“**”分別表示在置信水平為90%和95%時該結(jié)果與該行中的最好結(jié)果相比在統(tǒng)計上是顯著的.

在分類準(zhǔn)確性上，GEV線性回歸算法在大部分真實數(shù)據(jù)集上都能取得較好的分類結(jié)果，而由Logit和Probit鏈接函數(shù)這2種對稱函數(shù)構(gòu)成的回歸算法在SMOTE預(yù)處理技術(shù)的幫助下也能得到部分最優(yōu)結(jié)果，這從另一個角度說明它們的對稱性只適用于平衡數(shù)據(jù).在概率預(yù)測準(zhǔn)確性上，GEV線性回歸算法給出了大部分的最優(yōu)結(jié)果，表明其在分類的概率預(yù)測值上能提供更準(zhǔn)確的結(jié)果.其他3種回歸算法在SMOTE預(yù)處理下并沒有給出更好的結(jié)果，很多情況下反而更糟糕，這可能是因為SMOTE預(yù)處理下新生成的人為數(shù)據(jù)擾亂了概率值的準(zhǔn)確預(yù)測.

Table 4 Results of Classification Accuracy on the Datasets in Terms of AUC Score表4 以AUC指標(biāo)評價分類準(zhǔn)確度的結(jié)果

Notes： The superscripts “*” and “**” indicate statistical significance of the best method in that row with respect to other methods on the 90% and 95% confidence interval respectively.

Table 5 Results of Class Probability Estimation on the Datasets in Terms of Brier Score表5 以Brier指標(biāo)評價概率預(yù)測準(zhǔn)確度的結(jié)果

Continued (Table 5)

Notes： The superscripts “*” and “**” indicate statistical significance of the best method in that row with respect to other methods on the 90% and 95% confidence interval respectively.

Table 6 Results of Class Probability Estimation on the Datasets in Terms of Calibration Loss表6 以標(biāo)度損失評價概率預(yù)測準(zhǔn)確度的結(jié)果

Notes： The superscripts “*” and “**” indicate statistical significance of the best method in that row with respect to other methods on the 90% and 95% confidence interval respectively.

3.4 運行效率實驗

本節(jié)實驗內(nèi)容主要有2部分:1)觀察在3種最優(yōu)化方法(利普希茨優(yōu)化(Lipschitz)、梯度下降法(Gradient)、牛頓法(Hessian))下目標(biāo)優(yōu)化函數(shù)的收斂速度，也即其值隨迭代次數(shù)的增多而下降的趨勢;2)簡單測量3種最優(yōu)化方法的運行時間.其中梯度下降法還混合采用了二分線搜索方法加快步長參數(shù)的搜索.

1) 對3個最優(yōu)化方法的收斂速度的實驗.在作圖觀察時，由于校準(zhǔn)損失函數(shù)無法求值，所以用對數(shù)損失函數(shù)代替.這里選取了6個具有代表性的真實數(shù)據(jù)集，各取了前10輪迭代，結(jié)果如圖4所示:

Fig. 4 Comparison of convergence rate of three optimization methods圖4 3種最優(yōu)化方法的收斂速度比較

從圖4可以看出，隨著算法不斷迭代，3種最優(yōu)化方法都能使對數(shù)損失函數(shù)變小，其中梯度下降法減小的速度最慢，利普希茨優(yōu)化次之，牛頓法最快，這符合預(yù)期.另外還可以看到，利普希茨優(yōu)化的收斂速度其實與牛頓法非常接近，兩曲線幾乎重合.這得益于利普希茨優(yōu)化在保留了數(shù)據(jù)的二階結(jié)構(gòu)的同時用常數(shù)近似了海森矩陣，取得了與牛頓法差不多的效率.

2) 方法運行時間的實驗.3種最優(yōu)化方法在每個真實數(shù)據(jù)集上都運行了10遍，每種最優(yōu)化方法也都跑滿了100次迭代.最終結(jié)果如表7所示，用時最短的結(jié)果已加粗顯示.顯然，利普希茨優(yōu)化取得了所有真實數(shù)據(jù)集的最優(yōu)結(jié)果，這得益于其將海森矩陣的逆矩陣計算提前到了迭代之前，大大減少了每輪迭代的運算量.可以看到，本文使用的利普希茨優(yōu)化在算法運行效率上有顯著的提高.

Table 7 Comparison of Average Running Time of Three Optimization Methods

4 小 結(jié)

為了解決非平衡數(shù)據(jù)分類的概率預(yù)測問題，本文提出了GEV分布作為鏈接函數(shù)與校準(zhǔn)損失函數(shù)相結(jié)合的算法.具有形狀參數(shù)的GEV分布可以提供高度靈活的曲線形狀來適應(yīng)各種非平衡數(shù)據(jù)，并且目標(biāo)優(yōu)化函數(shù)是一個凸函數(shù)，算法確保了全局最優(yōu)解的存在.利用GEV逆鏈接函數(shù)的利普希茨連續(xù)性，本文提出的GEV線性回歸算法在運行效率上得到了顯著改善.此外，本文還提出了2個基于概率的模型來求取形狀參數(shù)，并利用人工數(shù)據(jù)集上的實驗證實了2個模型對形狀參數(shù)求取的有效性.

在真實數(shù)據(jù)集上的實驗顯示了本文算法有著較高的概率預(yù)測準(zhǔn)確性以及良好的分類性能.此外，在與其他優(yōu)化方法的比較中，本文所提優(yōu)化方法表現(xiàn)出很高的計算效率.未來的工作包括繼續(xù)研究更健壯的形狀參數(shù)求取方法以及對高維數(shù)據(jù)的實驗.