具有N-S磁極效應的最大間隔模糊分類器

劉忠寶，裴松年，楊秋翔

?

具有N-S磁極效應的最大間隔模糊分類器

劉忠寶，裴松年，楊秋翔

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

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

模糊技術; 核方法; 磁極效應; 模式分類

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

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

受以上方法啟發，本文在N-S磁極效應理論基礎上，結合傳統SVM的大間隔思想，提出一種具有N-S磁極效應的最大間隔模糊分類器MPMMFC，MPMMFC在構建最優決策面時，引入模糊性懲罰參數，降低噪聲和野點數據對決策面的影響，進一步提高泛化性能。

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

1 背景知識

1.1 N-S磁極效應

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

1.2 支持向量機

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

1) 線性形式

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

2) 非線性形式：

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

2 MPMMFC

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

2.1 線性形式

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

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

上述最優化問題的對偶形式為：

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

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

2.2 非線性形式

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

核化對偶形式為：

2.3 最大間隔的求解方法

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

其中：

2.4 判別函數

3 理論分析

3.1 算法復雜度分析

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

3.2 可調參數v性質

定理 1 設：

得到如下關系：

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

4 實驗結果與分析

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

式中，為訓練樣本平均范數的平方根。

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

定義數據點與點之間的距離為：

緊密度的隸屬度定義為：

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

表1 實驗中所采用的UCI數據集

4.1 實驗參數設置

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

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

4.2 實驗結論

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

4.2.1 人工數據集

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

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

4.2.2 UCI數據集

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

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

5 結 束 語

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

[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] 李航. 統計學習方法[M]. 北京: 清華大學出版社, 2012: 95-135.

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

[4] 鄧乃揚, 田英杰. 支持向量機——理論、算法與拓展[M]. 北京: 科學出版社, 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] 陶劍文, 王士同. 大間隔最小壓縮包含球學習機[J]. 軟件學報, 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]. 電子與信息學報, 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]. 軟件學報, 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 - )，男，博士后，副教授，主要從事機器學習方面的研究.