局部幾何保持的Laplacian代價敏感支持向量機

周國華,宋 潔,殷新春

(1. 常州輕工職業技術學院 信息工程系,江蘇 常州 213164；2. 揚州大學 信息工程學院,江蘇 揚州 225127)

0 引言

在現實世界中，人們采集的真實數據往往是不平衡的，比如癌癥疾病診斷實例中，健康人的樣本數目往往要遠多于患病者的樣本數目；詐騙短信分類中，正常短信的數目也遠多于詐騙短信的數目。解決此類問題一般主要有三種方法： 一種方法是重采樣來調整不同類別樣本的比例，如在支持向量機技術中常用的過采樣(over-sampling)和欠采樣(under-sampling)方法[1-3]，但是這類方法的缺點是會改變樣本的原始分布結構, 采取精確復制少數類樣本的策略容易造成分類器的過擬合，而采取抽樣多類樣本的策略容易丟失部分樣本信息。第二種方法是調整分類面的偏移[4]，讓分類面盡可能地遠離少數類，但是這種方法也易產生過擬合的問題。第三種方法是針對數據的不平衡性選取不同的代價參數[5]。這是因為樣本的不平衡分類問題一般常涉及到代價敏感學習問題[6-8]，即錯分代價。錯分代價包括類依賴的代價和樣本依賴的代價，其中類代價可以表示為錯誤分類兩類樣本的代價不同，樣本的不平衡分類常可表示為類別的代價敏感問題。如Lo等[9]在2011年通過考慮噪聲標注問題提出了用于自動音樂標注的代價敏感分類算法；萬建武等[10]將錯分代價融入局部保持降維的目標函數中, 提出了一種錯分代價最小化的局部保持降維方法，并采用了加權策略, 將算法應用到不平衡人臉數據集上；Liu等[11]基于滿足基本運算的不變性和各行間元素的大小差異性，并借鑒領域專家的先驗知識，提出了容易定義成對代價的概念，運用于不平衡數據的分類。

但是代價敏感學習方法通常為有監督學習方法，其必須獲取足夠的訓練數據。在實際應用中，由于標記樣本的標簽這一工作費時費力，人們更容易得到大量的無標記數據。因此在面對大量未知標簽信息的不平衡數據分類問題中，文獻[12]在代價敏感學習框架的基礎上使用半監督學習來處理不平衡數據分類問題，將未標記樣本納入到分類器的求解過程中。文獻[13]將半監督學習和代價敏感結合應用在microRNA的分類問題中。但是這兩種方法均沒有考慮數據的局部幾何分布信息對分類性能的影響，其分類精度還有待提高。

鑒于上述分析，本文提出了一種新的局部幾何保持的Laplacian代價敏感支持向量機(locality preserving cost sensitive laplacian support vector machine, LPCS-LapSVM)。該分類器為一種半監督分類方法，將針對不平衡數據的不同代價和樣本的局部幾何流形信息同時融入Laplacian支持向量機的架構中，從而更大程度地提高半監督學習中不平衡問題下分類器的分類精度。

1 相關工作

1.1 代價敏感支持向量機

(1)

其中ci為第i個樣本的誤分代價參數，其值可按照上段的描述設置。ciεi為第i個樣本錯分造成的損失，參數C則用于控制損失與模型復雜度的關系。CS-SVM是一種有監督學習模型，由于可以對不同類別的樣本設置不同的代價參數，對比傳統的支持向量機(support vector machine, SVM)，更能獲得盡可能小的總體代價，從而可以在不平衡的數據分類問題中得到更加精確的分類效果。但CS-SVM的不足是無法利用無標記信息來訓練模型，無法應用到半監督學習中。

1.2 Laplacian支持向量機

(2)

(3)

(4)

ξi>0,i=1,2,…,l

LapSVM的解的形式為式(5)。

f(x)=∑l+ui=1αiK(x,xi)

(5)

LapSVM作為一種成功的半監督學習方法，依然存在不足之處，其主要表現在： ①LapSVM認為如果兩個數據的內在幾何空間距離較近，則判定它們屬于同一類，但在兩類樣本的邊緣地帶這種假設往往并不成立； ②LapSVM利用了數據的整體流形信息而忽略了已知樣本的類別標簽信息，其結果導致忽略了不同類別內部樣本的局部分布信息。

2 局部幾何保持的Laplacian代價敏感支持向量機

