李 凱，李潔

（河北大學(xué)網(wǎng)絡(luò)空間安全與計(jì)算機(jī)學(xué)院，河北保定 071002）

0 引言

支持向量機(jī)（Support Vector Machine，SVM）是由Vapnik等［1］提出的一種機(jī)器學(xué)習(xí)方法，其目標(biāo)是根據(jù)輸入樣本集求解一個(gè)二次規(guī)劃問(wèn)題，從而獲得所需的最優(yōu)分類(lèi)超平面。為了解決SVM 計(jì)算復(fù)雜度高的問(wèn)題，Jayadeva 等［2］提出了孿生支持向量機(jī)（Twin Support Vector Machine，TWSVM），該方法通過(guò)求解兩個(gè)較小的二次規(guī)劃問(wèn)題，確定兩個(gè)非平行的超平面，使得每個(gè)超平面更接近其中的一個(gè)類(lèi)而遠(yuǎn)離另一個(gè)類(lèi)，該模型較好地提高了計(jì)算速度。此后，在TWSVM 的基礎(chǔ)上，研究者們提出了多種孿生支持向量機(jī)算法［3-4］，如基于pinball 損失的孿生支持向量機(jī)［5-7］、模糊孿生支持向量機(jī)［8］和結(jié)構(gòu)型孿生支持向量機(jī)［9-10］等，并將其應(yīng)用于實(shí)際問(wèn)題［11］。

可以看到，上述算法均適用于二分類(lèi)問(wèn)題，然而，在實(shí)際應(yīng)用中多分類(lèi)問(wèn)題更加常見(jiàn)，因此對(duì)多分類(lèi)問(wèn)題的研究是十分必要的。目前，人們基于孿生支持向量機(jī)對(duì)多分類(lèi)問(wèn)題［12］進(jìn)行了研究，主要分為三種類(lèi)型：

1）第一類(lèi)是基于二分類(lèi)的多分類(lèi)策略。該策略主要包括一對(duì)一和一對(duì)多兩種：一對(duì)一策略是在任意兩類(lèi)之間構(gòu)造一個(gè)二分類(lèi)器，對(duì)待分類(lèi)樣本使用投票法進(jìn)行分類(lèi)。例如Shao等［13］提出了一對(duì)一孿生支持向量機(jī)（One-Versus-One TWSVM，OVO-TWSVM）。該方法的缺點(diǎn)是當(dāng)數(shù)據(jù)類(lèi)別較多時(shí)，需構(gòu)造的分類(lèi)器數(shù)量過(guò)多，且存在數(shù)據(jù)不可分區(qū)域；而一對(duì)多策略［14］是在k個(gè)類(lèi)中任意挑選一類(lèi)作為正類(lèi)，其余k-1類(lèi)作為負(fù)類(lèi)，并構(gòu)造k個(gè)二分類(lèi)器進(jìn)行分類(lèi)，缺點(diǎn)是每個(gè)分類(lèi)器的訓(xùn)練集高度不平衡；有向無(wú)環(huán)圖支持向量機(jī)（Directed Acyclic Graph TWSVM，DAG-TWSVM）［15］可視為OVOTWSVM方法的一種變形，其訓(xùn)練過(guò)程與OVO-TWSVM 相似，在測(cè)試時(shí)使用有向無(wú)環(huán)圖對(duì)分類(lèi)樣本進(jìn)行分類(lèi)，有效減少了投票輪數(shù)，然而當(dāng)數(shù)據(jù)類(lèi)別較多時(shí)仍需構(gòu)造大量的分類(lèi)器，且在判決過(guò)程中存在誤差累積的現(xiàn)象。Don 等［16］提出了一種分而治之支持向量機(jī)（Divide and Conquer SVM，DCSVM），它將OVO-TWSVM 方法的簡(jiǎn)潔性與DAG-TWSVM 的分類(lèi)速度相結(jié)合，克服了分類(lèi)器過(guò)多的缺點(diǎn)，但分類(lèi)過(guò)程仍存在誤差累積問(wèn)題。除此之外，研究人員在這些算法的基礎(chǔ)上提出了多種改進(jìn)算法，Liu 等［17］提出了一種基于OVO 策略和SVM 算法的改進(jìn)多分類(lèi)算法，使用K近鄰法為分類(lèi)器設(shè)置權(quán)重，提高分類(lèi)準(zhǔn)確率；Yang 等［18］將多重遞歸投影孿生支持向量機(jī)、最小二乘法應(yīng)用到OVA-TWSVM（One-Versus-All TWSVM）算法中，提出最小二乘遞歸投影孿生支持向量機(jī)等。

