改進的直推式一類分類馬氏橢球學習機

叢偉杰, 何 磊

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

一類分類馬氏橢球學習機的目標是將樣本數據中的目標類和非目標類區分開[1-2]，是數據挖掘[3-4]中的一個重要問題。一類分類馬氏橢球學習機在圖像識別[5]，遙感成像[6]，工程故障檢測[7-8]等技術領域有著廣泛實際應用。

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

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

1 馬氏橢球學習機算法概述

1.1 預備知識

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

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

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

(1)

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

(2)

式中αi和αj為相應樣本點對應的拉格朗日乘子。設

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)是一個二次凸優化問題。

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

(4)

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

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

(5)

則這個樣本點就被認為是屬于目標集所在的類，否則就會被認為是非目標集所在的類。

1.2 MELM算法

馬氏橢球學習機[10]是處理判別函數一種常用算法，具體步驟可描述如下。

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

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

3)當所有待分類樣本點判別完成后，輸出相應結果，MELM算法結束。

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

1.3 TMELM算法

直推式馬氏橢球學習機[12]是為了提高馬氏橢球學習機的分類準確率的一種改進算法，算法具體步驟如下。

1)給定參數C1和C2，初始迭代p=0時，對已知類別樣本點進行訓練學習，獲得最初的超橢球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)，對其余未知類別的待分類樣本點進行判斷，直到將所有未知類別的待分類樣本點判別完成。如果未判別完成，則跳轉到步驟2；

4)當所有待分類樣本點判別完成后，輸出相應結果，算法TMELM結束。

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

2 改進的直推式馬氏橢球學習機

為了改善TMELM算法在處理較大規模數據集時耗時較長的問題，提出一種改進的直推式馬氏橢球學習機算法(ITMELM)。

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

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

Q(e)=M2(e)。

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

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

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

(6)

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

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

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

1)給定參數C1和C2，當迭代次數p=0時對已知類別的樣本點使用樣本協方差初始化策略進行訓練，并獲得超橢球E0(a0,R0)，利用式(5)對未知類別的待分類樣本點進行分類；

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

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

4)當所有待分類樣本點判別結束后，輸出相應結果，算法ITMELM結束。

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

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

3 實驗結果與分析

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

實驗過程中采用徑向基核函數為

并通過十倍交叉驗證的方法選擇核參數σ及參數C1，C2，以期選取最優結果的平均值。

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

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

表1 實驗數據特征

表2 3種算法的準確率和運行時間

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

表3 三種算法在較大規模數據下的準確率和運行時間結果

4 結論

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