支持向量机(support vector machine, SVM) ^[1]是一种基于统计学习理论的VC维和结构风险最小化原理的机器学习方法，由Cortes和Vapik^[2]于1995年提出。其在解决小样本、非线性和高维模式识别问题中有许多优势，目前已被应用到很多领域，例如文本分类、时间序列分析、模式识别和图像处理等^[3-7]。为了提高支持向量机的性能，学者们提出了许多改进算法。例如最小二乘支持向量机^[8]、近似支持向量机^[9]和基于广义特征值的近似支持向量机^[10]等。2007年，基于广义特征值近似支持向量机的思想，Jayadeva等^[11]提出了孪生支持向量机。和SVM不同，TWSVM是生成两个非平行的分类超平面，使得其中一个超平面尽量接近一类样本，并且尽可能的远离另一类样本。TWSVM^[12-13]将单个大型二次规划问题转化为两个较小的二次规划问题，明显缩短了运行时间。虽然孪生支持向量机的发展时间较短，但由于其坚实的理论基础和出色的性能表现，已经成为机器学习领域的一个研究热点。许多学者对TWSVM的研究做出了贡献，并取得了很多成果。例如光滑孪生支持向量机^[14]、最小二乘孪生支持向量机^[15-17]、模糊孪生支持向量机^[18]和投影孪生支持向量机^[19-20]等。

尽管近年来对TWSVM的研究在算法改进及其应用方面取得了很大的进展，但是仍有不足之处，其中之一就是TWSVM无法很好地处理参数选择问题。参数对分类结果有很大的影响，一个好的参数将直接提升TWSVM的性能。网格搜索^[21]是最普遍的参数选择方法，但是这种方法很耗时。Ding等^[22-23]采用粒子群算法和量子粒子群算法对TWSVM的参数进行优化。Zhai等^[24]将粒子群算法与局部搜索算法结合，提出了一种混合粒子群算法来优化小波孪生支持向量机的参数。随后，Sartakhti等^[25]将最小二乘孪生支持向量机与模拟退火算法结合来提高分类准确率。

人工鱼群算法(artificial fish swarm algorithm, AFSA)^[26]是一种基于动物行为的群体智能优化算法。该算法具有收敛速度快、灵活性强、容错性强、准确率高等优点。本文将人工鱼群算法与孪生支持向量机进行结合，以分类准确率作为适应度值，来对惩罚参数和核参数进行优化，提高算法的有效性。

1 相关理论 1.1 孪生支持向量机

假设在n维实空间Rⁿ中有m个训练样本，其中属于+1类的有m₁个，属于−1类的有m₂个。令 ${{A}} \in {{\rm{R}}^{{m_1} \times n}}$ 表示+1类的训练样本， ${{B}} \in {{\rm{R}}^{{m_2} \times n}}$ 表示−1类的训练样本。TWSVM的训练过程是要在Rⁿ中找到两个非平行的超平面：

$K({{{x}}^{\rm{T}}},{{{C}}^{\rm{T}}}){{w}}{}_1 + {b_1} = 0,{\rm{ }}K({{{x}}^{\rm{T}}},{{{C}}^{\rm{T}}}){{w}}{}_2 + {b_2}{\rm{ = 0}}$

(1)

其中K为核函数, C=[A;B]代表所有的训练样本， ${{{w}}_i}(i = 1,2)$ 是分类超平面的法向量， ${b_i}(i = 1,2)$ 为偏置。

通过求解下面两个二次规划问题可以得到这两个超平面：

$\begin{gathered} \mathop {\min }\limits_{{{w}_1},{{b}_1},{{\xi }_1}} \frac{1}{2}{\left\| {K({A},{{C}^{\rm{T}}}){{w}_1} + {{e}_1}{b_1}} \right\|^2} + {c_1}{e}_2^{\rm{T}}{{\xi }_2} \\ {\rm{s}}{\rm{.t}}{\rm{.\;- (}}K({B},{{C}^{\rm{T}}}){{w}_1} + {{e}_2}{b_1}) \geqslant {{e}_2} - {{\xi }_2},{{\xi }_2} \geqslant 0 \\ \end{gathered} $

(2)