2）第二類(lèi)是基于二分類(lèi)方法演變的其他解決方法，包括一對(duì)一對(duì)多孿生支持向量機(jī)Twin-KSVC（TwinK-class Support Vector Classification）［19］和多生支持向量機(jī)（Multiple Birth SVM，MBSVM）［20］。一對(duì)一對(duì)多孿生支持向量機(jī)較好地解決了OVO-TWSVM 中存在的隨機(jī)投票現(xiàn)象，但其子分類(lèi)器復(fù)雜，時(shí)間復(fù)雜度過(guò)高；而多生支持向量機(jī)極大減少了約束條件，使得時(shí)間復(fù)雜度低，計(jì)算速度顯著提高，但該算法容易陷入局部最優(yōu)；之后，研究人員針對(duì)這些方法提出了許多改進(jìn)算法［21-24］。

3）第三類(lèi)是直接構(gòu)造解決多分類(lèi)問(wèn)題的方法。該方法針對(duì)所有樣本直接構(gòu)造一個(gè)單一優(yōu)化問(wèn)題，并確定所有類(lèi)的決策函數(shù)，該方法有效解決了其他方法中存在不可分區(qū)域等問(wèn)題。例如：Guo 等［25］為解決SVM 不適用于未標(biāo)記的數(shù)據(jù)的問(wèn)題，提出了一種基于主動(dòng)學(xué)習(xí)和SVM 多分類(lèi)模型用于處理未標(biāo)記的數(shù)據(jù)。Weston 等［26］提出了多分類(lèi)支持向量機(jī)（Multi-Class SVM，MSVM），但其存在二次規(guī)劃問(wèn)題過(guò)大與計(jì)算時(shí)間長(zhǎng)等缺陷。Crammer 等［27］通過(guò)引入克羅內(nèi)克函數(shù)，使得約束更加緊湊，但其計(jì)算量依然較大。Wang等［28］通過(guò)引入新的寬松邊界條件，提出了簡(jiǎn)化的多分類(lèi)支持向量機(jī)（Simplified Multi-Class SVM，SimMSVM）算法，較好地提高了計(jì)算速度，如圖1（a）所示。然而，由于該方法使用鉸鏈損失，很容易導(dǎo)致算法具有噪聲敏感性和重采樣不穩(wěn)定性；此外，在一些應(yīng)用中，例如在推薦系統(tǒng)中，較新產(chǎn)品的重要性程度應(yīng)高于舊產(chǎn)品，同樣地，不同樣本對(duì)支持向量機(jī)的作用可能不同；最后，樣本間存在潛在的結(jié)構(gòu)信息，這些信息可能包含一些重要的先驗(yàn)知識(shí)來(lái)訓(xùn)練分類(lèi)器，該方法未考慮到這幾點(diǎn)，使得該方法對(duì)噪聲或異常點(diǎn)仍具有較大的敏感性和較低的泛化性能，分類(lèi)結(jié)果較差。

圖1 兩種算法的分類(lèi)示意圖Fig.1 Classification schematic diagram of two algorithms

為了進(jìn)一步解決上述問(wèn)題，將pinball損失函數(shù)、樣本模糊隸屬度和樣本結(jié)構(gòu)信息等引入到SimMSVM 算法中，本文提出了一種基于pinball 損失的結(jié)構(gòu)模糊多分類(lèi)支持向量機(jī)算法Pin-SFSimMSVM。如圖1（b）所示，該方法使用pinball 損失函數(shù)對(duì)分類(lèi)錯(cuò)誤的樣本進(jìn)行懲罰，同時(shí)對(duì)分類(lèi)正確的樣本給出一個(gè)額外懲罰，該函數(shù)使用分位數(shù)距離，使其對(duì)噪聲不敏感，數(shù)據(jù)重采樣更穩(wěn)定；為樣本添加模糊隸屬度，使得屬于一個(gè)類(lèi)的樣本在分類(lèi)時(shí)扮演更重要的角色；最后，將數(shù)據(jù)的先驗(yàn)結(jié)構(gòu)信息應(yīng)用到算法中，進(jìn)一步提高了支持向量機(jī)的分類(lèi)性能。

1 相關(guān)工作

對(duì)SimMSVM 算法的數(shù)學(xué)模型、算法中用到的鉸鏈損失函數(shù)以及本文所提出的Pin-SFSimMSVM 算法所用到的pinball損失函數(shù)進(jìn)行介紹。

1.1 SimMSVM

為了解決多分類(lèi)問(wèn)題，Wang等［28］提出了一種新的支持向量機(jī)算法，通過(guò)最大化每類(lèi)到其余類(lèi)的余量來(lái)區(qū)分出所有類(lèi)，并且可一次性確定所有類(lèi)的決策函數(shù)，解決了存在不可分區(qū)域的問(wèn)題，且和同類(lèi)方法相比在速度上也有較大的提升。給定l個(gè)樣本的k類(lèi)數(shù)據(jù)集T={(x1，y1)，(x2，y2)，…，(xl，yl)}，其中xi∈Rn為訓(xùn)練數(shù)據(jù)樣本，yi∈{1，2，…，k}為類(lèi)標(biāo)簽，其優(yōu)化問(wèn)題如下：

