非递归式决策树在动力计量计费系统中的应用

戴龙平+戴莉萍+刘丽珍

摘要：决策树算法的实现往往采用面向对象语言工具来实现，与数据库中的结构通常存在一定的差异，需要进行大量的数据转换。现在充分利用数据库中表结构特点和存储过程中PL/SQL语法的强大性及灵活性，采用一个动力计量计费系统中的数据，快速、有效且非递归地实现了决策树C4.5算法中的节点生成、扩展与剪枝主要过程；并进行了规则抽取。应用结果表明，该算法的实现方法具有一定的高效性、稳定性和普适性。

关键词： C4.5算法； 信息增益； 存储过程； 动力计量计费系统

中图分类号： TN919⁃34； TP391.77 文献标识码： A 文章编号： 1004⁃373X（2014）08⁃0091⁃04

Application of nonrecursive decision tree in power metrology⁃billing system

DAI Long⁃ping1, DAI Li⁃ping2, LIU Li⁃zhen3

（1. Jiangxi Branch, China Unicom, Nanchang 330096, China; 2. Software School, Jiangxi Normal University, Nanchang 330022, China;

3. Jiangxi Hongdu Aviation Industry Group Co., Ltd., AVIC, Nanchang 330024, China）

Abstract： The oriented⁃object program⁃developing tools are usually used to implement the algorithms of decision tree. Since the data structures in the programming languages are different from these in a database， massive data conversion is needed. With the data from a power metrology⁃billing system， the critical steps of node generation， node extension and pruning in C4.5 algorithm of decision tree can be implemented quickly， efficiently and non⁃recursively by making full use of the features of table object and the flexibility of PL/SQL in stored procedure， and the corresponding rules can be abstracted easily. Experimental results demonstrate that this method is effective， stable and adaptable.

Keyword： C4.5 Algorithm； information gain； stored procedure； power metrology⁃billing system

0引 言

决策树是用于分类和预测的主要技术，它着眼于从一组无规律的事例中推理出决策树表示形式的分类规则，采用自顶向下的递归方式，在决策树的内部节点进行属性值的比较，并根据不同属性判断从该节点向下分支，在决策树的叶节点得到结论。决策树的主要优点包括易于用户理解，只要训练事例能够用属性的方式表达出来，就可以使用其进行学习；并且易于转换为规则，从根节点到叶节点就对应着一条合理规则，整棵树就对应着一组表达式规则。而且许多实验及应用也说明了其良好的有效性[1⁃2]。近年来，决策树方法在机器学习、知识发现等领域得到了广泛的应用。

在决策树方法中，有2个基本步骤：构造树并将树应用于数据库。一般情况下，决策树的构造基本使用面向对象的高级语言完成，再调用数据库中的数据。这样的做法往往使得数据结构多样、算法处理复杂、实现难度加大等。而随着现代数据库技术的发展，其语言支持功能愈发强大，例如PL/SQL和存储过程。存储过程是一种子程序，实际存放在数据库的数据字典中，应用程序可通过它来访问关系型数据库系统。存储过程的典型应用有结合数据库的数据有效性验证和访问控制机制。而且，存储过程可以统一并加强原本只在应用程序中实现的复杂逻辑过程，从而应用程序可以调用该存储过程[3⁃4]。而且存储过程可以接受参数并回传值，灵活性和运行效率都有所提高。

因此本文中将这两个步骤全部放在SQL Server数据库中完成，利用存储过程完成了C4.5算法的快速实现，并把其应用在一个动力计量计费系统中。

1C4.5算法基本原理

C4.5是Ross Quinlan为改进ID3算法而提出来的一种决策树生成算法。它根据给定的样本集，以树的形式给出分类规则。其生成过程如下[5⁃6]。

假设类别表示为{C1，C2，…，Ck}，T表示为训练集。针对决策树给定节点中T的内容，在构造决策树时一般会有以下3种可能的情况：

（1） 当T包含的一个或多个样本都属于某个类别Cj，那么针对T的决策树则是指向类别Cj的叶节点；

（2） 当T不包含任何样本时，此时决策树仍是叶节点，但与此节点关联的类别则是其父节点中出现频率最高的类别；

