2016, Vol. 45
[PDF全文]
模式分类是模式识别中的重要内容之一，其通过对有限训练样本的学习得到一个具有较低结构风险和良好泛化能力的分类器[1]。在当前主流的模式分类方法中，支持向量机(SVM)[2,3,4]及其相关变体受到人们的广泛关注，其通过最大化类间间隔实现有效分类。文献[2,3,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 kerneldensity estimation,MLMEK)，MLMEK引入熵和核密度表征分类不确定性和样本分布特征实现分类；文献[12]综合最小包含球和最大间隔思想，提出一种用于新奇检测的小球体和大间隔方法(small sphere large margin，SSLM)，SSLM在高维特征空间中构建最小包含球包围正常样本实现分类；文献[13]提出一种模糊最大间隔球形结构多类支持向量机(fuzzymaximal-margin spherical-structured multi- class SVM,MSM-SVM)，MSM-SVM试图构造正负类间隔最大正类体积最小超球体实现分类。
受以上方法启发，本文在N-S磁极效应理论基础上，结合传统SVM的大间隔思想，提出一种具有N-S磁极效应的最大间隔模糊分类器MPMMFC，MPMMFC在构建最优决策面时，引入模糊性惩罚参数，降低噪声和野点数据对决策面的影响，进一步提高泛化性能。
对本文后续做以下规定：对于一个包含N个模式的二分类问题，给定训练样本集合$T=\{({{x}_{1}},{{y}_{1}},{{s}_{1}}),$$({{x}_{2}},{{y}_{2}},{{s}_{2}}),\cdots,({{x}_{N}},{{y}_{N}},{{s}_{N}})\}$。其中：${{x}_{i}}\in {{R}^{d}}(i=1,2,\cdots,N)$为输入数据集；${{y}_{i}}\in \{1,-1\}$为类标签，当$1\le i\le {{m}_{1}}({{m}_{1}}+{{m}_{2}}=N)$时，${{y}_{i}}=1$；当${{m}_{1}}+1\le i\le {{m}_{1}}+{{m}_{2}}$时，${{y}_{i}}=-1$；且${{s}_{i}}(1\le i\le N)$为模糊隶属度，$\sigma \le {{s}_{i}}\le 1$，σ为任意小的一个正数。${{y}_{i}}=1$含有m1个模式，${{y}_{i}}=-1$含有m2个模式。
1 背景知识 1.1 N-S磁极效应磁体上磁性最强的部分叫磁极。磁体周围存在磁场，磁体间的相互作用就是以磁场作为媒介的。一个磁体无论多么小都有两个磁极，可以在水平面内自由转动的磁体，静止时指向南方的磁极叫南极(S极)，指向北方的磁极叫做北极(N极)。之间呈现同性磁极相互排斥、异性磁极相互吸引的现象。
1.2 支持向量机支持向量机是一种基于统计学习理论的机器学习方法，核心思想是将结构风险最小化原则引入到分类中，在属性空间中构建最优分类超平面，将两类样本尽可能的分开[2,3]。
设超平面方程为$y={{\omega }^{\text{T}}}x+b$,分类间隔为${2}/{\left\| \mathbf{\omega } \right\|}\;$,则最优化问题可描述为如下两种形式。
1)线性形式
| $\begin{align} & \underset{\omega,b,{{\xi }_{i}}}{\mathop{\min }}\,\frac{1}{2}{{\left\| \mathbf{\omega } \right\|}^{2}}+C\sum\limits_{i=1}^{N}{{{\xi }_{i}}} \\ & \text{s}\text{.t}\text{.}{{y}_{i}}({{\omega }^{\text{T}}}{{x}_{i}}+b)\ge 1-{{\xi }_{i}},{{\xi }_{i}}\ge 0,i=1,2,\cdots,N \\ \end{align}$ | (1) |
式中，C为惩罚参数，控制对错分样本的惩罚程度；松弛变量${{\xi }_{i}}$允许错分样本的存在，一定程度上提高了算法的泛化能力。
2)非线性形式：
| $\begin{align} & \underset{\omega,b,{{\xi }_{i}}}{\mathop{\min }}\,\frac{1}{2}{{\left\| \omega \right\|}^{2}}+C\sum\limits_{i=1}^{N}{{{\xi }_{i}}} \\ & \text{s}\text{.t}\text{.}{{y}_{i}}({{\omega }^{\text{T}}}\phi \text{(}{{x}_{i}}\text{)}+b)\ge 1-{{\xi }_{i}},{{\xi }_{i}}\ge 0,i=1,2,\cdots,N \\ \end{align}$ | (2) |
由Lagrangian定理[13]将原始问题转化为如下对偶形式：
| $\begin{align} & \underset{\alpha }{\mathop{\min }}\,\frac{1}{2}\sum\limits_{i=1}^{N}{\sum\limits_{j}^{N}{{{\alpha }_{i}}{{\alpha }_{j}}{{y}_{i}}{{y}_{j}}K({{x}_{i}}{{x}_{j}})}}-\sum\limits_{i=1}^{N}{{{\alpha }_{i}}} \\ & \text{s}\text{.t}\text{.}\sum\limits_{i=1}^{N}{{{\alpha }_{i}}{{y}_{i}}}=0,0\le {{\alpha }_{i}}\le C,i=1,2,\cdots,N \\ \end{align}$ | (3) |
从物理学角度，MPMMFC可理解为在空间中寻找一个具有磁性的“磁极”分别对两类样本作用，根据样本的磁性不同对两类样本进行分类；从几何角度，MPMMFC可理解为在空间中寻找一个分类超平面，通过计算样本与超平面的关系判断样本类属。
2.1 线性形式基于上述分析，MPMMFC目标是在样本空间中试图构建一个超平面，使得一类模式离超平面尽可能的近，另一类模式离超平面尽可能的远，该优化问题可描述为如下最优化形式：
| $\begin{align} & \underset{\omega,\rho,\xi,b}{\mathop{\min }}\,\frac{1}{2}{{\omega }^{\text{T}}}\omega -v\rho+\frac{1}{{{v}_{1}}{{m}_{1}}}\sum\limits_{i=1}^{{{m}_{1}}}{{{\xi }_{i}}{{s}_{i}}}+\frac{1}{{{v}_{2}}{{m}_{2}}}\sum\limits_{j={{m}_{1}}+1}^{N}{{{\xi }_{j}}{{s}_{j}}} \\ & \ \ \ \ \ \ \ \ \ \ \text{s}\text{.t }{{\omega }^{\text{T}}}{{x}_{i}}+b\le {{\xi }_{i}},1\le i\le {{m}_{1}} \\ & \ \ \ \ \ \ \ {{\omega }^{\text{T}}}{{x}_{j}}+b\ge \rho -{{\xi }_{j}},{{m}_{1}}+1\le j\le N \\ & \ \ \ \ \ \ \ \ \ \ \ \xi \ge \text{0,}\rho \ge \text{0,}\sigma \le s\le 1 \\ \end{align}$ | (4) |
式中，${{s}_{i}}(1\le i\le N)$为模糊隶属度；σ为任意小的一个正数；$\rho$为两类样本间隔；用${{\xi }_{i}}{{s}_{i}}$代替松弛因子${{\xi }_{i}}$，使不同样本点在分类时起到不同的作用；v、v1、v2为3个正常数；m1和；m2分别为两类样本数。
上述最优化问题中$\frac{1}{2}{{\omega }^{\text{T}}}\omega $可以确定MPMMFC最优分类面的法向量；$v\rho$表示两类间隔；$\frac{1}{{{v}_{1}}{{m}_{1}}}\sum\limits_{i=1}^{{{m}_{1}}}{{{\xi }_{i}}{{s}_{i}}}$和$\frac{1}{{{v}_{2}}{{m}_{2}}}\sum\limits_{j={{m}_{1}}+1}^{N}{{{\xi }_{j}}{{s}_{j}}}$分别表示具有模糊特性的松弛因子，其中模糊特性通过模糊隶属度函数体现，该模糊特性将不同样本区别对待，松弛因子保证算法具有一定的容错性。
MPMMFC借鉴N-S磁极效应思想进行分类。从N-S磁极效应角度看，若将分类超平面看作磁极，则其对第一类吸引，而对第二类排斥。具体而言，在上述优化问题中，约束条件式(4)分别表示两类样本受到磁场作用而产生的不同反应，即第一类样本距离分类超平面近，而第二类样本远离分类超平面，$\rho$保证两类样本具有良好的可分性。
上述最优化问题的对偶形式为：
| $\begin{align} & \underset{\alpha \in {{R}^{d}}}{\mathop{\min }}\,\frac{1}{2}\sum\limits_{i=1}^{N}{\sum\limits_{j=1}^{N}{{{\alpha }_{i}}{{\alpha }_{j}}{{y}_{i}}{{y}_{j}}{{x}_{i}}x_{j}^{T}}} \\ & \text{s}\text{.t}\text{.0}\le {{\alpha }_{i}}\le \frac{{{s}_{i}}}{{{v}_{1}}{{m}_{1}}},1\le i\le {{m}_{1}} \\ & 0\le {{\alpha }_{j}}\le \frac{{{s}_{j}}}{{{v}_{2}}{{m}_{2}}},{{m}_{1}}+1\le j\le N \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \sum\limits_{i=1}^{N}{{{\alpha }_{i}}{{y}_{i}}}=0 \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ 2v\le \sum\limits_{i=1}^{N}{{{\alpha }_{i}}} \\ \end{align}$ | (5) |
证明 根据Lagrangian定理，上述MPMMFC原始问题的Lagrangian方程为：
| $\begin{matrix} \text{L(}\omega,\rho,\xi,b,\alpha,\beta,\lambda \text{)}=\frac{1}{2}{{\omega }^{\text{T}}}\omega -v\rho+\frac{\text{1}}{{{\nu }_{1}}{{m}_{1}}}\sum\limits_{i=1}^{{{m}_{1}}}{{{\xi }_{i}}{{s}_{i}}}+\\ \frac{1}{{{v}_{2}}{{m}_{2}}}\sum\limits_{j={{m}_{1}}+1}^{N}{{{\xi }_{j}}{{s}_{j}}}\text{+}\sum\limits_{i=1}^{{{m}_{1}}}{{{\alpha }_{i}}({{\omega }^{\text{T}}}{{x}_{i}}+b-{{\xi }_{i}})}- \\ \sum\limits_{j={{m}_{1}}+1}^{N}{{{\alpha }_{j}}({{\omega }^{\text{T}}}{{x}_{j}}+b-\rho+{{\xi }_{j}})}-\sum\limits_{k=1}^{N}{{{\beta }_{k}}{{\xi }_{k}}}-\lambda \rho \\ \end{matrix}$ | (6) |
式中，${{a}_{i}}\ge 0,{{\beta }_{k}}\ge 0,\lambda \ge 0$，它们分别为Lagrangian乘子，在$\text{L(}\omega,\rho,\xi,b,\alpha,\beta,\lambda \text{)}$方程中，分别对原始变量$\omega,\rho,\xi,b$求偏导并令各偏导方程为0，可得：
| $\frac{\partial \text{L}}{\partial \omega }=0\Leftrightarrow \omega=-\sum\limits_{i=1}^{N}{{{\alpha }_{i}}{{y}_{i}}}{{x}_{i}}$ | (7) |
| $\frac{\partial \text{L}}{\partial \rho }=-v+\sum\limits_{j={{m}_{1}}+1}^{N}{{{\alpha }_{j}}}-\lambda=0$ | (8) |
| $\frac{\partial \text{L}}{\partial {{\xi }_{i}}}\text{=}0\Rightarrow \text{0}\le {{\alpha }_{i}}\le \frac{{{s}_{i}}}{{{v}_{1}}{{m}_{1}}}$ | (9) |
| $\frac{\partial \text{L}}{\partial {{\xi }_{j}}}=0\Rightarrow \text{0}\le {{\alpha }_{j}}\le \frac{{{s}_{j}}}{{{\nu }_{2}}{{m}_{2}}}$ | (10) |
| $\frac{\partial \text{L}}{\partial b}=0\Leftrightarrow \sum\limits_{i=1}^{N}{{{\alpha }_{i}}{{y}_{i}}}=0$ | (11) |
将式(7)和式(11)带入到式(6)，可得MPMMFC的对偶形式。
2.2 非线性形式在非线性情况下，通过满足Mercer条件的核函数对输入空间进行高维映射，然后在高维特征空间中进行模式分类。MPMMFC的核化形式为：
| $\begin{align} & \underset{\omega,\rho,\xi,b}{\mathop{\min }}\,\frac{1}{2}{{\omega }^{\text{T}}}\omega -v\rho+\frac{1}{{{v}_{1}}{{m}_{1}}}\sum\limits_{i=1}^{{{m}_{1}}}{{{\xi }_{i}}{{s}_{i}}}+\frac{1}{{{v}_{2}}{{m}_{2}}}\sum\limits_{j={{m}_{1}}+1}^{N}{{{\xi }_{j}}{{s}_{j}}} \\ & \text{s}\text{.t}\text{.}{{\omega }^{\text{T}}}\phi({{x}_{i}})+b\le {{\xi }_{i}},1\le i\le {{m}_{1}} \\ \end{align}$ | (12) |
| $\begin{align} & {{\omega }^{\text{T}}}\phi({{x}_{j}})+b\ge \rho -{{\xi }_{j}},{{m}_{1}}+1\le j\le N \\ & \xi \ge \text{0,}\rho \ge \text{0,}\sigma \le s\le 1 \\ \end{align}$ | (13) |
核化对偶形式为：
| $\begin{align} & \underset{\alpha \in {{R}^{d}}}{\mathop{\min }}\,\frac{1}{2}\sum\limits_{i=1}^{N}{\sum\limits_{j=1}^{N}{{{\alpha }_{i}}{{\alpha }_{j}}{{y}_{i}}{{y}_{j}}K({{x}_{i}},{{x}_{j}})}} \\ & \text{s}\text{.t 0}\le {{\alpha }_{i}}\le \frac{{{s}_{i}}}{{{v}_{1}}{{m}_{1}}},1\le i\le {{m}_{1}} \\ \end{align}$ | (14) |
| $\begin{align} & 0\le {{\alpha }_{j}}\le \frac{{{s}_{j}}}{{{v}_{2}}{{m}_{2}}},{{m}_{1}}+1\le j\le N \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \sum\limits_{i=1}^{N}{{{\alpha }_{i}}{{y}_{i}}}=0 \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 2v\le \sum\limits_{i=1}^{N}{{{\alpha }_{i}}} \\ & \ \ \ \ \ \ \ \ \ \ \omega=-\sum\limits_{i=1}^{N}{{{\alpha }_{i}}{{y}_{i}}\phi }({{x}_{i}})\\ \end{align}$ | (15) |
式中，$K(\mu,v)$为符合Mercer条件的核函数。
2.3 最大间隔的求解方法在求解完式(12)～式(15)的QP问题后，考虑两类支持向量集合和$\alpha $集合：
| $SV{{X}_{1}}=\left\{ {{x}_{i}}|0<{{\alpha }_{i}}<\frac{{{s}_{i}}}{{{\nu }_{1}}{{m}_{1}}},1\le i\le {{m}_{1}} \right\}$ | (16) |
| $SV{{X}_{\text{2}}}\text{=}\left\{ {{x}_{j}}|0<{{\alpha }_{j}}<\frac{{{s}_{j}}}{{{\nu }_{2}}{{m}_{2}}},1\le j\le N \right\}$ | (17) |
| $SV{{\alpha }_{1}}=\left\{ {{\alpha }_{i}}|0<{{\alpha }_{i}}<\frac{{{s}_{i}}}{{{\nu }_{1}}{{m}_{1}}},1\le i\le {{m}_{1}} \right\}$ | (18) |
| $SV{{\alpha }_{2}}=\left\{ {{\alpha }_{j}}|0<{{\alpha }_{j}}<\frac{{{s}_{j}}}{{{\nu }_{2}}{{m}_{2}}},{{m}_{1}}+1\le j\le N \right\}$ | (19) |
根据KKT条件，对于$SV{{X}_{1}}$，式(13)变成了一个所有松弛因子为0的等式，即：
| ${{\omega }^{\text{T}}}\phi({{x}_{i}})+b=0\text{ }1\le i\le {{m}_{1}}$ | (20) |
同理对于$SV{{X}_{2}}$，式(15)也变成了一个等式，即：
| ${{\omega }^{\text{T}}}\phi({{x}_{j}})+b=\rho \text{ }{{m}_{1}}+1\le j\le N$ | (21) |
因此设${{n}_{1}}=\left| SV{{X}_{1}} \right|$，${{n}_{2}}=SV{{X}_{2}}$，由式(20)和式(21)得：
| ${\rho ^ * }{\rm{ = }}\frac{{\rm{1}}}{{{n_2}}}{{\rm P}_2} - \frac{1}{{{n_1}}}{{\rm P}_1}$ | (22) |
| ${b^ * } = - \frac{1}{{{n_1}}}{{\rm P}_1}$ | (23) |
其中：
| $\begin{array}{l} {{\rm P}_{\rm{1}}} = \sum\limits_{{\alpha _i} \in SV{\alpha _1}} {\sum\limits_{{{\bf{x}}_i},{{\bf{x}}_j} \in SV{X_1}} {{\alpha _i}K({x_i},{x_j})} } \\ {{\rm P}_2} = \sum\limits_{{\alpha _j} \in SV{\alpha _2}} {\sum\limits_{{{\bf{x}}_i},{{\bf{x}}_j} \in SV{X_2}} {{\alpha _j}K({x_i},{x_j})} } \end{array}$ |
为了判别一个新模式${{x}_{i}}={{R}^{d}}$的类属，MPMMFC通过比较该模式与构造出的超平面的距离是否小于0来确定该模式的类属。MPMMFC决策函数为：
| $f = {\mathop{\rm sgn}} ({\omega ^ * }\phi (x){\rm{ + }}{b^ * })$ | (24) |
求得$\alpha $后，可通过式(24)得到${{\mathbf{\omega }}^{*}},{{b}^{*}}$。
3 理论分析 3.1 算法复杂度分析MPMMFC解决一个具有线性约束的二次规划问题，其计算对象主要是核函数矩阵，空间复杂度是O(N2)，其中N为训练样本数；其时间复杂度为O(N3)。当面对大规模分类问题时，MPMMFC的训练时间随着样本数的增加呈指数级增长。因此MPMMFC不适用大规模分类问题。目前，一个新的研究成果引起人们的广泛关注：文献[16]提出的核心集向量机(core vector machine,CVM)试图建立最优化问题与最小包含球QP形式的等价性，从而将分类方法的适用范围从中小规模数据推广到大规模数据。限于本文篇幅，下一步的工作是探讨MPMMFC与最小包含球QP形式的等价性，从而解决MPMMFC无法进行大规模分类的问题。
3.2 可调参数v性质本文称对应Lagrangian乘子${{\alpha }_{i}}>0$的训练样本${{x}_{i}}(1\le i\le N)$为支持向量(SV)，对应的松弛变量${{\xi }_{i}}>0(1\le i\le N)$的训练样本${{x}_{i}}(1\le i\le N)$为间隔误差(ME)。
定理1设：
| $\text{M}{{\text{E}}_{1}}=\left\{ {{s}_{i}}\left| {{\xi }_{i}}>0,1\le i\le {{m}_{1}} \right.\right\}$ | (25) |
| $M{{E}_{2}}=\left\{ {{s}_{j}}\left| {{\xi }_{i}}>0,{{m}_{1}}\text{+}1\le j\le N \right.\right\}$ | (26) |
| ${{S}_{1}}=\left\{ {{s}_{i}}\left| {{a}_{i}}>0,1\le i\le {{m}_{1}} \right.\right\}$ | (27) |
| ${{S}_{2}}=\left\{ {{s}_{j}}\left| {{a}_{i}}>0,{{m}_{1}}\text{+}1\le j\le N \right.\right\}$ | (28) |
得到如下关系：
| $\frac{1}{{{m}_{1}}}\sum\limits_{{{s}_{i}}\in \text{M}{{\text{E}}_{1}}}{{{s}_{i}}}\le v{{v}_{1}}\le \frac{1}{{{m}_{1}}}\sum\limits_{{{s}_{i}}\in {{S}_{1}}}{{{s}_{i}}}$ | (29) |
| $\frac{1}{{{m}_{2}}}\sum\limits_{{{s}_{j}}\in \text{M}{{\text{E}}_{2}}}{{{s}_{j}}}\le v{{v}_{2}}\le \frac{1}{{{m}_{2}}}\sum\limits_{{{s}_{j}}\in {{S}_{2}}}{{{s}_{j}}}$ | (30) |
$v,{{v}_{1}},{{v}_{2}}$同时控制着支持向量的下界和间隔误差的上界。
证明 由于$\sigma \le {{s}_{i}}\le 1$，则式(14)约束条件变为：
| $0\le {{\alpha }_{i}}\le \frac{{{s}_{i}}}{{{v}_{1}}{{m}_{1}}}\le \frac{1}{{{v}_{1}}{{m}_{1}}},1\le i\le {{m}_{1}}$ | (31) |
根据Kuhn-Tucher定理，对偶变量与约束的乘积在鞍点处为0，即$\lambda \rho=0$，当$\rho >0$，由式(8)得：
| $-v+\sum\limits_{j={{m}_{1}}+1}^{N}{{{\alpha }_{j}}}=0\Rightarrow \sum\limits_{j={{m}_{1}}+1}^{N}{{{\alpha }_{j}}}=v$ | (32) |
由式(13)和式(26)得$\sum\limits_{i=1}^{{{m}_{1}}}{{{\alpha }_{i}}}=v$，当${{\xi }_{i}}>0$时，${{a}_{i}}=\frac{{{s}_{i}}}{{{v}_{1}}{{m}_{1}}}$对于所有正类间隔误差成立，则有：
| $\sum\limits_{i=1}^{{{m}_{1}}}{{{\alpha }_{i}}}=v\ge \frac{1}{{{v}_{1}}{{m}_{1}}}\sum\limits_{{{s}_{i}}\in \text{M}{{\text{E}}_{1}}}{{{s}_{i}}}$ | (33) |
由式(26)知，每个正支持向量至多贡献$\frac{{{s}_{i}}}{{{v}_{1}}{{m}_{1}}}$，则得：
| $\sum\limits_{i=1}^{{{m}_{1}}}{{{\alpha }_{i}}}=v\le \frac{1}{{{v}_{1}}{{m}_{1}}}\sum\limits_{{{s}_{i}}\in {{S}_{1}}}{{{s}_{i}}}\Rightarrow v\le \frac{1}{{{v}_{1}}{{m}_{1}}}\sum\limits_{{{s}_{i}}\in {{S}_{1}}}{{{s}_{i}}}$ | (34) |
由式(28)和式(29)可得$\frac{1}{{{m}_{1}}}\sum\limits_{{{s}_{i}}\in \text{M}{{\text{E}}_{1}}}{{{s}_{i}}}\le v{{v}_{1}}\le \frac{1}{{{m}_{1}}}\sum\limits_{{{s}_{i}}\in {{S}_{1}}}{{{s}_{i}}}$，对于负类，同理可得式(25)。
4 实验结果与分析实验的目的是验证MPMMFC和C-SVM、ν-SVM、OCSVM在UCI数据集上的有效性，实验环境为2.90GHzPentium CPU，2GRAM，RedhatEnterprise Linux Server 6.0及matlab2013a。实验选取的核函数为高斯核函数(RBF)：
| $K(x,y)=\exp \left(\frac{{{\left\| x-y \right\|}^{2}}}{{{\sigma }^{2}}} \right)$ | (35) |
式中，σ为训练样本平均范数的平方根。
目前，隶属度函数的构造方法有很多，一般模糊隶属度函数主要有两种：一种是基于样本到类中心的距离来度量模糊隶属度的大小；另一种是通过密度来度量模糊隶属度的大小。本文采用文献[14]提出的基于K近邻法思想的模糊隶属度函数，通过紧密度来度量模糊隶属度大小的方法。
定义数据点与点之间的距离为：
| $\begin{align} & {{d}_{ij}}=\left| {{x}_{i}}-{{x}_{j}} \right|\text{ }i,j\in l,i\ne j \\ & {{d}_{i1}}\le {{d}_{i2}}\le \cdots \le {{d}_{i(l-1)}} \\ \end{align}$ | (36) |
紧密度的隶属度定义为：
| $\left\{ \begin{matrix} {{b}_{i}}={1}/{\sum\limits_{j=1}^{k}{{{d}_{ij}}}}\;\\ B=\max({{b}_{1}},{{b}_{2}},\cdots,{{b}_{l}})\\ {{s}_{i}}={{{b}_{i}}}/{B}\;\\ \end{matrix} \right.$ | (37) |
实验数据集包括一个人工数据集以及11个UCI标准数据集，其中m1代表第一类样本数，m2代表第二类样本数。数据集详细信息如表 1所示。
| 表1 实验中所采用的UCI数据集 |
 |
本文所提算法MPMMFC、C-SVM、ν-SVM、OCSVM和SSLM的分类精度和参数选择密切相关，目前参数选择的方法主要有：单一验证估计、留一法和K倍交叉验证法等，本文采取5倍交叉验证法。
实验中所有参数的选择通过网格搜索策略来选取。对于核函数(高斯径向基)，${{\sigma }^{2}}$在网格{${{\sigma }^{2}}$/8,${{\sigma }^{2}}$/4,${{\sigma }^{2}}$/2,${{\sigma }^{2}}$,2${{\sigma }^{2}}$,4${{\sigma }^{2}}$,8${{\sigma }^{2}}$}中搜索选取。对于C-SVM，惩罚参数C在{0.01,0.03,0.05,0.08,0.1,0.1,0.5,1,5,10}中搜索选取，对于v-SVM，参数v在{0.01k,0.1k}中搜索选取，k为1～9之间的整数；对于OCSVM，参数v在网格{0.001,0.002,0.004,0.008,0.1,0.2,0.4,0.8,0.9,1}中搜索选取的；对于SSLM，参数v在网格{5,10,20,30,40,50,60,70,80}中选取，v1和v2在{0.001,0.01}中搜索；对于MPMMFC，根据参数定理，参数v在网格{1,3,5,8,10,13,15,20,25,30,35,40,45,50,60,80}中搜索，v1和v2在{0.001,0.01,0.1}中搜索，k在网格{0,1,2,3,4,5}中选择。
4.2 实验结论通过执行5倍交叉验证来搜索优化参数值，并采用g-means度量来评价性能，所有实验独立执行10次，实验结论取平均值，采用几何度量方法$g=\sqrt{{{a}^{+}}{{a}^{-}}}$评价算法性能，其中${{a}^{+}}$和${{a}^{-}}$分别为正类和负类的分类精度。该方法同时考虑了正类和负类的分类效果而被广泛用于处理不平衡数据集问题。
4.2.1 人工数据集首先采用人工数据集——banana数据集来比较MPMMFC算法和C-SVM、ν-SVM的性能优劣。实验参数及实验结果如图 1所示，图中横纵坐标为二维空间的xy轴坐标。
 |
| 图1 香蕉型数据集模式分类结果 |
从图 1a～1c可以看出，MPMMFC在人工香蕉型数据集上的支持向量数量相对于C-SVM、v-SVM要少，而且在分类性能上也有较高的准确率。
4.2.2 UCI数据集通过UCI数据集来评价MPMMFC和C-SVM、v-SVM、OCSVM及SSLM的性能。一类模式和二类模式最优实验参数、实验结果分别如表 2和表 3所示。
| 表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的分类性能略逊于传统算法v-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. |