具有N-S磁極效應(yīng)的最大間隔模糊分類器

劉忠寶，裴松年，楊秋翔

?

具有N-S磁極效應(yīng)的最大間隔模糊分類器

劉忠寶，裴松年，楊秋翔

(中北大學(xué)計算機與控制工程學(xué)院 太原 030051)

該文提出一種具有N-S磁極效應(yīng)的最大間隔模糊分類器C)。該方法尋求一個具有N-S磁極效應(yīng)的最優(yōu)超平面，使得一類樣本受磁極吸引離超平面盡可能近，另一類樣本受磁極排斥離超平面盡可能遠。針對傳統(tǒng)支持向量機面臨的對噪聲和野點敏感問題，引入模糊技術(shù)來降低噪聲和野點對分類的影響，從而進一步提高泛化性能和分類效率。通過人工數(shù)據(jù)集和實際數(shù)據(jù)集上的實驗，證明了MPMMFC的有效性。

模糊技術(shù); 核方法; 磁極效應(yīng); 模式分類

模式分類是模式識別中的重要內(nèi)容之一，其通過對有限訓(xùn)練樣本的學(xué)習(xí)得到一個具有較低結(jié)構(gòu)風險和良好泛化能力的分類器[1]。在當前主流的模式分類方法中，支持向量機(SVM)[2-4]及其相關(guān)變體受到人們的廣泛關(guān)注，其通過最大化類間間隔實現(xiàn)有效分類。文獻[2-4]提出C-SVM方法，該方法基于最大間隔思想在空間中尋找最優(yōu)超平面將兩類分開；文獻[5]提出-SVM方法，通過引入?yún)?shù)來控制支持向量個數(shù)的下界和訓(xùn)練誤差的上界；文獻[6]提出單類支持向量機(one class SVM, OCSVM)試圖在高維特征空間中構(gòu)建最大間隔超平面劃分正常數(shù)據(jù)和噪聲數(shù)據(jù)；文獻[7]提出的支持向量數(shù)據(jù)描述(support vector data description, SVDD)試圖在高維特征空間中計算尋求包含所有輸入樣本的最小包含球劃分正常數(shù)據(jù)和噪聲數(shù)據(jù)；針對SVM以及變體面臨對噪聲和野點的敏感問題，文獻[8]提出模糊支持向量機(fuzzy SVM, FSVM)，對不同的樣本采用不同的合理的權(quán)重系數(shù)，在構(gòu)造目標函數(shù)時削弱噪聲和野點對分類的影響，從而在一定程度上提高分類性能。

近年來，很多分類新方法在進行分類決策時將類間間隔和類內(nèi)分布性狀考慮在內(nèi)[1,9]。文獻[10]提出大間隔最小壓縮包含球?qū)W習(xí)機(large margin and minimal reduced enclosing ball, LMMREB)，該方法試圖尋求兩個同心壓縮包含球?qū)崿F(xiàn)類間間隔和類內(nèi)內(nèi)聚性的最大化并提高分類性能；文獻[11]提出基于熵理論和核密度估計的最大間隔學(xué)習(xí)機(maximum margin learning machine based on entropy concept and kernel density estimation, MLMEK)，MLMEK引入熵和核密度表征分類不確定性和樣本分布特征實現(xiàn)分類；文獻[12]綜合最小包含球和最大間隔思想，提出一種用于新奇檢測的小球體和大間隔方法(small sphere large margin，SSLM)，SSLM在高維特征空間中構(gòu)建最小包含球包圍正常樣本實現(xiàn)分類；文獻[13]提出一種模糊最大間隔球形結(jié)構(gòu)多類支持向量機(fuzzy maximal-margin spherical-structured multi- class SVM, MSM-SVM)，MSM-SVM試圖構(gòu)造正負類間隔最大正類體積最小超球體實現(xiàn)分類。