（3） 当T包含的样本属于不同的类别时，提出相应的设定，即基于单个属性确定一个结果集{O1，O2，…，On}，T被分成若干个子集{T1，T2，…，Tn}，其中Ti包含了产生Oi的所有样本。此时决策树包含了一个指向该设定的决策点，该决策点的每条分支对应到每个可能的结果。

对于每个子节点都可以继续进行判断，重复上述操作，直到满足决策树的终止条件为止，这个终止条件可以是：节点对应的所有样本属于同一类；或者不存在可以再分割的属性。

以下是决策树生成算法的一般描述。其中T为训练集，A为条件属性集，Y为目标属性，最终生成Tree。

Function Tree=Decision_Tree_Create（T，A，Y）

{

If 训练集为空，则返回值为Failure的单个节点Tree；

If训练集是由相同类别属性值的记录所组成，则返回一个带有该值的单个节点Tree；

If 没有可分的属性，则返回单个节点Tree，其值在训练集的记录中找出频率最高的类别属性值；

//对于A中属性，基于信息理论进行特征选择，从而确定最佳的分裂特性。其中X为分类属性，Values为分裂点；

（X，Values）=Attribute_Selection（T，A，Y）；

//根据分裂特性进行样本集的划分，生成相应的子节点，并对一直递归下去，最终形成一个分支并将其加入到Tree中；

for each V in Values do

subT=满足X的测试条件V的样本子集；

Node=Decision_Tree_Create（subT，A⁃{X}，Y）

Create_Branch（Tree， Node）；

end for

返回Tree；

}

其中节点如何进行分裂是决策树生成过程中的重要步骤。只有根据不同的属性将节点分开，方能形成多个类别。因此，整个问题的核心就是如何选择分裂的属性。通常的做法是测试所有的属性，对每个属性分类的好坏做出相应的量化评价，选择其中一个最好的分类方式。特征选择策略提供了这种量化的指标，这主要依赖于对集合不纯度的度量方法，信息增益就是其中一种，它衡量每个属性对分类后的数据子集的信息量的贡献[7]。

假设训练集T包含n个样本，这些样本分别属于m个类，其中第i个类在T中出现的比例为pi，那么T的信息熵为[3，8]：

[I(T)=i=1m-pilog2pi] （1）

如果m=1，也就是T的样本都属于一个类，那么I（T）=0，达到最小值；如果p1=p2=…=pm，也就是每类样本的个数相同，那么I（T）=log m，达到最大值。

假设属性A把集合T划分成V个子集{T1，T2，…，Tv}，其中Ti所包含的样本数为ni，那么划分后的熵就是：

[E(A)=i=1vninI(Ti)] （2）

那么，分裂后的信息增益为Gain（A）=I（T）-E（A）。

2决策树的节点生成

首先选取训练样本集，本文中使用的是某公司动力分厂中各种动力用量和费用作为数据集，如图1所示。构造决策树的目的就是希望能够知道一个时间段内各个单位各种动力用量高低对于其最终动力费用的影响程度。为描述简单，这里仅仅使用四种动力：综合电ZHD、高峰电GFD、低谷电DGD和平峰电PFD来描述整个决策树算法的快速实现与应用。

图1 各个动力用量费用显示

在构造决策树之前，已经使用朴素Bayes算法将各个动力用量按照高、中、低进行了分类。而后为决策树实现确定数据结构，图2是节点的主体结构。

图2 节点的主体结构

其中Type表示的是某种电量如综合电ZHD，H表示高，M表示中，L表示低。HH表示当ZHD用量分类为高时，总费用分类为高；HM表示当ZHD用量分类为高时，总费用为分类中，其他类推。NodeID是该节点编号，ParentID是其父节点编号，Ancestor保存了其祖辈信息。图3是一个节点的具体实例。

图3 节点表的数据显示

以根节点为例说明一个节点的具体生成过程，算法描述如下：

输入：训练样本集

输出：节点表新增一条节点记录

处理：主要使用T_DTVALUE表，该表中存放了确定分裂结点所需要的各种数值，例如动力类型、费用高中低各自的个数及总个数、信息量值、熵值以及信息增益值

