数据挖掘经典十大算法_C4.5算法

C4.5算法

一、对算法的通俗理解

C4.5算法是在ID3算法上的改进而来，为啥这么说呢？首先，我们知道ID3算法的核心是在决策树各个结点上应用信息增益做为特征选择的标准，递归的构建决策树，信息增益 = 信息熵 - 条件熵，但是信息增益有个缺点，会导致算法偏向于选择具有更多输出结果的特征。
产生的原因：从概念来看，信息增益反映的给定一个条件以后不确定性减少的程度, 对于某个属性来说必然是分得越细的数据集确定性更高,也就是条件熵越小,信息增益越大。
举个特栗，对于一个值是唯一的特征，即该属性的特征值为1，那么该属性是必然确定的，条件熵为0，这样的特征却具有最大的信息增益。但显然不是作为决策树分类最好的特征选择。这就是ID3算法的缺点，也是C4.5算法改进的地方。
为此，C4.5引入了信息增益率（信息增益比）的概念，对上述问题进行了校正，采用信息增益率作为特征选择的标准。

二、计算公式

关于a信息增益率 = a的信息增益Gain/a的信息熵Entropy

三、举个栗子

若是我们将数据进行处理，按照天气和最终的活动进行分类，得到下图

在上述数据集中有四个属性：记为A={天气，温度，湿度，风速}；以及两个类别标签B={取消，进行}
接下来利用C4.5算法构建决策树：

四、手动构建决策树

前提：所有的log均以2作为底数计算

1. 计算整体的信息熵：

# 在活动标签中，进行有9个，概率为9/14；取消有5个，概率为5/14
Entropy(D) =-9/14*log(9/14)+(-5/14*log(5/14)) = 0.940
1
2

2. 计算每个属性的条件熵：

'''
 （1）天气属性的条件熵
 首先天气属性下有三个类别标签，晴有5个，概率为5/14；阴有4个，概率为4/14；雨有5个，概率为5/14。
 在晴的条件下，活动取消概率为3/5，活动进行概率为2/5；在阴的条件下，活动取消概率为0，活动进行概率为1；在雨的条件下，活动取消概率为2/5，活动进行概率为3/5；
'''
E(天气)=5/14*[-3/5*log(3/5)+(-2/5*log(2/5))]+4/14*[-4/4*log(4/4)]+5/14*[-3/5*log(3/5)+(-2/5*log(2/5))] = 0.694
1
2
3
4
5
6

'''
 （2）温度属性的条件熵
 首先温度属性下有三个类别标签，炎热有4个，概率为4/14；适中有6个，概率为6/14；寒冷有4个，概率为4/14。
 在炎热的条件下，活动取消概率为2/4，活动进行概率为2/4；在适中的条件下，活动取消概率为2/6，活动进行概率为4/6；在寒冷的条件下，活动取消概率为1/4，活动进行概率为3/4；
'''
E(温度)=4/14*[-2/4*log(2/4)+(-2/4*log(2/4))]+6/14*[-2/6*log(2/6)+(-4/6*log(4/6))]+4/14*[-1/4*log(1/4)+(-3/4*log(3/4))] = 0.911
1
2
3
4
5
6

'''
 （3）湿度属性的条件熵
 首先湿度属性下有两个类别标签，高有7个，概率为7/14；正常有7个，概率为7/14.
 在高的条件下，活动取消概率为4/7，活动进行概率为3/7；在正常的条件下，活动取消概率为1/7，活动进行概率为6/7；
'''
E(湿度)=7/14*[-4/7*log(4/7)+(-3/7*log(3/7))]+7/14*[-1/7*log(1/7)+(-6/7*log(6/7))] = 0.789
1
2
3
4
5
6

'''
 （4）风速属性的条件熵
 首先风速属性下有两个类别标签，强有6个，概率为6/14；弱有8个，概率为8/14.
 在强的条件下，活动取消概率为3/6，活动进行概率为3/6；在弱的条件下，活动取消概率为2/8，活动进行概率为6/8；
'''
E(风速)=6/14*[-3/6*log(3/6)+(-3/6*log(3/6))]+8/14*[-2/8*log(2/8)+(-6/8*log(6/8))] = 0.892
1
2
3
4
5
6

3. 计算信息增益

