改進(jìn)的直推式一類分類馬氏橢球?qū)W習(xí)機(jī)

叢偉杰, 何 磊

(西安郵電大學(xué) 理學(xué)院， 陜西 西安 710121)

一類分類馬氏橢球?qū)W習(xí)機(jī)的目標(biāo)是將樣本數(shù)據(jù)中的目標(biāo)類和非目標(biāo)類區(qū)分開[1-2]，是數(shù)據(jù)挖掘[3-4]中的一個(gè)重要問(wèn)題。一類分類馬氏橢球?qū)W習(xí)機(jī)在圖像識(shí)別[5]，遙感成像[6]，工程故障檢測(cè)[7-8]等技術(shù)領(lǐng)域有著廣泛實(shí)際應(yīng)用。

解決一類分類問(wèn)題最常用的方法是基于支持向量域描述[9](Support Vector Domain Description，SVDD)的馬氏橢球?qū)W習(xí)機(jī)[10](Mahalanobis Ellipsoidal Learning Machine，MELM)，其核心思想是用馬氏距離代替SVDD中的歐氏距離，這樣就可以考慮到樣本點(diǎn)的分布信息，從而得到更加緊致的超橢球邊界，以替代原來(lái)的超球邊界，使樣本分類的準(zhǔn)確率得到提高。但是，在訓(xùn)練樣本點(diǎn)較少情況下，這種方法的分類準(zhǔn)確率并不高。其主要原因MELM通過(guò)訓(xùn)練樣本所構(gòu)造的判別函數(shù)，必須對(duì)所有待分類樣本點(diǎn)進(jìn)行判別。當(dāng)訓(xùn)練樣本點(diǎn)較少時(shí)，所構(gòu)造的判別函數(shù)分類性能較差。為此，將支持向量機(jī)中的直推模式[11]學(xué)習(xí)方法引入到MELM中，從而得到直推式馬氏橢球?qū)W習(xí)機(jī)[12](Transductive Mahalanobis Ellipsoidal Learning Machine，TMELM)。 該方法在訓(xùn)練過(guò)程中，不斷將待分類樣本點(diǎn)通過(guò)逐漸學(xué)習(xí)方式加入到訓(xùn)練集中，使構(gòu)造函數(shù)不斷得到優(yōu)化，即使在訓(xùn)練樣本點(diǎn)較少情況下，分類準(zhǔn)確率明顯提高。但是，TMELM方法在迭代時(shí)，選取加入到新訓(xùn)練集中的待分類樣本點(diǎn)，遍及當(dāng)前所形成的超橢球內(nèi)部的全部待分類樣本點(diǎn)。這樣就會(huì)使得在重新訓(xùn)練時(shí)，因數(shù)據(jù)集規(guī)模過(guò)大而造成運(yùn)行時(shí)間較長(zhǎng)、系統(tǒng)效率不高的問(wèn)題，尤其是在處理較大規(guī)模數(shù)據(jù)集時(shí)，該問(wèn)題就變得更加明顯。

為了在保證較高準(zhǔn)確率的前提下，提高運(yùn)算效率，本文采用有效處理最小閉包球問(wèn)題[13]的割平面法思想和基于協(xié)方差的初始化策略，提出了一種改進(jìn)的直推式馬氏橢球?qū)W習(xí)機(jī)(Improved Transductive Mahalanobis Ellipsoidal Learning Machine，ITMELM)。ITMELM在迭代過(guò)程中，僅僅選取距離當(dāng)前超橢球中心最遠(yuǎn)的待分類樣本點(diǎn)，加入到新的訓(xùn)練集中進(jìn)行重新訓(xùn)練，以提高計(jì)算效率。在ITMELM中，使用基于樣本協(xié)方差矩陣構(gòu)造的初始化策略[14]來(lái)提高較大規(guī)模數(shù)據(jù)集上最小體積超橢球的計(jì)算效率。通過(guò)對(duì)比實(shí)驗(yàn)驗(yàn)證ITMELM的分類準(zhǔn)確率和計(jì)算效率。

