摘 要 针对基于向量投影的支持向量预选取方法选取投影直线过于简单粗糙， 导致需要选取较多的边界向量才能包含原始问题的支持向量的问题， 提出了一种新的支持向量预选取方法． 该方法通过定义好的投影直线具备的3 个必要特征， 提出:对于线性可分情况， 利用 Fisher 线性判别算法来获取最佳的投影直线;对于非线性可分情况，利用特征空间中心向量所在直线作为相应的投影直线． 由于该方法确定的投影直线可以更好地对样本投影进行分离， 因此， 与基于向量投影的支持向量预选取方法相比， 该方法可用更少的原始样本来构造边界向量集合， 可有效降低支持向量机算法的时空复杂度． 在两个人工数据集和一个现实数据集上的实验表明， 所提方法不仅可以达到以往各种实用的支持向量机算法分类精度， 而且更为高效．

关键词 支持向量机;边界向量集合;Fisher 线性判别;中心向量

1 引 言

近些年， 支持向量机［1- 3 ］ 研究获得了越来越多的关注． 实践证明支持向量机对于许多实际问题有着很好的泛化能力， 例如手写字符识别 ［4 ］ 、 人脸识别［5- 6 ］ 、 行人检测 ［7- 8 ］ 、 文本分类 ［9- 10 ］ 、 入侵检测 ［11 ］ ，然而标准的支持向量机算法时间复杂度高， 并且需要大量的内存空间， 因此支持向量机的应用受到了很大的限制． 由于利用支持向量机算法进行决策时，最终的决策函数仅仅由支持向量决定 ［2 ］ ， 因此如果能够预先确定支持向量， 那么就可以极大地降低支持向量机训练算法的时空复杂度． 为此， 很多较实用的支持向量机算法被相继提出， 其中大多数被称之为分 解 方 法． 例 如， 方 法 Chunking ［12 ］ 、 Decompo-sing ［13 ］ 和序列最小最优化(SMO)算法 ［14 ］ ． 这些方法虽然可以预先确定支持向量， 但它们获得支持向量时需要迭代多次．为了快速获得支持向量， 李青等提出了一种基于向量投影的支持向量预选取方法 ［15 ］ ， 由于该方法可在边界向量集合上进行一次支持向量机训练， 因此该方法有效地降低了支持向量机训练的计算时间和内存需求． 但该方法还存在一些不足需要改进，如:(1) 没有对向量投影的原因给出详细的分析， 没有对投影直线的性能进行比较， 影响了该方法可信性;(2) 对于线性可分情况， 利用中心向量所在直线作为投影直线， 不能充分对原始样本的投影进行最大化的分离， 甚至会出现经投影后变为线性不可分，从而影响对边界向量集合的合理确定， 导致需要选取较多的原始样本构造边界向量集合;(3) 对于非线性可分情况， 将原始空间两类样本的中心 m 1 ， m 2通过核函数 ψ(·)映射到特征空间， 然后在特征空间中， 利用向量ψ(m 1 )ψ(m 2→     )所在直线作为投影直线， 由于该直线不是一般意义上的特征空间中的中心向量所在直线， 将影响特征空间中样本投影的分离， 导致需要选取较多的原始样本来构造边界向量集合．

针对文献［ 15］ 的不足， 本文提出了一种新的支持向量预选取方法， 对文献［ 15］ 中方法主要做了如下改进:(1) 深入分析了向量投影的原因， 明确了通过向量投影方式可以方便地确定边界向量集合， 并给出了好的投影直线应该具备的 3 个特征;(2) 对于线性可分情况， 为了有效地对原始样本进行最大化分离， 提出利用 Fisher 线性判别算法获取最佳投影直线， 保证了原始空间中的线性可分问题， 经投影后仍然线性可分， 方便了边界向量选取;(3) 对于非线性可分情况， 本文首先将原始样本投影到特征空间， 然后在特征空间中分别求取两类样本的中心m1ψ和 m2ψ， 最后利用向量m1ψm 2→   ψ 所在直线作为投影直线． 由于所获取的直线可以更好地对特征空间样本投影进行分离， 方便了边界向量选取， 因此本文提出的方法可以使用更少的原始样本构造边界向量集合， 为进一步降低支持向量机训练算法的时空复杂度提供了保障．在此基础上， 针对线性可分和非线性可分情况，提出了完整的分类算法， 并对算法的时间和空间复杂度进行详细分析;最后将本文所提算法与标准支持向量机算法、 SMO 算法和文献［ 15］中所提算法，在两个人工数据集上和一个实际问题数据集上进行对比测试， 并给出各种算法的运行时间、 分类精度和相应的分析结论．

