雙重特征加權(quán)模糊支持向量機(jī)

邱云志，汪廷華，戴小路

（贛南師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，江西贛州 341000）

0 引言

支持向量機(jī)（Support Vector Machine，SVM）［1-2］是基于統(tǒng)計(jì)學(xué)習(xí)理論提出的一種機(jī)器學(xué)習(xí)算法，旨在尋找一個(gè)最優(yōu)分類超平面，根據(jù)有限的樣本信息在模型的學(xué)習(xí)精度和學(xué)習(xí)能力之間尋求最佳折中。針對(duì)樣本線性可分情況，通過(guò)把原始問(wèn)題轉(zhuǎn)化為凸優(yōu)化問(wèn)題求解；樣本線性不可分時(shí)則應(yīng)用了核技巧，解決了傳統(tǒng)機(jī)器學(xué)習(xí)算法的維數(shù)災(zāi)難和局部最小問(wèn)題。SVM 算法在解決小樣本、非線性、高維模式識(shí)別中表現(xiàn)出了獨(dú)特的優(yōu)勢(shì)，廣泛應(yīng)用于圖像分類［3］、自然語(yǔ)言處理［4］、生物信息學(xué)［5］等領(lǐng)域。

關(guān)于常規(guī)SVM 算法的改進(jìn)，研究學(xué)者們做了大量工作，提出了許多改進(jìn)的SVM 模型。為了避免核函數(shù)被弱相關(guān)或不相關(guān)的特征所支配，文獻(xiàn)［6］中提出了特征加權(quán)支持向量機(jī)（Feature-Weighted SVM，F(xiàn)WSVM）模型；為了克服樣本中噪聲或離群點(diǎn)的影響，文獻(xiàn)［7］中提出了模糊支持向量機(jī)（Fuzzy Support Vector Machine，F(xiàn)SVM）模型，充分考慮到不同樣本對(duì)分類超平面貢獻(xiàn)的大小從而確定隸屬度值，降低了噪聲或離群點(diǎn)對(duì)分類性能的影響。后續(xù)的學(xué)者對(duì)于FSVM算法的關(guān)鍵問(wèn)題，即隸屬度函數(shù)的設(shè)計(jì)做了大量的研究：文獻(xiàn)［8］中將隸屬度的計(jì)算拓展到特征空間，在分類性能上有所提升；文獻(xiàn)［9-12］中分別通過(guò)設(shè)計(jì)新的隸屬度函數(shù)改進(jìn)了常規(guī)FSVM 算法；文獻(xiàn)［13］中綜合考慮了特征權(quán)重與樣本權(quán)重，在構(gòu)造隸屬度函數(shù)時(shí)應(yīng)用了特征權(quán)重，提出了基于Relief-F 特征加權(quán)的FSVM 算法，但該算法僅僅是在計(jì)算隸屬度時(shí)考慮了各個(gè)特征對(duì)樣本到其所在類中心距離的影響。

為同時(shí)考慮特征加權(quán)對(duì)隸屬度函數(shù)和核函數(shù)計(jì)算的影響，本文提出了一種新的模糊支持向量機(jī)方法——雙重特征加權(quán)模糊支持向量機(jī)（Doubly Feature-Weighted FSVM，DFWFSVM）。首先通過(guò)信息增益（Information Gain，IG）度量每個(gè)特征的重要性程度，得到每個(gè)特征相應(yīng)的權(quán)重。接著，一方面在隸屬度函數(shù)的計(jì)算中，在原始空間中應(yīng)用特征權(quán)重計(jì)算出樣本到類中心的加權(quán)歐氏距離，從而基于加權(quán)歐氏距離構(gòu)造隸屬度函數(shù)；另一方面在樣本訓(xùn)練過(guò)程中將樣本的特征權(quán)重應(yīng)用到核函數(shù)的計(jì)算中，從而避免弱相關(guān)或不相關(guān)的特征支配核函數(shù)的計(jì)算。實(shí)驗(yàn)結(jié)果表明，DFW-FSVM 相較于對(duì)比算法具有更好的推廣性能。