1 馬氏橢球?qū)W習(xí)機(jī)算法概述

1.1 預(yù)備知識(shí)

設(shè)X表示n×M樣本矩陣，包含M個(gè)樣本xi∈n(i=1,2,…M)，在SVDD中使用加入樣本信息的馬氏距離代替歐氏距離，得到可以包含近乎全部訓(xùn)練樣本點(diǎn)的超橢球[10]

E(a,R)={x∈n:
(x-a)TΣ-1(x-a)≤R2}，

其中，a是得到的超橢球的球心，R為超橢球的半徑。離群點(diǎn)是超橢球外側(cè)的點(diǎn)，在上述過(guò)程中需要求解下面的規(guī)劃問(wèn)題

(1)

式中，ξi≥0是對(duì)應(yīng)允許存在在超橢球外側(cè)樣本點(diǎn)的松弛變量，C是用來(lái)均衡在橢球內(nèi)外側(cè)的樣本點(diǎn)的數(shù)量和得到超橢球的規(guī)模的參數(shù)，Σ是樣本點(diǎn)的協(xié)方差矩陣。從而可以獲得式(1)的Lagrangian對(duì)偶問(wèn)題

(2)

式中αi和αj為相應(yīng)樣本點(diǎn)對(duì)應(yīng)的拉格朗日乘子。設(shè)

k(xi,xj)=φ(xi)Tφ(xj)，

φ(xi)與φ(xj)分別為xi與xj在空間中的映射，利用中心化核矩陣[10]

KC=QTΩQ，

其中

Q=[(1/M)(I-(1/M)E)]1/2，
Ω=QKQ，K=k(X,XT)，

I為M×M單位矩陣，E是M×M全1矩陣?？傻玫皆搯?wèn)題的核形式為

(3)

顯然，式(3)是一個(gè)二次凸優(yōu)化問(wèn)題。

下面，將利用式(3)構(gòu)造對(duì)未知類別的待分類樣本的判別函數(shù)。特征空間中的樣本點(diǎn)到球心a的馬氏距離的平方為

(4)

如果一個(gè)未知類別的待分類樣本點(diǎn)滿足條件

d2(φ(x),a)≤R2,

(5)

則這個(gè)樣本點(diǎn)就被認(rèn)為是屬于目標(biāo)集所在的類，否則就會(huì)被認(rèn)為是非目標(biāo)集所在的類。

1.2 MELM算法

馬氏橢球?qū)W習(xí)機(jī)[10]是處理判別函數(shù)一種常用算法，具體步驟可描述如下。

1)給定參數(shù)C1和C2，通過(guò)對(duì)已知類別的樣本點(diǎn)進(jìn)行訓(xùn)練學(xué)習(xí)獲得最初的超橢球E0(a0,R0)，這個(gè)過(guò)程即是求解式(3)的問(wèn)題過(guò)程；

2)利用所得到的超橢球，并利用式(5)對(duì)未知類別的樣本點(diǎn)進(jìn)行分類；

3)當(dāng)所有待分類樣本點(diǎn)判別完成后，輸出相應(yīng)結(jié)果，MELM算法結(jié)束。

可以看出，MELM算法是通過(guò)對(duì)已知類別的訓(xùn)練樣本點(diǎn)進(jìn)行初始化，獲得一個(gè)最初的超橢球并結(jié)合離群點(diǎn)的判定條件，然后，對(duì)未知類別的待分類樣本點(diǎn)進(jìn)行判定。

1.3 TMELM算法

直推式馬氏橢球?qū)W習(xí)機(jī)[12]是為了提高馬氏橢球?qū)W習(xí)機(jī)的分類準(zhǔn)確率的一種改進(jìn)算法，算法具體步驟如下。

1)給定參數(shù)C1和C2，初始迭代p=0時(shí)，對(duì)已知類別樣本點(diǎn)進(jìn)行訓(xùn)練學(xué)習(xí)，獲得最初的超橢球E0(a0,R0)，利用式(5)對(duì)未知類別的樣本點(diǎn)進(jìn)行初次分類；