為了能更精確地處理半監督場景下不平衡數據的分類問題，本文在LapSVM模型的基礎上提出了一種新的局部幾何保持的Laplacian代價敏感支持向量機LPCS-LapSVM。LPCS-LapSVM首先使用測地線距離構造一個新的局部幾何保持連接圖，提出類內局部保持散度矩陣，然后將基類內局部保持散度信息融入基于LapSVM的代價敏感學習框架中，得到一種新的Laplacian代價敏感支持向量機。因為LPCS-LapSVM中融入了類內局部保持散度信息，在解決半監督場景下不平衡分類問題時，能挖掘樣本的局部幾何結構特征和整體流形信息，從而提高半監督分類器的分類性能。LPCS-LapSVM算法構造原理如圖1所示。

圖1 局部幾何保持的Laplacian代價 敏感支持向量機構造原理

2.1 類內局部保持散度矩陣

現有算法在構造連接圖時，多采用歐氏距離，而本文方法為了利用數據在高維核空間下的局部內在幾何信息，使用測地線距離[17]構造局部幾何保持連接圖Gw。這是因為高維數據在核空間往往呈現折疊、螺旋或曲面等分布，導致歐氏距離無法正確計算樣本間的距離度量，而測地線距離能更好地根據樣本的幾何分布反映高維數據的流形信息。

定義1(局部幾何保持連接圖Gw)：Gw=(V,E),其中結點集V={x1,…,xl,xl+1,…,xl+u}，邊集E可表示為一個鄰接矩陣，基于高斯函數定義該鄰接矩陣的元素如式(6)所示。

(6)

其中exp(-d2(xi,xj)/t)為熱核函數，t為一個常數，KNN()表示K近鄰函數。距離度量函數d(xi,xj)的值由式(7)、式(8)計算得到：

值得注意的是，與常規LapSVM中使用的鄰接矩陣不同，dx(xi,xj)為圖Gw中邊長，dg(xi,xj)為同類別內結點xi和xj之間的測地線距離。初始化Gw時，如果xi和xj類別標簽相同且相鄰，則d(xi,xj)=dx(xi,xj)，否則d(xi,xj)設置為無窮大。

(9)

其中Dw為對角陣，Dw表示為Dw=∑l+uj=1Ww,ij，Lw=Dw-Ww為Gw的類內拉普拉斯矩陣。

2.2 LPCS-LapSVM

(10)

(11)

根據KKT條件，可得式(11)的對偶式為式(12)。

(12)

其中α是拉格朗日系數向量，Q=YJK(I+γILK+γGLwK)-1JTY，Y=diag(y1,y2,…,yl)，J=[I,0]l×(l+u)，I是l×l的單位陣。本文采用二次規劃問題求解方法可得式(12)的最優解α*，如式(13)、式(14)所示。

由此可得非線性LPCS-LapSVM的目標決策函數如式(15)所示。

(15)

通過上面的分析，得到LPCS-LapSVM算法的執行步驟，如算法1所示。

算法1：LPCS-LapSVM算法

輸入: l個已標記樣本{(xi,yi)}li=1,u個未標記樣本{(xj)}l+uj=l+1;輸出: 目標決策函數f*(x). //構建未標記數據的類內局部保持散度矩陣步驟1: 根據文獻[17]計算同類別內結點xi和xj之間的測地線距離dg(xi,xj);步驟2: 根據式(7)和式(8)計算xi和xj之間距離度量函數d(xi,xj);步驟3: 根據式(6)計算基于測地線距離的局部幾何保持連接圖矩陣Ww,ij;步驟4: 根據式(9)計算類內局部保持散度矩陣S^w;//使用全部訓練數據完成分類器的訓練步驟5: 對式(12)求解拉格朗日系數α*;

續表

LPCS-LapSVM算法在半監督學習框架的基礎上，繼承了半監督學習流形學習的特點，同時從考慮內在可分辨信息和樣本的局部幾何分布兩方面來提高代價敏感支持向量機在標記信息有限的場景中的分類性能。LPCS-LapSVM算法的時間復雜度采用了LapSVM框架，而LapSVM的時空復雜度與傳統的SVM相似，所以LPCS-LapSVM時間復雜度和空間復雜度分別是最差情況下為O((l+u)3)和O((l+u)2)，為了在一定程度上提高本文方法的執行效率, 可以采用SMO(sequential minimal optimization)等快速二次規劃優化算法求解。

3 實驗

3.1 實驗設置

