吕卓，谢松云，赵金，赵海涛

（1.西北工业大学电子信息学院，陕西西安710129；2.第四军医大学第一附属医院放射科，陕西西安710032）

支持向量机的优点是在处理小样本学习问题上具有独到的优越性[1]，与人工神经网络相比，支持向量机避免了“维数灾难”。然而，SVM研究的过程中，对于大规模问题，当样本数很大时[2]，一般的二次规划求解方法已不再适用，除了对大规模数据进行有效的预处理外，许多学者对算法本身进行了改进，从而加快了训练速度，减少了对内存的需求，同时提高了分类精度和泛化能力。fMRI技术能实时跟踪信号的改变，例如在仅几秒钟内发生的思维活动，或认知实验中信号的变化，时间分辨率达到1 s。fMRI具有非常好的空间分辨率和时间分辨率。这些特性为对人脑进行多种新颖的认知神经科学的实验提供了有利条件，并可进行脑病理的研究，具有相当大的临床意义。

1 支持向量机（SVM）基本算法

1.1 简单两类线性可分分类问题

给定训练样本集（x，y），y=1或-1两类假设分类面H的方程为wx+b=0。如果y=1，则wx+b＞0，否则wx+b＜0任意样分类面就是寻找最大的D以及相关的权系数向量w和偏置b，这一问题可以描述为以下的优化问题为如下的拉格朗日函数：

求拉格朗日函数关于w和b的最小值和关于α的最大值问题。α的最大值问题的Wolfe对偶形式：

而且最优解必须满足Karush-Kuhn-Tucher（KKT）条件。

1.2 复杂两类线性不可分分类问题

对于复杂两类线性不可分问题，首先通过一非线性映射φ将输入空间映射到高维特征空间F：x→φ（x）=（φ1（x），φ2（x），…φn（x）…），原空间中的对偶优化问题变为：

拉格朗日乘子法求得的最优分类判别函数为：

式中，对于高维空间的运算，靠的是内积运算来实现：

式中内积函数K（xi，x）为核函数，且必须满足Mercer条件。

2 支持向量机（SVM）改进算法

2.1 SSVM（Smooth SVM）[4-5]

标准的SVM是一个凸二次规划问题，求解复杂，可以通过一定的变形技巧，使其转化为光滑的无约束问题，再利用经典的最优化方法求解。取（n+1）维空间中的间距为去掉约束条件γ≥0。其最优化问题变为：

利用光滑技术，得到变形后光滑的无约束最优化问题：

2.2 PSVM（Proximal SVM）[5]

将SVM中不等式约束变成等式约束，边界超平面变成最邻近超平面，两类点在两超平面附近聚类，同时整合了松弛因子的作用，最后求解。改进后的分类优化问题为：

2.3 LPSVM（Linear programming SVM）[6]

2.4 NSVM（Newton SVM）[7]

将最优性条件用于原问题解的对偶问题，得对偶变量u的迭代公式，再得到隐式的Lagrangian无约束最小问题，最后用有穷Newton方法求解该无约束最小问题Qu/2-eu得到变量u的迭代公式：ui+1=Q-1（e+（（Qui-e）-αui）+）i=1，2…0 p α p 2/v得到隐式Lagrangian无约束最小问题：

最后用有穷Newton方法解该问题。

3 基于SVM的fMRI图像分类方法及性能比较

本实验所用数据来自西安市第四军医大学西京医院核磁共振室，选取右利手的健康人为受试者进行脑功能核磁共振图像的测试。

实验选取fMRI部分数据：选取靠近中心的6层图像数据，分前后两组测试，每组3层数据，60幅图像，所测得的部分原始图像如图1所示。分类矩阵中，以每幅fMRI图像作为

图1 功能核磁共振fMRI图像Fig.1 fMRI images

分类矩阵中，以每幅fMRI图像作为行向量，送入分类器后，随机打乱样本顺序，前50%数样本据为训练样本，其余为检验样本。

3.1 分类时间比较

由于SVM分类时间179.53 s，与其他分类算法运行时间相差多个数量级，所以比较时间时不加入SVM运行时间的比较。如图2所示。

