郭 明 朱 焱

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

0 引 言

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

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

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

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

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

1 相關(guān)工作

1.1 支持向量機(jī)(SVM)

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

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

定義1(超平面) 在支持向量機(jī)模型中,劃分正負(fù)類(lèi)樣本的決策目標(biāo)函數(shù)稱(chēng)為超平面。線性支持向量機(jī)的判別式為：

WTX+b=0

(1)

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

定義2(支持向量) 在支持向量機(jī)模型中,距離超平面最近且滿(mǎn)足一定條件的幾個(gè)訓(xùn)練樣本點(diǎn)被稱(chēng)為支持向量[8]。正類(lèi)和負(fù)類(lèi)支持向量所在的邊界可表示為：

WTX+b=1

(2)

WTX+b=-1

(3)

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

(4)

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

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

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

1.2 移動(dòng)最小二乘法

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

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

(5)

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

設(shè)影響域的半徑為d,假設(shè)對(duì)于二維問(wèn)題,待擬合的點(diǎn)為(x,y),影響域中的點(diǎn)有(xI,yI),則:

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

(6)

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

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

1.3 t-SNE降維

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

(7)

(8)

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

使用KL散度計(jì)算qij對(duì)pij的忠實(shí)度有：

(9)

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

(10)

式中：Y表示低維空間的坐標(biāo)；t表示不同迭代階段；η表示學(xué)習(xí)率；α(t)表示t階段時(shí)的動(dòng)量。

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

2 可視化設(shè)計(jì)策略

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

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

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

算法1MLS-SVMVis(D)

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

輸出：SVM可視化模型。

Begin:

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

2. 設(shè)定超平面預(yù)采樣點(diǎn)個(gè)數(shù)閾值nums；

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

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

5. ifcount(d==0)

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

6. 設(shè)定點(diǎn)的擬合偏差值閾值error；

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

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

9. for擬合超平面上每一個(gè)點(diǎn)的擬合偏差值miss

ifmiss>error

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

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

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

End

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

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

算法2PR-SVMVis(D)

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

輸出：SVM可視化模型。

Begin:

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

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

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

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

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

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

End

3 實(shí) 驗(yàn)

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

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

Iris數(shù)據(jù)集選取類(lèi)標(biāo)為“Iris-setosa”(正類(lèi))和“Iris-versicolor”(負(fù)類(lèi))共100條樣本,實(shí)驗(yàn)使用3個(gè)特征(sepal length、sepal width、petal length)。

Seeds數(shù)據(jù)集選取類(lèi)標(biāo)為“2”(正類(lèi))和“3”(負(fù)類(lèi))共140條樣本,實(shí)驗(yàn)使用Seeds數(shù)據(jù)集PCA降維后的三維特征。

Vertebral數(shù)據(jù)集選取類(lèi)標(biāo)為“SL”(正類(lèi))和“NO”(負(fù)類(lèi))共250條樣本,實(shí)驗(yàn)使用3個(gè)特征(sacral slope、pelvic radius、grade of spondylolisthesis)。

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

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

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

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

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

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

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

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

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

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

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

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

(11)

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

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

在可視化模型中,“■”代表正類(lèi),“●”代表負(fù)類(lèi),深灰色平面表示超平面。

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

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

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

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

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

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

4 結(jié) 語(yǔ)

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