（计算机应用技术专业论文）可变空间树分类器.pdf

何萍：可变空间树分类器 捅要 分类是机器学习的一个核心研究内容。在多种现存的分类器电，最力篱单有 效的一种就是决策树。但是，传统的决策树算法由于实现的年代较早，运行效率 为了适应当时有限的内存而有所魉牲；另一方面，传统决策树算法仅采用简单的 单变量测试，所以只能产生平行于坐标轴的超矩形决策面，在需要斜线或曲线决 策蘑的数据集上泛优性能不高。本论文针对以上不足，对决策树分类器进行了深 入的研究，并得到以下三个研究成果。 一、我们提出了一种基于主存的c 4 。5 快速实现，称为f 蔽c 4 5 。f a 或c 碡5 利 用预处理首先将所有数据在各连续属性上的先后顺序提取出来，然后用间接桶排 序结合位并行技术对连续属性的分裂点评价进行优化，透过在赛定范围内的二分 搜索来加速对测试属性分割点的寻找，并在此过程中进行一些结构上的整合来减 少冗余计算，改进系统的整体性能。f a s tc 4 。5 改善了c 4 5 算法的部分时间复杂度， 大大减少了决策树的构建时间，并在实验中得到验证。 4、 二、我们提出了一种潜在属性空间树分类器( l a s t ) 框架，通过将原属性空 间交换为更容易分离数据或更符合决策树分类特点的潜在属性空间，突破传统决 策树算法的超矩形决策面局限，改善树分类器的泛化性能。在l a s t 框架下，我 们提出了两种奇异向量空间斜决策树( s o d t ) 算法，通过对全局或局部数据构建 奇异向量空间，并在此新空间内构建传统的单变量决策树或树结点，最终间接获 得原空间内近似最优的斜决策树分类器。实验结采显示，与传统的单变量决策树 和其它斜决策树算法相比，s o d t 的分类准确率更高，构建的决策树大小更稳定， 置决策树构建时闻与单变量决策树相近，丽远小于其它斜决策树算法。 三、我们提出了一个基于非线性流形映射的分类器( n m m c ) 框架，通过结 合流形映射，分类器和在测试数据集上的扩展三个可变元素，力菲线性分类器的 设计提供了一个统一的框架。在n m m c 框架下，我们进一步提出了一种谱空间树 分类器( s s d f ) ，它将m 嵯醚c 韵流形映射实现为拉普拉薪矩阵的谱空间变换，将 分类器实现为决策树，从简化新条件属性与类别属性之间关系的角度，提高决策 旖分类器的泛纯能力。在s s d t 的基础上，我们还提出了一种基予有监督流形映 射的谱空间树分类器，通过在无监督的谱空间变换中加入已知训练数据的类别信 i i 扬州大学硕士学位论文 息，从而有监督地指导不同类别的数据在新流形上更好地分离开来。实验结果显 示，s s d t 无论在分类准确率、构建的决策树大小，还是在分类稳定性方面，都远 胜于传统的决策树算法。 关键字：机器学习，分类，决策树，c 4 5 ，奇异向量空间，流形映射，谱方法 何萍：可变空间树分类器i i i a b s t r a c t c l 蕊s i 曩e 躐i o 嚣i s 越i 撒蓼攫瞧越愆s e a 掩h 嚣既遮撒继辩l 砥邂孓a 瓣o n g 氆ev 鞫畦。璐 e x i s t i n gc l a s s i f i e r s ，o i l eo f t l l em o s tu s e 如1 搬l de a e c t i v et o o l si sd c c i s i o n 旬旧e h o w e v e r ， 翘黥i o 建舔蠢c 主s i o 珏囊伐越g o 斑阻塔勰隧l l y 妇v e 骶i r 瑚陡撒ep e 哟t 熊鞠c es a c 纛纛e 甜 f o rt l l ec o n s i d e r a t i o no ft h e1 i m i t e dn l a i nm e m o 巧a tt h a tt i m e ，a 1 1 dt h e i rs i i l 9 1 e v a r i 觚t 耗髓潍e a c h 溉e 妁a i ce 纽。糠yp 哩丽娃c ea x i s p 僦l 蘸巍y p e f i f e c 专黼g l ed e 吱s 主。建 b o u l l d a r i e s ，w h j c hh a 、，e 、 ，e a kg e n e r a l i z a t i o na b i l i t ) ，o nc o m p l e xd a t a s e t s i nt l l i st l l e s i s ， w e 勤c 璐豫壕ea b o v el i m i 纨i o 罄o f 弧d 诋o n 羹d e c i s i o 矬骶e sa 鼗dp f o v i 如氇e c o 仃e s p o n d i n gs o l u t i o n sa sf o l l o w s f 运s l ，w ep 室o p o s eaf 轰鲢m a i n 一搬e m o 拶泌l p l e m e 嫩a t i o no fc 4 5a l g o 撼t h m ，捌瞄e d f 邪tc 4 5 f 猫tc 4 5u s c sap r e p r o c e s s i n gt 0e x t r a c tt h eo r d c ri 响n n a t i o no fa nt l 圮 t l j p l e so ne v e 拶a t 蛹b u 钯，t h e no p 蘧i m i z c s 啦ec o n l 遗u o 潲a t t 矗b u l es p l i t se v a l l l a t io _ 薹l s 硒m 虹坨i n d i r e c tb u c k 晦s o r tc o n l b 孤溺、蕊m 饿eb i t - p a r a l l e l 钯c h n i q u c ，a n d f m a l l y i t a c c e l e r a l e st h es e a r c hf o rc u t o f ru s i l l gt 董l eb i n a 拶- s e a f c hw i t t l l e 姗w e s tr 激培e b e s i 氐s ，s o m es 戗u c t u 】嘲i n t e 蓼a t i o ni sa l s o 伽p l o y e dj l lf a s tc 4 5t 0r e d u c ef e d u n d a i l c y 锄di n m r o v ee 髓c i e n c y i ti ss h o w 熊馈哦f a s tc 4 。5r e d u c e sp a no ft h et i m ec o m p l e x 毋o f c 4 5a n da c c e l 麟蹴s 也e 椭e n s 钒l c t i o np c e s s 斛斑l yi ne x p 商m e n 士s 。 s e c o n d ，w ep r e s e n tal a t e n ta 晒b u t es p a c et r e e ( l a s t ) c l 嬲s i f i e r 丘锄e w o 咄 w k c h 船璐f o 触s 氇e 谢g 趣越a t 撕b u t es p a c e 诬专ot h em o f ed a 主a s e p 魏穗b l e 甜m o r e c l a s s m e r - o r i e n t e dl a t e n ta t t r i b u t e s p a c e ，s 0t l l a t m e 协a d i t i o n a l 仃c ：ec i 嬲s i f i e r s 。 b 灌卜r e e 鼬g i ed e c i s i 滩酌l l l i 面l r ye 跹b ee x t e l 通e d 锹避i t sg e n e f 越i z a 专i o 觳a b i l 姆e a nb e i i n p r o v e d u n d e rt h el a s t 觑眦e 、v o r k ，w ed e s i g nm os i n g u l 舯v e c t o r _ s p a c eo b l i q u e d e c i s i o n 讯e ( s o d d 峨蛹赴璐s o d t 潞溉鼢s i n 鲜l 甜v e e 幻rs p a c ef o r 嚣o b 蠢 a i l d o rl o c a ld 盛帆b u i l d st r a d i t i o r 妊dd e c i s i o nn e0 r 协e cn o d e si l lt h en e ws p a c e ，a l l d o b 凌燃氆e 鬈螂i m a 重e l y 难臻巅。坟i 鼋粥d 主s i o 鼓细eo f 氆e 撕g i 撒l 蘸瘟b l | 玺e 饕戳：e i 1 1 d i r e c t l y 硒i t sr e s u l t e x p e r h e n t 烈r e s u l t ss h o wm a t ，c o m p a r e d 、析t ht h e 缸a d i t i o i l a l 豫i v 蘸疆抵i s i 鼬豫a 醛。曩烈o b l i q 辩d e c i s i 黼锯e e 蠢笋蠢鼬簦s ，s o 研峨纛落m s g i v em 曲e r c l a s s i f i c a t i o na c c u r a c y ，i n o r es 协b l ed e c i s i o n 仃e ：e s i z e ， c o n l p 黼a b l e l v 扬熊大学硕士学位论文 t r e e c o i l ：s t n 蝣t i o nt 妇ea sn l ei l n i v a r i 趾td e c i s i o nt r e e ，a 芏l dm u c hl e s st b 王mt 1 1 a lo fo t h e r o b l i q u ed e c i s i o 髓臼e e s t i l i r d ，w ep r o p o an o n l m e a rm a l l i f o l dm 印p i n gc l a s s i f i e r ( n m m c ) 觑眦e w o r l 【 w 隧c h 证t e 掣a t e sm 8 嫩稻l d 匐躲p p i 毪g ，e l 鲻蛀f i 懿射添t e s t 如魄e x 忿n s i o 髓氇r e cv 鑫砖a ：b l e c o m p 0 鹏n t s ，t op r 0 v i d eau i l i f i e d 舭i i i l e w o r kf o rn o i l l i n e a rc l a s s i f i e rd e s i g l l u 1 1 d e rm e n 磁m c 彘腿硷矗，w ep p o s e 鑫s 辫敦罐s p e 丑i e e i s i 馓羹e e ( s s 莎d 确p 瘐l l m s s d ti n l p l e m e n t s 删嘣内l dm a p p i n go fn m m c 鹪s p e c t r a ls p a c et r a l l s f o m a t i o no nt h e l 印l a c i 雒蕊确叙毒ds i 掰p l i 每囊e 糙l a t i o 建婊谗o f 谯e 粒w 藏蠢l i o 隧l 删& 髓sa 稚氇e c l a s sa t t r i b u t e ，a i l ds e l e c t sd e c i s i o nt r c ea sm ec l a s s i f i e rf o rs i m p l i c i 够b yi n t e 笋a t i n g 氇ee l a s si 翻碗强森。纛o f 抚赫g 击唿谴国囊eo 蠢g i f l a 差l 獭s 珥骶i 辩ds p e e 嘲印e 佃舭s f 0 衄a t i o n ，w ea l s op r e s e n tas p e c 讹ls p a c ed e c i s i o l l 仃e ea i g o r i t h mb a s e do n 辚p o i s e d 舔雒i 南l d 礅辫肇i 嚣g ，妊艇e 魏隆印s 氇ed i 巍e 愆嫩e | 豁s e so f 蠡拯证幻辩w 渤 w i t hb c t t e rs e p a u r a t i o n w ep r o v e 洫e x p e r i e m e n t sm a ts s d th a v cg r e a ta d v a n _ c a g eo v e r 也e 缎迸i l i o 黻ld e c i s i 锄溉蠢静蠢专h 疆s 遍f e s 弦c o fe l 鑫s s i 曩e 继i 鼹e 越a c y ，d i s i 傩 1 t e es iz ea n dr o b u s t n e s s k e y 、帕r d s ：m a c m n el e 猢f l i n g ，c l a s s i f i c a t i o n ，d e c i s i o n 讯i e ，c 4 5 ，s i n g u l a rv e c t o rs p a c e ， 璎鑫嫩如l d 封躲卿越g ，s 辨c t 戚m e 饿酲 扬州大学硕士学位论文 扬州大学学位论文原创性声明和版权使用授权书 学位论文原创性声臻 本人声明：所呈交的学位论文是在导师指导下独立进行研究工作所取得的研 究成果。除文中已经标明引用的内容外，本论文不包含其他个人或集体已经发表 的研究成果。对本文的研究做如贡献的个人和集体，均已在文中以明确方式标明。 本声明的法律结果由本人承担。 学位论文作者签名： 可萍 签字墨期：加艿年芎月8 l 尽 学位论文版权使用授权书 本人完全了解学校有关保留、使用学位论文的规定，郎：学校有权保留并向 国家有关部门或机构送交学位论文的复印件和电子文档，允许论文被查阅和借阅。 本人授权扬州大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。同肘授权中国科学 技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通过网络向 社会公众提供信息服务。 l 学位论文作者签名： 可痹 导师签名： 。 l 夺五是 签字日期：埘辎月；f 日签字日期：2 瞄年5 月；f 日 ( 本页为学位论文末页。如论文为密件可不授权，但论文原创必须声明。) 何萍：可变空间树分类器 第一章引言 机器学习是计算机科学的一个重要研究领域，它对科学技术的发展起着重要 的支撑和推动作用。分类是机器学习的一个核心研究内容，它为机器学习其它方 面的研究提供了基础性的帮助。在多种分类器中，决策树是一种非常简单又高效 的分类方法。而近几年来新兴起的流形学习和谱方法，则为决策树分类器的进一 步发展提供了潜在的帮助。 1 1 机器学习 机器学习是人工智能的一个核心研究分支，顾名思义，即是让机器( 计算机) 具有与入一样( 甚至超过人) 的学习能力，苁面实现入工智麓【殛i 0 7 】。近年来， 机器学习在计算机科学的各个研究领域，尤其是计算机视觉和自然语言处理方面， 发挥饕越来越重要的终翊，已经成为当前最流行、最热门的技术之一，并逐渐受 到各个应用领域越来越多的关注。 在宇航领域，美国著名的n a s a 四l 实验室在“勇气”号和“机遇”号火星机器入 的设计过程中，应用了大量的机器学习技术；在汽车制造方面，一位机器学习专 家领导的斯坦福大学参赛队用他们的无人驾驶车，赢得了美国d a 即a ( 国防部先 进研究计划局) 组织的自动驾驶车辆竞赛；在互联网技术方面，g o o g l e 、y a h o o 和百度等互联网搜索引擎都必须依靠着不断更新的机器学习技术来支撵；在新兴 的生物信息学领域，各种机器学习技术都被用来研究从d n a 到基因、基因表达、 蛋自质、基因电路、细胞、生理表现等一系列环节上的现象和规律。美国的 n a s a j p l 实验室的科学家在s c i e n c e 【e d 0 1 】上指出，机器学习对科学研究的 整个过程正起到越来越大的支持作用，该领域将稳定丽快速地发展，并将对科学 技术的发展发挥更大的促进作用。 2 扬娜大学硕士学像论文 1 1 1 发展过程 机器学翊的发展大致经历了以下三个时期【c x 9 6 】。第一阶段是2 0 世纪5 0 年 代中时到钠年代中时，机器学习的热烈时期。此阶段的研究墨标是各类囊组织系 统和自适应系统，主要研究方法是不断修改系统的控制参数和改进系统的执行能 力，焉不涉及与具体任务有关的知识，主要代表工作有塞缪尔( s a 趱糖1 ) 的下棋程 序。 第二阶段是2 0 世纪6 0 年代中叶到7 0 年代中叶，机器学习的冷静时期。本阶 段的研究目标是模拟人类的概念学习过程，并采用逻辑结构或图结构作为机器内 部接述，主要代表工作有温斯顿( w 纽哟砖的结构学习系统和海靳罗思( 珏a 弦s r 娥h ) 等的基本逻辑的归纳学习系统。 第三阶段是2 0 世纪7 0 年代中叶到8 0 年代中叶，机器学习的复兴时期。研究 者们将单个概念的学习扩展为多个概念的学习，探索不同的学习策略和学习方法， 把学习系统与各种应用结合起来，并取得了巨大的成功。1 9 8 0 年美国卡内基梅隆 大学举行的第一届机器学习研讨会，标志着机器学习正式成为一个独立的学科领 域并在全世界兴起。 当前机器学习的发展正在经历着一个应用推动研究不断前进，研究内容日益 细化，各种新技术百花齐放的迅速发展时期。 1 1 2 研究内容 r s m i c h a l s l ( i 等人【t j t 8 3 】把机器学习的研究内容划分成“从例子中学习、“在 问题求解和规划中学习”、“通过观察和发现学习”、“从指令中学习”等范畴。e - a f e i g e n b 硼m 在著名的人工智能手册【p e 8 3 】中，则把机器学习技术划分为四大 类，即“机械学习”、“示教学习”、“类比学习”和“归纳学习”。 所谓“机械学习，就是指把外界输入的信息原封不动地记下来，然后在需 要的时候再取出来，这显然不是真正意义上的“学习”【z l l i 0 7 】。“示教学习”类 似于 t j t 8 3 】中的“从指令中学习，而“类比学习”则相当于m t 8 3 】中的“通 过观察和发现学习”【蹦0 7 】。“从例子中学习的“归纳学习”，是自2 0 世纪8 0 年 代以来在机器学习领域被研究地最多的，应用地最广的研究内容。以现在的观点 何萍：可变空间树分类器3 入的测试数据预测输出，例如分类和回归。无监督学习则是指连训练数据的输出 也是未知的，就要求找到关于输入数据的某种模式，例如聚类。而介于有监督学 习和无监督学习之间的半监督学习，就是指有一部分数据的输出是己知的，而另 一部分数据的输出却是未知的，它包括半监督分类，半监督聚类和半监督回归等 内容。 1 2 分类 分类是机器学习中最为基础和核心的研究内容。令以表示数据的第i 个条件属 性，刃些d 1 d 2 “表示m 个条件属性的取值集合，c 些 c 1 ，c 2 ，勺) 表 示类别集合，则分类的研究任务就是通过学习训练数据集 ( z i ，玑) ) 警，其中甄口 为第i 个训练数据在条件属性上的取值，玑c 表示z i 的类别，建立关于条件属性和 类比属性之间的模型，对未知类别的测试数据z 预测其所属类别。从根本上而言， 分类的目的在于重建我们所感知的模式的内在模型，而分类技术则相互区别于它 们所依赖的候选模型 i 冲d 0 l 】。 目前几种较为常用的分类方法包括：决策树，贝叶斯方法，人工神经网络，七 近邻，支持向量机和集成分类器等。 1 2 1 决策树 决策树 t 0 m 9 7 是求解分类问题的一种最为简单有用的技术【m a r 0 3 】。它用树的 形式来表示一系列查询回答式的模式分类过程。因此，使用该方法需要先构建一 棵决策树，对分类过程进行建模，然后再将其用于对新数据的分类。 一棵决策树是由结点和有向边组成的层次结构。它的根结点和内部结点对数 据的某个属性进行测试，通过与其相连的有向边给出相应的决策，它的每一个叶 子结点则都被赋予一个指定的类别标签。当决策树对新数据进行分类时，新数据 被从树的根结点开始，自上而下地经过若干个内部结点的测试，它在根结点和内 部结点上的测试结果决定了它沿哪个分枝向下移动，重复这个过程直到数据到达 树的某个叶结点为止，则此叶结点所带的类别标签就是该数据的类别标签。 决策树算法的优点在于可以对各个属性的重要性做出排序，执行速度快又准 4 扬州大学硕士学位论文 确率高，具有高可理解性和归纳推理能力；而决策树的缺点则在于对训练数据敏 感，稳定性不高。 ，- 一一、 g e n e1 、 、她! 三里妻乏 y e s ? 1 l 、 g e n e2 、 、是曼兰! ， 、 因 ( a ) 决策树 1 2 2 贝叶斯方法 ( b ) 决策树分类决策面 图1 1 决策树分类器 贝叶斯分类 j a 9 6 】是建立在贝叶斯理论基础上的一种基本统计分类。它的出发 点是利用概率的不同分类决策与相应的决策代价之间的定量折中。它的基本假设 是，决策问题可以用概率的形式来描述，并且所有有关的概率结构都已知。它的 方法是使用最大似然方法估计类别的条件后验概率。 贝叶斯分类的优点是简单，对噪声健壮；缺点是基于一些统计假设，可能不 符合实际情况。 ( a ) r e v e r e n dt b a y e s m 私) = 掣 ( b ) 贝叶斯公式 图1 2 贝叶斯分类器 蛰7 图 豳、一一一 何萍：可变空间树分类器 5 1 2 3 人工神经网络 人工神经网络( 砧州) 【a d t 9 6 】的原理来自于神经生物学上神经元的信号输入 输出过程。粗略地说，它是一套相互连接的输入、输出和隐含层单元的集合，每 个连接具有一个权重。神经网络通过在学习阶段调整这些权重，以期望对输入样 本做出正确的分类。 a n n 的优点在于，只要隐含层单元足够多，就可以拟和任何复杂形式的非线 性关系；而缺点则在于训练速度慢，且结果不易理解。 1 2 4 七近邻 图1 3 人工神经网络分类器 后近邻算法( 州) 【c h 9 5 】是一种简单的基于相似性度量的分类方法。它对未 知样本的分类是通过搜索数据空间中与未知样本距离最近的后个训练样本，然后 将这南个样本中出现频率最高的类别指定为未知样本的类别。由于k n n 无需在训 练样本上进行任何训练或者构建任何分类模型，因此它被称为是一种懒惰( 1 a z y ) 的分类器。 k n n 方法的优点是直观，误差率低且没有线性约束，而缺点则是难以定义准 确的距离，需要指定参数尼。 6 扬州大学硕士学位论文 ，一一、二 。 ， 、： ， 二、 二 lx i 、 ， ： 一 、 _ ， ( a ) k n n 1 2 5 支持向量机 盛懑 l 黛嚣 图1 4 七近邻分类器 ( b ) k n n 分类决策面 支持向量机( s v m ) b i v 9 2 建立在统计学习理论的结构风险最小化原则上， 其基本思想是针对二分类问题，在高维空间中寻找一个超平面对两类样本进行分 割，以保证分类边缘最大化和错误分类最小化。通过引入核技术( k e m e lm e t h o d ) ， s v m 还可以将原数据特征空间通过核函数映射到更高维的特征空间，然后在新的 特征空问中构造线性判别函数，从而保证了算法有较好的推广能力。 r _ 1 l l 嘎。、 h l，+ 一 。 ： ( a ) 多个决策面( b ) 最人化边缘的决策面 图1 5 支持向量机选择( b ) 作为分类决策面 m f l 曜川 。 一二- ，。iw8 何萍：可变空间树分类器7 ( a ) 原空间中复杂的决策面( b ) 高维空间中简单的决策面 图1 6 核方法 s v m 算法的优点在于将分类问题转化为二次规划，避免了陷入局部最小值的 陷阱；而缺点则是对核函数的选择缺少理论性的指导，对多分类问题的处理不够 自然。 1 2 6 集成分类器 罄下如瓣叼豢 雾is e t 瓷i 誉泌i ，鼢脯攀 囤，蛩 圆西 圈- 图1 7 集成分类器 集成分类器( e n s e m b l e ) 算法 d i e 0 0 通过重新使用或选择数据，训练得到多 8 扬州人学硕士学位论文 个不同的分类器，然后组合它们的的预测结果，以期达到改善分类器性能的目 的。它背后的思想内涵在于，从特定的数据集中抽取多个数据子集，使得有可能 计算任意统计量的值及其范围。目前较为著名的几种集成方法包括 b a g g i n g b r e 9 6 】，b o o s t i n g f s 9 7 和r 髓d o mf o r e s t 【b r e o1 】。 e n s e m b l e 的优点是易于实现，用简单的分类器就可以达到较高的泛化性能； 而缺点则是不一定能获得最优解，且容易对噪声数据产生过拟合现象。 1 3 流形学习 自2 0 0 0 年s c i e n c e 上发表了三篇关于流形的论文 t s l 0 0 】 r s 0 0 】【s l 0 0 】之后， 流形学习就逐渐受到机器学习和其它领域研究人员的广泛关注。流形学习假设数 据集在未知但存在的低维内在变量作用下，在观测空间会形成高维流形【z h a 0 6 】。 所以，流形学习的研究任务就是要挖掘出具有流形结构的数据集内在( 几何) 规 律。 与传统的维数约减方法如主成分分析( p c a ) 和线性判别分析( l d a ) 只能 处理具有线性结构和高斯分布的高维数据集相比，流形学习可以把在高维空间中 呈现高度扭曲的数据集，在低维空间中恢复其内在结构。z h a n g 等人 z l l a 0 4 根据 流形学习对低维流形或嵌入映射的不同约束或限制方式，将其划分为以下四类： ( 1 ) 投影法：假定具有流形的数据集属性间相互关联，通过用投影和期望的 方法迭代寻找数据集的主流形( 即中间曲面) ，从而描述数据集的内在结构。这 种方法几何上直观，但在高维空间中的推广较难。 ( 2 ) 生成式模型：假定观测数据是从均匀分布在低维的隐结点中生成的，通 过迭代的方法建立观测空间和隐空间之间的映射关系。该模型是一种生成拓扑模 型，但由于在计算上使用e m ( 期望最大化) 算法，因此易陷入局部最小。 ( 3 ) 嵌入法：假定数据集在观测空间和隐空间中保持相同的全局或局部结 构，通过最优化一定的目标函数，把数据集在尽可能维持原始结构的前提下，嵌 入到指定的低维空间中去。嵌入法可分为全局嵌入法和局部嵌入法。该方法易于 实现，不会陷入局部最小解，但对噪声数据不够鲁棒，并且对参数较为敏感。 ( 4 ) 信息论方法：假定在观测空间数据集和嵌入空间数据集中，近邻数据之 何萍：可变空间树分类器9 间的概率信息熵最小。信息论方法主要受嵌入法的启发，但也存在易陷入局部最 优的缺点。 1 4 谱方法 图1 8 流形学习 p h o t o r e c e p l o r s 嘲懒嘲啷”一出x 1 斓獭嬲蠲劫哪舾_ 缸x 2 ” 零膨珊 i ：翌孺粉静“币x 3 谱方法是一类使用特征值分解的方法。传统的谱方法最早仅被应用于一些具 有线性结构的学习问题，如主成分分析( p c a ) 和线性判别分析( l d a ) 。然而近 年来，一些活跃在在机器学习、统计学以及理论计算机科学研究领域的研究者们， 成功地将谱方法应用到如非线性维数约减，无参数聚类以及非线性分类等具有非 线性结构的学习问题上。由于谱方法建立在严格又具有较长历史的线性代数基础 上，一方面可以直接得到全局最优解而不必担心陷入局部最小，另一方面也有很 多现成的高效特征值分解实现使用谱方法铺平道路，因此，在应用上谱方法经常 表现出比传统的迭代和贪婪算法更为明显的优势。本文仅讨论主要应用在图像分 割和谱聚类上的谱方法。 l o 扬州大学硕士学位论文 1 s 论文的主要工作 图l 9 图谱分解五= 墨1 凡忱谚 本论文主要从以下几个方面展开工作： ( 1 ) 改善c 4 5 算法的运行效率，提出了f 缀c 4 。5 实现。c 4 。5 是一个在机器 学习领域被广泛应用的著名决策树分类算法，它的运行性能为了适应当时的有限 内存面被有魇牺牲。本文第二章提出了一种基于主存的c 4 3 算法快速实现，篱称 为f a s tc 4 5 。该实现利用预处理首先将所有数据在各连续属性上的先后顺序提取 出来，然震用闻接桶排序结合位著行技术对连续属性的分裂点评价进行优化，再 用在界定范围内的二分搜索加速对测试属性分割点的寻找，并在此过程中进行一 些结构上的整合来减少冗余计算，改进系统的整体性能。实验证踞，f 弧c 4 。5 和 经典的c 4 5 ( r e l e 嬲e8 ) 系统以及著名的w e k a 环境中的j 4 8 分类器相比，t c 4 5 的运行效率远高于后两者，并表现出近线性的可扩放性。 孵一 哪舻 l 一 u 学毫 气。 襻一 哪寸 学巍擎； 跚一 瑚矿 悉蝴 却铲 四b 嘶哪粥 何萍：可变空间树分类器 1 1 ( 2 ) 提高决策树分类器的泛化性能，提出了一个潜在属性空间树分类器框架 和框架下的两种奇异向量空间斜决策树算法。传统的决策树算法在每个树结点上 只对单个属性进行测试，因此决策面仅限于平行于坐标轴的超矩形，对需要使用 斜线或曲线分割的数据集，分类的泛化性能较差。本文在第三章提出了一种潜在 属性空间树分类器( l a s t ) 框架，通过将原属性空间变换为更容易分离数据或更 符合决策树分类特点的潜在属性空间，突破传统决策树算法的超矩形决策面局限， 改善树分类器的泛化性能。在l a s t 框架下，我们提出了两种奇异向量空间斜决 策树( s o d t ) 算法，通过对全局或局部数据构建奇异向量空间，然后在新空间内 间接构建原空间内近似最优的斜决策树分类器。实验显示，s o d t 与传统的单变量 决策树算法和其它斜决策树算法相比，s o d t 的分类准确率更高，构建的决策树大 小更稳定，决策树构建时间与单变量决策树算法相近，而远小于其它斜决策树算 法。 ( 3 ) 对决策树算法进行非线性扩展，提出了一个基于非线性流形映射的分类 器框架，并在该框架下提出一种谱空间树分类器。传统的单变量决策树算法和斜 决策树算法都无法很好处理的一种情况就是，数据的原条件属性与类别属性之间 存在着某种非线性( 如卷曲和折叠) 的关系。本文的第四章提出了一个基于非线 性流形映射的分类器( m c ) 框架，通过结合流形映射，分类器和测试数据集 的扩展三个可变元素，为非线性分类器的设计提供了一个统一的框架。在n l 订m c 框架下，我们进一步提出一种谱空间树分类器，将n m m c 的流形映射实现为拉普 拉斯矩阵的谱空间变换，将分类器实现为决策树，从简化新条件属性与类别属性 之间关系的角度，提高决策树分类器的泛化能力。实验结果显示，谱空间树分类 器无论在分类准确率，还是在构建的决策树大小上，都相比于传统的决策树算法 有很大的优势。 1 6 论文组织 论文以下章节的组织结构如下： 第二章提出一种快速的c 4 5 算法实现。 第三章中提出一个潜在属性空间树分类器框架，并在此框架下提出两种奇异 1 2 扬州大学硕士学位论文 向量空间斜决策树算法。 第四章提高一种基于j 摹线性流行映射的分类器框架，并在此框架下提出一种 谱空间树分类器。 最蜃，第五章对全文作出总结并给出工作展望。 何萍：可变空间树分类器1 3 第二章f a s tc 4 。5 c 4 5 是一个在机器学习领域被广泛应用的著名决策树分类算法，它的运行性 能由于为了适应当时有限的内存所以被有所牺牲。本章提出了一种快速的c 4 5 算 法实现，名为f a s tc 4 5 。该实现通过组织新的数据结构，把间接桶排序与位并行 技术相结合，以及将最佳分割点的二分搜索限制在最窄的范围之内，从而大大减 少了f a s tc 4 5 的决策树构建时间。实验显示，f a s tc 4 5 与c 4 。5 ( r e l e 嬲e8 ) 构建相 同决策树可加速达5 8 倍。此外，f a s tc 4 5 在不同类型的数据集上也表现出良好的 可扩放性性能。 2 1 引言 分类在机器学习领域和数据挖掘领域都是一个被广泛研究的问题。在现有的 多季孛分类器中，决策树分类器与其它分类器相毖有高效、准确等多种优点【t w y o 铡 d w k 0 4 】，它的高可理解性和可解释性更是其他分类器所不能比拟的。c 4 5 【q u i 9 3 】 算法是一个著名的决策树分类算法，它由锄i 蛰l 褫设计著实现，已成为目前为止使 用和研究最广泛的决策树算法之一。 在实现方嚣，q 试越飘实现的经典c 4 。5 系统由于考虑到当时的内存有限，所以 尽可能地减少了内存的使用量，但却以牺牲算法的运行效率为代价。现如今计算 机的蠹存不断增大，该如何提高算法的运行效率就变成了现在的开发者和用户最 关心的问题。 以往开发的基于主存的c 4 。5 算法的快速实现包括：e c 4 5 【勋9 0 2 】，它是经典 c 4 5 系统上的一个补丁，目的是改进c 4 5 算法的运行效率。e c 4 5 提出了三种不 同的优化策略，但对最佳优化策略的选择是部分经验性的，它的代码不可褥。y a d t 【r u 9 0 4 】，它是e c 4 5 的后续版本，但事实上已变成另一个类似于c 4 5 算法的决策 树算法。因此，我们把这两种实现排除本文的实验比较范围之外。对c 4 5 算法改 进的其它经典决策树算法还包括：将预排序和宽度优先生长策略相结合的s l i q 算 1 4 扬髑大学硕士学位论文 法【m 声舢6 】，将有序的属性值附在每个树结点上的s p 刚n t 算法【s a m 9 6 】，具有统 一的更有效的属性评价框架的黼n f o r e s t 算法【g r _ g 9 8 】。此外，还有c 例r t 算法 【b r e 8 4 】也是一个著名的用于分类和回归的决策树算法；b o a t 算法【g g r l 9 9 】为决 策树的构建提供了一种更快的递增式构建方式；基于外存的c l o u d s 算法0 媛s 9 8 】 通过近似操作减少了构树的计算复杂度和i o 复杂度；s c a l p a r c 算法岍张9 8 】用哈 希表实现了s p r 蚤疆算法的并行化；p c 霹5 算法【l s 9 硝提供了e 4 _ s 算法的并行纯实 现等。 一 本章提出了一种基于主存的c 4 5 算法快速实现，简称为f a s tc 4 5 。f a 鼓c 4 5 首先利用预处理将所有数据在各连续属性上的先后顺序提取出来，然后用间接桶 排序结合位并行技术对连续属性分裂点的评价进行优化，最后使用在界定范禹内 的二分搜索加速对测试属性分割点的确定。这一过程中，结合位并行技术的间接 桶排序将原来的菲线性时间复杂度o ( 1 r 滓叼l f l ) 减少到线性的0 ( m 口z 冗一m 锄冗) ， 在界定范围内的二分搜索将原来的线性复杂度o ( 1 t i ) 降为亚线性的d ( 业皤茜幽) ， 而预处理则增加了额外的时闻复杂度d ( 以铭；孵铊) 。此外，一些结构上的调整也被用 于减少冗余度和改进系统的整体性能。这些技术的组合使得f 嬲tc 4 。5 大大加速了 c 4 5 算法的决策树构建过程。实验结采显示，与经典的c 4 5 ( r - e l 髓s e8 ) 系统以及 著名的w e k a 环境中的j 4 8 分类器相比，f a s tc 4 5 的运行效率可高达后两者的5 8 倍和9 9 倍，而且数据集越大优势越明显。此外，f a s tc 4 5 在真实数据集和人工数 据集上也都表现出了近线性的可扩放性，优于经典c 4 5 系统和j 4 8 分类器的超线 性可扩放性。 本章的其它部分组织如下：第二节对决策树和c 4 5 算法进行了简单的介绍， 第三节分析了c 4 5 算法的运行瓶颈，第四节详细解释了f 缀c 4 5 的设计策略，第 五节给出了f a s tc 4 5 的性能评价，最后第六节总结全章。 2 2 决策树与c 4 5 算法 决策树是一类应用广泛的树分类器。本节首先介绍决策树的基本知识，然后 再绘出c 4 5 算法的决策树构建过程描述。 何萍：可变空间树分类器1 5 2 2 1 决策树 决策树是决策表的一种经济的表达形式，它包含了三种基本元素：内部结点， 分枝和叶子结点。内部结点指定一个对条件属性的测试，其形式取决于被测试属 性的类型。如果测试属性是连续型的，则测试是一个关于属性值是否小于或等于 某个特定值的问题，例如“a g e 3 4 7 。如果测试属性是离散型的，则测试就 是一个关于属性具体取值的问题，例如“s e x = ? 。从内部结点延伸出来的每个 分枝( 如y e s 和n o ) 都对应着一种可能的测试结果，而分枝达到的最底层叶子结 点则有一个类别属性的特定取值作为自己的类别标签。给定一棵决策树，对新数 据进行分类的方法是，将新数据从决策树的根结点开始，自上而下地按照测试结 果进行下移，直到它到达某个叶子结点为止，则该叶结点所带的类别标签就是新 数据的类别标签。图2 1 演示了由训练数据( a ) 构建决策树( b ) 的例子。在图2 1 ( a ) 中，训练数据被组织成元组( 呻l e ) 集合的形式。所谓“元组”就是指训练数据 表每行上的数据样本，它在各个属性上都有一个特定的值，如元组1 ( 2 0 ，1 8 8 ， m ) 就表示a g e = 2 0 ，h e i g h t = 1 8 8 ，c l 嬲s = m 。 国 o 0 囝 o a g eh e i g h t e l a 蠊 2 01 8 8m 81 4 5m 5 31 6 5f 2 5 1 8 3m l o1 1 0f 1 51 6 3f 伯t r a i n i n g 【) ；l 悟 k s t ： 他) d i s i o nt r 瞎 图2 一l 决策树示例 决策树的构建一般包括两个阶段：生长阶段和剪枝阶段。在生长阶段中，所 有训练样本被自项向下、分而治之地用于构建一棵完全生长的决策树。在这个阶 段，每个决策树结点的构建过程如图2 2 所述：首先判断分配至待建树结点的数据 集x 是否满足叶结点的条件，如满足则构建叶结点并返回( s t e p1 ) ；否则，选取最 佳测试+ ( s t e p2 ) 用于构建内部结点( s t e p3 ) ；然后，对于+ 每一个可能的分枝 1 6 扬州大学硕士学位论文 ( s t 印4 ) ，将x 中满足该分枝条件的数据样本( s t e p5 ) 分配给对应的子树结点用 于其递归构建( s t e p6 ) ；最后，返回构建的内部结点( s t e p8 ) 。 p r o c e d u 舡t r e e n o d e c o n s t r u c l r i o n ( x ) 却以? 分配至结点的数据集x d 婶耐? 构建的树结点 1 矿i s l e a f ( x ) 删跖朋+ 一l e a f ( x ) 2亡+ 卜s e l e c t b e s t t e s t ( x ) 3 卜n e n l a l n o d e ( x ，亡) 4 弦，即幽f b m c h c o u n t ( t + ) 5 k 卜p a n i t i o n ( + ，x ，i ) 6 咖c l l i l d f 卜t r e e n o d e c o n s t m c t i o n ( 咒) 1 e n 哇f o r 8r e t h r n6 图2 - 2 决策树结点构建过程 最常用的几种用于评价测试+ 的函数包括信息增益比( g a i n r 砒i o ) 【q u i 9 3 】、 基尼指数( g 谳) 【b r e 8 4 】、) ( 2 测验 h a r 8 4 m i n 8 7 】和g 系数【m i n 8 7 】等。c 4 5 算法 采用的信息增益比评价函数，定义如下： 令d 毋表示分配至树结点上的数据集，d ? 表示d 砂根据测试+ 分配至第i 个分支 的子数据集，磁表示d 毋中类别标签为c 的子数据集，则信息增益比定义为 g a i n r a t i o ( ) - 裂揣 。( 2 1 ) 其中 g a i n i n f o ( 砂纠三即卜胬即 ) ( 2 2 ) s p l i t i n f o ( 咖) _ 一莓高l o g 。高 ( 2 3 ) 即忙一罱慨胬 ( 2 4 ) 决策树构建的第二阶段即剪枝阶段，就是剪去一些统计无效、由噪声造成树 结点和分支，目的是防止过拟合。常用的剪枝方法包括代价一复杂度剪枝 ( c c p ) b r e 8 4 】，减少错误剪枝( i 冱p ) 【q u i 8 7 】，悲观错误剪枝( p e p ) q u i 8 7 】、基于错 误剪枝( e b p ) q u i 8 7 1 、最小错误剪枝( m e p ) 附b 8 6 】以及基于最小描述长度的剪枝 何萍：可变空间树分类器 1 7 【m 够5 】等。c 4 5 算法采用的基于错误剪枝( e 转p ) 方法假设决策树在训练数据 上的错误率呈正态分布，悲观估计各个树结点在置信度( 默认为o 2 5 ) 范围内的 测试错误率，从而确定是否需要子橱替代( s 曲锰霭瓣p l a c e n l c m ) 或子树上升( s 曲红优 豫i s i n g ) 的剪枝操作。e b p 的测试错误率估计公式为