程鳳偉

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

引言

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

1 基于SVM的單類線性SVM模型

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

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

(1)

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

(2)

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

根據以上算法模型,本文提出了基于SVM的單類線性SVM算法(LOSVM),通過以下兩種方法來實現本文的算法:

1)將上述公式(1)中不等式增強為等式,轉化為:

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

(3)

2)將拉格朗日轉化為:

(4)

接著,我們將本文提出的LOSVM算法應用于層次聚類和核聚類。

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

將LOSVM算法應用于核聚類。核聚類算法側重于數據點與中心點的距離,而不是數據集投影的精確形狀,LOSVM算法獲得的超球雖然比較小,但是超球中心點的功能并不低于用K近鄰算法求得的中心點的功能。

圖1 單類SVM算法與LOSVM算法的聚類結果示意圖

2 實驗結果

將本文提出的算法與基于單類SVM核聚類算法和經典K-均值聚類算法進行比較,實驗采用著名的IRIS數據集,LOSVM算法中懲罰參數C取值為1000,q取值為0.78;單類SVM算法中C取值為1.0,q為0.78.

圖2 三種方法的聚類結果

圖2給出了三種方法的聚類結果,圖中用粗體十字來表示被錯誤聚類的數據點。實驗得出,K-均值聚類算法的正確率是88.7%,LOSVM算法的正確率是94.7%,單類SVM算法的正確率是96%,LOSVM算法與其他兩個算法相比,運行速度有很大的提高,運算精度雖有所下降,但在可接受范圍內。

3 結束語

本文提出了一種基于單類SVM的新型分類器LOSVM算法,通過消除方程中的二次方項大大提高了算法的運行速度,并將該算法應用于層次聚類和核聚類。在實驗中,雖然LOSVM的誤差大于單類SVM算法,但是LOSVM算法的運行速度較單類SVM算法有很大提高,同時說明LOSVM適合用于單類SVM算法的預處理算法,當將LOSVM應用于核聚類算法時,LOSVM的準確率幾乎與單類SVM相同。在未來的工作中,考慮將LOSVM算法應用于對稱矩陣和其他一些復雜算法的預處理算法中。