陰影集的模糊支持向量機樣本選擇方法

蘇小紅，趙玲玲，謝 琳，馬培軍

（哈爾濱工業大學計算機科學與技術學院，150001 哈爾濱）

陰影集的模糊支持向量機樣本選擇方法

蘇小紅，趙玲玲，謝 琳，馬培軍

（哈爾濱工業大學計算機科學與技術學院，150001 哈爾濱）

樣本選擇可以提高模糊支持向量機訓練速度并在一定程度上提高其抗噪能力，但存在有效樣本選擇困難和選樣率高的問題，利用陰影集對模糊集的分析能力，提出一種新的基于陰影集的模糊支持向量機樣本選擇方法，將模糊集合劃分為可信任、不可信任及不確定3個子集，僅在可信任和不確定子集中選樣，并分別采用子空間樣本選擇和邊界向量提取的方法選樣.實驗結果表明，該方法在保持分類器泛化能力的前提下可以有效降低選樣率和訓練時間.因該方法去除了樣本中的不可信任數據，所以當訓練樣本中含有噪聲時，還可以有效提高分類器的分類性能.

模糊支持向量機;樣本選擇;陰影集

系統的性能退化狀態識別是智能維護(Intelligent Maintenance System，IMS)［1］系統的核心之一.目前，系統的退化狀態識別方法主要有3類［2］.基于模型的方法因系統的性能退化機理復雜、很難建立退化模型，而實際應用價值不大［3］.神經網絡雖應用廣泛，但因系統結構復雜，識別過程受很多因素的影響［4］，因此，識別退化狀態時，易發生“維度災難”問題［5］.支持向量機(Support Vector Machine，SVM)由 V.Vapnik［6］于 1995 年提出，該方法建立在結構風險最小化的基礎上，有良好的泛化能力，能較好的解決小樣本、非線性、高維度問題，因此廣泛應用于故障識別中.

將SVM用于退化狀態識別主要有兩個難點:首先，訓練集中人工標定的退化狀態中可能會有錯誤標定，即訓練集中存在噪聲，因此，應提高SVM的抗噪能力.其次，系統的退化數據較多，因此，應提高SVM在大樣本上的訓練速度.

實際上，系統的退化是一個連續的過程，明確標定每個樣本點的狀態是不合理的，因此，退化狀態識別應使用模糊支持向量機(Fuzzy Support Vector Machine，FSVM)［7］.樣本選擇是減少 FSVM訓練時間，一定程度提高其抗噪能力的一個有效且直接的方法.

本文利用陰影集［8－9］對模糊集的分析能力，提出一種基于陰影集劃分的FSVM樣本選擇方法，在不同置信區間采用不同的樣本選擇方法.實驗表明，該方法在保證FSVM泛化能力的前提下，大大減少了訓練時間，還提高了含噪聲數據的FSVM的預測精度.

1 傳統SVM與FSVM樣本選擇方法

傳統SVM的樣本選擇方法大致包含以下3種:隨機選樣的方法［10］、保留典型樣本的方法［11－12］、保留支持向量的方法［13－15］.其中，保留典型樣本方法主要采用的是對樣本進行聚類，保留聚類中心為典型樣本的策略.保留SVM的方法中，文獻［15］主要研究的是可分支持向量機的樣本選擇方法，該方法是所有的樣本選擇方法中，選樣率最低的一種方法，且能保證選樣后SVM的泛化能力.

FSVM與傳統SVM的最大區別在于其訓練樣本含有模糊隸屬度.隨機選樣方法可直接應用于FSVM，但不能保證選樣后FSVM的泛化能力.模糊隸屬度是樣本點的重要信息，而保留典型樣本的方法是根據樣本點的位置信息決定典型樣本，因此選出的典型樣本在模糊集中并不一定是典型的.FSVM中，模糊隸屬度不同的樣本點，分類面對它們的容忍程度是不一樣.而支持向量是由樣本點到分界面的距離以及樣本點的模糊隸屬度共同決定的.FSVM中，可以確定的非支持向量只有類別中心所在的樣本點，以及相較與類別中心，距離另一類更遠的點.文獻［16］就是基于這個思想，提出了基于邊界向量提取的模糊支持向量機.但該方法的選樣率較高，理論上需選擇1/2的樣本.