Einterior(a,R)={x∈n:
(x-a)TΣ-1(x-a)≤R2+ξi,ξi=0};

3)使用步驟2中所得到的超橢球Ep+1(ap+1,Rp+1)，對(duì)其余未知類別的待分類樣本點(diǎn)進(jìn)行判斷，直到將所有未知類別的待分類樣本點(diǎn)判別完成。如果未判別完成，則跳轉(zhuǎn)到步驟2；

4)當(dāng)所有待分類樣本點(diǎn)判別完成后，輸出相應(yīng)結(jié)果，算法TMELM結(jié)束。

算法TMELM基于MELM算法并引入支持向量機(jī)中直推式的思想[12]進(jìn)行改進(jìn)，即通過(guò)已知類別的訓(xùn)練樣本點(diǎn)獲得一個(gè)最初的超橢球，利用目標(biāo)點(diǎn)的判定條件對(duì)未知類別的樣本點(diǎn)進(jìn)行初次判定，將符合條件的樣本點(diǎn)加入到原有的訓(xùn)練集中，同原有的訓(xùn)練集一起組成一個(gè)新的訓(xùn)練集，并對(duì)其進(jìn)行重新訓(xùn)練，從而可以得到一個(gè)相對(duì)上一次迭代性能更加優(yōu)化的超橢球。不斷迭代上述過(guò)程，直到所有未知類別的待分類樣本點(diǎn)全部判別為止。但其在處理較大規(guī)模數(shù)據(jù)集時(shí)，就會(huì)出現(xiàn)算法耗時(shí)較長(zhǎng)的問(wèn)題。

2 改進(jìn)的直推式馬氏橢球?qū)W習(xí)機(jī)

為了改善TMELM算法在處理較大規(guī)模數(shù)據(jù)集時(shí)耗時(shí)較長(zhǎng)的問(wèn)題，提出一種改進(jìn)的直推式馬氏橢球?qū)W習(xí)機(jī)算法(ITMELM)。

首先，對(duì)已知類別的訓(xùn)練樣本點(diǎn)進(jìn)行初始化，并在初始化過(guò)程中引入樣本協(xié)方差初始化策略思想[14-15]。把每次迭代后組成的已知類別訓(xùn)練樣本作為下一次需要進(jìn)行初始化的樣本點(diǎn)，令

其中X∈n×M表示為一個(gè)列向量矩陣，該矩陣是由已知類別的訓(xùn)練樣本中的樣本點(diǎn)組成，e∈M是分量均為1的列向量。矩陣Q(e)可表示為[15]

Q(e)=M2(e)。

樣本點(diǎn)到超橢球中心的距離為

類似于文獻(xiàn)[14]，在所有初始化已知類別的訓(xùn)練樣本點(diǎn)中，選擇距離當(dāng)前中心最遠(yuǎn)的前2n個(gè)對(duì)應(yīng)的樣本點(diǎn)，記為A0={xi1,xi2,…,xi2n}。這時(shí)，得出初始的可行解為u0∈M，將u0輸出，其中可行解u0的分量為或?A0。

考慮到需要對(duì)待分類樣本點(diǎn)能夠作出較好的判別分類，并且得到一個(gè)更精確的類描述。因此，需要求解以下的優(yōu)化問(wèn)題[10]

(6)

式中x1,x2,…,xm∈n為一組已知的訓(xùn)練樣本點(diǎn)，y1,y2,…,yk∈n為待分類樣本點(diǎn)，C1和C2是給定的參數(shù)，分別表示已知和未知類別的訓(xùn)練樣本點(diǎn)的影響因子。為保證所得到參數(shù)的可靠性，通常通過(guò)十倍交叉校驗(yàn)的方法獲得。

改進(jìn)算法的訓(xùn)練過(guò)程也是求解式(6)優(yōu)化問(wèn)題的過(guò)程，而對(duì)未知類別待分類樣本點(diǎn)的判別則要求其要滿足式(5)的條件。

