郭 明 朱 焱

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

0 引 言

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

大數(shù)據(jù)可視化技術是當前的研究熱點。基于模型可視化的研究有助于理解模型的內(nèi)在分析原理,并增強結(jié)果的可信度。目前基于模型可視化的研究多針對決策樹或神經(jīng)網(wǎng)絡[1]。SVM可視化的研究主要分為以下兩個方面：

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

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

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

1 相關工作

1.1 支持向量機(SVM)

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

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

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

WTX+b=0

(1)

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

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

WTX+b=1

(2)

WTX+b=-1

(3)

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

(4)

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

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

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

1.2 移動最小二乘法

移動最小二乘法[9]是在最小二乘法基礎上引入了基函數(shù)和緊支撐權(quán)函數(shù)。

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

(5)

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

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

加入緊支撐權(quán)函數(shù),計算所有待擬合數(shù)據(jù)點的誤差加權(quán)平方和有：

(6)

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

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

1.3 t-SNE降維

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

(7)

(8)

式中：pij表示以xi為中心,xj到xi的鄰近概率；qij表示以yi為中心,yj到y(tǒng)i的鄰近概率。

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

(9)

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

(10)

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

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

2 可視化設計策略

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

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

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

算法1MLS-SVMVis(D)

輸入：三維特征數(shù)據(jù)集D。

輸出：SVM可視化模型。

Begin:

1. 對數(shù)據(jù)集進行訓練,構(gòu)建超平面方程；

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

3. 設定網(wǎng)格采樣參數(shù),進行網(wǎng)格采樣；

4. 計算采樣點到超平面的距離d,統(tǒng)計d等于0的點的個數(shù)；

5. ifcount(d==0)

返回到步驟3,更新采樣參數(shù)；

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

7. 網(wǎng)格化擬合區(qū)域,設置基函數(shù)P和影響域半徑R；

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

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

ifmiss>error

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

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

11. 輸出帶有數(shù)據(jù)點的三維SVM可視化模型；

End

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

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

算法2PR-SVMVis(D)

輸入：多維特征數(shù)據(jù)集D。

輸出：SVM可視化模型。

Begin:

1. 對數(shù)據(jù)集進行訓練,構(gòu)建超平面方程；

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

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

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

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

6. 輸出帶有數(shù)據(jù)點的SVM可視化模型；

End

3 實 驗

3.1 數(shù)據(jù)集與預處理

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

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

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

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

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

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

3.2 驗證實驗與結(jié)果分析

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

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

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

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

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

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

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

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

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

(11)

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

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

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

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

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

圖6 Robot-Navigation SVM模型展示(高斯核,σ=0.5,經(jīng)旋轉(zhuǎn))

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

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

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

4 結(jié) 語

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