InTheBloodHorse

机器学习(2) 决策树(ID3算法实现)

字数统计: 2.7k阅读时长: 11 min
2018/09/22 Share

决策树简介

概念

决策树,顾名思义就是选择,通过问答的形式,针对每一次问答,来推断分解,逐步缩小待猜测事物的范围。
即:问问题,回答,每回答一次,根据答案走到下一层,当没得走了,就是得到了结果了。下图为决策树的流程。TIM截图20180922165959.jpg

决策树的构造

优点:计算复杂度不高,输出结果易于理解,对中间值的缺失不敏感,可以处理不相关特征数据
缺点:可能会产生过度匹配问题
使用数据类型:数值型和标称型

构造细节

在构造决策树时,我们需要解决的第一个问题就是,当前数据集上哪个特征在划分数据分类时起决定性作用。为了寻找决定性的特征,划分出最好的结果,我们就必须评估每个特征。然后对数据进行划分,直到
某个分支下的数据属于同一个类型,表明这个分支已经区分完了。
下面是伪代码
TIM截图20180922170920.jpg

流程

(1) 收集数据:可以使用任何方法。
(2) 准备数据:决策树构造算法只适用于标称型数据,因此数据型数据必须离散化。
(3) 分析数据:可以使用任何方法,构造树完成之后,我们应该检查图形是否符合预期。
(4) 训练算法:构造树的数据结构。
(5) 测试算法:使用经验书计算错误率。
(6) 使用算法:此步骤可以适用于任何监督学习算法,而使用决策树可以更好地理解数据的内在含义。

测试特征包括:不浮出水面是否可以生存,以及是否有脚蹼。我们可以将这些动物分成两类:鱼类和非鱼类。现在我们想要决定依据第一个特征还是第二个特征。如图:
TIM截图20180922171354.jpg

信息增益

划分数据集的大原则是:将无序的数据变得更加有序。
在划分数据集之前之后信息发生的变化成为信息增益,我们可以计算每个特征值划分数据获得的信息增益,获得信息增益最高的特征就是最好的选择。在这里我们可以用过计算熵来实现

熵定义为信息的期望值,在明晰这个概念之前,我们必须知道信息的定义。如果待分类的事物可能划分在多个分类之中,信息定义为
TIM截图20180922201952.jpg
其中P(Xi)是选择该分类的概率。
为了计算熵,我们需要计算所有类别所有可能值包含的信息期望值,可以通过下面的公式得到:
TIM截图20180922202448.jpg其中n是分类的数目
计算香农熵的Python代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def calc_shannon_ent(data_set):
from math import log
# 总数目
sum_number = len(data_set)
label_counts = {}

for data in data_set:
current_label = data[-1]
label_counts[current_label] = label_counts.get(current_label, 0) + 1
shanno_ent = 0.0
for key, value in label_counts.items():
# 求概率
prob = float(value) / sum_number
# 对应的公式
shanno_ent -= prob * log(prob, 2)
return shanno_ent

然后我们就需要测试数据了(和第三张图对应)

1
2
3
4
5
6
7
8
9
10
def create_data_set():
data_set = [
[1, 1, 'yes'],
[1, 1, 'yes'],
[1, 0, 'no'],
[0, 1, 'no'],
[0, 1, 'no']
]
labels = ['no surfacing', 'flippers']
return data_set, labels

测试的结果为 0.9709505944546686
熵越高,则混合的数据也越多,我们可以在数据集中添加更多的分类,观察熵是如何变化的。
比如

1
2
3
4
data_set, label = create_data_set()
data_set[0][-1] = 'maybe'
ent1 = calc_shannon_ent(data_set)
print(ent1)

得到的结果是 1.3709505944546687
得到熵之后,我们就可以按照获取最大信息增益的方法划分数据集。

划分数据集

按照给定特征划分数据集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def split_data_set(data_set, axis, value):
"""
:param data_set: 待区分的数据集
:param axis: 特征值
:param value: 特征值返回的数值
:return: 区分好的数据集
"""
ret_data_set = []
for data in data_set:
if data[axis] == value:
# 接下来两步的目的是pop data[axis]
reduce_data = data[:axis]
reduce_data.extend(data[axis + 1:])
ret_data_set.append(reduce_data)
return ret_data_set

1
2
3
4
# 得到 每个数据说第0位 == 0 的数据集
spilt = split_data_set(data_set, 0, 0)
print(spilt)
#[[1, 'no'], [1, 'no']]

接下来我们将遍历整个数据集,循环计算香农熵和split_data_set()函数,找到最好的特征划分方式。熵计算将会告诉我们如何划分数据集是最好的数据组织方式。

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
def choose_best_feature_to_split(data_set):
# 除去最后一位 也就是 label位
num_value = len(data_set[0]) - 1
# 初始 香农熵,会和后面的进行比较
base_entropy = calc_shannon_ent(data_set)
best_gain = 0.0 # 当前最大的信息增益
best_gain_index = -1 # 能够得到最大信息增益的index
for i in range(num_value):
# 创建唯一的分类标签列表
data_list = [data[i] for data in data_set]
unique_data_list = set(data_list)

