监督学习之树模型（2）-- ID3算法

更新于
ID3算法是由澳大利亚计算机科学家Ross Quinlan提出的，建立在'奥卡姆剃刀'的基础上，越简单的决策树越优于越大的决策树（Be Simple），根据信息论的信息增益来进行评估和特征的选择，每次选择信息增益最大的特征作为判断模块。

ID3算法是由澳大利亚计算机科学家Ross Quinlan提出的，建立在”奥卡姆剃刀”的基础上，越简单的决策树越优于越大的决策树（Be Simple），根据信息论的信息增益来进行评估和特征的选择，每次选择信息增益最大的特征作为判断模块。
通过计算每个属性的信息增益，认为增益高的是好属性，易于分类。每次划分选取信息增益最高的属性作为划分标准，进行重复，直至生成一个能完美分类训练样本的决策树。

1、执行步骤

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

2、代码实现

基于ID3算法构建决策树

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

# coding:utf-8
'''
ID3决策树算法
'''
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_CondEntropy(dataSet, axis, uniqueVals):
    '''
    计算给定数据集划分的条件熵
    INPUT --> 数据集, 目标特征列序号, 目标特征列的值域
    OUTPUT --> 该划分的条件熵
    '''
    CondEntropy = 0.0
    for value in uniqueVals:
        subDataSet = splitDataSet(dataSet, axis, value)
        prob = len(subDataSet) / float(len(dataSet))
        CondEntropy += prob * get_Entropy(subDataSet)   # 条件熵的计算 
    return CondEntropy

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

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

    featVals = [line[axis] for line in dataSet]
    uniqueVals = set(featVals) # 每个元素不重复
    newEntropy = get_CondEntropy(dataSet, axis, uniqueVals)  # 计算条件熵
    infoGain = PEntropy - newEntropy # 信息增益 = 信息熵 - 条件熵
    return infoGain

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 = InfoGain(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)

根据决策树执行分类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def classify(inputTree, featureName, testVec):
    '''
    运用决策树进行分类
    INPUT --> 输入的决策树, 特征标签, 待分类数据
    OUTPUT --> 所属分类
    '''
    firstStr = list(inputTree.keys())[0] # 树的第一个属性
    sendDict = inputTree[firstStr]

    featIndex = featureName.index(firstStr)
    classLabel = None
    for key in sendDict.keys():

        if testVec[featIndex] == key:
            if type(sendDict[key]).__name__ == 'dict':
                classLabel = classify(sendDict[key], featureName, testVec)
            else:
                classLabel = sendDict[key]
    return classLabel


labels = ['年龄', '有工作', '有房子', '信贷情况']
result = classify(myTree, labels, ['老年', '否', '否', '一般'])
print(result)

树的可视化

0%