對模糊集直接進行樣本選擇是很困難的，因此，挖掘出模糊集中的確定信息，從而將傳統SVM的樣本選擇方法應用于FSVM中，是非常有意義的.

2 模糊集

定義1(模糊集)［17］設A是論域X到［0，1］上的一個映射關系，即

則稱A是X上的模糊集.

定義2(模糊隸屬度) 式(1)中，A(x)稱為x對模糊集A的模糊隸屬度，或直接稱其為模糊集的隸屬函數.

以下，記X上全體模糊集所構成的集合為F(X).如果，A ∈ F(X)，且 A:X → {0，1}，則 A 為經典集，記為A∈P(X).

定義3(模糊度) 若映射

滿足條件:

1)當且僅當A∈P(X)時，d(A)=0;

2)當且僅當A(x)≡0.5時，d(A)=1;

3)對于?x∈X，當B(x)≤A(x)≤0.5時，d(B)≤d(A);

4)對于A∈F(X)，有d(A)=d(Ac).

則稱映射d為F(X)上的一個模糊度，d(A)為模糊集A的模糊度.

常用的幾種模糊度計算公式如下:

令 A={(x1，A(x1))，(x2，A(x2))，…，(xn，A(xn))}表示一個模糊集.

模糊集A的Hamming模糊度為

模糊集A的Euclid模糊度為

雖然Hamming模糊度的計算簡單，但誤差較大.Euclid模糊度相比于 Hamming模糊度更準確.因此本文采用Euclid作為度量模糊集合的模糊度.

3 陰影集

陰影集由W.Pedrycz于1998年提出，它主要用于解決模糊邏輯中的一個矛盾問題:用確定的模糊隸屬度來描述不確定的集合.陰影集的一個主要依據是，模糊集中隸屬度為0.5附近的樣本，其類別信息很難確定，而隸屬度接近于1或隸屬度接近于0的樣本，其類別信息是可確定的.因此，陰影集映射將隸屬度足夠高的樣本的隸屬度提高為1，將隸屬度足夠低的樣本的隸屬度降低為0，而將其他樣本的隸屬度放寬為［0，1］區間.從而實現提取出了模糊集中的確定信息.

從模糊集到陰影集實質上是一個三值映射.

式中:A為模糊樣本集;Ψ為由模糊集到陰影集的映射，稱為模糊映射;α為確定陰影集劃分的閾值;映射Ψ將模糊隸屬度 ＜α的樣本映射為0;模糊隸屬度 ＞1－α的樣本映射為1;其余樣本映射為(0，1).

在陰影集的基礎上，本文提出可信任數據、不確定數據以及不可信任數據的概念.利用陰影集映射將原有的模糊集進行區域劃分.

定義4(可信任數據) 對于?(x，A(x))∈A，A為模糊集，A(x)稱為x對模糊集A的模糊隸屬度.

則稱x為可信任數據.

定義5(不可信任數據) 對于?(x，A(x))∈A，A為模糊集，A(x)稱為x對模糊集A的模糊隸屬度.

則稱x為不可信任數據.

定義6(不確定數據) 對于?(x，A(x))∈A，A為模糊集，A(x)稱為x對模糊集A的模糊隸屬度.

則稱x為不確定數據.

4 基于陰影集劃分的樣本選擇方法

4.1 劃分閾值的確定

閾值的確定是陰影集劃分中最關鍵的一步，合理的閾值選擇是后續分區域樣本選擇方法正確性的保證.