為了評價本文所提LPCS-LapSVM算法的有效性，本文選取了代價敏感支持向量機(CS-SVM)[14]、Laplacian支持向量機(LapSVM)[15]、代價敏感Laplacian支持向量機(CS-LapSVM)[13]、代價敏感半監督支持向量機(CS4VM)[18]半監督和加權支持向量機(SSWSVM)[21]共5種對比算法進行比較實驗。實驗選擇12個UCI數據集[19]進行對比實驗，詳細的數據集描述見表1。所有樣本的特征值都被規范化到[0,1]區間上。按照通用不平衡數據的實驗設置，少數類樣本設置為正類，多數類樣本設置為負類，同時參照文獻[18]的設置，負類樣本的誤分類代價為1，正類樣本的誤分類代價為{2, 5,10}。各SVM算法的正則化參數C取值為{10-3,10-2,…，103}，LPCS-LapSVM的正類樣本的正則化參數是負類樣本的10倍。核函數均采用高斯核, 核參數σ取值為{10-3,10-2,…,103}。LPCS-LapSVM中的k-近鄰參數k取值范圍為{1,3,5,7，9}，參數γI和γG的取值范圍為{10-3,10-2,…,103}。對比算法的其他參數設置采取文獻的默認設置。本文采用測試集上的整體錯分損失[20]來評價算法的分類性能。本文實驗依照表1中正負類標記樣本的數目隨機選取相應的樣本，執行10次并記錄了運行10次的整體錯分損失的平均值和標準差。本文的實驗在2.53GHz quad-core CPU, 8GB RAM, Windows 7 系統下執行, 所有算法均在 Matlab 2016b環境下實現。

表1 UCI數據集描述

3.2 實驗結果

本文所提LPCS-LapSVM算法與5種對比算法的整體錯分損失進行了比較，實驗結果如表2～4所示，表2～4分別選取正類樣本的誤分類代價為2、5和10。本節中我們使用T檢驗[22]來判斷所提算法與5種對比算法之間是否統計學顯著性差異，并設置顯著性水平α=0.05，受篇幅的限制，在檢測的操作中，我們使用表中加注(*)的方式表示算法間存在顯著性差異，即若LPCS-LapSVM取得的整體錯分損失較小，且與對比算法的顯著性水平<0.05，則在對比算法的性能旁加標注(*)；若LPCS-LapSVM取得的整體錯分損失較大，或整體錯分損失較小但與對比算法的顯著性水平>0.05，則在對比算法的性能旁不加標注。另外，實驗還對正類樣本的誤分類代價為5時LPCS-LapSVM算法與5種對比算法的訓練時間進行了比較。根據表2～5的實驗結果可以得到以下結論。

(1) 4種半監督代價敏感支持向量機(CS-LapSVM、CS4VM、LPCS-LapSVM和SSWSVM)在訓練集標記信息不足的場景下處理不平衡數據的分類問題都有較好的學習能力。在正類樣本的誤分類代價為2、5和10時取得的實驗結果在整體錯分損失這一指標上具有相似性。但是本文所提的LPCS-LapSVM在整體錯分損失上具有相當的優勢，除了在兩個數據集上分別略遜于CS4VM和CS-LapSVM算法，兩個數據集上略遜于SSWSVM。這是因為： 第一，LPCS-LapSVM在LapSVM模型的框架基礎上，考慮了不同類別數據的錯分代價，能提高不平衡數據的分類精度，同時還融入了類內局部保持散度矩陣，保持同類別樣本的鑒別信息，還可以體現不同樣本之間的差異信息，即全局考慮了樣本的內在結構信息，這充分說明了類內局部保持散度矩陣有助于提高分類器的性能。第二，在計算類內局部保持散度矩陣時，使用測地線距離代替歐氏距離來計算兩個樣本點之間距離的方法是合適的。LPCS-LapSVM是基于SVM框架的，SVM在處理線性不可分的數據分類問題上，通常使用核技術將原始樣本通過各類核函數投影在核空間，在這種情況下，使用測地線距離更能表達樣本間的距離關系。

(2) CS-SVM和LapSVM算法的整體錯分損失明顯高于另外3種對比算法和LPCS-LapSVM算法。這是因為CS-SVM基于標記樣本充足的場景考慮不同類別數據的錯分代價，在標記數據不足的場景下其整體錯分損失上升迅速。LapSVM算法是一種優秀的半監督分類算法，但不適應于不平衡數據的分類問題，特別是兩類樣本不平衡比例較大時，LapSVM算法在正類上的分類精度較低，因而得到的整體錯分損失在所有算法中是較低的。

