决策树算法在临床诊断中的应用分析

TOC\o"1-5"\h\z摘 要Abstract引 言 11 数据挖掘技术论述 31.1数据挖掘的概念 3数据挖掘的流程 4常用的数据挖掘方法 6数据预处理 92.决策树分类算法分析 132」决策树算法论述 13\o"CurrentDocument"2」.1 基本概念 13决策树的生成与应用过程 14决策树模型的评估 16典型的决策树算法 17决策树剪枝算法 20决策树的大小 20剪枝算法选择的因素 212.3.3常见的后剪枝算法 21基于多策略的决策树剪枝算法 24算法的提出 24算法的思想 24算法描述 26实验结果对比分析 29决策树算法在临床诊断中的应用 354.1临床诊断与医学数据挖掘 35\o"CurrentDocument"4.1.1临床诊断 35医学数据的特点 35医学数据挖掘的基本过程 36医学数据挖掘的儿个问题 37数据挖掘算法应用流程 38数据的选择 39数据预处理 39仿真结果 42结论 48参考文献 50作者简历 52学位论文数据集 54计算机和数据库技术日益普及，并越来越广泛地应用到各个领域。数据库规模日益庞大，复杂度也不断增长，如何充分地利用这些资源，从大量的数据中获取有用的信息为亟待解决的问题。而正是基于这种需求，数据挖掘技术越来越多地应用到在各种领域。受益于高科技的发展，现代医学在各种前沿技术的应用研究过程屮得到了飞快的发展。在数据挖掘的方法上，决策树、遗传算法、粗糙集理论、人工神经网络、贝叶斯网络等数据挖掘方法都得到了广泛的应用。决策树作为一种提出较早的数据挖掘方法，其应用范围比较广，也延伸到了医学领域。FI前国内外有相当多的研究者在探讨决策树在医学工作屮的应用，它主要应用领域有：药学、临床诊断及预防医学等。本文所选取的研究课题是决策树方法在临床诊断中的应用。传统的临床诊断过程带有浓重的主观性，依赖于医学专家的临床经验，各个医生的意见有时很不一致。因此，其诊断准确性因人而异，存在一定程度的不确定性。此外，［矢学专家的临床经验属于一种个人行为，不便于学习和普遍推广。而决策树方法作为分类器的一种，在这一方面有较强的优势，它能够通过挖掘数据中的隐含的知识，最终获得诊断疾病的能力。决策树方法在临床诊断的应用，极大地减轻了医务人员对于历史数据分析以及获取潜在知识的工作负担，大大改善了传统医学的诊断方式，为医务人员提供了必要的决策支持和重要参考，为疾病分析和诊断的研究提供了强有力的工具。由于医学数据的多样性和复杂性，使得传统的数据挖掘模型难以满足医学数据多样化的特点，也缺乏基于需求的灵活性。不同的分析对象对应着不同类型的数据集，应该有针对性地釆取相应的策略，同时还要提供足够的灵活性，保证满足不同的应用场景，女n：保证分类的精确性的同时，提高结果的可理解性等，从而辅助医生进行诊断，提高诊断的效率，为广大患者造福。决策树在临床诊断中的应用研究主要包括两个方面：决策树算法的研究、决策树在临床诊断中的应用研究。算法为应用提供理论依据，应用以算法为基础。决策树算法在临床诊断的应用中还存在剪枝算法缺乏可控性等缺陷，本文围绕这些问题进行了详细分析和探讨，提出了算法的改进方案，并应用于具体的临床诊断实例中。本文的后续章节组织如下：第1章对数据挖掘技术进行论述。从数据挖掘的基本概念开始到数据挖掘的流程和方法，以及数据预处理技术。第2章对决策树算法进行分析，对该算法学习中可能遇见的各种问题进行分析,包括：决策树的生成步骤、模型的生成与评估、典型的决策树算法对比分析等。另外，对决策树的各种后剪枝算法进行了综合的比较，分析了它们各自的特点。第3章是本文研究的重点，针对常见的几种决策树算法生成的决策树模型的缺乏灵活性、可控性的缺点，提岀了一种基于多策略思想的参数灵活的剪枝算法模型,通过实验数据来对比分析，该算法在精度不会大幅下降的基础上，灵活性有了很大的提高，可以更好地应用于医学诊断数据挖掘。第4章也是本文研究的重点，论述了医学数据挖掘以及临床诊断的研究方法与现状。本文选取了心脏病数据集作为数据挖掘的对象，从数据的选取、数据预处理、决策树算法在医学诊断中应用流程，最后采用WEKA作为平台，对这一过程进行了仿真。1数据挖掘技术论述1.1 数据挖掘的概念随着数据库技术的不断发展及越来越广泛的应用，人们所拥有的信息数量急剧增加，导致了“信息膨胀，知识贫乏”山的尴尬局面。这是因为数据库系统虽然可以实现数据的录入、查询、统计等功能，却很难发现数据中隐含的关系和规则，无法从海量的数据中提取岀有用的信息，进而预测未来的发展趋势。于是，人们采用机器学习的方法来分析数据，挖掘大量数据背后隐藏着的重要信息，促成了数据挖掘(DataMining)技术的产牛和发展，实现了对数据库海量信息的更高层次的分析。比如应用在商业上，获得有利于商业运作、提高竞争力的信息。数据挖掘也常称为数据库中的知识发现(KnowledgeDiscoveryinDatabases)121,其定义是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取出隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。数据挖掘涉及多学科技术的集成，是信息产业应用前景广阔的交叉学科，包括数据库技术、统计学技术、数据可视化、机器学习、模式识别、神经网络、信息检索等。通过数据挖掘，可以从数据库提取隐含的知识、规律，并可以从不同角度进行观察和研究，发现的知识可以用于多种用途，常见的有：过程控制信息管理、决策、查询处理等。数据挖掘被信息界认为是数据库系统最重要的前沿之一，同吋它又是一项面向应用的研究，在医学领域内有很多潜在应用，如用于HIS系统中医疗费用数据的挖掘⑶。因此数据挖掘技术得到了学术界和各业界的广泛关注。数据挖掘概念提出到现在，各种技术得到了快速发展，涉及的应用领域日益广泛。近年来，数据挖掘的研究逐渐转向系统应用，注重多种技术的集成和发现策略，同吋与其他学科之间的相互渗透，更为医疗卫生事业的发展及医学科研工作提供了有力的武器，开辟了新的广阔前景。数据挖掘的目的不是要求发现具有普遍意义的真理，或者用于发现崭新的自然科学定理和数学公式。实际上，所有发现的知识都是有特定前提和约束条件，局限于特定领域的，同时还要能够易于被用户理解。以糖尿病为例，在发达地区的所挖掘出的知识，与欠发达地区相比必然存在着很大的不同。例如，糖尿病的发生与地区的经济发展水平、水土、环境、饮食习惯等等有着很大的关联。1.2数据挖掘的流程数据挖掘过程包括对问题的理解和提出、数据收集、数据处理、数据转换、数据挖掘、模式评估与分析等过程，以上的过程不是一次完成的，其屮某些步骤或者全过程可能要反复进行。原始数据选择 ►被选择后数据预处理 ►经预处理后的数据转换 ►转换后的数据挖掘 ►被抽取的数据分析 ►分析结果— A Ar问题提出「" 数据准备和预处理■r数据挖掘"r评估与分析厂图i.i数据挖掘流程Fig.1.1FlowofDataMining问题的提出进行数据挖掘之前，首先要理解数据和实际的业务问题，对目标作出定义，明确发现何种知识就成为整个过程中第一个阶段。在这个过程中，数据挖掘人员必须和领域专家以及最终用户紧密协作，一方面明确实际工作对数据挖掘的要求；另一方面通过对各种学习算法的对比进而确定可用的学习算法。后续的学习算法选择和数据集准备都是在此基础上进行的。数据准备和预处理数据选取的目的是确定发现任务的操作对象，即目标数据，是根据用户的需要从原始数据库屮抽取的一组数据。数据预处理一般可能包括消除噪声、推导计算缺值数据、消除重复记录、完成数据类型转换等。当数据挖掘的对象是数据仓库时，一般来说，数据预处理已经在生成数据仓库吋完成了。数据变换的主要目的是消减数据维数或降维，即从初始特征屮找出真正有用的特征以减少数据挖掘时要考虑的特征或变量个数。(3)数据挖掘数据挖掘阶段首先根据对问题的定义明确挖掘的任务或冃的，如分类、聚类、关联规则发现或序列模式发现等。确定了挖掘任务后，就要决定使用什么样的算法。选择实现算法有两个考虑因素：一是不同的数据有不同的特点，因此需要用与Z相关的算法來挖掘；二是用户或实际运行系统的要求，有的用户可能希望获取描述型的、容易理解的知识，采用规则表示的挖掘方法显然要好于神经网络Z类的方法，而有的用户只是希望获取预测准确度尽可能高的预测型知识，并不在意获取的知识是否易于理解。(4)评估与表示模式评估根据某种兴趣度度量，识别表示知识的真正有趣的模式。知识表示阶段使用可视化和知识表示技术，向用户提供挖掘的知识。数据挖掘阶段发现出來的模式，经过评估，可能存在冗余或无关的模式，这时需要将其剔除；也有可能模式不满足用户要求，这时则需要整个发现过程回退到前续阶段，如重新选取数据、采用新的数据变换方法、设定新的参数值，甚至换一种算法等等。另外，数据挖掘由于最终是面向人类用户的，因此可能要对发现的模式进行可视化，或者把结果转换为用户易懂的另一种表示，如把分类决策树转换为“if・・・then…”规则⑷。数据挖掘仅仅是整个过程中的一个步骤。数据挖掘质量的好坏有两个影响要素：一是所采用的数据挖掘技术的有效性，二是用于挖掘的数据的质量和数据量的大小。如果选择了错误的数据或不适当的属性，或对数据进行了不适当的转换，则挖掘的结果不会好的。挖掘过程是一个不断反馈的过程，比如，用户在进行挖掘过程中发现选择的数据不理想，或使用的挖掘技术产生与期望的结果不相符。这时需要重复前而的过程，甚至从头重新开始1.3常用的数据挖掘方法一般地，数据挖掘模型分为预测性模型和描述性模型。预测型模型利用己知结果对新的数据样木进行预测，它能够完成的数据挖掘任务包扌舌：分类、时间序列分析和预测等；描述型模型是对数据中的模式或关系进行识別，它能够完成的数据挖掘任务包括：聚类、关联规则和序列发现等。决策树决策树是应用最为广泛的一种模型，它提供了一种展示类似在什么条件下会得到什么值这类规则的方法。决策树是通过一系列规则对数据进行分类的过程⑸。采用决策树，可以将数据规则可视化，其输出结果也容易理解。决策树方法精确度比较高，不像神经网络那样不易理解，同时系统也不需要长时间的构造过程，因此比较常用。具体的内容本文会在后面的章节详细阐述。人工神经网络神经网络近年来越来越受到人们的关注，因为它为解决复杂度很大的问题提供了一种相对来说比较有效的简单方法。神经网络可以很容易地解决具有上百个参数的问题。神经网络常用于两类问题：分类和回归。神经网络是建立在可以自学习的数学模型的基础之上的。它可以对大量复杂的数据进行分析，并可以完成对人脑或其他计算机来说极为复杂的模式抽取及趋势分析。神经网络系统由一系列类似于人脑神经元一样的处理单元组成，称之为节点⑹。这些节点通过网络彼此互连，如果有数据输入，它们便可以进行确定数据模式的工作。神经网络在某些分类问题上确实具有比符号方法更好的表现，但是神经网络也有它的缺点，在用于应用于数据挖掘的过程中无法获取显式的规则。神经网络的知识获取过程类似于一个“黑盒”系统，通过神经网络模型得到的知识也是以权值形式存在的隐式知识，因此其结果难以为人所理解。在临床决策领域，一个没有推理过程和决策依据的结论是很难被医务人员所接受的。(3)贝叶斯网络贝叶斯分类基于贝叶斯定理，是统计学分类方法，可以预测类成员关系的可能性。通过对分类算法的比较发现，一种称作朴素贝叶斯分类的简单贝叶斯分类算法可以与决策树和神经网络算法相媲美。在应用于大型的数据库过程中，贝叶斯分类表现出高准确率和高速度。朴素贝叶斯分类假定一个展性值对给定的影响独立于其它的展性的值。这一假定称作条件独立性。贝叶斯信念网络是图形模型，能表达屈性之间的依赖。贝叶斯信念网络也可用于分类。Bayes网络是一个带有概率注释的有向无环图(Heckerman,1997)⑻。这个图模型能有效地表示大的变量集合的联合概率分布，从而适合用来分析大量变量之间的相互关系，利用Bayes公式的学习和推理功能，实现预测、分类等数据釆掘任务。因为关于变量组的贝叶斯网络表示了X的联合概率分布，所以，一旦网络及其参数确定，原则上可以用它来推断任何感兴趣的概率。Bayes网络也是一种适合处理不确定性知识问题的知识表示方法，因为它可以从部分概率中进行推导。构造Bayes网络需要进行网络结构和网络参数两部分的学习。为了建立贝叶斯网络，首先确定问题的变量组，接着通过对变量Z间条件独立性的分析，建立一个表示这些变量Z间的关系的有向无环图。最后需要对变量指派局部概率分布。在离散的情形，需要为每一个变量的各个父节点的状态指派一个分布。(4)聚类分析一般把学习算法分成有监督和无监督学习两种方式。主要区别是有没有类信息作为指导。聚类是典型的无导师学习算法，一般用于自动分类。聚类是按照某个特定标准，如通常是某种距离，把一个数据集分割成不同的类，使得类内相似性尽可能的大，同|］寸类间的区别性也尽可能的大。直观的说，最终形成的每个聚类，在空间上都是一个稠密的区域。聚类方法主要分为平面聚类和层次聚类。平面聚类方法通过优化一个评估函数把数据集分割成多个部分；分层聚类在不同层次上对数据进行分割，具有明显的层次性，算法的执行过程可以用一棵层次树来描述。进行平面聚类，一般用距离来度量对象之间的相似性，典型的是欧氏距离⑼。距离越大，则相似性越小，反之亦然。若用对象的平均值来表示聚类的中心，则可以用对象到中心的距离作为分类的标准，把对象分配到离它最近的一个聚类中去，由此而导出了最小方差标准。因此一般的基于距离的算法可以分成以下两个步骤：首先把每个对象，分配到距离最近的一个聚类或组中去，然后重新调整该类的中心。反复重复这两个步骤，直到没有对彖被重新分配，且满足判别函数为止。此类算法很多，最著名的是K.Means算法，它要求用户给定聚类数目k值，然后任意选取k个点作为类中心开始迭代，直到满足判别函数。层次聚类方法可以分为分治法和聚合法。后者把实例集合看作单独的类，自下而上地合并。前者则相反，开始整个的实例集作为一个类，逐渐分裂。层次聚类的度量两个类的标准常见的有取两个类之间最小的距离作为类距离，也有取平均距离和最长距离的。聚类方法具有广泛的应用，典型的如文档的聚类。但是由于聚类是无监督的学习方法，其所研究的数据没有类别标签，我们很难判断得到的聚类划分是否反映了事物的本质。(5)粗糙集理论在知识发现的研究中，一肓存在着信息的模糊性等问题，经典逻辑不足以解决这些不确定性问题。为此，人们提出了一些解决方法，包括统计方法、模糊集理论，但这些方法都有一些内在缺陷或限定范围。相对而言，粗糙集方法具备几个优点：算法简单、易于操作；不需要预先知道的额外信息。粗糙集理论作为一种刻划不完整性和不确定性的数学工具，能有效地分析和处理不精确、不一致、不完整等各种不完备信息，并从屮发现隐含的知识，揭示潜在的规律。因此，粗糙集在数据库中的知识发现领域也得到了广泛的应用⑼。粗糙集理论把知识看作是关于论域的划分，并引入代数学中的等价关系来讨论知识，并提岀了能够保持分类能力不变的情况下，最小属性集约简的概念。对许多大型系统而言，并不是要保留数据库表中的所有属性，而如果能将某些对不对分类能力产生影响的那些属性删除，则可以增强系统潜在知识的清晰度，大大提高数据挖掘的效率，为数据挖掘提供了一种新的方法和工具。粗糙集理论在数据挖掘上有以下几点应用：第一，由于关系型数据库的关系表可被看作是租糙集理论中的决策表，这给粗糙集方法的应用带来极大的方便；第二，现实世界中的规则有确定性的，也有不确定性的。从数据库中发现不确定性的知识，为粗糙集方法提供了用武之地。第三，从数据中发现异常，排除知识发现过程中的噪声干扰也是粗糙集方法的特长。第四，运用粗糙集方法得到的知识发现算法有利于并行执行，这可极大地提高发现效率。对于大规模数据库中的知识发现来说，这是求之不得的。数据挖掘中的其它技术，如神经网络方法，不能自动地选择合适的属性集，而利用粗糙集方法进行预处理，去掉多余属性，可提高发现效率，降低错误率。第六，粗糙集方法比模糊集方法或神经网络方法在得到的决策规则和推理过程方面更易于证实和检测。1.4数据预処理进行数据挖掘的数据来源往往来自多个异构数据源。这些数据源存在着很多问题，因此不能直接用于数据挖掘。低质量的数据将导致低质量的挖掘结果，“垃圾入，垃圾出”(Garbagein,Garbageout)l，0J很适合这种情况。比较常见的几个问题有：(1)数据不完整性