文獻［8－9］在給出陰影集定義的同時，也給出了劃分閾值的確定原則:由模糊集到陰影集的映射應該保持整個集合不確定性的平衡.映射后，模糊集中隸屬度 ＜α的樣本點和隸屬度 ＞1－α的樣本點的不確定性都消除了，這部分的變化應該由陰影集(即本文定義的不確定數據集合)來補償.這里，不確定性是由樣本點的模糊隸屬度來衡量的.

理論上，如果已知模糊集的隸屬度函數且知道樣本點的分布，在樣本點無窮時，不確定性的平衡是可以達到的.但實際樣本點的分布是很難預知的，僅知有限點的模糊隸屬度，這時，可能找不到一個閾值，可保持不確定性的平衡.因此，劃分的閾值一般取使不確定性改變最小的值.由此，得到閾值α的確定公式為

上述閾值確定的方法存在一定的問題.首先，模糊理論中，集合的模糊性是由模糊度來衡量的.由文獻［8－9］提出的對模糊集不確定性的度量實際上是沒有歸一化的Hamming模糊度的計算，但是文獻［17］中指出，Hamming模糊度的計算有很大的誤差，這會給實際計算的閾值帶來很大的誤差.它可能使計算的閾值小于實際的閾值，也可能使計算的閾值大于實際的閾值.實際上，這是和樣本本身的分布有關的.其次，文獻［8－9］以不確定數據集合來衡量映射后集合不確定性的減少是不合理的.實際上，不確定數據對應的模糊集中的樣本，其不確定性本身就很大，雖然映射后，會增加這部分數據的不確定性，但是這個增量是＜1的.這個部分的計算也會產生較大的誤差，并且，這個誤差會使計算的閾值比實際的閾值大.

本文指出，由模糊集到陰影集的映射應該保持集合的模糊度不變.在此基礎上，給出新的閾值計算為

式中:d(A)、d(B)分別為模糊集A及其對應的陰影集B的模糊度.

模糊集中隸屬度為0.5的樣本，樣本信息是完全未知，與陰影集中不確定數據的含義相同，因此，本文將不確定數據模糊度的計算等同于模糊集中隸屬度為0.5的樣本的模糊度的計算.由此，給出劃分閾值為

由式(2)知，劃分閾值只是用于對模糊樣本的模糊隸屬度進行劃分，因此，這里劃分閾值可僅考慮有限種情況，它是由樣本的隸屬度決定的.

給定模糊集A，劃分閾值的取值集合為

分析可知，隨著所選閾值α的增大，不確定數據會逐漸減少，對應的陰影集的模糊度會由1逐漸減少為0.即隨著閾值α的增大，V(α)會先增大后減小.因此，當本文從小到大計算每一個α對應的V(α)時，只要在某一次計算中，V(α)的值變大，就可以認定之后V(α)會逐步增加，最佳閾值即是上次計算中的α.

本文給出的計算最佳閾值的算法如圖1所示.

圖1 最佳閾值的計算算法

可以看到，在對blongs［］進行排序后，最多掃描blongs［］一遍，因此，搜索最佳閾值的時間復雜度為O(n)，算法的時間復雜度為O(nlg n).

4.2 可信任數據集合的樣本選擇方法

可信任數據集合采用子樣本空間樣本選擇的方法.這里的子空間指的是已選數據集張成的空間.該方法是一種類內迭代的選樣方法，每次迭代中選擇距離子空間最遠的樣本點添加到已選數據集中，直到滿足誤差界或選樣個數.本質上說，該方法是對原樣本集空間維數的一個快速逼近，選樣個數最多是特征空間的維數.該方法不能完全逼近原數據集的凸包，即不能找到可信任數據中的所有支持向量，但實際中并不需要精確逼近原數據集的凸包就能保證支持向量機的泛化能力.

4.3 不確定數據集合的樣本選擇方法