（1） 生成属性取值和类别分布：使用的存储过程是PRC_CREDVALUE，传递一个字符串型的输入参数，即动力类型的名称，进而生成费用高中低的个数及其总个数，其T_DTVALUE中的部分数值如图4所示。

EXEC PRC_CREDTVALUE ′ZHD′

EXEC PRC_CREDTVALUE ′GFD′

EXEC PRC_CREDTVALUE ′DGD′

EXEC PRC_CREDTVALUE ′PFD‘

图4 属性取值与类别分布

（2） 计算训练样本的信息量：变量@H、@M和@L分别是目标属性高中低的样本个数，变量@TOTAL是总个数，根据公式（1）得到信息量值，这里取小数点后4位。

SET @H=（SELECT TOP 1 SUM（ZFYHIGH） FROM T_DTVALUE GROUP BY TYPE）

SET @M=（SELECT TOP 1 SUM（ZFYMIDDLE） FROM T_DTVALUE GROUP BY TYPE）

SET @L=（SELECT TOP 1 SUM（ZFYLOW） FROM T_DTVALUE GROUP BY TYPE）

SET @TOTAL=@H+@M+@L

SET @IT=⁃@H/@TOTAL*LOG（@H/@TOTAL）⁃@M/@TOTAL*LOG（@M/@TOTAL）⁃@L/@TOTAL*LOG（@L/@TOTAL）

（3） 计算每个属性的信息增益：根据式（1），（2），编写存储过程PRC_ ComputeEntropy，通过输入参数灵活求取各个动力类型的熵值。即先求取每个属性值的各个样本子集的信息量，而后信息量之和就是熵值，再用训练样本的信息量减去熵值得到信息增益。表T_DTVALUE中的信息增益值如图5所示。

EXEC PRC_ComputeEntropy ′ZHD′

EXEC PRC_ComputeEntropy ′GFD′

EXEC PRC_ComputeEntropy ′DGD′

EXEC PRC_ComputeEntropy ′PFD′

UPDATE T_DTVALUE SET GAIN=@IT⁃ENTROPY

图5 信息增益值

（4） 确定分裂结点，插入到结点表中：选取信息增益最大的属性作为分裂的节点，因为这里使用的是倒序排列，因此取第1位；因为是根节点，因此无父节点，赋值为0；因为根节点的所有直接子节点没有产生完毕，因此ISOK赋值为0。

SET @TYPE=（ SELECT TOP 1 TYPE FROM T_DTVALUE ORDER BY GAIN DESC）

INSERT INTO T_DTNODES （TYPE，PARENTID，ISOK） VALUES （@TYPE，0，0）

3决策树节点扩展与剪枝

分裂节点确定之后，需要生成其下属子节点。本文中采用了非递归式广度优先来生成决策树，即产生一个节点所有的直接子节点，而后根据这些子节点的顺序再依次产生其所有的直接子节点。为实现非递归方式，同时保证过程的灵活性，除了表结构需要特别仔细的设计外，还大量地使用了MSSQL动态指令执行语句：EXECUTE和SP_ExecuteSQL[9⁃10]。

为了使得到的决策树所蕴含的规则具有普遍意义，必须对决策树进行修剪。树枝修剪的任务主要是删除一个或更多的树枝，并用叶替换这些树枝，使决策树简化，以提高今后分类识别的速度和分类识别新数据的能力。通常采用两种方法进行树枝的修剪，即事前修剪和事后修剪。本文中采用了事前修剪，为每个节点扩展设置了一个阀值，一旦有结果超过阀值，该子树就停止生长。本系统中根据经验值和生产要求设置当前阀值为80%，当综合电用量为高时，总费用为高的比例超过80%，那就不需要进行子节点扩展了。这种剪枝方式比较简单直接而且有效，但是难点就通常在于阀值的确定。

节点表中的HH，HM等字段的赋值表明该节点是否需要进行子节点扩展，例如HH为⁃1表示规则已经产生；为0表示该节点不需要扩展；为⁃2表示继续生长；为1时表示没有这类情况出现。以根节点的子节点生成为例，描述节点扩展与剪枝的算法过程。