2 边界向量集合上的支持向量机训练

2. 1 支持向量预选取思路利用 支 持 向 量 机 解 决 分 类 问 题 时，许 多Lagrange乘子等于零， 然而最终的决策函数却仅仅由具有非零 Lagrange 乘子的样本决定， 这些样本就是所谓的支持向量． 因此如果能够预先确定支持向量， 那么支持向量机训练将变得更容易． 由于支持向量经常位于每一类样本的边界区域， 并且面向另一类样本． 因此一个很好的预选取支持向量的方法是寻找边界向量， 即位于每一类样本的边界区域， 并且面向另一类的样本 ［15- 16 ］ ．

2. 2 投影原因及投影直线的特征分析为了确定该边界向量集合， 有必要确定每一类样本面向另一类样本的边界． 由于现实世界中原始样本往往是高维的， 很难直接确定边界， 而采用将所有的样本投影到某一直线上的方法， 有可能在一维空间确定边界向量集合， 所以如何确定投影直线就成了确定边界向量集合的重要问题．由于可投影的直线很多， 为了确定投影直线， 给出合适的投影直线所应该具备的特点如下:(1) 对于原始空间中的线性可分问题， 合适的投影直线能够使其上样本投影也线性可分， 即该直线应该能够使两类样本在其上的投影是两个互不相交的区域．(2) 对于原始空间的非线性可分问题， 在将原始空间映射到高维空间之后， 合适的投影直线能够使特征空间内的向量在其上的投影也线性可分， 即该直线应该能够使特征空间中两类样本在其上的投影是两个互不相交的区域．(3) 为了便于确定边界向量， 合适的投影直线应能使各类样本投影后， 在一维的空间的各类样本投影尽可能分得开， 同时各类样本的投影内部尽量密集．

2. 3 投影直线确定方法基于上述分析， 本文提出如下投影直线确定方法:(1) 对于线性可分情况， 由于 Fisher 线性判别算法［17 ］ 能够寻找最大化类间离散度， 并且最小化类内离散度的投影直线方向， 所以该算法可以有效地对原始样本的投影进行最大化分离， 因此本文提出基于 Fisher 线性判别算法确定最佳投影直线的方法．(2)对于非线性可分情况， 通过核函数将原始空间映射到高维甚至是无穷维特征空间， 可将非线性可分情况转化为线性可分情况． 由于此时并不知道非线性映射 ψ(·)的具体形式， 所以无法通过 Fisher 线性判别算法求出特征空间中的最佳投影直线． 由于原始样本映射到特征空间后， 第 1 类样本中心 m1ψ和第2 类样本中心 m2ψ所在的直线， 是特征空间中两类样本间中心向量m1ψm 2→   ψ 所在的直线， 该直线能根据特征空间线性可分样本分布的变化有效地改变方向，使该直线能够较稳定地对线性可分样本的投影进行分离;又由于 m1ψ与 ψ(m 1 )、 m2ψ与ψ(m 2 )都不同， 所以投影向量ψ(m 1 )ψ(m 2→     )不是中心向量， 不能随着特征空间线性可分样本分布的变化有效地改变方向， 因此以投影向量ψ(m 1 )ψ(m 2→     )确定的投影直线，不能像中心向量m1ψm 2→   ψ 所确定的投影直线具有稳定的可分性． 因此对于非线性可分情况， 本文提出利用特征空间中心向量m1ψm 2→   ψ 所在直线作为投影直线．下面给出投影直线确定方法的具体实现过程．

2. 3. 1 线性可分问题的投影直线确定方法对于线性可分问题， 利用 Fisher 线性判别算法确定最佳投影直线的方法如下:设χ 1 = {x 1 1 ， …， x 1 l 1 }和χ 2 = {x 2 1 ， …， x 2 l 2 }是来自于两组不同类别的样本， m i =1l i∑l ij =1x i j 为样本中心．Fisher 线性判别通过求解 maxJ(w) 确定最佳投影直线方向 w ， 其中J(w) =w T S B ww T S W w(1)S B = (m 1 － m 2 )(m 1 － m 2 )T(2)S W = ∑i =1， 2∑x∈χ i (x － mi )(x － m i )T(3)之所以最大化函数 J(w)可以确定的最佳投影直线方向 w， 是由于 J(w)中的 S B 和 S W 分别是类间离散度和类内离散度， 通过最大化 J(w)确定方向为 w 的投影直线一定满足最大化类间离散度和最小化类内离散度．

