《一种约减型支持向量域数据描述算法》由会员分享，可在线阅读，更多相关《一种约减型支持向量域数据描述算法（4页珍藏版）》请在金锄头文库上搜索。
1、th Proceedings of the 25 Chinese Control Conference 7-11 August, 2006, Harbin, Heilongjiang 一种约减型支持向量域数据描述算法1 1 引 言1(Introduction) 支持向量域数据描述 (Support Vector Domain Description, SVDD)是TAX1等人在支持向量机 （Support Vector Machine，SVM）基础上提出的一 种数据描述算法。SVDD的主要思想是寻求一个能 把所有训练样本包围起来的最小超球，以此最小超 球的边界作为分类界限来对数据进行分类和描述
2、。 作为一种单值分类算法，SVDD在机械故障检测和 说话人识别等方面有许多成功的应用2。但是当训 IEEE Catalog Number:06EX1310 此项工作得到宁波博士基金资助项目资助, 项目批准号: 2005A610002 练样本数目很多时，原有的学习算法将会耗费很长 时间，对一些时效性很强的任务，算法的实用性将 大打折扣。由于支持向量域描述的分类边界是一封 闭曲面，此曲面的形状是由处于其上的训练样本即 支持向量所决定的，该曲面不同地方的曲率是不同 的，通过研究我们发现不同曲率的支持向量，对曲 率形状的影响大小不同，去除那些小曲率的支持向 量，整个分类面的形状不会有大的改变，但支持向
3、 量数会减少很多。从而训练时间会大幅减少。 赵英刚1，刘仰光2，何钦铭1,2 1. 浙江大学 计算机科学与技术学院, 杭州 310027 E-mail: ygz129 2. 浙江大学宁波理工学院 信息科学与工程分院, 宁波 315100 lyg E-mail: 摘 要 摘 要 支持向量域数据描述(SVDD)是一种单值分类算法，用于将目标样本与其它非目标样本区分开来，引入 数学中曲率的概念,文中根据分类边界线附近支持向量曲率的大小来对训练集进行约减，提出了一种约减型的 支持向量域数据描述快速训练算法 RSVDD，该算法与传统 SVDD 相比减少了训练时所需的支持向量数目，因而 训练时间大大减少，
4、同时分类性能几乎不受大的影响，该算法在大规模训练样本学习中具有现实的意义。 关键词 关键词 支持向量域数据描述，曲率，约减学习 One Kind of Reduced Learning Algorithm for Support Vector Domain Description Yinggang Zhao1 Yangguang Liu2, Qinming He1,2 1. College of Computer Science, Zhejiang University, Hangzhou 310027, China 2. School of Information Science & Eng
5、ineering, Ningbo Institute of Technology, Zhejiang University, Ningbo 315100, China Abstract: As a kind of one-class classification algorithm，Support Vector Data Description (SVDD) was used to distinguish target objects from outliers objects. By introducing the mathematics concept of curvature, we r
6、educed the training samples according to the value of support vectors locating on the classification boundary, then a reduced learning Support Vector Data Description (RSVDD) algorithm based on the reduced support machines was presented in this paper. Compared with the traditional SVDD, RSVDD only u
7、sed reduced support machines to construct the final classification boundary, so the training time was decreased greatly, meanwhile, the classification performance of the RSVDD can hardly be dropped obviously, and RSVDD is useful and effective especially in large scale training samples problem. Key w
8、ords: support vector data description, curvature, reduced learning 830 2 支 持 向 量 域 数 据 描 述 简 述 (Support Vector Domain Description) 支持向量域描述的基本思想是把要描述的对象 作为一个整体，建立一个封闭而紧凑的区域，使 被描述的对象全部或尽可能多地包容在内， 而非 该类对象没有或尽可能少地包含在内，如图1所 示. 给 定 一 个 包 含N个 数 据 对 象 的 数 据 集 ， 用来构建 SVDD 的学习样本。 试图找到一个体积最小的超球体，使全部（或尽可 能多） 的都
9、包含在该球体内. 对于奇异点(outliers) 来说，它们就位于超球体的外面. 为了减少奇异点 的影响，使用松弛变量 ,1,2,.,i = i xN i x i 把奇异点排除在超球体的 外面. 最小化超球体的体积是一个二次规划问题， 即在约束条件 图图 1 支持向量域描述（SVDD）示意图 2 () () T i aaR+ ii xx下最小化 2 min i i RC+ ，其中0 i ，C是某个指定的 常数，起到控制对错分样本惩罚程度的作用，以实 现在错分样本的比例和算法复杂程度之间的折中。 这个优化问题的解是由下面的拉格朗日 （Lagrange） 泛函的鞍点给出的: 2 ( , ,) ii
10、i i L R aRC =+ 222 (2) iiii ii Raa ii + xx (1) 式中：0 i ；0 i 为Lagrange系数。求式（1） 的最小值可变换为求其对偶问题的最大值： ，式中( )(,)(,) iiiijij ii LKK= x xx x i 满足约束条件和01 i i = i C，并且在 此已经用核函数代替了内积； （ (,) ij K x x (,)()() T ijij K=x xxx() i x，() j x分别为样 本和 i x j x在特征空间中的映射） 为满足Mercer条件 的核函数，比如径向基函数 22 ( , )exp | /(2),0K=x zx
11、z. 对于一个新样本z，判断它是否属于目标样本，有 如下的判别函数，如果 2 ( , ),(2 ii i faKKz= ()zz zx z 2 , (,) ijij i j KR+ x x (2) 成立，则判断样本属于目标样本，即接受其为该 类，否则判断为非目标样本，拒绝接受. z 在实际的计算中， 多数的 i 将为0， 只有少部 分0 i ，与0 i 相对应的这些样本称之为支 持向量 （SV） ， 只有这些支持向量才决定了a和R 的值，其它非支持向量因其对应的0 i =，在计 算中将被忽略. 3 支持向量域约减分类算法(Support Vector Domain Reduced Classi
12、fication Algorithm) 由于SVDD的分类边界是由位于分类边界上的 支持向量决定的，所以要提高算法的训练速度可通 过减少这些支持向量的数目来实现。但如果任意减 少支持向量数目会降低算法的分类准确率， Kuan-Ming Lin等3提出了针对两类分类方法-支 持向量机的RSVM算法，但该算法对单分类的 SVDD算法不太实用。Y. Zhan等4提出了另外一种 针对SVM的快速学习算法，但该算法实际上即使针 对二分类的SVM效果也不明显。 从图 1 我们可以直观地感觉到如果分别删除位于分 类边界上不同的支持向量比如 SV1 和 SV2， 将得到 弯曲程度不同的分类边界。图 2(a)和
13、图 2(b)形象地 说明了当分别去除 SV1 和 SV2 后重新训练样本集 得到的新的分类边界线的情况。 图 2 (a) 去除 SV1 后 SVDD 边界示意图 831 图 2 (b) 去除 SV2 后 SVDD 边界示意图 从图 2（a）我们看到当去除 SV1 后新得到的边 界线上的支持向量数从图 1 中的 12 个减少为 8 个， 当去除 SV1 后新得到的边界线上的支持向量数从 图 1 中的 12 个减少为 10 个。但我们同时看到尽管 图 2(a)中的支持向量数目减少了，但它的分类性能 并没有明显降低，仍然很好地区分了目标样本和非 目标样本（奇异点） 。 之所以会出现这种情况是是因为不
14、同的支持向 量对分类边界的弯曲程度贡献不同， 对于 SV1 由于 其曲率较 SV2 大， 所以对整个分界线的弯曲程度贡 献也要大些。 由于去除类似于 SV1 这样的曲率较大 的点能更多地减少构造SVDD分类边界所需的支持 向量数而又不影响分类性能，我们可以在改进的 SVDD 算法中刻意减少一些曲率较大的点，以此来 减少算法的训练时间，提高训练速度。下面给出我 们的改进算法： Step 1: 利用所有的训练样本得到一个初始的 SVDD， 假设我们求得包含个支持向量的支持向 量集和相应的判别函数 1 l 1 ,1,2,., i SV il= 1( ) f z； Step 2: 求得这个支持向量在分
15、类边界上的曲 率，并将它们按降序方式排序； 1 l Step 3: 从训练集中去除（）个曲率最 大的支持向量样本，然后重新训练剩余的样本，得 到包含个支持向量的新的向量的支持向量集 和相应的判别函数 n 1 nl 2 l Re 2 ,1,2,., i SVil= Re 2 ( )fz， 通常要远小于； 2 l 1 l Step 4：利用这个支持向量作为训练样本去 训练新的分类边界， 最后得到判别函数 2 l Re 3 ( )fz和新 的分类边界 （位于此分类边界上的支持向量数为， 3 l 32 lll1） 4 实 验(Experiments) 为了验证文中算法的性能，我们将该算法与 未对训练样
16、本进行约减前的标准SVDD算法进行 了对比实验， 实验选取了来自UCI数据库中的四个 数据集:Balance-scale, Breast-cancer, Ionosphere, Iris进行测试, 所有的数据都被处理为均值为0， 标 准差0.5. 数据集的基本信息见表1. 具体的实验环 境是PC机(P4 1.7G, 512M内存)，winXP操作系统。 实验中以径向基函数 2 2 ( ,)exp() 2 ij ij xx k x x =为核函数，其中 0.5= 由表 1 可以看出这些数据都不是单分类问题,但 我们通过可以把每个数据集中的某一类样本看作目 标类样本而其它类看做非目标类(outliers)样本的方 法将它们转化为单分类问题. 实验结果见表 2, 我 们以分类准确率和训练时间作为衡量指标。从表 2 的实验结果可以看出,和训练样本未约减前
