基于非線性核的SVM模型可視化策略

郭 明 朱 焱

(西南交通大學信息科學與技術學院 四川 成都 611756)

0 引 言

支持向量機(SVM)是一種基于黑盒模型的分類器。由于在數據挖掘建模的過程中隱藏了具體的分析細節,導致許多使用支持向量機模型解決問題的用戶,不太清楚其內部的分類機制。

大數據可視化技術是當前的研究熱點?；谀Ｐ涂梢暬难芯坑兄诶斫饽Ｐ偷膬仍诜治鲈?并增強結果的可信度。目前基于模型可視化的研究多針對決策樹或神經網絡[1]。SVM可視化的研究主要分為以下兩個方面：

(1) 基于模型轉換的可視化方法。Jakulin等[2]根據線性核中特征的可加性,首次將線性SVM模型的核函數轉換成概率模型,并利用Nomogram進行可視化。隨后在此基礎上,Cho等[3]提出利用局部徑向基核函數解決非線性核中特征不可加性的難題。Belle等[4]則在Nomogram可視化中融合顏色表達。文獻[2-4]提出的可視化方法能夠反映出每個特征對預測結果的影響程度,但是Nomogram是一個概率模型,無法在可視化上刻畫超平面,導致可視化后的SVM模型仍然難以被直觀理解。

(2) 基于數據與超平面關系的可視化方法。Caragea等[5]借助tours工具對多維數據進行低維線性投影,并通過網格采樣點來夾逼不同類之間的邊界。Hamel[6]采用自組織映射將多維數據投射到二維空間,并在支持向量之間適當模擬一個判別超平面。Ma等[7]將模型分為線性核和非線性核,對于線性核,通過包圍盒采樣線性超平面上的點,然后平行投影到二維空間,利用這些點的密集分布刻畫超平面；而對于非線性核,采用多個局部線性模型替代全局模型的方法。其中文獻[5-6]側重分類結果的表達,它刻畫的超平面是在二維空間根據正負類邊界模擬出的,因此,這種超平面無法定義數據與真實超平面之間的距離關系。文獻[7]在可視化線性核模型時,具有良好的直觀性；然而,在可視化非線性核模型時,非線性全局模型和局部線性模型的替代是參照兩者之間的分類精度,其說服力不強。在基于數據與超平面關系的可視化方法中,克服維度約束至關重要。文獻[5-7]都是將數據通過二維投影進行可視化展示,但是在刻畫超平面上,卻存在明顯缺陷,尤其是非線性核超平面。因此,目前關于超過二維空間的非線性SVM模型的可視化,仍然是一個重要挑戰。

針對方法(1)在模型的直觀理解上存在明顯缺陷和方法(2)在刻畫超過二維空間非線性超平面上存在的困難,本文對非線性核SVM模型超平面可視化技術展開了深入研究,并將模型分為三維特征模型與多維特征模型兩類,分別引入了曲面擬合和信息重構的思想,提出了基于移動最小二乘法擬合的三維特征模型超平面可視化策略與基于t-SNE點重構的多維特征模型超平面可視化策略,最后通過實驗數據對相關可視化策略進行驗證。實驗結果表明,本文提出基于非線性核的SVM模型可視化策略具有良好的直觀性,并在一定程度上解決了三維、多維空間非線性核超平面難以刻畫的問題。

1 相關工作

1.1 支持向量機(SVM)

設一組訓練樣本T={(x1,y1),(x2,y2),…,(xn,yn)},x∈Rm,y∈{-1,1},其中：x表示特征；y表示類標；n為樣本的個數；m為特征的個數。假設樣本數據是線性可分的,支持向量機通過訓練,尋找一個超平面將數據劃分為{-1,1}兩類。線性支持向量如圖1所示。

圖1 線性支持向量示意圖[7]

定義1(超平面) 在支持向量機模型中,劃分正負類樣本的決策目標函數稱為超平面。線性支持向量機的判別式為：

WTX+b=0

(1)

式中：X是m維特征向量；W是超平面的法向量；b是截距。

定義2(支持向量) 在支持向量機模型中,距離超平面最近且滿足一定條件的幾個訓練樣本點被稱為支持向量[8]。正類和負類支持向量所在的邊界可表示為：

WTX+b=1

(2)

WTX+b=-1

(3)

優化式(2)和式(3)滿足最大間隔。最后經推導,可得出支持向量機的決策目標函數：

(4)