2. 3. 2 非线性可分问题的投影直线确定方法对于非线性可分情况， 本文提出利用中心向量m1ψm 2→   ψ 所在直线作为投影直线． 虽然非线性映射ψ(·) 并未显式给出， 使得特征空间中心向量m1ψm 2→   ψ 的值无法确定， 然而这并不影响通过中心向量m1ψm 2→   ψ 确定边界向量集合． 原因是特征空间中边界向量集合的确定， 只需要确定特征空间中样本之间的相关距离即可(详见 2. 4 节)． 下面详细给出特征空间中的样本之间的几种必要距离的求法， 首先给出其中涉及到的几种距离的说明．自中心距离:样本与样本所属类别中心向量之间的距离．互中心距离:某一样本与另一类别中心向量之间的距离．中心距离:两类样本中心之间的距离．考虑到求解距离的方法具有普遍意义， 将所提出的几种距离的求法以定理的方式给出．定理 1． 已知两类模式的训练样本分别为χ 1={x 11 ， …， x1l 1 } 和 χ 2= {x 21 ， …， x2l 2 }， 经非线性映射ψ(·)作用后， 映射到某一特征空间 H， 则在特征空间中的中心距离为定理 2． 已知两类模式的训练样本分别为χ1= {x 11 ， …， x1l 1 }和χ2= {x 21 ， …， x2l 2 }， 经非线性映射ψ(·)作用后， 映射到某一特征空间 H， 则原始训练样本 x∈ χ 1 与 x'∈ χ 2 在特征空间中的自中心距离分别为

2. 4 边界向量集合确定

2. 4. 1 线性可分情况设 χ 1 = {x 1 1 ， …， x 1 l 1 }和 χ 2 = {x 2 1 ， …， x 2 l 2 }是两组来自于不同类别的样本， 将全体训练样本不加区分地记为 χ = χ 1 ∪ χ 2 = {x 1 ， …， x l }． 下面是本文提出的确定边界向量集合方法的具体实现步骤:1． 利用 Fisher 线性判别分析确定最佳投影直线， 即根据 2. 3. 1 节所示确定最佳投影直线方向 w．2． 将所有的原始样本投影到由步 1 确定的直线上． 设x 0 j (1jl)表示原始训练样本 x j (1jl)相应的投影， 设P 1 和 P 2 分别代表类 χ 1 和 χ 2 的投影． 分别求出 P 1 和 P 2 之间的最小距离 d(P 1 ， P 2 )、 来自于不同类别且满足 d(x 0i ， x0j ) = d(P 1 ， P 2 )的相应的投影 x 0 i 和 x 0 j 、 中点 c 0 及投影类 P 1 和 P 2 的类内最大距离 d(P 1 )和 d(P 2 )(即类内最远的投影距离)．3． 结合 Fisher 线性判别分析确定最佳投影直线， 设计抽取两类样本集合中对应投影点与中点 c 0 之间距离分别满足如下关系式的原始样本， 构造边界向量集合．d(P 1 ， P 2 )2 x 0m－ c 0 d(P 1 ， P 2 )2+ λd(P 1 ) (12)d(P 1 ， P 2 )2 x 0n－ c 0 d(P 1 ， P 2 )2+ λd(P 2 ) (13)其中:x 0m ∈P 1 ， x0n ∈P 2 ， λ 为控制边界向量集合大小的参数，0λ1．由式(12)和(13)可知， 如果 λ 接近 0， 被抽取到边界向量集合中的原始样本很少． 如果 λ 接近 1，被抽取到边界向量集合中的原始样本接近全部． 更进一步可以看出， 如果 λ = 1， 那么本文所提的支持向量机训练算法将退化为标准的支持向量机算法．文献［ 15］ 采用中心向量作为投影直线， 不能保证对样本投影进行最大化分离， 所以确定边界向量集合时， 必须分两种情况讨论． 与文献［ 15］ 相比， 由于本文采用 Fisher 线性判别分析确定最佳投影直线， 能够将原始样本进行最大化分离， 避免了对两种情况的讨论， 因此可以通过更简便的约束关系(12)和(13)方便地确定边界向量集合．