其中：C為懲罰參數(shù)；wm為第m類(lèi)的分類(lèi)決策向量；H為適當(dāng)維度的特征空間。通過(guò)求解式（1）可以得到所有k個(gè)類(lèi)的分類(lèi)決策向量。對(duì)于待分類(lèi)樣本x，利用式（2）確定其類(lèi)別：

1.2 損失函數(shù)

對(duì)于支持向量機(jī)與孿生支持向量機(jī)以及相關(guān)算法，在建立相應(yīng)模型時(shí)，主要使用了鉸鏈損失函數(shù)，即：

Lhinge(u)=max{0，u}

在算法中，常見(jiàn)的使用形式為：

Lhinge(x，y，f(x))=max(0，1-yf(x))

其中：y和f（x）分別為理想值和預(yù)測(cè)值。由于鉸鏈損失函數(shù)使用了最短距離，因此，它易導(dǎo)致噪聲敏感性和重采樣的不穩(wěn)定性。為此，人們對(duì)不同損失函數(shù)的SVM 及TWSVM 進(jìn)行研究，其中pinball 損失函數(shù)研究較為廣泛。pinball 損失函數(shù)定義如下：

在本文中，使用的pinball損失函數(shù)為：

其中τ∈［0，1］?？梢钥吹?，pinball損失函數(shù)不僅對(duì)分類(lèi)錯(cuò)誤的樣本進(jìn)行懲罰，而且對(duì)分類(lèi)正確的樣本給出一個(gè)額外懲罰；另外，由于該函數(shù)使用了分位數(shù)距離，因此，它對(duì)噪聲不敏感，數(shù)據(jù)重采樣更穩(wěn)定，且不會(huì)增加計(jì)算成本。當(dāng)pinball 損失的參數(shù)趨于零時(shí)，損失函數(shù)成為鉸鏈損失。

2 結(jié)構(gòu)模糊多分類(lèi)支持向量機(jī)

在本章中，將pinball損失函數(shù)、樣本權(quán)重和樣本的結(jié)構(gòu)信息引入到SimMSVM 中，提出了一種新的多分類(lèi)支持向量機(jī)算法Pin-SFSimMSVM。使用pinball 損失函數(shù)能較好地解決鉸鏈損失函數(shù)所帶來(lái)的噪聲敏感和重采樣不穩(wěn)定性等問(wèn)題，通過(guò)引入模糊隸屬度對(duì)樣本賦予不同權(quán)重，并充分挖掘樣本中潛在的結(jié)構(gòu)信息，數(shù)據(jù)中可能包含用于訓(xùn)練分類(lèi)器的重要先驗(yàn)知識(shí)，進(jìn)一步提高了算法的噪聲不敏感性和算法的性能。該方法不僅保留了SimMSVM 中一次性解決所有樣本的分類(lèi)問(wèn)題、避免產(chǎn)生數(shù)據(jù)不可分區(qū)域和計(jì)算速度快等優(yōu)點(diǎn)，且提高了算法的抗噪性和分類(lèi)準(zhǔn)確率。下面將從線(xiàn)性和非線(xiàn)性?xún)煞N情況對(duì)算法進(jìn)行介紹。

2.1 線(xiàn)性情況

給定一個(gè)含有l(wèi)個(gè)樣本的k類(lèi)訓(xùn)練數(shù)據(jù)集T={(xi，yi，Si)|i=1，2，…，l}，其中xi∈Rn為訓(xùn)練樣本，yi∈{1，2，…，k}為樣本類(lèi)標(biāo)簽。將pinball 損失函數(shù)、樣本模糊隸屬度和樣本結(jié)構(gòu)信息引入到SimMSVM 中，從而得到線(xiàn)性Pin-SFSimMSVM的優(yōu)化問(wèn)題：

其中：wm為第m類(lèi)樣本的分類(lèi)決策向量；C1和C2分別是平衡因子且C1>0，C2>0；Si為樣本模糊隸屬度；ξi為松弛變量；Σm為第m類(lèi)樣本的結(jié)構(gòu)信息；τ∈［0，1］為pinball損失參數(shù)。為了解決式（3），構(gòu)造拉格朗日函數(shù)如下：

其中α和β是由拉格朗日乘子構(gòu)成的向量，且α≥0，β≥0。

將拉格朗日函數(shù)對(duì)變量求偏導(dǎo)并令其等于0，得：

由式（7）和式（9）可得約束條件為：

將式（6）和式（8）代入到式（4）中，從而得到式（3）的對(duì)偶問(wèn)題如下：