1 相關(guān)理論基礎(chǔ)

1.1 模糊支持向量機(jī)

不失一般性，本文以二分類問(wèn)題進(jìn)行FSVM 算法的理論分析，對(duì)于已知標(biāo)簽的訓(xùn)練樣本集，其中xi∈Rn是原始空間中的樣本點(diǎn)，yi∈{+1，-1}是類標(biāo)簽，si∈[0，1]是隸屬度值，表示樣本點(diǎn)xi歸屬于某一類yi的權(quán)重。FSVM 的目的是尋找一個(gè)能最大化分類間隔的分類超平面wT?(x) +b=0，其中w為一個(gè)垂直于分類超平面的法向量，b為位移量。相較于線性可分問(wèn)題，對(duì)于非線性問(wèn)題，通過(guò)映射?將樣本xi從原始空間映射到高維特征空間中，在特征空間中求解最優(yōu)分類超平面的問(wèn)題便可以轉(zhuǎn)化成下面的最優(yōu)化問(wèn)題：

其中：ξ=(ξ1，ξ2，…，ξl)T是松弛變量，C>0 是正則化參數(shù)。

針對(duì)上面的最優(yōu)化問(wèn)題，通過(guò)Lagrange 乘子法求解，可以轉(zhuǎn)化成下面的對(duì)偶問(wèn)題：

其中：αi≥0 為拉格朗日乘子,表示內(nèi)積。

通常并不知道映射?的具體形式，也無(wú)需知道，根據(jù)式（2）可知只需計(jì)算內(nèi)積的值，研究人員引入核函數(shù)k(xi，xj)把特征空間中的內(nèi)積運(yùn)算轉(zhuǎn)化為在原始空間上進(jìn)行簡(jiǎn)單的函數(shù)計(jì)算，解決了維數(shù)災(zāi)難問(wèn)題。求得相應(yīng)的決策函數(shù)為：

其中sign(?)是符號(hào)函數(shù)。

常用的核函數(shù)如下：

1）多項(xiàng)式核函數(shù)：

2）徑向基核函數(shù)：

3）Sigmoid 核函數(shù)：

1.2 特征加權(quán)

特征加權(quán)一般指根據(jù)某種準(zhǔn)則對(duì)樣本中的特征賦予相應(yīng)的權(quán)重。本文對(duì)于特征權(quán)重的值通過(guò)信息增益來(lái)度量。信息增益指信息熵與特征條件熵之差，其中信息熵作為度量樣本集合純度的指標(biāo)，信息熵的值越大，樣本集合的純度越低。針對(duì)離散值和連續(xù)值特征的信息增益計(jì)算方法如下：

設(shè)樣本集合D有m個(gè)類別標(biāo)簽Ci(i=1，2，…，m)，|D|表示D中所有的樣本的個(gè)數(shù)，|Ci，D|表示D中類別標(biāo)簽為Ci的樣本個(gè)數(shù)。假定特征a有v個(gè)可能的取值aj(j=1，2，…，v)，則樣本集合D的信息熵定義如下：

如果是離散值特征，則可由下式表示用特征a對(duì)樣本集合D進(jìn)行劃分所獲得的信息增益Gain(D，a)：

其中Dj表示樣本集合D中在特征a上取值為aj的樣本集合。

如果是連續(xù)值特征，通常采用二分法對(duì)連續(xù)值特征進(jìn)行處理，首先對(duì)連續(xù)值特征升序排序，記為{a1，a2，…，av}?；趧澐贮c(diǎn)t將數(shù)據(jù)集D劃分為子集和，其中包含在特征a上取值不大于t的樣本，則包含在特征a上取值大于t的樣本，針對(duì)連續(xù)特征a，需要考察包含v-1 個(gè)元素的候選劃分點(diǎn)集合，然后像離散值特征一樣來(lái)考察這些劃分點(diǎn)，選取最優(yōu)的劃分點(diǎn)進(jìn)行樣本集合的劃分。可由式（9）表示用特征a對(duì)樣本集合D進(jìn)行劃分所獲得的信息增益Gain(D，a)：

