《基于特征可分性的核函数自适应构造》由会员分享，可在线阅读，更多相关《基于特征可分性的核函数自适应构造（11页珍藏版）》请在金锄头文库上搜索。
1、基于特征可分性的核函数自适应构造*基金项目：国家自然科学基金(No.60402032) E-mail: 任双桥 魏玺章 黎湘 庄钊文 （国防科技大学电子科学与工程学院空间电子信息技术研究所 湖南 长沙，410073）摘 要：核函数的选择与构造是是支撑矢量机研究中的关键问题和难点。本文针对该问题，首先讨论了特征空间的线性可分性，推导了其判别条件。然后，根据特征完全可分条件，基于函数逼近论和核函数的基本性质，提出了自适应多项式核函数和B-样条核函数模型，给出了模型参数的估计算法。实测数据仿真实验结果表明，与经典的核函数相比，本文提出的算法在分类性能上取得了明显改善。关键词：支撑矢量机，特征可分性
2、，核函数，多项式，B-样条1引言支撑矢量机（SVM）1是一种新的非常有发展前景的分类识别技术。SVM是建立在统计学习理论中结构风险最小化原理基础上，根据有限的样本信息，在模型的复杂性(即对特定训练样本的学习精度)和学习能力(即无错误地识别样本的能力)之间寻求最佳折衷，以期获得最好的推广能力。SVM克服了神经网络和传统分类器的过学习、局部极值点和维数灾难等诸多缺点，具备较强的泛化能力，已成为备受关注的研究热点。核函数是基于支撑矢量机解决原样本空间中线性不可分问题时引入的一种非线性变换。其基本思想就是通过核变换，使得样本在新的高维特征空间中线性可分，然后在高维特征空间中来实现最优分类面的求解。核函
3、数及核方法的研究是SVM 理论与方法研究中极为重要的一个分支。构造一个具有良好性能的支撑矢量机，模型选择是关键2。传统的作法包括两个相对独立的步骤，首先凭经验选定核函数的类型，其次根据一定的准则确定核函数的参数。目前，关于核函数的研究有很多3-9，但是，大多数的方法是在特定的应用领域内，通过实验分析来解决，至今没有一个能够指导SVM选择最优核的理论和方法。核函数的选择与构造仍是一个亟待解决的难题。 本文针对该问题，首先讨论了样本空间种特征的线性可分性，推导了其判别条件。然后，根据特征的完全可分条件，基于函数逼近论和核函数的基本性质，提出了自适应构造核函数的两种模型，即自适应多项式核函数和自适应
4、B样条核函数，给出了模型参数估计算法。实测数据仿真实验结果表明，与经典核函数相比，本文构造的核函数在分类性能和推广能力上均取得了明显改善。2特征空间中目标线性可分条件本节主要探讨样本空间特征的可分性，首先给出了特征的可分性定义，然后依据Farkas引理1推导了其判别条件。这些判别条件为自适应构造可分核函数提供了理论基础。2.1 线性可分性定义给定输入空间个训练样本，其中，为类别标示符。如果存在一个线性分类器能将每个样本正确分类，则称样本线性可分。定义2.1：称样本集，其中，线性可分是指，存在，使得(2.1)成立。， (2.1)若不存在满足不等式(2.1)的，则称样本集线性不可分。图1 样本集线
5、性可分示意图为讨论方便，将(2.1)写成矩阵形式，记，矩阵则有 （2.2） （2.3）在下述的讨论中，Farkas引理扮演了一个重要的角色。引理2.1（Farkas择一定理）10设矩阵，矢量，则不等式组和组恰一组有解。组： ， 组： ， 证明：参见文献10。证略。2.2线性可分性条件根据引理2.1，可从反面考察样本集的线性可分性，也即，若线性不可分，则不等式组无解，从而其充要条件是不等式组有解。若将（2.2）、（2.3）代入不等式组，则可得 （2.4） ， （2.5）， （2.6）从而可得的线性可分性理论形式的判据。定理2.1（可分性条件）观测样本集线性可分的充要条件是不等式组(2.4)、(2
6、.5)、(2.6)无解。为了求解齐次线性方程（2.4）,需要用到矩阵的广义逆。下述定理刻画了任意矩阵的全部广义逆。定理2.211 设矩阵，秩为，且设 其中，、分别为和可逆矩阵，为阶单位阵，则的全部广义逆为 其中，、分别为任意的，和矩阵。证明：参见文献11。证略。定理2.311 设矩阵，为任意给定的广义逆，则齐次线性方程组 的全部解为 其中，为任意的维矢量。证明：参见文献11。证略。根据定理2.3，记矩阵 （2.7）则不等式组(2.3)、(2.4)、（2.5）的解与下述不等式组同解 （2.8） （2.9） （2.10）其中，为任意给定的矩阵的广义逆。由此可得样本集线性可分充要条件是不等式组(2.
7、8)、(2.9)、(2.10)无解。推论2.1 若矩阵列满秩，即秩()=，则样本集线性可分。证明：由于秩()=，故存在可逆矩阵、，使得 （2.11）从而，其广义逆矩阵 （2.12）齐次方程（2.4）的解为 （2.13）显然，（2.13）与（2.9）矛盾，故不等式组(2.8)、(2.9)、(2.10)无解，从而样本集线性可分。证毕。若记Gram矩阵，则，其中 由于，因此，可得一个更有意义的结论。推论2.2 若Gram矩阵正定，则样本集线性可分。证明：由于Gram矩阵正定，且，故矩阵也是正定矩阵，从而秩()=。又由于 秩()秩()故秩()=，由推论2.1可知，样本集线性可分。证毕。根据推论2.2便
8、可以考察经过核映射以后的特征是否线性可分，这为自适应选择核函数、分析核函数可分性能提供了理论基础。3 核函数自适应构造支撑矢量机的性能很大程度上取决于核函数的设计。目前已有的支撑矢量核，由于其通过平移不能生成一组完备的基函数，因此，理论上支撑矢量机是不能逼近平方可积空间中的任意函数的。本节在对核函数可分性能的基础上，依据推论2.2和核函数性质，采用多项式和B-Spline自适应构造线性可分核函数。首先，介绍一个重要的定理。定理3.13 对任意给定的有限个样本以及某个核函数，若其相应的Gram矩阵是半正定的，则可构造映射，使得。证明：参见文献3。证略。定理3.1表明，对核函数Mercer条件1的
9、要求，可以放宽到对有限个观测样本点值的要求，也即只要能保证相应的Gram矩阵具有半正定性质。这一重要性质为自适应构造可分核函数提供了一条重要的途径。3.1 基于多项式表征核函数不妨假设核函数的一般形式为，其中，。根据Weierstrass定理5，闭区间上的连续函数可用多项式函数任意逼近。因此，可令 （3.1）由于常数对核函数的分类性能没有影响，所以多项式模型（3.1）中没有常数项。又由于为核函数，根据核函数性质可知，也为核函数。因此，为使（3.1）为核函数，只需多项式系数，。进一步，若要求构造出来的核函数具备线性可分的能力，由推论2.2和定理3.1可知，只需Gram矩阵，正定即可。因此，可令
10、（3.2）其中，。3.2 基于B-样条表征核函数由于多项式的逼近能力有限，对于函数逼近问题，B-样条函数是一个有力的工具，可以采用B-样条函数来表征核函数。假设或者，且。给定一组等距划分，步长，节点。记，则有 （3.3）其中，为阶标准B-样条函数，一般可取，则可得 同理，为保证（3.3）为核函数，由定理3.1可知，只需其所对应的Gram矩阵正定则可。因此，可对模型（3.3）的参数作如下要求。 ， （3.4）， （3.5）通过选择适当的，由B-样条函数的归一化性质12，（3.4）和（3.5）总可以保证（3.3）所对应的Gram矩阵正定。一般的，的取值范围可定为。3.3 核函数模型参数求解下面考察多项式核函数模型（3.2）和B-样条核函数模型（3.3）的参数求解。不妨假设核函数，即原空间通过非线性变换映射到高维特征空间。若记样本集中第一类样本点数为，第一类样本点数为，则在高维特征空间中，两类样本点的半径分别为 （3.6） （3.7）其中，、分别表示样本集中第一类和第二类样本点，、分别高维特征空间中两类样本点的中心。 （3.8） （3.9）将（3.8）、（3.9）代入（3.6）和（3.7），可得 （3.10） （3.11）若记两样本集之间的平均距离为，则有 （3.12）又由多项式模型（3.2）可知，若假设矢量，则有 （3.13）同理，对于B-样条参数模型（3.2），只需令