其中：γ=(α-β)；S為由樣本模糊隸屬度構(gòu)成的向量；G為一個(gè)l×l維的矩陣。G的矩陣元素為：

其中I為適當(dāng)維度的單位矩陣。

通過(guò)求解對(duì)偶問(wèn)題式（11），從而得到γ，進(jìn)一步可以求得wm，即每類(lèi)樣本的分類(lèi)決策向量。因此，獲得的決策函數(shù)為：

當(dāng)對(duì)待分類(lèi)樣本x進(jìn)行分類(lèi)時(shí)，其最終所屬類(lèi)別的求解方法如下：

2.2 非線(xiàn)性情況

在這一節(jié)中，將線(xiàn)性情況推廣到非線(xiàn)性情況中。通過(guò)核矩陣將輸入樣本映射到高維特征空間，使其在高維空間中也能實(shí)現(xiàn)線(xiàn)性可分。設(shè)φ是一個(gè)從輸入空間Rn到特征空間Z的映射，則非線(xiàn)性Pin-SFSimMSVM算法的優(yōu)化問(wèn)題為：

其中：um為第m類(lèi)樣本的分類(lèi)決策向量：C3、C4是平衡因子且C3>0，C4>0；ξi、Si和Σm分別為松弛變量、樣本模糊隸屬度和第m類(lèi)樣本的結(jié)構(gòu)信息，τ∈［0，1］為pinball損失參數(shù)。其拉格朗日函數(shù)為：

其中α≥0，β≥0為拉格朗日乘子。

將式（16）對(duì)變量求偏導(dǎo)并令其等于0得：

由式（19）和式（21）可得約束條件為：

將式（18）、（20）代入式（16），從而得到式（15）的對(duì)偶問(wèn)題為：

其中：γ=(α-β)；S為由樣本模糊隸屬度構(gòu)成的向量；G為一個(gè)l×l維的矩陣。G的元素為：

其中I為適當(dāng)維度的單位矩陣。

通過(guò)對(duì)其對(duì)偶問(wèn)題進(jìn)行求解，求得um的值，進(jìn)而得到如下決策函數(shù)：

其中K(xi，x)=φ(xi)Tφ(x)。

對(duì)于待分類(lèi)樣本x，利用決策函數(shù)可確定樣本x所屬類(lèi)別，即：

2.3 時(shí)間復(fù)雜度分析

對(duì)Pin-SFSimMSVM 算法的時(shí)間復(fù)雜度進(jìn)行分析，該方法針對(duì)所有樣本直接構(gòu)造一個(gè)單一優(yōu)化問(wèn)題，一次性確定所有類(lèi)的決策函數(shù)，并采用了較為簡(jiǎn)單的損失函數(shù)，因此時(shí)間復(fù)雜度為O(l3)，其中l(wèi)為問(wèn)題的規(guī)模。

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

首先，對(duì)樣本模糊隸屬度以及樣本結(jié)構(gòu)信息的獲取方法進(jìn)行介紹，實(shí)驗(yàn)中采用類(lèi)中心距離法、模糊C 均值法和S 型方法獲取樣本模糊隸屬度，并分別使用基于距離和基于聚類(lèi)的方法獲取樣本結(jié)構(gòu)信息。接著，對(duì)提出的Pin-SFSimMSVM 算法的性能進(jìn)行評(píng)估，從線(xiàn)性和非線(xiàn)性?xún)煞N情況對(duì)算法進(jìn)行實(shí)驗(yàn)比較。將SimMSVM［28］、OVO-TWSVM［13］、OVA-TWSVM［14］、Twin-KSVC［19］以及MBSVM［20］等多種多分類(lèi)算法與所提出的Pin-SFSimMSVM 算法在UCI 數(shù)據(jù)庫(kù)［29］中的8 個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集和4 個(gè)人工生成的數(shù)據(jù)集上分別進(jìn)行實(shí)驗(yàn)。此外，在標(biāo)準(zhǔn)數(shù)據(jù)集中分別加入5%和10%的特征噪聲并比較其準(zhǔn)確率，以檢驗(yàn)算法對(duì)噪聲的敏感性。結(jié)果表明，Pin-SFSimMSVM 算法在標(biāo)準(zhǔn)數(shù)據(jù)集和人工生成的數(shù)據(jù)集中都有很好的抗噪性。

3.1 模糊隸屬度

為了研究不同樣本賦予不同權(quán)重時(shí)對(duì)分類(lèi)結(jié)果的影響，本文將對(duì)使用類(lèi)中心距離法、模糊C 均值法和S 型三種不同方法賦予權(quán)重值時(shí)的測(cè)試結(jié)果進(jìn)行比較。

