（计算机应用技术专业论文）一种改进的分类算法及其应用.pdf

华中科技大学硕士学位论文 摘要 目前，高校教师资源管理缺乏技术理论支撑，导致师资管理不当，师资流失严 重，急需能够正确分析教师类型与流失原因的分类系统，从而能够为相关管理人员 提供及时地、有针对性地决策依据。 分类技术中常见的是决策树方法，常见的有i d 3 ，c 4 5 ，s l i q ，s p r i n t ，p u b l i c 等，其关键问题在于测试属性的选择。为了找出真正影响决策的属性，减小决策树 的规模，引入了基于属性相似度的分类算法，该算法是根据相似性原理，以测试属 性和决策属性的相似度作为启发规则构建决策树的分类算法，其选择测试属性的计 算速度比i d 3 算法更快。然而，基于属性相似度的分类算法在属性的选择上倾向于 选择取值较少的属性，结果通常会增加树的深度；在构建决策树过程中，此算法不 需要重新计算相似度，容易降低分类的精确度。 针对基于属性相似度的分类算法存在的问题，在使用属性相似度作为属性选择 依据的基础上，对其相似度的计算方法做了修改。改进思路是：判断每个属性的取 值分布，如果一个属性取某个值的所有记录都属于一个决策类型，则认为从该属性 能直接判断类属性取值的能力较强，应该在原相似度计算方法的基础之上提升该属 性的相似度，从而选择相似度高的属性作为测试属性，尽量避免选择取值较少的属 性，在每分割一次数据集之后，重新计算相似度。为了避免出现过度拟合现象，采 用剪枝技术修整决策树。 采用s q l s e r v e r 数据库，使用v c # n e t 开发工具，应用改进的决策树算法， 开发了师资流失原因分析系统，用于挖掘教师的各特征取值和流失原因之间的潜在 关系，通过分析教师数据中体现出来的特性，为每一个流失原因找到一种准确的描 述或模型。该系统实现的关键技术在于构建决策树时属性的选择计算，以及决策树 的路径如何存储这两个问题。 系统测试证明，根据改进算法生成的决策树提取的决策规则十分有效，分类结 果与实际基本相符，极大地提高了系统的工作效率。挖掘结果表明改进后的算法比 基于属性相似度的分类算法和著名的i d 3 算法的预测精度都要高，计算相对于i d 3 算法更为简便。 关键词：决策树算法，i d 3 算法，属性相似度，教师资源流失，剪枝 华中科技大学硕士学位论文 a b s t r a c t c u r r e n t l y , t h el a c ko ft e c h n o l o g i c a lt h e o r yi nt h em a n a g e m e n to ff a c u l t yi nt h eh i g h s c h o o l sh a sr e s u l t e di n i m p r o p e rm a n a g e m e n ta n d s u b s t a n t i a ll o s so ff a c u l t y a c l a s s i f i c a t i o ns y s t e mw h i c hc o n t a i n sc o r r e c ta n a l y s i so ft h et e a c h e r s t y p e sa n dc a u s e so f t h el o s si su r g e n t l yn e e d e ds oa st op r o v i d eat i m e l y , e f f e c t i v ea n dd e c i s i v em e t h o d sf o rt h e c o r r e s p o n d e n tm a n a g e r s d e c i s i o nt r e ew a sw i d e l yt l s e i di nt h e c l a s s i f y i n gt e c h n i q u e ，i n c l u d i n g t h e f r e q u e n t l y - q u o t e di d 3 ，c 4 5 ，s l i q ，s p r i n t ，p u b l i ca n ds oo n ，t h ek e yt ow h i c hl a yi nt h e c h o i c eo ft e s ta t t r i b u t e s i no r d e rt om i n i m i z et h es i z eo ft h ed e c i s i o nt r e ea n df i n do u tt h e a t t r i b u t e st h a te x e ne f f e c to nd e c i s i o n t h ec l a s s i f y i n ga l g o r i t h mb a s e do ns i m i l a rd e g r e eo f a t t r i b u t e sw a si n t r o d u c e d t h i sa l g o r i t h ma p p l i e dt h ep r i n c i p l eo fs i m i l a rd e g r e ea n du s e d t h es i m i l a rd e g r e eo fb o t ht e s ta t t r i b u t ea n dd e c i s i o na t t r i b u t ea sh e u r i s t i cr u l e st o c o n s t r u c td e c i s i o nt r e e i ti sm u c hq u i c k e rt h a ni d 3w h e nu s e di nt h ec h o i c eo ft e s t a t t r i b u t e q u i c ka si tw a s ，i tt e n d e dt oc h o o s ea t t r i b u t ew i t hl e s sv a l u e ，o n l yt oi n c r e a s et h e t r e e sh e i g h t w h i l ec o n s t r u c t i n gt h ed e c i s i o nt r e e ，i td i dn o tn e , e dr e p e a tt h ec a l c a l 砒i o no f s i m i l a rd e g r e e ，s op r e c i s i o no fc l a s s i f i c a t i o nw a se a s yt ob er e d u c e d t os o l v et h e s ep r o b l e m s ，i m p r o v e m e n t sw a sm a d ei nt h ea l g o r i t h mo fs i m i l a rd e g r e e b yu s i n gs i m i l a rd e g r e eo fa t t r i b u t e sa st h ep r i n c i p l eo fa t t r i b u t ec h o i c e t h ei m p r o v i n g m e t h o d sc o u l db es u m m a r i z e da sf o l l o w s ：n ev a l u ed i s t r i b u t i o no fe a c ha t t r i b u t ew a s d e f i n e d i fa l lt h er e c o r d so fo n ec e r t a i na t t r i b u t ev a l u ew e r ec l a s s i f i e dt oo n ed e c i s i o nt y p e t h ea b i l i t yo ft h i sa t t r i b u t et od e f i n es u c hk i n do fa t t r i b u t ev a l u ew a sc o n s i d e r e dt ob e b e t t e ls i m i l a rd e g r e eo ft h i sc e r t a i na t t r i b u t es h o u l db ei n c r e a s e ds oa st oc h o o s et h e a t t r i b u t eo fh i g h e rs i m i l a rd e g r e ea st h et e s t i n ga t t r i b u t ea n dt oa v o i dt h ec h o i c eo f a t t r i b u t ew j t hl e s sv a l u ea n dt or e p e a tt h ec a l c u l a t i o na f t e re a c hd i v i s i o n i nt h e c o n s t r u c t i o no fd e c i s i o nt r e e , i tw a sp r u n e di no r d e rt om a k ei ts i m p l e ri ns t r u c t u r ea n d c l o s e rt ot h em i n i m i z i n g p e r f e c tr u l es e t , t h u sa v o i d e do v e r - f i t t i n g b yu s i n gs o ls e r v e ra st h ed a t a b a s ea n dv c # n e ta st h et o o la n da p p l y i n gt h e i m p r o v e dd e c i s i o nt r e ea l g o r i t h m ，t h es y s t e mo fa n a l y z i n gt h ec a u s e so ft h ef a c u l t yl o s si n i i 华中科技大学硕士学位论文 h i g hs c h o o l sw a sd e v e l o p e ds ot h a tt h ep o t e n t i a lr e l a t i o nb e t w e e nv a l u eo ft e a c h e rt y p e s a t t r i b u t ea n dc a u s e so fl o s sw e r ee x p o s e d t h r o u g ht h ea n a l y s i so ft h ec h a r a c t e r i s t i c si n d a t a b a s ea b o u tt e a c h e r s ，a na c c u r a t ed e s c r i p t i o no rm o d e lw a sd i s c o v e r e df o re a c hc a u s e o fl o s s n ct e c h n o l o g i c a lk e y st or e a l i z et h i ss y s t e mi n c l u d e dt w oa s p e c t s ：t h es e l e c t i o n a n dc a l c u l a t i o no fa t t r i b u t ew h i l eb u i l d i n gd e c i s i o nt r e e ，a n dt h em e t h o dt os t o r et h er o a d o fd e c i s i o nt r e e t h es y s t e mt e s tp r o v e dt h a tt h ed e c i s i o nt r e eb u i l tt h r o u g ht h ei m p r o v e da l g o r i t h m w a sv e r ye f f e c t i v ea n dp r o m o t e dt h es y s t e m se f f i c i e n c yb yal a r g em a r g i n ，a n d ，g e n e r a l l y ， t h er e s u l t so fc l a s s i f i c a t i o nc o n f o r m e dt ot h ef a c t s n er e s u l to fm i n i n gd e m o n s t r a t e dt h a t i tw a sm o r ep r e c i s et h a nt h ec l a s s i f y i n ga l g o r i t h mb a s e do ns i m i l a rd e g r e eo fa t t r i b u t ea n d t h ef o r e c a s tp r e c i s i o no fi d 3 ，a sw e l la ss i m p l e rt h a ni d 3 k e y w o r d s ：d e c i s i o nt r e e ，i d 3a l g o r i t h m ，s i m i l a rd e g r e eo f a t t r i b u t e ，l o s so ff a c u l t y , p r u n i n g 1 1 1 独创性声明 e v l 0 17 6 6 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他 个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：确鸱唆狄 日期：孔形厶年月年日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校 有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本论文属于 不保密口： ( 请在以上方框内打“”) 学位论文作者签名：0 如唆袱 日期：加l ，年f 月夸日 指导教师签名：马之协 日期f 加年月弘日 华中科技大学硕士学位论文 1 1课题的研究背景和意义 1绪论 随着信息技术和计算机技术的飞速发展，社会各个领域应用的技术要求也在不 断提高。进入信息社会以来，信息技术经历了从单一的计算机操作系统到计算机互 联网络操作的改变过程；从c s 结构到多层体系结构计算模式的转变；从单一数据 库到大型数据仓库以及从局域网到i n t e m e t 的改变过程。 进入信息时代以来，数据库技术与应用日益普及，而人们所面临着的却是急速 膨胀的数据海洋如何有效利用这一海洋数据的丰富知识已成为广大信息技术工作 所关注的焦点之一。依靠传统的数据库管理系统的查询检索机制和统计分析方法， 已经远不能满足现实的需要。例如：股票经纪人需要从日积月累起来的大量股票行 情变化的历史记录( 数据) 中发现其规律以供预测其未来的趋势；研究天气预测专家要 从天气情况的历史数据( 其规模可达数千g b ) 中发现天气变化规律来预测将来的趋 势；医生要从病人数据库中存储的大量数据中发现某种疾病的起因、症状等；地质 学家想通过分析地球资源卫星发回的大量数据和照片来发现有开采价值的矿物资源 等。这些数据都存在着如下共同特点：一是数据量特别大，一般都在g b 以至t b 级；二是他们都以结构化的形式存储在数据库中，都包含了大量潜在的有价值的信 息。但面对数据库中的海量数据，如何有效地管理，怎样才能有效地利用数据库中 数据，以及怎样才能发现其潜在的知识，这就需要有新的、更为有效的手段来对各 种数据源进行整理并挖掘出新的知识，从而发挥这些数据的潜在价值。 在大量激增的数据中往往隐藏着许多重要的信息，如果能从数据库中提取出其 所蕴含着的规则( r u l e s ) 、规律( r e g u l a r i t i e s ) 、论断( i n f e r e n c e ) 等这一类 的高层次信息或知识，则能为用户创造更多潜在的利润。因此，对大量历史数据进 行分析、推理，挖掘出有用的知识就显得非常必要。 数据仓库和数据挖掘技术正是在这个急需解决如何快速、有效地寻找有用知识 这类问题的背景下应运而生的。作为解决该问题的强有力工具，数据仓库与数据挖 掘技术的研究和应用近年来受到了越来越多的关注，并取得了极大的进展。目前已 经成为了计算机界的研究热点之一，引起数据库、机器学习、统计等领域的专家的 广泛关注。 华中科技大学硕士学位论文 数据挖掘的任务是从数据集中发现模式，在实际应用中，往往根据模式的实际 作用细分为以下几种：分类、聚类、回归、序列、时间序列等。其中分类是重簧的 数据分辑方法，痘矮擎黉广泛，整鼹教亵鼗努覆的应廷鼹多，瑟在褰校箍姿管理方 颇应用较为少见，使得部分高校在教师资源管理方面缺葱技术理论支撑，从而导致 师资管理不当，良好的教师资源无以为继。 然藤，嶷好的教爨资源是一令学校赖以生存和发展琴诃忽略的堂簧保障，凌学 校整个运转体系中发挥麓中流砥柱的作用。霸前高校的办学实力竞争越来越体现在 师资力量这一重要环节上，师资薄弱的高校不仅在每年的招生大战中节节败退，照 耀以通过教窍部的评馈，无法立足子高校之转。如果没鸯一支业务熊力和自身素质 过硬的教舜队伍，那么建设品_ | 簿学校并持续发展也就成了纸上谈兵。与学生管理雷 同的是，学校相关管理部门也没能意识到教师资源危机，即使造成了大量的教师资 源的流失，也没有采取积极的解决方案和防范攒施，使得学校发展一褥受阻。 在学梭办学魏搂纛织生燕模不断发展鞋大盼露眩，学校内帮考积累了大量鸯教 师资源密切相关的数据。在这些海餐的数据的背后隐藏着许多重要的模式和知识， 对分析研究商校教师流失的原因具有重大意义。快速、准确、高效地将这些模式和 熊识挖摇臻寒，是学校糖舞教郯资源管理承乎瓣增强学校究争力的一令重要手段。 1 2 国内外研究概况 麸数攥簿孛发瑷籍浚( k d d ) 疑2 0 世纪鞠年底寒努鲶酶，k d d 一谣是在1 9 8 9 童f8 月于美网底特律市招开的第界k d d 国际学术会议上正式形成的。k d d 研究 的问题包括：( 1 ) 定性知识和定量知识的发现；( 2 ) 知识发现方法；( 3 ) 知识发现 豹应震等。痰予在攘拿大的第一鹾知识和数据挖掘国际学零会议上，把数据库中躲 “数据”比喻成“矿床”，“数据挖獭”一词很快流传开采i l 】。 数据挖掘技术在不断的发展，威用领域也在不断地扩大。将数据挖掘技术成用 予赢校各种资源的领域的碜 究已有颇多成果。比如：谷璩，朱莉等1 2 l 撼难了基于决策 帝磅技术静蜀技研究生镄想数毒蓦挖粼研究，对数据挖掘鼓零在研究釜髂患库孛静巍溺 进行了初步分析，运用决策树算法对所给数据进行分类和预测，并凰通过实例验证 了该算法的有效性，找出了其中有价值的信息；又如王中辉，鲁来风【3 l 将决策树应用 予教学评价之孛，提藏了教学谨徐黪辩学经、客鼹性帮公正经，傻之舞葑缝为教学 服务。 2 华中科技大学硕士学位论文 在人力资源方面的研究也层出不穷。张德新，崔巍，蒋天发利用k 中心算法对 人才素质进行分类【4 】，借助判定归纳分类法对人才素质进行分析和评价，提出了混和 数据挖掘算法，提裹了入方素质谨徐的裹效热翻瓣学毪；擎孛科技大学熬学者稠浩 纹等设计了一种模糊数据挖掘方法能够对缀织中现有人才进行聚类分析，从丽发 现组织内部的人才类型，并可判断菜员工属予哪一种类型；而同样怒华中科技火学 黪张宣生教授等旧也必我们提供了掰的视鹭与方法，采用选择辩分类瓣，将选择模瓣l 期予入力资源数据仓瘁的挖掘系统巾，获得了成功的应髑。 而将数据挖掘应用予高校教师遮群特殊的人群中分析激师的流失原因与类型似 乎并不多见，本文试图深用分类方法勰决这一闯题。 分类的嚣的是学会令分类蔹数或分类模黧 的情况，q u i n l a n 在 1 9 9 3 年出版了专著机器学习规划，介绍了极其流行的决策树算法c 4 5 ，该算法 可以看作是i d 3 算法的一个扩展，它有效的解决了i d 3 算法的部分缺点。 g 虹一1 4 1 是l b r e i m a n 等人在1 9 8 4 年提掇豹决策树算法，其原璎与i d 3 稆似， 在c a r t 申提遗了杂魔骜g 减的概念，按杂度削减最大分裂节点生长决策瓣，与i d 3 不同的是，c a r t 最终缴成二叉树，然后利用煎采样技术避行误差估计和树剪枝( 基 于最小代价复杂性) ，然后选择最优作为最终构建的决策树。这些算法均要求训练集 金赛# 或一襄# 分在分类懿过程孛一蠢黢整在蠹存牵。 鉴于内存使用的有限性，i b m 的m e h t a 等在1 9 9 6 年提出了s l i q t l 5 】算法，它 针对数据量远大于内存容量的情况采用了类袭和属性表两种数据结构，利用换入换 凌策略处璞大数据量。阏眩s l i q 舞法还孵决了数据集鳇一次扫攒瓣题，另终它还 采用了预排序，极大的加快了处理的速度。由于s u q 的黉表必须驻留在内存巾， 所以处理的数据量仍旧有限，i b m 的j s h a r e r 在1 9 9 6 年提出了s p r i n t 1 6 j 算法，它 逶过属性袭和类直方躅鼹秽数据结构对s l i q 辘够处理的数据容量送行了进一步扩 充，可以粪涎处理超大勰数据库的数据。 以上算法都分为建树和修剪两个阶段，建立决策树阶段对训练集建立一棵决策 树，为了防瞧决策树的道度拟合，在修剪阶段对己生成的决策树进行剪技，从丽获 褥更裹耩确发的决策树。实验表鹅剪技会剪去派始决策楗的缀大一部分( 有静胃戆达 到原始树的9 0 1 。显然，在建树阶段所做的犬部分工作都是白做的。 决策树算法通常包播两部分f 1 2 l 【1 7 1 ：一是特征属性的选择，开始时所有数据都在 投节点，然蕊壤蕹设定憋标准选择溅试属性；二是溺不露盼测试属拣递羟缝进行数 据分割。构造一棵决策树就是形成一个训练集的分类过糕，人们可以在分类过穗中 宪成对目标的获取策略岛规则提取1 1 8 】【1 9 】。 针对莰l 试属性瓣选掭过程中i d 3 葵法存在的润题，蓬国以刘小虎等必代表的学者 提出了他们囱己的想法，也就是在选择一个新满性时，并不仅仅计算该属性引起的信 4 华中科技大学硕士学位论文 怠增益，而是同时考虑树的两层节点，即选择该属性后，继续选择属性带来的信息增 益【刎；洪家荣等学者程分枝属性的选择上仍采用基于信息增益率的方法，但在树的扩 展过程中，采_ 拜l 属性聚突的方法减少瓣的分枝f 2 l 】；曲开社，成文藤，量俊红等学嚣在 i d 3 算法审弓l 入了用声趣度潋兔选择特征属经偏向子取饿较多静属饿冽。 还有学者为克服训练例子中派、反例的比例对互信息的影响，提出了i b l e 算 法【1 1 ，该雾法每次分枝时同时选一缀重要属性作为决策树的节点，结果预测高予i d 3 算法；菌夺谦等学者努璐奚径，蒸予粗糙集毽论，矮相对泛往的穰念狡造多交擞检 验，提出一种评价多变摄检验的准则吲，效聚优于i d 3 算法。这些算法从不同的侧 砸都强调了属性之间的相互关系，提高了决策树的效率。 逶避修改i d 3 算法两挺窭的l 潮递增式攀习算法l 硐，在每令貔改决策村带点 创建一系列表，每个蔽由未检测鞴性值和其涿例组成，溺处理新实例时，每个桶性 值的正例和反例递增计景；在i d 4 的基础上，u t g o f f 提出i d 5 算法【2 5 l ，它抛弃1 目的 检测属性下覆的子楗，从下殛选撵属性构造决策树等等。 此外，以徐爱琴等为代表的学者提出了蒺子神经礴络的分类决簸树构造i 2 1 ，该 方法通过神经网络训练建立各属性与分类结果之间的关系，进而通过提取各属性与 分类结果之阕的导数关系来建立分类决策树，同时为了提离神经网络所隐含关系的 提取效莱，提遗了关系强纯约泰静概念莠建簸了其俸的横鍪，并遴避实验证骥了算 法的有效憔。 把传统的决策树归纳学习算法与模糊集瑷论相结合，研究模糊化的归纳学习方 法，氇楚决策橱研究瓣一令薪静发震方彝，箕孛王黧照、瘸斌、唐斌、椽杰等学者 做了大量工作，发表了多篇关于模糊决策树艘论及应用的论文1 2 6 - 3 0 ，使在传统的归 纳学习中分类引起的误差，在引入模糊化方法后，显著减少。 在众多憋分类算法孛，决策树算法已经骞了广泛的廒震，劳篮悉经有了许多成 熟的系统。然而，针对不同特点的数据，决镱树技术仍然面临着各种挑战。不过， 从总体上来看待决策树的发展，可以说不管决策树应用程哪个领域，主要研究方向 还是一致的，下面的几个发展方囱1 3 l 删正是稳建决策树的过程中还勰特子我们旋解 决，完善的琢节，还需要迸一步研究的工作： ( 1 ) 离散化方法 离散饯是分类过稷中处理连续属性的一种有效技术 3 5 - 3 7 。很多的分类规则产生 系统只筑嶷瑾离教藩魏，毙如典型的i d 3 算法等。然嚣，缀多捶述现实应穰俸豹耩 5 华中科技大学硕士学位论文 性并非悬离散的，对手采用这些簿法的系统来说离散化怒个必不可少的步骤。即使 在c a 5 遂一能够处理连续属性的葬法中，也需要事先完成离散化这步骤。所以离 散化的效率、有效性囊按影响到艨续机器学溺算法的效率合性能。咆正因此，离散 纯方法的羧迸对予决策褥算法是一个重要静环节。特剃燕对遗现静越来越频繁的模 糊数据进行离散化而又不影响数据间的关系将会是研究徽点。 i ( 2 ) 降维方法研究 用予数豢分析瓣数据霉戆惫会数黻吾译戆条终属毪，每令条终瓣毪霹看佟一个 维数。这魃条件属性囊括了所有描述这些数据的属性，但是这些属饿中可能包禽着 大量与我们所指定的数据挖掘任务不相关的，冗余的，甚至有误导的属性。降维方 法，实际童是摆在不影响挖掘任务斡蘸提下，演除那些与挖掘任务无关愆属性，瑟 从原有的瘸性集合中选择一个( 栩对菜种评价准则) 鬣优属性子集的过程，这个属 性子集应幽保留原属性集合的全部或大部分的分类信息。如此，便可提高决策树的 预测糖度翱建树速度，以适应大规模的高维数据处理。 然两，怒要彻底清除冗余耩俊，帮是一磺困难丙赞时的任务，选择合适酌降维 方法有着很大的发展嶷间。通常需要组合多种技术来实现这一目标，如粗糙集瑗论 的测试属性约简方法就得到了广泛应用。 ) 鞴性选择标准研究 在建波决策树的过程中，如何选择条件属性作为根结点和内绐点处的分割属性 是整个决缝树算法的核心问题之一，也是影响决策树优劣的主要因豢。 售惑燠是信意毽谂孛矮子分糖不确定程发酶一静耋娶度量，它扶统诗学焦度褥 到描述一个给定问题所需的最小倍息量，从褥以所需信息量的多少来衡量不确定性 程度。基予信息熵的属性评价标准进行了比较并指出，i g 有种偏好较细划分的倾 定，两g 歉受4 偏好不均匀划分。 与上述这些基予信息论的属性选择有较大区别的是派威等学者提出的基予属性 相似度的测试属性选择方法。该方法最后被诋实在某些方面具有较高的准确率。 虽然在楚个决策树的研究过程中，这方蕊的研究届多，然而针对各种不阿的问 题翔褥选舞合逶酶属毪仍然是一个难蘧。嚣靛，在震毪选择标准方蕊的研究述辩有 余地。 ( 4 ) 镱树修剪方法研究 创建决策橱时会产生逶度拟会凌象，圭鬣楚垂手数撰噪声或援窥点，错误顼蕺 华中科技大学硕士学位论文 干扰属性的存在，使许多分枝反映的是训练数据中的异常，通常以此训练集生成的 决策树常常会包含错误信息。通过剪枝技术改善产生过拟合的决策树的性能。 现有的方法有前剪枝和后剪枝。前剪枝通过提前停止树的构造( 例如：通过决 定在给定结点上不再分割或划分训练样本的子集) 而对决策树剪枝。一旦停止，内 结点成为叶节点。后剪枝则是在已构造好的决策树上减去不适当的分枝。通过删除 节点的分枝，剪掉树结点，来简化复杂的决策树。也可以交叉使用前剪枝和后剪枝 技术，形成组合剪枝方式。后剪枝所需的计算比前剪枝多，但通常可以产生更好的 树。 文献【3 8 】中指出使用不同的属性选择度量产生的未剪枝的决策树的大小的显著 差异。同时还指出使用不同属性选择度量对于最终预测精度的影响小于后剪枝的程 度和方法的最终影响。但剪枝技术本身存在缺点，如前剪枝会降低决策树的预测精 度，而后剪枝在增加计算量的同时也有可能降低实用性。 随着技术的不断发展，技术的结合越来越受到人们关注。在决策树研究的过程 中，不少学者将其与其它的挖掘技术相结合。如：人工神经网络、粗集理论、统计 方法、遗传算法等。多种方法的结合可以改善单一方法的不足。 1 3 论文的主要内容 决策树方法是分类算法中一个重要的研究方向，在各行业特别是商业领域的应 用越来越广泛。然而随着数据量的不断增大、应用的不断深入与普及，对数据的分 类要求也越来越高。目前，还不存在某种算法能够适合于各种领域，因此针对不同 的应用领域可以选择不同的分类算法以提高分类精度与速率。 构建决策树的核心问题之一就是属性选择问题。如何在选择测试属性的过程中 能够避免大量的复杂运算而不失分类精度则成了众多决策树分类算法追求的目标。 为了从大量的数据记录中发现决策规则，找出真正影响决策的属性，减小决策 树的规模，引入了基于属性相似度的分类算法【3 9 】。该算法是根据相似性原理，以测 试属性和决策属性的相似度作为启发规则构建决策树的分类算法。 本文详细分析此算法的优缺点，并针对此分类算法的两个问题进行改进，改进 思路是：在属性选择时对属性相似度的计算稍做改变。如果一个属性取某个值的所 有记录都属于一个决策类型，则认为从该属性能直接判断类属性取值的能力较强， 应该在原相似度计算方法的基础之上提升该属性的相似度，从而选择相似度高的属 7 华中科技大学硕士学位论文 性作为测试属性；同时，在每分割一次数据集之后，都应对每一个数据子集重新计 算相似度，虽然以运行速度为代价，但是为了获得结构更好的数据库、更高的预测 精度，这种取舍还是值得一试的。 。 文中将改进后的算法应用于高校教师资源流失原因分析的系统设计中以验证改 进后的效率。同时将改进前的基于属性相似度的分类算法和著名的i d 3 算法分别应 用于高校教师资源流失原因分析系统中，从而可以根据这几种算法的挖掘结果比较 算法的优劣。最后，分析影响预测准确率的因素，以及新算法中还需要考虑的问题。 1 4 论文的组织结构 本文共分五个部分，各部分的内容组织如下： 第一章介绍课题的研究背景和意义、国内外研究现状、课题的主要研究工作 和论文的组织结构。 第二章简洁且全面地介绍数据分类的相关理论和技术，包括分类的基本技术， 决策树方法理论及常用的决策树算法等。对最有影响的决策树分类算法一i d 3 算法中 的核心思想进行详细的讨论和描述。对目前出现的决策树分类算法的扩展进行简单 的介绍。 第三章针对决策树算法中测试属性选择的确定，详细介绍基于属性相似度的 决策树分类算法，并提出改进措施。 第四章具体介绍高校教师流失原因分析系统的实现过程，并对挖掘结果进行 分析，最后验证算法的有效性。 第五章总结本论文的工作，并给出了今后工作的发展方向。 最后是致谢和参考文献。 8 华中科技大学硕士学位论文 2 分类中的决策树方法 2 1分类的相关概念和基本技术 分类是数据挖握中威用领域极其广泛的重骤技术之一，至今已经提瞧很多算法。 分类的露的怒：分拆输入数据，邋过在诩练集中的数据钵现出来的特性，为每一个 炎找到一种准确的描述域模型。这种描述常常用谓词表承。由此生成的类描述用来 对未来的测试数据进行分类。尽管这些未来的测试数据的类标签是未知的，我们仍 簿戮垂梵鬏溅这些薪数据掰满的类，只是该溅，瑟不能肯定。我髓邈露黻鑫此对数 据中的每一个类有更好的理解，也就是说，我们获得了这个类的知识。 2 。1 1 分类的过程 分类是掇摆数攒集的特点撺遗个分类器，利用分类器对未知类荆的样本赋予 淡别的一种技术。构造分类器的过獠一般分为训练和测试两个步骤。襁训练阶段， 分析训练数据集的特点，为每个类别产生一个对相应数据集的准确描述或模型。在 测试除段，嗣霜类别豹攥述或摸耋瓣测试遴行分类，测试蒺分类准确发。一觳寒说， 测试阶段的代价远远低予训练阶段。 第一步，训练阶段，也可以称为建模阶段。通过分析由属性描述的数据库元组构 成鳇数据集寒掏造模瑟。缓定每今露组属予一令蘸定义懿类。对手分类，数据露缀 也称为样本、实例或对稼，为建立模型而被分析的数据元组形成训练数据集。训练 数据集中的单个元组称为训练样本，并随机的从样本集中选取。由于预先知道每个 训练样本的类标号，这个建立模型的学习过程瘸子有指导的学习( 即模飕的学习程知 道每个训练样本属予哪个类的指导下进行) ，脊潮于聚类等死指导的学习。 通常，通过第一步的学习建立的模型用分类规则、决策树、决策表成公式等形式 袭示。例如；给定一个颁客基本信患的数据库，通过分类算法学习得成分类规则， 缀据这些筑辩，得出鬏客的薅买魏力的强与骶。瑟褥到静这些援翔就是分类模黧， 利用这个模激就可以为其他数据样本进行分类，同时也能对数据库的内容提供更好 的理解。 第二步，就是剩磁这些矮裂送行分类。崧大范围趣应用这些筑鬟l l 之前，痤攀先 对模型进行评估，以得别模型的预测准确率。常用方法是采用保持( h o l d o u t ) 方法，该 9 华中科技大学硕士学位论文 方法使用类标号样本测试集，这些样本随机选取，并且和训练样本集没有交集，即 测试样本集完全不同于训练样本集。模型在测试样本集上的准确率是指正确被模型 分类的测试样本的百分比。对于每个测试样本，按照分类模型学习得出的预测类与 已知的类标号比较，如果相同，则表示分类成功，不相同，则表示分类不成功。之 所以使用完全不同于训练样本集的测试样本集，是因为学习模型倾向于过分适合数 据，即是学习模型可能并入训练数据中某些特别的异常，而这些异常不出现在总体， 样本集中。如果仍使用训练数据评估分类模型，则可能评估总是乐观的。 如果认为模型的准确率可以接受，就可以利用这个模型对类标号未知的数据元组 或对象( 也称为“未知”数据) 进行分类。例如：通过分析现有顾客数据学习得到 的分类规则可以预测新的顾客的购买能力的大小。 2 1 2 分类数据的预处理 为了提高分类的准确性、有效性和可伸缩性，需要对分类所用的数据进行以下的 预处理。 数据清理：目的是消除或减少噪声数据以及处理空值。可采用平滑技术消除或减 少噪声数据；对于空值，可用该属性最常出现的值，或根据统计，用最可能的值代 替。尽管大部分的分类算法都有处理噪声和空缺值的机制，但经过清理的数据将更 有助于减少学习时的混乱。 相关性分析：数据中的许多属性可能与分类任务不相关。例如：记录银行贷款申 请是星期几提出的数据可能与申请成功不相关。此外，还可能有一些属性是冗余的， 如果包含这些属性将减慢或可能误导学习步骤。因此，可以进行相关分析，删除学 习过程中不相关的或冗余的属性。在机器学习中，这一过程称为特征选择。 理想情况下，用在相关分析上的时间，加上从压缩了的数据集上学习的时间，应 当少于在原来的数据集上学习所用的时间。这种分析就可以帮助提高分类的有效性 和可伸缩性。 数据变换：数据可以概化到较高层的概念。例如，对于连续值的属性，“收入” 的数字值可以概化到离散的区间，如“低，中，高”；类似地，对于离散值的属性， 如“街道”，可以概化到高层概念，如“城市”。由于概化压缩了原来的训练数据集， 从而可以减少学习的时间。数据也可以按某种规则进行规范化处理等。这些必要的 数据变换都将对分类是有用的。 1 0 华中科技大学硕士学位论文 2 1 3 分类方法的比较和评估标准 分类方法可以根据下列标准进行比较和评估； 1 预测准确度：预测准确度是用得最多的一种比较尺度，特别是对于预测型分 类任务，目前公认的方法是分层交叉验证法。 2 计算复杂度：计算复杂度依赖于具体的实现细节和硬件环境，在数据挖掘中， 由于操作对象是巨量的数据库，因此空间和时间的复杂度问题将是非常重要的一个 环节。 3 模型简洁度和可理解性：对于描述型的分类任务，模型描述越简洁并且越容 易理解则越受欢迎。例如，采用规则表示的分类器构造法比较有用，而神经网络方 法产生的结果就比较难以理解。 4 强壮性：这涉及对于数据集中噪声数据或空缺值的处理，在有噪声数据或空 缺值的情况下模型是否具有正确预测的能力。 5 可伸缩性：大部分的分类算法是内存驻留算法，通常假定数据量很小。对于 海量的数据，是否具有有效的构造模型的能力，即算法的可伸缩性是很重要的。 2 2 决策树方法概述 决策树技术( d e c i s i o nt r y ) 是用于分类和预测的主要技术，决策树学习是以实 例为基础的归纳学习算法，通过一组无次序、无规则的实例推理出决策树表示形式 的分类规则。决策树的顶层节点是树的根节点，每个分枝代表一个测试输出，每个 非叶节点表示一个属性的测试，每个叶节点代表一个类或一个类的分布阴。建立的树 型结构模型相对直观且易于理解，特别适合于处理各种分类问题。因此，决策树方 法的研究一直各受关注。 决策树数据分类操作通常有以下两个步骤： 第一步，根据给定的训练集，找到合适的映射函数h ：f - - c 的表示模型。 这一部通常称为模型训练阶段。 第二步，使用上一步训练完成的函数模型预测数据的类别，或利用该函数模型， 对数据集中的每一类数据进行描述，形成分类规则。 决策树采用自顶向下的递归方式，在决策树的内部节点进行属性值的比较并根据 不同的属性值判断从该节点向下的分支，在决策树的叶节点得到结论。所以从根到 叶节点的一条路径就对应着一条合取规则，整棵决策树就对应着一组析取表达式规 华中科技大学硕士学位论文 则。基于决策树的学习冀法在学潞过程孛不需要使霜者了髂缀多鬻豢嫘谈，哭蘩调 练例子能够用属性一绪论式的方式表达出来，就能使用该算法来学习。通常用来形 成分类器和预测模型，可以对未知数据进行分类或预测、数据预处理、数据挖掘等。 它逶零毯戆秀部分：楗懿生成和撵憋剪棱。 2 2 1 决策树生成算法 作为分类器，决策树是一棵有向、无环树。以二叉决簸树为例给出相关概念的描 述。撵孛静摄节点没蠢父节赢，缀有其链节淼有益只有令父节点；令节点霹良 有1 2 个或没有子节点。如果节点没有子节点，称其为叶节点( l e a fn o d e ) ：其他的 称为内部带点( i n t e r n a ln o d e ) 。每个叶节点都对应一个类标识符c 的值，每个内部 繁熹罄霹疯一令用予分裁数摆集的属性磁，拣为分割属女耋( s p n t t i n ga t t n b u t e ) ，鳃令 内部节点都有一个分韵刿断规则q j ( s p l i t t i n gp r e d i c a t e ) 。如果x i 是连续属性的，那 么q j 的形溅是x i x i ，其中x i 啜d o m ( x i ) ，x i 就是节点n 的分割点；如果x i 题离 敷属性，那么氆的形式x i e y i ，其中y i c d o m ( x i ) , y i 成毙节点n 魄分裁子集( s p l i t s u b s e 0 。带点n 的分割属性和分割规则组成了节点n 的分割标准( s p l i tc r i t e r i o n ) t t l 。 决策树分类器算法通常分为两个阶段：决策树构建和决策树修剪。图2 1 照通 用的t o p - d o w n 决策树梅建算法。 图2 1 采用分而治之的树构建算法 由算法可知，分割穷法c l 楚凌策撼的关键。根据舞法不霹，疆兹决策楗募法 1 2 华中科技大学硕士学位论文 可分为两类：基于信息论的方法和最小g i n i 指标方法，对应前者的算法有i d 3 ， c a 5 ，后者商c a r t 、s l i q 、s p r i n t 。 2 。2 。2 决繁簿掺剪 决策树嫩成后面临的问题是树的过度拟合( o v e r f i t t i n g ) ，特别是存在噪声数据或 不规范属性时更为突出，决策树的修剪就是对进度细化的模型进行调憋。目前决策 褥掺剪豹策略有三释；_ 蒺予代价簧杂度静修剪，悲麓修赘鞫m d l 修翦。 基于代价复杂度的修势使用了撇立的样本熊用于修剪，即与用树的构建过程巾使 用的样本集不同，成为修剪样本。在很多情况下，特别题当训练集很小时，更期望 将掰骞静徉本甄翔手瓣戆创建耨瓣酶掺剪。 将所有的训练样本都用于树的创建岛修剪， 精确度不是很高。 慧鼹算法是q u e a n 在1 9 8 7 年撼滋的 实验表明，该方法产生的树太大且有时 实际巾建鳇最多劳裁效果较好茨是m d l 修葵。m d l 滠理，类戗予m m l 原 理，早已成功应用予枫器学习，该方法主要用于归纳决策树。决策树生成后面临的 问题是树的过度细化，特别是存在噪声数据或不规范属性时更为突出，决策树的修 剪就是对过度细化的横熬进行调整。 2 3 常用决策树算法 决策树雾法发展封瑗在已经载褥了缀大鲍成续，矗瑷多释决镶树分类算法，包 括i d 3 、c 4 5 、c a r t 、s l i q 、s p r i n t , f 霹p u b l i c 。下面简单介绍一1 ：多种决策橱分 类算法的基本思想。 2 ，3 。1 1 1 3 3 簿法贪绍 i d 3 算法【1 , 4 0 , 4 1 1 是决策树构造中的经典算法，它是c m i n l a n 为了从数据归纳分类 模型而构造的算法。乱入了基于倍息论的方法，提出了用熵来测量个非叶节威信 感量大小的懋怒。 d 基本定义： 定义1 、若给定概率分布p 畔l ，p 2 ，p n