$\begin{gathered} \mathop {\min }\limits_{{{w}_2},{{b}_2},{{\xi }_2}} \frac{1}{2}{\left\| {K({B},{{C}^{\rm{T}}}){{w}_2} + {{e}_2}{b_2}} \right\|^2} + {c_2}{e}_1^{\rm{T}}{{\xi }_1} \\ {\rm{s}}{\rm{.t}}{\rm{. \;(}}K({A},{{C}^{\rm{T}}}){{w}_2} + {{e}_1}{b_2}) \geqslant {{e}_1} - {{\xi }_1},{{\xi }_1} \geqslant 0 \\ \end{gathered} $

(3)

其中c₁和c₂是惩罚参数，e₁和e₂是两个全1列向量， ${{ \xi} _1}$ 和 ${{ \xi} _2}$ 是松弛变量。

测试样本离哪个超平面近，就属于哪一类别，若

$K({{x}^{\rm{T}}},{{C}^{\rm{T}}}){w}{}_r + {b_r} = \mathop {\min }\limits_{i = 1,2} \left| {K({{x}^{\rm{T}}},{{C}^{\rm{T}}}){w}{}_i + {b_i}} \right|$

(4)

则x属于第r类，其中 $r \in \left\{ {1,2} \right\}$ 。

1.2 人工鱼群算法

人工鱼群算法是一种基于群体智能的优化算法，其灵感来自于鱼群行为。在AFSA中，每条人工鱼(artificial fish, AF)根据其当前状态和周围环境状态调整其行为。在每次迭代过程中，人工鱼通过觅食、聚群、追尾和随机这4种行为来更新自己。

假设 ${{{X}}_i} = ({x_1},{x_2},\cdots,{x_n})$ 是人工鱼AF_i的当前状态； ${{{Y}}_i} = f({{{X}}_i})$ 是 ${{{X}}_i}$ 的适应度函数；Visual是人工鱼的视野范围；try_number是觅食行为的最大尝试次数； $\delta $ 是拥挤度因子; Step 表示人工鱼移动的步长；n_f表示视野内的人工鱼数目。对于人工鱼AF_i，其视野内的一个随机状态 ${{{X}}_j}$ 可以用式(5)来表示，其中 ${\rm{Rand}}\left( {} \right)$ 是介于0和1之前的随机数。当满足更新条件时，AF_i用式(6)更新其状态。

${{{X}}_j} = {{{X}}_i} + {\rm{Visual}} \cdot {\rm{Rand}}()$

(5)

${{X}}_i^{t + 1} = {{X}}_i^t + \frac{{{{{X}}_j} - {{X}}_i^t}}{{\left\| {{{{X}}_j} - {{X}}_i^t} \right.\left\| {} \right.}}{\rm{Step}} \cdot {\rm{Rand}}()$

(6)

人工鱼的4种行为描述如下：

1)觅食行为：AF_i用式(5)在其视野范围内随机选择一个状态 ${{{X}}_j}$ 。如果在求极大值问题中， ${Y_i} < {Y_j}$ (在求极小值时为 ${Y_i} > {Y_j}$ ，它们之间可以转换)，则根据式(6)向 ${{{X}}_j}$ 移动一步。否则，再重新随机选择状态 ${{{X}}_j}$ ，判断是否满足要求 ${Y_i} < {Y_j}$ 。如果反复尝试try_number次后，仍不满足要求则执行随机行为。

2)聚群行为：假设 ${{{X}}_c}$ 是视野范围内的中心位置，如果 ${Y_c} > {Y_i}$ 且 ${Y_c}/{n_f} > \delta \cdot {Y_i}$ ，表明伙伴中心有更多食物且不拥挤，则根据式(6)向 ${{{X}}_c}$ 移动一步，否则执行觅食行为。

3)追尾行为：假设 ${{{X}}_b}$ 是视野范围内找到的最好位置，如果 ${Y_b}/{n_f} > \delta \cdot {Y_i}$ ，表明位置 ${{{X}}_b}$ 有更多食物且不拥挤，则根据式(6)向 ${{{X}}_b}$ 的方向前进一步，否则执行觅食行为。

4)随机行为：AF_i在其视野范围内随机选择一个位置，然后向该方向移动一步，它是觅食行为的一个缺省行为。

以上4种行为在不同条件下会相互转换，人工鱼会选择合适的行为以找到更优解的位置。

2 AFSA-TWSVM算法