1）類(lèi)中心距離法。該方法根據(jù)每類(lèi)中的樣本距離該類(lèi)中心的距離遠(yuǎn)近來(lái)定義其權(quán)重，距離類(lèi)中心點(diǎn)越近的樣本權(quán)重越大，距離越遠(yuǎn)權(quán)重越小。計(jì)算k類(lèi)中的任意一類(lèi)中的樣本權(quán)重Si的方法如下：

其中：di表示該樣本到該類(lèi)類(lèi)中心的距離；ri表示該類(lèi)的半徑，即距離類(lèi)中心最遠(yuǎn)的樣本到中心的距離。

2）模糊C 均值法。該方法將每類(lèi)樣本分為C個(gè)簇并使每個(gè)樣本到C個(gè)聚類(lèi)中心的距離最小，即為每一個(gè)樣本賦予一個(gè)權(quán)重，該權(quán)重的值表示樣本隸屬于某一簇的重要程度。任意一類(lèi)的優(yōu)化問(wèn)題如下：

其中：vj為聚類(lèi)中心；sij為第i個(gè)樣本在第j個(gè)簇中的權(quán)重；V和S分別由vj和sij組成；m為模糊加權(quán)指數(shù)。通過(guò)拉格朗日求解該優(yōu)化問(wèn)題得到vj和sij的計(jì)算式，再通過(guò)求解公式迭代更新矩陣S和集合V：

3）S 型方法。與類(lèi)中心距離法相似，根據(jù)樣本點(diǎn)距離該類(lèi)中心的距離遠(yuǎn)近來(lái)確定權(quán)重，不同的是，該方法將類(lèi)中心距離法中的線(xiàn)性函數(shù)用如下非線(xiàn)性函數(shù)替換：

其中：a、b、n均為定義好的參數(shù)并滿(mǎn)足b=(a+n)/2，且當(dāng)di=b時(shí)，Si=0.5。

3.2 結(jié)構(gòu)信息

同樣在算法中加入樣本的結(jié)構(gòu)信息可以更好地利用數(shù)據(jù)樣本中潛在的分布信息，本文主要使用以下兩種方法來(lái)獲取結(jié)構(gòu)細(xì)信息。

1）類(lèi)內(nèi)離散度法求結(jié)構(gòu)信息：用于描述每個(gè)類(lèi)內(nèi)部的結(jié)構(gòu)信息。設(shè)μm為第m類(lèi)樣本的均值向量，nm表示第m類(lèi)樣本的個(gè)數(shù)，則結(jié)構(gòu)信息可表示為：

2）基于聚類(lèi)方法求結(jié)構(gòu)信息：該方法通過(guò)對(duì)每類(lèi)樣本進(jìn)行聚類(lèi)，將其劃分成不同的簇，計(jì)算出每個(gè)簇的聚類(lèi)信息再求和得到該類(lèi)的聚類(lèi)信息。本文中主要使用到的聚類(lèi)技術(shù)有模糊C 均值聚類(lèi)、層次聚類(lèi)和C 均值聚類(lèi)。假設(shè)將其中第m類(lèi)樣本聚類(lèi)成c個(gè)簇，則第i個(gè)聚類(lèi)簇和第m類(lèi)的結(jié)構(gòu)信息可分別表示為：

3.3 實(shí)驗(yàn)數(shù)據(jù)集和分類(lèi)性能評(píng)價(jià)指標(biāo)

實(shí)驗(yàn)選取Ripley 綜合數(shù)據(jù)集［30］、人工生成的3 個(gè)數(shù)據(jù)集和UCI 標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)中的8 個(gè)數(shù)據(jù)集對(duì)Pin-SFSimMSVM 算法進(jìn)行驗(yàn)證。其中Ripley 為二類(lèi)數(shù)據(jù)集，共包含250 個(gè)訓(xùn)練樣本和1000個(gè)測(cè)試樣本，人工數(shù)據(jù)集中的數(shù)據(jù)為正態(tài)分布下隨機(jī)生成得到，將其分別命名為Data1、Data2 和Data3。其中，Data1每個(gè)類(lèi)數(shù)據(jù)按照均值[-5，5]、[5，5]、[-5，-5]和[5，-5]，方差［0.40；03］生成。Data2 中共三個(gè)類(lèi)：第一類(lèi)包含3 個(gè)簇，每個(gè)聚類(lèi)簇按照均值[2，-2]、［0，2］和[-4，5]，方差［0.70；00.7］生成；第二類(lèi)包含2 個(gè)簇，每個(gè)聚類(lèi)簇按照均值[-5，1]和[-1，0]，方差［0.40；03］生成；第三類(lèi)包含3 個(gè)簇，每個(gè)聚類(lèi)簇按照均值[-5，-4]、[-2，-4]和[1，-4]，方差［1.50；00.7］生成。Data3每個(gè)類(lèi)數(shù)據(jù)則按照均值[-4，4，2]、［4，4，2］、[-4，-4，2]、[4，-4，2]和［0，0，2］，方差［200；020；003］生成。數(shù)據(jù)集中的樣本數(shù)、特征個(gè)數(shù)、分類(lèi)數(shù)目和每類(lèi)樣本所包含的簇?cái)?shù)如表1所示。

