C4.5算法（上）

“

本公众号不定期分享大数据相关干货文章及学习资料，欢迎志同道合的朋友一起来交流学习！

”

今天跟大家分享一下C4.5算法相关内容，内容有点多，会分上下两篇写

简介

一种分类决策树算法，对海量数据集进行分类和回归。

其核心算法是ID3算法.，对ID3算法进行了改进：

1)用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；

2)在树构造过程中进行剪枝；

3)能够完成对连续属性的离散化处理；

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

优点：

产生的分类规则易于理解，准确率较高。

缺点：

在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。

Github

https://github.com/scottjulian/C4.5

案例：

01

什么是决策树

决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。

树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。

决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。 数据挖掘中决策树是一种经常要用到的技术，可以用于分析数据，同样也可以用来作预测（就像上面的银行官员用他来预测贷款风险）。

从数据产生决策树的机器学习技术叫做决策树学习, 通俗说就是决策树。（来自维基百科）

决策树基本思想

自顶向下的递归方法，其基本思想是以信息熵为度量构造一棵熵值下降最快的树，到叶子节点处的熵值为零。此时每个叶节点中的实例都属于同一类。

02

算法描述

该伪代码描述了C4.5的基本工作流程。

首先用根节点代表一个给定的数据集；然后从根节点开始（包括根节点）在每个节点上选择一个属性，使结点数据集划分（一棵树分裂为几棵树）为更小的子集(子树)；直到使用某个属性，其子集中所有样本都属于一个类别，才停止分裂。

03

属性选择度量

又称分裂规则，决定给定节点上的元组如何分裂。

属性选择度量提供了每个属性描述给定训练元组的秩评定，具有最好度量得分的属性被选作给定元组的分裂属性。

目前比较流行的属性选择度量有--信息增益、增益率和Gini指标。

04

信息增益

信息增益是ID3算法中用来进行属性选择度量的。它选择具有最高信息增益的属性来作为节点N的分裂属性。

该属性使结果划分中的元组分类所需信息量最小。

元祖分类所需期望信息公式

Info(D)又称为熵。

属性A将D划分成v个不同的类。在该划分之后，为了得到准确的分类还需要的信息由下面的式子度量。

信息增益定义为原来的信息需求（即仅基于类比例）与新需求（即对A划分之后得到的）之间的差。

缺点：

任意样本集的纯度，越纯，熵越小，也就是说在训练集中，某个属性所取的不同值的个数 越多，那么越有可能拿它来作为分裂属性。

信息增益率

分裂信息

利用引入属性的分裂信息来调节信息增益

信息增益率公式

优点：

信息增益率将分裂信息作为分母，属性取值数目越大，分裂信息值越大，从而部分抵消了属性取值数目所带来的影响。

相比ID3直接使用信息熵的增益选取最佳属性，避免因某属性有较多分类取值因而有较大的信息熵，从而更容易被选中作为划分属性的情况。

Gini指标

Gini指标在CART中使用。Gini指标度量数据划分或训练元组集D的不纯度，公式为