决策树(ID3)
决策树的思路
决策树是一种树形结构，其中每个内部节点表示一个属性上的判断，每个分支代表一个判断结果的输出，最后每个叶节点代表一种分类结果。因为其生成的模型很像一个树形结构所以称其为决策树。对于如何处理划分数据集，有ID3、C4.5、CART、随机森林..方法，本文是使用ID3算法进行决策树划分。
基本概念
信息熵
在ID3中是使用信息增益算法来实现划分，而其本质是划分后可以将无序的数据变得有序，也就是获得了更多的信息，而量化信息的定义就是信息熵，当然你也可以不理解信息熵的概念，其实它更本质是提供了数据压缩的一个临界值，但是它的公式很重要，首先要知道信息的定义，如果待分类的事件可能划分在多个分类中，则$x_{i}$的信息定义为
$$l(x_{i})=-\log p(x_{i})$$
其中$p(x_{i})$是选择该分类的概率。
而为了计算信息熵，我们要计算所有可能的信息期望值，通过下面公式得到
$$H=-\sum_{i=1}^{n}p(x_{i})\log p(x_{i})$$
其中$n$是分类的数目
信息增益
信息增益的 = 熵 - 条件熵，它表示的是信息不确定性减少的程度。如果一个属性的信息增益越大，就表示用这个属性进行样本划分可以更好的减少划分后样本的不确定性，当然，也就是选择该属性就可以更快更好地完成我们的分类目标。信息增益就是ID3算法的特征选择指标。
多数表决
试想一下如果最后一个属性结束后仍然没有唯一确定类别怎么办呢？这时就会使用多数表决的办法，即判断最后的标签中每个标签出现的次数，最多的就是最后的属性，这很类似上一篇写的KNN算法中的最后。
实现代码
部分重要代码
#计算信息增益
def cal_entropy(data):
entries_num = len(data)
label_count = {} # 字典存储每个类别出现的次数
for vec in data:
cur_label = vec[-1]
# 将样本标签提取出来，并计数
label_count[cur_label] = label_count.get(cur_label, 0) + 1
Entropy = 0.0
# 对每一个类别，计算样本中取到该类的概率
# 最后将概率带入，求出熵
for key in label_count:
prob = float(label_count[key]) / entries_num
Entropy += prob * math.log(prob, 2) # 此处使用numpy.math
return (0 - Entropy)
#递归生成决策树
def Create_Tree(dataset, labels):
classList = [x[-1] for x in dataset]
if classList.count(classList[0]) == len(classList):
return classList[0]
if len(dataset[0]) == 1:
return Majority_vote(classList)
best_feature = Split_by_entropy(dataset)
best_labels = labels[best_feature]
myTree = {best_labels: {}}
# 复制当前特征标签列表，防止改变原始列表的内容
subLabels = labels[:]
# 删除属性列表中当前分类数据集特征
del (subLabels[best_feature])
# 使用列表推导式生成该特征对应的列
f_val = [x[best_feature] for x in dataset]
uni_val = set(f_val)
for value in uni_val:
# 递归创建子树并返回
myTree[best_labels][value] = Create_Tree(Split_Data(dataset
, best_feature, value), subLabels)
return myTree
决策树储存
构造决策树是很耗时的任务，如果每次处理数据集都需要构建决策树，会消耗非常多的计算时间，所以我们可以把构建好的决策树利用pickle模块存储起来。需要的时候再读取出来。
def storetree(inputtree, filename):
with open(filename, 'wb') as fw:
pickle.dump(inputtree, fw)
def readtree(filename):
with open(filename, 'rb') as fr:
return pickle.load(fr)
全部代码
#decisiontree.py
# -*- coding: utf-8 -*-
from numpy import *
import operator
import pickle
def cal_entropy(data):
entries_num = len(data)
label_count = {} # 字典存储每个类别出现的次数
for vec in data:
cur_label = vec[-1]
# 将样本标签提取出来，并计数
label_count[cur_label] = label_count.get(cur_label, 0) + 1
Entropy = 0.0
# 对每一个类别，计算样本中取到该类的概率
# 最后将概率带入，求出熵
for key in label_count:
prob = float(label_count[key]) / entries_num
Entropy += prob * math.log(prob, 2) # 此处使用numpy.math
return (0 - Entropy)
def Split_Data(dataset, axis, value):
new_subset = []
# 利用循环将不符合value的特征值划分入另一集合
# 相当于将value单独提取出来（或作为叶节点）
for vec in dataset:
if vec[axis] == value:
feature_split = vec[:axis]
feature_split.extend(vec[axis + 1:])
new_subset.append(feature_split)
# extend将VEC中的元素一一纳入feature_split
# append则将feature_split作为列表结合进目标集合
return new_subset
def Split_by_entropy(dataset):
feature_num = len(dataset[0]) - 1
ent_old = cal_entropy(dataset)
best_gain = 0.0
best_feature = -1
# ENT_OLD代表划分前集合的熵，ENT_NEW代表划分后的熵
# best_gain将在迭代每一次特征的时候更新，最终选出最优特征
for i in range(feature_num):
feature_list = [x[i] for x in dataset]
uniVal = set(feature_list)
ent_new = 0.0
# 使用set剔除重复项，保留该特征对应的不同取值
for value in uniVal:
sub_set = Split_Data(dataset, i, value)
prob = len(sub_set) / float(len(dataset))
# 使用熵计算函数求出划分后的熵值
ent_new += prob * (0 - cal_entropy(sub_set))
# 由ent_old - ent_new选出划分对应的最优特征
Info_gain = ent_old - ent_new
if (Info_gain > best_gain):
best_gain = Info_gain
best_feature = i
return best_feature
def Majority_vote(classList):
classcount = {}
for vote in classList:
classcount[vote] = classcount.get(vote, 0) + 1
sorted_count = sorted(classcount.items(), key=operator.itemgetter(1), \
reverse=True)
# 获取每一类出现的节点数（没出现默认为0）并进行排序
# 返回最大项的KEY所对应的类别
return sorted_count[0][0]
def Create_Tree(dataset, labels):
classList = [x[-1] for x in dataset]
if classList.count(classList[0]) == len(classList):
return classList[0]
if len(dataset[0]) == 1:
return Majority_vote(classList)
best_feature = Split_by_entropy(dataset)
best_labels = labels[best_feature]
myTree = {best_labels: {}}
# 复制当前特征标签列表，防止改变原始列表的内容
subLabels = labels[:]
# 删除属性列表中当前分类数据集特征
del (subLabels[best_feature])
# 使用列表推导式生成该特征对应的列
f_val = [x[best_feature] for x in dataset]
uni_val = set(f_val)
for value in uni_val:
# 递归创建子树并返回
myTree[best_labels][value] = Create_Tree(Split_Data(dataset
, best_feature, value), subLabels)
return myTree
def classify(inputtree, indexlabels, testdata):
label = list(inputtree.keys())[0]
secondtree = inputtree[label]
index = indexlabels.index(label)
for key in secondtree.keys():
if testdata[index] == key:
if isinstance(secondtree[key], dict):
return classify(secondtree[key], indexlabels, testdata)
else:
return secondtree[key]
def createDataSet():
dataSet = [
[
1, 1, 'yes'],
[
1, 1, 'yes'],
[
1, 0, 'no'],
[
0, 1, 'no'],
[
0, 1, 'no']]
labels = ['no surfacing', 'flippers']
return (
dataSet, labels)
def storetree(inputtree, filename):
with open(filename, 'wb') as fw:
pickle.dump(inputtree, fw)
def readtree(filename):
with open(filename, 'rb') as fr:
return pickle.load(fr)
if __name__ == "__main__":
mydat, labels = createDataSet()
mytree = Create_Tree(mydat, labels)
storetree(mytree, 'tree.txt')
print(readtree('tree.txt'))
代码总结
其实这次的代码我有一部分是copy的结果，因为自己在最后递归生成树的时候想复杂了(改来改去导致最后面目全非)，所以就都删了，按照别人的代码copy了一份，有点尴尬:sweat:
总结
决策树其实有很多种算法，这篇文章我先使用了ID3，以后会使用CART等等，继续学习:sparkles:
Comments | NOTHING