基因云馆新一代信息数据库

简介

基因芯片技术在最近几年里得到了蓬勃发展，紧跟着到来的是大量的基因序列数据，在如此海量的生物信息数据库里，蕴藏着许许多多的重要信息。因此，通过有效的手段，从基因表达数据里准确提取生物特征，比较正常与患者之间的基因表达差异，找出影响样本类别的特征基因，实现对关键基因的准确识别，对疾病的诊断以及治疗有重要的意义。 支持向量机(Support Vector Machine, SVM) 是Corinna Cortes和Vapnik等于1995年首先提出的一种有监督的学习方法，它通过训练一种“分类器”来辨别与已知的共调控基因表达类型相近的新基因，与经典的无监督聚类方法不同，该方法建立在已有的数据信息基础之上，并且有改进现有数据信息的能力。 由于基因芯片表达谱数据集具有数据量大、维数高、样本少等特点，可以使用SVM来对基因芯片数据进行分析。

1.2.1 优势    它是专门针对有限样本的情况，其目标是得到现有信息下的最优解，而不是样品趋于无穷大时的渐近最优值；算法最终将转化为一个二次型寻优问题，从理论上说，得到的将是全局最优点，会舍弃个别偏差较大的数据，解决在网络神经法中无法避免的局部极值问题，使分类结果富有整体感；与无监督的学习方法相比，支持向量机能够运用更多的距离或相似性度量，其中包括线性函数和非线性函数，使算法可以更精确地考虑基因表达谱向量之间的关系。    支持向量机之所以越来越多地应用于基因芯片数据挖掘和数据分析领域，是因为在聚类过程中更可能的利用了已有的生物学信息，使分类的结果更具有生物学意义。

SVM 算法

分类原理

SVM方法是通过一个非线性映射，把样本空间映射在一个更高维特征空间中，使得在以前样本空间中非线性可分的问题转化为在高维特征空间中的线性可分的问题。SVM方法灵巧地化解了一般的升维都会带来计算的复杂化的难题：通过核函数的应用，就不需要知道非线性映射的显式表达式，可以在低维空间进行高维度映射过后的计算，使得计算复杂程度大为降低。 简单的说，给定一定数量数据点，它们分别属于两个不同的类，线性分类器SVM便能够把这些数据分成两类。假设用x 来表示数据点，用y 的正负来表示这两个类别，一个线性分类器的训练目标便是要在多维的数据空间中找到一个超平面，这个超平面可以用以下方程表示：

W•x + b = 0

权重w

接下来还需要介绍的就是权重w，权重w为本实验判断此基因是否为关键基因的关键量。简单的理解，权重w可以认为是样本点到分类超平面的距离，如下图所示。在对一个特征的分类之中，用SVM算法进行分类确定超平面之后，获取此分类中各数据点权重绝对值|w|的平均值，即为此特征的权重wi。 在该分类超平面中消除权重趋近于零的特征，并剔除权重较小的特征，然后对各个特征wi按照大小顺序进行排序，取前几个权重较大的特征形成一个特征子集。如果每一个基因是是一个特征，那么最终得到的特征子集即为关键基因集。这样经过一步步地重复操作，进一步筛选，便可以渐渐的缩小关键基因集。    

对于很多分类问题，例如最简单的，一个平面上的两类不同的点，如何将它用一条直线分开？在平面上我们可能无法实现，但是如果通过某种映射，将这些点映射到其它空间（比如说球面上等），我们有可能在另外一个空间中很容易找到这样一条所谓的“分隔线”，将这些点分开。

SVM基本上就是这样的原理，但是SVM本身比较复杂，因为它不仅仅是应用于平面内点的分类问题。SVM的一般做法是：将所有待分类的点映射到“高维空间”，然后在高维空间中找到一个能将这些点分开的“超平面”，这在理论上是被完全证明了是成立的，而且在实际计算中也是可行的。

但是仅仅找到超平面是不够的，因为在通常的情况下，满足条件的“超平面”的个数不是唯一的。SVM 需要的是利用这些超平面，找到这两类点之间的“最大间隔”。为什么要找到最大间隔呢？我想这与SVM的“推广能力”有关，因为分类间隔越大，对于未知点的 判断会越准确，也可以说是“最大分类间隔”决定了“期望风险”，总结起来就是：SVM要求分类间隔最大，实际上是对推广能力的控制。

