雙重特征加權模糊支持向量機

邱云志，汪廷華，戴小路

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

0 引言

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

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

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

1 相關理論基礎

1.1 模糊支持向量機

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

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

針對上面的最優(yōu)化問題，通過Lagrange 乘子法求解，可以轉化成下面的對偶問題：

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

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

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

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

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

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

3）Sigmoid 核函數(shù)：

1.2 特征加權

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

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

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

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

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

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

通過這種方法可以計算出樣本集合D中每個特征的信息增益，信息增益的值越大，表示該特征對于分類的貢獻越大，因此求出的各個特征的信息增益可以代表各個特征的權重。

2 基于雙重特征加權的模糊支持向量機

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

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

1）特征加權多項式核函數(shù)：

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

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

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

歐氏距離作為應用最廣泛的距離度量方式，簡單易行，但標準歐氏距離對于每個樣本的特征都賦予了相同的權重，然而實際情況并非如此，因此有些學者提出了特征加權歐氏距離的計算方法。兩個樣本xi和xj間的特征加權歐氏距離的計算公式如下：

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

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

設x+、x-分別代表正類和負類樣本的n個特征上的均值點并作為正負類的類中心，分別代表正類和負類樣本點到其所在類中心的加權歐氏距離，r+、r-分別代表正類和負類樣本點距離其所在類中心的最遠距離。

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

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

2.3 算法設計

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

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

輸出 預測標簽。

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

3）構造加權隸屬度函數(shù)，計算出每個樣本的隸屬度si；

4）構造特征加權核函數(shù)kp(xi，xj)；

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

6）運用DFW-FSVM 算法進行預測，并進行相關性能評估。

3 實驗與結果分析

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

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

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

將本文算法與以下五種算法進行對比：

1）SVM：標準的SVM 分類算法［1-2］。

2）FSVM：標準的FSVM 分類算法，即在原始空間中基于樣本點到類中心的距離計算隸屬度的FSVM 分類算法［7］。

3）FWSVM：通過信息增益算法對標準的SVM 算法進行特征加權［6］。

4）FWFSVM：為了更好地與本文提出的DFW-FSVM 算法進行性能上的對比，通過用信息增益算法替換原算法中的Relief-F 算法，對標準的FSVM 算法進行特征加權［13］。

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

為了使實驗結果更具說服力，本文使用準確率（Acc）和F1值（F1）作為對比各算法分類性能的評價指標。準確率是指分類正確的樣本占樣本總數(shù)的比例，是分類任務中最常用的性能度量；F1值是查準率（Precision，Pre）與 查全率（Recall，Rec）的調和平均。計算公式為：

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

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

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

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

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

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

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

4 結語

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