基于最小二乘孿生支持向量機(jī)的不確定數(shù)據(jù)學(xué)習(xí)算法

劉錦能，肖燕珊，劉 波

（1.廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院, 廣東 廣州 510006；2.廣東工業(yè)大學(xué) 自動(dòng)化學(xué)院, 廣東 廣州 510006）

支持向量機(jī)[1]是由Vapnik提出的一種用于二分類學(xué)習(xí)的監(jiān)督學(xué)習(xí)模型。支持向量機(jī)可以找到最大化間隔兩類的分割超平面。除了最大化間隔，支持向 量機(jī)還最小化分類誤差。如今，支持向量機(jī)已廣泛用于文本分類[2]、人臉識(shí)別[3]、目標(biāo)檢測(cè)[4]和生物醫(yī)療[5]等領(lǐng)域。然而，支持向量機(jī)有著O(n2)的時(shí)間復(fù)雜度，導(dǎo)致它不能很好地應(yīng)用在大規(guī)模數(shù)據(jù)的學(xué)習(xí)問(wèn)題。

為了加快訓(xùn)練速度，Mangasarian和Wild通過(guò)求解生成的特征值問(wèn)題提出了尋求2個(gè)不平行超平面的模型[6](Generalized Eigenvalue Problem Support Vector Machine, GEPSVM) 。對(duì)于每一類數(shù)據(jù)點(diǎn)，GEPSVM給它們分配一個(gè)超平面，通過(guò)求解2個(gè)廣義特征值問(wèn)題，2個(gè)不平行的超平面就能得到，它們是2個(gè)特征向量，對(duì)應(yīng)廣義特征值問(wèn)題的2個(gè)最小特征值。Jayadeva等[7]采用相似于GEPSVM的方法，提出了孿生支持向量機(jī)模型。類似地，它使一類的數(shù)據(jù)點(diǎn)靠近一個(gè)超平面，同時(shí)遠(yuǎn)離另一個(gè)超平面，從而導(dǎo)致求解的是2個(gè)小型的二次規(guī)劃問(wèn)題。與傳統(tǒng)支持向量機(jī)需要求解單個(gè)大的二次規(guī)劃問(wèn)題不同，孿生支持向量機(jī)只計(jì)算2個(gè)小的二次規(guī)劃問(wèn)題，這使得孿生支持向量機(jī)的訓(xùn)練時(shí)間是傳統(tǒng)支持向量機(jī)的四分之一[7]。孿生支持向量機(jī)已被拓展為各種變體，包括投影孿生支持向量機(jī)[8]、偏二叉樹(shù)孿生支持向量機(jī)[9]和最小二乘孿生支持向量機(jī)(Least Squares Twin Support Vector Machine, LSTSVM)[10-13]。最小二乘孿生支持向量機(jī)是由孿生支持向量機(jī)衍生而來(lái)，區(qū)別在于將孿生支持向量機(jī)中的不等式約束修改為最小二乘孿生支持向量機(jī)中的等式約束。因此，用一對(duì)線性方程組代替兩個(gè)凸二次規(guī)劃問(wèn)題可以更高效地求解該問(wèn)題。

現(xiàn)有的有關(guān)孿生支持向量機(jī)的工作，大多假設(shè)訓(xùn)練數(shù)據(jù)可以準(zhǔn)確地收集，沒(méi)有任何不確定的信息。然而，由于傳輸干擾或測(cè)量誤差，數(shù)據(jù)不可避免地包含不確定信息。為了處理數(shù)據(jù)的不確定性，Qi等[14]通過(guò)求解二階錐規(guī)劃(Second-Order Cone Programming,SOCP) 問(wèn)題提出了一種魯棒孿生支持向量機(jī)方法(Robust Twin Support Vector Machine, R-TWSVM) 用于模式識(shí)別。然而，它必須解決導(dǎo)致高計(jì)算成本的SOCP問(wèn)題。

