第2卷第6期 智能系统学报 Vol.2 N26 2007年12月 CAAI Transactions on Intelligent Systems Dec.2007 基于超曲面的分类算法研究进展 何清2，史忠植2 (1.中国科学院计算技术研究所，北京100080：2.中国科学院研究生院，北京100039) 摘要：综述了基于超曲面的分类算法，该算法通过区域合并计算获得多个超平面组成的双侧闭曲面作为分类超曲 面对空间进行划分.分类超曲面可以有效地解决在有限连通区域分布很复杂的非线性数据多类分类问题，分析了算 法准确率与极小样本集的关系，总结了已有成就和最新进展，指出了基于超曲面的分类算法进一步发展的方向. 关键词：超曲面：分类算法：机器学习 中图分类号：TP301文献标识码：A文章编号：1673-4785(2007)060001-07 Research advances in classification algorithm based on hyper-surface HE Qing'2,SHI Zhong-zhi'2 (1.Institute of Computing Technology,Chinese Academy of Sciences,Beijing 100080,China;2.Graduate University,Chinese Academy of Sciences,Beijing 100039,China) Abstract:In this paper,a classification method based on Hyper Surface ("HSC"for short)is introduced. In this method,the space is partitioned through classification hyper-surface which are double-sided closed surfaces consisting of several hyper-surfaces by merging the connected regions.HSC can efficiently solve the nonlinear multi-class classification problems,in which the sample data distributions are very complicat- ed within the finite connected regions.The relationship between accuracy and the minimal consistent sub- set is analyzed.Finally,the existing achievements and the latest progresses in this subject are summa- rized,and the future research directions are pointed out. Key words:hyper-surface;classification algorithm;machine learning 分类算法研究是机器学习的核心研究内容，分 iant的“可学习理论”(PAC)之间的联系).关于 类能力是人类智能的最显著特征之一，机器学习在PAC的研究派生出被称为“计算学习理论(compu- 最近30多年取得了很大进展.1971年，前苏联数学 tational learning theory,COLT)的学派，现已定期 家Vapnik与Chervonenkis提出了一种基于VC维 召开这方面的国际会议.1995年Vapnik出版了 度的对空间划分的理论山.1984年Valiant提出了 “统计学习理论”一书(the nature of statistical 可学习理论(probability approximately correct, learning theory),在理论上，这是继Duda等人在 PAC),并将可学习性与计算复杂性联系在一起I. 20世纪60年代奠定统计模式识别理论之后5.6)， 在Valiant学习理论中，有2种学习复杂性测度.一 对统计模式识别最为完整的研究.这个理论的基础 是样本复杂性，这是随机实例的数目，用以产生具有 之一是Vc维度(Vapnik-Chervonenkis dimen- 高的概率和小的误差，二是计算复杂性，定义为最坏 sion).关于统计学习理论最新综述包括在文献[7] 情况下给定数目的样本产生假设所要求的计算时 中.事实上，对PAC的研究一直是理论性的、存在 间.这2种复杂性在对分类算法的研究中起着重要 性的，Vapnik的这个研究却是构造性的，并将感知 作用.1986年Blumer等人证明了VC维度与Va- 机的研究包括在其中，他将这种模型称为支持向量 收稿日期：2007-0-10. 机(support vector machine,SVM).在SVM的研究 基金项目：国家自然科学基金资助项目(60435010,60675010)：国家 重点基础研究发展计划资助项目(2006AA01Z128):北京 中我国学者作出了大量工作8.川.与此同时，在基 市自然科学基金资助项目(4052025) 于覆盖的分类学习算法方面，我国学者在最近10年 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net第 2 卷第 6 期 智 能 系 统 学 报 Vol. 2 №. 6 2007 年 12 月 CAAI Transactions on Intelligent Systems Dec. 2007 基于超曲面的分类算法研究进展 何 清1 ,2 ,史忠植1 ,2 (1. 中国科学院 计算技术研究所 ,北京 100080 ;2. 中国科学院 研究生院 ,北京 100039) 摘 要 :综述了基于超曲面的分类算法 ,该算法通过区域合并计算获得多个超平面组成的双侧闭曲面作为分类超曲 面对空间进行划分. 分类超曲面可以有效地解决在有限连通区域分布很复杂的非线性数据多类分类问题 ,分析了算 法准确率与极小样本集的关系 , 总结了已有成就和最新进展 , 指出了基于超曲面的分类算法进一步发展的方向. 关键词 :超曲面 ;分类算法 ;机器学习 中图分类号 : TP301 文献标识码 :A 文章编号 :167324785 (2007) 0620001207 Research advances in classification algorithm based on hyper2surface H E Qing 1 ,2 , SHI Zhong2zhi 1 ,2 (1. Institute of Computing Technology , Chinese Academy of Sciences , Beijing 100080 ,China ;2. Graduate University , Chinese Academy of Sciences , Beijing 100039 , China) Abstract :In t his paper , a classification method based on Hyper Surface “( HSC”for short) is introduced. In t his method , t he space is partitioned t hrough classification hyper2surface which are double2sided closed surfaces consisting of several hyper2surfaces by merging the connected regions. HSC can efficiently solve t he nonlinear multi2class classification problems , in which t he sample data distributions are very complicat2 ed within t he finite connected regions. The relationship between accuracy and t he minimal consistent sub2 set is analyzed. Finally , t he existing achievements and t he latest progresses in this subject are summa2 rized , and t he f uture research directions are pointed out. Keywords :hyper2surface ; classification algorit hm ;machine learning 收稿日期 :2007201210. 基金项目 :国家自然科学基金资助项目 (60435010 ,60675010) ;国家 重点基础研究发展计划资助项目 (2006AA01Z128) ;北京 市自然科学基金资助项目(4052025) . 分类算法研究是机器学习的核心研究内容 ,分 类能力是人类智能的最显著特征之一. 机器学习在 最近 30 多年取得了很大进展. 1971 年 ,前苏联数学 家 Vap nik 与 Chervonenkis 提出了一种基于 VC 维 度的对空间划分的理论[1 ] . 1984 年 Valiant 提出了 可学 习 理 论 ( probability approximately correct , PAC) ,并将可学习性与计算复杂性联系在一起[2 ] . 在 Valiant 学习理论中 ,有 2 种学习复杂性测度. 一 是样本复杂性 ,这是随机实例的数目 ,用以产生具有 高的概率和小的误差 ;二是计算复杂性 ,定义为最坏 情况下给定数目的样本产生假设所要求的计算时 间. 这 2 种复杂性在对分类算法的研究中起着重要 作用. 1986 年 Blumer 等人证明了 VC 维度与 Val2 iant 的“可学习理论”(PAC) 之间的联系[ 3 ] . 关于 PAC 的研究派生出被称为“计算学习理论 (comp u2 tational learning t heory ,COL T) 的学派 ,现已定期 召开这方面的国际会议[4 ] . 1995 年 Vap nik 出版了 “统 计 学 习 理 论”一 书 ( t he nature of statistical learning t heory) , 在理论上 ,这是继 Duda 等人在 20 世纪 60 年代奠定统计模式识别理论之后[5 - 6 ] , 对统计模式识别最为完整的研究. 这个理论的基础 之一 是 VC 维 度 ( Vap nik2Chervonenkis dimen2 sion) . 关于统计学习理论最新综述包括在文献[ 7 ] 中. 事实上 ,对 PAC 的研究一直是理论性的、存在 性的 ,Vap nik 的这个研究却是构造性的 ,并将感知 机的研究包括在其中 ,他将这种模型称为支持向量 机(support vector machine ,SVM) . 在 SVM 的研究 中我国学者作出了大量工作[8 - 11 ] . 与此同时 ,在基 于覆盖的分类学习算法方面 ,我国学者在最近 10 年