监督学习之树模型(3)-- C4.5算法

ID3选择(属性)树节点是选择信息增益值最大的属性作为节点。使用信息增益的话其实是有一个缺点,那就是它偏向于具有大量值的属性——就是说在训练集中,某个属性所取的不同值的个数越多,那么越有可能拿它来作为分裂属性,而这样做有时候是没有意义的。
C4.5是ID3的一个改进算法,继承了ID3算法的优点,并引入了新概念”信息增益率”,C4.5算法用信息增益率来选择划分属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足。

信息增益率
信息增益率是用前面的信息增益度和分裂信息度splitInfo(分裂信息度用来衡量属性分裂数据的广度和均匀)来共同定义的。
$$信息增益率 = \frac{信息增益度} {分裂信息度}$$

1、执行步骤

step 1:计算信息熵、条件熵、信息增益率来选择最好的数据集划分特征
step 2:选取信息增益率最高的特征作为根节点划分数据集,创建分支节点
step 3:对每个分支进行判定类别是否相同。相同则停止划分,不同则按照上述方法继续进行划分。

2、代码实现

基于C4.5算法构建决策树

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
# coding:utf-8
'''
C4.5决策树算法
'''
import numpy as np
import math

#========================================================
# 生成训练集
#========================================================

def createDataSet():
dataSet = [['青年', '否', '否', '一般', '拒绝'],
['青年', '否', '否', '好', '拒绝'],
['青年', '是', '否', '好', '同意'],
['青年', '是', '是', '一般', '同意'],
['青年', '否', '否', '一般', '拒绝'],
['中年', '否', '否', '一般', '拒绝'],
['中年', '否', '否', '好', '拒绝'],
['中年', '是', '是', '好', '同意'],
['中年', '否', '是', '非常好', '同意'],
['中年', '否', '是', '非常好', '同意'],
['老年', '否', '是', '非常好', '同意'],
['老年', '否', '是', '好', '同意'],
['老年', '是', '否', '好', '同意'],
['老年', '是', '否', '非常好', '同意'],
['老年', '否', '否', '一般', '拒绝'],
]
featureName = ['年龄', '有工作', '有房子', '信贷情况']
return dataSet, featureName

#========================================================
# 信息熵
#========================================================

def get_Entropy(dataSet):
'''
计算给定数据集的信息熵
'''
# 为分类创建字典
labelCounts = {}
for featVec in dataSet:
currentLabel = featVec[-1]
if currentLabel not in labelCounts.keys():
labelCounts.setdefault(currentLabel, 0)
labelCounts[currentLabel] += 1

# 计算信息熵
Entropy = 0.0
for key in labelCounts:
prob = float(labelCounts[key]) / len(dataSet)
Entropy -= prob * math.log(prob, 2)

return Entropy

#========================================================
# 数据集分割和条件熵
#========================================================

def splitDataSet(dataSet, axis, value):
'''
按照给定的特征列及特征值划分数据集
INPUT --> 数据集, 特征列序号, 特征值
OUTPUT --> 符合该特征的所有实例并且自动移除掉这维特征
'''

# 循环遍历dataSet中的每一行数据,返回不含划分特征的子集
output = []
for featVec in dataSet:
if featVec[axis] == value:
smallFeatVec = featVec[:axis]
smallFeatVec.extend(featVec[axis+1:])
output.append(smallFeatVec)
return output

def get_CE_SI(dataSet, axis, uniqueVals):
'''
计算给定数据集划分的条件熵和分裂信息度
INPUT --> 数据集, 目标特征列序号, 目标特征列的值域
OUTPUT --> 该划分的条件熵和分裂信息度
'''
CondEntropy = 0.0
splitInfo = 0.0
for value in uniqueVals:
subDataSet = splitDataSet(dataSet, axis, value)
prob = len(subDataSet) / float(len(dataSet))
CondEntropy += prob * get_Entropy(subDataSet) # 条件熵的计算
splitInfo -= prob * math.log(prob, 2);
return CondEntropy, splitInfo

#========================================================
# 找出信息增益率最大的特征
#========================================================

def infoGainRatio(dataSet, PEntropy, axis):
'''
计算信息增益
INPUT --> 数据集, 父节点信息熵, 目标特征列序号
OUTPUT --> 该划分的信息增益
'''

featVals = [line[axis] for line in dataSet]
uniqueVals = set(featVals) # 每个元素不重复
newEntropy, splitInfo = get_CE_SI(dataSet, axis, uniqueVals) # 计算条件熵和分裂信息度
infoGainRatio = (PEntropy - newEntropy)/splitInfo
return infoGainRatio

def chooseBestFeat(dataSet):
'''
选择最好的划分特征
INPUT --> 数据集
OUTPUT --> 最好的划分特征
'''
numFeatures = len(dataSet[0]) -1 # 最后一列是分类
baseEntropy = get_Entropy(dataSet) # 返回整个数据集的信息熵
bestInfoGain = 0.0
bestFeature = -1
for i in range(numFeatures): # 遍历所有特征
infoGain = infoGainRatio(dataSet, baseEntropy, i) # 返回具体特征的信息增益率
if(infoGain > bestInfoGain):
bestInfoGain = infoGain
bestFeature = i
return bestFeature

#========================================================
# 构造决策树
#========================================================

def majorityCnt(classList):
'''
投票表决代码
'''
classCount = {}
for vote in classList:
if vote not in classCount.keys():
classCount.setdefault(vote, 0)
classCount[vote] += 1
sortedClassCount = sorted(classCount.items(), key=lambda i:i[1], reverse=True)
return sortedClassCount[0][0]

def createTree(dataSet, featureName):
'''
创建决策树
INPUT --> 数据集, 特征标签
'''
classList = [line[-1] for line in dataSet] # 分类目标列

if classList.count(classList[0]) == len(classList): # 统计属于类型classList[0]的个数
return classList[0] # 当类别完全相同则停止继续划分
if len(dataSet[0]) ==1: # 当只有一个特征的时候,遍历所有实例返回出现次数最多的类别
return majorityCnt(classList) # 返回类别标签

bestFeat = chooseBestFeat(dataSet)
bestFeatLabel = featureName[bestFeat] # 该特征的label
myTree ={bestFeatLabel:{}} # map结构,key为featureLabel
del (featureName[bestFeat])
# 找到需要分类的特征子集
featValues = [line[bestFeat] for line in dataSet]
uniqueVals = set(featValues)
for value in uniqueVals:
subLabels = featureName[:] # 子集合
# 构建数据的子集合,并进行递归
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
return myTree

#========================================================
# 主程序
#========================================================

if __name__ == '__main__':
dataSet, featureName = createDataSet()
r = chooseBestFeat(dataSet)
# print(r)
myTree = createTree(dataSet, featureName)
print(myTree)
0%