其中Gain(D，a，t)是樣本集D基于劃分點(diǎn)t二分后的信息增益。

通過(guò)這種方法可以計(jì)算出樣本集合D中每個(gè)特征的信息增益，信息增益的值越大，表示該特征對(duì)于分類的貢獻(xiàn)越大，因此求出的各個(gè)特征的信息增益可以代表各個(gè)特征的權(quán)重。

2 基于雙重特征加權(quán)的模糊支持向量機(jī)

2.1 特征加權(quán)核函數(shù)

關(guān)于特征加權(quán)核函數(shù)的構(gòu)造，本文以常用的三種核函數(shù)為例，根據(jù)式（8）和（9）求出特征權(quán)重=(1，2，…，n)，則特征矩陣的對(duì)角矩陣的形式如下：

1）特征加權(quán)多項(xiàng)式核函數(shù)：

2）特征加權(quán)徑向基核函數(shù)：

3）特征加權(quán)Sigmoid 核函數(shù)：

2.2 特征加權(quán)隸屬度函數(shù)

歐氏距離作為應(yīng)用最廣泛的距離度量方式，簡(jiǎn)單易行，但標(biāo)準(zhǔn)歐氏距離對(duì)于每個(gè)樣本的特征都賦予了相同的權(quán)重，然而實(shí)際情況并非如此，因此有些學(xué)者提出了特征加權(quán)歐氏距離的計(jì)算方法。兩個(gè)樣本xi和xj間的特征加權(quán)歐氏距離的計(jì)算公式如下：

其中：≥0(k=1，2，…，n)表示第k個(gè)特征的權(quán)重，n表示特征的個(gè)數(shù)。

本文設(shè)計(jì)隸屬度函數(shù)時(shí)，考慮基于原始空間計(jì)算樣本到其所在類中心的加權(quán)歐氏距離的大?。簶颖军c(diǎn)到類中心的距離越小，表示該樣本點(diǎn)的隸屬度越大；反之，則表示該樣本點(diǎn)的隸屬度越小。下面以二分類數(shù)據(jù)為例設(shè)計(jì)隸屬度函數(shù)。

設(shè)x+、x-分別代表正類和負(fù)類樣本的n個(gè)特征上的均值點(diǎn)并作為正負(fù)類的類中心，分別代表正類和負(fù)類樣本點(diǎn)到其所在類中心的加權(quán)歐氏距離，r+、r-分別代表正類和負(fù)類樣本點(diǎn)距離其所在類中心的最遠(yuǎn)距離。

通過(guò)式（15）～（17）的計(jì)算可得出基于距離的隸屬度函數(shù)表達(dá)式如下：

其中δ為事先給定的一個(gè)很小的正數(shù)用來(lái)保證si∈(0，1]。

2.3 算法設(shè)計(jì)

DFW-FSVM 算法的具體步驟如下：

輸入 數(shù)據(jù)集S；

輸出 預(yù)測(cè)標(biāo)簽。

1）數(shù)據(jù)集預(yù)處理并按照7∶3 的比例隨機(jī)劃分訓(xùn)練集與測(cè)試集；

3）構(gòu)造加權(quán)隸屬度函數(shù)，計(jì)算出每個(gè)樣本的隸屬度si；

4）構(gòu)造特征加權(quán)核函數(shù)kp(xi，xj)；

5）通過(guò)網(wǎng)格搜索尋找核函數(shù)參數(shù)γ和正則化參數(shù)C的最優(yōu)值，訓(xùn)練FSVM 算法；