说到SVM的基本原理，有两个概念不能不提到，一个就是上面说到的“最大分类间隔面”，另一个是关于“VC”的概念。最大分类间隔面比较好懂，从字面上也能知道它的大致含义。但是VC维的概念，我有必要在这里着重说一下。

VC维（Vapnik-Chervonenkis Dimension）的概念是为了研究学习过程一致收敛的速度和推广性，由统计学习理论定义的有关函数集学习性能的一个重要指标。

传统的定义是：对一个指标函数集，如果存在H 个样本能够被函数集中的函数按所有可能的2的K次方种形式分开，则称函数集能够把H个样本打散；函数集的VC维就是它能打散的最大样本数目H。若对任意数 目的样本都有函数能将它们打散，则函数集的VC维是无穷大，有界实函数的VC维可以通过用一定的阀值将它转化成指示函数来定义。

VC维反映了函数集的学习能力，VC维越大则学习机器越复杂（容量越大），遗憾的是，目前尚没有通用的关于任意函数集VC维计算的理论，只对一些特殊的函数集知道其VC维。例如在N维空间中线形分类器和线形实函数的VC维是n+1。

“推广能力”

推广能力”是分类问题（classification，也称为模式识别问题，在概率统计中则称为判别分析问题）的一个指标。所谓推广就是在求得决策函数f(x)后，对一个新的输入x，按照y=f(x)推断出x相应的输出y。“推广能力”就是描述推广优劣的一种度量。

那么，决策函数f(x)是怎么回事？这要从分类问题的（数学语言描述的）定义说起，参见（邓乃扬等人的《数据挖掘中的新方法——支持向量机》，科学 出版社，2005）。通俗的讲。就是一个表示x,y之间关系的函数，而x,y就是样本中的一对数据。其中x代表输入，y代表类别。分类问题就是找到这个决 策函数f(x)，而对于新的输入x，能够判断其所属类别y则是个预测（回归）问题。

简单世界和复杂世界

统计学习理论（Vapnik V N, 许建华 张学工译, 电子工业出版社, 2004）是SVM的坚实的理论基础，其作者指出，在可以只用几个变量描述的简单世界中，传统的科学哲学的目标是“发现普遍的自然规律”。但是，这一目标 在需要用很多变量描述的复杂世界中不一定可行。因此，在一个复杂世界中，我们需要放弃寻找一般规律的目标，而考虑其他目标。

在Vapnik的The nature of statistical learning theory(1995年)一书中，作者对复杂世界的推理提出了如下法则：“在解决一个感兴趣的问题时，不要把解决一个更一般的问题作为一个中间步骤。要 试图得到所需要的答案，而不是更一般的答案。很可能你拥有足够的信息来很好地解决一个感兴趣的特定问题，但却没有足够的信息来解决一个一般性的问题。”

东亚人就是这种理论的坚决执行者，“他们注重在其所处环境中的对象，很少关心类别和普适规则，基于在特定时刻施加于对象个体上的各种作用来解释其行 为。没有太多地采用形式逻辑，而常常采用各种辩证推理规则，包括综合、超越和归一。”而西方人则注重对象及其特性（即一般性规律），并且用这种假定的基于 分类的规则来预测和解释对象的行为（这样经常是错误的）。形式逻辑就是西方人的“法宝”，在推理、分类和规则验证中发挥了作用。

从机器学习到支持向量机

机器学习(Machine Learning, ML)的目的是根据给定的训练样本求对某系统输入输出之间依赖关系的估计，使它（这种关系）能够对未知输出做出尽可能准确地预测。机器学习至今没有一个精 确的公认的定义。作为人工智能(Artificial Intelligence, AI)的一个重要研究领域，ML的研究工作主要围绕学习机理、学习方法和面向任务这三个基本方面进行研究。模式识别、函数逼近和概率密度估计是三类基本的ML问题。

从数学的角度来考虑，机器学习问题就是已知n个独立同分布的观测样本，在同一组预测函数中求一个最优的函数对依赖关系进行估计，使期望风险R[f]最小。损失函数是评价预测准确程度的一种度量，它与预测函数f(x)密切相关。而f(x)的期望风险依赖于概率分布和损失函数，前者是客观存在的，后者是根据具体问题选定的，带有（主观的）人为的或偏好色彩。期望风险的大小直观上可以理解为，当我们用f(x)进行预测时，“平均”的损失程度，或“平均”犯错误的程度。