原始SVM算法计算方式主要是将原问题最终转化为一个二次凸规划优化问题来解。本实验所用的数据是fMRI图像，每一幅图像由128×128个像素点组成，分类器所用分类矩阵为120维，训练集的规模比较大，支持向量很多。这样解二次凸规划优化问题时，即解下式：

图2 运行时间比较图（单位/s）Fig.2 Runtime comparison（s）

计算代价比较大，支持向量机的学习过程需要占用大量的内存，寻优速度非常缓慢。原始SVM算法运行时间问题的主要症结在于求解二次凸规划优化问题计算代价太大。

PSVM算法：由于PSVM算法将SVM中不等式约束变成等式约束，边界超平面变成最邻近超平面，两类点在两超平面附近聚类。相对于原始算法，求解问题变成下式：

不再是计算复杂的二次凸规划优化问题，而只需求解一组线性等式。所以PSVM运算速度极快，实验数据120维的计算代价相比较原始SVM算法小得多。

NSVM算法：分析发现，NSVM算法对于计算速度的提升方式与PSVM相同，但思路不同。PSVM直接对二次凸规划优化问题进行改进，而NSVM算法从SVM算法的最优解所必须满足的条件——KKT条件出发，寻求出了另一种巧妙的逆向思路。需要求解的：

所得到的最优解必须满足Karush-Kuhn-Tucher（KKT）条件。

找到KKT条件的必要充分最优条件，得对偶变量u的迭代公式，也就是解的循环公式。同时得到隐式的Lagrangian无约束最小问题，并用有穷Newton方法求解该问题，且能在很少的次数内达到全局最优解。

同样的，NSVM也并不是直接求解对偶问题，避免了计算代价过大，速度得到了极大的提升。

SSVM算法：与PSVM、NSVM类似，SSVM算法也将二次凸规划问题回避，但是使用的方式、思路都不同。SSVM的计算方式是通过一定的变形技巧，利用光滑技术，将求解二次凸规划问题中的不等式约束问题，转化为光滑的等式约束问题：

这个转化后光滑的等式约束问题可以用快速Newton-Armijo算法求解，这是一种成熟的光滑算法。同时，这种算法能保证全局收敛到唯一解，速度较快，但比PSVM、NSVM略慢。

LPSVM算法：与以上改进算法不同，LPSVM算法没有在解二次凸规划优化问题上寻求改进，而是引入一种处理输入空间特征的方法求解。这种方法的思路是：首先处理输入空间中的数据集，将对支持向量没有做贡献的输入特征进行筛除。

由原始SVM算法的原理可知，最优分类平面的确定只取决于支持向量（SV），如果输入的训练集中，较多特征对确定特征没有贡献，将会扰乱训练过程，拖延学习时间，最终使寻优时间过长。LPSVM即是采用一种选择性抑制输入空间特征的快速牛顿算法，用于SVM分类器的线性规划方程，使寻优时间缩短，同时也从另一种意义上降低了求解二次凸规划优化问题的复杂度。对于改善分类速度有显著的功效。

3.2 分类精确度比较

5种分类算法的分类精度均不高，仅50～60%。如图3所示。

对于SVM算法，训练集的样本点不能过多或者过少，需要包括求解问题的不同状态和反映求解问题的重要特征。输入中所含的特征应该只与求解问题有关，无关的输入会干扰支持向量（SV）的选取，即噪声干扰。各种SVM算法对噪声干扰十分敏感。

图3 原始数据分类精度比较图（单位/正识率）Fig.3 Comparison of data classification accuracy upon the original data（percents）

因为本次实验的数据是未经过预处理的医学图像fMRI图像，在fMRI图像采集过程中，各种形式的运动都是引起信号波动的噪声源，例如受试者头部在实验过程中未完全固定而发生的的刚体运动、心跳和呼吸周期引起头部的节律性运动等。这些噪声的特点是低频或宽带范围，干扰了SVM及其改进算法算法找到最佳的决策函数，从而降低了总体的分类精确度。