表1 人工數(shù)據(jù)集特征Tab.1 Synthetic dataset characteristics

選用UCI 數(shù)據(jù)庫(kù)中的8 個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集對(duì)算法進(jìn)行驗(yàn)證，它們分別為Iris、Zoo、Glass、Seeds、Ecoli、Balance、Soybean 和CMC，表2中描述了數(shù)據(jù)集的詳細(xì)特征。

表2 UCI數(shù)據(jù)集特征Tab.2 UCI dataset characteristics

另外，在分類(lèi)問(wèn)題中，分類(lèi)器的性能評(píng)價(jià)指標(biāo)也是選擇最優(yōu)分類(lèi)器的重要依據(jù)。本文中選取的評(píng)價(jià)指標(biāo)為分類(lèi)準(zhǔn)確率和標(biāo)準(zhǔn)差，準(zhǔn)確率為分類(lèi)正確的樣本與總樣本的比，標(biāo)準(zhǔn)差則是算法在數(shù)據(jù)集上進(jìn)行10 次分類(lèi)結(jié)果平均值方差的平方根。

3.4 Pin-SFSimMSVM算法實(shí)驗(yàn)

將所提出的算法Pin-SFSimMSVM在人工數(shù)據(jù)集和UCI標(biāo)準(zhǔn)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，并與SimMSVM、OVO-TWSVM、OVATWSVM、Twin-KSVC 以及MBSVM 這幾種常用的多分類(lèi)算法進(jìn)行對(duì)比。下面介紹實(shí)驗(yàn)中用到的參數(shù)及參數(shù)的選擇。懲罰參數(shù)C1和C2為平衡因子且大于0，C1值較大時(shí)對(duì)誤分類(lèi)的懲罰增大，C2值較大時(shí)則結(jié)構(gòu)信息所起作用增大；反之亦然。在非線(xiàn)性情況下，使用高斯核函數(shù)k(x，y)=作為核函數(shù)。當(dāng)pinball 損失參數(shù)τ為0 時(shí)，損失函數(shù)為鉸鏈損失，因此參數(shù)τ在（0，1］取值。為使實(shí)驗(yàn)結(jié)果達(dá)到最優(yōu)，C1，C2和p在2-4～210進(jìn)行取值，首先取80%的樣本為訓(xùn)練數(shù)據(jù)集，使用網(wǎng)格搜索和十重交叉驗(yàn)證的方法對(duì)4 個(gè)參數(shù)進(jìn)行篩選，得到實(shí)驗(yàn)結(jié)果最優(yōu)時(shí)的各項(xiàng)參數(shù)值；并使用得到的最優(yōu)參數(shù)對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行訓(xùn)練得到?jīng)Q策函數(shù)，對(duì)測(cè)試樣本進(jìn)行分類(lèi)得到最終的分類(lèi)準(zhǔn)確率。實(shí)驗(yàn)中對(duì)每種算法均采用10 次測(cè)試的平均值和標(biāo)準(zhǔn)差作為最終的評(píng)價(jià)指標(biāo)。

為驗(yàn)證所提出算法的分類(lèi)性能，在表3和表4中分別給出了線(xiàn)性及非線(xiàn)性情況下，已有的5 種用于多分類(lèi)的算法和本文所提出的Pin-SFSimMSVM 算法在幾個(gè)人工數(shù)據(jù)集上的分類(lèi)準(zhǔn)確率和標(biāo)準(zhǔn)差。其中Pin-SFSimMSVM算法使用模糊C均值法獲取樣本模糊隸屬度，并分別使用層次聚類(lèi)和C 均值聚類(lèi)方法獲取樣本的結(jié)構(gòu)信息。

根據(jù)表3和表4可以看出，Pin-SFSimMSVM算法在線(xiàn)性和非線(xiàn)性情況中均表現(xiàn)出比SimMSVM 算法更好的性能，且在Ripley、Data1和Data2這3個(gè)數(shù)據(jù)集中均優(yōu)于其余幾種多分類(lèi)算法。SimMSVM 和Pin-SFSimMSVM 這兩種算法對(duì)Ripley 數(shù)據(jù)集和Data1數(shù)據(jù)集的一次分類(lèi)結(jié)果如圖2～3所示，在圖中對(duì)分類(lèi)錯(cuò)誤的樣本點(diǎn)進(jìn)行了標(biāo)記。

圖2 Ripley數(shù)據(jù)集及使用不同算法在其上的分類(lèi)結(jié)果Fig.2 Ripley dataset and classification results of different algorithms on it

