计 算 机 工 程 第 35 卷 第1期
V ol.35 No.1 Computer Engineering
文章编号：1000—3428(2009)01—0171—02 ·人工智能及识别技术·
2009年1月
January 2009
文献标识码：A
中图分类号：TP311.13
改进的支持向量机特征选择算法
吕世聘1,2，王秀坤1，孙 岩2,3，唐一源2
(1. 大连理工大学计算机科学与工程系，大连 116023； 2. 大连理工大学神经信息学研究所，大连 116023；
3. 辽宁师范大学计算机与信息技术学院，大连 116029)
摘 要：针对采用支持向量机进行分类的特征子集选择问题，提出一种改进的基于梯度向量的特征评测算法。该算法在核特征空间中，利用数据点到分类超平面的距离函数的梯度向量对各个特征的重要性进行排序，省去了已有算法中计算梯度向量与各个坐标轴夹角的过程，实验结果表明，该算法简化了已有的基于角度的特征选择方法，并且结果保持一致。 关键词：支持向量机；特征选择；核函数
Improved Feature Selection Algorithm for SVM
LV Shi-pin1,2, WANG Xiu-kun1, SUN Yan2,3, TANG Yi-yuan2
(1. Department of Computer Science and Engineering, Dalian University of Technology, Dalian 116023; 2. Institute of Neuroinformatics, Dalian University of Technology, Dalian 116023; 3. Department of Computer & Information Technology, Liaoning Normal University, Dalian 116029) 【Abstract】An improved feature selection algorithm based on gradient is proposed, aiming at the problem of feature subset selection when applying Support Vector Machine(SVM) to classification. The algorithm ranks the features by the criterionof the local gradients of distance function, measuring the distance from a datapoint to the classification hyperplane in the kernel-induced feature space, and eliminates the calculation of theangles of gradients with every axis. Experimental results show that the proposed algorithm simplifies the method of feature selection based on anglecalculation and keeps the results consistent.
【Key words】Support Vector Machine(SVM); feature selection; kernel function
1 概述 在机器学习领域，特征选择就是从对象已有的特征中，筛选出一个与任务密切相关的适当的子集，使得该特征子集能很好地用于最终的学习目的。特征选择对于提高学习效果是非常关键的，恰当的方法可以消除不相关或冗余的特征，减少数据维度，削减计算时在空间和时间上的耗费，同时也可以降低噪声的影响、避免过学习，比较常用的算法有wrapper, filter和embedded等。在研究支持向量机(Support Vector Machine, SVM)分类器几何特性的基础上，Hermes等人[1]提出了一种专门针对SVM分类器的特征选择方法(简称L-J算法)：首先计算数据点到分类超平面的距离函数的梯度，然后求该梯度向量与各个坐标轴的夹角，并以此作为衡量特征重要性的指标，夹角越小，相应的特征对分类结果的影响但每个特征都需要计算一次就越大。L-J算法使用较为方便，相应的角度，当数据维度很高时，比较繁琐。本文在其基础上进行改进，免去夹角的计算，直接用距离函数的梯度向量在各个坐标轴上分量的绝对值来度量各个特征的重要性，实验表明，其与L-J算法的结果一致。 ⎧Maxα∑αi-∑αiαjyiyjK(xi,xj)⎪ii,j
(1) ⎨
s.t. αy0,0αCi=≤≤∀∑iii⎪i⎩
相应的判别函数为 ⎛⎞
f(x)=sgn⎜∑αiyiK(xi,x)+b⎟ (2) ⎝x∈SV⎠
i
其中，K(x,y)为核函数。 令g(x)=∑aiyiK(xi,x)+b，则g(x)为度量样本点x
xi∈SV
到分类超平面的距离函数。 3 特征选择算法 3.1 L-J算法 由式(2)可知，距离函数g(x)决定着SVM分类器的结果，首先求取该函数在样为了评测各个特征对g(x)的影响大小，本点x的梯度∇xg(x)=∑aiyi∇xK(xi,x)，其中∇xK(xi,x)xi∈SV
对于常用的核函数来说很容易求取，具体见表1。梯度向量∇xg(x)为g(x)增益最大的方向向量，其与坐标轴的夹角越2 支持向量机 训练SVM分类器的步骤为：采用“核计巧”，将数据投影到高维的特征空间，然后采用最大间隔法求取最优超平面。考虑有监督学习的二分类问题，设含m个样本、维度为d的训练数据集为：S={(x1,y1),(x2,y2),\",(xm,ym)}, xi∈Rd，其误差时，支持向量机相当于求解如下的凸二次规划[2]：
中yi∈{-1,1}为类型标志。在引入松弛变量，允许一定的分类小，相应的特征对g(x)的作用越大，也就对SVM的分类结果影响越大。 基金项目：国家自然科学基金资助项目(60472017, 30670699) 作者简介：吕世聘(1973－)，男，博士研究生，主研方向：数据库，决策支持系统，神经信息学；王秀坤，教授、博士生导师；孙 岩，博士研究生；唐一源，教授、博士生导师
收稿日期：2008-06-29 E-mail：7sunson@163.com
—171—
表1 常用的核函数及其偏导数 K(u,v)uv
TT
此算法相当于求取集合Iε所有数据点处的∇xg(x)的“合力”，省去了L-J算法中繁琐的角度计算，所以较为简捷。 θ∇vK(u,v) 2
u
T
4 数值实验 (1+uv)θu1+uv
()θ-1
2
exp-γu-v
() 2γ(u-v)⋅exp-γu-v
() 分析SVM分类器的几何特点可知，距离函数g(x)与训练样本x相应的系数α有如下的关系： ⎧g(xi)≥1αi=0
⎪
(3) ⎨g(xi)<1αi=C
⎪
⎩g(xi)=10<αi其中，满足0<αβ∈{0,1}⎜∇xg(x)⎪⎝⎩⎞⎫
⎟⎪⎬ (4) ⎟⎪⎠⎭
0.250.15
特征对于分类结果的影响就越大。
(5)求取αj=1−⋅
2∑i∈Iεαj(xi)
，αj数值越大，其相应的Iεπ
0.05246特征序号810 3.2 改进的算法 L-J算法用角度作为评测标准，需要计算梯度向量∇xg(x)与各个单位向量ej间的夹角，每个特征都要计算一图1 2种特征选择算法的实验对比 5 结束语 本文对支持向量机分类器的几何特性进行了研究，改进了现有的特征选择算法。首先训练生成支持向量分类器，然后计算距离函数的梯度，最后以该向量各个分量的绝对值作为评测特征作用大小的指标，从而进行特征选择。算法避免了计算梯度向量与各坐标轴夹角的繁琐过程，简化了L-J算法，并保证了相同的实验结果。 参考文献 [1] Hermes L, Buhmann J M. Feature Selection for Support Vector
Machines[C]//Proc. of the 15th International Conference on Pattern Recognition. Barcelona, Spain: [s. n.], 2000: 716-719.
[2] Vapnik V. An Overview of Statistical Learning Theory[J]. IEEE
Trans. Neural Networks, 1999, 10(5): 988-999.
[3] Chang Chihchung, Lin Chinjen. LIBSVM: A Library for Support
Vector Machines[EB/OL]. (2007-09-15). http://www.csie.ntu.edu. tw/~cjlin/libsvm.
次，当数据维度很高时，比较繁琐。设∇xg(x)为∇xg(x)的各个分量取绝对值后生成的向量，将∇xg(x)归一化后，其第j个分量越大，则αj就越大，所以∇xg(x)的各个分量可以替代αj的作为。改进的算法直接用向量作为评测标准，具体流程如下： (1)~ (3)同L-J算法； (4)在集合Iε中将∇xg(x)归一化后求和： V=∑i∈Iε∇g(x)∇g(x) (5) V
，则V的各个分量的大小反映(5)将V归一化：V=V出相应特征的重要性。 （上接第170页）
参考文献 [1] Pappis C P, MamdaniE H. A Fuzzy Logic Controller for a Traffic
Junction[J]. IEEE Trans. on System Man and Cybernetics, 1997, 7(10): 707-717.
[2] 刘智勇. 智能交通控制理论及应用[M]. 北京: 科学出版社,
2003.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
[3] 丛 爽. 神经网络、模糊系统及其在运动控制中的应用[M].
合肥: 中国科学技术大学出版社, 2001.
[4] 周子力, 王新伟, 王艳娜. 基于元胞自动机的城市交通流仿真系
统[J]. 计算机工程, 2005, 31(13): 183-185.
— —172
