本文详细介绍了C4.5决策树算法，包括与ID3的改进点、算法流程、代码实现分析，以及如何进行训练和样本分类。通过信息增益率选择属性、剪枝和处理非离散数据，C4.5算法在分类任务中表现出色。 摘要由CSDN通过智能技术生成

1.     算法概述

C4.5 ，是机器学习算法中的另一个分类决策树算法，它是决策树 ( 决策树也就是做决策的节点间的组织方式像一棵树，其实是一个倒树 ) 核心算法，是相对于 ID3 算法的改进，主要改进点有：

1. 用信息增益率来选择属性。 C4.5 克服了 ID3 用信息增益选择属性时偏向选择取值多的属性的不足。

2. 在树构造过程中进行剪枝。

3. 对非离散数据也能处理。

4. 能够对不完整数据进行处理。

2.     算法过程

统计好样本集 S ，属性集 A ，分别求出属性集中每个属性的信息增益率，选中增益率最大的属性 P ，假设 P 总有 n 种情况的取值（连续变量要离散化），那么分别统计好第 i 种情况时样本集 Si 和除去 P 的属性集 Pi ，递归生成相对应的子树。

2.1 主要步骤

1 ） 读取文件信息，统计数目

2 ） 建立决策树

如果样本集为空，则生成一个信息数目都为 0 的树节点返回

如果样本均为同一类别，则生成一个叶子节点返回

计算节点正负样本的数目

如果属性值只有那个类别的属性，则生成一个叶子节点，并赋值类型索引

如果以上都不是，则选择一个增益率最大的属性（连续属性要用增益率离散化），按那个属性的取值情况从新定义样本集和属性集，建造相关子树

3 ） 事后剪枝（采用悲观错误率估算）

4 ） 输出决策树

5 ） 移除决策时

3.     算法实现分析

3.1 训练分类器

public void buildClassifier(Instances instances) throws Exception {

ModelSelectionmodSelection;

if ( m_binarySplits )

modSelection= new BinC45ModelSelection( m_minNumObj , instances, m_useMDLcorrection );

modSelection= new C45ModelSelection( m_minNumObj , instances, m_useMDLcorrection );

if (! m_reducedErrorPruning )

m_root = new C45PruneableClassifierTree(modSelection, ! m_unpruned ,

m_CF , m_subtreeRaising , ! m_noCleanup , m_collapseTree );

m_root = new PruneableClassifierTree(modSelection, ! m_unpruned ,

m_numFolds , ! m_noCleanup , m_Seed );

m_root . buildClassifier (instances);

第一个if判断是否对nominal属性进行二分裂，第二个if是判断是否对tree进行剪枝。

modSelection后面会被用于选择足有的分裂模型。

m_root是该树的根节点。

上面比较重要的是最后一句m_root.buildClassifier(instances);用于在各节点中构建分类器。下面我们看看其代码：

(C45PruneableClassifierTree.java)

public void buildClassifier(Instances data) throws Exception {

buildTree(data, m_subtreeRaising );

if ( m_collapseTheTree ){

collapse();

if ( m_pruneTheTree ) {

prune();

if ( m_cleanup ) {

cleanup( new Instances(data, 0));

过程为:首选见创建树然后根据需要对数进行节点折叠、剪枝、清理内存空间等。下面我们依次分析：

3.1.1 创建树buildTree (ClassifierTree.java)

public void buildTree(Instances data, boolean keepData) throws Exception {

Instances [] localInstances;

if (keepData) {

m_train = data;

m_test = null ;

m_isLeaf = false ;

m_isEmpty = false ;

m_sons = null ;

m_localModel = m_toSelectModel .selectModel(data); //选择最优的分裂模型

if ( m_localModel .numSubsets()> 1) {

localInstances = m_localModel .split(data);  //对训练数据进行分组

data = null ;

m_sons = new ClassifierTree [ m_localModel .numSubsets()]; //分配子树

for ( int i = 0; i <

用 WEKA 进行数据挖掘，第 2 部分 weka 算法参数整理 文章目录1 算法原理1.1 计算类别信息熵1.2 计算每个属性的信息熵1.3 计算信息增益1.4 计算属性分裂信息度量1.5 计算信息增益率2 weka 上的实现2.1 WEKA 数据集2.2 在 WEKA 内进行分类 1 算法原理   首先， C4 .5是 决策树 算法的一种。 决策树 算法作为一种分类算法，...