劉忠寶，裴松年，楊秋翔

?

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

劉忠寶，裴松年，楊秋翔

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

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

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

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

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

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

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

1 背景知識(shí)

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

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

1.2 支持向量機(jī)

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

1) 線性形式

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

2) 非線性形式：

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

2 MPMMFC

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

2.1 線性形式

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

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

上述最優(yōu)化問(wèn)題的對(duì)偶形式為：

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

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

2.2 非線性形式

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

核化對(duì)偶形式為：

2.3 最大間隔的求解方法

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

其中：

2.4 判別函數(shù)

3 理論分析

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

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

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

定理 1 設(shè)：

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

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

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

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

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

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

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

緊密度的隸屬度定義為：

實(shí)驗(yàn)數(shù)據(jù)集包括一個(gè)人工數(shù)據(jù)集以及11個(gè)UCI標(biāo)準(zhǔn)數(shù)據(jù)集，其中代表第一類樣本數(shù)，代表第二類樣本數(shù)。數(shù)據(jù)集詳細(xì)信息如表1所示。

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

4.1 實(shí)驗(yàn)參數(shù)設(shè)置

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

實(shí)驗(yàn)中所有參數(shù)的選擇通過(guò)網(wǎng)格搜索策略來(lái)選取。對(duì)于核函數(shù)(高斯徑向基)，在網(wǎng)格{/8,/4,/2,, 2, 4, 8}中搜索選取。對(duì)于C-SVM，懲罰參數(shù)在{0.01, 0.03, 0.05, 0.08, 0.1, 0.1, 0.5, 1, 5, 10}中搜索選取，對(duì)于-SVM，參數(shù)在{0.01, 0.1}中搜索選取，為1～9之間的整數(shù)；對(duì)于OCSVM，參數(shù)在網(wǎng)格{0.001,0.002,0.004,0.008,0.1,0.2,0.4, 0.8,0.9,1}中搜索選取的；對(duì)于SSLM，參數(shù)在網(wǎng)格{5,10,20,30,40,50,60,70,80}中選取，1和2在{0.001, 0.01}中搜索；對(duì)于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 實(shí)驗(yàn)結(jié)論

通過(guò)執(zhí)行5倍交叉驗(yàn)證來(lái)搜索優(yōu)化參數(shù)值，并采用-means度量來(lái)評(píng)價(jià)性能，所有實(shí)驗(yàn)獨(dú)立執(zhí)行10次，

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

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

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

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

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

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

5 結(jié) 束 語(yǔ)

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

[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)計(jì)學(xué)習(xí)方法[M]. 北京: 清華大學(xué)出版社, 2012: 95-135.

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

[4] 鄧乃揚(yáng), 田英杰. 支持向量機(jī)——理論、算法與拓展[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ī)[J]. 軟件學(xué)報(bào), 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] 劉忠寶, 王士同. 基于熵理論和核密度估計(jì)的最大間隔學(xué)習(xí)機(jī)[J]. 電子與信息學(xué)報(bào), 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ī)方法[J]. 軟件學(xué)報(bào), 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

國(guó)家社科基金后期資助項(xiàng)目(15FTQ008)

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