Gain(天气) = Entropy(D)-E(天气) = 0.940-0.694 = 0.246
Gain(温度) = Entropy(D)-E(温度) = 0.940-0.911 = 0.029
Gain(湿度) = Entropy(D)-E(湿度) = 0.940-0.789 = 0.15
Gain(风速) = Entropy(D)-E(风速) = 0.940-0.892 = 0.048
1
2
3
4

4. 计算属性分裂信息度量（属性的信息熵）

# 天气属性，晴有5个，概率为5/14；阴有4个，概率为4/14；雨有5个，概率为5/14。
H(天气) = -5/14*log(5/14)+(-4/14*log(4/14))+(-5/14*log(5/14)) = 1.577
# 温度属性，炎热有4个，概率为4/14；适中有6个，概率为6/14；寒冷有4个，概率为4/14。
H(温度) = -4/14*log(4/14)+(-6/14*log(6/14))+(-4/14*log(4/14)) = 1.556
# 湿度属性，高有7个，概率为7/14；正常有7个，概率为7/14.
H(湿度) = -7/14*log(7/14)+(-7/14*log(7/14)) = 1.0
# 风速属性，强有6个，概率为6/14；弱有8个，概率为8/14.
H(风速) = -6/14*log(6/14)+(-8/14*log(8/14)) = 0.985
1
2
3
4
5
6
7
8

5. 计算信息增益率

GainRatio(天气) =  Gain(天气) / H(天气) = 0.246/1.577 = 0.155
GainRatio(温度) =  Gain(温度) / H(温度) = 0.029/1.556 = 0.0186
GainRatio(湿度) =  Gain(湿度) / H(湿度) = 0.151/1.0 = 0.151
GainRatio(风速) =  Gain(风速) / H(风速) = 0.048/0.985 = 0.048
1
2
3
4

6. 至此可以得出天气属性的信息增益率为最大值，可以做为决策树的根节点。得到决策树的第一层。
   
7. 天气为阴时，活动类别是“纯”的，因此选择其做为叶子节点，选择“不纯”的节点继续分裂。
8. 在子节点中重复1~7，构建完整的决策树。

重复的过程举个栗子吧：
例如：在天气为雨的条件下
（1）计算整体的信息熵
Entropy(D) =-2/5* log(2/5)+(-3/5* log(3/5)) 在雨的条件下，进行为3/5，取消为2/5
（2）计算温度、湿度、风速的条件熵
E(温度) =-3/5*[-2/3* log(2/3)+(-1/3* log(1/3))]+(-2/5* [-1/2* log(1/2)+(-1/2* log(1/2))])
在温度属性中，适中为3/5，进行为2/3，取消为1/3；寒冷为2/5，进行为1/2，取消为1/2；
E(湿度) =-2/5*[-1/2* log(1/2)+(-1/2* log(1/2))]+(-3/5* [-2/3* log(2/3)+(-1/3* log(1/3))])
在湿度属性中，高为2/5，进行为1/2，取消为1/2；正常为3/5，进行为2/3，取消为1/3；
E(风速) = -2/5*(-1* log(1))+(-3/5*(-1* log(1)))
在风速属性中，强为2/5，进行为0，取消为1；弱为3/5，进行为1，取消为0；
（3）计算信息增益
Gain(温度) = Entropy(D)-E(温度)
Gain(湿度) = Entropy(D)-E(湿度)
Gain(风速) = Entropy(D)-E(风速)
（4）计算属性分裂信息度量（属性的信息熵）
H(温度)=-3/5log(3/5)+(-2/5log(2/5))
在温度属性中，适中为3/5，寒冷为2/5
H(湿度)=-2/5log(2/5)+(-3/5log(3/5))
在湿度属性中，高为2/5，正常为3/5
H(风速)=-2/5log(2/5)+(-3/5log(3/5))
在风速属性中，强为2/5，弱为3/5
（5）计算信息增益率
GainRatio(温度) = Gain(温度) / H(温度)
GainRatio(湿度) = Gain(湿度) / H(湿度)
GainRatio(风速) = Gain(风速) / H(风速)
（6）比较三者信息增益率的最大值做为“雨”的子节点

综上：就可以完整的实现使用C4.5算法手动构建决策树啦！