受以上方法啟發(fā)，本文在N-S磁極效應(yīng)理論基礎(chǔ)上，結(jié)合傳統(tǒng)SVM的大間隔思想，提出一種具有N-S磁極效應(yīng)的最大間隔模糊分類器MPMMFC，MPMMFC在構(gòu)建最優(yōu)決策面時，引入模糊性懲罰參數(shù)，降低噪聲和野點數(shù)據(jù)對決策面的影響，進一步提高泛化性能。

對本文后續(xù)做以下規(guī)定：對于一個包含個模式的二分類問題，給定訓(xùn)練樣本集合。其中：為輸入數(shù)據(jù)集；為類標簽，當時，；當時，；且為模糊隸屬度，，為任意小的一個正數(shù)。含有個模式，含有個模式。

1 背景知識

1.1 N-S磁極效應(yīng)

磁體上磁性最強的部分叫磁極。磁體周圍存在磁場，磁體間的相互作用就是以磁場作為媒介的。一個磁體無論多么小都有兩個磁極，可以在水平面內(nèi)自由轉(zhuǎn)動的磁體，靜止時指向南方的磁極叫南極(S極)，指向北方的磁極叫做北極(N極)。之間呈現(xiàn)同性磁極相互排斥、異性磁極相互吸引的現(xiàn)象。

1.2 支持向量機

支持向量機是一種基于統(tǒng)計學(xué)習(xí)理論的機器學(xué)習(xí)方法，核心思想是將結(jié)構(gòu)風險最小化原則引入到分類中，在屬性空間中構(gòu)建最優(yōu)分類超平面，將兩類樣本盡可能的分開[2-3]。

1) 線性形式

式中，為懲罰參數(shù)，控制對錯分樣本的懲罰程度；松弛變量允許錯分樣本的存在，一定程度上提高了算法的泛化能力。

2) 非線性形式：

由Lagrangian定理[13]將原始問題轉(zhuǎn)化為如下對偶形式：

2 MPMMFC

從物理學(xué)角度，MPMMFC可理解為在空間中尋找一個具有磁性的“磁極”分別對兩類樣本作用，根據(jù)樣本的磁性不同對兩類樣本進行分類；從幾何角度，MPMMFC可理解為在空間中尋找一個分類超平面，通過計算樣本與超平面的關(guān)系判斷樣本類屬。

2.1 線性形式

基于上述分析，MPMMFC目標是在樣本空間中試圖構(gòu)建一個超平面，使得一類模式離超平面盡可能的近，另一類模式離超平面盡可能的遠，該優(yōu)化問題可描述為如下最優(yōu)化形式：

MPMMFC借鑒N-S磁極效應(yīng)思想進行分類。從N-S磁極效應(yīng)角度看，若將分類超平面看作磁極，則其對第一類吸引，而對第二類排斥。具體而言，在上述優(yōu)化問題中，約束條件式(4)分別表示兩類樣本受到磁場作用而產(chǎn)生的不同反應(yīng)，即第一類樣本距離分類超平面近，而第二類樣本遠離分類超平面，保證兩類樣本具有良好的可分性。

上述最優(yōu)化問題的對偶形式為：

證明 根據(jù)Lagrangian定理，上述MPMMFC原始問題的Lagrangian方程為：

將式(7)和式(11)帶入到式(6)，可得MPMMFC的對偶形式。

2.2 非線性形式

在非線性情況下，通過滿足Mercer條件的核函數(shù)對輸入空間進行高維映射，然后在高維特征空間中進行模式分類。MPMMFC的核化形式為：

核化對偶形式為：

2.3 最大間隔的求解方法

在求解完式(12)～式(15)的QP問題后，考慮兩類支持向量集合和集合：

其中：

2.4 判別函數(shù)

3 理論分析

3.1 算法復(fù)雜度分析