但是，只有样本却无法计算期望风险，因此，传统的学习方法用样本定义经验风险Remp[f]作为对期望风险的估计，并设计学习算法使之最小化。即所谓的经验风险最小化(Empirical Risk Minimization, ERM)归纳原则。经验风险是用损失函数来计算的。对 于模式识别问题的损失函数来说，经验风险就是训练样本错误率；对于函数逼近问题的损失函数来说，就是平方训练误差；而对于概率密度估计问题的损失函数来 说，ERM准则就等价于最大似然法。事实上，用ERM准则代替期望风险最小化并没有经过充分的理论论证，只是直观上合理的想当然做法。也就是说，经验风险最小不一定意味着期望风险最小。其实，只有样本数目趋近于无穷大时，经验风险才有可能趋近于期望风险。但是很多问题中样本数目离无穷大很远，那么在有限样本下ERM准则就不一定能使真实风险较小啦。ERM准则不成功的一个例子就是神经网络的过学习问题（某些情况下，训练误差过小反而导致推广能力下降，或者说是训练误差过小导致了预测错误率的增加，即真实风险的增加）。

统计学习理论(Statistical Learning Theory, SLT)和支持向量机(Support Vector Machine, SVM)建立了一套较好的有限训练样本下机器学习的理论框架和通用方法，既有严格的理论基础，又能较好地解决小样本、非线性、高维数和局部极小点等实际问 题，其核心思想就是学习机器（又叫预测函数，或学习函数，或学习模型）F要与有限的训练样本相适应。在学习算法中需要选择恰当的F，这里的关键因素是F的大小，或者F的丰富程度，或者说F的“表达能力”，VC维(Vapnik-Chervonenkis Dimension)就是对这种“表达能力”的一种描述。

VC维的定义如下：对于一个指示函数集，如果存在h个样本能够被函数集中的函数按所有可能的2的h次幂种形式分开，则称函数集能够把h个样本都打散，h的最大值就是函数集的VC维。VC维是SLT中的一个重要概念，它是函数集学习性能的重要指标。目前尚没有通用的关于任意函数集VC维计算的理论，只知道一些特殊的函数集的VC维。比如，在n维空间中线性分类器和线性实函数的VC维是 n+1，而 f(x,a) = sin(ax) 的VC维则为无穷大。对于给定的学习函数集，如何（用理论或实验的方法）计算其VC维是当前统计学习理论中有待研究的一个问题。

由上文可知，在有限样本情况下，仅仅用ERM来近似期望风险是行不通的。统计学习理论给出了期望风险 R[f] 与经验风险 Remp[f] 之间关系：R[f] <= ( Remp[f] + e )。其中 e = g(h/n) 为置信区间，e 是VC维 h 的增函数，也是样本数n的减函数。右端称为结构风险，它是期望风险 R[f] 的一个上界。经验风险的最小依赖较大的 F （样本数较多的函数集）中某个 f 的选择，但是 F 较大，则VC维较大，就导致置信区间 e 变大，所以要想使期望风险 R[f] 最小，必须选择合适的 h 和 n 来使不等式右边的结构风险最小，这就是结构风险最小化(Structural Risk Minimization, SRM)归纳原则。实现SRM的思路之一就是设计函数集的某种结构使每个子集中都能取得最小的经验风险（如使训练误差为0），然后只需选择适当的子集使置信范围最小，则这个子集中使经验风险最小的函数就是最优函数。SVM方法实际上就是这种思想的具体实现。

SVM是一种基于统计的学习方法，它是对SRM的近似。概括地说，SVM就是首先通过用内积函数定义的非线性变换将输入空间变换到一个高维空间，然后再在这个空间中求（广义）最优分类面的分类方法。

支持向量机的原理

名词解释1——支持向量机：“机（machine，机器）”实际上是一个算法。在机器学习领域，常把一些算法看 作是一个机器（又叫学习机器，或预测函数，或学习函数）。“支持向量”则是指训练集中的某些训练点的输入 xi 。它是一种有监督（有导师）学习方法，即已知训练点的类别，求训练点和类别之间的对应关系，以便将训练集按照类别分开，或者是预测新的训练点所对应的类 别。

