论文研究-基于决策树的医疗数据挖掘 .pdf-资料库

weixin_39841365-11561487-4744302543380247281.pdf-第1页.png

第1页 / 共6页

weixin_39841365-11561487-4744302543380247281.pdf-第2页.png

第2页 / 共6页

weixin_39841365-11561487-4744302543380247281.pdf-第3页.png

第3页 / 共6页

weixin_39841365-11561487-4744302543380247281.pdf-第4页.png

第4页 / 共6页

weixin_39841365-11561487-4744302543380247281.pdf-第5页.png

第5页 / 共6页

weixin_39841365-11561487-4744302543380247281.pdf-第6页.png

第6页 / 共6页

基于决策树的医疗数据挖掘 http://www.paper.edu.cn 胡瑞娟长春理工大学计算机学院，长春 (130000) E-mail：huruijuan01@126 .com 摘要：本文通过研究决策树的 ID3 算法，针对 ID3 算法的不足提出了决策树的修剪方法，利用决策树算法对乳腺疾病数据进行挖掘，使用 SQL Server 2005 数据挖掘工具，主要对乳腺癌复发情况进行预测。挖掘结果证明了决策树算法在医疗数据挖掘中的有效性，为医生提供了诊断帮助。关键词：数据挖掘；ID3 算法；决策树修剪；乳腺疾病中图分类号： 1．引言计算机信息管理系统在医疗机构的广泛应用，促进了医疗信息的数字化，医院数据库的信息容量不断地膨胀。这些宝贵的医疗信息资源对于疾病的诊断、治疗和医疗研究都是非常有价值的。如何对医疗数据库进行自动提升和处理，提供全面的、准确的诊断决策和保健措施，已成为促进医院发展、提高服务质量而必须解决的新问题。正是在这种背景下，医疗数据挖掘应运而生【1】。数据挖掘算法很多，有关联规则方法、决策树方法、聚类方法等。本文采用决策树方法对医院信息系统中285例乳腺疾病患者数据进行医疗数据挖掘。 2．基于决策树医疗数据挖掘根据决策树的基本原理建立决策树，由于 ID3 算法容易产生过度适合的问题，因此需要对决策树进行修剪。下面我们就围绕如何建立决策树并对其进行修剪做详细论述，同时给出数据源并对相应数据进行挖掘。 2.1 决策树基本原理决策树建树的基本原理可以用 ID3 算法【2】来说明。ID3 算法是决策树算法的代表，绝大多数决策树算法都是在它的基础上加以改进而实现的。它采用分治策略在决策树的构造过程中，在树的各个节点上利用特征属性的信息增益大小作为分枝属性选择的启发式函数，选择信息增益最大的特征作为分枝的属性。ID3 算法的描述如下：设 E=D1×D2×…×Dn 是 n 维有穷向量，其中 Dj 是有穷离散符号集，E 中的元素 e=< v1,v2,…,vn>是样本，vj∈Dj，j=1，2，…，n。设 PE 和 NE 分别是 E 的正样本集和反样本集，而且其中的样本数分别为 p 和 n。ID3 算法根据信息论的理论，基于以下两个假设： (1)在向量空间 E 上，一棵决策树对任意样本的分类概率同 E 中正样本和反样本的概率一致； (2)一棵决策树能对一样本作出正确判别所需的期望信息的比特数为： I(p,n)= − p + np ㏒ 2 p + np − n + np ㏒ 2 n + np (1) 如果以属性 A 作为决策树的根节点，A 具有 n 个值{u1,u2,…,un}，它将样本集 E 分成 v 个子集{E1,E2,…,En}。假设 Ei 中包含 pi 个正样本和 ni 个反样本，那么子集 Ei 所需的信息为 I(pi+ni)，以属性 A 为根节点所需要的期望信息为： -1-

