基于数据挖掘的决策树算法分析*

杜 丽 英

(吉林建筑大学计算机科学与工程学院，长春 130118)

0 引言

随着数据库技术的不断发展，信息系统已普及到各个应用领域.在系统的业务处理过程中，通常将产生的相关数据存储在数据库中，在数据库中存储的这些大量数据背后往往隐藏着重要的信息，这些重要信息可以辅助制定营销策略并指导企业的实际决策.从大量的数据中挖掘潜在信息的过程和技术就是数据挖掘.决策树是数据挖掘中常用的算法，主要应用于分类和预测，具有直观且易于理解、效率高的特点.构造决策树的算法有多种，其中ID3和C4.5算法是目前决策树算法中最有影响力的算法.ID3算法是国际上产生最早的决策树分类算法，是以信息增益为标准选择决策属性的，C4.5是在ID3算法的基础上的优化和改进，以信息增益率作为选择决策属性的标准，并在ID3算法的基础上增加了对连续型数据属性的处理[1].

1 决策树算法

在决策树的算法中引入了信息论的方法，用熵来衡量非叶节点的信息量的大小.通过构造一颗决策树，对训练样本所属的类别进行分类.决策树中的非叶节点表示属性，叶子节点表示样本实例所属类别.决策树生成算法的输入是一组带有类别标记的训练样本集合，构造输出的结果是一棵二叉或多叉的树.

1.1 相关概念

(1) 信息熵

1) 设S为含有n个训练样本的数据集，将其划分为m个不同的类，类别集合为{S1,S2,…,Si,…Sm},每个类含有的样本数目为ni，pi=ni/n是类别Si出现的概率.将S划……