(3) 表2～表4中參照顯著性檢驗T檢驗的結果可知，所提LPCS-LapSVM在12個UCI數據集的大部分數據集上，與5種對比算法相比，均具有顯著性差異。說明LPCS-LapSVM在代價敏感的不平衡分類問題上具有顯著優勢，與5種對比算法相比是具有競爭力的。進一步說明，LPCS-LapSVM非常適用于代價敏感不平衡分類場景的應用。

(4) 表5顯示了LPCS-LapSVM算法與5種對比算法的訓練時間，實驗中比較的6種算法都是基于SVM的分類算法，訓練問題都可以轉換成QP(qualification programme)問題，時間復雜度為訓練樣本的3次方。CS-SVM的訓練時間最短，LPCS-LapSVM與另4種半監督SVM算法的訓練時間相當。其原因在于CS-SVM不是半監督SVM分類算法，而半監督SVM在訓練過程中需構建保持數據分布的幾何鄰接圖，因此CS-SVM相對時間復雜度較低，訓練時間較短。如何提高所提LPCS-LapSVM的計算效率是下階段的工作之一。

表2 各算法的整體錯分損失比較(正類樣本的誤分類代價為2)

表3 各算法的整體錯分損失比較(正類樣本的誤分類代價為5)

續表

表4 各算法的整體錯分損失比較(正類樣本的誤分類代價為10)

表5 各算法的訓練時間比較(正類樣本的誤分類代價為5，單位為s)

3.3 參數敏感性實驗

LPCS-LapSVM中需要設定的參數有6個： 正類樣本的誤分類代價參數c，k-近鄰參數，正則化參數C，高斯核核參σ，參數γI和γG。其中正則化參數C和高斯核核參σ是SVM模型中皆有的兩個參數，其最優值通常情況下都在給定的范圍內尋優獲得，由于篇幅的限制，本節沒有給出這兩個參數的敏感性分析結果。誤分類代價參數c對本文方法LPCS-LapSVM算法性能的影響如表2～4所示。表6顯示了k-近鄰參數k對本文方法LPCS-LapSVM在12個UCI數據集上的整體錯分損失的影響，實驗中固定誤分類代價參數c=5，正則化參數C和高斯核核參σ分別是1和0.1，參數γI和γG均為1。另外，圖2顯示了參數γI在4個UCI數據集上的敏感性實驗結果，實驗中固定誤分類代價參數c=5，正則化參數C和高斯核核參σ分別是1和0.1，k-近鄰參數k=5，參數γG為1。圖3顯示γG在4個UCI數據集上的敏感性實驗結果，實驗中固定誤分類代價參數c=5，正則化參數C和高斯核核參σ分別是1和0.1，k-近鄰參數k=5，參數γI為1。分析表6和圖2、圖3可得到以下的結論。

表6 LPCS-LapSVM在k-近鄰參數不同k值時的整體錯分損失

圖2 LPCS-LapSVM在不同參數γI下的G-mean值

圖3 LPCS-LapSVM在不同參數γG下的G-mean值

(1) 從表6結果可知，LPCS-LapSVM的分類性能受k取值的變化很大，但是我們也注意到，LPCS-LapSVM在12個UCI數據集上的整體錯分損失的最小值一般在k<7時獲得，當k值大于7時，整體錯分損失有所上升。因為在計算類內局部保持散度矩陣時使用的測地線距離是計算核空間中近鄰點最短距離的累加，當k取大值時，無法準確地表達這一空間距離信息。

(2) 參數γI的作用是調節流形正則項，通過在范圍{10-3，10-2，…，103}內尋優獲得最佳值。從圖2可知，各數據集上的整體錯分損失對γI值很敏感，且不同數據集獲得最佳分類效果時取得的γI值差異很大，因此參數γI適合在給定的數值范圍內尋優得到。

(3) 參數γG的作用是調節類內局部保持散度項，類內局部保持散度矩陣的計算結果與數據集在核空間分布有直接關系。從圖3結果可知，4個UCI數據集上的整體錯分損失也對參數γG敏感，因此參數γG也適合在給定的數值范圍內尋優得到。

4 結論

本文提出了局部幾何保持的Laplacian代價敏感支持向量機LPCS-LapSVM，該算法在LapSVM框架的基礎上融入了代價敏感學習的思想，還構造了一種新的類內局部保持散度矩陣，其使用測地線距離來計算核空間下結點間的距離，類內局部保持散度矩陣不僅能夠表示樣本的類別分布信息，還可以表示樣本的局部幾何結構特征，特別是保證兩類樣本的邊緣地帶的幾何特征。通過12個UCI數據集上的對比實驗，驗證了LPCS-LapSVM算法的有效性。