决策树数据挖掘技术在医学诊断中的实现

陈 健

（福建商学院 信息工程学院，福建 福州350012）

大规模数据库和互联网的迅速发展，使人们对数据库的应用提出更多新要求，仅使用查询检索的方法已经不能满足用户提取有用数据实现其目标的结论性信息的要求。数据库中所包含的大量知识无法得到充分的挖掘和使用，造成极大的信息浪费，并产生大量的数据垃圾［1］。另外，从领域专家获得知识是非常复杂的个人到个人之间的交互过程，具有很强的个性及随机性［2］。因此，人们开始考虑用数据库作为知识源，通过数据挖掘可以自动处理数据库中的大量原始数据，挖掘出具有必然的、富有意义的规则和模式，成为有助于人们实现目标的知识［1］，找出人们需要解决问题的答案。

决策树是建立在信息论上解决分类问题比较常用的一种方法，用树形的结构来表示分类规则，构造决策树的过程就是分类规则形成的过程。它根据各变量对目标变量的影响情况产生效应的不同而进行预测，通过这个分类规则就可以比较容易的对未知数据事例进行分类识别和预测，这种方法容易实现可视化，其输出结果的效率也较高，规则也容易理解，所以得到广泛的应用［3］。

1 PEP 剪枝算法

PEP 后剪枝算法是在ID3 算法的基础上，采用自上而下的剪枝算法，对训练事例集的错误估计进行，比较剪枝前后的错分样本数来进行剪枝，在采用同一训练事例集来生成决策树同时又用它来进行剪枝，这样进行剪枝的速度将比较快。正是因为没有使用剪枝事例集，使得对错分样本率R（t）的估计具有较大偏离，因而不能得到最优的剪枝树。所以追加了一个可以对错分样本率R（t）进行校正的连续校正公式，通过校正后可以得到一个较为合理的错分样本率。

用Ni表示决策树的内部节点，Nl表示树的叶节点，N 表示决策树的所有节点，则N=Ni∪Nl，Tt表示以节点t 为根节点的子树。树T 的叶子节点的个数用│Nl│表示。到达节点t 且属于类i 的实例个数用Ni（t）表示，节点t 覆盖的实例总个数用N（t）表示，假设节点t 的实例共有k 类，则N（t）=N1（t）+N2（t）+…+Ni（t）+…+Nk（t）。节点t 覆盖的例外实例个数用E（t）表示：E（t）=N（t）-Max（Ni（t）），其中Max（Ni（t））表示到达节点t 的包含最多实例的类的实例数，即Max（Ni（t））=Max（N1（t）+N2（t）+…+Ni（t）+…+Nk（t））。

令单个节点t 上的错误分类率为

由于使用PEP 后剪枝算法进行决策树的遍历，访问决策树T 的每个子树最多一次，比较其他剪枝算法，PEP 剪枝算法的优点在于剪枝的速度更快。

2 医疗系统的设计

医疗系统是在基于病案数据的医疗数据上进行数据挖掘，首先对医疗数据进行数据预处理，得到离散化的手术诊断决策信息表并存放在数据库中。如何利用决策树数据挖掘技术对手术诊断决策信息表进行挖掘，发现他们之间隐含的关系是该系统的研究重点。以下将介绍具体的系统设计框架，挖掘出手术诊断的决策规则，并介绍实现该系统具体的程序结构和软件包。

2.1 数据预处理

该系统是在基于病案的医疗数据上进行数据挖掘的，在使用前必须对相关的医疗数据进行相应的处理，数据预处理的目的在于可以提供进行数据挖掘和知识发现的数据。对相关医疗数据进行预处理的任务是明确条件属性和决策属性，建立医疗数据信息表，并存放在数据库中，为下一步的决策树挖掘做准备。

院方提供的数据字典和部分医疗数据表包含：病人基本信息表（病例号，性别，年龄，婚否，职业，出生地，民族，家庭地址，住院日期，出院日期）、疾病诊断信息表（病例号，疾病代码，治疗情况，发病日期，住院日期，出院日期）、手术诊断信息表（病例号，手术时间，切口，手术名称，麻醉情况，诊断类别，主刀医生）、医生基本信息表（姓名编码，姓名，职称，工作时间，毕业院校，年龄，科室编码）、门诊用药信息表（病例号，所用药物编号）、疾病列表（疾病代码，…）等，考虑在进行数据挖掘之前，需要对原始的医疗数据表中的属性字段进行如下处理：对于如姓名、联系人等与数据挖掘无关的属性进行删除；对于与决策属性强相关的属性也要去除；对于如主刀医生和麻醉情况等字段，有利于进行决策分析的属性可考虑细化处理；对于如年龄取值为连续的属性转化为离散取值，如幼儿、儿童、少年、青年、中年、老年等；对于如发病日期、住院日期、出院日期取值过多的离散值的属性，进行合并和归类，归纳为手术季节等。

由于手术诊断信息表中部分记录有比较严重的缺损，还有一些对诊断决策不产生影响的冗余的属性，可以考虑把这些记录和属性删除，最终将获得一个比较完备的手术诊断信息表，包含7 个条件属性为{手术类别，病人性别，病人年龄，麻醉情况，主刀职称，手术环境，手术季节}，1 个决策属性为{术后情况}）［4］。

2.2 系统设计框图

