决策树算法C4.5VIP专享VIP免费

数据仓库与数据挖掘 《数据仓库与数据挖掘》 决策树算法 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 将作以下处理。  将该结点上的所有数据...