输入：根节点结构的初始值和训练样本集

输出：根节点的扩展子节点

处理：当综合电ZHD用量分类为高时

（1） 计算各种情况下的数值比例。例如下段代码就是求取综合电ZHD用量分类为高且总费用分类为高时的比例@HRATE。首先把赋值语句SELECT以字符串的形式赋给变量@STR，而后使用系统存储过程SP_EXECUTESQL执行该条语句，@FLAG的赋值为H，以获取到各个计数值， @NODEID是当前扩展节点的编号。

SET

@STR=′SELECT @HRATE=ROUND（′+@FLAG+′HCOUNT/（′+@FLAG+′HCOUNT+′+@FLAG+′MCOUNT+′+@FLAG+′LCOUNT），2）′

SET @STR=@STR+′ FROM T_DTNODES WHERE NODEID=@NODEID′

EXEC SP_EXECUTESQL @STR， N′@HRATE DECIMAL（10，2） OUT，@NODEID INT′，@HRATE OUT，@NODEID

同理，还需要计算总费用分类为中和低时的比例，即@MRATE和@LRATE。

（2） 回写扩展标识以确定是否在后续过程中得到相应的处理。下段代码是判断综合电ZHD用量分类为高时的子节点生成情况。这里利用到了CASE语句，把求取到的@HRATE，@MRATE和@LRATE和确定好的阀值做比较，来决定不同的结果值。

SET

@STR=′ UPDATE T_DTNODES SET ′+@FLAG+′H=CASE WHEN @HRATE>=0.8 THEN ⁃1

WHEN @MRATE>=0.8 OR @LRATE>=0.8 THEN 0 WHEN @HRATE<0.8 AND @MRATE<0.8 AND

@LRATE<0.8 AND （@HRATE>0 OR @MRATE>0 OR @LRATE>0）THEN ⁃2

WHEN @HRATE=0 AND @MRATE=0 AND @LRATE=0 THEN 1END

WHERE NODEID=@NODEID′

EXEC SP_EXECUTESQL @STR，

N′@HRATE DECIMAL（10，2），

@MRATE DECIMAL（10，2），

@LRATE DECIMAL（10，2），

@NODEID INT′， @HRATE，@MRATE，@LRATE，@NODEID

同理，还需要回写当总费用分类为中和为低时的扩展标识。

4规则的生成

当决策树生成之后，就可以从中推导出分类规则，这个步骤称为规则抽取。每个叶节点表示为一条规则，规则的条件是从根节点出发到该叶节点路径上的所有中间节点构成的一个“与”判断，规则的结论是叶节点的类别。在对新样本进行分类时，如果样本满足某条分类规则的条件判断，那么它的类别就是规则右边的值。这部分算法比较简单，大致的流程描述如下。

输入：节点表T_DTNODES，主要使用到的字段就是节点编号nodeid，父节点编号parentid，ancestor是该节点的所有父辈节点的文字描述；部分数据如图6所示。

输出：规则表T_DTRULES，部分数据如图7所示。

处理：由于在生成树的过程中就较好地保存了各个节点相对应的祖父信息，因此只需要根据nodeid和parentid进行相应的遍历，把这些信息转换成对应的文字表示即可。规则生成比较简单，主要在存储过程中使用了游标，逐行处理。最后还要进行规则的适当调整。

图6 节点表的父子信息

图7 规则表

5结语

本文利用SQL Server数据库中的表结构和存储过程实现了一个决策树算法。其中数据结构简单，基本就是二维表，易于处理；全部算法过程放置在几个存储过程中，非递归式层层调用，增强了灵活性，易于理解；而且应用中由于对数据的访问都是通过存储过程来进行的，可以在不改动存储过程接口的情况下对数据库进行任何改动，使得更新对应用程序而言具有透明性，增强适应性和可维护性。在实际应用中，算法能够正确运行，对于大量的数据具有较好的执行能力，其规则也体现了一定的准确性。不过训练数据由于受到人员录入方式、朴素Bayes分类结果等因素的影响，使得阀值的确定难度加大，进而使得生成的决策树会存在一定的偏差，希望在下一步的工作中调整。