名词解释2——符号函数：sgn(a) = 1, a >= 0;sgn(a) = -1, a < 0.

一般地，考虑 n 维空间上的分类问题，它包含 n 个指标和 l 个样本点。记这 l 个样本点的集合为 T = {(x1,y1),...,(xl,yl)}，其中 xi 是输入指标向量，或称输入，或称模式，其分量称为特征，或属性，或输入指标；yi 是输出指标向量，或称输出，i = 1,...,l。 这 l 个样本点组成的集合称为训练集，所以我们也称样本点位训练点。

对于训练集来说，有线性可分、近似线性可分和线性不可分等三种情况，这就是分类问题的三种类型。其实，无论是哪类问题，都有对应的分类机，这将在以下的内容中进行详细阐述。那么，有人可能会问，什么叫线性可分？通俗地讲，就是可以用一条或几条直线把属于不同类别的样本点分开。实际上，求解分类问题，就是要求出这条或这几条直线！那么，问题是：怎么求？这里先以二维两类线性可分的分类问题为例，做个详细的说明，然后再过渡到多类分类问题。

首先，回忆一下平面（二维）坐标系中某条直线的方程。还记得直线的一般方程

Ax + By + C = 0 （公式一）

吧，我们引入向量的概念，则该方程可以写成{x,y}与{A,B}的内积加上C等于0，即

{A,B}·{x,y} + C = 0

你还记得法向量和方向向量的概念吗？其实{A,B}就是法向量，而{B，-A}就是方向向量了。那么我们可以把直线的一般方程简化成为

w·x + b = 0 （公式二）

的形式（因为这个式子是大家最常用的嘛）。注意：（公式二）中的 x 和（公式一）中的 x 不同，前者一个二维向量，后者是一个实数。

对于两类问题，如果将某一直线两侧的样本点分为正类和负类，则用符号函数的方式推断点 x 所对应的类别 y 的决策函数如下：

y = f(x) = sgn((w·x) + b) （公式三）

根据符号函数的定义，很明显 y 的取值要么是 1 ，要么是 -1，也就是说样本点的类别只有 1 和 -1 两类。此时的分类问题是：对于任意给定的一个新的模式 x ，根据训练集推断它所对应的输出 y 是 1 还是 -1。这就是线性可分的分类问题，也是一个模式识别问题，我们要做的工作就是要求出 w 和 b 。

直接求这两个参数基本上不太可能，除了训练集我们又没有别的信息可以利用，这可如何是好？前辈们给出了一个绝妙的方法——就是所求得的预测函 数 f(x) 对原有样本的分类错误率最小。那么，问题又出来了，这个错误率咋算？损失函数就是专门用来评价预测准确程度的一种度量，而且模式识别问题使用的正是 “0-1损失函数”。根据我的上一篇学习体会——《从机器学习到支持向量机》http://axywestwind.bokee.com/viewdiary.14525093.html中的阐述，使（公式三）中的 f(x) 的预测误差最小的问题转化成期望误差最小、经验风险最小，最后在统计学习理论中又转化为结构风险最小(Structural Risk Minimization, SRM)。而实现SRM的思路之一就是设计预测函数集的某种结构使每个子集中都能取得最小的经验风险（如使训练误差为0），然后只需选择适当的子集使置信范围最小，则这个子集中使经验风险最小的函数就是最优函数。SVM方法实际上就是这种思想的具体实现，它是对SRM的近似。说了半天，终于和上次的内容连接上了。但是，为了求解SRM这个最小化问题，还得将它转化成数学形式。

SVM方法是从线性可分情况下的最优分类面提出的，它是实现统计学习理论思想的方法。什么是最优分类面呢？这要从最优分类线说起。所谓最优分类线就是要求分类线不但能将两类无错误地分开，而且要使两类的分类间隔最大。前者是保证经验风险最小（如使训练误差为0），而使分类间隔最大实际上就是使推广性的界中的置信范围最小，从而使真实风险最小。推广到高维空间，最优分类线就成为最优分类面。

