-
Notifications
You must be signed in to change notification settings - Fork 291
/
c45.md
107 lines (54 loc) · 7.32 KB
/
c45.md
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
# 1. 决策树C4.5算法的改进
上一节我们讲到ID3算法有四个主要的不足，一是不能处理连续特征，第二个就是用信息增益作为标准容易偏向于取值较多的特征，最后两个是缺失值处理的问和过拟合问题。昆兰在C4.5算法中改进了上述4个问题。
对于第一个问题，不能处理连续特征， C4.5的思路是将连续的特征离散化。比如m个样本的连续特征A有m个，从小到大排列为a1,a2,...,am,则C4.5取相邻两样本值的中位数，一共取得m-1个划分点，其中第i个划分点$$T_i$$表示为：$$T_i = \frac{a_i+a_{i+1}}{2}$$。对于这m-1个点，分别计算以该点作为二元分类点时的信息增益。选择信息增益最大的点作为该连续特征的二元离散分类点。比如取到的增益最大的点为at,则小于at的值为类别1，大于at的值为类别2，这样我们就做到了连续特征的离散化。要注意的是，与离散属性不同的是，如果当前节点为连续属性，则该属性后面还可以参与子节点的产生选择过程。
对于第二个问题，信息增益作为标准容易偏向于取值较多的特征的问题。我们引入一个信息增益比的变量IR\(X,Y\)，它是信息增益和特征熵的比值。表达式如下：
$$I_R(D,A) = \frac{I(A,D)}{H_A(D)}$$
其中D为样本特征输出的集合，A为样本特征，对于特征熵$$H_A(D)$$, 表达式如下：
$$H_A(D) = -\sum\limits_{i=1}^{n}\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|}$$
其中n为特征A的类别数，$$Di$$为特征A的第i个取值对应的样本个数。D为样本个数。
特征数越多的特征对应的特征熵越大，它作为分母，可以校正信息增益容易偏向于取值较多的特征的问题。
对于第三个缺失值处理的问题，主要需要解决的是两个问题，一是在样本某些特征缺失的情况下选择划分的属性，二是选定了划分属性，对于在该属性上缺失特征的样本的处理。
对于第一个子问题，对于某一个有缺失特征值的特征A。C4.5的思路是将数据分成两部分，对每个样本设置一个权重（初始可以都为1），然后划分数据，一部分是有特征值A的数据D1，另一部分是没有特征A的数据D2. 然后对于没有缺失特征A的数据集D1来和对应的A特征的各个特征值一起计算加权重后的信息增益比，最后乘上一个系数，这个系数是无特征A缺失的样本加权后所占加权总样本的比例。
对于第二个子问题，可以将缺失特征的样本同时划分入所有的子节点，不过将该样本的权重按各个子节点样本的数量比例来分配。比如缺失特征A的样本a之前权重为1，特征A有3个特征值A1,A2,A3。 3个特征值对应的无缺失A特征的样本个数为2,3,4.则a同时划分入A1，A2，A3。对应权重调节为2/9,3/9, 4/9。
对于第4个问题，C4.5引入了正则化系数进行初步的剪枝。具体方法这里不讨论。下篇讲CART的时候会详细讨论剪枝的思路。
除了上面的4点，C4.5和ID的思路区别不大。
# 2. 决策树C4.5算法的不足与思考
C4.5虽然改进或者改善了ID3算法的几个主要的问题，仍然有优化的空间。
1\)由于决策树算法非常容易过拟合，因此对于生成的决策树必须要进行剪枝。剪枝的算法有非常多，C4.5的剪枝方法有优化的空间。思路主要是两种，一种是预剪枝，即在生成决策树的时候就决定是否剪枝。另一个是后剪枝，即先生成决策树，再通过交叉验证来剪枝。后面在下篇讲CART树的时候我们会专门讲决策树的减枝思路，主要采用的是后剪枝加上交叉验证选择最合适的决策树。
2\)C4.5生成的是多叉树，即一个父节点可以有多个节点。很多时候，在计算机中二叉树模型会比多叉树运算效率高。如果采用二叉树，可以提高效率。
3\)C4.5只能用于分类，如果能将决策树用于回归的话可以扩大它的使用范围。
4\)C4.5由于使用了熵模型，里面有大量的耗时的对数运算,如果是连续值还有大量的排序运算。如果能够加以模型简化可以减少运算强度但又不牺牲太多准确性的话，那就更好了。
# 3. 示例说明
上面的训练集有4个属性，即属性集合A={OUTLOOK, TEMPERATURE, HUMIDITY, WINDY}；而类标签有2个，即类标签集合C={Yes, No}，分别表示适合户外运动和不适合户外运动，其实是一个二分类问题。
我们已经计算过信息增益，这里直接列出来，如下所示：
数据集D包含14个训练样本，其中属于类别“Yes”的有9个，属于类别“No”的有5个，则计算其信息熵：
H\(D\) = -9/14 \* log2\(9/14\) - 5/14 \* log2\(5/14\) = 0.940
下面对属性集中每个属性分别计算信息熵，如下所示：
H\(D\|OUTLOOK\) = 5/14 \* \[- 2/5 \* log2\(2/5\) – 3/5 \* log2\(3/5\)\] + 4/14 \* \[ - 4/4 \* log2\(4/4\) - 0/4 \* log2\(0/4\)\] + 5/14 \* \[ - 3/5 \* log2\(3/5\) – 2/5 \* log2\(2/5\)\] = 0.694
H\(D\|TEMPERATURE\) = 4/14 \* \[- 2/4 \* log2\(2/4\) – 2/4 \* log2\(2/4\)\] + 6/14 \* \[ - 4/6 \* log2\(4/6\) - 2/6 \* log2\(2/6\)\] + 4/14 \* \[ - 3/4 \* log2\(3/4\) – 1/4 \* log2\(1/4\)\] = 0.911
H\(D\|HUMIDITY\) = 7/14 \* \[- 3/7 \* log2\(3/7\) – 4/7 \* log2\(4/7\)\] + 7/14 \* \[ - 6/7 \* log2\(6/7\) - 1/7 \* log2\(1/7\)\] = 0.789
H\(D\|WINDY\) = 6/14 \* \[- 3/6 \* log2\(3/6\) – 3/6 \* log2\(3/6\)\] + 8/14 \* \[ - 6/8 \* log2\(6/8\) - 2/8 \* log2\(2/8\)\] = 0.892
根据上面的数据，我们可以计算选择第一个根结点所依赖的信息增益值，计算如下所示：
I\(D, OUTLOOK\) = H\(D\) - H\(D\|OUTLOOK\) = 0.940 - 0.694 = 0.246
I\(D, TEMPERATURE\) = H\(D\) - H\(D\|TEMPERATURE\) = 0.940 - 0.911 = 0.029
I\(D, HUMIDITY\) = H\(D\) - H\(D\|HUMIDITY\) = 0.940 - 0.789 = 0.151
I\(D, WINDY\) = H\(D\) - H\(D\|WINDY\) = 0.940 - 0.892 = 0.048
接下来，我们计算分裂信息度量H\(V\)：
* OUTLOOK属性
属性OUTLOOK有3个取值，其中Sunny有5个样本、Rainy有5个样本、Overcast有4个样本，则
H\(OUTLOOK\) = - 5/14 \* log2\(5/14\) - 5/14 \* log2\(5/14\) - 4/14 \* log2\(4/14\) = 1.577406282852345
* TEMPERATURE属性
属性TEMPERATURE有3个取值，其中Hot有4个样本、Mild有6个样本、Cool有4个样本，则
H\(TEMPERATURE\) = - 4/14 \* log2\(4/14\) - 6/14 \* log2\(6/14\) - 4/14 \* log2\(4/14\) = 1.5566567074628228
* HUMIDITY属性
属性HUMIDITY有2个取值，其中Normal有7个样本、High有7个样本，则
H\(HUMIDITY\) = - 7/14 \* log2\(7/14\) - 7/14 \* log2\(7/14\) = 1.0
* WINDY属性
属性WINDY有2个取值，其中True有6个样本、False有8个样本，则
H\(WINDY\) = - 6/14 \* log2\(6/14\) - 8/14 \* log2\(8/14\) = 0.9852281360342516
根据上面计算结果，我们可以计算信息增益率，如下所示：
IGR\(OUTLOOK\) = Info\(OUTLOOK\) / H\(OUTLOOK\) = 0.246/1.577406282852345 = 0.15595221261270145
IGR\(TEMPERATURE\) = Info\(TEMPERATURE\) / H\(TEMPERATURE\) = 0.029 / 1.5566567074628228 = 0.018629669509642094
IGR\(HUMIDITY\) = Info\(HUMIDITY\) / H\(HUMIDITY\) = 0.151/1.0 = 0.151
IGR\(WINDY\) = Info\(WINDY\) / H\(WINDY\) = 0.048/0.9852281360342516 = 0.048719680492692784