6）運(yùn)用DFW-FSVM 算法進(jìn)行預(yù)測(cè)，并進(jìn)行相關(guān)性能評(píng)估。

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

本文的實(shí)驗(yàn)在i5 處理器、CPU 頻率2.6 GHz、安裝內(nèi)存（RAM）8 GB、Windows 7 操作系統(tǒng)上進(jìn)行，采用LIBSVM 工具箱的變體［14］，為每個(gè)樣本分配不同的權(quán)重，實(shí)驗(yàn)工具是Matlab R2015b。為了驗(yàn)證本文所提算法具有較好的性能，在UCI 機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)［15］中選取了8 個(gè)二分類的數(shù)據(jù)集，具體的數(shù)據(jù)信息如表1 所示，其中對(duì)數(shù)據(jù)集WBC，去除了16 個(gè)包含未知特征值的樣本，剩下683 個(gè)樣本。

表1 實(shí)驗(yàn)數(shù)據(jù)信息Tab.1 Experimental data information

本實(shí)驗(yàn)對(duì)所有數(shù)據(jù)均歸一化到［0，1］區(qū)間，并按照7∶3的比例隨機(jī)抽樣劃分訓(xùn)練集和測(cè)試集，核函數(shù)選擇高斯核函數(shù)，通過(guò)網(wǎng)格搜索的方法尋找核函數(shù)參數(shù)γ和正則化參數(shù)C的最優(yōu)值，其中C={2-5，2-3，…，215}，γ={2-15，2-14，???，23}。

將本文算法與以下五種算法進(jìn)行對(duì)比：

1）SVM：標(biāo)準(zhǔn)的SVM 分類算法［1-2］。

2）FSVM：標(biāo)準(zhǔn)的FSVM 分類算法，即在原始空間中基于樣本點(diǎn)到類中心的距離計(jì)算隸屬度的FSVM 分類算法［7］。

3）FWSVM：通過(guò)信息增益算法對(duì)標(biāo)準(zhǔn)的SVM 算法進(jìn)行特征加權(quán)［6］。

4）FWFSVM：為了更好地與本文提出的DFW-FSVM 算法進(jìn)行性能上的對(duì)比，通過(guò)用信息增益算法替換原算法中的Relief-F 算法，對(duì)標(biāo)準(zhǔn)的FSVM 算法進(jìn)行特征加權(quán)［13］。

5）CKA-FSVM：基于中心核對(duì)齊思想設(shè)計(jì)隸屬度函數(shù)的FSVM 分類算法［12］。

為了使實(shí)驗(yàn)結(jié)果更具說(shuō)服力，本文使用準(zhǔn)確率（Acc）和F1值（F1）作為對(duì)比各算法分類性能的評(píng)價(jià)指標(biāo)。準(zhǔn)確率是指分類正確的樣本占樣本總數(shù)的比例，是分類任務(wù)中最常用的性能度量；F1值是查準(zhǔn)率（Precision，Pre）與 查全率（Recall，Rec）的調(diào)和平均。計(jì)算公式為：

其中：真正例TP（True Positive）表示正確分類的正類結(jié)果樣本數(shù)，假正例FP（False Positive）表示錯(cuò)誤分類的正類結(jié)果樣本數(shù)，真反例TN（True Negative）表示正確分類的負(fù)類結(jié)果樣本數(shù)，假反例FN（False Negative）表示錯(cuò)誤分類的負(fù)類結(jié)果樣本數(shù)。

六種算法的分類準(zhǔn)確率和F1值的對(duì)比如表2 所示?？梢钥闯?，DFW-FSVM 算法在選定的8 個(gè)數(shù)據(jù)集上的F1值最高，并在7 個(gè)數(shù)據(jù)集上取得了最高的分類準(zhǔn)確率，其中：在Ionosphere 數(shù)據(jù)集上，F(xiàn)WSVM 算法達(dá)到了與DFW-FSVM 算法一樣的分類準(zhǔn)確率；特別注意到CKA-FSVM 算法在非平衡數(shù)據(jù)集上取得了較好的效果，比如在Hepatitis 數(shù)據(jù)集上取得了最高的分類準(zhǔn)確率，在CMSC 數(shù)據(jù)集上也取得了最高的F1值。