用類似于直推式支持向量機(jī)啟發(fā)式算法[16]的思想，ITMELM算法的具體步驟如下。

1)給定參數(shù)C1和C2，當(dāng)?shù)螖?shù)p=0時(shí)對(duì)已知類別的樣本點(diǎn)使用樣本協(xié)方差初始化策略進(jìn)行訓(xùn)練，并獲得超橢球E0(a0,R0)，利用式(5)對(duì)未知類別的待分類樣本點(diǎn)進(jìn)行分類；

2)如果第p(p≥1)次迭代對(duì)應(yīng)的樣本點(diǎn)yj滿足yj∈Einterior(ap,Rp)，則計(jì)算所有符合條件的yj及當(dāng)前迭代所形成的超橢球中心點(diǎn)的距離，選取距離最大的點(diǎn)(一個(gè)或多個(gè)點(diǎn))，并將這些點(diǎn)加入到訓(xùn)練樣本中，和原有的訓(xùn)練樣本組成新的訓(xùn)練集，重新訓(xùn)練后得到下一次迭代的超橢球Ep+1(ap+1,Rp+1)；

3)使用步驟2中得到的超橢球Ep+1(ap+1,Rp+1)對(duì)其余未知類別的待分類樣本點(diǎn)進(jìn)行判斷，直到將所有未知類別的待分類樣本點(diǎn)判別完成。如果未判別完成，則跳轉(zhuǎn)到步驟2；

4)當(dāng)所有待分類樣本點(diǎn)判別結(jié)束后，輸出相應(yīng)結(jié)果，算法ITMELM結(jié)束。

ITMELM算法首先使用樣本協(xié)方差的初始化策略對(duì)所有的已知類別的訓(xùn)練樣本點(diǎn)進(jìn)行初始化，進(jìn)而會(huì)得到一個(gè)初始的超橢球，其次結(jié)合目標(biāo)點(diǎn)的判定條件對(duì)未知類別的待分類樣本點(diǎn)進(jìn)行初次判定，最后在所有符合條件的樣本點(diǎn)當(dāng)中選取距離當(dāng)前超橢球中心點(diǎn)最遠(yuǎn)的樣本點(diǎn)，并將它們加入到原有的目標(biāo)點(diǎn)集當(dāng)中形成新的訓(xùn)練樣本點(diǎn)集，通過(guò)重新訓(xùn)練得到一個(gè)新的超橢球，再使用它去判定剩余的待分類樣本點(diǎn)。

其中使用樣本協(xié)方差初始化策略可以得到更好的初始超橢球，而在下一次迭代過(guò)程當(dāng)中使用這種策略得到的超橢球的判別準(zhǔn)確率也會(huì)稍好一些。在加入目標(biāo)點(diǎn)的過(guò)程中通過(guò)使用處理最小閉包球問(wèn)題的割平面法思想選擇的樣本點(diǎn)更有意義，因?yàn)樵谛纬沙瑱E球的過(guò)程中，越靠近邊界的點(diǎn)與其他部分的點(diǎn)相比較，它們可以更快地形成滿足條件的超橢球，減少整個(gè)算法的迭代次數(shù)，進(jìn)而縮短了需要的運(yùn)行時(shí)間。這樣將待分類樣本的信息通過(guò)逐漸學(xué)習(xí)的方式加入到改進(jìn)算法中的訓(xùn)練樣本集合中，使判別模型每通過(guò)一次訓(xùn)練學(xué)習(xí)都會(huì)提高其原有模型的判別準(zhǔn)確率，經(jīng)過(guò)多次的不斷學(xué)習(xí)后可以達(dá)到一個(gè)比較滿意的結(jié)果。因此ITMELM算法與MELM算法和TMELM算法這兩種算法相比，可以在確保較高分類準(zhǔn)確率的前提下，有效地減少算法運(yùn)行時(shí)間，從而更好地提高處理較大規(guī)模數(shù)據(jù)集的計(jì)算效率。