以上方法对于原始采集的fMRI图像数据分类精度均太低，在工程应用中达不到应用要求，使得对比分类精度失去意义。因此，引入PCA（Principal Components Analysis主成分分析）算法对原始采集数据进行预处理。计算主成分的目的是将高维数据投影到较低维空间，进行特征提取的同时剔除了无关或关系较少的成分。在SVM及其改进算法进行分类时，伪支持向量（Pseudo Support Vector）减少，提高了总体的分类精度，如图4所示。

图4 预处理数据分类精度比较图（单位/正识率）Fig.4 Comparison of data classification accuracy upon the preprocessed data（percents）

3.2.1 算 法误差分析

PSVM的改进思路是针对于分类平面的，将最优分类平面用最邻近分类平面代替，作了一定程度上的近似，但对于分类，近似的影响几乎可忽略。LPSVM算法是首先处理输入空间中的数据集，将对选取支持向量贡献小的输入特征数据进行筛除，也就是对训练样本进行带阈值的分类，这样就进一步，本实验数据量比较大，阈值以下的训练样本对支持向量的选择也有贡献，筛除了它们后，算法选取的支持向量的准确度就受到影响。支持向量选取的准确度直接影响着算法的分类精确度，所以PSVM、LPSVM算法均作了不同程度的近似，分类精确度下降了。NSVM所用的有穷Newton方法、SSVM进行了光滑近似，保留了函数的严格凸和可微属性，采用用的快速Newton-Armijo算法都在解优化问题时进行一定得近似，出现一定的误差，也导致了最后分类精度的下降。

3.2.2 各 改进SVM算法适用范围影响分析

PSVM算法代码简单，能处理大规模问题（几千个点），分类精度与SVM相当，但所需时间急剧减少。PSVM算法的主要优势在于分类速度的极大提高。

NSVM方法采用穷Newton方法求解该无约束最小问题，在很少的次数内达到全局最优解；LPSVM将输入空间进行了有选择的抑制，也可以看做是进行了预处理特征提取，它们两种算法主要优势都在于可以处理极高维数的数据集。

SSVM算法采用光滑技术进行近似时，保留了函数的严格凸和可微属性，应用光滑技术的重要目的是使SSVM算法可以推广到用完全任意核解决非线性分类问题。

4 结论

本实验采用的是fMRI图像，这4种改进算法在不同方面存在优缺点，所以它们在本实验中的表现必然会存在差异，我们也可以通过这次实验，寻求到相对适合fMRI图像分类的算法，即在分类精度与计算速度上都体现出优越性的改进算法：PSVM算法。

[1]唐发明.基于统计学习理论的支持向量机算法研究[D].武汉：华中科技大学，2005.

[2]谢松云，张海军，赵海涛，等.基于SVM的脑功能分类与识别方法研究[J].中国医学影像技术，2007（1）：125-128.

XIE Song-yun，ZHANG Hai-jun，ZHAO Hai-tao，et al.Classification and recognition of brain function based on support vector machine[J].China Medical Imaging Technology，2007（1）：125-128.

[3]XIE Song-yun，GUO Rong，LI Ning-fei，et al.Brain fMRI processing and classification based on combination of PCA and SVM[J].IJCNN’09，2009:3384-3389.

[4]熊金志，胡金莲，袁华强.光滑支持向量机的原理和进展[J].计算机工程，2008，34（13）:172.

XIONG Jin-zhi，HU Jin-lian，YUAN Hua-qiang.Principles and advances of smooth support vector machine[J].Computer Engineering.2008，34（13）：172.

[5]Jye L Y，Mangasarian O L.SSVM:a smooth support vector machine for Classification[J].Computational Optimization and Application，2001，20（1）:5-22.

[6]XIE Song-yun，WANG Peng-wei，ZHANG Hai-jun，et al.Research on the classification of brain function based on SVM[J].The 2nd International Conference on Bioinformatics and Biomedical Engineering.2008（5）:1931-1934.

[7]Fung G，Mangasarian O L.Finite newton method for lagrangian support vector machine classification[J].Neurocomputing，2003，55（1-2）:39-55.

[8]张伟平.行为刺激下脑功能核磁共振图像处理新方法研[D].西安：西北工业大学，2008.