表2 六種算法在UCI數(shù)據(jù)集上的準(zhǔn)確率與F1值對(duì)比 單位：%Tab.2 Comparison of accuracies and F1 values of six algorithms on UCI dataset unit：%

綜合分析表明，在相同的條件下，DFW-FSVM 算法的性能有明顯的提升。

1）當(dāng)隸屬度函數(shù)設(shè)計(jì)得不好時(shí)，模糊支持向量機(jī)會(huì)出現(xiàn)分類效果不如標(biāo)準(zhǔn)SVM 算法的情況，例如CKA-FSVM、FSVM和FWFSVM 算法在CMSC 數(shù)據(jù)集上的分類準(zhǔn)確率低于SVM算法；FWSVM 算法在CMSC 數(shù)據(jù)集上的F1值低于SVM算法。

2）針對(duì)本文實(shí)驗(yàn)中的8 個(gè)數(shù)據(jù)集而言，特征加權(quán)思想有效地提高了算法的泛化性能，但是針對(duì)某些數(shù)據(jù)集也會(huì)存在特征加權(quán)失效的情況。比如在Hepatitis 數(shù)據(jù)集上，F(xiàn)WSVM算法雖然在F1值上優(yōu)于SVM 算法，但是在算法分類準(zhǔn)確率上反而低于SVM；反之，在CMSC 數(shù)據(jù)集上，F(xiàn)WSVM 算法雖然在分類準(zhǔn)確率上優(yōu)于SVM 算法，但是在F1值上卻低于SVM 算法；在ST 數(shù)據(jù)集上，F(xiàn)WFSVM 算法在分類準(zhǔn)確率和F1值上都低于SVM 算法。

3）DFW-FSVM 算法在上述8 個(gè)數(shù)據(jù)集上獲得了比對(duì)比算法更好結(jié)果的原因可以從學(xué)習(xí)算法的魯棒性加以解釋，該算法通過(guò)獲得的特征權(quán)重分別應(yīng)用到隸屬度函數(shù)和核函數(shù)的計(jì)算中，從而避免在計(jì)算過(guò)程中被一些弱相關(guān)或不相關(guān)的特征所支配，同時(shí)相較于單重特征加權(quán)算法，極大提高了算法的泛化性能，具有很好的推廣性能。

4 結(jié)語(yǔ)

本文在分析基于特征加權(quán)的FSVM 算法的基礎(chǔ)上，針對(duì)該算法只考慮特征權(quán)重對(duì)隸屬度函數(shù)的影響，而沒(méi)有考慮到在樣本訓(xùn)練過(guò)程中將特征權(quán)重應(yīng)用到核函數(shù)的計(jì)算上的缺陷，提出了基于雙重特征加權(quán)的模糊支持向量機(jī)方法DFWFSVM。詳細(xì)闡述了模糊支持向量機(jī)原理、特征權(quán)重的求解、特征加權(quán)核函數(shù)及隸屬度函數(shù)的推導(dǎo)過(guò)程，并進(jìn)一步通過(guò)實(shí)驗(yàn)驗(yàn)證了該算法可以改變特征空間中點(diǎn)與點(diǎn)之間的位置關(guān)系，避免在計(jì)算中被一些弱相關(guān)或不相關(guān)的特征所支配，表明了該算法能夠較明顯地提高分類器的泛化能力。由于本文算法只涉及單核的計(jì)算，因此下一步將考慮應(yīng)用組合核函數(shù)以及如何改進(jìn)隸屬度的計(jì)算來(lái)提升分類器的性能。