MPMMFC解決一個具有線性約束的二次規(guī)劃問題，其計算對象主要是核函數(shù)矩陣，空間復(fù)雜度是O(N)，其中為訓(xùn)練樣本數(shù)；其時間復(fù)雜度為O(3)。當面對大規(guī)模分類問題時，MPMMFC的訓(xùn)練時間隨著樣本數(shù)的增加呈指數(shù)級增長。因此MPMMFC不適用大規(guī)模分類問題。目前，一個新的研究成果引起人們的廣泛關(guān)注：文獻[16]提出的核心集向量機(core vector machine, CVM)試圖建立最優(yōu)化問題與最小包含球QP形式的等價性，從而將分類方法的適用范圍從中小規(guī)模數(shù)據(jù)推廣到大規(guī)模數(shù)據(jù)。限于本文篇幅，下一步的工作是探討MPMMFC與最小包含球QP形式的等價性，從而解決MPMMFC無法進行大規(guī)模分類的問題。

3.2 可調(diào)參數(shù)v性質(zhì)

定理 1 設(shè)：

得到如下關(guān)系：

根據(jù)Kuhn-Tucher定理，對偶變量與約束的乘積在鞍點處為0，即，當，由式(8)得：

4 實驗結(jié)果與分析

實驗的目的是驗證MPMMFC和C-SVM、-SVM、OCSVM在UCI數(shù)據(jù)集上的有效性，實驗環(huán)境為2.90 GHz Pentium CPU，2 G RAM，Redhat Enterprise Linux Server 6.0 及matlab2013a。實驗選取的核函數(shù)為高斯核函數(shù)(RBF)：

式中，為訓(xùn)練樣本平均范數(shù)的平方根。

目前，隸屬度函數(shù)的構(gòu)造方法有很多，一般模糊隸屬度函數(shù)主要有兩種：一種是基于樣本到類中心的距離來度量模糊隸屬度的大?。涣硪环N是通過密度來度量模糊隸屬度的大小。本文采用文獻[14]提出的基于K近鄰法思想的模糊隸屬度函數(shù)，通過緊密度來度量模糊隸屬度大小的方法。

定義數(shù)據(jù)點與點之間的距離為：

緊密度的隸屬度定義為：

實驗數(shù)據(jù)集包括一個人工數(shù)據(jù)集以及11個UCI標準數(shù)據(jù)集，其中代表第一類樣本數(shù)，代表第二類樣本數(shù)。數(shù)據(jù)集詳細信息如表1所示。

表1 實驗中所采用的UCI數(shù)據(jù)集

4.1 實驗參數(shù)設(shè)置

本文所提算法MPMMFC、C-SVM、-SVM、OCSVM和SSLM的分類精度和參數(shù)選擇密切相關(guān)，目前參數(shù)選擇的方法主要有：單一驗證估計、留一法和倍交叉驗證法等，本文采取5倍交叉驗證法。

實驗中所有參數(shù)的選擇通過網(wǎng)格搜索策略來選取。對于核函數(shù)(高斯徑向基)，在網(wǎng)格{/8,/4,/2,, 2, 4, 8}中搜索選取。對于C-SVM，懲罰參數(shù)在{0.01, 0.03, 0.05, 0.08, 0.1, 0.1, 0.5, 1, 5, 10}中搜索選取，對于-SVM，參數(shù)在{0.01, 0.1}中搜索選取，為1～9之間的整數(shù)；對于OCSVM，參數(shù)在網(wǎng)格{0.001,0.002,0.004,0.008,0.1,0.2,0.4, 0.8,0.9,1}中搜索選取的；對于SSLM，參數(shù)在網(wǎng)格{5,10,20,30,40,50,60,70,80}中選取，1和2在{0.001, 0.01}中搜索；對于MPMMFC，根據(jù)參數(shù)定理，參數(shù)在網(wǎng)格{1,3,5,8,10,13,15,20,25,30,35,40,45,50,60,80}中搜索，1和2在{0.001,0.01,0.1}中搜索，在網(wǎng)格{0,1,2, 3,4,5}中選擇。

