（计算机应用技术专业论文）粗糙集与决策树算法用于冠心病分类研究.pdf

摘要 计算机辅助诊断冠心病是医学和计算机领域联合研究的热点问题，冠心病 病例作为数据的一种，其内部存在着大量的隐含信息。数据挖掘正是研究如何 从数据中寻找这些隐含的信息，并建立辅助决策的模型的方法。基于上述背景， 数据挖掘技术用于冠心病数据分析是有意义的。 分类是数据挖掘中一种主要的分析手段，它通过分析数据，建立分类模型， 生成分类规则，并用于分析新的数据。分类包括很多种方法如：决策树、关联 规则、贝叶斯、神经网络、遗传算法等。 本文以冠心病数据为研究对象，利用粗糙集和决策树( 具体为c 4 5 算法) 对其进行分类，深入研究这两种算法的具体执行过程、内部参数设计及所获得 的结果，比较两种算法对冠心病数据分析的适应度。 主要工作包括： 1 整理实验数据。 2 设计实验内容。 3 分类过程与结果比较。 通过研究，在对冠心病数据进行分类时，应用粗糙集和决策树算法取得了 两组不同的分类规则，结果如下： 1 使用c 4 5 决策树算法进行分类的准确率高于改进的粗糙集方法； 2 使用c 4 5 决策树获得的分类规则的数量多于改进的粗糙集方法； 3 c 4 5 决策树获得的规则的可读性更强。 关键词：决策树c 4 5 决策树粗糙集分类 a b s t r a c t c o m p u t e ra i d e dc o r o n a r yh e a r td i s e a s ed i a g n o s i sw a sac o n j u n c t i o ns t u d y p o i n ti nm e d i c a la n dc o m p u t e ra r e a c o r o n a r yh e a r td i s e a s ec a s e si sak i n do fd a t a t h a tc o n t a i n sh u g ea m o u n to fi m p l i c a t ei n f o r m a t i o n t h eo b j e c to fd a t am i n i n gi s m e t h o d sw h i c hs e a r c h i n gi m p l i c a t e di n f o r m a t i o nf r o md a t a ，a n de s t a b l i s h e sa i d e d d e c i s i o nm o d e l b a s e do nt h ea b o v eb a c k g r o u n d ，d a t am i n i n gu s e df o rc o r o n a r y h e a r td i s e a s ea n a l y s i sw a sm e a n i n g f u l c l a s s i f i c a t i o ni sam a i na n a l y s i sm e a ni nd a t am i n i n g i tc a ne s t a b l i s h c l a s s i f i c a t i o nm o d e la n dg e n e r a t e sc l a s s i f i c a t i o nr u l e sb ya n a l y z i n gd a t aa n dc a n b e u s e dt oa n a l y z en e wd a t a c l a s s i f i c a t i o ni n c l u d e sm a n yk i n d so fm e t h o d s ： d e c i s i o nt r e e ，a s s o c i a t i o nr u l e ，b a y e s ，n e u r a ln e t w o r k ，g e n e t i ca l g o r i t h ma n ds oo n t h ea n a l y s i so b j c o to ft h ep a p e rw a sag r o u po fc o r o n a r yh e a r td i s e a s ed a t a r o u g hs e ta n dd e c i s i o nt r e e ( c 4 5a l g o r i t h m ) w e r es e l e c t e da sa n a l y s i sm e t h o d s t h es t u d ym a i n l yf o c u s e do np r o c e s s i n gp r o c e d u r e ，p a r a m e t e r sd e s i g na n dr e s u l t s ， c o m p a r e dt h ef i t n e s so ft h et w oa l g o r i t h m so nc o r o n a r yh e a r td i s e a s e t h ep a p e rm a i n l yw o r k e do n ： 1 t r i m m e dc o r o n a r yh e a r td i s e a s ed a t a 2 d e s i g n e dc o n t e n t so fe x p e r i m e n t 3 c o m p a r e dc l a s s i f i c a t i o np r o c e d u r ea n dr e s u l t t h r o u g hs t u d y ，d i f f e r e n tc l a s s i f i c a t i o nr u l es e tw e r ea c q u i r e db yr o u g hs e t a n dc 4 5d e c i s i o nt r e e ： ， 1 t h ec l a s s i f i c a t i o na c c u r a c yr a t eo fc 4 5w a sh i g h e rt h a nt h a to fr o u g hs e t 2 t h en u m b e ro fr u l e sg o t t e nb yt h ec 4 5d e c i s i o nt r e ea l g o r i t h mw a sl a r g e rt h a n t h a to fr o u g hs e t 3 c 4 5r u l e sw e r em u c hr e a d a b l et h a nr o u g hs e tr u l e s k e yw o r d s ：d e c i s i o nt r e e c 4 5d e c i s i o nt r e e r o u g hs e t c l a s s i f i c a t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作和取得的研究成果，除了文中特别加以标注和致谢之处外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 天津理工大学或其他教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明 确的说明并表示了谢意。 学位论文作者签名：李穸 签字日期：加。7 年 月y 日 学位论文版权使用授权书 本学位论文作者完全了解天津理工大学有关保留、使用学位 论文的规定。特授权天盗理工大堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制 手段保存、汇编，以供查阅和借阅。同意学校向国家有关部门或机 构送交论文的复本和电子文件。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：季爹 签字日期：7 0 0 年月f 彦日 第一章引言 1 1 论文研究的背景及意义 第一章引言 分类o 。4 “，作为数据挖掘中的一种方法，可以作为辅助手段，通过分析数据，建立 分类模型，对新数据进行分类。提到分类，就要对于数据挖掘这一概念加以说明”。 分类只是数据挖掘众多方法中的一类，从技术的角度讨论数据挖掘的定义，可以分为狭 义、广义两种。 1 ) 从狭义上讲，数据挖掘仅仅指的是k d d ( k n o w l e d g ed i s c o v e r yo ft h ed a t a b a s e 知识发现，k d d 一词是在1 9 8 9 年8 月于美国底特律市召开的第一届k d d 国际学术会议上正 式形成的。) 中的一个步骤，即对转换后的数据进行建模分析，提取模式的过程。 2 ) 从广义上讲，数据挖掘不单指k d d 的一个步骤，它渗透到i ( d d 中的一些相关环节， 如：数据选择、数据变换以及模式评估等，因为这些环节的实施与数据挖掘所采用的算 法、模型是紧密相关的。从广义的观点给出数据挖掘的定义，即：数据挖掘就是从大量 的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们 事先不知道的、但又是潜在有用的信息和知识的过程叫。 利用数据挖掘技术，可以从大规模数据中提取有用信息，帮助决策者做出决定，制 订更加合理的计划，为企业和政府提供强有力的技术支持；协助专家，对于某一领域的 问题做出更加准确的判断，改变以往单纯依靠经验的作法；对某些无法精确推理的问题， 从已有的经验中找到某些规律，做出几种可能性的预测。 分类这一数据挖掘的技术本身，已经存在了大量的算法。用于不同的应用背景中 o ”1 1 2 , 1 3 。在冠心病数据处理领域，已经有了成功的案例，例如，利用神经网络方法，对 冠心病患者的数据进行训练分类嘲；利用小波变换方法，对冠心病患者的生理信号分析 并且分类处理。每种分类算法，处理不同的数据背景，其适应度不同。 使用不同的分类方法，应用于冠心病数据的分类，然后比较其结果，选择其中较为 适合的一种，作为分类此数据背景的方法，这一思路，正是本文的出发点。 本论文对于冠心病患者的数据加以整理，使用不同的分类方法，应用于这一特定背 景并且加以比较和总结，达到综合使用分类算法的目的，为使用多种分类方法处理同一 数据提供了一个新的例子。 1 2 相关内容简介 1 2 1 粗糙集 粗糙集“”1 ( r o u g hs e t ，r s ) 是波兰数学家z p a w l a k 在1 9 8 2 年提出的一种分析数据 第一章引言 的数学理论。z p a w l a k 本人后来又在1 9 9 1 年发表专著，对于这种理论在处理数据的方面， 进行了介绍汹】。w z i a r k o 于1 9 9 1 年汹1 ，k c i o s 和w p e d r y c z 、r s w i n i a r s k i 于1 9 9 8 年侧 分别发表了文章，针对数据挖掘，对于粗糙集进行了简要的总结”“。目前已经有租糙集 应用于特征规约和专家系统的案例，并且其经典的特征归约的算法已经提出啪4 4 “。 粗糙集用上、下近似集来解决不确定性问题“”。它从数据库中发现分类规则的基本 思想如下： 1 ) 用户提出发现任务。由用户指定数据库中某一个或多个属性作为分类的决策属 性，根据这些属性的不同取值，将数据库中数据分成不同的类别，发现任务就是生成这 些不同类别的判定规则。 2 ) 用粗糙集理论的规则发现算法，获取分类规则“9 。 关于粗糙集如何进行信息系统的划分，将在3 1 1 节粗糙集理论的概述中进行详细 的叙述。它的这种划分适用于具有模糊性的分类问题，这与模糊数学使用概率( 或归属 度) 来表示对于目标的分类结果是不同的。 粗糙集本身对于待分类数据的维数与数据量来说，是没有要求的，但是，在应用于 这一冠心病数据的过程当中，会遇到困难，其典型分类方法所遇到的问题如下所述： 1 ) 实验所使用的冠心病数据维数比较高，计算重要度这一步无法进行，即使采取 降低重要度要求的方法，也无法求出典型算法所需要的重要度。 2 ) 简化规则这一步，在应用于本实验所使用的数据时，将会遇到与重要度求取一 样的问题，从而无法正常进行。 针对以上问题，本文对于经典的粗糙集分类方法，进行了改进。目的在于，使经典 的粗糙集分类方法能够适用于这一冠心病数据，改进内容如下： 1 ) 对于求取各个条件属性的重要度的改进。 2 ) 获取规则并简化规则这一步骤的改进。 1 2 2 决策树算法简介 决策树算法是一种典型的分类方法。决策树概念，最早出现在c l s ( c o n c e p tl e a r n i n g s y s t e m ) 中【7 】。i d 3 算法是较早的决策树归纳算法，该算法在选择属性时利用了信息 增益的概念，算法的基础理论清晰【博】；决策树的每个分支都对应一个分类规则，因此产 生的分类规则易于理解；同时，分类速度较快，准确率较高。但是i d 3 算法也存在着许 多不足： 1 ) 不能够处理连续值属性； 2 ) 计算信息增益时偏向于选择取值较多的属性； 3 ) 对噪声较为敏感； 4 ) 在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法 的低效； 2 第一章引言 5 ) 只适合能够驻留于内存的数据集使用，当训练集大得无法在内存容纳时程序无 法运行 2 0 l 。 c 4 5 算法是早期的针对i d 3 算法的改进算法中的一种【1 9 】。由以上对i d 3 算法缺点 的叙述可以看出，i d 3 算法的主要缺陷是用信息增益作为分裂属性选择的标准时，有偏 向于取值较多的属性的缺点，而在某些情况下，这类属性可能不会提供太多有价值的信 息。“5 采用了信息增益比作为选择测试属性的标准，弥补了i d 3 的不足 1 7 , 1 9 】( 第二项) 。 除此以外，c 4 5 不仅可以处理离散值属性，还能处理连续值属性，并且能够对于不完整 数据进行处理0 5 1 。 使用c 4 5 算法，从决策树中抽取规则需要两个步骤：获得简单规则、精简规则属 性t 15 1 。 其他决策树分类方法，还有i d 3 的改进版i d 4 、i d 5 ，比i d 3 更早期的c a r t ，以及后 来提出的q u s e t ，p u b l i c 等等 2 3 , 7 4 , 2 5 , 2 6 , 2 7 1 。本文根据对决策树分类方法在理论上进行的 研究，选定c 4 5 决策树进行研究，原因如下： 1 ) c 4 5 决策树算法能够处理连续值属性，克服了计算信息增益时偏向于选择取值较 多的属性的个缺点，这是选择它的原因。另外，也与本实验所使用的冠心病数据，本身 的特点有关，因为在最初的数据获得过程中，部分属性值有缺失，这对于i d 3 算法来说 是很不利的，因而进一步选择了它的改进版本- - c 4 5 。 2 ) q u e s t 、p u b l i c 等算法，算法的复杂性( 这里主要就是对于分裂节点选择的计 算) 增加，分类数据、生成规则的时间增加，初期的实验结果并不理想，所以没有进一 步进行试验。 由此选定c 4 5 算法用于冠心病数据分类，以达到较为准确分类的目的。 1 3 本文主要工作 本文使用两种不同的分类方法，对冠心病样例数据进行训练，得出两套不同的判定 规则，并使用检测数据检测其分类效果，包括如下内容： 1 ) 整理实验数据。这是由实验数据本身的特点决定的。对待分类的训练数据进行整 理，包括原始数据的数字化、连续属性值的离散化、离散属性值划分域值、属性值缺失 数据的处理。 2 ) 设计实验内容。在已有的理论研究基础上，利用粗糙集和c 4 5 决策树算法对冠 心病数据进行分类，在应用过程中，对算法的规则获取步骤进行了必要的修改，使之适 用于冠心病数据。 3 ) 分类分类过程与结果比较。对已经获取的规则，在数据整理过程、获取规则及简 化规则过程、分类规则效果和可读性、分类条件属性，这四个方面进行了比较。 第二章待分类冠心病数据的前期处理 第二章待分类冠心病数据的前期处理 2 1 冠心病数据的获得与处理 本文的实验对象，是与冠心病有关的各项数据。这一冠心病数据，包含7 l 项条件属 性，l 项决策属性( 即该病例记录的病人是否患有冠心病) 。训练数据为1 3 9 9 个病人的 记录，检测数据为3 2 4 个病人的记录。预期的结果是使用改进过的粗糙集分类方法和 c 4 5 决策树分类算法产生分类规则，将未患冠心病的病人记录，与患冠心病的病人记录 区分开来。现将7 2 个属性的属性名列出如下： 表2 1 ：数据属性名称 t a b l e2 1 ：c a p t i o no f a t t r i b u t e 属性号属性名属性号属性名 1 性别 2 性格 3 年龄 4 疼痛性质 5 疼痛部位 6 疼痛时间 7 放射 8诱因体力过劳 9 诱因情绪激动 1 0 诱因大量饮酒 1 1 诱因过量吸烟 1 2 诱因饱餐后 1 3 诱因安静平卧 1 4 诱因其它 1 5 缓解方式休息 1 6 缓解方式汉化硝酸甘油 1 7 是否缓解 1 8 缓解方式其它 1 9 脉搏 2 0血压s 2 1 血压d 2 2 速率 2 3 节律 2 4 第3 ，4 心音 2 5 家族史高血压 2 6 家族史糖尿病 2 7 家族史猝死 2 8 家族史冠心病 2 9 个人吸烟史年数 3 0 个人吸烟史量 3 1 个人饮酒史年数 3 2 个人饮酒史量 3 3 个人史高血压年数 3 4个人史糖尿病年数 3 5 血糖 3 6 尿糖 3 7血脂 3 8 血脂t g 3 9血脂t c 4 0 血脂h d l 4 第二章待分类冠心病数据的前期处理 4 l血脂l d l4 2血脂a p o a 4 3血脂a p o b 4 4 血脂v l d l 4 5心肌酶c k4 6心肌酶c k m b 4 7心肌酶l d k 4 8 心肌酶g o t 4 9 尿酸 5 0 心电图s t 段水平压低 5 l心电图s t 段抬高 5 2 心电图q 卜q 2 5 3 心电图窦停博 5 4 心电图窦房阻滞 5 5心电图房室阻滞5 6心电图室内阻滞 5 7 心电图a f 5 8 心电图室早 5 9 u c g 超生心动l v 6 0u c g 超生心动l a 6 1 u c g 超生心动e f 6 2h o l t e rs t - t 改变 6 3h o l t e rq 波6 4 h o l t e r 窦房阻滞 6 5h o l t e r 窦停博 6 6 h o l t e r 房室阻滞 6 7 h o l t e r 室内阻滞 6 8a f 6 9 房早或房速 7 0 室早 7 1 陈旧型心肌梗塞诊断结果 ( 续表2 1 ) 在原始的数据获得过程中，数据的采样、取值直接由冠心病专家完成，并且划分了 取值区间，所以在此对后期整理过的属性值的意义、离散与连续性作出说明： 表2 2 ：属性说明 t a b l e2 2 ：t h ea t t r i b m e se x p l i c a t i o n 属性号 属性名取值类型取值的意义 1 性别离散1 ：男，一1 ：女 2 性格离散1 ：a 型，一1 ：b 型 年龄本身属于连续属性值，但是在实际的采 3 年龄离散样数据中，按照实际年龄取值后，划分了9 个不同的年龄段，成为离散数据 原始数据有不同的几个取值，此处将每种取 4疼痛性质离散 值为1 然后相加，结果作为最终的属性值 按照疼痛部位不同赋值，每个部位取值都为 5疼痛部位离散 1 ，然后相加 在实际的采样数据中，疼痛时问以秒为单位 6 疼痛时间连续计算后，划分为6 个不同的时间段，成为离 散数据，0 0 1 表示不疼痛 7 放射 离散每种取值为1 ，然后相加 第二章待分类冠心病数据的前期处理 ( 续表2 2 ) 安静平卧、视患者是否由此原因引起症状发作而取值取 8 1 4 离散 诱因其它值为一1 ，1 缓解方式视患者是否按时休息而取值实行：1 ，不实 1 5离散 休息 行：一l 缓解方式含视患者在含化硝酸甘油后是否有 1 6 离散 化硝酸甘油所缓解而取值实行：1 ，不实行：一l 视患者症状是否有所缓解而取值实行：1 ，不实 1 7 是否缓解 离散 行：- 1 缓解方式视其它的方式是否能够缓解患者症状而取值 1 8离散 其它实行：1 ，不实行：一1 按照脉搏跳动次数取值，但是在实际的采样数 1 9 脉搏连续据中，按照实际脉搏取值后，划分了7 个不同 值，成为离散数据 按照高压取值，但是在实际的采样数据中，按 2 0血压s 连续照实际血压s 取值后，划分了5 个不同值，成 为离散数据 按照低压取值，但是在实际的采样数据中，按 2 1血压d 连续照实际血压d 取值后，划分了6 个不同值，成 为离散数据 按照次数秒取值，但是在实际的采样数据中， 2 2 速率连续按照实际速率取值后，划分了6 个不同值，成 为离散数据 按照心跳是否有节律划分，取值意义：1 ：有节 2 3 节律离散 律，一1 ：无节律 家族史视高血压史的年数而取值，一定年数后( 具体 2 5离散 高血压年数由冠心病专家划定) 即取1 ，否则取一1 家族史视糖尿病的年数而取值，一定年数后( 具体年 2 6 离散 糖尿病数由冠心病专家划定) 即取1 ，否则取一1 个人吸烟史年数属于连续属性值，按照个人吸 个人吸烟史烟史年数取值，但是在实际的采样数据中，按 2 9 离散 年数照实际个人吸烟史年数取值后，划分了6 个不 同值，成为离散数据 个人吸烟史量属于连续属性值，按照支数取 3 0 个人吸烟量离散值，但是在实际的采样数据中，按照实际支数 取值后，划分了5 个不同值，成为离散数据 6 第二章待分类冠心病数据的前期处理 ( 续表2 2 ) 个人饮酒史本身属于连续属性值，按照个人 个人饮酒史饮酒年数取值，但是在实际的采样数据中， 3 1 离散 年数按照个人饮酒年数取值后，划分了8 个不同 l 值，成为离散数据 个人饮酒史量本身属于连续属性值，按照个 人饮酒两数取值，但是在实际的采样数据 3 2个人饮酒量 离散 中，按照个人饮酒两数取值后，划分了5 个 不同值，成为离散数据 个人史高血压年数本身属于连续属性值，按 个人史照个人史高血压年数取值，但是在实际的采 3 3 离散 高血压数年样数据中，按照个人史高血压年数取值后， 划分了6 个不同值，成为离散数据 个人史糖尿病年数本身属于连续属性值，按 个人史糖尿照个人史糖尿病年数取值，但是在实际的采 3 4 离散 病年数样数据中，按照个人史糖尿病年数取值后， 划分了5 个不同值，成为离散数据 3 5血糖离散 正常：1 ，增高：- i 心电图 5 2 离散每种取值为1 ，然后相加，划分为4 个值 q l q 2 心电图 5 3 离散按照有无此症状划分不同的取值 窦停博 心电图 5 4离散按照有无此症状划分不同的取值 窦房阻滞 心电图 5 5离散按照不同症状划分为4 个不同的取值 房室阻滞 5 7 心电图a f离散按照有无此症状划分不同的取值 5 8 心电图室早离散 按照有无此症状划分不同的取值 h o l t e r 6 2 离散 正常：1 ，异常：一1 s t - t 改变 h o l t e r 6 4 离散按照有无此症状划分不同的取值 窦房阻滞 h o l t e r 6 5离散按照有无此症状划分不同的取值 窦停博 第二章待分类冠心病数据的前期处理 ( 续表2 2 ) 6 6 h o l t e r 离散按照症状的不同划分为4 个不同的取值 房室阻滞 6 8a f 离散按照有无此症状划分不同的取值 6 9 房早或房速离散按照有无此症状划分不同的取值 7 0 室早离散按照症状的不同划分为6 个不同的取值 陈旧型 7 l 离散按照症状的不同划分为4 个不同的取值 心肌梗塞 按照病人不同的诊断结果划分为5 个不同的属 7 2 诊断结果离散 性值 上述，是对于属性的原始数据离散性，及其取值意义的描述，可见，在原始数据的 获得过程中，已将某些本身是连续值的属性值做了离散化处理，如年龄，本身是连续属性， 但是由冠心病专家划分了域值，使之成为离散属性。这样做，简化了分类算法对于数据 的处理。 2 2 数据处理中划分域值的作用 如上一节所述，冠心病患者的原始数据中，有很多检查数据本身是连续值。但是， 为了方便分类方法处理数据，由冠心病专家划分了不同的值域，从而实现了连续数据的 离散化。 其实，原始的数据所能够包含的信息较多，连续数据的离散化对数据处理也是有影 响的。在1 2 2 节中，曾经提到，c 4 5 决策树算法，是可以处理连续属性的，但是粗糙 集理论无法处理连续属性。本文使用处理过的冠心病患者的数据，而不是原始的患者检 查数据本身，正是考虑这一原因。 离散数据适合各种分类方法使用，但是，当离散数据本身的属性值较多时，将增加 分类的工作量，从而加大了获取规则的难度。这就是在原始的冠心病数据中，对本身已 经是离散数据的一些属性值，仍然划定值域的原因。 第三章基于租糙集方法的冠心病数据分类研究 第三章基于粗糙集方法的冠心病数据分类研究 粗糙集理论 3 1 1 粗糙集理论的概述 粗糙集理论的核心思想，是将信息系统表示为上近似集与下近似集对信息系统的划 分，信息系统定义如下： s = ( u ，a ，v ，f ) 其中，u ：是一个非空有限对象集合，即为各项记录( 元组) 组成的集合。 a ：是记录的属性集合，分为不相交的两个子集，决策属性与条件属性。 v ：是属性值的集合。 f ：是一个函数，即u x a ，它为每个对象的每个属性赋予了一个属性值，即任何一 个信息系统内的记录的任意属性，必然有一个属性值l 。5 ) 。 由信息系统的定义来看，粗糙集定义的信息系统就是一个关系型数据表。对这一信 息系统，粗糙集按照特定目标，将其分为下近似集，上近似集、边界线性区域，即完全 可以按照某一标准分类的记录集合、所有可能按照某一标准分类的记录集合、以及处于 这两者之间的记录集合。 基于这一思想，在对完整的记录集合( 即每一项记录的决策属性都有其确定的属性 值) 进行分类的时候，可以使用其对于下近似集合的划分，实现分类的目的。 3 1 2 粗糙集理论的规则获取步骤( 典型算法) 表3 1 ：规则获取步骤 t a b l e3 1 ：s t e p so f r u l e s a c q u i r e m e n t 9 第三章基于粗糙集方法的冠心病数据分类研究 序号步骤具体内容 1 ) 条件属性的等价集的计算。( 即对比各个元组( 记录) 的条件属性， 查找出条件属性取值完全相同的元组) 2 ) 决策属性的等价集的计算。( 按照决策属性取值分类各个元组) 3 ) 决策属性的各等价集的下近似集的计算。( 按照决策属性分类 等价集下近 后的元组，遍历条件属性等价集，完全被包含的条件属性等价集， l 似和依赖度 即划入决策属性的等价集) 4 ) 计算p o s ( c , d ) 和厂( c ，d ) 的计算 ( p o s ( c ，d ) 表示属性d ( 决策属性) 的划分中的等价集关于c ( 条件 属性) 的下近似集的并集，lp o s ( c , d ) i 表示该并集的元素个数。y 表 示由条件属性c 的取值能准确判断出属于某个决策属性d 的等价 集的对象所占整个对象集合中的比例，即表示条件属性c 能区分决 策属性等价集的能力) 。 1 ) 排除掉要计算重要度的属性，然后对剩余的条件属性进行分类， 各属性重要 完全相同的分为一类。 22 ) 计算各决策属性的各等价集的下近似集。 度的计算 3 ) 计算排除掉要计算重要度的属性后的p o s 和，。 4 ) 得出属性的重要度。 得出的属性重要度中肯定有重要度为o 的属性，去除掉这部分属 3简化数据表 性的属性值后，得出新的数据表。 等价集、上 4下近似集的 针对简化后的数据表分类出条件属性、决策属性的等价集。 计算 5 获取规则根据简化后的数据表中的决策属性，得出规则。 对于已经产生的，针对同一决策属性值的分类规则进行简化。即 将同一条件属性具有不同属性值的规则进行合并( 当然，其他属 6 规则简化 性的属性值是相同的) 。当某一属性的所有不同属性值都被合并 后，即产生一条新的分类规则。 7 规则整理 将规则归入集合中。 1 0 第三章基于租糙集方法的冠心病数据分类研究 3 2 典型的粗糙集理论获取分类规则时遇到的问题 3 2 1 计算各个属性的重要度时遇到的问题 从上文粗糙集的经典分类方法可以看出，经典分类方法的重要部分有两个步骤： ( 1 ) 计算各个属性的重要度； ( 2 ) 获取规则并简化规则； 以下举一个流感实例数据分类的例子，说明经典算法计算属性重要度的步骤。 下表为流感实例数据表，具体计算各个属性重要度的计算方法如下，如计算属性a 的重要度，步骤如下： 首先遍历元组的条件属性c ( b ，曲，找出其中的等价集。 然后寻找决策属性的各等价集的下近似集。 最后求出y ( c 一 口 ，d ) = 5 7 。因此属性a 的重要度即为2 7 ，不为0 ，属性a 不可 省略。 表3 2 ：流感数据 1 砌e 3 2 ：f l ud a t a c ( 条件属性)d ( 决策属性) 数据 头痛( a )肌肉痛( b )体温( c )流感( d ) e 1 是( 1 )是( 1 )正常( 0 )否( o ) e 7 否( o )否( o )高( 1 )是( 1 ) 由计算重要度这一步可以看出，一个属性的重要度即为去掉该属性后，造成决策属性取 值不同的元组，在分类的过程中，无法由其他条件属性来分类的元组数目。 但是，当处理的分类数据维数比较高的时候，我们很难完全按照这一步骤计算出各 个属性的重要度。本文的分析对象是冠心病数据，它具有7 1 个条件属性。在1 3 9 9 条记 录中，只有属性1 2 符合经典算法求取重要度的要求，即除去第1 2 个条件属性外其他条 件属性取值完全相同，而这两个记录的决策属性是不同的。 3 2 2 获取规则并简化规则所遇到的问题 就经典的粗糙集数据分类方法而言，产生规则的过程，其实就是寻找简化后的数据， 其条件、决策属性取值完全相同的记录组，其条件属性值所组成的交集即为分类规则。 而简化规则一步，其实质就是将找到的规则中，某属性的属性值不同的规则进行合并， 第三章基丁粗糙集方法的冠心病数据分类研究 合并的条件为：这些规则包含这一属性所有属性值，而规则的其他属性值完全相同，那 么这些规则即合并为同一条规则。其问题与求取属性重要度所遇到的问题一样，即处理 高维数据时，条件属性不符合经典算法合并训练数据项的要求。 3 3 粗糙集用于冠心病数据分类的改进 3 3 1 求取重要度问题的解决 已经指出，重要度的经典求取方法在处理高维数据的过程中是难以应用的。那么重 要度在求取的过程中究竟表示什么实际意义呢? 如前所述，一个属性的重要度，即为去掉 该属性后，造成原本决策属性取值不同的元组，无法由其他条件属性来分类的元组数目。 由于数据维数的增加，使得在去掉某一条件属性之后，其他条件属性值不完全相同， 那么也就无法完成各个属性重要度的计算。 在其他很多经典分类算法中，并不是直接去掉无关的条件属性，而是按照某些步骤 依次求出条件属性及特定条件属性值的重要度，然后开始建立分类规则。那么可以考虑， 在计算各条件属性重要度的过程中，从其实际意义出发，检测一个条件属性对于分类一 条记录本身所起到的作用。就这一改进而言，可以考虑一个条件属性的不同取值对不同 决策属性值的影响。决策属性值不同的记录，其对应条件属性值如果不同，那么这一属 性就对不同决策属性值的产生起到了作用，这种作用程度的大小，即可作为重要度的衡 量标准。 这样改进的另外一个作用，就是便于两种不同分类算法的相互比较。因为在c 4 5 决策树算法中，对每一个非叶子节点的分枝选择，就是对一个新的属性集合中重要度的 计算。 具体计算步骤如下： 第三章基于粗糙集方法的冠心病数据分类研究 图3 1 ：计算属性重要度步骤的流程图 f i 9 3 1 ：f l o w c h a r t o f a t t r i b u t ei m p o r t a n c e c o m p u t a t i o ns t e p s 3 3 2 获取并简化规则步骤的改进 由于求解重要度这部分的改进，必须使用重要度排序后的属性来获取规则并简化 之。在3 2 2 中已经指出，对第2 个重要的步骤一获取规则并简化规则，遇到的问题是由 于属性维数太大，在产生了规则后，很难按照经典的规则简化步骤来简化已经获得的规 则，这与重要度求取过程中遇到的困难很相似，即很难产生除了一个属性值不同外，其 他属性值完全相同的规则，那么简化将无法进行。 经典的粗糙集数据分类方法，其产生规则并且简化规则的思想，重要的在于简化规 则，而简化规则一步，其实质就是将找到的规则中，某属性的属性值不同的规则进行合 并，合并的条件为：这些规则包含这一属性所有属性值，而规则的其他属性值完全相同， 那么这些规则即合并为同一条规则。可见，其核心思想在于，找到对某一决策属性值而言， 产生这一决策属性值的时候，重要度不为0 的属性，某些值将起到分类的作用，而同一 属性的其他值没有起到作用。 困难在于，当属性增加到一定量的时候，很难产生一个属性的属性值不相同而其他 属性的属性值完全相同的记录，这在3 1 2 中已经阐述过了。 采用如下改进的步骤简化规则： 1 ) 首先在已经获得重要度的属性中，选出条件属性值不完全包含在这一记录集合( 决 策属性相同) 中的条件属性。即找到产生这一决策属性值的时候重要度比较高的属性中， 只有部分属性值起到了分类作用的条件属性。 2 ) 就这些属性的重要度排位，按照其属性值建立规则，分类训练数据。当训练数 据被完全分类时，即停止这一过程。如果没有完全分类，则在新的依条件属性值划分后 的训练数据集合中，重复这一步骤，即选择重要度排位次之的条件属性，继续分类。 需要说明一下，具体的求取过程相对于上述求取并简化规则的步骤来说有所改进， 这是针对数据集本身所做的一些变化，当然，其核心思想仍然如上所述。 具体步骤如下： 1 ) 在集合中，寻找属性重要度排位较为靠前的属性中，其条件属性值不完全包含在 这一记录集合中的条件属性。 2 ) 在这些选出的属性中，依次寻找出取某一属性值的记录个数最大的属性值。 3 ) 把取这些属性值的记录个数排序，个数最少的属性值即为分类规则的属性取值。 不同属性，记录个数相同的属性值，按照已有的重要度排序。 4 ) 按照排序后的属性的顺序，找出取某一属性值的记录个数最少的属性值，然后找 出同一属性，比取这一属性值的记录个数多的属性值，由少到多依次排序，直到所 有属性值取完为止。 5 ) 将取某一属性值的记录个数最大的属性值的属性中，取某一属性值的记录个数最 少的属性值，作为最初的分类规则的属性值，产生规则。 第四章基于c 4 5 决策数算法的冠心病数据分类研究 第四章基于c 4 5 决策树算法的冠心病数据分类研究 4 1c 4 5 决策树算法的原理 决策树学习是一种逼近离散值目标函数的方法，学习到的函数被表示为一棵树，并 能分解为由多个i f - t h e n 规则组成的规则集 4 1 。 决策树通过把实例从根结点划分到某个叶子结点来分类实例，叶子结点即为实例所 属的分类。树上的每一个结点说明了对实例的某个属性的测试，并且该结点的每一个后 继分支对应于该属性的一个可能值域。所生成的决策树形如图4 1 1 2 0 1 。 图4 1 ：决策树不葸图 f i g4 hs k e t c hm a po f d e c i s i o nt r e e 这里通过一个典型的决策树例子来说明。 例如：如果想根据天气知道周六上午是否合适打网球，条件为天气的三个方面，阴 晴、湿度、风力，最后得出的规则如下： i ( 阴晴= 晴天八湿度= j 下常) v ( 阴晴= 多云) v ( 阴晴= 下雨八风力= 较弱) = ( 适合)l 这个规则的意思是这样的，当天气状况如下时可以去打网球：晴天并且湿度正常、 或者多云时、或者下雨并且风力较弱时h 暑l 。 可见通过决策树代表实例属性值约束合取的析取式，即从根到叶节点的每一条路径 对应一组属性测试的合取，树本身对应这些合取的析取 4 1 。 决策树的分类过程可以简单总结如下： 1 ) 选取各个条件属性中重要的一个( 相对于某一决策属性值而言。不同的决策属性 值即意味着不同的分类目标，其条件属性的重要度排列也不同了) 作为根结点，也就是 开始的一个分类属性。 2 ) 由根结点的不同属性值产生出了不同的分枝，即将原始的训练数据分为几组具有 不同条件属性值的数据。在这几组具有不同条件属性值的训练数据中，选择其各自的新 的根结点，作为该组数据的分类依据。 3 ) 重复1 和2 的步骤，直到完全分类原始的训练数据，或者将原始的训练数据按照某 一标准分类达到一定程度，即停止继续分类。 随之而来的问题是，究竟哪一个属性在每一组数据( 包括最初的未分类数据、已经 1 4 第四章基于c 4 5 决策数算法的冠心病数据分类研究 按照上述步骤重复多次的数据) 中适于作为分类属性，这种选择标准有何利弊；生成的 最终规则是否会过度拟合其依赖的训练数据，是否有必要对已经生成的规则进行进一步 的简化；当最初的数据集合中出现某些属性的值缺失时如何处理；如果原始数据并非离 散数据，需要连续数据离散化时应该如何应付。这些问题将在下文中针对c 4 5 决策树算 法逐一作出回答。 c 4 5 决策树分类算法是j r q u i n l a i n 于1 9 9 3 年提出的针对i d 3 的改进算法。在引言 中已经叙述过，c 4 5 决策树分类算法采用了信息增益比作为选择测试属性的标准，弥补 了i d 3 的不足，信息增益比的概念将在4 3 1 节中详细的叙述。 对原始的训练数据，c 4 5 不仅可以处理离散值属性，还能处理连续值属性，并且能 够对不完整数据进行处理。当然，对原始数据连续属性离散化的过程已经在数据采集整 理的过程中完成了。 在实验过程中，不完整数据的处理并没有直接采用“5 决策树分类算法所使用的 整理过程，而是使用了一种较为简单的处理方法，4 2 节中有详细的叙述。 关于避免过度拟合的问题，c 4 5 决策树分类算法使用“规则后修剪”的变体，在4 4 节中，对c 4 5 的剪枝方法，及本实验的简化步骤加以说明。 4 2 训练样例属性值缺失处理的方法 在某些情况下，可供使用的数据可能缺少某些属性的值【4 】。这些情况有多种原因， 比如在医学领域，某些患者的检测结果并不全面，但是医生已经可以根据其某些特征确 诊其患病的情况，那么另外的检测结果就是多余的了。但是在使用决策树分类方法分类 数据时，这种数据缺失的情况将造成无法继续分类的结果。 处理缺失属性值的一种策略是赋给它某个结点的训练样例中该属性的最常见值。然 后使用这个估计值的训练样例就可以被现有的决策树学习算法使用了。m i n g e r s j 分析 了这个策略【4 】。第二种更为复杂的策略是为每个缺失的属性值赋一个可能的赋值概率。 假设a 是决策结点疗的最佳测试属性，此时样例瑚q 很多属性值缺失，那么使用这一方法 给缺失属性值的属性赋值过程是这样的： 根据结点n 的样例上爿的不同值的出现频率，这些概率可以再次被估计。例如，给定 一个布尔属1 生一，如果结点h 包含6 个已知彳= 1 和4 个4 = 0 的样例，那么4 ( x 户1 的概率是0 6 ， 爿( x ) = o 的概率是0 4 。于是，实例x 的6 0 被分配至u a = i 的分支，4 0 被分配到另一个分 支。在测试新样例的时候这一方法也可以用以处理缺失的属性。 本实验的缺失属性处理方法是采用第一种处理方法，即赋给缺失属性训练样例中该 属性最为常见的属性值。这样做的目的是简化的预处理数据的步骤。这种方法降低了复 杂度，减小了计算量，也是出于完成实验的时间限制的考虑。 第四章基于c a 5 决策数算法的冠心病数据分类研究 4 3 属性选择的度量标准 4 3 1 信息增益比率的概念 算法选择的是有助于分类实例的属性。那么衡量属性值的一个好的定量标准是什 么呢? 这里将定义一个统计属性，称为“信息增益”，用来衡量给定的属性区分训练样 例的能力。接着再给出信息增益比的概念。 为了精确地定义信息增益，先定义信息论中广泛使用的一个度量标准，称为熵 ( e n t r o p y ) ，它刻画了任意样例集的纯度。给定包含关于某个目标概念的正反样例的样例 集s ，那么s 相对这个布尔型分类的熵为： ( 4 1 ) 其中，尸+ 是在s 中正例的比例，p 是在s 中反例的比例。在有关熵的计算中定义0 l 0 9 2 0 为o 【4 1 。 信息论中熵的一种解释是，熵定义了要编码集合s 中任意成员( 即以均匀的概率 随机抽取出的一个成员) 的分类所需要的最少二进制位数。 讨论了目标分类是布尔型的情况下的熵。更一般的，如果目标属性具有c 个不同的 值，那么s 相对于c 个状态的分类的熵定义为： f e n t r o p y ( j ) - 一p ，l o g ：p ， ( 4 2 ) 其中，只是s 中属于类别f 的比例。请注意对数的底数仍然为2 ，原因是熵是以二进 制的个数来度量编码长度的【4 】。 已经有了熵作为衡量训练样例集合纯度的标准，现在可以定义属性分类训练数据 的能力的度量标准。这个标准被成为“信息增益”。简单地说，一个属性的信息增益就 是由于使用这个属性分割样例而导致地期望熵降低。更精确地说，一个属性a 相对样 例集合s 的信息增益g a i n 圆，4 ) 被定义为： 函郴，伊胁聊( 鼬- 。y , 篙寻咖( 对 ) ”( m i o i 其中，v a l u e s ( a ) 是属性a 所有可能值的集合，s ，是s 中属性a 的值为v 的子集( t g 就是，s v = j sj a o ) = v ，) 。 信息增益度量存在一个内在偏置，它偏袒具有较多值的属性。举一个极端的例子， 如果心脏病数据中有一个出生年月日的属性，那么，它在所有的属性中有最大的信息 增益，因为这个属性的属性值几乎完全不同，它本身就可以分类全部数据了。