由于使用过程中人为因素所造成的影响，或者系统设计时存在的缺陷，等等都有可能造成缺少必需的数据而导致数据的不完整。(2)数据兀余性在数据库中存在两个或两个以上完全相同的描述的情况。因为数据来源于多个数据库或其他数据文件，这样在将它们的数据进行汇总时，很有可能存在数据的重复和信息的冗余现彖。比如同样一名患者，出现在两个数据库中。(3)数据不一致各个数据源的数据缺乏统一标准和定义，数据结构可能也有较大的差异，因此各系统间的数据存在较大的不一致性，往往不能直接拿来使用。比如在数据库A中按年龄存储，而数据库B中按出牛日期存储，当两个数据库合并时就涉及到统一转换的问题，否则将导致不一致性。数据清理数据变换数据归约2003-09-20数据清理数据变换数据归约2003-09-20图1.3数据预处理的方法Fig.1.3MethodsofDataPreprocessing如果进行挖掘的算法是基于这些脏数据的，那么挖掘效果会受到噪声的干扰而产生偏差。因此釆用数据预处理技术能够使得对数据的挖掘过程更加有效、更加容易。数据预处理技术有很多。数据集成将数据由多个源合并成一致的数据存储；数据清理可以去掉数据中的噪声，纠正不一致；数据归约可以通过聚类、删除冗余特性或聚类等方法来压缩数据。这些数据处理技术在数据挖掘Z前使用，可以大大提高数据挖掘模式的质量，降低实际挖掘所需要的|］寸间。(1)数据集成通常來讲，数据挖掘的数据源往往来白多个不同的数据库或文件，必须将这些分散的数据进行集成，以便获得一个具有统一格式的数据集，从而方便对数据进行处理和挖掘。在进行数据集成过程中，会涉及到几个问题：首先是模式集成，即从多个异构数据库、文件或遗留系统提取并集成数据，解决语义二义性，统一不同格式的数据,消除冗余、重复存放数据的现象。通常借助于数据库或数据仓库的元数据进行模式识别，帮助避免模式集成中的错误。此外，数据可能来自多个实际系统，因而存在异构数据的转换问题和数据类型的选择问题。其次，对于冗余的处理。数据集成往往导致数据冗余，如同一属性多次出现、同一属性命名不一致等。对于属性间冗余可以用相关分析检测到，然后将其删除⑴】。另外，对于数据值冲突的检测与处理。由于表示、比例、编码等的不同，现实世界中的同一实体，在不同数据源中的属性值可能不同。这种数据语义上的歧异性是数据集成的最大难点。(2)数据清理数据清理可以去掉数据中的噪声，纠正不一致，是数据挖掘必要步骤。数据清理例程通过填写缺失的值、光滑噪声数据、识别或删除离群点并解决不一致性来“清理”数据。如果用户认为数据是脏的，则他们不会相信这些数据的挖掘结果。下面逐一说明数据清理采用的方法。空缺值处理：如果一个数据集得空缺值的比例比较小，那么删除含空值的数据记录不失为一种有效的方法。但是当比例过大时，如仍采用直接删除方法，将大大减少数据集中的记录，可能会导致丢失大量的信息，影响最终挖掘的结果。因此，空值也是数据清洗的一项重要内容。一般对于缺失值的处理方法包括：均值替代法、专家经验法、回归分析法、数据挖掘法等等。具体采用哪种方法，要根据数据集的特点。非法值处理：原始数据中的数据项有的是有一定的区间范围的，不在此区间范围的数据都视为菲法数据。如果直接将这些数据做为数据挖掘的输入，会大大的影响数据挖掘的结果和效率，因此，也要对这一部分数据去做预处理。不一致数据处理：原始数据中除了缺失数据外，还存在一些不一致的数据。同一意义的属性字段同一记录的值，在不同的数据文件中记录的数值却有可能不一致。对于这种情况可以引用其他材料进行人工纠正，但对于海量数据而言，这种方式就不适用了。另一种方式是采用算法挖掘出属性字段之间的函数依赖，进而查找出违反规则的值。如数据库A中某患者的年龄为18岁，数据库B中该患者为48岁，同时该患者患有非胰岛素依赖型糖尿病，那么可以推断数据库B中的年龄信息更可靠。数据变换数据变化将数据转换成统一的格式，以适合数据挖掘。通常包括：通过平滑处理去掉数据中的噪声；通过聚类数据概化来对数据进行汇总和聚集，用来为多粒度数据分析构造数据立方体；通过规范化将屈性数据按比例缩放，使之落入一个小的特定区间等等。数据归约如果直接对数据的所有属性进行分析和挖掘的话，数据量将是非常之大的。特别是对海量数据，数据分析和挖掘将花费很长的时间，使得这种分析是不现实或者不可行的。而数据归约技术能在接近于保持原数据的完整性的基础上，通过删除不相关的展性来减少数据量，得到数据集的归约表示，它比原始数据集要小的多I⑶。从而大大降低了分析和挖掘的时间，并能产生几乎相同的分析结果。2.决策树分类算法分析决策树算法论述基本概念本文研究的内容属于分类模型的范畴。分类在数据挖掘中是一项非常重要的任务，目前在商业中应用最多。分类的目的是学会一个分类函数或分类模型。该模型能把数据库中的数据映射到给定类别中的某一个。分类和冋归都可用于预测。预测的目的是从利用历史数据记录中自动推导出给定数据的推广描述，从而能对未来数据进行预测。要构造分类器，需要有一个训练样本数据集作为输入。训练样本数据集亦称训练集，是一条条数据记录组成的。每一条记录包含若干条属性，组成一个特征向量。训练集的每条记录还有一个特定的类标签与之对应，该类标签是系统的输入，通常是以往的一些经验数据。分类的目的是：分析输入数据，通过在训练集中的数捌本现出来的特性，为每一个类找到一种准确的描述或模型。这种描述常常用谓词表示。由此生成的类描述用来对未来的测试数据进行分类。尽管这些未来的测试数据的类标签是未知的，仍可以由此预测这些新数据所属的类。我们也可以由此对数据中的每一个类有更好的理解。在进行数据挖掘时可采用许多不同的方法，例如神经网络、决策树、遗传算法和可视化技术等，同时同一方法下又有数以百计的派生方法。决策树方法自20世纪60年代以来，在分类、预测、规则提取等领域有着广泛应用。特别是在Quinlan⑸于1986年提出ID3算法以后，在机器学习、知识发现领域得到了进一步应用及巨大的发展。现在很多公司的数据挖掘产品中都采用了决策树数据挖掘算法，J.R.Quinlan对决策树算法作岀了详细的理论描述。决策树算法中一种广为人知的算法就是ID3算法，是1986年由Quinlan提出的一种基于信息埔的决策树算法，近年来在很多知识发现领域得到应用，很多学者针对ID3算法进行研究与改进。生成一棵决策树是从数据中生成分类模型的一个非常有效的方法，相对于其他分类方法，其独特的优点包括：学习过程中使用者不需要了解很多背景知识，只要训练事例能够用属性一一结论的方式表达出来，就能用该算法进行学习；决策树的训练时间相对较少，其他的分类方法如神经网络，即使对小数据集也要花费很多的训练时间；决策树的分类模型是树状结构，简单直观，比较符合人类的理解方式；可以将决策树屮到达每个叶节点的路径转换为If-Then形式的分类规则，这种形式更有利于理解；决策树方法具有较高的分类精确度。决策树是一树状结构，它的每一个树结点可以是叶结点，对应着某一类，也可以对应着一个划分，将该结点对应的样木集划分成若干个子集，每一个子集对应一个结点。对一个分类问题或规则学习问题，决策树的生成是一个从上而下、分而治之的过程。分类的目标是通过分析训练集中的数据，对类进行准确的描述或者建立模型，然后用它对数据库中的其他数据分类或者上升为分类规则。2.1.2决策树的生成与应用过程下面是构造决策树的一般性的描述：开始时是一个训练集和空树，接下去对当前节点应用该节点的测试将其划分。如果所有的当前节点的训练样木属于同一个类别，创建一个带有该类的分类信息的叶子节点并停止。否则，使用最优测量计算每一个集合的每一个可能的划分。选择最优划分作为当前节点的测试。创建与该划分的不同输出数同样多的子节点。使用该划分的输出标注父亲和儿子之间的边并使用该划分把训练数据划分到子节点中。把子节点作为当前节点，循环进行(2)-(5)步骤，直到不存在可以划分的节点为止。