i pI ( i + n i ) (2) http://www.paper.edu.cn E(A)= n n p +∑ i np + i 1 = 因此，以属性 A 为根节点的分类属性的信息增益为 Gain(A)=I(p,n)-E(A)。ID3 算法选择使 Gain(A)最大的属性作为该节点的分枝属性，对于决策树的每个节点使用这条原则，直到决策树建立完毕(每个节点中的样本都属于同一类或者所有的分类属性都用完)。ID3 的一个优点是它的建树时间和任务的困难度(如样本集样本个数，每个样本的属性个数，研究概念的复杂程度即决策树的节点数)呈线性递增关系，计算量相对较小。 2.2 决策树修剪 ID3 算法的一个突出的不足是容易产生过度适合的问题。由于训练样本集是用来建立样本属性与样本所属类别关系的全部信息，随着决策树建树的进行，后面各层节点上可用的样本会越来越少，这时，算法的结果会对训练数据分类效果非常好，而对测试数据的分类效果并不好，这时就会产生过度适合的问题。过度适合问题的解决办法是对决策树进行修剪。决策树修剪算法分为两类：（1）建树过程中修剪,方法是在决策树完全建立前终止生长，以避免过度适合问题的出现。（2）建树后修剪,其基本思想是首先完全建成整棵决策树，在建树过程中允许过度适合现象的出现，然后对决策树进行修剪，来消除过度适合的问题。使用前一种方法往往会丧失一些有用的结论,而这些结论往往在决策树完全建成以后才会被发现,而且,在确定何时终止决策树生长时遇到很大的问题,所以目前使用最多的是后一种方法。建树后修剪的算法分为两类：首先生成一组决策树,然后从中选择最佳决策树，这类算法以最小代价-复杂性修剪算法(Minimal Cost-Complexity Pruning)[3]为代表；再者直接对原来的决策树进行修剪，这类算法以减少分类错误修剪算法(Reduced Error Pruning)为代表。下面将分别介绍这两种算法。在最小代价-复杂性算法中，设 E(T)是决策树 T 对训练数据分类错误的样本数，C(T)是决策树的复杂度，即叶子节点数；另外设 α 为复杂性参数，那么定义代价-复杂性函数： Rα(T)=R(T)+αC(T)。作为决策树修剪效果时的度量函数。对于一定范围内的复杂性参数 α 的任一取值，对建成的决策树从下往上逐个节点进行修剪，若修剪后的代价复杂性参数 Rα(T) 的值降低，则修剪掉该节点；否则保留该节点，所有的节点修剪一遍后，得到一棵修剪后的决策树。对于最后得到对应各个 α 的决策树集合，利用测试样本集合选择分类效果最优的决策树。减少分类错误修剪算法，利用决策树对测试样本集分类效果作为决策树修剪效果的度量函数，其具体的修剪过程如下：对于每一个节点，对该节点样本进行类别统计，将该节点修剪为叶子节点，节点的类别取该节点大多数样本所属的类；然后利用测试样本集合判断修剪后的分类效果，并和修剪以前作比较，如果分类效果增高，则修剪掉该节点，否则不修剪。持续以上过程，直到整棵决策树修剪完毕。 -2-

http://www.paper.edu.cn 2.3 医疗数据挖掘的实现 1. 数据准备决策树算法主要是一种分类方法，它从数据中选出已经分好类的训练集，建立分类模型，对于没有分类的数据进行分类。同时决策树还可以用于预测。本文提取了病人年龄（age）、肿瘤大小（tumor-size）、受侵淋巴结数（inv-nodes）、有无结节冒（node-caps）、恶性肿瘤程度（deg-malig）、肿块位置（breast）、肿块所在象限（breast-quad）、是否放疗（irradiat）、是否复发（Class）共8个属性作为每个病例的属性，通过数据挖掘来建立肿瘤复发和其他属性的关系。使用SQL Server 2005建立的病例数据库表见图1。图 1 乳腺疾病病例数据表（片段） Fig1 data table for part of breast-cancers 将 285 个病例样本分为两类，随机抽取 180 个样本作为训练样本集，剩余 105 个样本作为测试样本集。用 ID3 算法建立决策树，建树的算法流程如下： (1)创建节点 N。 (2)如果属于该节点的样本都属于同一类 C，那么，返回 N 为一个分类结果为 C 的叶子节点。 (3)如果所有可用于分类的属性都已经用完，那么返回 N 为一个叶子节点，该节点的分类取值为所有样本隶属最多的类。 (4)如果(2)和(3)的情况不存在,那么利用最大信息增益方法，从属性列表中选择该节点的分类属性，将节点 N 标记为这个分类属性。 (5)对于每一个所选的分类属性的值 ai，生长出对应的子节点，计算属于各个子节点的样本数,如果某个子节点样本数 0，那么将其标记为叶子节点，分类值取其上级节点所有样本中隶属最多的类。 (6)对于每个非叶子节点,重复以上步骤，直到整个决策树建立完毕。决策树建立完毕以后，分别用最小代价-复杂性修剪算法和减少分类错误修剪算法对决策树进行修剪；然后分别利用训练样本和测试样本对修剪后的决策树进行分类准确率的计算。 -3-