表3 線(xiàn)性情況下不同算法準(zhǔn)確率和標(biāo)準(zhǔn)差對(duì)比 單位：%Tab.3 Comparison of accuracy and standard deviation of different algorithms in linear condition unit：%

表4 非線(xiàn)性情況下不同算法準(zhǔn)確率和標(biāo)準(zhǔn)差比較 單位：%Tab.4 Comparison of accuracy and standard deviation of algorithms in nonlinear condition unit：%

在UCI 數(shù)據(jù)集上的部分實(shí)驗(yàn)結(jié)果如表5～6 所示，對(duì)每個(gè)數(shù)據(jù)集中實(shí)驗(yàn)結(jié)果最好的算法進(jìn)行了標(biāo)記，其中Pin-SimMSVM 算法為僅使用pinball 損失替換原算法中的鉸鏈損失而不作其他改變得到的算法，和原算法進(jìn)行對(duì)比可以更好地觀察不同損失函數(shù)對(duì)算法分類(lèi)結(jié)果的影響?？梢钥闯?，大多數(shù)數(shù)據(jù)集在使用pinball 損失和模糊隸屬度后，準(zhǔn)確率已有了一定的提升，為了研究pinball 損失參數(shù)τ 的變化對(duì)分類(lèi)結(jié)果的影響，使用非線(xiàn)性情況下的Pin-SimMSVM 算法對(duì)其進(jìn)行測(cè)試，在圖4 中給出了在UCI 數(shù)據(jù)集上Pin-SimMSVM 算法的精度隨pinball 損失參數(shù)τ 變化的規(guī)律，可以看出，隨著τ 值的變化，數(shù)據(jù)集的準(zhǔn)確率十分穩(wěn)定，表明了Pin-SimMSVM 算法的性能是穩(wěn)定的。

圖4 UCI數(shù)據(jù)集上Pin-SimMSVM算法的精度隨τ值變化曲線(xiàn)Fig.4 Accuracy curve of Pin-SimMSVM algorithm varying with τ on UCI datasets

表5 不同算法求取模糊隸屬度在UCI數(shù)據(jù)集上的準(zhǔn)確率和標(biāo)準(zhǔn)差對(duì)比（線(xiàn)性） 單位：%Tab.5 Comparison of accuracy and standard deviation of different algorithms in solving fuzzy membership degree on UCI datasets（linear）unit：%

表6 不同算法求取模糊隸屬度在UCI數(shù)據(jù)集上的準(zhǔn)確率和標(biāo)準(zhǔn)差對(duì)比（非線(xiàn)性） 單位：%Tab.6 Comparison of accuracy and standard deviation of different algorithms in solving fuzzy membership degree on UCI datasets（nonlinear）unit：%

圖3 Data1數(shù)據(jù)集及使用不同算法在其上的分類(lèi)結(jié)果Fig.3 Data1 dataset and classification results of different algorithms on it

為驗(yàn)證不同獲取樣本模糊隸屬度的方法對(duì)實(shí)驗(yàn)結(jié)果的影響，使用在Pin-SimMSVM 算法的基礎(chǔ)上引入樣本模糊隸屬度得到的Pin-FSimMSVM 算法進(jìn)行實(shí)驗(yàn)，分別使用類(lèi)中心距離、模糊C 均值和S型三種方法獲取樣本模糊隸屬度，根據(jù)表5～6的實(shí)驗(yàn)結(jié)果可以看出，使用模糊C 均值方法獲取模糊隸屬度的算法在大部分?jǐn)?shù)據(jù)集中具有較好的性能：線(xiàn)性情況下在Ecoli、Balance和CMC三個(gè)數(shù)據(jù)集中略低于其他獲取模糊隸屬度的方法，但相較于SimMSVM算法依然具有優(yōu)勢(shì)；非線(xiàn)性情況下，模糊C均值方法和S型方法均具有較好的性能。因此，在后續(xù)實(shí)驗(yàn)中均選取模糊C均值方法獲取樣本模糊隸屬度。

除此之外，針對(duì)選取的UCI 數(shù)據(jù)集，表7～8 中給出了線(xiàn)性及非線(xiàn)性情況下，使用四種不同獲取樣本結(jié)構(gòu)信息的算法準(zhǔn)確率，根據(jù)結(jié)果可知，與基于距離的方法比較，基于聚類(lèi)的方法具有一定的優(yōu)勢(shì)，特別是層次聚類(lèi)其優(yōu)勢(shì)較為明顯。

表7 不同算法求取結(jié)構(gòu)信息在UCI數(shù)據(jù)集上的準(zhǔn)確率和標(biāo)準(zhǔn)差對(duì)比（線(xiàn)性） 單位：%Tab.7 Comparison of accuracy and standard deviation of different algorithms in solving structural information on UCI datasets（linear）unit：%