不確定數據集合采用基于邊界向量提取方法進行樣本選擇.首先，該方法利用支持向量描述的方法確定類別的中心，認為這兩個中心肯定不是支持向量;然后以這兩個中心的連線為直徑確定一個圓，并定義圓內的樣本為邊界向量.模糊支持向量機的支持向量肯定位于圓內，選擇邊界向量進行訓練，因此減少了訓練時間.

4.4 基于陰影集劃分的樣本選擇方法

本文提出的樣本選擇基本流程如圖2所示.其基本思路為:先利用陰影集思想判定模糊集中的樣本是可信任、不可信任還是不確定數據;其次，由于可信任數據是樣本集中可確定類別的樣本，兩類的可信任數據集是可分的.因此，對可信任數據集采用子空間樣本選擇方法，對不確定數據采用邊界向量提取方法;最后將兩部分樣本合并得到最終的精簡模糊樣本集.

5 模糊隸屬度的確定

本文在文獻［18］的基礎上，修改隸屬度映射公式為

式中:ξi為某樣本點的模糊隸屬度;di為該樣本點距離該類中心的距離;r為包含該類大多數樣本點的最小超球的半徑;λ為最小包圍球內外樣本點的臨界隸屬度，一般取為0.4;σ1、σ2分別為控制隸屬度變化范圍的一個尺度因子，這里分別取為2.0和4.0.

圖2 基于陰影集劃分的樣本選擇的流程

6 實驗結果與分析

實驗在Pentium IV 1.6 GHz CPU，1.00 GB內存的PC上執行.為方便比較，FSVM中，核函數取為徑向基函數，FSVM都為C-FSVM模型.參數利用libsvm［19］工具包選取對傳統SVM分類效果最好的參數形式.

6.1 實驗1:仿真數據實驗

為直觀給出本文方法選樣點的位置信息，該實驗主要分析2維數據的線性不可分問題.由MATLAB生成的兩類分布不同的隨機數.正類和反類分別為以［0.25，0.50］和［0.75，0.50］為期望的50個二維正態隨機數集合.

訓練樣本點及數據劃分如圖3所示.集合中樣本點按照上述模糊隸屬度公式確定樣本的隸屬度.求解出最優的劃分閾值后，就得到了對應的陰影集.可見，兩個類的可信任數據是可分的，不確定數據在可信任數據外圍，有部分的交叉.不可信任數據則是離中心較遠的數據，可視為噪聲，直接舍去.在兩類中，一部分樣本點遠離另一類，也被認為是不可信任數據而舍棄了.這是因為模糊隸屬度是按樣本點到類中心的距離計算的，這部分數據離中心較遠，被賦予了較小的模糊隸屬度.但由于這部分數據肯定不是支持向量，不管其舍棄與否，都對FSVM的訓練結果沒有影響.

圖3 訓練樣本點及數據劃分圖

選樣前后分類效果對比如圖4所示.圖中，較細的線表示選樣前樣本訓練得到的分類面，較粗的線表示選樣后樣本訓練得到的分類面.從分類效果上來看，用原模糊集進行訓練得到的分類面較好，錯分了9個樣本點，選樣后的樣本訓練得到的分類面錯分了10個樣本點.從泛化能力上來看，實際的分類面應該是過(0.5，0)的垂直線.選樣后的樣本點訓練得到的分類面要稍優于不選樣訓練得到的分類面.

圖4 選樣前后分類效果對比

6.2 實驗2:真實數據集實驗

本文選擇 Statlog［20］中的 german.numer數據集，對數據歸一化后，計算模糊隸屬度，得到需要的模糊集.

6.2.1 子實驗1:閾值比較

這里，模糊度的計算分別采用Hamming和Euclid兩種方法.文獻［9］和本文方法得到的閾值如表1所示.

表1 閾值比較

可以看到，文獻［9］確定的閾值比本文確定的閾值要大，映射增大了集合的模糊度.