為此，本文提出了一種新的基于不確定數(shù)據(jù)的最小二乘孿生支持向量機(jī)方法，該方法能夠高效地處理數(shù)據(jù)的不確定性。首先，考慮到數(shù)據(jù)可能包含不確定信息，引入一個(gè)噪聲向量來(lái)建模每個(gè)實(shí)例的不確定信息。其次，將噪聲向量融入最小二乘孿生支持向量機(jī)。最后，采用2步啟發(fā)式框架求解優(yōu)化問(wèn)題。

1 面向不確定性數(shù)據(jù)的最小二乘孿生支持向量機(jī)

1.1 線性模型構(gòu)建

所收集的實(shí)例數(shù)據(jù)x可能被噪聲破壞。本文引入一個(gè)噪聲向量 Δx對(duì)不確定性信息進(jìn)行建模，使得真正的實(shí)例表示為x+Δx。噪聲向量Δx是未知的，將在學(xué)習(xí)訓(xùn)練過(guò)程中得到優(yōu)化。將實(shí)例表示為x+Δx，對(duì)應(yīng)地，數(shù)據(jù)矩陣A和B可 以表示為A+ΔA和B+ΔB?；谏鲜龆x，面向不確定性數(shù)據(jù)的線性最小二乘孿生支持向量機(jī)(Uncertain-data-based Least Squares Twin Support Vector Machine, ULSTSVM) 的優(yōu)化公式可表示為

1.2 模型求解

由于變量ω(1)，b(1)， ω(2)，b(2)，ξ(1)，ξ(2)，ΔA和 ΔB是未知的，很難求解優(yōu)化函數(shù)(1) 。在本文采用啟發(fā)式框架來(lái)處理該優(yōu)化問(wèn)題，并提出了一種新的方案來(lái)評(píng)估每個(gè)訓(xùn)練數(shù)據(jù)點(diǎn)的邊界參數(shù)δ1i和δ2j。

為了求解問(wèn)題(1) ，本文提出了由2個(gè)步驟組成的啟發(fā)式框架。第1步， ΔA和 ΔB是固定的，通過(guò)求解2個(gè)二次規(guī)劃問(wèn)題(3) 和(4) ，可以得到 ω(1)，b(1)，ω(2)和b(2)。在第2步中，ω(1)，b(1)，ω(2)和b(2)是固定的，更新ΔA和ΔB。2個(gè)步驟的細(xì)節(jié)如下所示。

1.2.1 固定噪聲向量，求解超平面

首 先 初 始 化 ΔA和ΔB，并 確 保| |ΔAi||≤δ1i和||ΔBj||≤δ2j。然后，可以移除優(yōu)化問(wèn)題(1) 中的約束||ΔAi||≤δ1i和||ΔBj||≤δ2j。目標(biāo)函數(shù)表示為

在問(wèn)題(8) ，第1個(gè)和第2個(gè)約束式都是等式約束，將它們代入到問(wèn)題(8) ，可以得到

1.2.3 啟發(fā)式框架

本文采用一個(gè)啟發(fā)式框架來(lái)求解目標(biāo)方程(1) 。在第1步中，固定矩陣 ΔA和ΔB，然后學(xué)習(xí)分類器f1(x)和f2(x) 。在第2步中，固定學(xué)習(xí)分類器f1(x)和f2(x)， 然后更新矩陣ΔA和 ΔB。在滿足停止條件之前，這兩個(gè)步驟將不斷迭代。ULSTSVM的偽代碼如算法1所示。這里使用文獻(xiàn)[16]中的迭代停止標(biāo)準(zhǔn)來(lái)確定ULSTSVM的終止。設(shè)Fval(t)表示目標(biāo)函數(shù)(1) 在第t次迭代中的值。當(dāng) |Fval(t)-Fval(t-1)|與Fmax的比值小于參數(shù)ε，算法就會(huì)終止。ε ≥0是一個(gè)非負(fù)參數(shù)。在實(shí)驗(yàn)中，將ε 設(shè)置為0.1。