式中：k表示支持向量的個數；αi為第i個支持向量的拉格朗日系數；yi為第i個支持向量的原始類標；xi為支持向量對應的特征；x為待預測樣本的特征；K(xi,x)表示核函數。

定義3(核函數) 對于所有x,x′∈χ,滿足K(x,x′)=(Φ(x),Φ(x′))[8]，其中Φ表示非線性函數。常見的非線性核函數有：

(2) 多項式核：K(x,x′)=(xTx′)n。

1.2 移動最小二乘法

移動最小二乘法[9]是在最小二乘法基礎上引入了基函數和緊支撐權函數。

定義4(擬合函數) 在擬合區的局部子域上,擬合函數可表示為[10]：

(5)

定義5(緊支撐權函數) 緊支撐權函數是帶約束的權函數。常用的緊支撐權函數是樣條函數：

設影響域的半徑為d,假設對于二維問題,待擬合的點為(x,y),影響域中的點有(xI,yI),則:

加入緊支撐權函數,計算所有待擬合數據點的誤差加權平方和有：

(6)

式中：m表示影響域中的點個數；w(sI)為(xI,yI)處的影響權重；f(x)是擬合函數；yI是x=xI處的節點值。

然后取式(6)的極小值,可求出a(x),最后將a(x)代入式(5)中,便可求出x處的擬合值。

1.3 t-SNE降維

t-SNE是由Maaten等[11-12]提出的對高維數據的可視化方法。t-SNE降維核心思想為：將數據點的歐氏距離轉換為鄰近概率分布。設高維空間中的數據集X=(x1,x2,…,xn),其在低維空間中的映射數據表示為Y=(y1,y2,…,yn)。其中n表示數據點的個數。高維空間中的數據的概率分布可由式(7)定義,低維空間中的數據的概率分布可由式(8)定義。

(7)

(8)

式中：pij表示以xi為中心,xj到xi的鄰近概率；qij表示以yi為中心,yj到yi的鄰近概率。

使用KL散度計算qij對pij的忠實度有：

(9)

式中：C是總代價；P是高維空間的聯合概率分布；Q是低維空間的聯合概率分布。

(10)

式中：Y表示低維空間的坐標；t表示不同迭代階段；η表示學習率；α(t)表示t階段時的動量。

t-SNE能夠在低維空間保留數據在高維空間的全局結構和局部結構,并有效地解決了SNE在降維處理時參數難以尋優和低維空間數據擁擠的問題。因此,它已成為高維數據可視化的重要方法之一。

2 可視化設計策略

當特征空間的維度從二維上升到三維時,由于維度的增加,造成了非線性核超平面目標函數在三維特征空間難以有效轉換。因此,大部分研究學者選擇投影至二維空間后去模擬超平面或利用線性超平面替代非線性超平面的方法。

本文在研究三維特征空間非線性核SVM模型可視化時,未沿用上述可視化方法。主要出于三個方面考慮：(1) 二維投影后模擬出的超平面無法反映真實數據點與真實超平面之間的距離關系；(2) 線性超平面替代非線性超平面的不確定性太強且說服力不足；(3) 三維空間本身就處于人類可識別的維度范圍內。

因此,如果將三維特征空間非線性核SVM模型在三維空間進行可視化,那么就可以有效避免(1)和(2)存在的問題。然而,非線性核超平面卻難以直接通過超平面方程進行平面/曲面采樣。為此,本文引入網格采樣+曲面擬合的思想,提出了基于移動最小二乘法擬合的三維特征模型超平面可視化策略MLS-SVMVis。該策略通過網格采樣超平面上的點；由于直接通過采樣點繪制超平面,超平面在光滑性和直觀性上都存在極大的視覺缺陷,故MLS-SVMVis策略以超平面采樣點為基礎,采用移動最小二乘法對超平面進行擬合,從而改善了非線性SVM模型的直觀性。具體算法步驟如算法1所示。

算法1MLS-SVMVis(D)

輸入：三維特征數據集D。

輸出：SVM可視化模型。

Begin:

1. 對數據集進行訓練,構建超平面方程；

2. 設定超平面預采樣點個數閾值nums；

3. 設定網格采樣參數,進行網格采樣；

4. 計算采樣點到超平面的距離d,統計d等于0的點的個數；

5. ifcount(d==0)

返回到步驟3,更新采樣參數；

6. 設定點的擬合偏差值閾值error；

7. 網格化擬合區域,設置基函數P和影響域半徑R；

