第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 年
·2 智能系统学报 第2卷 相继提出了一些很有价值的分类学习方法.张铃、张 围绕数)为奇数，x∈X的外部自x引出的射线与 钹教授给出了MP神经元的几何意义，通过球面投 X的相交数为偶数.如图1所示.现在问题的关键在 影变换将神经网络的最优设计问题转化为某种最优 于如何获得分类超曲面 覆盖问题！.张铃、张钱教授给出了邻域覆盖算法 和交叉覆盖算法，以及改进的函数覆盖算法和核覆 盖算法.王守觉院士提出了仿生模式识别（拓扑模式 识别))，它是基于“认识”事物而不是基于“区 分”事物为目的，与传统以“最佳划分”为目标的统计 模式识别相比，它更接近于人类“认识”事物的特 性，故称为“仿生模式识别”徐宗本教授最近提出了 图1分类判别图示 一种基于视觉的分类方法(visual classification al- Fig.I Classification theorem illustration gorithm,VCA)),这种方法是针对目前很多分类 下面的算法给出了构造和使用分类超曲面的 方法主要是通过发现数据内在的结构来分类，很少 基本过程 或没有注意到从模拟人的感觉和感知来进行分类而 假定M个训练样本：Kan={x'(i)川t=1,2;i= 提出的.何清等提出了基于超曲面的分类学习算法 1,2M,不失一般性，假设样本点己预先标记好 (hyper surface classification,HSC)2),这t也是一种 的类别∈{1,2：训练空间D为一封闭区域，且其 覆盖分类算法.本文综述了基于超曲面的分类算法， 边界满足Jordan曲线定理的基本条件 对算法进行了详细分析和阐述，并指出了基于超曲 )设前m个训练样本落在区域D内，m∈ 面的分类算法进一步发展的方向 1,2,…,M. 1基于超曲面的分类学习算法 2)将区域D划分成n个小区域，设D=D1U D2U…UDm,n≥m.且满足以下条件： 基于超曲面的分类学习算法基本思想是从几何 ①D,(j=1,2,,的边界H满足Jordan曲 学和拓扑学出发的，该算法基于Jordan曲线定理， 线定理的基本条件： 根据围绕数的奇偶进行分类判断，该算法不需要考 ②x()∈D,i=1,2,…m,j=1,2,n,不妨 虑使用何种核函数，而直接地解决非线性分类问题. 设i=j,即每个小区域至多含一个样本点， 下面给出Jordan曲线定理和分类判别定理 3)设D(j=1,2,…,m的边界H分别由k Jorn曲线定理设XCR是闭子集，X同胚 个超平面片组成，可以将每片超平面表示为用，i= 于球面S2,那么它的余集R/S有2个连通分支，一 1,2,,k:则可将H表示为含类别分量和超平面 个是有界的，另一个是无界的，X中任何一点的任 片的集合， 何邻域与这2个连通分支均相交 H={5,|p=1,2,k;4=1,2} 上述定理可推广到高维空间 式中：t为D,所含样本点x'(的类别 定理1高维空间的Jordan曲线定理 4)若D,与D,(i)相邻，且=i,则合并边 若XCS”同胚于球面Sm,那么m≤n否则X= 界H,和H,不妨设H与H重合，即H=), S.若m<n,余集的同调群为 将重合超平面片消去，则获得封闭区域A虹，其边界 Z⊙Z,m=n-1且k=0, 为 Z,m<n-1且k=0, BL H,U Hj= 0,其他 ft,Ha,|a=1,…k,且a≠p 当m=n-1时SX由2个连通分支组成，当m<n b=1,k,且b≠q;红=. -1时，只有1个连通分支 继续合并相邻同类区域，最终获得一组由若干超平 Jordan曲线定理表明任何由n-1维球面经连 面片组成的封闭超曲面一分类超曲面，记为 续变形得到的双侧闭曲面都把n维空间分成2个区 SHS={ti,HPi|i∈f1,2,…; 域—一个外部和一个内部，这种曲面可用于分类， 1=1,2,…k;1=1,2},r≤m. 称之为分类超曲面.给定一个点x,判断它在分类超 以链的形式存储SHS的各超平面片HP,1=1,2, 曲面X的内部，还是在外部的方法是：x∈X的内部 “,k 自x引出的射线与X的相交数（即X关于x的 5)输入新样本点X=x'(m+1),按照以下方法 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
相继提出了一些很有价值的分类学习方法. 张铃、张 钹教授给出了 M2P 神经元的几何意义 ,通过球面投 影变换将神经网络的最优设计问题转化为某种最优 覆盖问题[12 ] . 张铃、张钹教授给出了邻域覆盖算法 和交叉覆盖算法 ,以及改进的函数覆盖算法和核覆 盖算法. 王守觉院士提出了仿生模式识别(拓扑模式 识别) [17 - 18 ] ,它是基于“认识”事物而不是基于“区 分”事物为目的 ,与传统以“最佳划分”为目标的统计 模式识别相比 , 它更接近于人类“认识”事物的特 性 ,故称为“仿生模式识别”. 徐宗本教授最近提出了 一种基于视觉的分类方法 ( visual classification al2 gorithm ,VCA) [21 ] ,这种方法是针对目前很多分类 方法主要是通过发现数据内在的结构来分类 ,很少 或没有注意到从模拟人的感觉和感知来进行分类而 提出的. 何清等提出了基于超曲面的分类学习算法 (hyper surface classification , HSC) [23 ] ,这也是一种 覆盖分类算法. 本文综述了基于超曲面的分类算法 , 对算法进行了详细分析和阐述 ,并指出了基于超曲 面的分类算法进一步发展的方向. 1 基于超曲面的分类学习算法 基于超曲面的分类学习算法基本思想是从几何 学和拓扑学出发的 ,该算法基于 Jordan 曲线定理 , 根据围绕数的奇偶进行分类判断 ,该算法不需要考 虑使用何种核函数 ,而直接地解决非线性分类问题. 下面给出 Jordan 曲线定理和分类判别定理. Jordan 曲线定理 设 X < R 3 是闭子集 , X 同胚 于球面 S 2 ,那么它的余集 R 3 / S 有 2 个连通分支 ,一 个是有界的 ,另一个是无界的 , X 中任何一点的任 何邻域与这 2 个连通分支均相交. 上述定理可推广到高维空间. 定理 1 高维空间的 Jordan 曲线定理. 若 X < S n 同胚于球面 S m ,那么 m ≤n 否则 X = S n . 若 m < n ,余集的同调群为 Hk (s n \ X) µ Z Ý Z , m = n - 1 且 k = 0 , Z , m < n - 1 且 k = 0 , 0 ,其他. 当 m = n - 1 时 S n \ X 由 2 个连通分支组成 ,当 m < n - 1 时 ,只有 1 个连通分支. Jordan 曲线定理表明任何由 n - 1 维球面经连 续变形得到的双侧闭曲面都把 n 维空间分成 2 个区 域 ———一个外部和一个内部 ,这种曲面可用于分类 , 称之为分类超曲面. 给定一个点 x ,判断它在分类超 曲面 X 的内部 ,还是在外部的方法是 : x ∈X 的内部 Ζ自 x 引出的射线与 X 的相交数 (即 X 关于 x 的 围绕数) 为奇数 , x ∈X 的外部 Ζ自 x 引出的射线与 X 的相交数为偶数. 如图 1 所示. 现在问题的关键在 于如何获得分类超曲面. 图 1 分类判别图示 Fig. 1 Classification theorem illustration 下面的算法给出了构造和使用分类超曲面的 基本过程. 假定 M 个训练样本 : Ktrain = { x′( i) | t = 1 ,2 ; i = 1 ,2 …, M} ,不失一般性 ,假设样本点已预先标记好 的类别 ti ∈{ 1 ,2} ;训练空间 D 为一封闭区域 ,且其 边界满足 Jordan 曲线定理的基本条件. 1) 设前 m 个训练样本落在区域 D 内 , m ∈ { 1 ,2 , …, M} . 2) 将区域 D 划分成 n 个小区域 ,设 D = D1 ∪ D2 ∪…∪Dn , n ≥m. 且满足以下条件 : ①Dj ( j = 1 , 2 , …, n) 的边界 Hj 满足 Jordan 曲 线定理的基本条件; ②x′( i) ∈Dj , i = 1 ,2 , …, m , j = 1 ,2 , …, n ,不妨 设 i = j ,即每个小区域至多含一个样本点. 3) 设 Dj ( j = 1 , 2 , …, m) 的边界 Hj 分别由 k j 个超平面片组成 ,可以将每片超平面表示为 H j i , i = 1 ,2 , …, kj ;则可将 Hj 表示为含类别分量和超平面 片的集合 , Hj = { tj , H j p | p = 1 ,2 , …, kj ; tj = 1 ,2} . 式中 :tj 为 D j 所含样本点 x′( j) 的类别. 4) 若 Di 与 D j ( i ≠j) 相邻 ,且 ti = tj ,则合并边 界 Hi 和 H j (不妨设 H i p 与 H j p 重合 ,即 H i p = H j q ) , 将重合超平面片消去 ,则获得封闭区域 AL ,其边界 为 BL = Hi ∪ Hj = { tL , H i a , H j b | a = 1 , …, ki ,且 a ≠p ; b = 1 , …, kj ,且 b ≠q; tL = ti} . 继续合并相邻同类区域 ,最终获得一组由若干超平 面片组成的封闭超曲面 ———分类超曲面 ,记为 SHS t i = { ti , HP i l | i ∈{ 1 ,2 , …, r} ; l = 1 ,2 , …, ki ; ti = 1 ,2} , r ≤m. 以链的形式存储 SHS t i 的各超平面片 HP i l , l = 1 , 2 , …, ki . 5) 输入新样本点 X = x t ( m + 1) ,按照以下方法 ·2 · 智 能 系 统 学 报 第 2 卷
第6期 何清，等：基于超曲面的分类算法研究进展 。3 进行判别（设T为样本点分类所得类别）：选择适当 点，但与连通分支的形状无关，在现实中的数据分 的由待定点X出发的射线fx,设fx与SHS的相 布大都满足条件之一25] 交点数为C,分别计算fx与/SHSl a=1,,n}和 H$C算法发展至今，已相继解决了二维2类分 {SHSb=1,,n}(n+n=)的相交点数之和， 类23引、二维多类分类24)、二维一般连通区域分 1 类2)、三维多类21、高维换维分类问题2)、高维多 记为c.和c,则有 6- 类集成分类问题28.451」 C为奇数r=1 关于HSC算法的最新进展包括：利用HSC算 法构造了极小样本集，提出了基于覆盖的极小样本 集的概念使之不仅可以代表整个模型，而且可以反 或 C为奇数7=2 映出整个训练集的拓扑结构6，并研究了BAG 实际上，求C的过程，就是求∫x与HP相交数量 GNG和ADABOOST算法使用不同的训练样本集 的过程 时对HSC分类器性能的影响，试验结果表明，他们 6)若不能判别X的类别，就对X所在的小区域 对分类精度的提高是受极小样本集制约的).另外 边界进行标定，不妨设x'(m+1)∈Dm+1,则Dm+1的 从视觉认知角度研究了超曲面在和数据理解中的作 边界可表示为 用41.采用Aget(智能主体)技术用于多个HSC Hm+1=f1m+1,Hg1|p=1,2,…km+1 分类器的合成，使得HSC算法适合在分布式环境 之后转入4)，继续合并相邻同类区域： 中进行数据挖掘.这种合成的特点是不把样本集划 以上给出了基于分类超曲面的分类判别方法的 分为若干小样本集的横向划分，而是对分布在不同 基本算法，即通过区域合并计算获得多个超平面组 地点的不同属性的样本集就地作属性集纵向划分后 成的双侧闭曲面作为分类超曲面对空间进行划分， 的合成4 也就是在样本点周围形成一个封闭区域，该区域由 3基于超曲面的覆盖分类学习算法的 多个分类超平面片围成，并使得该区域覆盖某一类 研究方向 尽可能多的样本点，同时不覆盖异类样本点】 基于超曲面的分类学习算法HSC作为一种新 2算法特点与已有研究成果 的算法，有很多问题亟待研究，这既包括算法优化 H$C算法有2个关键步骤，一是局部化策略， 又包括理论分析，还包括应用中遇到的现实问题 另一个是用围绕数判断类别.该算法中，判别样本所 首先是优化高维数据分类算法问题.从理论上 属类别，不需与所有分类边界链表作相交操作后再 讲，这种方法可以推广到高维，因为Jordan定理在 判断，而只需满足：由样本点所引射线与一完整分类 任意有限维空间都是成立的.但是高维空间中的实 边界链表相交点数为奇数即可，这样可提高判别速 现存在以下挑战性问题：一是高维空间的单位方体 度.这种方法得到的分类超曲面是由若干个封闭闭 的合并计算复杂度随着维数增加而提高，另一方面 曲面构成，而曲面的局部是由低维平面片构成.每个 高维超曲面的存储开销大.但是这并不意味HSC 闭曲面内部是一类样本，这样对闭曲面可以进行类 不能处理高维数据，借助数据预处理和集成学习技 别标记.样本类别可以是多个，所以这种方法对于多 术，对于高维数据处理提出并实现了2种解决办法. 类问题的解决是很方便的，因为多个分类器可以在 这2种高维处理方法与HSC算法特点紧密结合，这 一次训练过程中产生，避免了2类分类器转化为多 就是基于样本数据重排的换维分类学习算法和基于 类分类器的技术处理.对二维和三维双螺旋及UCI 集成学习思想的分维分类学习算法.有关集成学 中的数据的分类实验结果说明，分类超曲面可以有 习周志华教授做了出色的工作1，).HSC的集成 效地解决在有限区域分布很复杂的海量(10')的非 特点是通过分维获得子分类器，不是通过划分样本 线性数据多类分类问题，计算速度较高，同时对计 集获得子分类器21.基于样本数据重排的换维分类 算机资源要求很低，而传统的SVM不具备这种优 学习]，将涉及到维排序和维组合问题，这些策略 点.另外小样本训练大样本测试结果表明，基于分类 具有多样性，他们如何影响分类器性能，如何找到最 超曲面的分类法的泛化能力较好.该方法是对直接 优的策略是待研究的问题.由于分类器集成方法是 解决非线性分类问题的一种尝试，此方法的一个前 基于分维的，那么维的排序策略、划分策略及权重策 提是同类样本点应具有在有限个连通分支分布的特 略就值得研究 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
进行判别(设 T 为样本点分类所得类别) :选择适当 的由待定点 X 出发的射线 f X ,设 f X 与 SHS t i 的相 交点数为 C t i ,分别计算 f X 与{SHS 1 a | a = 1 , …, r1 }和 {SHS 2 b | b = 1 , …, r2 } ( r1 + r2 = r) 的相交点数之和 , 记为 ∑ r 1 a = 1 C 1 a 和 ∑ r 2 b= 1 C 2 b ,则有 ∑ r 1 a= 1 C 1 a 为奇数 Ζ T = 1 或 ∑ r 2 b= 1 C 2 b 为奇数 Ζ T = 2. 实际上 ,求 C t i 的过程 ,就是求 f X 与 HP i l 相交数量 的过程. 6) 若不能判别 X 的类别 ,就对 X 所在的小区域 边界进行标定 ,不妨设 x t ( m + 1) ∈Dm + 1 ,则 Dm + 1的 边界可表示为 Hm+1 = { tm+1 , H m+1 p | p = 1 ,2 , …, km+1 } , 之后转入 4) ,继续合并相邻同类区域. 以上给出了基于分类超曲面的分类判别方法的 基本算法 ,即通过区域合并计算获得多个超平面组 成的双侧闭曲面作为分类超曲面对空间进行划分 , 也就是在样本点周围形成一个封闭区域 ,该区域由 多个分类超平面片围成 ,并使得该区域覆盖某一类 尽可能多的样本点 ,同时不覆盖异类样本点. 2 算法特点与已有研究成果 HSC 算法有 2 个关键步骤 ,一是局部化策略 , 另一个是用围绕数判断类别. 该算法中 ,判别样本所 属类别 ,不需与所有分类边界链表作相交操作后再 判断 ,而只需满足 :由样本点所引射线与一完整分类 边界链表相交点数为奇数即可 ,这样可提高判别速 度. 这种方法得到的分类超曲面是由若干个封闭闭 曲面构成 ,而曲面的局部是由低维平面片构成. 每个 闭曲面内部是一类样本 ,这样对闭曲面可以进行类 别标记. 样本类别可以是多个 ,所以这种方法对于多 类问题的解决是很方便的 ,因为多个分类器可以在 一次训练过程中产生 ,避免了 2 类分类器转化为多 类分类器的技术处理. 对二维和三维双螺旋及 UCI 中的数据的分类实验结果说明 ,分类超曲面可以有 效地解决在有限区域分布很复杂的海量 (10 7 ) 的非 线性数据多类分类问题 ,计算速度较高 , 同时对计 算机资源要求很低 , 而传统的 SVM 不具备这种优 点. 另外小样本训练大样本测试结果表明 ,基于分类 超曲面的分类法的泛化能力较好. 该方法是对直接 解决非线性分类问题的一种尝试 , 此方法的一个前 提是同类样本点应具有在有限个连通分支分布的特 点 , 但与连通分支的形状无关 ,在现实中的数据分 布大都满足条件之一[25 ] . HSC 算法发展至今 ,已相继解决了二维 2 类分 类[23 ] 、二维多 类 分 类[24 ] 、二 维 一 般 连 通 区 域 分 类[25 ] 、三维多类[26 ] 、高维换维分类问题[ 27 ] 、高维多 类集成分类问题[28 - 45 ] . 关于 HSC 算法的最新进展包括 :利用 HSC 算 法构造了极小样本集 ,提出了基于覆盖的极小样本 集的概念使之不仅可以代表整个模型 ,而且可以反 映出整个训练集的拓扑结构[46 ] ,并研究了 BA G2 GIN G和 ADABOOST 算法使用不同的训练样本集 时对 HSC 分类器性能的影响 ,试验结果表明 ,他们 对分类精度的提高是受极小样本集制约的[47 ] . 另外 从视觉认知角度研究了超曲面在和数据理解中的作 用[48 ] . 采用 Agent (智能主体) 技术用于多个 HSC 分类器的合成 ,使得 HSC 算法适合在分布式环境 中进行数据挖掘. 这种合成的特点是不把样本集划 分为若干小样本集的横向划分 , 而是对分布在不同 地点的不同属性的样本集就地作属性集纵向划分后 的合成[ 49 ] . 3 基于超曲面的覆盖分类学习算法的 研究方向 基于超曲面的分类学习算法 HSC 作为一种新 的算法 ,有很多问题亟待研究 ,这既包括算法优化 , 又包括理论分析 ,还包括应用中遇到的现实问题. 首先是优化高维数据分类算法问题. 从理论上 讲 ,这种方法可以推广到高维 ,因为 Jordan 定理在 任意有限维空间都是成立的. 但是高维空间中的实 现存在以下挑战性问题 :一是高维空间的单位方体 的合并计算复杂度随着维数增加而提高 ,另一方面 高维超曲面的存储开销大. 但是这并不意味 HSC 不能处理高维数据 ,借助数据预处理和集成学习技 术 ,对于高维数据处理提出并实现了 2 种解决办法. 这 2 种高维处理方法与 HSC 算法特点紧密结合 ,这 就是基于样本数据重排的换维分类学习算法和基于 集成学习思想[30 ]的分维分类学习算法. 有关集成学 习周志华教授做了出色的工作[31 - 32 ] . HSC 的集成 特点是通过分维获得子分类器 ,不是通过划分样本 集获得子分类器[28 ] . 基于样本数据重排的换维分类 学习[27 ] ,将涉及到维排序和维组合问题 ,这些策略 具有多样性 ,他们如何影响分类器性能 ,如何找到最 优的策略是待研究的问题. 由于分类器集成方法是 基于分维的 ,那么维的排序策略、划分策略及权重策 略就值得研究. 第 6 期 何 清 ,等 :基于超曲面的分类算法研究进展 ·3 ·
智能系统学报 第2卷 其次是初始的划分尺度与泛化能力的关系问 集合的取值要求就可以得出结论.Gallant的这篇论 题.基于超曲面的分类方法与传统方法相比，如与 文开创了神经网络规则抽取这一领域，成为该领域 Parzen窗分类器相比s),由于HSC采用了局部化 被引用最多的文献之一.在Gallant之后，陆续有一 策略，克服了Parzen窗在样本分布不均衡情况下， 些研究者对神经网络规则抽取进行了研究4.0】 若窗宽度较小所导致的分类区域过于零散，分类曲 1995年，Andrews等人a]为从神经网络抽取的规 面复杂，推广性差，以及窗宽度较大时，由于分类区 则提出了一个评价体系，并提出了规则抽取算法的 域融合过度所造成的分类误差大的问题.在H$C 分类体系.前者为不同规则抽取算法的比较提供了 中由于采用局部化策略是对存在异类数据分布的同 标准，并对新算法的设计具有指导作用，后者使得对 一单元区域进行，因而这种方法是基于对数据分布 规则抽取算法的系统化分析成为可能.这2个体系 的感知来工作.Parzen窗分类器的窗宽度是可以通 为神经网络规则抽取这一领域的进一步发展奠定了 过实验逐步择优的，但是一旦选定某个值，在整个分 基础，因此，Andrews等人的这篇论文as)被认为是 类过程中就不再变化，这对于分布不均衡的样本分 该领域的一个里程碑.H$C分类超曲面以链表方式 类有明显的缺陷.但是初始的划分尺度，对HSC的 表达，已经实现了分类超曲面的可视化，但可视化并 分类精度是有影响的，研究有关这种影响的估计以 不意味着数据可理解，这些链表包含了分类信息，这 及提高精度的策略是重要的.划分尺度与极小样本 些信息能否像神经网络规则抽取那样，从中抽出分 集之间的关系.在一定意义上来说同仿生模式识别 类规则是值得研究的问题.从分类超曲面中得到的分 类似，HSC将模式识别问题看成是模式的认识，而 类规则就是可以学习、可以理解、可以传播的知识了 不是分类划分，不是模式分类.因而，其数学模型与 另外，HSC在数据理解中的作用问题.理解数 传统模式识别的“最优分类”界面的概念大不相同， 据，即获得数据集合的不同简洁程度表示，己成为机 划分尺度越小HSC所得到的模型和训练样本的拓 器学习研究的另一个重要研究方向.解决这个问题 扑结构的匹配程度就越高，误识率就越低，但这也将 的途径不能沿袭传统检验有效性的方法，即以检验 导致据识率的提高、泛化能力的下降.但是无论采用 个别事例为基础，而需要寻找必要的数学理论.数据 多大的划分尺度最终都会得到一个一致的分类模 理解包括人对数据的理解和机器对数据理解，人对 型，区别在于其细化程度的不同.还要研究不同划分 数据的理解，可以理解为借用符号机器学习的约简 尺度产生的极小样本集间有何不同，并比较它们之 与可解释的特性，将一本使用数据语言书写的书翻 间的性质 译为人可理解的表示形式，从而丰富人的知识.这就 再次，最优的H$C覆盖问题.张铃、张钹教授 是数据挖掘的主要任务之一，计算机的数据理解就 给出了MP神经元的几何意义，通过球面投影变换 是传统意义下的机器学习，分类超曲面可以看作数 将神经网络的最优设计问题转化为某种最优覆盖问 据分布的一个包络，这是对数据理解的一个方面，另 题.他们把神经元与几何上样本的球形邻域对应起 一个方面的理解是数据分布的主曲线，主曲线相当 来.按照这种观点，HSC可以看成神经元是由分类 于数据分布的骨架，这两者结合将会得到对数据更 超曲面构成的神经网络，分类超曲面的个数就是神 全面的理解 经元的个数.所不同的是HSC的分类是靠样本围 另外，要研究HSC学习算法的计算复杂性，包 绕数来计算得出的，而神经网络是通过修正权值后 括时间复杂性、空间复杂性、样本复杂性以及模型对 加权计算获得，如何找到超曲面个数少分类性能好 新问题的求解能力，或称为泛化能力.在数学上来 的HSC分类器是一个重要的问题，这也是一个最 看，学习理论就是通过计算有限的随机样本获得数 优覆盖问题 据中包含的知识4.51.函数海量数据与学习精确度 还有，HSC的抽取规则问题.以往人们觉得神 (泛化能力)以及数据性质的多样性（领域依赖）等要 经网络学习算法的分类过程不可理解，难以解释.这 求，需要考虑使用更多更复杂的数学理论，如函数逼 样在Gallant提出了一个简单的算法来解释连接主 近论和宽度理论来揭示己有或正在发展的理论与方 义专家系统所做的推理】.该算法通过产生规则来 法所存在的问题，及其对问题的适应性 解释神经网络如何为某个给定案例得出结论.其基 最后，极小样本集的性质以及与PAC样本复杂 本思想就是从当前已知的信息集中选择一个能有效 度的关系问题亟待研究.此外PAC的样本复杂度理 地产生该结论的最小信息集合，也就是说，不管其他 论给出了有多少随机抽取训练样例才足以可能近似 未知输入分量的取值为多少，只要满足该最小信息 正确(PAC)地学习到任意目标概念.通过HSC得 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
其次是初始的划分尺度与泛化能力的关系问 题. 基于超曲面的分类方法与传统方法相比 ,如与 Parzen 窗分类器相比[5 ] ,由于 HSC 采用了局部化 策略 ,克服了 Parzen 窗在样本分布不均衡情况下 , 若窗宽度较小所导致的分类区域过于零散 ,分类曲 面复杂 ,推广性差 ,以及窗宽度较大时 ,由于分类区 域融合过度所造成的分类误差大的问题. 在 HSC 中由于采用局部化策略是对存在异类数据分布的同 一单元区域进行 ,因而这种方法是基于对数据分布 的感知来工作. Parzen 窗分类器的窗宽度是可以通 过实验逐步择优的 ,但是一旦选定某个值 ,在整个分 类过程中就不再变化 ,这对于分布不均衡的样本分 类有明显的缺陷. 但是初始的划分尺度 ,对 HSC 的 分类精度是有影响的 ,研究有关这种影响的估计以 及提高精度的策略是重要的. 划分尺度与极小样本 集之间的关系. 在一定意义上来说同仿生模式识别 类似 , HSC 将模式识别问题看成是模式的认识 ,而 不是分类划分 ,不是模式分类. 因而 ,其数学模型与 传统模式识别的“最优分类”界面的概念大不相同. 划分尺度越小 HSC 所得到的模型和训练样本的拓 扑结构的匹配程度就越高 ,误识率就越低 ,但这也将 导致据识率的提高、泛化能力的下降. 但是无论采用 多大的划分尺度最终都会得到一个一致的分类模 型 ,区别在于其细化程度的不同. 还要研究不同划分 尺度产生的极小样本集间有何不同 ,并比较它们之 间的性质. 再次 ,最优的 HSC 覆盖问题. 张铃、张钹教授 给出了 M2P 神经元的几何意义 ,通过球面投影变换 将神经网络的最优设计问题转化为某种最优覆盖问 题. 他们把神经元与几何上样本的球形邻域对应起 来. 按照这种观点 , HSC 可以看成神经元是由分类 超曲面构成的神经网络 ,分类超曲面的个数就是神 经元的个数. 所不同的是 HSC 的分类是靠样本围 绕数来计算得出的 ,而神经网络是通过修正权值后 加权计算获得. 如何找到超曲面个数少分类性能好 的 HSC 分类器是一个重要的问题 ,这也是一个最 优覆盖问题. 还有 , HSC 的抽取规则问题. 以往人们觉得神 经网络学习算法的分类过程不可理解 ,难以解释. 这 样在 Gallant 提出了一个简单的算法来解释连接主 义专家系统所做的推理[33 ] . 该算法通过产生规则来 解释神经网络如何为某个给定案例得出结论. 其基 本思想就是从当前已知的信息集中选择一个能有效 地产生该结论的最小信息集合 ,也就是说 ,不管其他 未知输入分量的取值为多少 ,只要满足该最小信息 集合的取值要求就可以得出结论. Gallant 的这篇论 文开创了神经网络规则抽取这一领域 ,成为该领域 被引用最多的文献之一. 在 Gallant 之后 ,陆续有一 些研究者对神经网络规则抽取进行了研究[34 - 40 ] . 1995 年 ,Andrews 等人 [43 ]为从神经网络抽取的规 则提出了一个评价体系 ,并提出了规则抽取算法的 分类体系. 前者为不同规则抽取算法的比较提供了 标准 ,并对新算法的设计具有指导作用 ,后者使得对 规则抽取算法的系统化分析成为可能. 这 2 个体系 为神经网络规则抽取这一领域的进一步发展奠定了 基础 ,因此 ,Andrews 等人的这篇论文[43 ] 被认为是 该领域的一个里程碑. HSC 分类超曲面以链表方式 表达 ,已经实现了分类超曲面的可视化 ,但可视化并 不意味着数据可理解 ,这些链表包含了分类信息 ,这 些信息能否像神经网络规则抽取那样 ,从中抽出分 类规则是值得研究的问题. 从分类超曲面中得到的分 类规则就是可以学习、可以理解、可以传播的知识了. 另外 , HSC 在数据理解中的作用问题. 理解数 据 ,即获得数据集合的不同简洁程度表示 ,已成为机 器学习研究的另一个重要研究方向. 解决这个问题 的途径不能沿袭传统检验有效性的方法 ,即以检验 个别事例为基础 ,而需要寻找必要的数学理论. 数据 理解包括人对数据的理解和机器对数据理解. 人对 数据的理解 ,可以理解为借用符号机器学习的约简 与可解释的特性 ,将一本使用数据语言书写的书翻 译为人可理解的表示形式 ,从而丰富人的知识. 这就 是数据挖掘的主要任务之一. 计算机的数据理解就 是传统意义下的机器学习 ,分类超曲面可以看作数 据分布的一个包络 ,这是对数据理解的一个方面. 另 一个方面的理解是数据分布的主曲线 ,主曲线相当 于数据分布的骨架 ,这两者结合将会得到对数据更 全面的理解. 另外 ,要研究 HSC 学习算法的计算复杂性 ,包 括时间复杂性、空间复杂性、样本复杂性以及模型对 新问题的求解能力 ,或称为泛化能力. 在数学上来 看 ,学习理论就是通过计算有限的随机样本获得数 据中包含的知识[44 - 45 ] . 函数海量数据与学习精确度 (泛化能力) 以及数据性质的多样性(领域依赖) 等要 求 ,需要考虑使用更多更复杂的数学理论 ,如函数逼 近论和宽度理论来揭示已有或正在发展的理论与方 法所存在的问题 ,及其对问题的适应性. 最后 ,极小样本集的性质以及与 PAC 样本复杂 度的关系问题亟待研究. 此外 PAC 的样本复杂度理 论给出了有多少随机抽取训练样例才足以可能近似 正确(PAC) 地学习到任意目标概念. 通过 HSC 得 ·4 · 智 能 系 统 学 报 第 2 卷
第6期 何清，等：基于超曲面的分类算法研究进展 5· 到极小样本集的方法给出了选择的训练样本，为了 Recognition Letters,2004,25(10):1165-1171. 使在其上学习得到的模型有很好的性能应满足的性 [11]许建华，张学工，李衍达.一种基于核函数的非线性感 质（包含某一极小样本集）.将从包含极小样本集这 知器算法U].计算机学报，2002,25(7)：689.695. 个目标出发，在一定的限制条件下得到一个新的样 XU Jianhua,ZHANG Xuegong,LI Yanda.A nonlinear 本集所包含实例个数的边界，并与PAC的样本复杂 perceptron algorithm based on kernel functions[J].Chi- 度理论进行比较 nese Journal of Computers,2002,25(7):689-695. [12]ZHANG Ling,ZHAN G Bo.A geometrical representa- 3结束语 tion of MeCulloch Pitts neural model and its applica- tions [J ]IEEE Transactions on Neural Networks. 总之，在基于覆盖的分类学习算法方面，基于覆 1999,10(4):925-929. 盖思想在最近10年相继提出过一些很有价值的分 [13]吴涛，张铃，张燕平.机器学习中的核覆盖算法] 类学习方法和理论分析，但是，大量的理论问题尚 计算机学报，2005,28(8)：1295,1301 未解决，H$C学习算法作为一种覆盖分类算法，其 WU Tao,ZHANG Ling,ZHANG Yanping.Kernel 性能提高以及计算复杂性、泛化能力等理论问题值 covering algorithm for machine learning [J].Chinese 得深入研究。 Journal of Computers,2005,28(8):1295-1301 [14]陶品，张钱，叶榛.构造型神经网络双交叉覆盖增 参考文献： 量学习算法[0].软件学报，2003,14(2)：194.201。 TAO Pin,ZHANG Bo.YE Zhen.An incremental bi- [1]VAPNIK V.The nature of statistical learning theory [M].New York:Springer-Verlag,1995. covering learning algorithm for constructive neural net- work[J ]Journal of Software,2003,14 (2):194 [2]VAL IANT L G.A theory of the learnable[J ]Commu nications of the ACM,1984.27(11):1134-1142. 201. [3]BLUMER A,EHRENFEUCHT A,HASSL ER D,et [15]张铃，张钱，殷海风.多层前向网络的交叉覆盖设 al.Classifying learnable geometric concepts with the 计算法U].软件学报，1999,10(7)：737.742. Vapnik-Chervonenkis dimension[A ]Proceedings of the ZHAN GLing,ZHANGBo,YIN Haifeng.An alterna- 19th Annual ACM Symposium on Theory of Computing tive covering design algorithm of multi-layer neural net- [C].Berkeley,US,1986. works[J ]Journal of Software,1999,10(7):737- [4]DANA A.Computational learning theory:survey and 742. selected bibliography [A].Proceedings of the Twenty- [16]周志华，曹存根.神经网络及其应用[M门.北京：清华大 fourth Annual ACM Symposium on Theory of Compu- 学出版社2004 ting[C].[s.1.],1992. [17]王守觉.仿生模式识别（拓扑模式识别） 一一种模式 [5]DUDA R O,HART P E.Pattern classification and 识别新模型的理论与应用[U].电子学报，2002,30 scene analysis[M].New York:John Wiley Sons, (10):1417.1420. 1973 WANG Shoujue.Bionic (topological)pattern recogni- [6]DUDA RO,HART P E,STOCKD G.模式分类[M] tion-a new model of pattern recognition theory and its 北京：机械工业出版社，2003. applications [J ]Acta Electronica Sinica,2002,30 [7]MENDEL SON S.A few notes on statistical learning the- (10):1417.1420. ory R].Advanced Lectures on Machine Learning, [18 ]WANGSJ,QU Y F,LI WJ.Face recognition:biomi- LNAI2600,2003. metic pattern recognition vs traditional recognition [J] [8]张文生，丁辉，王珏.基于邻域原理计算海量数据支 Acta Electronica Sinica,2004,32(7):1057-1061. 持向量的研究01.软件学报，2001,12(5)：711.720. [19]CAO W M,HAO F,WANG S J.The application of ZHANG Wensheng,DING Hui,WANG Jue.Study on DBF neural networks for object recognition [J].Infor- computing the support vectors of massive data based on mation Sciences-Informatics and Computer Science:An neighborhood principle [J ]Journal of Software,2001, International Journal,2004,160(1-4):153-160 12(5):711.720. [20]王守觉，王柏南.人工神经网络的多维空间几何分析及 [9]TAO Q,WANG J.Kernel projection algorithm for 其理论[]，电子学报，2002,30(1)：1-4. large-scale SVM problems[J ]Journal of Computer Sci- WANG Shoujue,WANG Bainan.Analysis and theory ence Technology,2002,17(5):556-564. of highdimension space geometry for artificial neural [10]TAO Qing,WU Gaowei,WANGJue.A generalized S networks[J].Acta Electronica Sinica,2002,30(1): 3Kalgorithm for learning SVM classifiers[J].Pattern 1.4. 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
到极小样本集的方法给出了选择的训练样本 ,为了 使在其上学习得到的模型有很好的性能应满足的性 质(包含某一极小样本集) . 将从包含极小样本集这 个目标出发 ,在一定的限制条件下得到一个新的样 本集所包含实例个数的边界 ,并与 PAC 的样本复杂 度理论进行比较. 3 结束语 总之 ,在基于覆盖的分类学习算法方面 ,基于覆 盖思想在最近 10 年相继提出过一些很有价值的分 类学习方法和理论分析 ,但是 , 大量的理论问题尚 未解决. HSC 学习算法作为一种覆盖分类算法 ,其 性能提高以及计算复杂性、泛化能力等理论问题值 得深入研究. 参考文献 : [1 ] VAPNIK V. The nature of statistical learning theory [ M]. New York : Springer2Verlag , 1995. [2 ]VAL IAN T L G. A theory of the learnable [J ]. Commu2 nications of the ACM , 1984 , 27 (11) : 1134 - 1142. [3 ]BLUMER A , EHRENFEUCH T A , HASSL ER D , et al. Classifying learnable geometric concepts with the Vapnik2Chervonenkis dimension[ A ]. Proceedings of the 19th Annual ACM Symposium on Theory of Computing [C]. Berkeley , US , 1986. [4 ]DANA A . Computational learning theory : survey and selected bibliography [ A ]. Proceedings of the Twenty2 fourth Annual ACM Symposium on Theory of Compu2 ting[C]. [ S. l. ] ,1992. [5 ] DUDA R O , HART P E. Pattern classification and scene analysis [ M ]. New York : John Wiley & Sons , 1973. [6 ]DUDA R O , HART P E , STOCK D G. 模式分类[ M]. 北京 :机械工业出版社 ,2003. [ 7 ]MENDELSON S. A few notes on statistical learning the2 ory [ R ]. Advanced Lectures on Machine Learning , LNAI 2600 , 2003. [8 ]张文生 ,丁 辉 ,王 珏. 基于邻域原理计算海量数据支 持向量的研究[J ]. 软件学报 ,2001 ,12 (5) : 711 - 720. ZHAN G Wensheng , DIN G Hui , WAN G J ue. Study on computing the support vectors of massive data based on neighborhood principle [J ]. Journal of Software , 2001 , 12 (5) :711 - 720. [ 9 ] TAO Q , WAN G J. Kernel projection algorithm for large2scale SVM problems[J ]. Journal of Computer Sci2 ence Technology , 2002 , 17 (5) : 556 - 564. [10 ] TAO Qing , WU Gaowei , WAN G J ue. A generalized S ∃ K algorithm for learning2SVM classifiers[J ]. Pattern Recognition Letters , 2004 , 25 (10) : 1165 - 1171. [11 ]许建华 , 张学工 , 李衍达. 一种基于核函数的非线性感 知器算法[J ]. 计算机学报 , 2002 ,25 (7) : 689 - 695. XU Jianhua , ZHAN G Xuegong , L I Yanda. A nonlinear perceptron algorithm based on kernel functions[J ]. Chi2 nese Journal of Computers , 2002 , 25 (7) : 689 - 695. [12 ]ZHAN G Ling , ZHAN G Bo. A geometrical representa2 tion of McCulloch2 Pitts neural model and its applica2 tions [J ]. IEEE Transactions on Neural Networks , 1999 ,10 (4) : 925 - 929. [13 ]吴 涛 ,张 铃 ,张燕平. 机器学习中的核覆盖算法[J ]. 计算机学报 ,2005 ,28 (8) :1295 - 1301. WU Tao , ZHAN G Ling , ZHAN G Yanping. Kernel covering algorithm for machine learning [J ]. Chinese Journal of Computers , 2005 , 28 (8) : 1295 - 1301. [14 ]陶 品 ,张 钹 ,叶 榛. 构造型神经网络双交叉覆盖增 量学习算法[J ]. 软件学报 ,2003 ,14 (2) :194 - 201. TAO Pin , ZHAN G Bo , YE Zhen. An incremental bi2 covering learning algorithm for constructive neural net2 work[J ]. Journal of Software , 2003 , 14 ( 2) : 194 - 201. [15 ]张 铃 ,张 钹 ,殷海风. 多层前向网络的交叉覆盖设 计算法[J ]. 软件学报 ,1999 ,10 (7) :737 - 742. ZHAN G Ling , ZHAN GBo , YIN Haifeng. An alterna2 tive covering design algorithm of multi2layer neural net2 works[J ]. Journal of Software , 1999 , 10 (7) : 737 - 742. [16 ]周志华 ,曹存根. 神经网络及其应用[ M ]. 北京 :清华大 学出版社 ,2004. [17 ]王守觉. 仿生模式识别 (拓扑模式识别) ———一种模式 识别新模型的理论与应用 [J ]. 电子学报 , 2002 , 30 (10) : 1417 - 1420. WAN G Shoujue. Bionic (topological) pattern recogni2 tion —a new model of pattern recognition theory and its applications [ J ]. Acta Electronica Sinica , 2002 , 30 (10) : 1417 - 1420. [ 18 ]WAN G S J , QU Y F , L I W J. Face recognition : biomi2 metic pattern recognition vs traditional recognition [J ]. Acta Electronica Sinica , 2004 , 32 (7) : 1057 - 1061. [19 ]CAO W M , HAO F , WAN G S J. The application of DBF neural networks for object recognition [J ]. Infor2 mation Sciences2Informatics and Computer Science : An International Journal , 2004 , 160 (1 - 4) : 153 - 160. [20 ]王守觉 ,王柏南. 人工神经网络的多维空间几何分析及 其理论[J ]. 电子学报 ,2002 ,30 (1) :1 - 4. WAN G Shoujue , WAN G Bainan. Analysis and theory of high2dimension space geometry for artificial neural networks[J ]. Acta Electronica Sinica , 2002 , 30 ( 1) : 1 - 4. 第 6 期 何 清 ,等 :基于超曲面的分类算法研究进展 ·5 ·
·6* 智能系统学报 第2卷 [21]XU Zongben,MEN GDeyu,J IN G Wenfeng.A new ap- [33 GALLANT S I.Connectionist expert systems [J ] proach for classification:visual simulation point of view Communications of the ACM,1988,31(2):152-169. [A ]Proceedings of the ISNN 2005 [C].Spring Ver- [34]SETIONO R,LIU H.Understanding neural networks 1ag,2005. via rule extraction[A].Proceedings of the 14th Interna- [22]张涌，朱洪.一类弱集合覆盖问题的近似算法[U] tional Joint Conference on Artificial Intelligence [C]. 计算机学报，2005,28(9)：1497.1500. Montreal,Canada,1995. ZHANG Yong,ZHU Hong.Approximation algorithms [35]WU X.Knowledge acquisition from databases [M]. for the problems of weak set cover[J].Chinese Journal Norwood,1995. of Computers,2005,28(9):1497-1500 [36]AL EXANDER J A,MOZER M C.Template based [23]HE Qing,SHI Zhongzhi,REN Li'an.The classifica- procedures for neural network interpretation[J].Neural tion method based on hyper surface[A].Proceedings of Networks,1999,12(3):479-498. the IEEE International Joint Conference on Neural Net- [37]周志华，曹存根.神经网络及其应用[M,北京：清华大 works[C].Hawaii,2002. 学出版社，2004. [24]HE Qing,SHI Zhongzhi,REN Li'an.The multi-class [38 ]ZHOU Z H.Rule extraction:using neural networks or classification method in large database based on hyper for neural networks [J].Journal of Computer Science surface[A ]Proceedings of the International Confer- and Technology,2004,19(2):24-253. ence on Machine Learning and Application[C].Las Ve- [39]ZHOU Z H,JIANG Y,CHEN S F.A general neural gas,2002. framework for classification rule mining [J ]Interna- [25]何清，任力安，史忠植.基于超曲面的海量数据直接 tional Journal of Computers,Systems and Signals, 分类法[U].计算机学报，2003,26(2)：206.211 2000,1(2):154-168. HE Qing,REN Li'an,SHI Zhongzhi.The large data [40]周志华，陈世福.神经网络规则抽取U].计算机研究 direct classifying method based on hyper surface [J ] 与发展，2002,39(4)：398.405. Chinese Journal of Computers,2003,26(2):206-211. ZHOU Zhihua,CHEN Shifu.Rule extraction from [26]HE Qing,Shi Zhongzhi,REN Li'an,et al.A novel neutral networks [J ]Journal of Computers Research classification method based on hypersurface[J ]Inter- and Development,2002,39(4):398-405. national Journal of Mathematical and Computer Model- [41]周志华，陈世福.神经网络集成[J].计算机学报， ing,2003,38:395.407. 2002,25(1):1-8. [27]HE Qing,ZHAO Xiurong,SHI Zhongzhi.Clssification ZHOU Zhihua,CHEN Shifu.Neural network ensemble based on dimension transposition for high dimention da- [J].Chinese Jornal of Computers,2002,25(1):1-8. ta[J ]Soft Computing,2007,11(4):329-334. [42]ZHOU Z H,JIANG Y,CHEN S F.Extracting sym- [28]ZHAO Xiurong,HE Qing,SHI Zhongzhi.Hyper sur- bolic rules from trained neural networks[J].AI Com- face classifier ensemble for high dimensional data sets munications,2003,16(1):3.15. [A].Proceedings of the 3rd International Symposium [43]ANDREWS R,DIEDERICH J,TICKLE A B.Survey on Neural Networks (ISNN 2006)[C].Berlin:Spring and critique of techniques for extracting rules from er-Verlag,2006. trained artificial neural networks [J].Knowledge-Based [29]DASARATHY B V.Minimal consistent set (MCS)i- Systems,1995,8(6):373,389. dentification for optimal nearest neighbor decision sys- [44JOHN S T.ROBERT C,WILLIAMSON P.Generaliza- tems design [J ]IEEE Trans Syst,Man,Cybern, tion performance of classifiers in terms of observed cov- 1994,24(3):511-517 ering numbers fischer [A].Proceedings of the Euro- [30]HANSEN L K,SALAMON P.Neural network ensem- COLT99[C].Berlin:Springer-Verlag,1999. bles[J].IEEE Trans Pattern Analysis and Machine In- [45]王珏，石纯一.机器学习研究].广西师范大学学报 telligence,1990,12(10):993-1001. (自然科学版)，2003,21(2)：1-15. [31]ZHOU Zhihua WU Jianxin JIANG Yuan,et al.Genetic WANG Jue,SHI Chunyi.Investigations on machine algorithm based selective neural network ensemble[A]. learning [J ]Journal of Guangxi Normal University Proceedings of the 17th International Joint Conference (Natural Science Edition),2003,21(2):1-15. on Artificial Intelligence[C].Seattle,US,2001. [46]HE Qing,ZHAO Xiurong,SHI Zhongzhi.Sampling [32]ZHOU Z H,WU J,TANG W.Ensembling neural net- based on minimal consistent subset for hyper surface works:many could be better than all [J].Artificial In- classfication [A].Proceedings of the Sixth Internation- telligence,2002,137(1-2):239-263 al Cenference on Machine Learning and Cybernetics 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
[ 21 ]XU Zongben , MEN G Deyu , J IN G Wenfeng. A new ap2 proach for classification : visual simulation point of view [ A ]. Proceedings of the ISNN 2005 [ C]. Spring2Ver2 lag , 2005. [22 ]张 涌 ,朱 洪. 一类弱集合覆盖问题的近似算法[J ]. 计算机学报 , 2005 ,28 (9) :1497 - 1500. ZHAN G Yong , ZHU Hong. Approximation algorithms for the problems of weak set cover[J ]. Chinese Journal of Computers , 2005 , 28 (9) : 1497 - 1500. [23 ] HE Qing , SHI Zhongzhi , REN Li’an. The classifica2 tion method based on hyper surface [ A ]. Proceedings of the IEEE International Joint Conference on Neural Net2 works[C]. Hawaii , 2002. [24 ] HE Qing , SHI Zhongzhi , REN Li’an. The multi2class classification method in large database based on hyper surface [ A ]. Proceedings of the International Confer2 ence on Machine Learning and Application[C]. Las Ve2 gas , 2002. [25 ]何 清 ,任力安 ,史忠植. 基于超曲面的海量数据直接 分类法[J ]. 计算机学报 ,2003 ,26 (2) :206 - 211. HE Qing , REN Li’an , SHI Zhongzhi. The large data direct classifying method based on hyper surface [J ]. Chinese Journal of Computers , 2003 , 26 (2) :206 - 211. [26 ] HE Qing , Shi Zhongzhi , REN Li’an , et al. A novel classification method based on hypersurface [J ]. Inter2 national Journal of Mathematical and Computer Model2 ing , 2003 , 38 :395 - 407. [ 27 ] HE Qing , ZHAO Xiurong , SHI Zhongzhi. Clssification based on dimension transposition for high dimention da2 ta[J ]. Soft Computing , 2007 , 11 (4) : 329 - 334. [28 ]ZHAO Xiurong , HE Qing , SHI Zhongzhi. Hyper sur2 face classifier ensemble for high dimensional data sets [ A ]. Proceedings of the 3rd International Symposium on Neural Networks (ISNN 2006) [C]. Berlin : Spring2 er2Verlag , 2006. [29 ]DASARA TH Y B V. Minimal consistent set (MCS) i2 dentification for optimal nearest neighbor decision sys2 tems design [J ]. IEEE Trans Syst , Man , Cybern , 1994 ,24 (3) :511 - 517. [30 ] HANSEN L K , SALAMON P. Neural network ensem2 bles[J ]. IEEE Trans Pattern Analysis and Machine In2 telligence , 1990 ,12 (10) : 993 - 1001. [31 ]ZHOU Zhihua WU Jianxin J IAN G Yuan ,et al. Genetic algorithm based selective neural network ensemble[ A ]. Proceedings of the 17th International Joint Conference on Artificial Intelligence[C]. Seattle , US , 2001. [ 32 ]ZHOU Z H , WU J , TAN G W. Ensembling neural net2 works: many could be better than all [J ]. Artificial In2 telligence , 2002 , 137 (1 - 2) : 239 - 263. [ 33 ] GALLAN T S I. Connectionist expert systems [J ]. Communications of the ACM , 1988 , 31 (2) : 152 - 169. [34 ]SETIONO R , L IU H. Understanding neural networks via rule extraction[ A ]. Proceedings of the 14th Interna2 tional Joint Conference on Artificial Intelligence [ C ]. Montreal , Canada , 1995. [35 ] WU X. Knowledge acquisition from databases [ M ]. Norwood , 1995. [ 36 ] AL EXANDER J A , MOZER M C. Template2based procedures for neural network interpretation[J ]. Neural Networks , 1999 , 12 (3) : 479 - 498. [37 ]周志华 ,曹存根. 神经网络及其应用[ M ]. 北京 :清华大 学出版社 ,2004. [38 ]ZHOU Z H. Rule extraction : using neural networks or for neural networks [J ]. Journal of Computer Science and Technology , 2004 , 19 (2) : 24 - 253. [39 ]ZHOU Z H , J IAN G Y, CHEN S F. A general neural framework for classification rule mining [J ]. Interna2 tional Journal of Computers , Systems and Signals , 2000 , 1 (2) : 154 - 168. [40 ]周志华 , 陈世福. 神经网络规则抽取[J ]. 计算机研究 与发展 , 2002 , 39 (4) : 398 - 405. ZHOU Zhihua , CHEN Shifu. Rule extraction from neutral networks [J ]. Journal of Computers Research and Development , 2002 , 39 (4) :398 - 405. [41 ]周志华 , 陈世福. 神经网络集成 [J ]. 计算机学报 , 2002 , 25 (1) : 1 - 8. ZHOU Zhihua , CHEN Shifu. Neural network ensemble [J ]. Chinese Jornal of Computers ,2002 , 25 (1) :1 - 8. [42 ]ZHOU Z H , J IAN G Y , CHEN S F. Extracting sym2 bolic rules from trained neural networks[J ]. AI Com2 munications , 2003 , 16 (1) : 3 - 15. [43 ]ANDREWS R , DIEDERICH J , TICKL E A B. Survey and critique of techniques for extracting rules from trained artificial neural networks[J ]. Knowledge2Based Systems , 1995 , 8 (6) : 373 - 389. [44 ]JO HN S T ,ROBERT C ,WILL IAMSON P. Generaliza2 tion performance of classifiers in terms of observed cov2 ering numbers fischer [ A ]. Proceedings of the Euro2 COL T’99[C]. Berlin : Springer2Verlag , 1999. [45 ]王 珏 ,石纯一. 机器学习研究[J ]. 广西师范大学学报 (自然科学版) , 2003 ,21 (2) :1 - 15. WAN G J ue , SHI Chunyi. Investigations on machine learning [J ]. Journal of Guangxi Normal University (Natural Science Edition) , 2003 , 21 (2) :1 - 15. [46 ] HE Qing , ZHAO Xiurong , SHI Zhongzhi. Sampling based on minimal consistent subset for hyper surface classfication [ A ]. Proceedings of the Sixth Internation2 al Cenference on Machine Learning and Cybernetics ·6 · 智 能 系 统 学 报 第 2 卷
第6期 何清，等：基于超曲面的分类算法研究进展 [C].Hong Kong,2007. 作者简介： [47]HE Qing,ZHUANG Fuzhen,ZHAO Xiurong,et al. 何清，1965年生，教授，博士生 Enhanced algorithm performance for classification based 导师，主要研究方向为人工智能、数据 on hyper surface using bagging and adaboost [A ]Pro- 挖掘机器学习、模糊集理论，发表学 ceedings of the Sixth International Conference on Ma- 术论文60多篇 chine Learning and Cybernetics [C].Hong Kong, Email heq @ics.ict.ac.cn 2007 [48]HE Qing,ZHAO Xiurong,SHI Zhongzhi.A cognitive 史忠植，1944年生，研究员，博士 data visualization method based on hyped surface[A ] 生导师，主要研究方向为人工智能、多 Proc 6th IEEE Int Conf on Cognitive Informatics (IC- 主体系统、数据挖掘、机器学习、知识 c1007)[C1.[S.1.],2007. 工程等.1979年、1998年2001年均获 [49]HE Qing,ZHAO Xiurong,LUO Ping ,et al.Combina- 中国科学院科技进步二等奖，1994年 tion methodologies of multi-Agent hyper surface classi- 获中国科学院科技进步特等奖，2002 fiers:design and implementation issues [A ]LNAI 年获国家科技进步二等奖，发表学术 4476[C].Berlin:Springer-Verlag,2007. 论文400多篇，出版专著5部 Email shizz @ics.ict.ac.cn 《可拓工程》简介 Introduction to Extensional Engineering 可拓工程的基本思想是用形式化的方法处理各领域中的矛盾问题，研究如何化不相容为相容、化对立为 共存、化不是为是 把理论应用于各个实际领域的关键在于方法.为了更多的学者能运用可拓学的基本理论去处理所在领 域的矛盾问题，我们总结了多年来的研究工作，从可拓学的基本原理出发，完善和发展了可拓方法，它是可拓 论应用于实际的桥梁.把可拓方法与各实际领域相结合，去解决其中的矛盾问题的方法，统称为可拓工程方 法.本书系统地阐述了可拓工程的理论基础、方法体系和应用领域，并给出可拓工程方法的应用案例 为便于读者学习，本书第一章简要介绍可拓学的概况，包括可拓学的研究概况与发展历程、可拓学的理 论框架、可拓学的方法论体系、研究可拓学的科学意义和可拓工程研究现状：第二章介绍可拓工程的理论基 础可拓论，包括基元的概念、拓展分析原理、共轭分析原理、可拓变换、复合元、可拓集、关联函数和可拓 逻辑简介，第三章介绍可拓工程的方法基础可拓方法，包括拓展分析方法、可拓变换方法、共轭分析与共 轭变换方法、可拓集方法、优度评价方法和可拓思维模式；第四章介绍矛盾问题的求解方法，包括矛盾问题的 界定及其可拓模型矛盾问题的运算拓展与变换、不相容问题的求解方法可拓策略生成方法、对立问题 的求解方法转换桥方法和矛盾问题智能化处理的初步研究：第五章介绍可拓工程方法与技术，包括可拓 信息·知识.策略的形式化体系、可拓策略生成系统的实用技术、可拓数据挖掘方法、可拓营销方法、可拓策 划方法、可拓设计方法、可拓控制与可拓检测方法简介和可拓方法在识别、搜索、诊断中的应用.各部分内容 都以若干案例来帮助读者理解可拓学的基本方法和可能的应用.我们期望高等院校和科研单位的教学科研 人员能将这些方法与自己的研究领域相结合，提出更多适合于各专业的可拓工程方法， 本书是作者承接和参加的国家自然科学基金项目和广东省自然科学基金项目的有关研究成果的总结， 作者冀求以此拙作作为引玉之砖，以使更多领域的学者利用可拓工程方法去处理所在领域的矛盾问题，同 时，也希望这本书能成为可拓学通向应用之路的桥梁.本书理论与应用相结合，分析透彻，可操作性强.为方 便不同知识背景和不同层次读者的学习，各部分内容都配备一些通俗易懂的案例，适合高等院校从事管理科 学与工程、智能科学、信息科学、计算机、设计等领域的师生、工程技术人员和管理决策人员阅读，特别适合作 为高等院校相关专业本科、硕士、博士生的选修课教材 本书是“可拓学丛书”之一，由杨春燕研究员和蔡文研究员共同撰写，全书约35万字，科学出版社于 2007年7月出版」 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
[C]. Hong Kong , 2007. [47 ] HE Qing , ZHUAN G Fuzhen , ZHAO Xiurong , et al. Enhanced algorithm performance for classification based on hyper surface using bagging and adaboost[ A ]. Pro2 ceedings of the Sixth International Conference on Ma2 chine Learning and Cybernetics [ C ]. Hong Kong , 2007. [48 ] HE Qing , ZHAO Xiurong , SHI Zhongzhi . A cognitive data visualization method based on hyped surface [ A ]. Proc 6th IEEE Int Conf on Cognitive Informatics ( IC2 CIO07) [C]. [ S. l. ] , 2007. [49 ] HE Qing , ZHAO Xiurong , LUO Ping ,et al. Combina2 tion methodologies of multi2Agent hyper surface classi2 fiers: design and implementation issues [ A ]. LNAI 4476[C]. Berlin : Springer2Verlag , 2007. 作者简介 : 何 清 , 1965 年生 ,教授 ,博士生 导师 ,主要研究方向为人工智能、数据 挖掘、机器学习、模糊集理论 ,发表学 术论文 60 多篇. E2mail :heq @ics. ict. ac. cn. 史忠植 ,1944 年生 ,研究员 ,博士 生导师 ,主要研究方向为人工智能、多 主体系统、数据挖掘、机器学习、知识 工程等. 1979 年、1998 年、2001 年均获 中国科学院科技进步二等奖 ,1994 年 获中国科学院科技进步特等奖 ,2002 年获国家科技进步二等奖 ,发表学术 论文 400 多篇 ,出版专著 5 部. E2mail :shizz @ics. ict. ac. cn. 《可拓工程》简介 Introduction to Extensional Engineering 可拓工程的基本思想是用形式化的方法处理各领域中的矛盾问题 ,研究如何化不相容为相容、化对立为 共存、化不是为是. 把理论应用于各个实际领域的关键在于方法. 为了更多的学者能运用可拓学的基本理论去处理所在领 域的矛盾问题 ,我们总结了多年来的研究工作 ,从可拓学的基本原理出发 ,完善和发展了可拓方法 ,它是可拓 论应用于实际的桥梁. 把可拓方法与各实际领域相结合 ,去解决其中的矛盾问题的方法 ,统称为可拓工程方 法. 本书系统地阐述了可拓工程的理论基础、方法体系和应用领域 ,并给出可拓工程方法的应用案例. 为便于读者学习 ,本书第一章简要介绍可拓学的概况 ,包括可拓学的研究概况与发展历程、可拓学的理 论框架、可拓学的方法论体系、研究可拓学的科学意义和可拓工程研究现状 ;第二章介绍可拓工程的理论基 础 ———可拓论 ,包括基元的概念、拓展分析原理、共轭分析原理、可拓变换、复合元、可拓集、关联函数和可拓 逻辑简介 ;第三章介绍可拓工程的方法基础 ———可拓方法 ,包括拓展分析方法、可拓变换方法、共轭分析与共 轭变换方法、可拓集方法、优度评价方法和可拓思维模式 ;第四章介绍矛盾问题的求解方法 ,包括矛盾问题的 界定及其可拓模型、矛盾问题的运算、拓展与变换、不相容问题的求解方法 ———可拓策略生成方法、对立问题 的求解方法 ———转换桥方法和矛盾问题智能化处理的初步研究 ;第五章介绍可拓工程方法与技术 ,包括可拓 信息 - 知识 - 策略的形式化体系、可拓策略生成系统的实用技术、可拓数据挖掘方法、可拓营销方法、可拓策 划方法、可拓设计方法、可拓控制与可拓检测方法简介和可拓方法在识别、搜索、诊断中的应用. 各部分内容 都以若干案例来帮助读者理解可拓学的基本方法和可能的应用. 我们期望高等院校和科研单位的教学科研 人员能将这些方法与自己的研究领域相结合 ,提出更多适合于各专业的可拓工程方法. 本书是作者承接和参加的国家自然科学基金项目和广东省自然科学基金项目的有关研究成果的总结 , 作者冀求以此拙作作为引玉之砖 ,以使更多领域的学者利用可拓工程方法去处理所在领域的矛盾问题 ,同 时 ,也希望这本书能成为可拓学通向应用之路的桥梁. 本书理论与应用相结合 ,分析透彻 ,可操作性强. 为方 便不同知识背景和不同层次读者的学习 ,各部分内容都配备一些通俗易懂的案例 ,适合高等院校从事管理科 学与工程、智能科学、信息科学、计算机、设计等领域的师生、工程技术人员和管理决策人员阅读 ,特别适合作 为高等院校相关专业本科、硕士、博士生的选修课教材. 本书是“可拓学丛书”之一 ,由杨春燕研究员和蔡文研究员共同撰写 ,全书约 35 万字 ,科学出版社于 2007 年 7 月出版. 第 6 期 何 清 ,等 :基于超曲面的分类算法研究进展 ·7 ·