图2」决策树生成与应用过程Fig.2.1ProcessofDecisionTreeBuildingandApplication建造好决策树以后，就要使用决策树对新的事例进行分类。分类是根据一个事例的属性值计算它的类标签。一个事例计算它的类标签是将其从树的根节点开始通过整个树。该事例从根节点开始，相继通过内部节点，最终到达某个叶子节点。在每一个内部节点中，节点中的测试对事例进行测试，其结果决定了该事例要通过哪一个分支到达下面哪一个节点［川。该事例的类就是最终叶子节点的类。如果分类结果和事例所应属于的类不一致，那么该树对该事例分类出错。决策树正确的分类的比例被称做正确率，相反错误分类的事例的比率称作错误率。在决策树的建立过程中，另一个重要的问题是树的精确性和复杂度之间要取得一定的衡。一种方法是反复的对模式进行简单化直到树的精确性和复杂度达到所需的平衡。这种方法是使训练数据保持一定，而不停的对模式进行调整。另一种方法是同吋调整模式和训练集。这种方法先建立一个模式，然后删除一些样本，使模式的在训练集上的自我评估能够最大的提高。这两步交替执行直到达到预期的标准。这个过程称之为Esteem(EliminationOfSuspieiousTrainingExampleswithErrorontheModel)[12]o决策树学习采用自顶向下的递归方式，在决策树的内部结点进行属性值的比较，并根据不同的属性值判断从该结点向下的分支，在决策树的叶结点得到结论。所以从根到叶结点的一条路径就对应着一条合取规则，整个决策树就对应着一组析取表达式规则。2.1.3决策树模型的评估准确性该指标描述分类模型准确预测新的或未知的数据类的能力。预测准确性是决策人员最关心的问题，对于他们来说，之所以采用分类发现模型的原因在于:分类发现模型可以在巨量数据中，按照用户的使用要求处理数据，对数据进行分类，从中找寻有用信息。经分类发现模型处理后，从数据中得到的信息的准确程度不同在很大程度上将会影响决策人员的决策制定的准确性。鲁棒性鲁棒性是对模型预测准确性的一个补充，是在存在噪声及数据缺损的情况下，准确对求知其类的数据进行分类的能力。正如前面所提到的，数据挖掘处理的对象是大量的数据，而这些数据又常常存在不完整的情况，数据缺损、噪声数据以及冗余数据等情况是普遍存在的，在这种情况下，就要求所建立的模型对这些情况有充分的适应能力。可理解性这是针对分类发现模型对问题的描述方式以及该描述方式的可理解水平提出的。分类发现模型的最终目的是方便决策人员的使用，所以，对于决策人员来说，模型描述越简洁，也就越易于理解，同吋也就越受欢迎。例如采用规则表示的分类器构造法所提供的分类模型的描述方式就比较简洁、易于理解；而神经网络方法产生的描述结果相对来说就难以理解，从而使其更进一步的广泛应用受到限制。计算复杂性计算复杂性依赖于具体的实现细节，在数据挖掘中，由于某种操作对象是巨量的数据库，因此空间和时间的复杂性问题将是非常重要的一个环节，将直接影响生成与使用模型的计算成本。(5)可规模性可规模性是指在海量数据的情况下，构造模型的能力以及构造分类模型的精确度。数据挖掘所处理的对象数量是巨大的，那么就要求所构建的挖掘模型可以适用于各种不同规模的数据量情况。一些经典的决策树模型就不能很好地处理大规模数据，比如：ID3,它要求必须一次性地把所有数据载入内存中，这对于大规模数据来说是不现实的。而SPRINT算法则能够很好地处理这类问题。2.2典型的决策树算法(1)ID3算法ID3算法是1986年由Quiulna提出的一种基于信息嫡的决策树学习算法［⑶，他把香农的信息论引入到了决策树算法中，并构造决策树来预测如何由测试属性对整个实例空间进行划分。ID3对CLS进行了改进，提出了以信息嫡下降速度作为选取测试属性的标准，并增加了窗口技术。ID3算法的基本步骤：A・选出整个训练实例集T的窗口规模为w的随机子集Ti；以信息嫡下降的速度做为每次的测试属性标准，形成当前窗口的决策树；顺序处理所有训练实例，找出当前决策树的例外，如果没有例外则训练结束；组合当前窗口的一些训练实例与某些在C屮找到的例外形成新的窗口，返MBo虽然ID3算法得到了广泛的应用，但它仍然存在着很多不足。其主要存在的问题有：在数据存在较多噪声的情况下，效果比较差；并不能排除出现重复子树的可能性；由于构造的是单变量决策树，忽略了属性间的相互关系；其信息增益的计算倾向于选择那些取值较多的属性，存在种类偏见问题；虽然也能处理非离散的属性，但效果并不理想。C.45算法C4.5算法是ID3算法的改进⑺。它在ID3算法的基础上增加了对连续属性、缺省属性的处理，使用后修剪技术避免树的不平衡、交叉验证等。C4.5在每一个结点通过使用测试评估函数选取具有最大函数值的测试作为最优测试來划分该结点。C4.5使用两种测试评估函数，分别为信息增益函数和信息增益率函数。信息增益率函数的定义如下：这种算法利用比较各个描述性属性的Gain值的大小，来选择Gain值最大的属性进行分类。对于连续型的描述性属性，采取离散化的方式，其具体方法是：A、 寻找该连续型属性的最小值，并把它赋值给Min,寻找该连续型属性的最大值，并把它赋值Max；B、 设置区间(min,max)中的N个等分断点Ai，它们是Ai=Min+(max-min)/nXi,其中，i二1,2,…，NC、 分别计算把［Min,Ai］和(Ai,Max］(i=l,2,…，N)作为区间值时的Gain(A)=I(p,n)-E(A)值，并进行比较；D、 选取Gain值最大的从作为该连续型属性的断点，把属性值设置为［Min,A订和(Ar,max］两个区间值o生成决策树是C4.5算法的第一阶段，下一个阶段是剪枝。C4.5算法采用EBP剪枝算法对决策树进行剪枝，通过随机计算每个节点的分类错误率，来决定剪枝策略。非叶节点的分类错误为它的各个子节点的分类错误之和，叶节点的分类错误为该节点中不屈于该节点所表示类别的样本的取值之和。如果该子树的分类错误大于将该子树剪枝为叶节点后的分类错误，则将该子树剪枝为叶节点，并用该子树中多数实例所表示的类来标识。相对于ID3算法，C4.5算法在功能上有了很大的提高，不仅可以直接处理连续型属性，还可以允许训练样本集中出现属性空缺的样本。生成的决策树的分支也比较少。CART算法CART(ClassificationandRegressionTree)算法是是由LeoBreiman,JeromeFriedman,RichardOlshen和CharlesStone于1984年提出的一种数据勘测和预测算法［⑹，可以处理高度倾斜或多态的数值型数据，也可以处理顺序或无序的类属性数据。CART算法生成的决策树是结构简单的二叉树，容易为人理解和解释。因为它采用一种二分递归分割的技术，使得牛成的决策树的每个非叶节点都有两个分支。算法按照使得生成的两个孩子节点的平均纯度最大的原则选取最优的划分，最常用的分割算法是Gini算法和Twoing算法。在Gini算法中，CART选择具有最小Gini系数值的属性作为测试属性，Gini值越小，样本的“纯净度”越高，划分效果越好。CART的剪枝算法使用独立于训练样木集的剪枝样木集，比较剪枝前后分类错误的变化再决定剪枝策略。如果样本数太少而不能分出独立的剪枝样本集，它采用一种交叉验证的方法，将原始训练样本集分成n份，每次取第i作为测试样本集，其余的份作为训练样本，如此迭代直到n份样木集都做了一次测试集。这样总共得到n棵决策树，以此类推，直到n份样本集都做了一次测试集为止。这样总共得到n棵局部决策树，综合这n棵局部决策树形成全局决策树。这样形成的全局决策树在性能上非常近似于由包含所有样本的原始训练样本集得出的决策树。SLIQ算法如果数据量巨大，无法全部装入内存时，那么上述的几种算法将无法解决这个问题。而SLIQ算法是IBM于1996年提出的一种高速可伸缩的数据挖掘分类算法f,81o它通过预排序技术，高速准确地生成决策树，来着重解决这个问题。该算法利用三种数据结构来构造树，分别是属性表、类表和类直方图，其屮属性表含有两个字段：样本类别和样本所属叶节点。类表可以随吋指示样本所属的划分，所以必须长驻内存；每个属性都有一张属性表，可以驻留磁盘；类直方图附属在叶节点上，用来描述节点上某个属性的类别分布。通过这种数据结构有利于树的构造，同时能处理离散字段和连续字段。SPRINT算法SPRINT(ScalablePrarallelizableInductionofClassificaTree)算法是对SLIQ算法的改进，采取传统的深度优先生成树的策略，其着核心在两个方面：一是更好的并行建立决策树；二是真正地消除了所有的内存限制，使其适合更大规模的数据集。SPRINT算法吸取了SLIQ算法的预排序技术，但它使用不同的数据结构，分别是属性表和直方图，进一步增强了可伸缩性。该算法在设计中兼顾了并行处理，允许多个处理器相互合作生成一致的模型。它所采用与SLIQ相同的剪枝算法。2.3决策树剪枝算法2.3.1决策树的大小在生成决策树吋，可能使得产生的决策树非常庞大，对应的分类规则也难以理解。导致这种结果的原因是多样的：首先不恰当的描述方式不能精确的建立目标概念模型，当用这种描述方式吋，目标模型非常复杂。相反，运用得当的描述将人大降低模型的复杂程度。因此在树修剪过程中要考虑相应的描述。另一个导致树庞大的原因是数据库中存在这大量的、复杂的噪声。噪声导致无关的事例掺杂在选定的测试集中，这将引起“无谓建模”的现象"9】，即树将目标概念和内部噪声都作为建模的对象。这是个普遍的问题，因为给定事例中都不同程度地包含噪声。虽然有多种降低噪声的剪树方法，但没有一个剪树方法对任何噪声都有效。特别对于医学数据，这个问题尤为突出。庞大的树的特点是具有过多的叶节点，并且每个叶节点仅含有少量的实例，这些叶节点是分散的，发生的可能性都很低。不管什么原因，复杂树不仅难以理解，而且分类模糊，更易出错。这样的叶子节点比拥有许多实例的叶更易出现分类错误,更易受噪声影响。一种树修剪方法是通过剪掉只有少数实例的叶子来消除这种分散性。然而，很难在训练集屮辨别特征的真伪，在不考虑对树在未知测试实例中运行性能的影响下，修剪树往往会降低对训练集分类的精确度。因此，我们有必要研究控制决策树的大小的的方法与精简条件属性的方法，在不大幅降低分类准确率的前提下，尽量控制决策树的规模，推导出尽可能短的可理解性强的分类规则。但由于寻找最优的决策树被证明是NP・hanl问题，所以只能通过各种剪枝算法来简化决策树。剪枝是决策树学习算法中一个十分重要的方面，其日的是确保精确程度的同时，提高可理解性。剪枝算法在于确保精确程度的同时，提高可理解性。这两个日标不一定是矛盾的，可能有种方法能同时提高精确度和可理解性。实际上，最初引入树简化方法的目的是控制训练集中的噪声，而后发现它可以提高许多含噪声的数据集的精确度。剪枝算法选择的因素常见的剪枝算法往往分为两种：前剪枝(pepruning)和后剪枝(post-pruning)[201。前剪枝是在决策树构造过程中选取某个预定义的阈值，使得某些节点不再继续分裂，限制树的生长。但选取一个合适的阈值较困难，限制了前剪枝的应用。后剪枝是将已生成的决策树做去分支处理。虽然比前剪枝算法需要更多的计算时间，然而会产生的决策树更可靠，因此应用更加广泛一些。对于剪枝算法的选择有几点需要考虑的因素：分类的精确度如果修剪树导致精确度大幅降低，那么修剪将是毫无意义的。同时，也并不是节点越少错误率就越低，要在树的规模与精确度Z间平衡。决策树的规模生成树的规模越小，则其规则越短也就越容易理解；若树的规模较大，则其节点就越多，每个节点所包含的训练实例个数就越少，则支持每个节点的分类的样本个数就越少，导致错误率可能较大。是否需要独立的剪枝数据集为了解决过分拟合问题，某些剪枝算法采取了独立的剪枝数据集。若数据样本较为丰富，则推荐此种方法；但若数据集很小，一般会釆用其他的剪枝算法。剪枝算法的复杂度通常牛成树阶段的耗时往往比剪枝阶段要多，因为剪枝阶段只需访问牛成的决策树而已。一般地剪枝算法计算复杂度是线性的，值得注意的是CCP算法是非线性的。当训练数据量巨大，无法全部载入内存时，则必须考虑空间复杂度。例如：SLIQ算法就是为解决这一问题而提出的一种高速可伸缩的数据挖掘分类算法。常见的后剪枝算法常见的后剪枝算法主要有以下几种：REP(ReducedErrorPruning)由Quinlan首先提出，它采用独立的剪枝数据集。用叶子替代决策树T的一棵非叶子树So若子树S被替代后形成的新树关于D的误差小于等于S关于D所产生的误差，则用叶子替代子树So重复此过程，直到任意一个子树被叶子节点替代并且不引入其在测试集上新的分类错误〔2匕这样就使因为训练集中的巧合规律性而加入的结点很可能被删除，因为同样的巧合不大会岀现在测试集中。反复地比较错误率，每次总是选取那些删除后可能最大提高决策树在测试集上的精度的结点进行修剪，直到进一步的修剪会降低决策树在测试集上的精度为止。REP方法计算复杂性是线性的，因为决策树中的每个非叶子结点只需要访问一次就可以评估其子树被修剪的概率。它得到的决策树是关于测试集的具有最高精度的子树，并且是规模最小的树。另外它使用独立的测试集，和原始决策树相比，修剪后的决策树对未来新事例的预测偏差较小。该方法的缺点是偏向于过度修剪。因为那些在测试集中不会出现的一些很稀少的训练数据实例所对应的分枝，在剪枝过程中都要被删除。对于小数据集来说是非常不利的。PEP(PessimisticErrorPruning)PEP算法是基于对训练集数据的错误估计的，不需要独立的剪枝数据集。这对于样本较少的情况非常有利，并且对误差估计增加了连续性校正，提高了对未知数据预测的可靠性。PEP方法被认为是当前后剪枝算法屮精度较高的算法之一，但它仍然存在一些缺陷。由于PEP是唯一使用自顶向下剪枝策略的后剪枝算法，与其它方法相比效率更高，速度更快，因为树中的每棵子树最多需要访问一次，但这种策略会带来与前剪枝方法岀现的同样问题。MEP(MinimumErrorPruning)MEP算法采用自底向上的剪枝方式，不需要独立的剪枝数据集。对于树中的非叶子节点，首先计算该节点的误差，再计算该节点每个分支的误差，然后加权相加来判定修剪或者保留该子树，其中权为每个分支拥有的训练样本比例。后来Cestnik和Bratko对MEP做出了一些改进将pi⑴称作“m概率估计”。m的取值可以根据问题域的不同进行调整。一般地来说，m的值越大，树的剪枝程度就越大。由于在MEP的改进版中，m的取值非常重要，Cestnik和Bratko建议由专家领域，依据数据的噪声程度或者是通过对选择生成树的学习来为m选择适当的值。(4)CCP(Cost-ComplexityPruning)CCP方法就是CART剪枝算法，它主要分为两个步骤：首先自底向上，通过对原始决策树中的修剪得到一系列的子树{To,Ti，T2,・・・,Tn},其中To为未经任何修剪的原始树，Tn为只有一个节点的树，Ti+1是由Ti中的一个或多个子树被替换所得到的；按照树的错课率的估计，评价这些树，再根据真实课差率来选择一个最优树作为最后被剪枝的树。由于CCP方法的运行时间和训练数据样木数的关系是二次的。这就比木文中将要介绍的其它几种剪枝方法所需要的时间长得多，因为其它剪枝方法的运行时间和非叶节点的关系是线性的。3基于多策略的决策树剪枝算法算法的提出剪枝算法是决策树中一种克服噪声的技术，它能使决策树得到简化，有助于提高决策树对待测数据的分类能力，同时也会加快分类的速度。有两种极端的情况：一种是过剪枝，虽然生成树变小了，但无疑会降低分类的精度，某些潜在的有价值的知识可能被剪掉了；相反的情况是欠剪枝，虽然对训练数据有很高的分类准确率，但由于决策树过于复杂，对噪声过于敏感，拟合程度较高，对新数据的预测能力降低了。因此如何选择合适的剪枝程度，在结果的可理解性与准确率之间找到平衡，对构建一个合理高效的临床诊断模型起着非常重要的作用。这一点在实际问题的处理中显得更为重要。前面介绍的决策树剪枝算法各有各的优点和缺点，而且倾向于使用一种策略来解决所有问题。这些算法对于某个目标可能实现得很好，如精确度，但对于我们所希望同时满足的其他目标却很难达到，比如：同时满足最低精度以及生成树的规模的要求。对于解决这个问题的思路，一种是改进或提出新的剪枝算法，女口：D.Founrnier等提出的一种新的修剪决策树的方法・DI剪枝法〔2性另一种是提出满足多FI标的新的决策模型。本文沿着第二条思路进行研究，提出了一种基于多策略思想的决策树模型。这种剪枝模型具有更好的灵活性，用户可以根据需要设定不同的参数从而生成不同的剪枝策略。算法的思想为了能够实现对最终决策树模型的控制，首先要使用已有的数据生成一颗决策树，然后输入想要得到的理想模型的参数以及各个参数的权值（即一种策略）。根据此策略作为参照，对原始决策树进行剪枝，最终得到满足此策略最优的决策树模型。对于策略参数的选择上，首先要考虑的精度，这也是很多剪枝算法要考虑的唯一标准参照。而实际应用中，除了满足精度之外，还要考虑的因素有：时间、结果复杂程度、稳定性等等。本文选取了决策树的规模、样本规模、结果匹配度作为主要策略参数。下面是本文定义中出现的基本概念：h为决策树的高度；n为决策树叶子节点数。T为由决策树生成算法生成的未剪枝的完全决策树。为以内部节点t为根的一棵子树。为训练集样本总数；Wv为测试集样本总数。n⑴为分到节点t的训练集样木数；v⑴为分到节点t的测试集样木数。M⑴为分到节点t且属于节点t类别的测试集样本数。定义1树的规模H：决策树规模的大小可以从树的高度和广度来考察。高度Hhigh：决策树的高度即树的层深h,—般地h在2至10之间为宜。低于2则没有意义，高于10则难于理解，复杂性过高。据此给出下列公式：Hhigh(h)=l,当2WhW5；Hhigh(h)=(10-h)/5,当5〈hW10；Hhigh(h)=0,当h>10或hv2。广度Hwidz决策树的广度可以用叶节点数n来衡量。叶节点数越多分类越细。根据经验来看，节点数n在2至20之间比较合适。若数量太多则失去了分类的效果，数量太少则降低了参考价值。给出下列公式：Hwidth(n)—n/5>当2WnW5Hwidth(n)=l,当5vnW10Hwidth(n)=(20-n)/10,当10vnW20Hwidth(n)=0,当nv2或n>20定义2样本规模S：不同的剪枝算法对样本数目的大小有着不同的适用性。有的趋向于过剪枝，适合于丰富样本集；有的修剪程度较小，适合于小样本集。样本总数W=W(+Wv,根据多次实验的数据，给出下列经验公式：S=0,当WW100；S=W/2000,当1000WW>100；S=0.5+W/20000,10000<W>1000；S=l,W>10000o定义3匹配度M：精确度是用来衡量决策树分类准确的程度。但仅仅要求精确度是不够的。以对一位癌症患者的诊断为例作为说明，该患者最终诊断结果为肝癌晚期。将该患者分类为肝癌早期或者非肝癌都是错误的，但是两者匹配的程度不同，显然前者相对地是匹配程度更高些。设Q为给定的阈值，用M(t)來表示叶节点t的匹配度，测试集样本准确率c=vV)/v(z)。若c>a,则有M(t)=1；若cWa,贝ljM(t)二0。整个树的匹配度M为：M=_!_* JM巳0,1]由于策略的不同，选取的描述参数不同，每个决策树Ti都对应一组描述向量(Xii，Xi2，…，Xin),向量的各个分量可以是树的规模、样本规模、匹配度等等。可以简单地将各个分量进行合成PF丈应。7=13.3算法描述具体的策略剪枝过程如下：第一步：设定策略的参数，包括样本规模、树的规模、匹配度等。第二步：设"为T剪枝得到的决策树，L为"去掉第i个叶节点所得到的树。i首先令T二分别计算L和7/的性能参数。若P(Tz)^max(P(r/)),则L为最优计算停止；否则，继续寻找max(P(7'/)),t'=T.o第三步：重复第二步，直到参数不能优化为止，得到按此策略剪枝的最优树。如果对结果不满意，可以修改参数，继续寻找最优解。算法的部分pseudocode描述如下：DefInitialize()TREE_SIZE=input//setthesizeofthetreeMATCH=input//setthematchdataValidate()node=rootEndDefValidate()//validatetheinputvalueUnlessTREE_SIZE>=0AndTREE_SIZE<=1.0RaiseErrorEndUnlessMATCH>=0AndMATCH<=1.0RaiseErrorEndEndDefCalculatePerformance(sub_tree)//calculatethesubtree'sperformanceIfsub_treeisleafThenReturnperform(sub_tree)EndForeachvalueinsub_tree.valuesresult+=value//composeofallvaluesEndReturnresultEndDefGetSubTree(node)//removethenodeandreturnthetreeremove(node)Returnsub_treeEndDefMaxPerformance//getthemaxperformancep=pruned_treeForeachnodeinsub_tree.nodessub_tree=GetSubTree(node)per_arr=[]per_attr«CalculatePerformance(sub_tree)max=per_arr[0]Foreachpinper_arrIfp>maxThenmax=pElseContinueEndEndReturnmaxEndEndDefIsOptimized(node)//thenodeisoptimized?ForeachattrinattributesIfattrisanumericattributeThenForeveryrecordofattrp=CalculatePerformance(self)Ifp>max_performanceThenreturn(true)Elsereturn(false)EndIfattrisacategoryattributeThenForeveryrecordofattrp=CalculatePerformance(self)Ifp>max_valueThenreturn(true)Elsereturn(false)EndEndEndEndDefOptimize()//optimizethetree,findthemaxperformancep=pruned_treeForeachnodeinroot.nodeson=IsOptimized(node)Ifon==TrueThenReturnonEndEnd//ifnothingreturned,thatmeanscannotfindtheoptimizedtreeReturnFalseEnd3.4实验结果对比分析下面采用一组来自于UCI的关于肝功能异常的医学诊断数据作为数据挖掘对象对本算法进行仿真：原始数据片段如下：表3.1肝功异常数据Tab31DataofLiver-disordersmcvalkphossgptsgotgamma^tdrinksselector8592452731().0185645932230.028654331654().0291783424360.0287701228100.0298551317170.02886220179().5188672111110.51925422207().519060251950.51该数据集共有345条记录，7条属性，各个属性说明如下：mcv(meancorpuscularvolume)平均红细胞体积、alkphos(alkalinephosphotase)碱性磷酸酶、sgpt(alamineaminotransferase)丙氨酸氨基转移酶、sgot(aspartateaminotnmsferase)谷草转氨酶、gammagt(gamma-glutamyltranspeptidase)丫-谷氨酰转、drinks(numberofhalf-pintequivalentsofalcoholicbeverages%drunkperday)每天所摄取的含酒精的饮料量、selector(fieldusedtosplitdataintotwosets)分类。C4.5算法首先采用C4.5算法，其生成的规则如下：gammagt<=20sgpt<=19gammagt<=7:1(4.0)gammagt>7alkphos<=77:2(42.0/6.0)alkphos>77mcv<=90sgpt<=16:2(3.0)sgpt>16sgpt<=17:1(2.0)sgpt>17mcv<=89:2(2.0)mcv>89:1(2.0)mcv>90:1(5.0)sgpt>19sgot<=20drinks<=3:1(31.0/1.0)drinks>3sgpt<=23:2(3.0)sgpt>23:1(5.0)sgot>20drinks<=5sgpt<=26:2(21.0/8.0)sgpt>26:1(15.0/3.0)drinks>5:1(5.0)gammagt>20drinks<=5drinks<=3alkphos<=65:2(42.0/6.0)alkphos>65sgot<=24gammagt<=29:1(12.0/1.0)gammagt>29mcv<=87:2(7.0/1.0)mcv>87mcv<=92:1(9.0/2.0)mcv>92:2(2.0)sgot>24sgpt<=39:2(12.0)sgpt>39sgpt<=48:1(7.0/2.0)sgpt>48:2(4.0)drinks>3:2(41.0/3.0)drinks>5drinks<=12sgpt<=21:2(10.0/1.0)sgpt>21sgot<=22:1(11.0/1.0)sgot>22:2(44.0/18.0)drinks>12:1(4.0)该算法生成的决策树大小为51,叶子节点数为26,分类准确率为68.6957%。从上面所生成的规则比较难以理解，虽然进行了剪枝操作过程，但生成树的规模仍比较大。通过此规则不容易应用到新实例的诊断中。CART算法CART生成原始树时用gini系数测度每一个结点内n个类样本的差异程度。在对样本集进行分割时，分割规则采用二叉树表示形式，算法从根结点开始分割，递归地对每个结点从重复进行：下面采用CART算法，其生成的规则如下：gammagt<20.5sgpt<19.5:2(41.0/19.0)sgpt>=19.5:1(60.0/20.0)gammagt>=20.5:2(139.0/66.0)该算法生成的决策树大小为5,叶子节点数为3,分类准确率为67.5362%。在与C4.5在分类准确率相差很小的情况下，CART算法生成的规则要少得多，大大提升了结果的可理解性。基于多策略的决策树剪枝算法下面采用本文的算法，设定TREE_SIZE为0.5,匹配度为0.9,其生成的规则如下：gammagt<=20sgptv=19gammagt<=7:1(4.0)gammagt>7alkphos<=77:2(42.0/6.0)alkphos>77:1(14.0/3.0)sgpt>19sgot<=20:1(38.0/3.0)sgot>20drinks<=5sgptv=26:2(21.0/8.0)sgpt>26:1(15.0/3.0)drinks>5:1(5.0)gammagt>20drinks<=5drinks<=3alkphos<=65:2(42.0/6.0)alkphos>65sgot<=24gammagt<=29:1(12.0/1.0)gammagt>29:2(11.0/3.0)sgot>24sgpt<=39:2(12.0)sgpt>39:1(11.0/3.0)drinks>3:2(41.0/3.0)drinks>5:2(69.0/13.0)该策略生成的决策树大小为27,叶子节点数为14,分类准确率为68.4536%o比C4.5略低，比CART算法略高。决策树的规模大概是C4.5的一半。下面仍采用本文的算法，设定TREE_SIZE为0.25,匹配度为0.8,其生成的规则如下：gammagt<20.5sgpt<19.5alkphos<77.0sgot<14.5:1(5.0/2.0)sgot>=14.5:2(34.0/4.0)alkphos>=77.0mcv<8&5:2(3.0/1.0)mcv>=88.5:1(10.0/2.0)sgpt>=19.5sgot<21.5:1(38.0/5.0)sgot>=21.5mcv<88.5:2(13.0/1.0)mcv>=88.5:1(17.0/5.0)gammagt>=20.5:2(139.0/66.0)该策略生成的决策树大小为15,叶子节点数为8,分类准确率为6&8621%o比C4.5算法和CART算法略高。在保证精度的同时，决策树生成的规则也具有很好的可理解性。为了更全面、科学地了解前面三种算法，做更好地比较，本文又选取了其他儿个数据集，做了多次的实验。本文使用的数据集来源于UCI,共4个数据集，包括：

甲状腺功能低下(hypothyroid)＞糖尿病(diabetes)＞心脏病(heart-c)o具体数据集的参数如下：表3.2挖掘数据集参数Tab・3.2ParameterofDnlaMiningSeihvnothvroiddiabetesheart-cliver-disorders记录个数3772768303345属性个数309147连续属性个数7462离散属性个数23585缺失率5.4%0%0%0%表3.3三种算法的对比分析Tab.3.3contrastof3Algorithmshypothyroiddiabetesheart-cliver-disorders准确率99.5758%73.8281%77.5578%68.6957%C4.5决策树大小29395151叶节点数15203026准确率99.5493%75.1302%80.8581%67.5362%CART决策树大小155195叶节点数83103准确率99.6257%75.3293%79.2658%68.4536%基丁少束呛白勺宙T七士皆卄决策树大小2092927叶节点数1261614通过以上儿个实例可以看出，不同策略的选择导致了结果产生较大的变化，可以根据应用场景选择不同的策略，大大地增强了应用的灵活性。需要说明的是，以上实验结果，并不能反映绝对的性能指标。因为比较的结果均是基于本文中特定的数据样本集合，以及具体参数方法基础之上建立的。采用不同的具体参数设定，不同的数据样本集合，得到的结果可能会不同。因此在实际运用屮，可以根据数据样本的特征和其他要求来选择合适的策略模型。4决策树算法在临床诊断中的应用4丄临床诊断与医学数据挖掘临床诊断临床诊断是医学诊断的核心，它是运用己有的医学知识对疾病的表现进行分析，最终得出结论的过程。诊断的过程是比较复杂的，医生往往要根据病人的症状、化验数据和医学影像结果等才能作岀综合性的判断。传统的疾病诊断过程主要依靠医生的个人经验，其诊断准确性因人而异，存在一定程度的不确定性和主观性。尤其对一些疑难病例的诊断，高度依赖于医学专家的临床经验。因此，此外，医学专家的临床经验常常是一种个人行为，不便于学习和推广。在这样的背景下，数据挖掘的一系列方法开始被用于临床辅助诊断，并取得了一定的效果。如何充分利用以前的确诊病例和医生的诊断经验加上当前病人的信息，让计算机辅助医生快速、有效地正确诊断疾病，正是计算机辅助医学诊断系统的目标。为此，本章将把上一章中提出的决策树算法应用于心脏病的诊断屮，通过数据挖掘的方法发现若干有用的临床诊断知识。医学数据的特点医学数据具有以下特点：形式多样性：医学信息包括纯数据、信号、图象、文字等各种多媒体信息。内容不完整性：许多医学数据的表达、记录本身就具有不确定和模糊性。一些人为因素也可能导致数据记录的偏差和残缺。病例和病案的有限性使医学数据库不可能对任何一种疾病信息都能全而地反映。时效性：医学检测的波形、图像都是时间的函数。信息冗余性：在医疗过程中，经常有“同病异治、界病同治”的现象©】，即对于同一种疾病，不同病人的表现不尽相同，治疗方案也会不同；而对于某些不同的疾病，其化验的结果以及所采取的治疗措施都可能完全相同。另外，不同的医生由于其诊断的主观性，对同一种疾病治疗的方案也可能千差万别。这种现象体现在数据库中，导致了数据库中的大量冗余信息。医学信息的这些特点，决定了医学数据挖掘的特殊性。其中形式多样性是I矢学数据数据不同于其他领域数据的显著区别，这无疑加大了数据挖掘的难度，一次医学数据挖掘是一门涉及面比较广的交叉学科，在疾病的诊断和治疗方面将会发挥巨大的作用。4.1.3医学数据挖掘的基本过程医学数据的特点使得医学数据挖掘与常规的数据挖掘之间存在较大的差异，针对医疗数据库的特点，本文总结了通常意义上医疗数据挖掘的基本过程：理解应用领域、识别数据挖掘的目标。理解医学领域问题的范围和识别I矢疗数据挖掘过程的目标就是要明确数据挖掘的I矢学对象和要得到的结果。产牛目标数据库。为了得到最终的结果，需要牛成一个完整的记录病人医学诊断信息的数据库，各个诊断系统根据不同的冃标來组织其数据库，其中应包含充足的各类病例或一定比率的正病例和反病例作为数据挖掘的训练例和测试例，以便最终能够得到令人满意的正确结果⑶I。清理与预处理数据。其目的是填充数据中的空缺值，消除数据中的噪声数据，纠正数据中的不一致数据。匹配目标与特殊的数据挖掘算法。其目的是决定何种数据模型可能适合搜索数据屮的模式，使用何种数据挖掘方法能与挖掘过程的目标相匹配。模型选择通常基于要挖掘数据的类型，数据挖掘方法的选择依赖于需要什么形式的最终结果，通常是发现或预测。提取数据模式。使用智能的方法从目标数据中提取数据模式。对医疗数据库进行数据挖掘的主要日的是预测和分类疾病。分类和预测是二种数据分析形式，可以用于提取描述重要数据类的模型或预测未来的数据趋势。解释和评估挖掘到的模式。大多数的数据挖掘算法都会挖掘出许多模式。用户应该根据自己的需要识别真正有用的模式，并使用可视化和知识表示技术提供这些有用模式。4.1.4医学数据挖掘的几个问题匿名化与标识转换由于医学信息涉及到患者隐私信息的问题，医学数据除了需要经过一般的数据预处理以外，述需耍进行特别的数据处理，即对患者与记录进行匿名化和标识转换，从而分离患者与患者记录Z间的关联关系〔辺。匿名化是指从记录中去除患者的标识，比如患者的姓名、住址、医院记录号等，或者用错误的标识代替正确的标识。匿名化之后，研究人员不可能通过观察记录知道有关患者的任何信息。标识转换与匿名化有一些细微的差别。变换后的标识可能仍然隐含着患者的真实信息，但是这些隐含的真实信息只有那些经过授权的研究人员才能获得，而未经授权的人员根本无法通过隐含的线索获得患者的任何真实信息。［矢学文本数据挖掘医学文本信息屮，医学专家对影像、信号或者其它临床数据的解释是非标准化的，难以直接进行数据挖掘，因此需要对文本数据进行标准化处理。目前通过计算机对医学文本数据进行标准化转换已经起到了一定的成效。机器转换主要包括三个步骤：分析源语句，转换，产生目标语句。转换的一个难点是源语句不是唯一的。因此需要无止尽地收集各种形式的源语句。目前的机器转换只能处理小于10个单词的语句。影像数据挖掘:当前医学影像数据主要来自一些成像仪器(如B超、CT等)，它们已被越来越多的医学专家视为一种可靠的辅助诊断手段①】。因此，开发有效的影像数据挖掘工具也成为I矢学数据挖掘过程中的关键技术之一，这不仅仅与纯数字数据的挖掘方法不同，而且实现更加困难。医学影像数据挖掘主耍包括：去除或降低影像噪音的影响，提高目标影像质量或对目标组织进行边缘提取医学影响数据的管理与检索。此外，研究快速的、鲁棒的挖掘算法，确保挖掘所得知识的准确性和可靠性，都是庾学数据挖掘的关键性问题。4.2数据挖掘算法应用流程建立决策树的临床诊断系统可分为四步：数据的准备。首先选定挖掘主题，确定数据源，即数据选择；经过数据清洗，缺失值处理等数据预处理过程，构建可用于挖掘的数据集。建立决策树诊断模型。根据需要，确定挖掘的策略参数，进而建立决策树模型。规则输出。每一个决策树模型都对应一组决策规则，这些规则将成为临床诊断的依据。模型评估，对于得到诊断模型，要与已有的医学知识相对照或者请专家进行评估，最终确定诊断模型，形成诊断知识。Fig.4.2FlowofApplicationofDataMining4.3数据的选择目前心脏病己成为危害人类健康的主要疾病之一疾病的确诊是治疗的关键，由于用于心脏病诊断的各项临床检验指标既含有定性数据，如性别，又含有定量数据，如心率，在诊断时存在着明显的模糊性和不精确性，因此在诊断中常有误诊、漏诊发生，特别是在一些基层医院更是如此。应用计算机借助数据挖掘的方法建立辅助疾病诊断模型和专家系统是提高疾病诊断准确率的一个很有发展前景的方向。下面我们将运用有指导学习的方法对心脏病人数据集进行数据挖掘，此数据集是由位于加州LongBeach的VA医疗中心的Detr