8. 根據超平面采樣點,利用移動最小二乘法進行擬合,并計算擬合點的擬合偏差值；

9. for擬合超平面上每一個點的擬合偏差值miss

ifmiss>error

返回步驟7,更新基函數P和影響域半徑R；

10. 繪制超平面擬合曲面；

11. 輸出帶有數據點的三維SVM可視化模型；

End

對于一個n維特征的支持向量機模型,其超平面為(n-1)維。當特征空間高于三維時,非線性核模型的超平面將呈現出不規則的多維幾何體樣貌。因此,通過投影技術來展示超平面,可能無法在低維空間反映出數據與超平面之間的關系。

為了能夠反映高維數據分布情況以及數據與超平面之間的關系,本文根據t-SNE基于鄰近概率分布降維原理,引入信息重構的思想,提出了基于t-SNE點重構的多維特征模型超平面可視化策略PR-SVMVis。該策略以高維數據在二維空間上的分布和點到超平面之間的距離作為重構信息。對于一個多維特征空間非線性SVM模型,如果將點到超平面的距離d看作一個維度,那么這個維度能夠反映出點與超平面之間的關系,且刻度為0的地方即為超平面。然而,信息重構時,在高維數據的二維空間表示中增加了一個維度,會破壞數據原來的空間分布。為了使重構后數據依然保持原來的空間分布,本文利用t-SNE基于鄰近概率分布降維原理,通過擴大高維數據在轉換至二維空間展示時的坐標尺度,然后再與d進行信息重構,這樣就能達到弱化d的效果,從而降低了增加維度對數據的鄰近概率分布產生的影響。因此,重構后的數據,既能反映數據在高維空間的分布結構,還能刻畫出數據與超平面之間的關系。具體算法步驟如算法2所示。

算法2PR-SVMVis(D)

輸入：多維特征數據集D。

輸出：SVM可視化模型。

Begin:

1. 對數據集進行訓練,構建超平面方程；

2. 計算數據集到超平面的距離,記為集合D；

3. 通過的t-SNE將數據集降維到擴增尺度的二維空間,記為集合L；

4. 將L和D重構成三維坐標點,記為集合M；

5. 對于集合M,根據D的取值為0繪制超平面；

6. 輸出帶有數據點的SVM可視化模型；

End

3 實 驗

3.1 數據集與預處理

為了驗證本文提出的策略能夠有效地可視化非線性二分類SVM模型,本文選取了四個經典的UCI真實數據集(Iris、Seeds、Vertebral和Robot-Navigation)進行實驗。其中：Iris、Seeds和Vertebral用于驗證基于MLS-SVMVis可視化策略；Robot-Navigation用于驗證基于PR-SVMVis可視化策略。

Iris數據集選取類標為“Iris-setosa”(正類)和“Iris-versicolor”(負類)共100條樣本,實驗使用3個特征(sepal length、sepal width、petal length)。

Seeds數據集選取類標為“2”(正類)和“3”(負類)共140條樣本,實驗使用Seeds數據集PCA降維后的三維特征。

Vertebral數據集選取類標為“SL”(正類)和“NO”(負類)共250條樣本,實驗使用3個特征(sacral slope、pelvic radius、grade of spondylolisthesis)。

3個數據集分別選取80%作為訓練集和20%作為測試集。

Robot-Navigation也是Ma等[7]實驗中的數據集,共24個特征,本文保持與該實驗樣本的一致性,選取類標為“Sharp-Right-Turn”和“Move-Forward”共4 302條樣本，以“Sharp-Right-Turn”為正類,“Move-Forward”為負類,分別在正負類中各取50%作為訓練集和測試集。

3.2 驗證實驗與結果分析

3.2.1基于MLS-SVMVis三維特征模型可視化

Iris、Seeds和Vertebral都是小樣本數據集,本文在進行實驗時,將超平面預采樣點個數閾值nums設為200；然后,進行網格化,在每個特征取值范圍內采集了90個值,構建了90×90×90采樣點；由于在嚴格意義上不容易采集到距離超平面恰好為0的點,實驗設定點到超平面距離|d|≤0.000 85的點為超平面上的點。對于擬合函數,實驗選用了基函數PT=[1,x,y],error=0.1。分別設定3個數據集擬合函數的影響域半徑,RIris=0.7,RSeeds=0.6,RVertebral=0.7。

