程鳳偉

(太原學(xué)院,山西 太原 030032)

引言

為了使支持向量機(jī)理論應(yīng)用于無(wú)監(jiān)督學(xué)習(xí),Tax 和 Duin[1]提出了單類(lèi)支持向量機(jī)算法,成功地應(yīng)用于層次聚類(lèi)[2-3]和核聚類(lèi)等算法中[4-5],單類(lèi)SVM分類(lèi)算法的主要思想是用一個(gè)適當(dāng)?shù)暮瘮?shù)[6-7]代替內(nèi)積將數(shù)據(jù)點(diǎn)映射到高維特征空間,在特征空間里找到一個(gè)能包含最多數(shù)據(jù)點(diǎn)映射的最小范圍,單類(lèi)SVM算法的關(guān)鍵步驟在于解決一個(gè)有關(guān)樣本維度的二次規(guī)劃問(wèn)題。隨著樣本數(shù)目的增加,算法的復(fù)雜度也越來(lái)越高。為了避免解決二次規(guī)劃問(wèn)題,本文提出了基于SVM的單類(lèi)線(xiàn)性分類(lèi)算法(Linear One-Class Classification Algorithm based on SVM,LOSVM),采用兩種方法分別消除二次項(xiàng)和不等式。首先,增強(qiáng)約束不等式方程;其次,為拉格朗日懲罰項(xiàng)加平方。計(jì)算出簡(jiǎn)化的拉格朗日公式后,便可得到一組計(jì)算簡(jiǎn)便的線(xiàn)性方程。本文提出的新的分類(lèi)算法可以應(yīng)用到聚類(lèi)和核聚類(lèi)問(wèn)題中。實(shí)驗(yàn)結(jié)果表明,本算法與單類(lèi)SVM算法相比,在正確率不變的情況下,運(yùn)行速率大大提高。

1 基于SVM的單類(lèi)線(xiàn)性SVM模型

單類(lèi)SVM算法是一種針對(duì)只有正類(lèi)樣本組成的數(shù)據(jù)集進(jìn)行處理的核方法,算法的主要思想是計(jì)算出在特征空間能包含所有樣本映射的最小超球。

‖φ(xi)-α‖2≤R2ξ+εi

(1)

其中,‖·‖是歐幾里得范數(shù),a是超球的中心,R是超球的半徑,ξi是松弛變量,ξi≥0,i=0,1,2…n,為了解決這個(gè)問(wèn)題,我們引入

(2)

其中,αi≥0和βi≥0,i=1,2,3…n,αi,βi是與公式(1)及ξi相關(guān)的拉格朗日乘子,C用來(lái)權(quán)衡算法的簡(jiǎn)易性和容錯(cuò)程度。

根據(jù)以上算法模型,本文提出了基于SVM的單類(lèi)線(xiàn)性SVM算法(LOSVM),通過(guò)以下兩種方法來(lái)實(shí)現(xiàn)本文的算法:

1)將上述公式(1)中不等式增強(qiáng)為等式,轉(zhuǎn)化為:

‖φ(xi)-α‖2=R2+ξi

(3)

2)將拉格朗日轉(zhuǎn)化為:

(4)

接著,我們將本文提出的LOSVM算法應(yīng)用于層次聚類(lèi)和核聚類(lèi)。