4.2 實驗結(jié)論

通過執(zhí)行5倍交叉驗證來搜索優(yōu)化參數(shù)值，并采用-means度量來評價性能，所有實驗獨立執(zhí)行10次，

4.2.1 人工數(shù)據(jù)集

首先采用人工數(shù)據(jù)集——banana數(shù)據(jù)集來比較MPMMFC算法和C-SVM、-SVM的性能優(yōu)劣。實驗參數(shù)及實驗結(jié)果如圖1所示，圖中橫縱坐標為二維空間的軸坐標。

從圖1a～1c可以看出，MPMMFC在人工香蕉型數(shù)據(jù)集上的支持向量數(shù)量相對于C-SVM、-SVM要少，而且在分類性能上也有較高的準確率。

4.2.2 UCI數(shù)據(jù)集

通過UCI數(shù)據(jù)集來評價MPMMFC和C-SVM、-SVM、OCSVM及SSLM的性能。一類模式和二類模式最優(yōu)實驗參數(shù)、實驗結(jié)果分別如表2和表3所示。

從表2和表3可以看出，和其他幾種方法(C-SVM，-SVM，OCSVM，SSLM)相比，MPMMFC在二類分類和一類分類上都取得了較好或相近的性能，在breast、liver、glass、balance-scale、monks、spectf、heart等數(shù)據(jù)集上，MPMMFC相對于傳統(tǒng)的算法具有明顯的性能優(yōu)勢；而在iris、pima等數(shù)據(jù)集上，MPMMFC和傳統(tǒng)分類方法分類精度基本相當；在blood、seeds數(shù)據(jù)集上，MPMMFC的分類性能略遜于傳統(tǒng)算法-SVM，但分類精度基本可以接受。綜上所述，MPMMFC在核函數(shù)映射后的高維空間，通過模糊隸屬度給不同的樣本增加不同的權(quán)重系數(shù)，使得構(gòu)造的超平面不僅能實現(xiàn)二類模式分類，而且還能解決單類模式分類問題。

5 結(jié) 束 語

受大間隔思想和N-S磁極效應(yīng)理論，本文提出具有N-S磁極效應(yīng)的最大間隔模糊分類器。該方法借鑒N-S磁極效應(yīng)理論，在樣本空間中尋找一個最優(yōu)超平面，使得一類樣本受磁極吸引離超平面盡可能近，另一類樣本受磁極排斥離樣本盡可能遠，而且通過引入模糊技術(shù)，根據(jù)不同樣本的貢獻賦予不同的權(quán)重進一步提高算法的分類性能。人工數(shù)據(jù)集和UCI數(shù)據(jù)集實驗結(jié)果表明，與傳統(tǒng)分類方法C-SVM、-SVM、SSLM、OCSVM相比，MPMMFC在解決二分類以及單類問題上具有一定的優(yōu)勢。

[1] KOBY C, MEHRYAR M, FEMANDO P. Gaussian margin machines[C]//Proceedings of the 12th International Conference on Artificial Intelligence and Statistics. Clearwater Beach Florida: Journal of Machine Learning Research, 2009, 5: 105-112.

[2] VAPNIK V. The nature of statistical learning theory[M]. New York: Springer-Verlag, 1995.

[3] 李航. 統(tǒng)計學(xué)習(xí)方法[M]. 北京: 清華大學(xué)出版社, 2012: 95-135.

LI Hang. Statistical learning methods[M]. Beijing: Tsinghua University Press, 2012: 95-135.

[4] 鄧乃揚, 田英杰. 支持向量機——理論、算法與拓展[M]. 北京: 科學(xué)出版社, 2009.

DENG Nai-yang, TIAN Ying-jie. Support vector machine- theory, algorithms and extension[M]. Beijing: Science Press, 2009.