在可視化模型中,“■”代表正類,“●”代表負類；深灰色的平面表示超平面,淺色的平面表示正、負類支持向量邊界。

圖2、圖3、圖4分別展示了基于Iris數據集、Seeds數據集、Vertebral數據集的分類情況，其中ACC表示算法的準確率。其中圖2(a)、圖3(a)和圖4(a)是根據采樣點直接繪制的超平面,圖2(b)-圖2(d)、圖3(b)-圖3(d)和圖4(b)-圖4(d)是采用MLS-SVMVis策略擬合的超平面。對比兩者的可視化效果,可以看出采用MLS-SVMVis策略擬合的超平面是十分光滑的曲面或近似的平面,直觀性較好。分別計算3個數據集擬合超平面上各個點在超平面方程中的偏差值(即擬合點到超平面的距離)。missIris∈[-0.06,0.07],missSeeds∈[-0.08,0.01],missVertebral∈[-0.002,0.009]。

(a) 根據網格采樣點直接繪制的超平面 (b) 基于移動最小二乘法擬合的超平面(c) 加入正負、類支持向量邊界的可視化模型(d) 測試集在模型中的表現圖2 Iris非線性SVM模型展示(高斯核,σ=0.5,ACCtrain=1,ACCtest=1)

(a) 根據網格采樣點直接繪制的超平面 (b) 基于移動最小二乘法擬合的超平面 (c) 加入正負、類支持向量邊界的可視化模型 (d) 測試集在模型中的表現圖3 Seeds非線性SVM模型展示(高斯核,σ=5,ACCtrain=1,ACCtest=1)

(a) 根據網格采樣點直接繪制的超平面 (b) 基于移動最小二乘法擬合的超平面 (c) 加入正負、類支持向量邊界的可視化模型 (d) 測試集在模型中的表現圖4 Vertebral非線性SVM模型展示(多項式核,n=2,C=1.5,ACCtrain=0.944,ACCtest=0.975)

MLS-SVMVis策略在保持擬合效果同時,改善了通過采樣點直接繪制SVM模型超平面的粗糙性,它能夠避免當數據點與超平面采樣點接近時,通過點密集程度刻畫超平面[5，7]所產生的視覺混亂。

3.2.2基于PR-SVMVis多維特征模型可視化

(11)

式中：xmin、ymin、xmax和ymax分別表示未經縮放前x和y的最小值和最大值。

經t-SNE二維降維的點(xi,yi)通過式(11)可縮放表示為(xI,yI)。

在可視化模型中,“■”代表正類,“●”代表負類,深灰色平面表示超平面。

Robot-Navigation數據集有24個特征,故將t-SNE二維降維后的兩個維度縮放至[0,2 400]。圖5和圖6展示了基于Robot-Navigation訓練數據的分類情況,ACCtrain=1。圖7和圖8展示了測試數據的表現,ACCtest=0.921,圖中可以清晰地看到,有一些數據點被SVM分類器誤分了。計算t-SNE降維后的數據與點重構轉換后的數據之間的KL散度,KLtrain(2→3)=3.45×10-6,KLtest(2→3)=3.15×10-6,可認為點重構沒有破壞t-SNE降維后的數據分布,即重構的數據依然保持了數據在高維空間相似的分布結構。由于PR-SVMVis策略增加的維度是點到超平面距離d,因此,在可視化模型中,數據點在超平面哪一側、距超平面大小與超平面方程計算的結果是完全一致的。

圖5 Robot-Navigation SVM模型展示(高斯核,σ=0.5)

圖6 Robot-Navigation SVM模型展示(高斯核,σ=0.5,經旋轉)

圖7 測試集表現(高斯核,σ=0.5)

圖8 測試集分類器誤分情況(高斯核,σ=0.5)

PR-SVMVis策略能夠在直觀上反映多維數據點在高維空間中的分布結構以及數據點與超平面之間的距離關系,有利于增強用戶對多維SVM模型分類結果的理解,提升分類結果的可信力度。

4 結 語

本文提出基于非線性核的SVM模型可視化策略在一定程度上解決了三維、多維空間非線性核超平面難以直觀刻畫的問題。然而,網格采樣點、基函數、影響域半徑對曲面擬合效果有較大的影響,故使用基于MLS-SVMVis可視化策略需要根據數據集的不同設定合適的參數值。下一步工作準備將基于MLS-SVMVis可視化策略與交互設計相結合,通過交互操作來選擇合適的參數和可視化方案。