2. 4. 2 非线性可分情况对非线性可分情况， 用映射 ψ(·)将原始样本空间转变为高维特征空间， 问题就变成了在高维特征空间中的线性可分问题． 下面给出非线性可分情况时具体确定边界向量集合的过程:1． 求出特征空间的中心距离 D， 建立数轴， 并以 m1ψ为坐标原点， 以原点右方 D 个单位为 m2ψ．2． 分别对特征空间中两类样本中的每一个样本 ψ(x)，求取自中心距离与互中心距离． 根据三角形的唯一性， 可知自中心距离、 互中心距离、 与中心距离对应的三边可组成一个三角形． 由余弦定理可知， 若自中心距离的平方加上中心距离的平方之和大于互中心距离的平方， 则该样本点在中心向量m1ψm 2→   ψ 上的投影点， 应该位于 m1ψ和 m2ψ之间． 对于投影点位于 m1ψ和 m2ψ之间的样本点 ψ(x)， 根据相应的几种距离关系， 可求出它的投影点到 m1ψ的距离 d， 并在数轴原点右方 d 处标记该点．3． 对第一类中投影点位于 m1ψ和 m2ψ之间的样本， 分别求出它们的投影点到 m1ψ的最大距离 D 1 和最小距离 D 2． 为了避免文献［ 15］中对两类不同的样本， 采用同样大小的边界区域取值范围， 导致样本选取不均衡的问题， 本文设计了按照固定比例 λ， 确定边界区域， 使样本选取更均衡．(a)若 D 1 小于 D 2 ， 则从投影点位于 m1ψ和 m2ψ之间的样本中， 选出投影点到 m1ψ的距离 d 满足不等式D 2 － D 12D 2 + D 12－ d D 2 － D 12+ λD 1 (14)或D 2 － D 12 d －D 2 + D 12D 2 － D 12+ λ(D － D 2 )(15)的样本作为边界向量， 其中参数 λ 与2. 4. 1 节中相同．(b) 若 D 1 大于 D 2 ， 则分别从投影点位于 m1ψ和 m2ψ之间的第 1、 2 类样本中， 选出投影点到 m1ψ的距离 d 满足不等式0  d －D 1 + D 22D 1 － D 22+ λD 2 (16)或0  d －D 1 + D 22D 1 － D 22+ λ(D － D 1 ) (17)的样本作为边界向量．以上边界向量求解过程说明， 只需要确定特征空间中样本之间的相关距离即可确定特征空间中边界向量集合．

2. 5 算 法

