叢偉杰, 何 磊

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

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

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

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

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

1.1 預(yù)備知識

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

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

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

(1)

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

(2)

式中αi和αj為相應(yīng)樣本點對應(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矩陣?？傻玫皆搯栴}的核形式為

(3)

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

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

(4)

如果一個未知類別的待分類樣本點滿足條件

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

(5)

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

1.2 MELM算法

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

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

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

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

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

1.3 TMELM算法

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

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

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

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

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

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

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

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

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

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

Q(e)=M2(e)。

樣本點到超橢球中心的距離為

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

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

(6)

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

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

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

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

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

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

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

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

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

3 實驗結(jié)果與分析

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

實驗過程中采用徑向基核函數(shù)為

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

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

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

表1 實驗數(shù)據(jù)特征

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

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

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

4 結(jié)論

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