6.2.2 子實驗2:可信任數據選樣數對結果的影響

對可信任數據，選樣的最大數量是人為定義的.不難發現，隨著選擇樣本的最大數量的增大，對測試集的識別率會提高，但選樣時間也會增大.每類樣本的最大選樣數量和預測精度的關系如圖5所示.

圖5 可信任數據集選樣數與預測精度關系

這里，原樣本訓練得到的FSVM的預測精度為73.273 3%.可以看出，對可信任數據，當每類最大選樣點逐漸增加時，預測的正確率呈上升趨勢，并且對于german.numer數據集，當每類選樣數為18時，對測試集的預測精度最高.其后，隨著選樣數的增加，預測精度基本保持.可以認為，對可信任數據，只要一個很小的選樣數，就能保證預測的精度.

當每類選樣數為18時，利用本文方法進行樣本選擇的時間為0.031 s，挑選后的樣本利用FSVM訓練的時間為0.032 s，該方法的總時間為0.063 s.而不進行樣本選擇的訓練FSVM的時間為0.3 s.可見選樣后大大減少了樣本的訓練時間.

6.3 實驗3:結果分析

實驗 采 用 的 數 據 集 包 括 TKH96a［21］中fourclass，Statlog 中的 german.numer，NIPS 2003 Feature Selection Challenge［22］中的 gisetts.數據集說明如表2所示.

表2 數據集說明

這里主要從預測精度以及運行時間上驗證本文算法的有效性.實驗比較了選樣前后，訓練FSVM的時間，以及對測試集的預測精度.這里，選樣率指選擇的樣本數占原模糊集樣本數的比例.實驗結果如表3所示.

表3 實驗對比結果

對fourclass數據集的可信任數據，當每類最大選樣數為23時，預測準確率為100%;當每類最大選樣數為16時，預測準確率為99.651 6%(錯誤預測一個樣本).對可信任數據，若每類選樣16個，則在基本保持預測精度的前提下，還可進一步減少運行時間.

一般來說，邊界向量提取的方法的選樣率在0.5左右，本文提出的方法將選樣率降低至0.2左右，大大降低了選樣率.可以看出，采用本文方法，可大大減少FSVM的訓練時間，且能保證預測的準確率.

7 結論

1)利用陰影集的思想挖掘中的確定信息，將SVM的樣本選擇方法應用于FSVM中，大大減少了選樣率.

2)給出了新的陰影集閾值確定方法，并給出了基于陰影集的模糊支持向量機樣本選擇算法.

3)實驗表明，本文提出的選樣方法在保證FSVM的泛化能力的前提下，大大降低了選樣率，減少了FSVM的訓練時間.

［1］LEE J.Measurement of machine performance degradation using a neural network model［J］.Computers in Industry，1996，30(3):193－209.

［2］郭磊，陳進.設備性能退化評估與預測研究綜述［J］.振動與沖擊，2008，27(S):139 －142.

［3］VENKATASUBRAMANIAN V，RENGASWAMY R，YIN K，et al.A review of process fault detection and diagnosis part I:quantitative model-based methods［J］.Computers and Chemical Engineering，2003，27(3):293－311.

［4］柴天佑，丁進良，王宏，等.復雜工業過程運行的混合智能優化控制方法［J］.自動化學報，2008，34(5):505－515.

［5］呂琛，王桂增，張澤宇.PWM型VLSI神經網絡在故障診斷中的應用［J］.自動化學報，2005，31(2):195－201.

［6］VAPNIK V.The nature of statistical learning theory［M］.New York:Springer，1995.

［7］LIN Chunfu，WAN Shengde.Fuzzy support vector machine［J］.IEEE Trans.on Neural Networks，2002，13(2):464－471.

［8］PEDRYCZ W.Shadowed sets:representing and processing fuzzy sets［J］.IEEE Trans on Systems，Man and Cybernetics— Part B:Cybernetics，1998，28(1):103－109.