http://www.paper.edu.cn 对修剪后最后得到的决策树，其中表达的知识可以用“If-Then”的形式来进行规则提取。每条规则可以沿着从决策树的根节点到叶节点的路径来获得，沿着一条给定路径遇到的属性及其取值的合集构成规则的先决条件(If 部分)，叶子节点给出类别的预测值，构成规则的结论部分(Then 部分)。 3．挖掘结果及分析使用 SQL Server 2005 数据挖掘工具[5]进行决策树算法的实现。选择 Class 为可预测的列，其他属性作为输入列，生成的挖掘模型如图 2。图 2 利用决策树的挖掘结果 Fig2 the results of DM based on Decision Tree 图 3 依赖关系图 Fig3 the relationship of dependences -4-

http://www.paper.edu.cn 图 4 挖掘结果准确性提升图图 5 挖掘图例 Fig4 veracity advance of the result of DM Fig5 cutline of DM 从挖掘结果图可以看出,决策树将受侵淋巴结数、肿块大小和肿瘤的恶性程度这些特征作为判定乳腺疾病是否复发的主要因素,这和临床的诊断是一致的。依赖关系图显示了所预测属性与其他属性的关系，可以通过改变链接的强弱来观察节点的依赖关系，受侵淋巴结数与肿瘤是否复发关系最强，另外肿瘤是否复发还与肿块大小以及恶性程度有关。利用决策树算法进行数据挖掘的准确率可以达到80%,接近甚至超过临床诊断的效果,这充分证明了决策树算法在乳腺疾病数据挖掘中的有效性。 4．总结本文通过对决策树 ID3 算法进行研究，针对算法的不足提出了决策树修剪方法，使用 SQL Server 2005 对 HIS 中乳腺疾病数据进行挖掘，得出了判定乳腺疾病是否复发的主要因素和临床诊断一致，挖掘的准确率到 80%，决策树算法在医疗数据挖掘中起到很大的作用。对医学数据库中的各种检验和检查数据进行分类和预测，得到医学诊断的各种规则，从而帮助医生对患者进行客观而有效的诊断。参考文献 [1] 邵峰晶,于忠清. 数据挖掘原理与算法[M]. 北京: 中国水利水电出版社, 2003:102～121. [2] 易静. 医院信息数据挖掘及实现技术的探索[D]. 重庆医科大学,2007 [3] Kantardzic M. Data Mining Concept、Models、Methods and Algorithms[J]. IEEE Press , 2002 [4] Markey MK, LoJY,Floyd CE Jr.differences between computer-aided diagnosis of breast masses and that of calcifications. Radiology[J], 2002,(223):489～493 [5] 朱德利. SQL Server 2005 数据挖掘与商业智能完全解决方案[M]. 北京: 电子工业出版社, 2007 [6] 强永乾,郭佑民,王秋萍.数据挖掘技术在临床医学中的应用[A].中国高等医学教育.2007,(4):64 ～68 -5-

Medical Data Mining Based on Decision Tree http://www.paper.edu.cn Department of Computer Science,ChangChun University of Science and Technology, ChangChun, Hu Ruijuan (130000) Abstract This paper studies on ID3 algorithm of decision tree. Because of ID3 algorithm’sdisadvantages, it brings forword pruning methods of decision tree. Based on decision tree, it provides us the data mining for breast-cancers. Using SQL Server 2005 data mining tools, it mainly predicts the situation of breast- cancer recurrences. The results of data mining shows that the decision tree algorithm in the medical data mining has effectiveness. It can provide help for diagnosis for doctors. Keywords: data mining; ID3 algorithm; pruning methods of decision tree; breast-cancer -6-

资料库

论文研究-基于决策树的医疗数据挖掘 .pdf

相关推荐

开发技术

热门标签

最新资料