参考文献

[1] 冯少荣.决策树算法的研究与改进[J].厦门大学学报：自然科学版，2007，46（4）：496⁃500.

[2] DUNHAM M H.数据挖掘教程[M].郭崇慧，田凤占，靳晓明，等译.北京：清华大学出版社，2005.

[3] 徐人凤，曾建华.SQL Server 2005数据库及应用[M].北京：高等教育出版社，2007.

[4] 王珊.数据库系统概论[M].4版.北京：高等教育出版社，2007.

[5] 陈安，陈宁，周龙骧.数据挖掘技术及应用[M].北京：科学出版社，2006.

[6] 曲守宁，卢健.C4.5分类算法在硕士研究生智育测评中的应用[J].济南大学学报：自然科学版，2009，23（3）：253⁃256．

[7] 马伟杰.C4.5决策树法在高校贫困生认定中的应用[J].河南教育学院学报：自然科学版，2012，21（3）：27⁃30.

[8] 吴小刚，周萍，彭文惠.决策树算法在大学生心理健康评测中的应用[J].计算机应用与软件，2011，28（10）：240⁃244.

[9] 郭绍虑，甄涛，贾琦.基于存储过程的海量邮件数据挖掘[J].计算机工程，2010，36（1）：40⁃42.

[10] 姚亚夫，邢留涛.决策树C4.5连续属性分割阈值算法改进及其应用[J].中南大学学报：自然科学版，2011，42（12）：3772⁃3776.

（1） 计算各种情况下的数值比例。例如下段代码就是求取综合电ZHD用量分类为高且总费用分类为高时的比例@HRATE。首先把赋值语句SELECT以字符串的形式赋给变量@STR，而后使用系统存储过程SP_EXECUTESQL执行该条语句，@FLAG的赋值为H，以获取到各个计数值， @NODEID是当前扩展节点的编号。

SET

@STR=′SELECT @HRATE=ROUND（′+@FLAG+′HCOUNT/（′+@FLAG+′HCOUNT+′+@FLAG+′MCOUNT+′+@FLAG+′LCOUNT），2）′

SET @STR=@STR+′ FROM T_DTNODES WHERE NODEID=@NODEID′

EXEC SP_EXECUTESQL @STR， N′@HRATE DECIMAL（10，2） OUT，@NODEID INT′，@HRATE OUT，@NODEID

同理，还需要计算总费用分类为中和低时的比例，即@MRATE和@LRATE。

（2） 回写扩展标识以确定是否在后续过程中得到相应的处理。下段代码是判断综合电ZHD用量分类为高时的子节点生成情况。这里利用到了CASE语句，把求取到的@HRATE，@MRATE和@LRATE和确定好的阀值做比较，来决定不同的结果值。

SET

@STR=′ UPDATE T_DTNODES SET ′+@FLAG+′H=CASE WHEN @HRATE>=0.8 THEN ⁃1

WHEN @MRATE>=0.8 OR @LRATE>=0.8 THEN 0 WHEN @HRATE<0.8 AND @MRATE<0.8 AND

@LRATE<0.8 AND （@HRATE>0 OR @MRATE>0 OR @LRATE>0）THEN ⁃2

WHEN @HRATE=0 AND @MRATE=0 AND @LRATE=0 THEN 1END

WHERE NODEID=@NODEID′

EXEC SP_EXECUTESQL @STR，

N′@HRATE DECIMAL（10，2），

@MRATE DECIMAL（10，2），

@LRATE DECIMAL（10，2），

@NODEID INT′， @HRATE，@MRATE，@LRATE，@NODEID

同理，还需要回写当总费用分类为中和为低时的扩展标识。

4规则的生成

当决策树生成之后，就可以从中推导出分类规则，这个步骤称为规则抽取。每个叶节点表示为一条规则，规则的条件是从根节点出发到该叶节点路径上的所有中间节点构成的一个“与”判断，规则的结论是叶节点的类别。在对新样本进行分类时，如果样本满足某条分类规则的条件判断，那么它的类别就是规则右边的值。这部分算法比较简单，大致的流程描述如下。