3 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證本文ITMELM算法的效果，在實(shí)際數(shù)據(jù)上，將本文ITMELM算法與MELM算法[10]和TMELM算法[12]分別進(jìn)行對(duì)比試驗(yàn)。實(shí)驗(yàn)運(yùn)行的環(huán)境為MatlabR2014a。實(shí)驗(yàn)過(guò)程中使用的實(shí)際數(shù)據(jù)集是從University of California Irvine(UCI)機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)[17]中進(jìn)行選取的。實(shí)驗(yàn)數(shù)據(jù)不僅選取了文獻(xiàn)[12]中的5組數(shù)據(jù)進(jìn)行對(duì)比試驗(yàn)，還選取了5組較大規(guī)模的數(shù)據(jù)進(jìn)行驗(yàn)證ITMELM算法相較于TMLEM算法的計(jì)算效率。在進(jìn)行實(shí)驗(yàn)前，對(duì)所選取的數(shù)據(jù)集先需要做一些簡(jiǎn)單處理，如去掉了少量不完整數(shù)據(jù)，在數(shù)據(jù)內(nèi)部調(diào)整數(shù)據(jù)位置信息等；對(duì)于多種類別的數(shù)據(jù)集，則選取其中一種類別為所要學(xué)習(xí)的類別，并選取該數(shù)據(jù)集中約22%的數(shù)據(jù)作為初始訓(xùn)練數(shù)據(jù)，剩余數(shù)據(jù)作為待分類數(shù)據(jù)，其目的是為了保證在訓(xùn)練樣本中樣本點(diǎn)比較少，而待分類樣本點(diǎn)比較多的情況下進(jìn)行對(duì)比試驗(yàn)。

實(shí)驗(yàn)過(guò)程中采用徑向基核函數(shù)為

并通過(guò)十倍交叉驗(yàn)證的方法選擇核參數(shù)σ及參數(shù)C1，C2，以期選取最優(yōu)結(jié)果的平均值。

表1為實(shí)驗(yàn)所選數(shù)據(jù)的特征描述。表2分別給出了三種算法在相同數(shù)據(jù)集上執(zhí)行所得準(zhǔn)確率和運(yùn)行時(shí)間的實(shí)驗(yàn)結(jié)果。從表2中可以看出，在已知類別的訓(xùn)練樣本點(diǎn)較少而未知類別的待分類樣本較多的情況下，MELM算法的判別準(zhǔn)確率比TMELM算法和ITMELM算法均明顯較差。這是因?yàn)镸ELM算法在通過(guò)使用已知類別的訓(xùn)練樣本得到初始超橢球后，然后對(duì)未知待分類樣本進(jìn)行判別，因初始訓(xùn)練樣本數(shù)量較少，故得到的判別類型準(zhǔn)確率自然不高。而對(duì)于TMELM算法和ITMELM算法，均使用了增量學(xué)習(xí)的策略，在得到初始超橢球后，再對(duì)待分類樣本點(diǎn)判別時(shí)，不斷將待分類樣本點(diǎn)信息加入到學(xué)習(xí)機(jī)中進(jìn)行重新訓(xùn)練，從而逐漸改善了模型的判別準(zhǔn)確率。對(duì)比ITMELM算法和TMELM算法的分類準(zhǔn)確率結(jié)果也可以看出，ITMELM算法可以達(dá)到與TMELM算法的相當(dāng)高的分類準(zhǔn)確率。這是因?yàn)镮TMELM算法在初始化時(shí)加入樣本協(xié)方差初始化策略，將得到一個(gè)相較于TMELM算法更優(yōu)的初始超橢球，所以，其分類準(zhǔn)確率相對(duì)于TMELM算法在部分?jǐn)?shù)據(jù)上會(huì)略有提高。

