数据仓库与数据挖掘 《数据仓库与数据挖掘》 决策树算法 C4.5 本组成员: 07103218 王维光 07103224 郑辰 07103229 刘倩 07103230 宋琛 数据仓库与数据挖掘 一.背景 最早的决策时算法是由Hunt 等人于1966 年提出的CLS。当前最有影响的决策树算法是Quinlan 于1986 年提出的ID3 和 1993 年提出的C4.5。ID3 只能处理离散型描述属性,它选择信息增益最大的属性划分训练样本,其目的是进行分枝时系统的熵最小,从而提高算法的运算速度和精确度。ID3 算法的主要缺陷是,用信息增益作为选择分枝属性的标准时,偏向于取值较多的属性,而在某些情况下,这类属性可能不会提供太多有价值的信息。C4.5 是ID3 算法的改进算法,不仅可以处理离散型描述属性,还能处理连续性描述属性。C4.5 采用了信息增益比作为选择分枝属性的标准,弥补了 ID3 算法的不足。 决策树算法的优点如下:(1)分类精度高;(2)成的模式简单;(3)对噪声数据有很好的健壮性。因而是目前应用最为广泛的归纳推理算法之一,在数据挖掘中受到研究者的广泛关注。 二.C4.5 改进的具体方面 1.ID3 算法存在的缺点 (1)ID3 算法在选择根 节 点和各 内 部 节 点中的分支 属性时,采用信息增益作为评 价标准。信息增益的缺点是倾 向于选择取值较多的属性,在有些情况下这类属性可能不会提供太多有价值的信息。 (2)ID3 算法只能对描述属性为离散型属性的数据集 构 造 决策树。 2. C4.5 算法做 出的改进 (1)用信息增益率 来 选择属性 克 服 了用信息增益来 选择属性时偏向选择值多的属性的不足。信息增益率 定 义为: 其中Gain(S,A)与ID3 算法中的信息增益相 同 ,而分裂 信息 SplitInfo(S,A)代 表了按 照 属性 A 分裂 样本集 S 的广度和均 匀 性。 数据仓库与数据挖掘 其中,S1到Sc 是c 个不同值的属性A 分割S 而形成的c 个样本子集。 如按照属性A 把S 集(含30 个用例)分成了10 个用例和20 个用例两个集合 则SplitInfo(S,A)=-1/3*log(1/3)-2/3*log(2/3) (2)可以处理连续数值型属性 C4.5 既可以处理离散型描述属性,也可以处理连续性描述属性。在选择某节点上的分枝属性时,对于离散型描述属性,C4.5 的处理方法与ID3 相同,按照该属性本身的取值个数进行计算;对于某个连续性描述属性Ac,假设在某个结点上的数据集的样本数量为total,C4.5 将作以下处理。 将该结点上的所有数据...