输入：节点表T_DTNODES，主要使用到的字段就是节点编号nodeid，父节点编号parentid，ancestor是该节点的所有父辈节点的文字描述；部分数据如图6所示。

输出：规则表T_DTRULES，部分数据如图7所示。

处理：由于在生成树的过程中就较好地保存了各个节点相对应的祖父信息，因此只需要根据nodeid和parentid进行相应的遍历，把这些信息转换成对应的文字表示即可。规则生成比较简单，主要在存储过程中使用了游标，逐行处理。最后还要进行规则的适当调整。

图6 节点表的父子信息

图7 规则表

5结语

本文利用SQL Server数据库中的表结构和存储过程实现了一个决策树算法。其中数据结构简单，基本就是二维表，易于处理；全部算法过程放置在几个存储过程中，非递归式层层调用，增强了灵活性，易于理解；而且应用中由于对数据的访问都是通过存储过程来进行的，可以在不改动存储过程接口的情况下对数据库进行任何改动，使得更新对应用程序而言具有透明性，增强适应性和可维护性。在实际应用中，算法能够正确运行，对于大量的数据具有较好的执行能力，其规则也体现了一定的准确性。不过训练数据由于受到人员录入方式、朴素Bayes分类结果等因素的影响，使得阀值的确定难度加大，进而使得生成的决策树会存在一定的偏差，希望在下一步的工作中调整。

参考文献

[1] 冯少荣.决策树算法的研究与改进[J].厦门大学学报：自然科学版，2007，46（4）：496⁃500.

[2] DUNHAM M H.数据挖掘教程[M].郭崇慧，田凤占，靳晓明，等译.北京：清华大学出版社，2005.

[3] 徐人凤，曾建华.SQL Server 2005数据库及应用[M].北京：高等教育出版社，2007.

[4] 王珊.数据库系统概论[M].4版.北京：高等教育出版社，2007.

[5] 陈安，陈宁，周龙骧.数据挖掘技术及应用[M].北京：科学出版社，2006.

[6] 曲守宁，卢健.C4.5分类算法在硕士研究生智育测评中的应用[J].济南大学学报：自然科学版，2009，23（3）：253⁃256．

[7] 马伟杰.C4.5决策树法在高校贫困生认定中的应用[J].河南教育学院学报：自然科学版，2012，21（3）：27⁃30.

[8] 吴小刚，周萍，彭文惠.决策树算法在大学生心理健康评测中的应用[J].计算机应用与软件，2011，28（10）：240⁃244.

[9] 郭绍虑，甄涛，贾琦.基于存储过程的海量邮件数据挖掘[J].计算机工程，2010，36（1）：40⁃42.

[10] 姚亚夫，邢留涛.决策树C4.5连续属性分割阈值算法改进及其应用[J].中南大学学报：自然科学版，2011，42（12）：3772⁃3776.

（1） 计算各种情况下的数值比例。例如下段代码就是求取综合电ZHD用量分类为高且总费用分类为高时的比例@HRATE。首先把赋值语句SELECT以字符串的形式赋给变量@STR，而后使用系统存储过程SP_EXECUTESQL执行该条语句，@FLAG的赋值为H，以获取到各个计数值， @NODEID是当前扩展节点的编号。

SET

@STR=′SELECT @HRATE=ROUND（′+@FLAG+′HCOUNT/（′+@FLAG+′HCOUNT+′+@FLAG+′MCOUNT+′+@FLAG+′LCOUNT），2）′

SET @STR=@STR+′ FROM T_DTNODES WHERE NODEID=@NODEID′

EXEC SP_EXECUTESQL @STR， N′@HRATE DECIMAL（10，2） OUT，@NODEID INT′，@HRATE OUT，@NODEID

同理，还需要计算总费用分类为中和低时的比例，即@MRATE和@LRATE。

（2） 回写扩展标识以确定是否在后续过程中得到相应的处理。下段代码是判断综合电ZHD用量分类为高时的子节点生成情况。这里利用到了CASE语句，把求取到的@HRATE，@MRATE和@LRATE和确定好的阀值做比较，来决定不同的结果值。

SET