# 计算每种划分方式的信息熵
new_entropy = 0.0
for value in unique_data_list:
sub_data_set = split_data_set(data_set, i, value)
prob = len(sub_data_set) / float(len(data_set))
new_entropy += prob * calc_shannon_ent(sub_data_set)

# 比较,计算出最好的信息增益
dis_gain = base_entropy - new_entropy
if dis_gain > best_gain:
best_gain = dis_gain
best_gain_index = i
return best_gain_index

这个函数是遍历当前特征种的所有唯一属性值,对每个特征划分一次数据集,然后计算数据集中的新熵值,并对所有唯一特征值得到的熵求和。信息增益是熵的减少或者是数据无序度的减少。最后比较所有特征中的信息增益,返回最好特征划分的索引值。

1
2
 print(choose_best_feature_to_split(data_set))
# 0

我们可以看到输出的结果是0,说明第0个特征是最好的用于划分数据集的特征。实际上我们去比较一下,会发现结果是正确的。

递归构建决策树

下面思考一个问题:递归什么时候结束?
1:当我们区分出来的数据都是同一个类别的时候,停止。
2:当我们判断的特征全部用完的时候,自然也都全部停止了。
先完②的代码,当全部用完的时候,我们可能还没有完全区分出数据,所以我们需要筛选,遍历完所有特征时返回出现次数最多的

1
2
3
4
5
def majority_cnt(classList):
class_count = {}
for vote in classList:
class_count[vote] = class_count.get(vote, 0) + 1
return sorted(class_count.items(), key=lambda x: x[1], reverse=True)[0][0]

这个代码和我们讲K-近邻算法的规则相似,也容易理解,这里便不多解释。
接下来就是创建树

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
def create_tree(data_set, label):
# 得到一个新的labels,因为后续有del的操作,会改变原列表,会造成某些bug,所以这里创建一个新的
labels = label[:]
# 创建 标签,判断结束条件
class_list = [data[-1] for data in data_set]
if class_list.count(class_list[0]) == len(class_list):
return class_list[0]

if len(data_set[0]) == 0:
return majority_cnt(class_list)
# 得到最好的划分特征索引
best_feat = choose_best_feature_to_split(data_set)
best_feat_label = labels[best_feat]

my_tree = {best_feat_label: {}}
# 与删除已经区分的label
del labels[best_feat]

# 获得唯一特征值
feat_values = [data[best_feat] for data in data_set]
feat_values_set = set(feat_values)

for value in feat_values_set:
# 复制标签,这样原数据不会被改变
sub_labels = labels[:]
my_tree[best_feat_label][value] = create_tree(
# 根据 最好的划分数据索引 得到的特征值 来生成新的数据集
split_data_set(data_set, best_feat, value),
sub_labels)
return my_tree

最后代码遍历当前选择特征包含的所有属性值,在每个数据集划分上递归调用函数 create_tree(),得到的返回值将被插入到字典变量my_tree中。
测试代码

1
2
print(create_tree(data_set, label))
# {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

用Matplotlib注解绘制树形图

用字典的方式非常不易理解,所以采用绘图的方式(能力有限 PIL的内容不多介绍,抱歉)

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
import matplotlib.pyplot as plt
from decision_tree.tree import create_data_set, create_tree

decisionNode = dict(boxstyle="sawtooth", fc="0.8")
leafNode = dict(boxstyle="round4", fc="0.8")
arrow_args = dict(arrowstyle="<-")


def getNumLeafs(myTree):
numLeafs = 0
firstStr = list(myTree.keys())[0]
secondDict = myTree[firstStr]
for key in secondDict.keys():
if type(secondDict[
key]).__name__ == 'dict':
numLeafs += getNumLeafs(secondDict[key])
else:
numLeafs += 1
return numLeafs


def getTreeDepth(myTree):
maxDepth = 0
firstStr = list(myTree.keys())[0]
secondDict = myTree[firstStr]
for key in secondDict.keys():
if type(secondDict[
key]).__name__ == 'dict':
thisDepth = 1 + getTreeDepth(secondDict[key])
else:
thisDepth = 1
if thisDepth > maxDepth: maxDepth = thisDepth
return maxDepth


def plotNode(nodeTxt, centerPt, parentPt, nodeType):
createPlot.ax1.annotate(nodeTxt, xy=parentPt, xycoords='axes fraction',
xytext=centerPt, textcoords='axes fraction',
va="center", ha="center", bbox=nodeType, arrowprops=arrow_args)


def plotMidText(cntrPt, parentPt, txtString):
xMid = (parentPt[0] - cntrPt[0]) / 2.0 + cntrPt[0]
yMid = (parentPt[1] - cntrPt[1]) / 2.0 + cntrPt[1]
createPlot.ax1.text(xMid, yMid, txtString, va="center", ha="center", rotation=30)