此外，在問(wèn)題(1) 中，需要給出參數(shù) δ1i和δ2j的值。如文獻(xiàn)[17]中所述，對(duì)于正類中的實(shí)例x1i，這里計(jì)算x1i與其k個(gè)近鄰之間的距離，距離的平均值分配給δ1i。上述方法也適用于負(fù)類中的實(shí)例x2j。這樣，可以得到δ1i和δ2j的值。

1.3 非線性核函數(shù)

受非線性孿生支持向量機(jī)的啟發(fā)，這里將線性ULSTSVM擴(kuò)展到非線性情況，旨在學(xué)習(xí)2個(gè)用核函數(shù)生成的超平面(14) 和(15) 。

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

本文將ULSTSVM與3個(gè)對(duì)比方法在不同數(shù)據(jù)集上進(jìn)行比較，以驗(yàn)證其有效性。所有的實(shí)驗(yàn)都在MATLAB中運(yùn)行，機(jī)器設(shè)備是一臺(tái)Intel Core I5 CPU、4GB內(nèi)存的筆記本電腦。在實(shí)驗(yàn)中，本文的目標(biāo)是：(1) 在真實(shí)數(shù)據(jù)集上驗(yàn)證ULSTSVM的性能。(2) 當(dāng)噪聲數(shù)據(jù)呈百分比變化時(shí)，驗(yàn)證ULSTSVM的性能。(3) 驗(yàn)證ULSTSVM的訓(xùn)練時(shí)間。

2.1 對(duì)比方法與實(shí)驗(yàn)設(shè)置

第1個(gè)對(duì)比方法是最小二乘孿生支持向量機(jī)LSTSVM[10]，它生成2個(gè)不平行超平面來(lái)分離2類數(shù)據(jù)點(diǎn)。然而，LSTSVM假設(shè)數(shù)據(jù)可以精確收集，并且數(shù)據(jù)中沒(méi)有不確定的信息。它沒(méi)有考慮數(shù)據(jù)的不確定性問(wèn)題。它用于展示ULSTSVM在處理不確定數(shù)據(jù)方面的性能。

第2個(gè)對(duì)比方法是魯棒孿生支持向量機(jī)RTWSVM[14]，用于處理孿生支持向量機(jī)中的實(shí)例噪聲問(wèn)題。然而，它需要解決具有高時(shí)間復(fù)雜度的SOCP問(wèn)題。它用于展示ULSTSVM的訓(xùn)練效率。

第3個(gè)對(duì)比方法是總支持向量機(jī)(Total Support Vector Classification, TSVC)[18]，它是基于傳統(tǒng)支持向量機(jī)并且考慮了數(shù)據(jù)的不確定性。

本文在UCI數(shù)據(jù)集和真實(shí)的不確定數(shù)據(jù)集上測(cè)試上述方法。本文使用準(zhǔn)確率作為UCI數(shù)據(jù)集的評(píng)估指標(biāo)，并使用F1度量作為真實(shí)不確定數(shù)據(jù)集的評(píng)估指標(biāo)。在實(shí)驗(yàn)中，分別使用了線性核和RBF核。對(duì)于所有的方法，如果使用RBF核，核參數(shù) σ都是從集合{10i|i=-7,···,7} 中獲取。正則化參數(shù)C從集合{2i|i=-7,···,7}中獲取。此外，在R-TWSVM中，參數(shù)R從集合 {0,0.01,0.02,···,0.1}中獲取。在本文的方法中，計(jì)算實(shí)例的K個(gè)近鄰的距離取平均值來(lái)設(shè)置實(shí)例的邊界參數(shù)δ。參數(shù)K設(shè)置為0.1n，其中n是數(shù)據(jù)集中的實(shí)例數(shù)。此外，本文將閾值參數(shù)ε 設(shè)置為0.1。

2.2 UCI數(shù)據(jù)集