［9］PEDRYCZ W.From fuzzy sets to shadowed sets:interpretation and computing［J］.International Journal of Intelligence System，2009，24(1):48－61.

［10］LEE Y J，MANGASARIAN O L.RSVM:reduced support vector machines［R］.Wiscosin:University of Wisconsin，2000.Chicago，2001.

［11］ZHENG Songfeng，LU Xiaofeng，ZHENG Nanning，et al.Unsupervised clustering based reduced support vector machine［C］//Proceeding of IEEE International Conference on Acoustics，Speech，and Signal Processing(ICASSP).Piscataway，NJ:IEEE，2003:821 －824.

［12］ALMEIDA M B，BRAGA A P，BRAGA J P.Svm-km:speeding svms learning with a priori cluster selection and k-means［C］//Proceeding of the 6th Brazilian Symposium on Neural Networks.Washington，DC:IEEE Computer Society，2000:162－167.

［13］李紅蓮，王春花，袁保宗，等.針對大規模訓練集的支持向量機學習策略［J］.計算機學報，2004，27(5):140－144.

［14］LI Yuangui，HU Zhonghui，CAI Yunza，et al.Support vector based prototype selection method for nearest neighbor rules ［M］.Berlin，Germany:Springer，2005:528－535.

［15］姜文瀚.模式識別中的樣本選擇研究及應用［D］.南京:南京理工大學，2007.

［16］吳青，劉三陽，杜喆.基于邊界向量提取的模糊支持向量機方法［J］.模式識別與人工智能，2008，21(3):332－337.

［17］胡寶清.模糊理論基礎［M］.武漢:武漢大學出版社，2004.

［18］張翔，肖小玲，徐光祐.基于樣本之間緊密度的模糊支持向量機方法［J］.軟件學報，2006，17(5):951－958.

［19］CHANG Chih-chung，LIN Chih-jen.LIBSVM:a library for support vector machines［J］.ACM Transactions on Intelligent Systems and Technology，2011，2(3):27.

［20］BRAZDIL P.Statlog dataset［EB/OL］.http://www.liacc.up.pt/ML/old/statlog/datasets.html.

［21］HO T K，KLEINBERG E M.Building projectable classifiers of arbitrary complexity［C］//Proceedings of the 13th International Conference on Pattern Recognition.Washington，DC:IEEE Computer Society，1996:880 －885.

［22］GUYON I，GUNN S，HUR A B，et al.Result analysis of the NIPS 2003 feature selection challenge［J］.Neural Information Processing Systems，2005，(17):545 －552.

Shadowed sets-based sample selection method for fuzzy support vector machine

SU Xiao-hong，ZHAO Ling-ling，XIE Lin，MA Pei-jun

(School of Computer Science and Technology，Harbin Institute of Technology，150001 Harbin，China)

Sample selection can speed up the training of Fuzzy Support Vector Machine(SVM).However，it is difficult to select effective sample and the selection ratio is very high.This paper proposes a new sample selection method for Fuzzy SVM based on shadowed sets.We divide the fuzzy sets into three subsets，i.e.trustable data sets，trustless data sets and uncertain data sets.The samples are only selected in trustable data sets and uncertain data sets by using the subspace selection algorithm and the border vector extraction method respectively.Experimental results show that the training time and selection ratio is significantly reduced without any decrease in generalization ability by using the samples chosen by the proposed method.Furthermore，it improves the prediction performance of the classifiers when the data sets contain noises.

fuzzy support vector machine;sample selection;shadowed sets

TP183

A

0367－6234(2012)09－0078－07

2011－05－24.

國家自然科學基金資助項目(61175027).

蘇小紅(1966—)，女，教授，博士生導師;

馬培軍(1963—)，男，教授，博士生導師.

蘇小紅，sxh@hit.edu.cn.

(編輯 張 紅)