那么如何构造这个最优分类面呢？方法有 2 个：平分最近点法和最大间隔法。有趣的是，这两个方法殊途同归，它们求解得到的是同一个超平面（由三个定理联合起来证明了这个结论）。由这三个定理可知，这两个方法与一个最优化问题求解方法等价，这个方法就称为“线性可分支持向量分类机”。其实，这个分类机是将最大间隔法求解最优分类面的最优化问题转化为其对偶问题，从而通过求解相对简单的对偶问题来求解原分类问题的算法。随后引入松弛变量和惩罚因子来解决非线性分类问题，并且允许一定的分类错误（软间隔），最终得到非线性软间隔的标准的 C-支持向量机(C-SVC)。其中的巧妙之处就在于把一个复杂的最优化问题的求解简化为对原有样本数据的内积运算。我们要做的就是选择适当的核函数及其参数、惩罚因子就可以了。

概括地说，SVM就是首先通过用内积函数定义的非线性变换将输入空间变换到一个高维空间，然后再在这个空间中求（广义）最优分类面的分类方法。

那么，如何通过计算机来求解这个内积运算呢？且听下回分解！下次会介绍选块算法、分解算法，并重点介绍由分解算法改进得到的最经典的 SMO 算法。

参考文献：

1、邓乃扬，数据挖掘中的新方法——支持向量机[M]，北京：科学出版社，2004。

2、边肇祺，张学工，模式识别（第二版）[M]，清华大学出版社，2000。

附录：

知识工程学：一个新的重要研究领域 http://zcwbluesky.bokee.com/1834927.html

SMO算法分析与程序实现

先提供一个 libsvm 2.6 的程序源码注释http://www.pami.sjtu.edu.cn/people/gpliu/document/libsvm_src.pdf，大家先看看，具体的算法分析以后再写，最近比较忙！

本文中提到的算法是 Platt 在1998年提出、由 Fan 等人于2005年改进的序列最小最优化(Sequential Minimal Optimization,SMO)分解方法，程序源码参考libsvm-2.8.3 （http://www.csie.ntu.edu.tw/~cjlin/libsvm/）。

参考文献

[1] July.支持向量机通俗导论(理解SVM 的三层境界)[EB/OL].http://blog.csdn.net/v_ july_v/article/details/7624837

[2] Jun Meng,Dong Liu,Chao Sun,Yushi Luan.Prediction of plant pre-microRNAs and their microRNAs in genome-scale sequences using structure-sequence features and support vector machine[EB/OL].2014.http://www.biomedcentral.com/1471-2105/15/423

[3] Kai Wang, Chun Liang, Jinding Liu1, Huamei Xiao, Shuiqing Huang, Jianhua Xu,Fei Li.Prediction of piRNAs using transposon interaction and a support vector machine[EB/OL].BMC Bioinformatics (2014) 15:419

[4] Minta Thomas, Kris De Brabanter, Johan AK Suykens1, Bart De Moor.Predicting breast cancer using an expression values weighted clinical classifier[EB/OL].BMC Bioinformatics (2014) 15:411

[5] John C. Platt.Sequential Minimal Optimization:A Fast Algorithm for Training Support Vector Machines[R]．Technical Report MSR-TR-98-14．1998

[6] J. C. Platt. Fast training of support vector machines using sequential minimal optimization.

In B. Sch¨olkopf, C. J. C. Burges, and A. J. Smola, editors, Advances in
Kernel Methods - Support Vector Learning, Cambridge, MA, 1998. MIT Press.

[7] R.-E. Fan, P.-H. Chen, and C.-J. Lin. Working set selection using second order
information for training SVM. Journal of Machine Learning Research, 6:1889–1918,
2005. URL http://www.csie.ntu.edu.tw/ cjlin/papers/quadworkset.pdf.
[8] 姬水旺，姬旺田，支持向量机训练算法综述[J]，微机发展，14（1），2004。

[9] 刘江华，程君实，陈佳品，支持向量机训练算法综述[J]，信息与控制，31（1），2002。

以下是网上现有的几个中文版的支持向量机软件libsvm使用的网址：

1、陆振波的个人主页http://luzhenbo.88uu.com.cn/

2、piaip's Using (lib)SVM Tutorial（piaip 的 (lib)SVM 簡易入門）http://ntu.csie.org/~piaip/svm/svm_tutorial.html
3、Libsvm学习笔记（http://mirrorlake.bokee.com/5133582.html）