（计算机软件与理论专业论文）基于分类超曲面的数据分类方法的研究.pdf

中国科技人学例究生院坝j 论义 摘要+ 使用支持向量机理论处理海量数据的学习分类问题是相当困难的。针对这个 问题，本文在对现有学习方法分析的基础上，基于拓扑学中的j o r d a n 曲线定理， 提出了一种基于分类超曲面的通用数据分类方法并加以研究。本文的研究工作主 要包括如下几个方面： ( 1 ) 研究分类超曲面的存在性与构造方法。支持向量机分类的基本思想是 将样本集映射到高维空间，借助二次规划求解支持向量。而基于分类超曲面的方 法( s v m 直接方法) 则是一种全新分类判断算法6 其具有以下特点： 。l 令通过区域细化直接解决非线性分类问题。不需要选择核函数，不需作升维变 换。 夺通用可操作的分类超曲面构造法。通过区域合并计算获得多个超平面组成的 双侧闭曲面作为分类超曲面对空间进行划分。 夺独特、简便、易行的分类判别方法。根据样本点关于分类超曲面的围绕数的 奇偶性进行分类，使得基于非凸的超曲面的分类判别变得简便、易行。 、i 夺适合海量、多类数据分类，并有望推广到高维数据分类。彳 ( 2 ) 基于分类超曲面的思想，提出分类判别方法的基本步骤并设计出s v m 直接方法的训练算法及分类算法。 ( 3 ) 实现s v m 直接方法在二维和三维线性空间中的数据分类。对典型的非 线性数据的分类实验结果说明：分类超曲面可以有效地解决大数据量( 1 07 ) 的非 线性数据的分类问题，并能够提高分类效率和准确度。 ( 4 ) 对s v m 直接方法的推广应用作了进步探讨。提出解决基于分类超曲 面的多类与高维分类问题的方法，并对下一步研究工作提出了建议。 关键词： 机器学习；支持向量机；分类超曲面：s v m 直接方法；j o r d a n 曲线定理 本项州究得到国家自然科学基金资助( 谍趣号6 0 0 7 3 0 1 9 、6 9 8 0 3 0 1 0 ) 与北京市重点自然科学捧仓资助( 谍 咂甘4 0 1 1 0 0 3 ) 中国科技人辱研究生院坝1 1 论义 t h ed a t ac l a s s i f y i n gm e t h o db a s e do ns e p a r a t i n gh y p e r s u r f a c e r e dl j - a n d i r e c t e db yp r o f e s s o rs h iz h o n g - z h i a b s t r a c t i ti sq u i t ed i f f i c u l tt os o l v em a s s i v ed a t al e a r n i n ga n dc l a s s i f y i n gp r o b l e m su s i n g t h et h e o r yo f s u p p o r tv e c t o rm a c h i n e o rs v m t os o l v et h ep r o b l e m ，t h i sd i s s e r t a t i o n a n a l y z e s t h e l e a r n i n g m e t h o d si ne x i s t e n c e f i r s t l y a c c o r d i n g t oj o r d a nc u r v e t h e o r e m an e wu n i v e r s a lm e t h o di sp u lf o r w a r dt oc l a s s i f yd a t ab a s e do ns e p a r a t i n g h y p e r s u r f a c ep r i n c i p l ei nt h i sp a p e r t h ec o n t r i b u t i o n so f t h i sd i s s e r t a t i o na r ea sf o l l o w s ： ( 1 ) t h ee x i s t e n c ea n dc o n s t r u c t i n gm e t h o do f s e p a r a t i n gh y p e r s u r f a c ei ss t u d i e d t h em a i ni d e ao fs v mi st om a pt h ed a t ai n t oh i g h e rd i m e n s i o nl i n e a rs p a c ei nw h i c h t h ed a t ac a nb es e p a r a t e db yh y p e r p l a n e a n ds v m c o m p u t e ss u p p o r t v e c t o r s b y c o m p u t i n gq u a d r a t i cp r o g r a m m i n g h o w e v e r t h em e t h o db a s e do n s e p a r a t i n g h y p e r s u r f a c e ，d i r e c t s v mm e t h o do rd s v m ，i san o v e l a p p r o a c h ，w h i c h c h a r a c t e r i s t i c sm a i n l yl i s ta sf o l l o w i n g ： ( a ) b yd i v i d i n gd o m a i n ，d s v mc a nd i r e c t l ys o l v et h en o n l i n e a rc l a s s i f y i n g p r o b l e m i tn e e d n tc o n s i d e rk e m e lf u n c t i o na n dn e e d n tm a k em a p p i n gf r o ml o w e r d i m e n s i o ns p a c et oh i g h e rd i m e n s i o ns p a c ee i t h e r ) d s v m i sau n i v e r s a la n d o p e r a b l e m e t h o dt om a k e s e p a r a t i n g h y p e r s u r f a c e d s v mu s e ss e p a r a t i n gh y p e r s u r f a c et op a r t i t i o ns a m p l es p a c e w h i c h i sb o t h s i d ec l o s es u r f a c et h a ti sc o m p o s e do f m u l t i h y p e r p l a n eg o t t e nb yu n i t i n ga n d c o m p u t i n gr e g i o n s ( c ) d s v mi s au n i q u e ，c o n v e n i e n ta n dm a n a g e a b l ee l a s s i f 姐n gm e t h o d i t c l a s s i f i e sd a t aa c c o r d i n gt ow h e t h e rt h ew i n dn u m b e ro f t h e s a m p l ei so d d o re v e n s o i ti sc o n v e n i e n ta n d m a n a g e a b l e t oc l a s s i f yd a t au s i n g n o n - p r o t r u d i n gh y p e r s u r f a c e ( d ) d - s v mi ss u i t a b l e 幻c l a s s i f ym a s s i v ea n dm u l t i - c l a s sd a t aa n dc a nb e e x t e n d e dt od e a lw i t hh i g hd i m e n s i o nd a t a p r o b l e m s ， ( 2 ) b a s e du p o nt h ei d e ao fs e p a r a t i n g h y p e r s u r f a e e ，t h i sd i s s e r t a t i o np u t s f o r w a r dt h eb a s i cp r o c e s so f c l a s s i f y i n gd a t a m o r e o v e r ，t h et r a i n i n ga n dc l a s s i f y i n g a l g o r i t h m so f d s v mm e t h o da r ed e s i g n e d ( 3 ) u s i n gd s v mm e t h o d ，t h ep r o g r a m sf o rc l a s s i f y i n gd a t aa r ed e s i g n e di n 2 - d i m e n s i o na n d3 - d i m e n s i o ns p a c e t h ee x p e r i m e n t a lr e s u l t so f t y p i c a ln o n l i n e a r d a t ad i s c r i m i n a t i o ns h o wt h a tt h e s e p a r a t i n gh y p e r s u r f a c em e t h o dc a l l s o l v et h e p r o b l e m o f c l a s s i f i c a t i o no f a v a s ta m o u n t o f d a t a ( 1 0 7 ) e f f e c t i v e l y ，a n d i t i sc l e a r t h a t t h ec l a s s i f y i n ge f f i c i e n c ya n da c c u r a c yh a v eb e e n i m p r o v e db yu s i n gt h em e t h o d ( 4 ) w ee x p l o r et h eg e n e r a l i z a t i o no ft h ed - s v mm e t h o dt or e s o l v et h e c l a s s i f y i n gp r o b l e m so f m u l t i c l a s sa n d h i g hd i m e n s i o n d a t a a tl a s t ，t h e s u g g e s t i o n f o rr e s e a r c hs c h e m eo ff u t u r ei sg i v e n s u p p o r t e db y t h e n a t i o n a l n a t u r a ls c i e n c ef o u n d a t m no f c h i n au n d e r g r a n t n o6 0 0 7 3 0 1 9 ，n o6 9 8 0 3 0 10 t h e k e y n a m r a ls c i e n c ef o u n d a t i o no f b e i j i n ga n d e r g r a n t n o4 0 1j 0 0 3 中困科技人学州究生院f ! ! i | i j 论义 k e y w o r d s ： m a c h i n el e a r n i n g ，s u p p o r tv e c t o rm a c h i n e ，s e p a r a t i n gh y p e r s u r f a c e ，d i r e c ts v m m e t h o d ，j o r d a n c u r v et h e o r e m 中匡i 科技人学训究生院坝卜论义 第一章绪论 人的智慧中一个很重要的方面是从实例学习的能力，通过对已知事实的分析 总结出规律，预测不能直接观测的事实。在这种学习中，利用学习得到的规律 不但可以较好地解释已知的实例，而且能够对未来的现象或无法观洲的现象做出 正确的预测和判断。这种能力就称为推广能力。 在人们对机器智能的研究中，希望能够用机器( 计算机) 来模拟这种学习能 力，这就是我们所说的基于数据的机器学习问题，或者简单地称作机器学习 ( m a c h i n el e a n i n g ) 问题。 1 1 机器学习综述 1 1 1 机器学习的概念和内容 机器学习研究计算机怎样模拟或实现人类的学习行为，以获取薪的知识或技 能，重新组织已有的知识结构使之不断改善自身的性能。它是人工智能领域的一 个重要分支。 机器学习从研究人类学习行为出发，研究一些基本方法( 如：归纳、一般化、 特殊化、：类比等) 去认识客观世界，获取各种知识和技能，以对人类的认识规律 进行探索，深入了解人类的各种学习过程，借助于计算机科学和技术原理建立各 种学习模型，从而为计算机系统赋予学习能力。为了实现这一目的的理论、方法 和工程构成了机器学习的主要任务。此外，机器学习还有另一个基本目标，就是 从理论上探索一些人类尚未发现的新学习方法和途径。 学习能力是智能行为的一个非常重要的特征。但至今对学习的机理尚不清 楚。人们曾对机器学习给出各种定义。h a s i m o n 认为，学习是系统所作的适应 性变化，使得系统在下一次完成同样或类似的任务时更为有效。r sm i c h a ls k j 认为，学习是构造或修改对于所经历事务的表示。从事专家系统研究的人们则认 为学习是知识的获取。这些观点各有侧重，第一种强调学习的外部行为效果，第 二种则强调学习的内部过程，而第三种主要是从知识工程的实用性角度出发的。 机器学习的理论基础涉及人工智能、统计学、脑知模型( b r a i nm o d e s ) 、 适应性控制理论、心理学模型、进化模型( 如遗传算法) n i l s s o n ，1 9 9 6 。机 器学习的研究丌始于二寸一世纪中叶，经过半个世纪的发展，在其它学科的影响下， 其领域内已形成多种并行研究，如归纳学习( i n d u c t i r el e a r n i n g ) 、神经网络 ( n e u r a ln e t w o r k s ) 、聚类( c 1 u s t e r i n g ) 、类比学习( l e a r n i n gb ya n a l o g y ) 、 中国科技人学l l 究生院坝f 论义 遗传算法( g e n e t i ca l g o r it h m s ) 以及学习理论( t h e o r i e s o f1 e a r n in g ) ! f a l e x a n d e r 1 9 9 6 ( 如图1 1 ) ，并且已经取得了很多的成果。机器学习逐渐成为 人工智能的研究核心之一。它的应用己遍及人工智能的各个分支，如专家系统、 自动推理、自然语言+ 理解、模式识别( p a t t e r nr e c o g n i t i o n ) 、计算机视觉、钳 能机器人等领域。 数学 嚣舭m 女龇 哲学 唯心论雌物论 生物学 中枢种鲐系绽 图1 1 学习领域 统汁学 概芈，倌仃等宝l 叭叫斯判决胤则 机器学习的研究是根据生理学、认知科学等对人类学习机理的了解，建立人 类学习的计算模型或认知模型；发展各种学习理论和学习方法，研究通用的学习 算法并进行理论上的分析；建立面向任务具有特定应用的学习系统。这些研究目 标相互影响相互促进。 1 1 2 学习问题的发展 自1 9 5 6 年人工智能奠基以来，学习问题的研究，至今已经历了四个发展阶 段。 ( 1 ) 第一阶段始于5 0 年代的中期 这一阶段的工作不少程度上受启发于神经生理学、生物学等的研究，主要是 研究不需要什么初始知识的通用学习系统，特别是神经网络系统。这一阶段的 个重要特点是数值表示和参数调整，不像当时的人工智能领域重心在于符号表示 和启发式方法，而更偏向于模式识别。这一时期的代表性工作是有感知器、生物 进化过程模拟，以及a l s a m u e l 的很有名的、曾击败过i i 级冠军的计算机跳梗 学习程序。 中国科技人学训究生院颂_ | 论立 r o s e n b a t t 的感知器是第一个学习机器的模型，它利用了最简单的神经冗 模型的自适应特性，每一个神经元都是一个m c c u l o c h p i t t s 模型( 神经元的闽 值元件模型，简称m p 模型) 。感知器被用来解决模式识别问题，在最简单的情况 下就是用给定的例子来构造一个把两类数据分开的规则；他证明了两层感知器能 够将输入分为两类，假如这两种类型是线性并可分，也就是一个超平面能将输入 空间分割。 ( 2 ) 第二阶段始于6 0 年代的初期 这一阶段的不少工作受到心理学和人类学习的启示，主要是概念学习和语言 获取，有人称其为符号概念获取阶段。这一时期的主要特征是使用符号表示而不 是数值表示。当时符号表示已成为人工智能的主要方法。另外，采用数值表示的 神经网络由于m m i n s k y 等于1 9 6 9 年发表的著作从理论上分析了感知器的能力和 限制，使得这方面的研究陷入低谷。这一时期的代表性工作有概念学习系统c l s ， 积木世界结构学习系统。在学习计算理论方面，建立了极限辨识理论。 另外，为了研究学习过程一致收敛的速度和推广性，定义了一系列有关函数 集学习性能的指标，其中最重要的核心概念是v c 维( v a p n i k - c h e r v o n e n k i s d i m e n s i o n ) 。模式识别方法中一个指示函数集的v c 维就是它能打散的最大样本 数目。v c 维反映了函数集的学习能力，v c 维越大则学习机器越复杂( 容量越大) 。 在此基础上，统计学习理论的基本思想得到了很大发展，主要内容包括：大数定 律( 均值一致收敛于其期望的充分必要条件) 、完全有界的函数集和无界函数集 一致收敛速度的界，以及结构风险最小化原则( s t r u c t u r a lr i s km i n i m i z a t i o n ， 即s r m 原则) 。 ( 3 ) 第三阶段始于7 0 年代中后期 由于专家系统的成功和知识工程的形成，这一阶段的工作对知识的重要性尤 其关注，一方面，领域知识大量引入学习程序之中；另一方面知识的自动获取 成为机器学习的应用目标。这一时期机器学习逐渐走向兴盛，各种学习策略、学 习方法相继出现，除了作为主要的归纳学习外，还出现了类比学习、解释学习、 观察和发现学习等等。这一时期有影响的工作有学习质谱仪预测规则系统 m e t a d e n d r a l ，利用a q l l 方法学习大豆疾病诊断规则系统，利用i d 3 方法学习 象棋残局规则，数学概念发现系统棚，符号积分系统l e x ，以及一系列物理定理 重新发现系统b a c o n 。 在学习计算理论上，v a l i a n tl g 提出了概率近似正确p a c 学习模型 v a l i a n t ，1 9 8 4 ，并与计算复杂性联系在一起，这一成果推动了学习计算理论 的发展。 ( 4 ) 第四阶段始于8 0 年代中后期 主要源于神经网络的重新兴起。由于使用隐单元的多层神经网络及反向传播 中国科拽人学圳宄生院坝1 论义 ( b a c k - p r o p a g a t i 0 1 1 ，b p ) 算法的提出，克服了早期线性感知器的局限性，从而 使得非符号的神经网络的研究得以与符号学习并行发展。同时，机器学习在符号 学习的各个方面也更加深入和广泛地展开，并形成了较为稳定的几种学习风范， 如归纳学习，分析学习( 特别是解释学习和类比学习) ，遗传学习等。 这时期有影响的工作有多层神经网络反向传播学习算法，基于解释的学 习，一系列决策树归纳学习方法，j h h o l l a n d 的遗传学习和分类器系统， a n e w e l l 等的s o a r 学习系统，以及p r o d i g y 学习系统等，近期由于复杂世界的 实际应用的需要，出现了结合各种学习方法的集成系统、多策略学习技术、特别 是关于连接学习与符号学习的结合。另外，有着很大应用价值的数掘库知识发现 技术也得到很快发展。 1 2 统计学习理论 包括模式识别、神经网络等在内，现有机器学习方法共同的重要理论基础之 一是统计学。 统计是无需很多背景知识和启发性知识的最基本的、唯一的分析手段。传统 统计学研究的是样本数目趋于无穷大时的极限( 渐近) 特征，现有学习方法也多 是基于此假设。但在实际问题中，样本数往往是有限的，因此一些理论上很优秀 的学习方法实际中表现却可能不尽人意。 v a p n i k 等人从6 0 年代开始研究有限样本下的机器学习问题 v a p n i k ，1 9 9 7 1 。 到9 0 年代，形成了一个比较完善的理论体系一一统计学习理论( s t a t i s t i c a ! l e a r n i n gt h e o r y ) ，对可学习性、正确性、过学习和欠学习、局部极小点等问题 取得了较好的结果。其主要内容包括四个方面： 经验风险最小化准则下统计学习致性的条件； 在这些条件下关于统计学习方法推广性的界的结论； v ，在这些界的基础上建立的小样本归纳推理准则： 实现新的准则的实际方法( 算法) 。 1 2 1 机器学习的本质 机器学习就是对n 个独立同分布训练样本( x ，y ) ，( _ ，儿) 求任意预测函数 集合 f ( x ，w ) 中的最优函数f ( x ，w o ) ，使预测的期望风险最小： r ( w ) = f l ( y ，f ( x ，w ) ) d f ( 艽，y ) 其中，1 4 ) q 是函数的广义参数，l ( y ，f ( x ，w ) ) 是用f ( x ，w ) 预测出j ，造成的 中国科技人学州究生院坝1 j 论义 损失。 在实际学习问题中，用数学平均代替逼近经验风险r 。，= 吉喜( y ，厂( x ，w ) ) ， 调整参数w 使经验风险尺。( w ) 最小代替期望风险只( w ) 最小，就是经验风险最小 化( e r m ) 原则。 如果输出y 是二值的，f ( x ，w ) 是指示函数，损失函数为 三c y ，厂c x ，w ，= ? ；，f ，y = f 。( 。x ，, 计w ) 此时，期望j x l 险就是平均错误率，使它最小的学习方法就是贝叶斯决策：如 果正常状态下x 的类别条件概率密度比异常状态下的大，则把x 归类于正常状 态。 如果输出y 是连续的，即为函数拟合问题，损失函数定义为 三( 弘，( 叻) = ( y 一厂( 五w ) ) 2 ，则有r 。= 吉喜( y 一，( x ，w ) ) 2 ，问题转化为最小二 乘法拟合。 对概率密度估计问题，设密度估计函数为p ( x ，们，损失函数为 z ( p ( x ，砌= - l o g p ( x , w ) 。则有心，= 一l o g p ( z ，曲，即为最大似然法。 h 西 但是，经验风险最小并不一定有期望风险最小：训练误差最小不是总能达到 最好的预测效果，往往存在推广性不强；学习的复杂性不仅与研究的系统有关， 而且要与有限的学习样本相适应。 学习过程的一致性( c o n s i s t e n c y ) 是指训练样本无限时经验风险的最优值收 敛于真实风险最优值( 期望风险值) 。设f ( x ，矿) 是n 个独立同分布样本下函数集 中经验预测风险最小的预测函数，它带来的损失为l ( y ，f ( x ，矿i ) ) ，最小经验风 险和真实风险分别为r , m p ( w * j 月) ，r ( w ln ) 。当 r e m p ( w + i n ) ：g ( w o )r ( 矿i h ) ：r ( w o ) h , 1 ，经验风险最小化学习过程是一致的。其中r ( w 0 ) = i n fr ( w ) 是实际可能的最 小风险。并且，对预测函数集中的所有函数都必须满足经验风险致地收敛于真 实风险( 称非平凡一致性) ，而不是个别函数如此，才有实际意义。 中国科技人学州究生院坝j 。i 仑义 定理( 学习理论关键定理) 对于有界的损失函数，经验风险最小化学习一 致的充要条件是经验风险在如下意义上一致地收敛于真实风险： l i m p s u p ( r ( w ) 一r 。( w ) ) 6 】= 0 ，v 0 其中p 表示概率 月叶w 这一定理还可以强化成双边一致收敛。它把学习一致性问题转化为一致收敛 问题。在学习过程中，经验风险和期望风险都是预测函数的函数( 泛函) ，通过 求使经验风险最小化的函数来逼近能使期望风险最小化的函数。 1 2 2 函数集的学习性能与v c 维 设指示函数集为f ( x ，w ) ， n 个训练样本组成的样本集为 z 。= ( z ，= ( 一，y ，) ，f _ 1 , 2 ，n j 。f ( x ，m 在乞上的随机熵h ( z 。) 是f ( x ，w ) 对z 。实 现不同分类组合数目的对数，即h ( z ) = i n n ( z 。) 。f ( x ，w ) 在所有可能的样本数 为n 的样本集上的随机熵的期望值称f ( x ，们在样本数n 上的v c 熵，即 h ( n ) = e ( i n n ( z 。) ) 。v c 熵是衡量函数集分类能力的指标。 对任意的n ，如果p ( ( r ( 扩i n ) 一r ( w 0 ) ) s ) - j 过程是双边一致收敛的 ( l i r a 研s u p 月( w ) 一( w ) p = 0 , v s 0 ) ，猢l i r a h 月( n ) = o 。 定理函数集学习过程收敛速度快的充分条件是1 i m 皇盟：o 。 h 定理函数集学习过程是一致收敛的，当且仅当对任意的样本分铂 中国川投人学驯究生院坝i 论文 】i m ! 迎：0 ，且这时学习过程收敛速度一定是快的。 h v a p n i k 和c h e r v o n e n k i s 发现所有函数集的生长函数或与样本数成n i 比： g ( n ) ：h i n 2 ，或以样本数的某个对数函数为上界：g ( n ) h ( 1 n ；+ 1 ) ，h h ，其 九 中h 是线性函数到对数函数的转折点。函数集的生长函数如果是线性的，则它的 v c 维无穷大：如果生长函数以对数函数为上界，则v c 维等于h 。经验风险最 小化学习过程是一致的，当且仅当函数集的v c 维是有限的，此时收敛速度是快 的。训练时误差最小并不意味着使用时误差最小，但降低v c 维可以提高学习能 力，这是控制v c 维的原因。 1 2 3 推广性的界 如果损失函数o ( z ，w ) = l ( y ，f ( x ，w ) ) 的耿值是二值的( o 或1 ) ，经验风险和实 际风险之间至少以概率1 一叩满足尺( w ) r 。( w ) + 2 ，其中 。；半m ，型型半型业w 的取值无限多时 | 2 ( i n n l n r l ) n ，函数集中包含有限( n ) 个时 h 是函数集的v c 维，0 1 2 ，则设s 为从s 中权重为1 的b o o t s t r a p 抽样，转步骤3 6 8 j = j ( 1 一e i 、 7 对s 中的每个x ，如c l ( x ，) = y ，则w e i g h t ( x ，) = w e i g h t ( x ，) 屈 8 归一化实例的权重，使s 的总权重为m 9 c 沁) 一8 警。轰，1 0 8 万1 该算法中，不正确实例的权重将作反比于训练集误差的调整，弱学习算法是 保证步骤5 中误差率不超过1 2 。 1 4 本文的研究背景和内容 在现代的信息社会里，计算机科学和技术的进步使得各种形态的数字化信息 的数量和规模以极快的速度增长，越来越多的数据采集设备和科学观测仪器每天 都在产生着大量的数据信息。信息的多元化、复杂化为信息分类和相关技术领域 的研究和发展提出了新的挑战。能够快速赢效地获得所需要的信息是每一个人的 迫切要求，而有力的信息分类工具的支持将是必不可少的。因此，基于数据的学 习问题的研究显得尤为重要。 1 4 1 研究背景 统计学习理论为机器学习问题建立了一个较好的理论框架，也发展了一种新 的通用学习算法支持向量机( s v m ) 。s v m 对小样本、非线性和高维数据具 有很好分类性能，其方法是通过内积函数定义的非线性映射( 核函数) 将非线性 样本集映射到一个高维线性空间使之可分。在计算上，s v m 借助二次规划求解 支持向量需要反复计算一个n 维的内积矩阵( 其中n 是样本个数) ，所需要的计 算开销是相当大的，从计算理论上分析，在个人计算机上，用s v m 技术处理样 本个数的规模界限一般为4 ，0 0 0 个 s c h l k 6 p f , 1 9 9 9 张，2 0 0 1 】，因而解决海量数掘 的分析与处理是几乎不可能的。 1 9 9 9 年，张铃与张钹教授提出二次规划优化函数的几何方 法 z h a n g ，1 9 9 9 。 采用球面投影函数作为非线性映射，完成样本点的分类问题，即将计算分类超、r 中国科技人学训究 二院坝l 论义 面的问题转换为计算样本点两两之间距离j ；j 亍构成的距离空间上的覆盖问题。实质 上是基于邻域晌方法，需要作升维变换。艾献张，2 0 0 1 】对邻域方法作了详尽的 数学分析和几何解释，并给出了三种典型的求支持向量的邻域算法。其中，测试 中达到两千力线性可分数据，一万非线性u ，分数据。 上述方法共同的特点是作升维变换，神二高维空间，通过分类超平面对样本点 分类，逆向来看，就是在低维空间存在分类超曲面可对样本点分类。 1 4 2 本文的研究内容 1 4 2 1 研究内容 本文研究的目的是在低维样本空间直接寻求分类超曲面。 本文在研究统计学习理论，支持向量机( s v m ) ，基于邻域的空问划分方法， j o r d a n 曲线定理基础上，建立基于超曲面的分类判别理论，实现一种用于海量数 据分类的s v m 直接方法。具体包含以下研究内容： 分类超曲面的存在性研究与构造方法： 基于超曲面的分类判别方法； 低维状态下，s v m 直接方法的实现； 提出解决基于分类超曲面的多类与高维分类问题的方法。 1 4 2 2 本文的组织结构 本论文主要出七章组成。 第一章是全文的概述，对机器学习、统计学习理论以及分类学习的研究现状 进行了简单的综述。 第二章中讨论了几种主要的分类学习方法，着重对支持向量机和基于邻域的 空间划分方法作了分析。 第三章提出了基于分类超曲面的分类方法的基本思想；并对此分类方法的理 论基础及分类超曲面的存在性加以论述。 第四章、第五章中分别讨论了s v m 直接方法在二维和三维数据分类中的实 现；并对实验结果加以分析。 第六章提出基于分类超曲面的多类与高维分类问题的解决思想。 第七章s v m 直接方法的编程实现。 论文的最后部分是全文的总结和对未来工作的展望。 中国科投人学训篼生院坝f j 论卫 第二章学习中的分类问题 2 1 学习问题的一般描述 学习问题可以看作是利用有限数量的观测来寻找待求的依赖关系的问题。可 以用一个学习模型来描述( 如图2 - 1 ) 。 幽2 - 1 学习系统模型 在图2 1 中，圆圈表示信息体( 如观察的数据，以及事实、规则等知识) ； 方框表示过程；箭头指示数据在学习系统中的流向。 环境为学习单元提供外界信息源( 如经验实例) 。学习单元利用该信息对知 识库作出改进( 增加新知识或重新组织已有知识) 。执行单元利用知识库中的知 识执行任务，任务执行后的信息又反馈给学习单元作为进一步学习的输入。 当考虑执行单元的反馈信息时，存在两种相对的学习方式，即监督学习和非 监督学习。前者是指有导师立即给予学习者( 学习单元) 关于其学习行为的反馈 信息，后者则是学习者自己为自己作出判定，或仅能得到一点很粗略的指导。在 分类任务领域里，监督学习一般称为实例学习。丽非监督学习的学习者必须自己 决定自己的类以及类的数目，这种学习称