將LOSVM算法應(yīng)用于層次聚類(lèi)算法。在高維特征空間得到的超球模型由若干部分組成,每部分是一個(gè)包含數(shù)據(jù)點(diǎn)的獨(dú)立聚類(lèi),定義R(x)為特征空間數(shù)據(jù)點(diǎn)到超球中心的距離函數(shù),R作為最小超球的半徑,那么數(shù)據(jù)空間中球面的投影集合是{x|R(x)=R}。圖1是單類(lèi)SVM算法和LOSVM算法在同一數(shù)據(jù)集上的聚類(lèi)結(jié)果的示意圖,數(shù)據(jù)集由220個(gè)點(diǎn)組成,其中右上60個(gè)點(diǎn),左下60個(gè)點(diǎn),中間100個(gè)點(diǎn)。從圖1可知,LOSVM算法的誤差大于單類(lèi)SVM算法的誤差,因?yàn)樵谶吘壍臄?shù)據(jù)點(diǎn)(ξi>0)會(huì)被較小的球拒絕,然而對(duì)于LOSVM來(lái)說(shuō),為每一個(gè)數(shù)據(jù)點(diǎn)分配一個(gè)聚類(lèi)并不是必要的。我們采用層次聚類(lèi)算法對(duì)內(nèi)部的點(diǎn)(ξi<=0)進(jìn)行標(biāo)記,對(duì)于外部的數(shù)據(jù)點(diǎn)(ξi>0)采用K近鄰算法[8]進(jìn)行標(biāo)記。顯然,LOSVM算法可以將數(shù)據(jù)集劃分為兩部分:內(nèi)集和邊緣集,而邊緣集包含了潛在支持向量,這些支持向量可以在單類(lèi)SVM算法模型中進(jìn)一步訓(xùn)練。因此,LOSVM可以用于支持向量機(jī)的預(yù)處理,它也適用于在一定條件下的監(jiān)督學(xué)習(xí),基于LOSVM的預(yù)處理算法也正在進(jìn)一步研究中。

將LOSVM算法應(yīng)用于核聚類(lèi)。核聚類(lèi)算法側(cè)重于數(shù)據(jù)點(diǎn)與中心點(diǎn)的距離,而不是數(shù)據(jù)集投影的精確形狀,LOSVM算法獲得的超球雖然比較小,但是超球中心點(diǎn)的功能并不低于用K近鄰算法求得的中心點(diǎn)的功能。

圖1 單類(lèi)SVM算法與LOSVM算法的聚類(lèi)結(jié)果示意圖

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

將本文提出的算法與基于單類(lèi)SVM核聚類(lèi)算法和經(jīng)典K-均值聚類(lèi)算法進(jìn)行比較,實(shí)驗(yàn)采用著名的IRIS數(shù)據(jù)集,LOSVM算法中懲罰參數(shù)C取值為1000,q取值為0.78;單類(lèi)SVM算法中C取值為1.0,q為0.78.

圖2 三種方法的聚類(lèi)結(jié)果

圖2給出了三種方法的聚類(lèi)結(jié)果,圖中用粗體十字來(lái)表示被錯(cuò)誤聚類(lèi)的數(shù)據(jù)點(diǎn)。實(shí)驗(yàn)得出,K-均值聚類(lèi)算法的正確率是88.7%,LOSVM算法的正確率是94.7%,單類(lèi)SVM算法的正確率是96%,LOSVM算法與其他兩個(gè)算法相比,運(yùn)行速度有很大的提高,運(yùn)算精度雖有所下降,但在可接受范圍內(nèi)。

3 結(jié)束語(yǔ)

本文提出了一種基于單類(lèi)SVM的新型分類(lèi)器LOSVM算法,通過(guò)消除方程中的二次方項(xiàng)大大提高了算法的運(yùn)行速度,并將該算法應(yīng)用于層次聚類(lèi)和核聚類(lèi)。在實(shí)驗(yàn)中,雖然LOSVM的誤差大于單類(lèi)SVM算法,但是LOSVM算法的運(yùn)行速度較單類(lèi)SVM算法有很大提高,同時(shí)說(shuō)明LOSVM適合用于單類(lèi)SVM算法的預(yù)處理算法,當(dāng)將LOSVM應(yīng)用于核聚類(lèi)算法時(shí),LOSVM的準(zhǔn)確率幾乎與單類(lèi)SVM相同。在未來(lái)的工作中,考慮將LOSVM算法應(yīng)用于對(duì)稱(chēng)矩陣和其他一些復(fù)雜算法的預(yù)處理算法中。