@STR=′ UPDATE T_DTNODES SET ′+@FLAG+′H=CASE WHEN @HRATE>=0.8 THEN ⁃1

WHEN @MRATE>=0.8 OR @LRATE>=0.8 THEN 0 WHEN @HRATE<0.8 AND @MRATE<0.8 AND

@LRATE<0.8 AND （@HRATE>0 OR @MRATE>0 OR @LRATE>0）THEN ⁃2

WHEN @HRATE=0 AND @MRATE=0 AND @LRATE=0 THEN 1END

WHERE NODEID=@NODEID′

EXEC SP_EXECUTESQL @STR，

N′@HRATE DECIMAL（10，2），

@MRATE DECIMAL（10，2），

@LRATE DECIMAL（10，2），

@NODEID INT′， @HRATE，@MRATE，@LRATE，@NODEID

同理，还需要回写当总费用分类为中和为低时的扩展标识。

4规则的生成

当决策树生成之后，就可以从中推导出分类规则，这个步骤称为规则抽取。每个叶节点表示为一条规则，规则的条件是从根节点出发到该叶节点路径上的所有中间节点构成的一个“与”判断，规则的结论是叶节点的类别。在对新样本进行分类时，如果样本满足某条分类规则的条件判断，那么它的类别就是规则右边的值。这部分算法比较简单，大致的流程描述如下。

输入：节点表T_DTNODES，主要使用到的字段就是节点编号nodeid，父节点编号parentid，ancestor是该节点的所有父辈节点的文字描述；部分数据如图6所示。

输出：规则表T_DTRULES，部分数据如图7所示。

处理：由于在生成树的过程中就较好地保存了各个节点相对应的祖父信息，因此只需要根据nodeid和parentid进行相应的遍历，把这些信息转换成对应的文字表示即可。规则生成比较简单，主要在存储过程中使用了游标，逐行处理。最后还要进行规则的适当调整。

图6 节点表的父子信息

图7 规则表

5结语

本文利用SQL Server数据库中的表结构和存储过程实现了一个决策树算法。其中数据结构简单，基本就是二维表，易于处理；全部算法过程放置在几个存储过程中，非递归式层层调用，增强了灵活性，易于理解；而且应用中由于对数据的访问都是通过存储过程来进行的，可以在不改动存储过程接口的情况下对数据库进行任何改动，使得更新对应用程序而言具有透明性，增强适应性和可维护性。在实际应用中，算法能够正确运行，对于大量的数据具有较好的执行能力，其规则也体现了一定的准确性。不过训练数据由于受到人员录入方式、朴素Bayes分类结果等因素的影响，使得阀值的确定难度加大，进而使得生成的决策树会存在一定的偏差，希望在下一步的工作中调整。

参考文献

[1] 冯少荣.决策树算法的研究与改进[J].厦门大学学报：自然科学版，2007，46（4）：496⁃500.

[2] DUNHAM M H.数据挖掘教程[M].郭崇慧，田凤占，靳晓明，等译.北京：清华大学出版社，2005.

[3] 徐人凤，曾建华.SQL Server 2005数据库及应用[M].北京：高等教育出版社，2007.

[4] 王珊.数据库系统概论[M].4版.北京：高等教育出版社，2007.

[5] 陈安，陈宁，周龙骧.数据挖掘技术及应用[M].北京：科学出版社，2006.

[6] 曲守宁，卢健.C4.5分类算法在硕士研究生智育测评中的应用[J].济南大学学报：自然科学版，2009，23（3）：253⁃256．

[7] 马伟杰.C4.5决策树法在高校贫困生认定中的应用[J].河南教育学院学报：自然科学版，2012，21（3）：27⁃30.

[8] 吴小刚，周萍，彭文惠.决策树算法在大学生心理健康评测中的应用[J].计算机应用与软件，2011，28（10）：240⁃244.

[9] 郭绍虑，甄涛，贾琦.基于存储过程的海量邮件数据挖掘[J].计算机工程，2010，36（1）：40⁃42.

[10] 姚亚夫，邢留涛.决策树C4.5连续属性分割阈值算法改进及其应用[J].中南大学学报：自然科学版，2011，42（12）：3772⁃3776.