另外，從表2中還可以發(fā)現(xiàn)，MELM算法相對(duì)其他兩種算法的運(yùn)行時(shí)間最少，但是它的分類準(zhǔn)確率較低，從綜合性能角度來(lái)看，MELM算法相對(duì)較差。對(duì)比ITMELM算法和TMELM算法的運(yùn)行時(shí)間結(jié)果很容易發(fā)現(xiàn)，ITMELM算法的運(yùn)行時(shí)間會(huì)較小，且ITMELM算法的運(yùn)行時(shí)間比TMELM算法至少可以減少24.9% 以上。其原因是在增量學(xué)習(xí)過(guò)程中，加入了樣本點(diǎn)構(gòu)成新的訓(xùn)練集時(shí)，TMELM算法是將每次迭代中的全部的樣本點(diǎn)均加入到新的樣本集合中，而ITMELM算法每次均選取距離超橢球中心點(diǎn)距離最遠(yuǎn)的點(diǎn)加入到訓(xùn)練樣本中，由于這些樣本點(diǎn)相對(duì)于其他樣本點(diǎn)來(lái)說(shuō)，可以更快地形成超橢球，從而避免了在迭代過(guò)程中重復(fù)尋找超橢球的過(guò)程，同時(shí)，這樣的點(diǎn)作為支持向量點(diǎn)，可以更加快速地形成預(yù)期的超橢球，減少了加入全部點(diǎn)時(shí)形成超橢球的迭代次數(shù)，進(jìn)而使整體運(yùn)行時(shí)間縮短。

表1 實(shí)驗(yàn)數(shù)據(jù)特征

表2 3種算法的準(zhǔn)確率和運(yùn)行時(shí)間

在較大規(guī)模數(shù)據(jù)集下,3種算法的準(zhǔn)確率和運(yùn)行時(shí)間如表3所示。從表中可以看出，在數(shù)據(jù)規(guī)模較大的情況下，ITMELM算法的分類準(zhǔn)確率可以與TMELM算法相當(dāng)，但是，ITMELM算法運(yùn)行時(shí)間進(jìn)一步降低，ITMELM算法的運(yùn)行時(shí)間比TMELM算法縮短了約2～5倍。主要原因在于采用了樣本協(xié)方差初始化策略，對(duì)于規(guī)模比較大的數(shù)據(jù)集，相對(duì)于較小規(guī)模數(shù)據(jù)集情形，運(yùn)算的迭代次數(shù)減少地更加明顯。因此改進(jìn)算法在處理大規(guī)模數(shù)據(jù)時(shí)更具有優(yōu)勢(shì)。

表3 三種算法在較大規(guī)模數(shù)據(jù)下的準(zhǔn)確率和運(yùn)行時(shí)間結(jié)果

4 結(jié)論

針對(duì)在訓(xùn)練樣本點(diǎn)較少的情況下，馬氏距離進(jìn)行直推式一類分類橢球?qū)W習(xí)機(jī)處理較大規(guī)模數(shù)據(jù)集時(shí)間較長(zhǎng)的問(wèn)題，提出了一種改進(jìn)的直推式馬氏橢球?qū)W習(xí)機(jī)算法(ITMELM)。一方面，ITMELM有效地使用樣本協(xié)方差的初始化策略進(jìn)行初始化過(guò)程；另一方面，采用將離超橢球中心點(diǎn)最遠(yuǎn)的待分類樣本點(diǎn)加入到訓(xùn)練樣本點(diǎn)中的方式，并循序漸進(jìn)的作出判別分類，具有較強(qiáng)的自我學(xué)習(xí)能力。實(shí)驗(yàn)結(jié)果和分析表明，在保證較高分類準(zhǔn)確率的前提下，相對(duì)于MELM算法和TMELM算法， 本文所提ITMELM算法能有效地減少運(yùn)行時(shí)間。特別是在較大規(guī)模的數(shù)據(jù)且訓(xùn)練樣本較少的情況下，將能保證較高分類準(zhǔn)確率同時(shí)，還能極大地縮短處理數(shù)據(jù)的運(yùn)行時(shí)間。因此，本文提出的ITMELM算法，在處理訓(xùn)練樣本比較少、待分類樣本較多的規(guī)模較大數(shù)據(jù)時(shí)，是一個(gè)可供選擇的有效算法。