2. 5. 1 线性可分问题下的训练算法针对线性可分问题， 提出一种新的支持向量机训练算法:基于 Fisher 线性判别的支持向量机训练算法(SVMs training based on Linear Fisher Discrimi-nant， SVMLFD)． 该算法首先利用 Fisher 线性判别算法确定最佳投影直线的方向， 然后将原始样本投影到所确定的直线上， 再根据边界向量集合确定方法确定边界向量集合， 最后利用标准支持向量机算法进行分类训练． 算法实现的伪代码如算法 1 所示．算法 1． SVMLFD．输入:原始训练集 T = {(x i ， y i )， i = 1， …， l 1 + l 2 } ={(x i ， 0)， i =1， …， l 1 }∪{(x i ， 1)， i =1， …， l 2 }输出:决策函数 fw = lfd(T); /* w 是利用 Fisher 线性判别算法确定的最佳投影直线方向* /T 0 = extract(T，w); /* T 0 表示从原始训练集 T 中确定的边界向量集合 * / f = svm(T 0 ); /* f 是标准支持向量机算法在 T 0 集合上确定的决策函数* /

2. 5. 2 非线性可分问题下的训练算法针对非线性可分问题， 本文提出一种新的支持向量机训练算法:基于中心向量投影的支持向量机训练算法(SVMs training based on Mean Vector Pro-jection， SVMMVP)． 该算法首先利用特征空间中心向量作为投影直线， 然后通过求取特征空间样本间的相关距离间接等价的将样本投影到所确定的直线上， 然后根据边界向量集合确定方法确定边界向量集合， 最后利用标准支持向量机算法进行分类训练．算法实现的伪代码如算法 2 所示．算法 2． SVMMVP．输入:原始训练集 T = {(x i ， y i )， i = 1， …， l 1 + l 2 } ={(x i ， 0)， i = 1， …， l 1 }∪{(x i ， 1)， i = 1， …， l 2 };核函数K(x， x')输出:决策函数 fa = mvp(T， K(x， x')); /* a 是距离向量， 记录着与训练集 T 相关的中心距离、 自中心距离和互中心距离* /T 0 = extract(T， a); /* T 0 表示从原始训练集 T 中确定的边界向量集合* /f = svm(T 0 ); /* f 是标准支持向量机算法在 T 0 集合上确定的决策函数* /

2. 6 时间空间复杂度分析

2. 6. 1 线性可分情况的时空复杂度分析对于线性可分情况， SVMLFD 算法的时间复杂度主要取决于边界向量集合的确定和边界向量集合上的标准支持向量机训练， 其中边界向量集合确定的时间复杂度主要由 2. 4. 1 节步 1、 2 和 3 的时间复杂度决定．对于步 1:设原始训练集大小为 n， 寻找 Fisher判别准则下的最佳投影方向 w 的计算复杂度主要由计算类内散布矩阵和其逆矩阵的过程所决定， 其时间复杂度为 O(d 2 n) ［17 ］ ， 其中 d 是原始训练样本的维数．对于步 2:只需要分别求出两类样本在直线上投影的最大值和最小值， 就可以方便地求出步 2 中涉及的数量． 设第 1 类样本个数为 l 1 ， 第 2 类样本个数为 l 2 ． 计算第 1 类样本投影总共需要做 l1 次运算，而求取第 1 类样本投影的最大值和最小值最多只需要进行 2l 1 次比较． 计算第 2 类样本投影总共需要做l 2 次运算， 同样求取第 2 类样本投影的最大值和最小值最多只需要进行 2l 2 次比较． 因此步 2 的时间复杂度为 O(n)， 其中 n = l 1 + l 2 ， 为样本的总数目．对于步 3:需要对每个样本判断是否满足 2. 4. 1节中的不等式关系， 因此时间复杂度为 O(n)．又由 于 标 准 支 持 向 量 机 的 时 间 复 杂 度 是O(n 3 ) ［2 ］ ， 因此综上所述 SVMLFD 算法的时间复杂度为 O(d 2 n + k 3 )， 其中， k 表示边界向量集合的大小且 kn． 所以相对于标准支持向量机算法 O(n 3 )的时间复杂度和 O(n 2 )的空间复杂度， SVMLFD 算法的时间与空间复杂度分别降低为 O(d 2 n + k 3)和O(k 2 )．

2. 6. 2 非线性可分情况的时空复杂度分析对于非线性情况， 空间复杂度仍为 O(k 2 )， 时间复杂度则主要取决边界向量集合的确定和边界向量集合上的标准支持向量机训练， 其中边界向量集合的确定主要包含以下几个内容的计算:(1) 特征空间中心距离以及各样本的自中心距离和互中心距离的计算．(2) 各样本在中心向量投影方向上的投影与第1 类样本中心 m1ψ之间的距离;第 1 类样本投影到m1ψ的最大距离;第2 类样本投影到 m1ψ的最小距离．(3) 根据 2. 4. 2 节中不等式约束关系， 确定边界向量集合．下面分别对各个内容的计算复杂度进行分析．内容(1)． 需要计算的距离分别是特征空间中的中心距离、 两类样本的自中心距离和两类样本的互中心距离． 根据式(4)， (7) ～ (10)， 可知这 5 类距离共同包含对 ∑l 1i =1∑l 1j =1K(x 1i ， x1j )或者 ∑l 2i =1∑l 2j =1K(x 2i ， x2j )的计算， 可以将这两个数量预先求出． 因此这 5 类距离主要需计算 l 21 + l22次．内容(2)． 在求出上面 5 类距离的基础上， 利用余弦定理可以求出各样本在中心向量方向上的投影与第1 类样本中心 m1ψ之间的距离， 主要需要计算 l 1+ l 2 次， 而求取第 1 类样本投影到 m1ψ的最大距离，第 2 类样本投影到 m1ψ的最小距离， 则一共最多需要比较 l 1 + l 2 次．内容(3)． 为了判断各样本投影是否满足不等式约束， 需要比较 l 1 + l 2次．由于 n = l 1 + l 2 ， 因此边界向量集合确定的计算复杂度为 O(n 2 )． 又由于标准支持向量机的时间复杂度是 O(n 3 )， 所以 SVMMVP 算法时间复杂度为 O(n 2 + k 3 )， k 表示边界向量集合的大小． 因此在kn的情况下， SVMMVP 算法与标准支持向量机算法相比也具有更低的时间和空间复杂度．

3 仿真实验

本节选用了两个人工数据集和一个实际问题数据集进行算法的测试， 以说明本文所提出的新的支持向量机算法在达到较高分类精度的前提下， 具有较低的时间复杂度．

3. 1 线性可分问题实例为了与文献［ 15］对比， 本实验数据选取文献［ 15］ 中的实例:两类均匀分布的样本， 第 1 类样本服从分布 U(［ 0， 2］×［ 0， 0. 95］ )， 第 2 类样本服从分布 U(［ 0， 2］×［ 1. 05， 2］ )． 对于每一类， 随机生成800 个样本， 其中随机选取 300 个作为训练样本， 其余的作为测试样本． 本实验分别利用标准支持向量机算法、 文献［ 15］中线性可分算法和本文提出的SVMLFD 算法进行．对于上述 3 种算法， 分别选择 C- SVC ［18 ］ 和径向基函数K(x， y) = exp －x － y22σ( ) 2(18)作为基本的分类算法和核函数， 其中 C 是惩罚因子， σ 是宽度参数， x 与 y 是原始样本空间中的 n 维向量． 本实验中通过 10 折交叉验证［19 ］ 来确定最优的参数 C 和 σ． 根据文献［ 15］ 中线性可分算法采取D =0 和 μ =0. 1， 可获得较优结果的情况， 本次测试对于参数 D 和 μ 的取值不变;对于本文提出的SVMLFD 算法， 为了有效地权衡时空复杂度和分类精度， 取 λ = 0. 1． 于是， 采用 3 种算法的 5 次 10 折交叉验证的平均实验结果如表 1 所示， 其中对于文献［ 15］ 中线性可分算法和 SVMLFD 算法的训练时间包括边界向量确定时间和边界向量集合上的标准支持向量机训练时间．表 1 标准支持向量机算法、 文献［ 15］ 中线性可分算法和 SVMLFD 算法分类比较算法 边界向量集合大小 训练时间/s 精度/%标准支持向量机算法 无 283. 2 100文献 ［ 15］ 中线性可分算法 55 2. 1 100SVMLFD 算法32 1. 3 100由表 1 可以看出， 标准支持向量机算法的训练时间要比文献［ 15］中线性可分算法和 SVMLFD 算法长得多， 主要原因在于标准支持向量机算法的求解过程是在整个原始训练集上进行的， 而后两种算法的求解过程仅仅是在边界向量集合上进行． 尽管后两种算法训练时间还包括边界向量确定时间， 但是由 2. 6 节的时间复杂度分析可知， 在边界向量集合样本数目足够小的情况下， 后两种算法的运行时间较标准支持向量机算法少得多． 对比文献［ 15］ 中线性可分算法和 SVMLFD 算法， 可以发现本文提出的 SVMLFD 算法的训练时间更短一些， 其主要原因是 SVMLFD 算法利用 Fisher 线性判别确定投影直线， 所确定的直线满足好的投影直线的特征， 能够更好地对原始样本的投影进行分离， 可以更为方便地确定边界向量集合， 从而可以用更少的原始样本来构造边界向量集合． 因此尽管利用 Fisher 线性判别确定投影直线的操作较文献［ 15］中确定中心向量所在直线的操作耗费时间多， 但根据 2. 6 节的时间复杂度分析可知， 在所选边界向量集合样本数目足够小的情况下， SVMLFD 算法的运行时间仍然会比文献［ 15］ 中线性可分算法的运行时间少．表 1 还表明 SVMLFD 算法能达到标准支持向量机算法同样的精度， 主要原因是 SVMLFD 算法从原始训练样本集中抽取的边界向量集合， 包括了原始训练样本集中所有的支持向量． 这可以从图 1 中清晰的看出来． 图 1 是从本实验中选取的一幅样本分布图片， 其中空心点和实心点分别代表两类不同的样本， 加圈的点代表选取的边界向量， 五星形点代表由标准支持向量机算法确定的支持向量． 由图 1可以看出， 边界向量集合包括了所有的支持向量， 并排除了大多数非支持向量．

3. 2 非线性可分问题实例为了与文献［ 15］对比， 本实验数据选取文献［ 15］ 中的实例:两类交错的同心圆样本x = ρcosθy = ρsin{θ(19)其中 θ∈U［ 0， 2π］ ， 第 1 类样本的半径服从均匀分布 U［ 0， 6］ ， 第 2 类样本的半径服从均匀分布 U［ 5，10］ ． 对每一类随机产生 800 个样本， 其中随机选择300 个作为训练样本， 剩下的作为测试样本． 本实验将对标准支持向量机算法、 文献［ 15］ 中非线性可分算法和 SVMMVP 算法进行测试， 仍然选择 C- SVC 算法作为基本分类算法， 选择式(18)中所定义的径向基函数作为核函数． 本实验中通过 10 折交叉验证来确定最优的参数 C 和 σ． 根据文献［ 15］ 中线性可分算法采取取 D =10 和 μ =0. 1， 可获得较优结果的情况， 本次测试对于参数 D 和 μ 的取值不变;对于本文提出的 SVMMVP 算法， 为了有效地权衡时空复杂度和分类精度， 取 λ =0. 2． 3 种算法的 5 次 10 折交叉验证的平均实验结果如表 2 所示．表 2 标准支持向量机算法、 文献［ 15］ 中非线性可分算法和 SVMMVP 算法分类比较算法 边界向量集合大小 训练时间/s 精度/%标准支持向量机算法 无 331. 4 94. 9文献 ［ 15］ 中非线性可分算法 182. 0 59. 6 91. 2SVMMVP 算法 155. 041. 3 93. 1由表 2 可以看出， SVMMVP 算法与文献［ 15］ 中非线性可分算法的训练时间要比标准支持向量机算法的训练时间少得多， 主要原因在于这两种算法各自所确定的边界向量集合的大小较原始训练集小得多． 由表 2 可以进一步看出， SVMMVP 算法可以选取更少的边界向量进行训练， 可以进一步降低训练时间， 而精度却较文献［ 15］中非线性可分算法的高， 这主要是由于 SVMMVP 算法利用了特征空间中真正的中心向量所在直线作为投影直线， 可以更好地对特征空间中的样本投影进行分离， 从而可以更好地确定边界向量集合．表 2 还显示了 SVMMVP 算法几乎可以达到标准支持向量机算法的分类精度， 主要原因是对于SVMMVP 算法， 边界向量集合几乎包括了原始样本集中所有的支持向量， 这可以很明显地从图 2 中看出． 图 2 是从本实验中选取的一幅样本分布图片， 其中加号和点分别代表两类不同的样本， 星号代表选取的边界向量， 加圈的点代表由标准支持向量机算法确定的支持向量． 由图 2 可以看出， 边界向量集合几乎包括了所有的支持向量．

3. 3 实际问题数据集实例为了测试本文所提算法在大规模数据集上的性能， 利用入侵检测数据集进行试验． 本实验所采用的入侵检测数据集为 kdd- cup_10_per， 来自于 KDDCUP 99， 共包含 494021 条记录． 每一条记录包含 41个特征属性， 其中34 个属性为连续属性， 其余属性为离散属性． 该数据集包含23 个类别， 其中 “Normal” 表示正常连接行为， 其它 22 类(如 “Back” ， “Neptune” ，“Smurf” 等)是入侵行为． 本实验首先将这 23 类记录映射到 5 种类型， 即 Normal、 Dos、 R2L、 U2R 和Probing ［20 ］ ． 不同类型的数据分布如表 3 所示．表 3 不同类型的数据分布类型 记录数 比例/%Normal 97278 19. 69Dos 391458 79. 24Probing 4107 0. 83R2L 1126 0. 23U2R 52 0. 01

3. 3. 1 实验数据从 kdd- cup_10_per 数据集中选择 11 500 个样本． 为了更好地进行分类测试， 需要对每一种类型选取有效数目的样本， 具体分布如表 4 所示．表 4 所选数据集的分布类型 训练样本数 测试样本数Normal 900 960Dos 3700 3790Probing 600 800R2L 300 398U2R 30 22

3. 3. 2 字符属性数值化kdd- cup_10_per 数据集中的每一条记录包含 4个字符属性， 由于支持向量机算法只接受数值向量，所以需要对它们进行数值化， 具体方法可以参见文献［ 20］ ．

3. 3. 3 数据规范化由于原始数据中每个属性的取值范围不同， 因此需要对数据进行规范化． 本实验通过计算V =v － min(f i )max(f i ) － min(f i )(20)将连续属性的取值映射到区间［ 0. 0， 1. 0］ ， 其中 V为规范化后的属性值， v 为原始数据中的属性值，min(f i ) 和 max(f i ) 分别为属性 f i 的最小值和最大值．

3. 3. 4 实验结果为了对算法性能进行比较， 本实验采用如下两个性能指标:DR = d 1 /D 1FR = d 2 /D 2(21)其中:DR 表示检测率， FR 表示误报率， D 1 表示异常数据的总数， d 1 表示被检测出的异常数据的总数， D 2表示正常数据的总数， d 2 表示被误分的正常数据的数目． 本实验对 SMO 算法、 文献［ 15］ 中非线性可分算法(D =5， μ =0. 1)和 SVMMVP(λ =0. 2， λ =0. 3)算法进行测试， 选择 C- SVC 算法作为基本分类算法． 由于本实验是一个多分类问题， 因此选择一对多(1-v- r)分类方案． 本实验仍然选择式(18)中所定义的径向基函数作为核函数， 最优的参数 C 和 σ 仍然通过 10 折交叉验证来确定． 3 种算法的 5 次 10 折交叉验证的平均实验结果如表 5 所示．由表 5 可知， 对于大规模数据集， 本文所提出的SVMMVP 算法可以有效地缩短训练时间， 而且随着λ 值的增大， SVMMVP 算法在分类精确度上几乎可以和 SMO 算法相媲美， 而 SMO 算法是一种极为经典的支持向量机训练算法． 从表 5 还可以看出，SVMMVP 算法可以利用更少的训练时间达到甚至超过文献［ 15］ 中非线性可分算法的分类性能．

4 总 结

本文提出了一种新的支持向量预选取方法， 该方法采用投影的方式进行边界向量集合确定， 所确定的投影直线由于满足好的投影直线的特征， 可以更好地对样本的投影进行分离， 因此本文方法可以用更少的原始样本来构造边界向量集合． 针对得到的边界向量集合进行支持向量机训练， 可以在保证分类精度的前提下， 进一步降低训练时间和内存占用率． 因此， 本文提出方法， 为有效降低支持向量机算法的时空复杂度， 提供了一种新的思路， 有一定的借鉴作用．

参 考 文 献［ 1］ Vapnik V． Estimation of Dependences Based on Empirical Data． Springer- Verlag， 1982［ 2］ Vapnik V． The Nature of Statistical Learning Theory． Springer-Verlag， 1995［ 3］ Burges C J C． A tutorial on Support Vector Machines for patternrecognition． Data Mining and Knowledge Discovery，1998 (2):121- 167［ 4］ VamvakasG，Gatos B，Perantonis S J． Handwritten character rec-ognition through two- stage foreground sub- sampling． Pattern Rec-ognition， 2010， 43(8): 2807- 2816［ 5］ Dai G，Yeung D Y，Qian Y T． Face recognition using a kernelfractional- step discriminant analysis algorithm． Pattern Recogni-tion， 2007， 40(1): 229- 243［ 6］ ChoiS I，Kim C，Choi C H． Shadow compensation in 2D imagesfor face recognition． Pattern Recognition，2007，40(7): 2118-2125［ 7］ Oren M，Papageorgious C，Sinha P et al． Pedestrian Detection U-sing Wavelet Templates/ /Proceedings of the Computer Vision andPattern Recognition． San Jan，Puerto Rico， 1997: 193- 199［ 8］ Assheton P，Hunter A． A shape- based voting algorithm for pedes-trian detection and tracking． Pattern Recognition，2011，44(5):1106- 1120［ 9］ Joachims T． Text Categorization with Support Vector Machines．Technical Report: 23，University of Dortmund，Dortmund，Ger-many， 1997［ 10］ QinJ Z，Yung N H C． Scene categorization via contextual visualwords． Pattern Recognition， 2010， 43(5):1874- 1888［ 11］ Yang J， Yu X， Xie Z Q． A novel virtual sample generation meth-od based on Gaussian distribution． Knowledge- Based Systems，2011， 24 (6): 740- 748［ 12］ Vapnik V． Statistical Learning Theory． New York: Wiley，1998［ 13］ OsunaE，Freund R， Girosi F． An improved training algorithm forsupport vector machines/ /Proceedings of the IEEE Workshop onNeural Networks for Signal Processing． Amelia Island，USA，1997a: 276- 285［ 14］ Platt J C． Fast training of support vector machines using sequen-tial minimal optimization/ /Schlkopf B，Burges C J C，Smola AJ． Advances in Kernel Methods—Support Vector Learning． Cam-bridge，MA: MIT Press， 1999: 185- 208［ 15］ Li Qing，Jiao Li- Cheng，Zhou Wei- Da． Pre- extracting supportvectors for support vector machine based on vector projection．Chinese Journal of Computers， 2005， 28(2): 145- 152(in Chi-nese)(李青，焦李成，周伟达． 基于向量投影的支持向量预选取．计算机学报， 2005， 28(2): 145- 152)［ 16］ Yan Ping- Fan． Some views on the research of multilayer feedfor-ward neural networks． Aata Electronica Sinica，1999，27(5):82- 85(in Chinese)(阎平凡． 对多层前向神经网络研究的进一步看法． 电子学报， 1999， 27 (5): 82- 85)［ 17］ DudaR O， Hart P E， Stork D G． Pattern Classification． 2nd Edi-tion． Wiley， 2001［ 18］ Cortes C，Vapnik V N． Support- vector network． Machine Learn-ing， 1995， 20(8): 273- 297［ 19］ KohaviR． A study of cross- validation and bootstrap for accuracyestimation and model selection/ /Proceedings of the 14th Joint In-ternational Conference on Artificial Intelligence． Montreal，Cana-da， 1995: 1137- 1143［ 20］ Dong Chun- Xi． Study of support vector machines and its applica-tion in intrusion detection systems［Ph． D． Dissertation］． XidianUniversity，Xi'an，China， 2004(in Chinaese)(董春曦． 支持向量机及其在入侵检测中的应用研究［博士学位论文］ ． 西安电子科技大学，西安， 2004)