表8 不同算法求取結(jié)構(gòu)信息在UCI數(shù)據(jù)集上的準(zhǔn)確率和標(biāo)準(zhǔn)差對(duì)比（非線(xiàn)性） 單位：%Tab.8 Comparison of accuracy and standard deviation of different algorithms in solving structural information on UCI datasets（nonlinear）unit：%

為了驗(yàn)證所提出的Pin-SFSimMSVM 算法的有效性，在標(biāo)準(zhǔn)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)并選取SimMSVM、OVO-TWSVM、OVATWSVM、Twin-KSVC 與MBSVM 算法進(jìn)行比較；同時(shí)，為了檢驗(yàn)算法的抗噪性能，在8 個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集中分別加入了5%和10%的噪聲數(shù)據(jù)進(jìn)行對(duì)比實(shí)驗(yàn)，噪聲數(shù)據(jù)服從均值為0、方差為1 的高斯分布，實(shí)驗(yàn)結(jié)果見(jiàn)表9，其中r表示所含噪聲比例，結(jié)構(gòu)信息的獲取分別使用層次聚類(lèi)和C均值聚類(lèi)方法。

表9 不同算法在UCI數(shù)據(jù)集上添加噪聲的準(zhǔn)確率和標(biāo)準(zhǔn)差對(duì)比（非線(xiàn)性） 單位：%Tab.9 Comparison of accuracy and standard deviation of different algorithms on UCI datasets with adding noise（nonlinear） unit：%

實(shí)驗(yàn)結(jié)果表明，在選取的8 個(gè)UCI 標(biāo)準(zhǔn)數(shù)據(jù)集中，Pin-SFSimMSVM 算法在7 個(gè)數(shù)據(jù)集中均表現(xiàn)出優(yōu)異的性能，尤其是在加入噪聲數(shù)據(jù)后，準(zhǔn)確率均高于其他算法，而在Balance數(shù)據(jù)集中，盡管本文所提出的算法低于OVO-TWSVM 等算法，但仍?xún)?yōu)于SimMSVM 算法，且在加入噪聲后得到的實(shí)驗(yàn)結(jié)果仍有明顯提高，這也表明了所提出的算法對(duì)噪聲和重采樣數(shù)據(jù)不具有敏感性。

此外，根據(jù)表9的實(shí)驗(yàn)結(jié)果，將Pin-SFSimMSVM 算法的實(shí)驗(yàn)結(jié)果與其他五種多分類(lèi)算法的實(shí)驗(yàn)結(jié)果在8 個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集中進(jìn)行比較，如表10所示。其含義為將Pin-SFSimMSVM 算法與其他五種不同算法在UCI 標(biāo)準(zhǔn)數(shù)據(jù)集上的輸局/平局/贏局個(gè)數(shù)，例如Pin-SFSimMSVM 算法與SimMSVM 算法在沒(méi)有添加噪聲情況下相比較的結(jié)果為1/1/6，則表明所提出的算法僅1次準(zhǔn)確率低于原算法，1次準(zhǔn)確率與原算法相等，6次結(jié)果優(yōu)于原算法。

表10 Pin-SFSimMSVM算法與其他算法在UCI標(biāo)準(zhǔn)數(shù)據(jù)集上的贏局/平局/輸局對(duì)比Tab.10 Comparison of Pin-SFSimMSVM algorithm with other different algorithms for win/draw/loss on UCI standard datasets

可以發(fā)現(xiàn)，本文所提出的算法的性能僅在一個(gè)數(shù)據(jù)集上差于改進(jìn)前的SimMSVM 算法，但在噪聲數(shù)據(jù)集上優(yōu)于SimMSVM 算法，與其他算法相比，所提出的算法也具有很高的精度，表明Pin-SFSimMSVM具有更好的噪聲不敏感性。

4 結(jié)語(yǔ)

本文提出了一種新的用于多分類(lèi)的支持向量機(jī)算法Pin-SFSimMSVM，該算法在SimMSVM 的基礎(chǔ)上，基于pinball 損失函數(shù)，通過(guò)引入樣本的模糊隸屬度和結(jié)構(gòu)信息，較好地解決了多分類(lèi)方法存在不可分區(qū)域，以及對(duì)數(shù)據(jù)中的噪聲和重采樣數(shù)據(jù)敏感等問(wèn)題，并且在準(zhǔn)確率上有很大提升。通過(guò)在人工數(shù)據(jù)集和UCI 標(biāo)準(zhǔn)數(shù)據(jù)集上對(duì)SimMSVM、OVO-TWSVM、OVA-TWSVM、Twin-KSVC 以及MBSVM 等多分類(lèi)算法的對(duì)比實(shí)驗(yàn)，驗(yàn)證了所提出算法的有效性。