def plotTree(myTree, parentPt, nodeTxt):
numLeafs = getNumLeafs(myTree)
depth = getTreeDepth(myTree)
firstStr = list(myTree.keys())[0]
cntrPt = (plotTree.xOff + (1.0 + float(numLeafs)) / 2.0 / plotTree.totalW, plotTree.yOff)
plotMidText(cntrPt, parentPt, nodeTxt)
plotNode(firstStr, cntrPt, parentPt, decisionNode)
secondDict = myTree[firstStr]
plotTree.yOff = plotTree.yOff - 1.0 / plotTree.totalD
for key in secondDict.keys():
if type(secondDict[
key]).__name__ == 'dict':
plotTree(secondDict[key], cntrPt, str(key))
else:
plotTree.xOff = plotTree.xOff + 1.0 / plotTree.totalW
plotNode(secondDict[key], (plotTree.xOff, plotTree.yOff), cntrPt, leafNode)
plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key))
plotTree.yOff = plotTree.yOff + 1.0 / plotTree.totalD


def createPlot(inTree):
fig = plt.figure(1, facecolor='white')
fig.clf()
axprops = dict(xticks=[], yticks=[])
createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)
plotTree.totalW = float(getNumLeafs(inTree))
plotTree.totalD = float(getTreeDepth(inTree))
plotTree.xOff = -0.5 / plotTree.totalW;
plotTree.yOff = 1.0
plotTree(inTree, (0.5, 1.0), '')
plt.show()


if __name__ == '__main__':
data_set, labels = create_data_set()
dict_tree = create_tree(data_set, labels)
print(dict_tree)
createPlot(dict_tree)

我们可以看到调用了creatPlot就可以呈现出我们的决策树
TIM截图20180922211714.jpg

测试算法:使用决策树执行分类

我们通过训练数据构造了决策树之后,我们可以将它用于实际数据的分类。
决策树的分类函数

1
2
3
4
5
6
7
8
9
10
11
12
13
def classiyf(tree, labels, vecotr):
current_node = list(tree.keys())[0]
next_dict = tree[current_node]
feat_index = labels.index(current_node)
for key in next_dict.keys():
if vecotr[feat_index] == key:
# 当前是决策节点
if type(next_dict[key]).__name__ == 'dict':
class_label = classiyf(next_dict[key], labels, vecotr)
else:
# 当前是叶子节点的话,就返回值
class_label = next_dict[key]
return class_label

递归函数,根据我们的传入的向量vector模拟我们的数据,一直走,直到叶子节点。
测试代码

1
2
3
4
5
tree = create_tree(data_set, label)
print(classiyf(tree, label, [1, 0]))
print(classiyf(tree, label, [1, 1]))
# no
# yes

从我们用PIL绘制的决策树图形可以看出,当我们第一步选择 1,第二步选择 0 时,返回的结果为 no,和我们分类函数返回的结果一致。

使用算法:决策树的存储

因为我们每次构造决策树都非常的耗时,即使处理很小的数据集,我们可以用pickle序列化对象将我们训练好的模型存储起来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def store_tree(tree, filename):
import pickle
with open(filename, 'wb') as f:
pickle.dump(tree, f)


def get_tree(filename):
import pickle
try:
fr = open(filename)
return pickle.load(fr)
except Exception as e:
return False

judge = get_tree('tree_model')
if judge:
tree = judge
else:
tree = create_tree(data_set, label)
#存储
store_tree(tree, 'tree_model')

示例:使用决策树预测隐形眼镜类型

代码完全一致 只是数据集变化了而已。(数据集在github,最下方)

1
2
3
4
5
6
7
8
9
10
11
12
def get_data_set():
data_set = []
labels = ['age', 'prescript', 'astigmatic', 'tearRate']
with open('lenses.txt') as f:
for i in f.readlines():
data_list = i.replace('\t', ',').replace('\n', '').split(',')
data_set.append(data_list)
return data_set, labels

data_set, labels = get_data_set()
tree = create_tree(data_set, labels)
createPlot(tree)

我们可以观察到如图
TIM截图20180922213509.jpg
关于机器学习的所有内容都会在GitHub
参考:《机器学习实战》

CATALOG
  1. 1. 决策树简介
    1. 1.1. 概念
    2. 1.2. 决策树的构造
      1. 1.2.1. 构造细节
    3. 1.3. 流程
    4. 1.4. 信息增益
    5. 1.5.
    6. 1.6. 划分数据集
    7. 1.7. 递归构建决策树
    8. 1.8. 用Matplotlib注解绘制树形图
    9. 1.9. 测试算法:使用决策树执行分类
    10. 1.10. 使用算法:决策树的存储
    11. 1.11. 示例:使用决策树预测隐形眼镜类型