UCI數(shù)據(jù)集包括“Hepatitis” “WPBC”“BUPA liver”“Heart-Stalog”“Sonar”“Votes” “Australian”“German”“Breast”和 “Pima”。本文采用十折交叉驗(yàn)證來(lái)記錄結(jié)果。對(duì)于每個(gè)數(shù)據(jù)集，將其分成相等的10個(gè)部分。在每一輪中，訓(xùn)練集由9個(gè)部分組成，剩下的一部分作為測(cè)試集處理，并記錄準(zhǔn)確率的平均結(jié)果。按照文獻(xiàn)[19-21]的方法生成UCI數(shù)據(jù)集中的不確定信息。對(duì)于每一個(gè)維度，計(jì)算數(shù)據(jù)集的標(biāo)準(zhǔn)偏差σi。在[0, 2σi]范圍內(nèi)生成一個(gè)偏差值。然后，用生成的第i維偏差值來(lái)產(chǎn)生噪聲數(shù)據(jù)，這使得噪聲在不同維度上有所不同。將噪聲隨機(jī)添加到40% 的訓(xùn)練集實(shí)例中。訓(xùn)練數(shù)據(jù)加上噪聲后，在UCI數(shù)據(jù)集上對(duì)ULSTSVM，LSTSVM，R-TWSVM和TSVC這4種方法進(jìn)行比較。非線性核RBF下的分類準(zhǔn)確率如表1所示。

表1 RBF核在UCI數(shù)據(jù)集上的分類準(zhǔn)確率Table 1 Classification accuracy of the RBF kernel on the UCI dataset %

從表1中可以看出，本文的方法ULSTSVM明顯比LSTSVM獲得更高的分類準(zhǔn)確率，同時(shí)在大多數(shù)UCI數(shù)據(jù)集中，分類準(zhǔn)確率與R-TWSVM和TSVC相當(dāng)。本文的方法不同于LSTSVM，因?yàn)長(zhǎng)STSVM沒(méi)有考慮到數(shù)據(jù)的不確定性。在每個(gè)實(shí)例中引入一個(gè)噪聲變量來(lái)對(duì)不確定信息進(jìn)行建模，并對(duì)該變量進(jìn)行優(yōu)化，以獲得更魯棒的分類超平面。與LSTSVM相比，ULSTSVM具有更好的性能，這表明本文的方法能夠有效地處理不確定數(shù)據(jù)。

2.3 真實(shí)的不確定數(shù)據(jù)集

本文在個(gè)人活動(dòng)定位數(shù)據(jù)集(Localization Data Person Activity，LDPA) 上進(jìn)行了實(shí)驗(yàn)。LDPA是基于傳感器的異?；顒?dòng)預(yù)測(cè)的數(shù)據(jù)集。它包含5個(gè)人的11項(xiàng)活動(dòng)。這些活動(dòng)有“摔倒”“走路”“躺下”“洗衣服”“四肢著地”等。按照文獻(xiàn)[22]中的處理方式，將11項(xiàng)活動(dòng)分為兩類?！八闹亍薄八さ埂薄白诘厣险酒饋?lái)”和“坐在地上”被分為正類，其余活動(dòng)被視為負(fù)類。在文獻(xiàn)[22]中，F(xiàn)1值用作評(píng)估指標(biāo)，它是平衡精確率p和召回率r的一個(gè)指標(biāo)。計(jì)算F1值的方法是F1=2pr/(p+r)。

ULSTSVM和3種對(duì)比方法在LDPA數(shù)據(jù)集上的F1值如圖1所示。很明顯地看到，ULSTSVM在LDPA數(shù)據(jù)集上獲得了最高的F1值。具體來(lái)說(shuō)，LSTSVM具有最低的F1值，因?yàn)樗鼪](méi)有考慮數(shù)據(jù)的不確定性。此外，ULSTSVM與R-TWSVM和TSVC的分類性能相當(dāng)。本文引入噪聲向量Δx對(duì)不確定信息進(jìn)行建模，并采用兩步啟發(fā)式框架求解優(yōu)化問(wèn)題，并且在LDPA數(shù)據(jù)集上證明了該方法的有效性。

圖1 不同方法在LDPA數(shù)據(jù)集上的F1值Fig.1 F1-measure values of different methods on the LDPA dataset

2.4 不同噪聲水平