根据如上所述，设计了一个可视化的基于决策树PEP 剪枝算法挖掘技术的决策系统。该系统设计框图如图1 所示。

图1 系统设计框图

2.3 程序结构及软件包内组织关系

在构建可视化决策系统时考虑使用B/S 架构，当客户访问系统时，客户端可以通过Applet 与服务器交互，这时是用浏览器自动下载服务器上的Applet 进行访问的。在设计的过程中可以将类分为两类，分别是客户端类和服务器端类。另外由于该系统是图形化决策树挖掘算法系统，分别独立出两个类作为决策树算法和图形绘制方面的应用类。根据以上分析，最终把整个系统分为以下5 个类包：本系统的顶级包为decisiontree。服务器端和客户端通信的数据传输类为decisiontree.info。客户端的类集合包为decisiontree.client。服务器端的类集合包为decisiontree.server。决策树图构建包即图形绘制相关类为decisiontree.wldata。决策树算法相关类为decisiontree.id3。

定义了软件包结构间的调用关系后，通过具体的数据流图详细说明训练集与测试集的采集、信息从客户端到服务器端的传输及反馈、服务器端决策树的生成和客户端决策树的显示整个过程，如图2所示。

图2 系统整体架构图

客户端处理模块（Client）的主要功能：接收客户端的指令流（包括打开决策表或决策树图命令、提取服务器端文件列表命令、由数据表生成决策树命令、保存增删改后的决策树命令和用训练集或测试集优化决策树命令等），并向下传送；向下发送与指令流相对应的数据流信息（包括决策表参数信息和编辑后的决策树结构信息）；接收服务器端反馈的数据流信息（包括构造决策树结构信息、训练集与测试集记录信息和经过服务器端处理的反映决策树决策能力的指标信息等），经过客户端处理模块的处理后向客户端IE 提交显示。

信息封装拆封模块（Info）的主要功能：接收客户端的指令编码进行分析，判断数据信息对应的数据结构对象类（WlData），用该对象类加载数据信息，然后将指令编码和数据信息封装为可序列化的信息流，通过网络向服务器端传送；接收服务器端反馈的序列化信息流，拆封后进行分析，按照指令编码类型确定数据信息的装载对象类，然后用该对象类还原为决策树的数据结构信息或决策表记录信息，并向客户端处理模块发送。

在图2 中将信息封装拆封模块分为Client 端和Server 端是为了说明问题的方便，实际上在Client端和Server 端实现的功能是对称的，因此在程序设计中只需要一个模块就足够了。

网络传输模块（HTTP）的主要功能：基于java 的Servlet 技术，对无论上传或下传的序列化流都是用Servlet Stream 进行封装后在网络中传输。由于该模块只用于数据传输，并且与服务器端耦合紧密，因此在实际设计中，将该模块并入服务器端模块中。

服务器端处理模块（Server）的主要功能：根据负载平衡的需要，为了减轻客户端的负载，把繁重的处理任务尽量放在服务器端执行。客户端只进行指令流、数据流的传输和信息的可视化。服务器端处理模块接收指令信息和数据信息后，根据指令类别调用相应的模块进行处理。服务器端处理模块通过接口连接决策树生成模块（ID3）、决策树训练模块（Training）、决策树测试模块（Testing）以及其他一些处理模块。服务器端和XML 文件是可以交互的：接收要保存的数据信息，经过处理后存入服务器端XML 文件；请求要编辑的XML 文件，经过封装后向客户端发送。

决策树生成模块（ID3）、决策树训练模块（Training）、决策树测试模块（Testing）的主要功能：决策树生成模块（ID3）根据具体的决策表记录信息和字段信息用ID3 算法生成一棵原始的决策树；决策树训练模块（Training）用训练集对原始的决策树进行训练，修剪枝叶，使得决策树在决策能力不发生大的落差情况下树的深度尽可能小；决策树测试模块（Testing）用来测试经过上面两个模块处理后的决策树的实际决策能力，得出正确率和错误率的信息。

2.4 实验结果

从医院获得基于病案的医疗数据库中，经过前期的数据预处理，得到一个术后情况信息决策表。包含7 个条件属性为{手术类别，病人性别，病人年龄，麻醉情况，主刀职称，手术环境，手术季节}，1 个决策属性为{术后情况}）［5］。通过与医院医生的沟通，了解到医生比较关注的是手术后不理想的情况，所以主要筛选出术后情况都是乙等或丙等的记录［6］。取40%的数据记录来生成决策树，并将全部记录用来测试。在实验中，分别进行生成决策树和测试后剪枝算法，具体结果如表1 所示。

表1 决策树后剪枝及其数据集测试结果列表

3 结语

本文介绍了基于决策树PEP 剪枝算法可视化系统，并且得出了手术诊断决策的规则。生成决策树并进行剪枝以及规则归纳和测试的过程都可以利用该系统来完成，并且实现了可视化。但是，由于其他客观因素得到的数据有限，可能还存在其他因素影响手术质量，条件字段集内容还不够，使得决策表中存在许多矛盾的数据，对于最后决策规则的生成产生了一定的负面影响。把产生的规则集和医院的医生进行探讨，医生认为产生的大部分规则客观反映了影响手术的诸多因素，有些规则对他们还是有借鉴意义的，取得了比较满意的结果。