第13卷第1期 智能系统学报 Vol.13 No.I 2018年2月 CAAI Transactions on Intelligent Systems Feb.2018 D0:10.11992/tis.201610019 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20170702.0418.002.html 可拓支持向量分类机 陈晓华'，刘大莲2，田英杰3，李兴森 (1.北京联合大学教务处，北京100101；2.北京联合大学基础部，北京100101,3.中国科学院虚拟经济与数据科学 研究中心，北京100190：4.浙江大学宁波理工学院管理学院，浙江宁波315100) 摘要：针对分类问题.基于可拓学的思想，提出了可拓支持向量分类机算法。与标准的支持向量分类机不同，可拓 支持向量机在进行分类预测的同时，更注重于找到那些通过变化特征值而转换类别的样本。文中给出了可拓变量和 可拓分类问题的定义，并构建了求解可拓分类问题的两种可拓支持向量机算法。把可拓学与SVM结合是一种新的 方向，文中所提出的算法还有待进一步的理论分析，将在未来的工作里，继续探索如何在可拓学的基础上，构建更加 完善的可拓SVM方法。 关键词：数据挖掘：可拓学：分类：支持向量机：最优化：最优化核函数；先验知识：统计学习理论 中图分类号：TP181文献标志码：A文章编号：1673-4785(2018)01-0147-05 中文引用格式：陈晓华，刘大莲，田英杰，等.可拓支持向量分类机.智能系统学报，2018,131：147-151. 英文引用格式：CHEN Xiaohua,,LIU Dalian,.TIAN Yingjie,et al Extension support vector classification machine.CAAI transac- tions on intelligent systems,2018,13(1):147-151. Extension support vector classification machine CHEN Xiaohua',LIU Dalian',TIAN Yingjie',LI Xingsen' (1.Dean's office,Beijing Union University,Beijing 100101,China;2.Department of Basic Course Teaching,Beijing Union Uni- versity,Beijing 100101,China;3.Research Center on Fictitious Economy and Data Science,Chinese Academy of Sciences,Beijing 100190,China;4.School of Management,Ningbo Institute of Technology,Zhejiang University,Zhejiang 315100,China) Abstract:We propose an extension support vector machine(ES VM)to address the classification problem.Unlike the standard support vector machine,ESVM considers samples that can be converted into different labels by changing some feature values.We define the extension variables and extension classification problems and construct the corresponding optimization problem using a heuristic algorithm.In the future,we will improve the proposed method to incorporate the extension theory Keywords:data mining;extension;classification;support vector machine;optimization;kernel function;prior know- ledge;statistical learning theory 随着社会的进步，科学技术的飞速发展，当今 一类数学、计算机和管理等多学科相结合的交叉科 各种社会生产活动中每时每刻都在产生大量的数据 学。其旨在从海量数据中识别、提取有效的、新颖 信息，而随着计算机技术的不断进步，互联网的出 的甚至潜在有用的以及最终可被识别、理解的知 现使得全球数据共享成为现实，从而全面进人了大 识，从而作为管理决策者进行决策的科学决策依 数据时代。因此如何将海量数据进行充分有效地挖 据。数据挖掘作为一个热门研究领域，涉及的新方 掘和利用从而指导社会生产是当前数据挖掘领域的 法有神经网络、决策树、随机森林、支持向量机、深 核心任务。数据挖掘是20世纪80年代后期出现的 度学习等。 收稿日期：2016-10-15.网络出版日期：2017-07-02 可拓数据挖掘是将可拓学的理论和方法 基金项目：国家自然科学基金项目(61472390.11271361.71331005)： 北京市自然科学基金项自(1162005)， 与挖掘数据的方法、技术相结合的一门新技术。它 通信作者：刘大莲.E-mail:Idlluck(@sina.com. 在发现事物的类别转化以及识别潜在的变换知识等
DOI: 10.11992/tis.201610019 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20170702.0418.002.html 可拓支持向量分类机 陈晓华1 ，刘大莲2 ，田英杰3 ，李兴森4 （1. 北京联合大学 教务处，北京 100101; 2. 北京联合大学 基础部，北京 100101; 3. 中国科学院 虚拟经济与数据科学 研究中心，北京 100190; 4. 浙江大学宁波理工学院 管理学院，浙江 宁波 315100） 摘 要：针对分类问题，基于可拓学的思想，提出了可拓支持向量分类机算法。与标准的支持向量分类机不同，可拓 支持向量机在进行分类预测的同时，更注重于找到那些通过变化特征值而转换类别的样本。文中给出了可拓变量和 可拓分类问题的定义，并构建了求解可拓分类问题的两种可拓支持向量机算法。把可拓学与 SVM 结合是一种新的 方向，文中所提出的算法还有待进一步的理论分析，将在未来的工作里，继续探索如何在可拓学的基础上，构建更加 完善的可拓 SVM 方法。 关键词：数据挖掘；可拓学；分类；支持向量机；最优化；最优化核函数；先验知识；统计学习理论 中图分类号：TP181 文献标志码：A 文章编号：1673−4785(2018)01−0147−05 中文引用格式：陈晓华, 刘大莲, 田英杰, 等. 可拓支持向量分类机[J]. 智能系统学报, 2018, 13(1): 147–151. 英文引用格式：CHEN Xiaohua, LIU Dalian, TIAN Yingjie, et al. Extension support vector classification machine[J]. CAAI transactions on intelligent systems, 2018, 13(1): 147–151. Extension support vector classification machine CHEN Xiaohua1 ，LIU Dalian2 ，TIAN Yingjie3 ，LI Xingsen4 (1. Dean’s office, Beijing Union University, Beijing 100101, China; 2. Department of Basic Course Teaching, Beijing Union University, Beijing 100101, China; 3. Research Center on Fictitious Economy and Data Science, Chinese Academy of Sciences, Beijing 100190, China; 4. School of Management, Ningbo Institute of Technology, Zhejiang University, Zhejiang 315100, China) Abstract: We propose an extension support vector machine (ESVM) to address the classification problem. Unlike the standard support vector machine, ESVM considers samples that can be converted into different labels by changing some feature values. We define the extension variables and extension classification problems and construct the corresponding optimization problem using a heuristic algorithm. In the future, we will improve the proposed method to incorporate the extension theory. Keywords: data mining; extension; classification; support vector machine; optimization; kernel function; prior knowledge; statistical learning theory 随着社会的进步，科学技术的飞速发展，当今 各种社会生产活动中每时每刻都在产生大量的数据 信息，而随着计算机技术的不断进步，互联网的出 现使得全球数据共享成为现实，从而全面进入了大 数据时代。因此如何将海量数据进行充分有效地挖 掘和利用从而指导社会生产是当前数据挖掘领域的 核心任务。数据挖掘是 20 世纪 80 年代后期出现的 一类数学、计算机和管理等多学科相结合的交叉科 学。其旨在从海量数据中识别、提取有效的、新颖 的甚至潜在有用的以及最终可被识别、理解的知 识，从而作为管理决策者进行决策的科学决策依 据。数据挖掘作为一个热门研究领域，涉及的新方 法有神经网络、决策树、随机森林、支持向量机、深 度学习等。 可拓数据挖掘[1-6]是将可拓学的理论和方法[7-8] 与挖掘数据的方法、技术相结合的一门新技术。它 在发现事物的类别转化以及识别潜在的变换知识等 收稿日期：2016−10−15. 网络出版日期：2017−07−02. 基金项目：国家自然科学基金项目 (61472390，11271361，71331005)； 北京市自然科学基金项目 (1162005). 通信作者：刘大莲. E-mail：ldlluck@sina.com. 第 13 卷第 1 期 智 能 系 统 学 报 Vol.13 No.1 2018 年 2 月 CAAI Transactions on Intelligent Systems Feb. 2018
·148· 智能系统学报 第13卷 方面有着广阔的应用前景。 本文吸取了可拓学寻找变换知识的思想，考虑 minyyx)o-a =11 事物的某种性质的变化所带来的问题转化，结合当 S.t. ya:=0 户1 前已经非常成熟的支持向量机模型，从而提出了可 0≤a≤C,i=1,…,l 拓支持向量机这一新的可拓数据挖掘新方法。 得到解=[a5,…,。 1支持向量机 3)计算最优超平面参数(w,b): w=∑ayx 支持向量机(support vector machine,SVM)9-is] =1 b=y-(w*·x,je{0≤a≤C} 是一种通用的、有效的机器学习算法，主要建立在 4)构造分划超平面(w·x)+b=0,从而求出决策函 统计理论(statistical learning theory,.SLT)、最优化理 数fx)=sgn(w·x)+b)0 论及核理论的三大理论基础之上。以分类问题为 算法1为针对线性分类问题的SVM算法，事 例，SVM首先把输入映射到某一个高维的特征空间 实上在很多实际问题中，分类问题并不能被线性分 中，利用统计学习理论中的结构风险最小化原则把 划。这时需引入从空间R到Hilbert空间的变换 分类问题转化为一个凸二次规划问题来解决；然后 x=(),将训练集变换到特征空间并在该空间执行 利用最优化理论中的对偶理论，得到该凸规划的对 算法1，相应地，(，)转化为(()，(》，而 偶问题，使得引入核函数成为可能；最后再利用核 (④(x,(x》的计算可以通过引进核函数K(x,x)= 理论来处理非线性分类的情况。与数据挖掘中的 (x),(x)代替计算。通常，常用的核函数有RBF 其他方法相比，SVM理论相对完备，较好地解决了 核函数、多项式核函数、B样条核函数等。 其他方法中经常出现的一些棘手问题。随着科学技 术的进步和完善，支持向量机的研究也更为深入广 2可拓支持向量机 泛，许多新的理论、算法层出不穷，应用领域更为 广阔。 在实际问题中，我们不仅关注对未知样本的类 标准的两类分类问题为：给定训练集 别预测，更关心已有类别或被预测了类别的样本能 S={(x1y),(x2,y2)…,(,}R" (1) 否转化到相反的类别，在什么条件下会转化，所付 式中：x∈R,y∈={1，-1，i=1,2,…,1。在此基础 出的代价有多大。这些在可拓学里被称为变换的知 上，试寻找定义在R空间上的一个实值函数g(x),从 识。挖掘这些变换的知识的一个途径，就是找到那 而得到决策函数： 些可以变换的特征或变量。以疾病的辅助诊断为 f(x)=sgn (g(x)) (2) 例，患者患有疾病的相关特征（变量）有很多，比如 以便推断任意x对应的输出y。若g(x)是线性函数 性别、年龄、身高、体重、血压（低压）、胆固醇、血常 g(x)=(w·x)+b,则式(2)对应着用超平面(w·)+ 规等，这些变量中，对某个患者来说，其性别就是不 b=0将空间R"分成两部分，称为线性分类机。 可变换的变量，而血压则可以通过吃药等治疗手段 基于结构风险最小化原则，SVM构造出的线性 变高或变低。那么在解决疾病辅助诊断的分类问题 分类机的原始最优化问题为 时，我们一方面希望决策函数能准确地预测未知样 本的类别，另一方面希望这个决策函数能找到那些 wr+c∑ (3) 可以互相转换类别的样本，这样就可以找到更多的 s.t.ya(w…x+b)≥1-ξi,i=1,2,,1 (4) 变换的知识。首先给出以下定义。 5≥0，i=1.2,…,1 (5) 可拓变量若向量x=(,…,[x)中分量 式中5=[店…「，C≥0是一个惩罚参数。通过求解 的值可以变化，则称[x)为可拓变量。 上述问题的对偶问题（见算法1中的优化问题）， 可拓变量集合由全体可拓变量构成的集合则 SVM建立了处理二分类的线性算法（算法1）。 称为可拓变量集合，记为E。 算法1SVM 可拓变量区间可拓变量[x],的值所变化的区 输入输入训练集（见(1）式)： 间[a,b]称为可拓变量区间。 输出分划超平面以及决策函数。 可拓分类问题给定训练集 1)输人训练集（见式(1）)，并选择合适的惩罚参 S={(y1),(,2),…,(n}≤（®"×Y/ (6) 数C≥0. 式中：：∈R",[xl,jeE,可在某个区间内变化，y:∈= 2)构造并求解凸二次规划问题： {1,-1,i=1,2,…,1。基于此，在R空间上寻找一个实
方面有着广阔的应用前景。 本文吸取了可拓学寻找变换知识的思想，考虑 事物的某种性质的变化所带来的问题转化，结合当 前已经非常成熟的支持向量机模型，从而提出了可 拓支持向量机这一新的可拓数据挖掘新方法。 1 支持向量机 支持向量机 (support vector machine, SVM)[9-18] 是一种通用的、有效的机器学习算法，主要建立在 统计理论 (statistical learning theory, SLT)、最优化理 论及核理论的三大理论基础之上。以分类问题为 例，SVM 首先把输入映射到某一个高维的特征空间 中，利用统计学习理论中的结构风险最小化原则把 分类问题转化为一个凸二次规划问题来解决；然后 利用最优化理论中的对偶理论，得到该凸规划的对 偶问题，使得引入核函数成为可能；最后再利用核 理论来处理非线性分类的情况。与数据挖掘中的 其他方法相比，SVM 理论相对完备，较好地解决了 其他方法中经常出现的一些棘手问题。随着科学技 术的进步和完善，支持向量机的研究也更为深入广 泛，许多新的理论、算法层出不穷，应用领域更为 广阔。 标准的两类分类问题为：给定训练集 S = {(x1,y1),(x2, y2),···, (xl ,yl)} ⊆ R n (1) xi ∈ R n , yi ∈ = {1,−1},i = 1,2,···,l R n g(x) 式中： 。在此基础 上，试寻找定义在 空间上的一个实值函数 ，从 而得到决策函数： f(x) = sgn (g(x)) (2) g(x) g(x) = (w· x)+b (w· x)+ b = 0 R n 以便推断任意 x 对应的输出 y。若 是线性函数 ，则式 ( 2 ) 对应着用超平面 将空间 分成两部分，称为线性分类机。 基于结构风险最小化原则，SVM 构造出的线性 分类机的原始最优化问题为 min w,b,ξ 1 2 ∥w∥ 2 +C ∑l i=1 ξi (3) s.t. yi(w· x+b) ⩾ 1−ξi ,i = 1,2,···, l (4) ξi ⩾ 0,i = 1,2,···, l (5) ξ = [ξ1 ··· ξl] T 式中 ,C ⩾ 0 是一个惩罚参数。通过求解 上述问题的对偶问题 (见算法 1 中的优化问题)， SVM 建立了处理二分类的线性算法 (算法 1)。 算法 1 SVM 输入 输入训练集 (见 (1) 式)； 输出 分划超平面以及决策函数。 C ⩾ 0 1) 输入训练集 (见式 (1))，并选择合适的惩罚参 数 。 2) 构造并求解凸二次规划问题： min w,b,ξ 1 2 ∑l i=1 ∑l j=1 yiyj(xi · xj)αiαj− ∑l j=1 αi s.t. ∑l j=1 yiαi = 0 0 ⩽ αi ⩽ C,i = 1,···, l α ∗ = [α ∗ 1 x ∗ 2 ,···, α∗ l ] 得到解 T。 (w ∗ ,b ∗ 3) 计算最优超平面参数 )： w ∗ = ∑l i=1 α ∗ i yixi ; b ∗ = yj−(w ∗ · xj), j ∈ { j|0 ⩽ α ∗ i ⩽ C } (w ∗ · x)+b = 0 f(x) = sgn((w ∗ · x)+b) 4) 构造分划超平面 , 从而求出决策函 数 。 R n x = Φ(x) (xi , yi) (Φ(xi),Φ(xj)) (Φ(xi),Φ(xj)) K(x, x ′ ) = (Φ(x),Φ(x ′ )) 算法 1 为针对线性分类问题的 SVM 算法，事 实上在很多实际问题中，分类问题并不能被线性分 划。这时需引入从空间 到 Hilbert 空间的变换 ，将训练集变换到特征空间并在该空间执行 算 法 1 ，相应地， 转化为 ， 而 的计算可以通过引进核函数 代替计算。通常，常用的核函数有 RBF 核函数、多项式核函数、B 样条核函数等。 2 可拓支持向量机 在实际问题中，我们不仅关注对未知样本的类 别预测，更关心已有类别或被预测了类别的样本能 否转化到相反的类别，在什么条件下会转化，所付 出的代价有多大。这些在可拓学里被称为变换的知 识。挖掘这些变换的知识的一个途径，就是找到那 些可以变换的特征或变量。以疾病的辅助诊断为 例，患者患有疾病的相关特征 (变量) 有很多，比如 性别、年龄、身高、体重、血压 (低压)、胆固醇、血常 规等，这些变量中，对某个患者来说，其性别就是不 可变换的变量，而血压则可以通过吃药等治疗手段 变高或变低。那么在解决疾病辅助诊断的分类问题 时，我们一方面希望决策函数能准确地预测未知样 本的类别，另一方面希望这个决策函数能找到那些 可以互相转换类别的样本，这样就可以找到更多的 变换的知识。首先给出以下定义。 x = ( [x]1 , ···, [x]n) [x]j [x]j 可拓变量 若向量 中分量 的值可以变化，则称 为可拓变量。 可拓变量集合 由全体可拓变量构成的集合则 称为可拓变量集合，记为 E。 [x]j [aj ,bj] 可拓变量区间 可拓变量 的值所变化的区 间 称为可拓变量区间。 可拓分类问题 给定训练集 S = {(x1,y1),(x2, y2),···, (xl ,yl)} ⊆ (R n × ) l (6) xi ∈ R n , [xi]j , j ∈ E yi ∈ {1,−1},i = 1,2, ···, l R n 式中： ，可在某个区间内变化， = 。基于此，在 空间上寻找一个实 ·148· 智 能 系 统 学 报 第 13 卷
第1期 陈晓华，等：可拓支持向量分类机 ·149· 值函数g(x),得到决策函数： 得到解a=[a5,…,aT。 f(x)=sgn(g(x)) (7) 3)计算最优超平面参数： 以便推断任意x对应的输出y,并判断其是否可以 变换为相反的输出-y。 w=∑ayx 可拓样本若样本点x可以通过改变某个或某 b=y-(wx),je0≤a≤C 些可拓变量的值而改变类别标号，则称x为可拓 4)构造分划超平面(w·x)+b=0,从而求出决策函 样本。 数fx)=sgn(w·)+b)。 下面给出可拓分类问题示意性的例子。图1中 5)对输入x,首先用决策函数f(x)得到其对应 给出了两类点，分别用▲和■表示，分量[x2为可拓 的预测类别%，然后用其可拓变量对应的可拓区间 变量。图1(a)所示的是所有点的可拓变量区间均 a和b分别代替[xJ,这样对E个可拓变量，会得到 满足[x2∈[a,b]的情况，即所有点被上下两条直线 2个不同的组合值，相应的，我们基于x,得到了 [x2=a和[x2=b所控制；图1(b)所示的是每个点的 2个新的输入，分别用决策函数来判断，若有一个 可拓变量区间不同的情况，即满足[x,∈[d,b,在图 被判断为%，则认为该输入是可变换的。 中就是每个点分别被双箭头线段所控制。 对图1(a)所示的例子，可以用算法2得到图 2(a)所示的分划线，因该问题的可拓变量区间为定 [x 值，所以可以直接得到两条垂直的线，在这两条垂 直线中间的点都是可拓样本（用圆圈标注），并用箭 头表示该样本在可拓变量的变化方向。对图1(a) 所示的例子，用算法2得到图2(b)所示的分划线， 可以看出没有可拓样本点，即没有点可以通过可拓 0 [x) 变量的区间变化来达到类别标号的改变。 (a)可拓变量区间固定 ]2 [2 0 (a)可拓区间固定的分划线 0 [x]2 b)可拓变量区间变化 图1可拓分类问题 Fig.1 Extension classification problem 注意，与标准的两类分类问题不同，这里除了 0 给出标准的训练集外，还给出了每个点的可拓变量 b)可拓区间变化的分划线 区间。据此可以构建算法2：可拓SVM1。 图2可拓分类SVM 算法2可拓SVM1 Fig.2 Extention classification SVM 输入输入训练集（见式(1）)： 进一步，考虑稍微复杂的情况，若对上述的可 输出决策函数。 拓分类问题，增加了先验知识。该先验知识为：在 1)输入训练集（见式(1）)，并选择合适的惩罚参 给定的训练集S中，训练点x,的可拓变量 数C>0。 [x],i=1,2,,l,jeE在可拓区间内变化时，其y,没 2)构造并求解凸二次规划问题： 有变化，如何寻找决策函数来推断任意x对应的输 四gwy宫a 出y,并判断其是否可以变换为相反的输出-y。 =1 可以看出，这时候训练点的输入就不再是一个 s.t.】 y=0 点，而是一个集合。如果限定该集合是一个凸集， 0≤a≤C,i=1,2,…,l 比如为一个球体，则训练集变为
值函数 g(x) ，得到决策函数： f(x) = sgn(g(x)) (7) 以便推断任意 x 对应的输出 y，并判断其是否可以 变换为相反的输出–y。 可拓样本 若样本点 x 可以通过改变某个或某 些可拓变量的值而改变类别标号，则称 x 为可拓 样本。 [x]2 [x]2 ∈ [a, b] [x]2 = a [x]2 = b [xi]j ∈[a i j , b i j ] 下面给出可拓分类问题示意性的例子。图 1 中 给出了两类点，分别用▲和■表示，分量 为可拓 变量。图 1(a) 所示的是所有点的可拓变量区间均 满足 的情况，即所有点被上下两条直线 和 所控制；图 1(b) 所示的是每个点的 可拓变量区间不同的情况，即满足 ，在图 中就是每个点分别被双箭头线段所控制。 注意，与标准的两类分类问题不同，这里除了 给出标准的训练集外，还给出了每个点的可拓变量 区间。据此可以构建算法 2：可拓 SVM1。 算法 2 可拓 SVM1 输入 输入训练集 (见式 (1))； 输出 决策函数。 1) 输入训练集 (见式 (1))，并选择合适的惩罚参 数 C >0。 2) 构造并求解凸二次规划问题： min w,b,ξ 1 2 ∑l i=1 ∑l j=1 yiyj(xi · xj)αiαj− ∑l j=1 αi s.t. ∑l j=1 yiαi = 0 0 ⩽ αi ⩽ C, i = 1,2, ···, l α ∗ = [α ∗ 1 x ∗ 2 ,··· ,α∗ l ] 得到解 T。 3) 计算最优超平面参数: w ∗ = ∑l i=1 α ∗ i yixi b ∗ = yj−(w ∗ · xj), j ∈ {j 0 ⩽ α ∗ i ⩽ C} (w ∗ · x)+b = 0 f(x) = sgn((w ∗ · x)+b) 4) 构造分划超平面 , 从而求出决策函 数 。 xk f(xk) a k j b k j [xk]j |E| 2 |E| 2 |E| 5) 对输入 , 首先用决策函数 得到其对应 的预测类别 yk，然后用其可拓变量对应的可拓区间 和 分别代替 ，这样对 个可拓变量，会得到 个不同的组合值，相应的，我们基于 xk 得到了 个新的输入，分别用决策函数来判断，若有一个 被判断为-yk，则认为该输入是可变换的。 对图 1(a) 所示的例子，可以用算法 2 得到图 2(a) 所示的分划线，因该问题的可拓变量区间为定 值，所以可以直接得到两条垂直的线，在这两条垂 直线中间的点都是可拓样本 (用圆圈标注)，并用箭 头表示该样本在可拓变量的变化方向。对图 1(a) 所示的例子，用算法 2 得到图 2(b) 所示的分划线， 可以看出没有可拓样本点，即没有点可以通过可拓 变量的区间变化来达到类别标号的改变。 [xi]j ,i = 1,2, ···, l, j ∈ E 进一步，考虑稍微复杂的情况，若对上述的可 拓分类问题，增加了先验知识。该先验知识为：在 给定的训练 集 S 中，训练 点 x i 的可拓变量 在可拓区间内变化时，其 yi 没 有变化，如何寻找决策函数来推断任意 x 对应的输 出 y，并判断其是否可以变换为相反的输出–y。 可以看出，这时候训练点的输入就不再是一个 点，而是一个集合。如果限定该集合是一个凸集， 比如为一个球体，则训练集变为 (a) ਟᤃਈ䟿४䰤പᇊ (b) ਟᤃਈ䟿४䰤ਈॆ [x]2 O [x]1 [x]2 O [x]1 图 1 可拓分类问题 Fig. 1 Extension classification problem (a) ਟᤃ४䰤പᇊⲴࡂ࠶㓯 (b) ਟᤃ४䰤ਈॆⲴࡂ࠶㓯 [x]2 O [x]1 [x]2 O [x]1 图 2 可拓分类 SVM Fig. 2 Extention classification SVM 第 1 期 陈晓华，等：可拓支持向量分类机 ·149·
·150· 智能系统学报 第13卷 S={X1,y1),(X2,2),,(X,ym} (8) 的矩形则为点在这些区间内变化时，类别发生了变 式中输入集合X,是一个以X,为球心、以”为半径 化。这时问题就变得复杂，需要引入可拓集的概念 的球体，y:∈7={1，-1，i=1,2,,l。那么该分类问 和关联函数来处理，这是进一步的研究方向。并且 题就转化为鲁棒支持向量机所求解的问题，此时 还可以将其拓展到应用广泛的多示例、多标签学习 构造的原始最优化问题为 等方面。 吧w2+c∑ (9) [x]. st.y:(w(x+x)+b)≥1-专 ≤1，i=1,2,…,1 (10) 5≥0，i=1,2,…,1 (11) 因为约束式(10)含有无穷多个约束，一般做法 0 [ 是把它转化成一个仅含有有限个约束的问题，并求 (a)可拓区间为球体 解相应的对偶问题1，据此构造可拓SVM2,见算 法3。 算法3可拓SVM2 输入输入训练集（见式(8）)： 输出决策函数。 0 1)输入训练集（见式(8）)，并选择合适的惩罚参 0 数C>0。 2)构造并求解二阶锥规划： 0 [xh 盟，u-W+C2 (b)可拓区间为矩形 =1 s.t.y:(w-(x+xw)+b)≥1-东，i=1,2,…,1 图3可拓分类SVM 5≥0，i=1,2,…,1 Fig.3 Extension classification SVM u+v=1 [uvtr∈L3 3结束语 [tw]P∈L+l 3)计算五，构造决策函数： 本文提出了一种新的分类方法一可拓支持向 f间=gn2对+20g-+万2 量机，可拓支持向量机在进行分类预测时较标准的 支持向量分类机有所不同，它更注重于找到那些通 式中(B)g=(x(△)g),9=1,2,…,no 过变化特征值而转换类别的样本。文中给出了可拓 4)对输入x,首先用决策函数fx)得到其对应 变量和可拓分类问题的定义，并构建了求解可拓分 的预测类别y,然后在其可拓变量对应的可拓区间 类问题的两种算法。基于此模型，我们可以在理论 内随机取值m次，这样对E个可拓变量，会得到 和方法上做一系列研究。理论上，包括对其相应的 m个不同的组合值，相应的，基于x得到了m个新 统计学习理论基础研究，可拓决策函数集的VC维 的输入，分别用决策函数来判断，若有一个被判断 估计，推广能力的上界估计，可拓结构风险的实现 为-y,则认为该输入是可变换的。 原理等：方法上，包括如何在标准的支持向量机模 如图3(a)所示，设[x、[x均为可拓变量，每 型中引入关联函数，构造可拓的核函数，对其相应 个点的可拓区间为半径不同的球体，空心圆是正 的大规模最优化问题的快速求解算法，模型参数选 类，实心圆是负类。根据算法3可得到图中的分划 择问题等。 线，则可知虚线所示的圆的圆心点为正类，但当该 点在圆内变化时，它的类别会改变。 参考文献： 如果先验知识为：在给定的训练集S中，训练 [1]蔡文，杨春燕，陈文伟，等.可拓集与可拓数据挖掘M.北 点x,的可拓变量[x],i=1,2…,1,jeE在可拓区间内 京：科学出版杜，2008 变化时，其y,产生了变化，如图3(b)所示。 CAI Wen,YANG Chunyan,CHEN Wenwei,et al.Exten- [x1,[x均为可拓变量，每个点的可拓区间为不同大 sion set and extension data mining[M].Beijing:Science 小的矩形，白色为正类，黑色为负类。而黑白相间 Press,2008
S = { (X1,y1), (X2, y2),···, (Xi , yl) } (8) yi ∈ = {1, −1}, i = 1,2, ···, l 式中输入集合 Xi 是一个以 Xi 为球心、以 ri 为半径 的球体, 。那么该分类问 题就转化为鲁棒支持向量机所求解的问题[15] ，此时 构造的原始最优化问题为 min w,b,ξ 1 2 ∥w∥ 2 +C ∑l i=1 ξi (9) s.t. yi(w·(xi + xiui)+b) ⩾ 1−ξi , ∀∥ui∥ ⩽ 1,i = 1,2,···,l (10) ξi ⩾ 0,i = 1,2,···,l (11) 因为约束式 (10) 含有无穷多个约束，一般做法 是把它转化成一个仅含有有限个约束的问题，并求 解相应的对偶问题[15] ，据此构造可拓 SVM2，见算 法 3。 算法 3 可拓 SVM2 输入 输入训练集 (见式 (8))； 输出 决策函数。 1) 输入训练集 (见式 (8))，并选择合适的惩罚参 数 C >0。 2) 构造并求解二阶锥规划： min w,b,ξ,u,v,t 1 2 (u−v)+C ∑l i=1 ξi s.t. yi(w ·(xi + xiui)+b) ⩾ 1−ξi , i = 1, 2,···, l ξi ⩾ 0, i = 1,2, ···, l u+v = 1 [u v t] T ∈ L 3 [t w] T ∈ L n+1 3) 计算 b¯，构造决策函数： f(x) = sgn(∑l i=1 αiyi(xi · x)+ ∑l i=1 yiBi T (β¯ ∗ i −β¯ i)+b¯) (12) ( B i ) q = ( x ·(∆i).,q ) 式中 ,q = 1,2,··· ,n。 f(xk) |E| m|E| m|E| 4) 对输入 xk , 首先用决策函数 得到其对应 的预测类别 yk，然后在其可拓变量对应的可拓区间 内随机取值 m 次，这样对 个可拓变量，会得到 个不同的组合值，相应的，基于 xk 得到了 个新 的输入，分别用决策函数来判断，若有一个被判断 为–yk，则认为该输入是可变换的。 如图 3(a) 所示，设 [x]1、[x]2均为可拓变量，每 个点的可拓区间为半径不同的球体，空心圆是正 类，实心圆是负类。根据算法 3 可得到图中的分划 线，则可知虚线所示的圆的圆心点为正类，但当该 点在圆内变化时，它的类别会改变。 [xi]j ,i = 1,2,···, l, j ∈ E [x]1, [x]2 如果先验知识为：在给定的训练集 S 中，训练 点 xi 的可拓变量 在可拓区间内 变化时， 其 y i 产生了变化，如 图 3(b ) 所示。 均为可拓变量，每个点的可拓区间为不同大 小的矩形，白色为正类，黑色为负类。而黑白相间 的矩形则为点在这些区间内变化时，类别发生了变 化。这时问题就变得复杂，需要引入可拓集的概念 和关联函数来处理，这是进一步的研究方向。并且 还可以将其拓展到应用广泛的多示例、多标签学习 等方面[19-22]。 3 结束语 本文提出了一种新的分类方法——可拓支持向 量机，可拓支持向量机在进行分类预测时较标准的 支持向量分类机有所不同，它更注重于找到那些通 过变化特征值而转换类别的样本。文中给出了可拓 变量和可拓分类问题的定义，并构建了求解可拓分 类问题的两种算法。基于此模型，我们可以在理论 和方法上做一系列研究。理论上，包括对其相应的 统计学习理论基础研究，可拓决策函数集的 VC 维 估计，推广能力的上界估计，可拓结构风险的实现 原理等；方法上，包括如何在标准的支持向量机模 型中引入关联函数，构造可拓的核函数，对其相应 的大规模最优化问题的快速求解算法，模型参数选 择问题等。 参考文献： 蔡文, 杨春燕, 陈文伟, 等. 可拓集与可拓数据挖掘[M]. 北 京: 科学出版杜, 2008. CAI Wen, YANG Chunyan, CHEN Wenwei, et al. Extension set and extension data mining[M]. Beijing: Science Press, 2008. [1] (a) ਟᤃ४䰤Ѫ⨳փ (b) ਟᤃ४䰤Ѫ⸙ᖒ [x]2 O [x]1 [x]2 O [x]1 图 3 可拓分类 SVM Fig. 3 Extension classification SVM ·150· 智 能 系 统 学 报 第 13 卷
第1期 陈晓华，等：可拓支持向量分类机 ·151· [2]杨春燕，蔡文.可拓工程M北京：科学出版社，2007. gorithms,and extensions[M].Boca Raton:CRC Press, YANG Chunyan,CAI Wen.Extension engineering[M]. 2013. Beijing:Science Press,2007. [16]HUANG Kaizhu,YANG Haiqin,KING I,et al.Learning [3]CAI Wen.Extension theory and its application[J].Chinese large margin classifiers locally and globally[C]//Proceed- science bulletin,1999,44(17):1538-1548. ing of the 21st International Conference on Machine Learn- [4]李立希，李铧汶，杨春燕.可拓学在数据挖掘中的应用初 ing.Banff,Alberta,Canada,2004. 探).中国工程科学，2004,6(7)：53-59. [17]SHAWE-TAYLOR J,CRISTIANINI N.Kernel methods LI Lixi,LI Huawen,YANG Chunyan.Study on the applica- for pattern analysis[M].Cambridge:Cambridge University tion of extenics in data mining[J].Engineering science, Press,2004. 2004,6(7):53-59. [18]BORGWARDT K M.Kernel methods in bioinformatics [)]陈文伟，黄金才.从数据挖掘到可拓数据挖掘[)智能技 [M]//LU HH S,SCHOLKOPF B,ZHAO Hongyu.Hand- 术，2006,1(2)：50-52 book of Statistical Bioinformatics.Berlin,Heidelberg: CHEN Wenwei,HUANG Jincai.From data mining to ex- Springer,2011:317-334 tension data mining[J].Intelligent technology,2006,1(2): [19]VAPNIK V,IZMAILOV R.Learning using privileged in- 50-52. formation:Similarity control and knowledge transfer[J]. [6]杨春燕，蔡文.可拓数据挖掘研究进展U数学的实践与 Journal of machine learning research,2015,16:2023- 认识，2009,39(4)：136-141. 2049. YANG Chunyan,CAI Wen.Recent progress in extension [20]SUN S.A survey of multi-view machine learning[J].Neur- data mining[J].Mathematics in practice and theory,2009, al computing and applications,23(7):2031-2038. 39(4):136-141 [21]CHEPLYTGINA V.TAX,D M.LOOG M.Multiple in- [刀蔡文，杨春燕，何斌.可拓逻辑初步M北京：科学出版社， stance learning with bag dissimilarities[J].Pattern recogni- 2003 tion,2015,48(1)264-275. CAI Wen,YANG Chunyan,HE Bin.Extension logic[M]. [22]CARBONNEAU M A,GRANGER E,RAYMOND A J,et Beijing:Science Press,2003. [8]蔡文，杨春燕，林伟初.可拓工程方法M.北京：科学出版 al.Robust multiple-instance learning ensembles using ran- dom subspace instance selection[J].Pattern recognition, 社，1999. CAI Wen,YANG Chunyan,LIN Weichu.Extension engin- 2016,58:83-99 eering methods[M].Beijing:Science Press,1999. 作者简介： [9]CORTES C,VAPNIK V.Support-vector networks[J].Ma- 陈晓华，女，1975年生，工程师， chine learning,1995,20(3):273-297. 主要研究方向为电力系统及其自动化。 [10]CRISTIANINI N.SHAWE-TAYLOR J.An introduction to support vector machines and other kernel-based learn- ing methods[M].Cambridge:Cambridge University Press, 2000. [11]VAPNIK V N.Statistical learning theory[M].New York: John Wiley and Sons,1998. 刘大莲，女，1978年生，副教授， [12]NOBLE W S.Support vector machine applications in com- 博土研究生，主要研究方向为数据挖掘。 putational biology[M]//SCHOELKOPF B,TSUDA K, VERT J P.Kernel Methods in Computational Biology. Cambridge:MIT Press,2004. [13]ADANKON MM,CHERIET M.Model selection for the LS-SVM.application to handwriting recognition[J].Pat- tern recognition,2009,42(12):3264-3270. 田英杰，男，1973年，研究员，博 士生导师，主要研究方向为最优化与 [14]TIAN Yingjie,SHI Yong,LIU Xiaohui.Recent advances 机器学习。 on support vector machines research[J].Technological and economic development of economy,2012,18(1):5-33. [15]DENG Naiyang,TIAN Yingjie,ZHANG Chunhua.Sup- port vector machines:optimization based theory,al-
杨春燕, 蔡文. 可拓工程[M]. 北京: 科学出版社, 2007. YANG Chunyan, CAI Wen. Extension engineering[M]. Beijing: Science Press, 2007. [2] CAI Wen. Extension theory and its application[J]. Chinese science bulletin, 1999, 44(17): 1538–1548. [3] 李立希, 李铧汶, 杨春燕. 可拓学在数据挖掘中的应用初 探[J]. 中国工程科学, 2004, 6(7): 53–59. LI Lixi, LI Huawen, YANG Chunyan. Study on the application of extenics in data mining[J]. Engineering science, 2004, 6(7): 53–59. [4] 陈文伟, 黄金才. 从数据挖掘到可拓数据挖掘[J]. 智能技 术, 2006, 1(2): 50–52. CHEN Wenwei, HUANG Jincai. From data mining to extension data mining[J]. Intelligent technology, 2006, 1(2): 50–52. [5] 杨春燕, 蔡文. 可拓数据挖掘研究进展[J]. 数学的实践与 认识, 2009, 39(4): 136–141. YANG Chunyan, CAI Wen. Recent progress in extension data mining[J]. Mathematics in practice and theory, 2009, 39(4): 136–141. [6] 蔡文, 杨春燕, 何斌. 可拓逻辑初步[M]. 北京: 科学出版社, 2003. CAI Wen, YANG Chunyan, HE Bin. Extension logic[M]. Beijing: Science Press, 2003. [7] 蔡文, 杨春燕, 林伟初. 可拓工程方法[M]. 北京: 科学出版 社, 1999. CAI Wen, YANG Chunyan, LIN Weichu. Extension engineering methods[M]. Beijing: Science Press, 1999. [8] CORTES C, VAPNIK V. Support-vector networks[J]. Machine learning, 1995, 20(3): 273–297. [9] CRISTIANINI N, SHAWE-TAYLOR J. An introduction to support vector machines and other kernel-based learning methods[M]. Cambridge: Cambridge University Press, 2000. [10] VAPNIK V N. Statistical learning theory[M]. New York: John Wiley and Sons, 1998. [11] NOBLE W S. Support vector machine applications in computational biology[M]//SCHÖELKOPF B, TSUDA K, VERT J P. Kernel Methods in Computational Biology. Cambridge: MIT Press, 2004. [12] ADANKON M M, CHERIET M. Model selection for the LS-SVM. application to handwriting recognition[J]. Pattern recognition, 2009, 42(12): 3264–3270. [13] TIAN Yingjie, SHI Yong, LIU Xiaohui. Recent advances on support vector machines research[J]. Technological and economic development of economy, 2012, 18(1): 5–33. [14] DENG Naiyang, TIAN Yingjie, ZHANG Chunhua. Support vector machines: optimization based theory, al- [15] gorithms, and extensions[M]. Boca Raton: CRC Press, 2013. HUANG Kaizhu, YANG Haiqin, KING I, et al. Learning large margin classifiers locally and globally[C]//Proceeding of the 21st International Conference on Machine Learning. Banff, Alberta, Canada, 2004. [16] SHAWE-TAYLOR J, CRISTIANINI N. Kernel methods for pattern analysis[M]. Cambridge: Cambridge University Press, 2004. [17] BORGWARDT K M. Kernel methods in bioinformatics [M]//LU H H S, SCHÖLKOPF B, ZHAO Hongyu. Handbook of Statistical Bioinformatics. Berlin, Heidelberg: Springer, 2011: 317–334. [18] VAPNIK V, IZMAILOV R. Learning using privileged information: Similarity control and knowledge transfer[J]. Journal of machine learning research, 2015, 16: 2023– 2049. [19] SUN S. A survey of multi-view machine learning[J]. Neural computing and applications, 23(7): 2031–2038. [20] CHEPLYTGINA V, TAX, D M, LOOG M. Multiple instance learning with bag dissimilarities[J]. Pattern recognition, 2015, 48(1): 264–275. [21] CARBONNEAU M A, GRANGER E, RAYMOND A J, et al. Robust multiple-instance learning ensembles using random subspace instance selection[J]. Pattern recognition, 2016, 58: 83–99. [22] 作者简介： 陈晓华，女，1975 年生，工程师， 主要研究方向为电力系统及其自动化。 刘大莲，女，1978 年生，副教授， 博士研究生，主要研究方向为数据挖掘。 田英杰，男，1973 年，研究员，博 士生导师，主要研究方向为最优化与 机器学习。 第 1 期 陈晓华，等：可拓支持向量分类机 ·151·