在本小節(jié)中，研究ULSTSVM、LSTSVM、RTWSVM和TSVC對(duì)不同數(shù)據(jù)噪聲水平的敏感性。這里讓噪聲百分比從0%上升到100%。在圖2中，x軸為噪聲百分比，y軸為平均準(zhǔn)確率。首先可以看出，當(dāng)噪聲百分比增加時(shí)，4種方法的分類性能同步降低。這是由于隨著噪聲數(shù)據(jù)點(diǎn)的增加，正類和負(fù)類之間的分類邊界存在偏差，分類器很難對(duì)正負(fù)數(shù)據(jù)進(jìn)行分類。其次，當(dāng)噪聲數(shù)據(jù)的比例從20%增加到100%時(shí)，ULSTSVM比LSTSVM有更高的分類準(zhǔn)確率。因?yàn)榭紤]了數(shù)據(jù)不確定的影響，ULSTSVM能夠獲得比LSTSVM更好的分類性能。最后，ULSTSVM與RTWSVM和TSVC相比，ULSTSVM在大多數(shù)數(shù)據(jù)集上都具有更好的分類效果。

圖2 不同方法在不同噪聲水平數(shù)據(jù)集上的分類準(zhǔn)確率Fig.2 Accuracy of different methods on the datasets with different levels of noise

2.5 訓(xùn)練時(shí)間

在上述幾個(gè)小節(jié)中，研究了ULSTSVM和3種對(duì)比方法在UCI數(shù)據(jù)集和LDPA數(shù)據(jù)集上的分類性能以及對(duì)不同數(shù)據(jù)噪聲水平的敏感性，本節(jié)將比較它們的訓(xùn)練時(shí)間。圖3給出了ULSTSVM、R-TWSVM和TSVC在UCI數(shù)據(jù)集上的訓(xùn)練時(shí)間。首先，可以看到ULSTSVM在所有數(shù)據(jù)集上都用了最少的訓(xùn)練時(shí)間，是最高效的方法。其次，ULSTSVM的訓(xùn)練速度比RTWSVM快得多。R-TWSVM需要解決計(jì)算量較大的SOCP問(wèn)題。而ULSTSVM沒(méi)有像R-TWSVM那樣求解SOCP問(wèn)題，只是求解線性方程組，這使得本文的方法比R-TWSVM訓(xùn)練得更快。最后，ULSTSVM明顯比TSVC快。TSVC是基于傳統(tǒng)支持向量機(jī)的，因此它求解的是單個(gè)具有不等式約束的大規(guī)模的二次規(guī)劃問(wèn)題。相比之下，ULSTSVM是基于最小二乘孿生支持向量機(jī)的，因此它只需求解2個(gè)較小規(guī)模的二次規(guī)劃問(wèn)題，這使得ULSTSVM比TSVC更高效。

圖3 不同方法在UCI數(shù)據(jù)集上的訓(xùn)練時(shí)間Fig.3 The training time of different methods on the UCI dataset

3 結(jié)論

本文提出了一種用于求解帶有不確定數(shù)據(jù)的最小二乘孿生支持向量機(jī)模型ULSTSVM。ULSTSVM是R-TWSVM在最小二乘意義上的擴(kuò)展。與需要解決SOCP問(wèn)題的R-TWSVM相比，ULSTSVM更加高效，因?yàn)樗恍枨蠼饩€性方程組。在ULSTSVM中，首先，引入噪聲向量對(duì)每個(gè)實(shí)例的不確定信息進(jìn)行建模，并在訓(xùn)練階段對(duì)噪聲向量進(jìn)行優(yōu)化，使模型對(duì)噪聲的影響不太敏感。其次，本文將最小二乘孿生支持向量機(jī)的思想融入到ULSTSVM中，使得這個(gè)方法比RTWSVM跑得更快。最后，采用2步啟發(fā)式框架解決了ULSTSVM的學(xué)習(xí)問(wèn)題。

本文的方法ULSTSVM在訓(xùn)練速度上超過(guò)了RTWSVM，同時(shí)也獲得了相當(dāng)不錯(cuò)的分類效果。

（責(zé)任編輯：楊耀輝 英文審核：費(fèi)倫科）