AFSA-TWSVM的核心思想是通过AFSA找到TWSVM的最优参数。人工鱼AF_i的位置 ${{{X}}_i} = ({x_1},{x_2}, \cdots ,{x_n})$ 对应TWSVM的一组参数，该位置是一个向量，其维数代表参数的个数。AFSA-TWSVM的目标函数是TWSVM的分类准确率，AFSA找到的最佳位置就是TWSVM的最佳参数。

AFSA-TWSVM的算法步骤如下：

1) 初始化设置，包括人工鱼群规模 $N$ 、最大迭代次数 $K$ 、每个人工鱼的初始位置、步长 ${\rm{Step}}$ 、视野 ${\rm{Visual}}$ 、尝试次数 ${\rm{try\_number}}$ 、拥挤度因子 $\delta $ 和TWSVM的参数上下限。

2) 以人工鱼的位置为参数计算孪生支持向量机的分类准确率，将分类准确率作为目标函数进行寻优。得到每个人工鱼的适应度值，并记录全局最优的人工鱼的位置。

3) 每个人工鱼都执行聚群行为和追尾行为，并判断个体是否得到改善。如果得到改善，则选择一个更优行为执行，否则执行觅食行为。

4) 执行人工鱼选择的行为，更新每条人工鱼的位置。

5) 更新全局最优人工鱼的状态。

6) 判断是否达到最大迭代次数，如果是则输出最优解和对应的参数组合，否则迭代次数加1，并跳转到2) 。

AFSA-TWSVM的流程图如图1所示，通过这个流程图可以直观地看出本文所提出算法的过程。

3 实验结果及分析

为了验证基于人工鱼群算法的孪生支持向量机的有效性，选取UCI机器学习数据库中的8个常用数据集来进行测试，数据集的基本特征如表1所示。为了得到更可靠的测试结果，本文使用十折交叉验证方法。实验在Matlab环境下实现，硬件配置为Windows 10操作系统，4 GB内存，250 GB硬盘，i5-2400和3.1 GHz主频CPU的计算机。

在实验中，选取未优化参数的孪生支持向量、基于网格搜索的孪生支持向量机(Grid-TWSVM)和基于粒子群算法的孪生支持向量机(PSO-TWSVM)作为对比实验，与AFSA-TWSVM进行比较。由于Gauss径向基函数具有较好的适应性，故选取该函数作为核函数进行实验。

孪生支持向量机的惩罚参数 ${c_1}$ 、 ${c_2}$ 和高斯核函数相关参数 $R(R = 1/{\sigma ^2})$ 的取值范围为(0,10]。人工鱼群算法的最大尝试次数 ${\rm{try\_number}}$ 为5，视野 ${\rm{Visual}}$ 为0.5，步长 ${\rm{Step}}$ 为0.1，拥挤度因子 $\delta $ 为0.618。粒子群算法中速度上界为1，速度下界为−1，学习因子 ${\eta _1}$ 和 ${\eta _2}$ 都为2。AFSA和PSO的种群规模 $N$ 为10，最大迭代次数为50。

表2给出了4种算法的十折交叉验证的平均分类准确率和标准差，表3给出了在不同数据集上的运行时间，图2是分类准确率效果图。为了更好地体现算法的优越性，用加粗数字代表特定数据集下的最高分类准确率。同时，Mean acc 给出了所有算法的平均准确率，“W-T-L” (win-tie-loss)比较了AFSA-TWSVM与其他算法性能。从中可以看到，本文所提出的AFSA-TWSVM在大多数数据集中都获得了最佳分类准确率，并且平均分类准确率也是最好的。因此可以得出结论，与传统的分类算法相比，AFSA-TWSVM具有更好的分类性能。这是因为AFSA具有较好的全局搜索能力，能避免自己过早地陷入局部最优，从而能更精确地找到参数。由于有更好的参数选择，AFSA-TWSVM提高了TWSVM的分类准确率。

4 结束语

与传统的分类算法相比，TWSVM有许多特有的优势，但也存在着一些不足。本文针对TWSVM参数难以设置的问题，提出了一种基于人工鱼群算法的孪生支持向量机(AFSA-TWSVM)，利用AFSA优化参数，避免了参数选择的盲目性。通过选取UCI数据集进行实验，与TWSVM、Grid-TWSVM和PSO-TWSVM相比，AFSA-TWSVM有更好的分类性能。但是不足之处在于，人工鱼群算法寻优速度较慢，如何进一步提高算法的寻优速度是下一步需要研究的问题。