[5] SCHOLKOPF B, SMOLA A, BARTLET P. New support vector algorithms[J]. Neural Computation, 2000, 12(5): 1207-1245.

[6] SCHOLKOPF B, SMOLA A . Learning with kernels[M]. Cambridge: MIT, 2002.

[7] TAX D M J, DUIN R P W. Support vector data description[J]. Machine Learning, 2004, 54(1): 45-66.

[8] LIN C F, WAN S D. Fuzzy support vector machine[J]. IEEE Transactions on Neural Networks, 2002, 13(2): 464-471.

[9] SHIVASWAMY P K, JEBARA T. Maximum relative margin and data-dependent regularization[J]. Journal of Machine Learning Research, 2010, 11(2): 747-788.

[10] 陶劍文, 王士同. 大間隔最小壓縮包含球?qū)W習(xí)機[J]. 軟件學(xué)報, 2012, 23(6): 1458-1471.

TAO Jian-wen, WANG Shi-tong. Large margin and minimal reduced enclosing ball learning machine[J]. Journal of Software, 2012, 23(3): 1458-1471.

[11] 劉忠寶, 王士同. 基于熵理論和核密度估計的最大間隔學(xué)習(xí)機[J]. 電子與信息學(xué)報, 2011, 33(9): 2187-2194.LIU Zhong-bao, WANG Shi-tong. A maximum margin learning machine based on entropy concept and kernel density estimation[J]. Journal of Electronics & Information Technology, 2011, 33(9): 2187-2194.

[12] WU Ming-rui, YE Jie-ping. A small sphere and large margin approach for novelty detection using training data with outliners[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2009, 31(11): 2088-2092.

[13] HAO P Y. A new fuzzy maximal-margin spherical- structured multi-class support vector machine[C]// Proceedings of the 2013 International Conference on Machine Learning and Cybernetics. Tianjin: Machine Learning and Cybernetics (ICMLC), 2013, 1: 241-246.

[14] 張祥, 徐光佑, 肖小玲. 基于樣本之間緊密度的模糊支持向量機方法[J]. 軟件學(xué)報, 2006, 17(5): 951-958.

ZHANG Xiang, XU Guang-you, XIAO Xiao-ling. Fuzzy support vector machine based on affinity among samples[J]. Journal of Software, 2006, 17(5): 951-958.

[15] QIN Chuan-dong, LIU San-yang. Fuzzy smooth support vector machine with different smooth functions[J]. Journal of Systems Engineering and Electronics, 2012, 23(3): 460-466.

[16] TSANG I W, KWOK J T, CHEUNG P M. Core vector machines: Fast SVM training on very large data sets[J]. Journal of Machine Learning Research, 2005(6): 363-392.

編 輯 葉 芳

Maximum Margin Fuzzy Classifier with N-S Magnetic Pole Effect

LIU Zhong-bao, PEI Song-nian, and YANG Qiu-xiang

(,Taiyuan 030051)

Inspired by space geometry and magnetic pole effect theory, a maximum margin fuzzy classifier with N-S magnetic pole (MPMMFC) is proposed in this paper. The main idea is to find an optimal hyperplane based on N-S magnetic pole effect in order to ensure that the distance between one class and the hyperplane is much closer due to pole attractive and the distance between the other class and the hyperplane is much greater due to repulsion. Moreover, due to the traditional support vector machine (SVM) sensitive to noises and outliers, a fuzzy technology is introduced in this paper to reduce the influence of noises and outliers, and the classification efficiencies and generalization performance are improved further. Experimental results on the synthetic datasets and UCI datasets show that the proposed approaches are effective.

fuzzy technology; kernel method; magnetic pole; pattern classification

TP181

A

10.3969/j.issn.1001-0548.2016.03.012

2014 - 10 - 08；

2015 - 03 - 30

國家社科基金后期資助項目(15FTQ008)

劉忠寶(1981 - )，男，博士后，副教授，主要從事機器學(xué)習(xí)方面的研究.