ML08-决策树
2018-12-30 本文已影响243人
杨强AT南京
一、决策树应用体验
- 分类
import numpy as np
from sklearn import datasets
from sklearn.tree import DecisionTreeClassifier
# 认知红酒数据集（178个样本，3类红酒，每类样本数 ( 59, 71, 48 ) ）
data,target=datasets.load_iris(return_X_y=True)
#data,target=datasets.load_wine(return_X_y=True)
print(data.shape,target.shape)
print((target==0).sum())
print((target==1).sum())
print((target==2).sum())
# ============================
clf = DecisionTreeClassifier()
clf = clf.fit(data[0:145], target[0:145])
# ============================
# 分类结果
pre_cls = clf.predict( data )
# 分类概率
pre_pro = clf.predict_proba(data)
# 分类准确率
score = clf.score(data, target)
# print(pre_cls)
# print(pre_pro)
print(score)
# path=clf.decision_path(data)
# print(path)
print(clf.predict( data[145:150]))
(150, 4) (150,)
50
50
50
1.0
[2 2 2 2 2]
从上面可以看出，决策树对分类具有线性回归无可比拟的优势, 如果对未参与训练的数据集是否也有这么好的分类效果。
- 回归
import numpy as np
from sklearn import datasets
from sklearn.tree import DecisionTreeRegressor
# 体能数据physiological Data（Weight重, Waist腰 and Pulse脉搏.），exercise Target（Chins下巴, Situps仰卧起坐 and Jumps跳跃.）
data,target=datasets.load_linnerud(return_X_y=True)
print(data.shape)
print(target.shape)
clf = DecisionTreeRegressor()
clf = clf.fit(data[0:15], target[0:15])
pre=clf.predict([data[14]])
print(pre)
print(target[14])
(20, 3)
(20, 3)
[[193. 36. 46.]]
[193. 36. 46.]
二、决策树的数学基础
1. 决策与信息论
- 从决策开始谈起
人类经常面临各种决策，比如到了周末，准备安排下自己的周末活动，就会使用到决策：
---->公司老板是否有约------------------------------------------有---【加班】
|---->女朋友是否有约-------------------------------有---【嗨皮】
|---->朋友是否有约打球----------------有---【锻炼】
|-----------------------------无---【游戏】
上述决策中，抽象成一般的数学描述是：
|-一个人的分类结果：加班，嗨皮，锻炼，游戏
|-分类的数据行为数据：[公司老板是否，女朋友是否有约，朋友是否有约球]，我们称为样本数据，数据中的三个情况，称为数据特征。
如果使用鸢尾花数据应该更加细致一点说明，见后面程序中的可视化数据。
循环直到样本都属于某一类，最后分类成功。上面分类产生的决策结构就是决策树(一种形象的称呼)
-
决策的核心要素
决策中有两个核心要素：
|-（1）选择合适的特征
|-（2）分类的阈值
决策的结果：决策树 -
决策的数学知识
其中选取哪个特征，特征的阈值怎么取，依赖一个数学分支学科：信息论。
信息论是运用概率论与数理统计的方法研究信息、信息熵、通信系统、数据传输、密码学、数据压缩等问题的应用数学学科。信息论将信息的传递作为一种统计现象来考虑。
信息论之父：克劳德·香农（Claude Shannon） -
决策分类与信息论
决定决策特征与分类阈值的数学过程就是决策树算法，该算法使用信息论理论知识。其中最基础的算法称为ID3算法。该算法还衍生出C4.5，C5.0和CART算法。
ID3（Iterative Dichotomiser 3）算法也称迭代二分法，是一种贪心算法，用来构造决策树。ID3算法起源于概念学习系统（CLS），以信息熵的下降速度为选取测试属性的标准，即在每个节点选取还尚未被用来划分的具有最高信息增益的特征作为划分标准，然后继续这个过程，直到生成的决策树能完美分类训练样例。
2. 决策树基本概念
-
不纯度
当在某个节点上，样本不是属于单一的一个类别，我们称为样本不纯，度量样本不纯的概念称为不纯度。 当某个节点上样本都属于某一类，该节点的样本的不纯度为0。
度量不纯度有三种方式：
|- 基尼指数：Gini index()
|- 信息熵：Entropy()
|- 分类误差：Classification Error()
-
基尼指数（Gini Index）
假设在某个决策节点，有个样本，
个类别。每个类别的概率为
：
|- -
信息熵（Entropy）
假设在某个决策节点，有
|-
备注： 当年Claude Shannon提出这个公式的时候，冯诺依曼（John von Neumann）建议给一个名字为：熵（Entropy：平均信息值）
-
分类误差（Classification Error）
假设在某个决策节点，有
|- -
概率与占比
上述度量公式中使用的概率，可以使用样本在每个决策节点中的类别占比来代替：
假设在某个决策节点，有，
}。每个类别的概率为
|-，其实就是：每类总数 / 样本总数
-
信息增益
信息增益用来决定分类的阈值，每个算法的信息增益值不一样，下面在具体的算法中给不不同算分信息增益计算公式。
3. 决策树模型
-
生成决策树
|- (1)计算信息熵
|- (2)计算信息增益
|- (3)根据信息增益，选择分类特征；
|- (4)计算特征的不纯度，不纯度为0，就是叶子节点，不在继续分类，不纯度不为0，则继续（1）步骤，直到所有样本的不纯度都是0，就是被正确分类。
两个关键项：
|-信息增益值确定分类特征 。
|-不纯度确定子节点产生（ 纯与不纯 ），确定分类的阈值 。 -
决策模型
直接输入分类特征，按照决策树分类，到叶子节点的结果就是最终的分类输出。
三、决策树算法验证与数学基础
1. 决策树算法验证
- 过拟合缺陷体验
下面代码用来体验，决策树的过拟合缺点。尽管决策树有容易理解，算法容易实现，计算量小等优点，但他有个缺陷就是：过拟合。
import numpy as np
from sklearn.tree import DecisionTreeClassifier
from sklearn import datasets
from sklearn.model_selection import train_test_split # 训练集切分
data,target=datasets.load_iris(return_X_y=True)
train_data, test_data,train_target, test_target = train_test_split(data, target, test_size=0.4,shuffle=True)
print(train_data.shape)
print(train_target.shape)
print(test_data.shape)
print(test_target.shape)
dtc=DecisionTreeClassifier()
# 使用训练样本训练
dtc.fit(train_data,train_target)
# 使用测试集测试
score=dtc.score(test_data,test_target)
print('预测评估：',score)
# 使用全部样本训练
dtc.fit(data,target)
# 使用全部样本测试
score=dtc.score(data,target)
print('预测评估：',score)
(90, 4)
(90,)
(60, 4)
(60,)
预测评估： 0.9333333333333333
预测评估： 1.0
- 决策树属性的理解体验
下面代码输出决策树的属性，可以结合上面决策树的模型去理解。
import numpy as np
from sklearn.tree import DecisionTreeClassifier
from sklearn import datasets
from sklearn.model_selection import train_test_split # 训练集切分
data,target=datasets.load_iris(return_X_y=True)
#data,target=datasets.load_linnerud(return_X_y=True)
dtc=DecisionTreeClassifier(random_state=0,min_samples_split=2) # 为了保证输出结果的稳定性，需要random_state固定。
dtc.fit(data,target) #训练
print('分类类别：',dtc.classes_)
print('特征的重要性：',dtc.feature_importances_ )
print('最大特征数：',dtc.max_features_)
print('类别数：',dtc.n_classes_)
print('训练时的特征数：',dtc.n_features_)
print('训练输出数据的维数：',dtc.n_outputs_) # 一般对分类来说都是一个标量来判定，体能数据的输出就是3
print('评估：',dtc.score(data,target))
分类类别： [0 1 2]
特征的重要性： [0. 0.01333333 0.06405596 0.92261071]
最大特征数： 4
类别数： 3
训练时的特征数： 4
训练输出数据的维数： 1
评估： 1.0
- 决策树的树结构体验
通过决策树的结构体验，我们基本上知道决策事是怎么实现的，然后关注特征选择的信息熵的计算，以及不纯度的计算，我们就可以实现决策树。
import numpy as np
from sklearn.tree import DecisionTreeClassifier
from sklearn import datasets
from sklearn.model_selection import train_test_split # 训练集切分
import sklearn
data,target=datasets.load_iris(return_X_y=True)
#data,target=datasets.load_linnerud(return_X_y=True)
dtc=DecisionTreeClassifier(random_state=0,min_samples_split=2) # 为了保证输出结果的稳定性，需要random_state固定。
dtc.fit(data,target)
tree=dtc.tree_
# 打印树的帮助
# help(sklearn.tree._tree.Tree)
print('结点数：\n',tree.node_count)
print('容量：\n',tree.capacity)
print('最大深度：\n',tree.max_depth)
print('节点分类的特征索引：-2表示没有分类特征，就是叶子节点：\n',tree.feature) #-2表示是叶子节点（因为没有分类特征）
# 说明：3表示使用的第4个特征，进行子节点分叉。-2表示叶子节点，没有子节点分叉。
结点数：
17
容量：
17
最大深度：
5
节点分类的特征索引：-2表示没有分类特征，就是叶子节点：
[ 3 -2 3 2 3 -2 -2 3 -2 2 -2 -2 2 1 -2 -2 -2]
print('节点的样本总数：\n',tree.n_node_samples)
# 150表示决策树上每个节点，未分叉样本数。
节点的样本总数：
[150 50 100 54 48 47 1 6 3 3 2 1 46 3 2 1 43]
print('节点每类样本数：\n',tree.value)
# [[50. 0. 0.]] 表述决策树上，，节点的样本所属类别（标签）的样本数：A类50个，B类0个，C类0个，这是一个不纯度为0的节点，是叶子节点。
节点每类样本数：
[[[50. 50. 50.]]
[[50. 0. 0.]]
[[ 0. 50. 50.]]
[[ 0. 49. 5.]]
[[ 0. 47. 1.]]
[[ 0. 47. 0.]]
[[ 0. 0. 1.]]
[[ 0. 2. 4.]]
[[ 0. 0. 3.]]
[[ 0. 2. 1.]]
[[ 0. 2. 0.]]
[[ 0. 0. 1.]]
[[ 0. 1. 45.]]
[[ 0. 1. 2.]]
[[ 0. 0. 2.]]
[[ 0. 1. 0.]]
[[ 0. 0. 43.]]]
print('分类阈值：-2表示叶子节点，不在分子节点：\n',tree.threshold)
# -2表示没有分叉 ，是叶子节点，阈值就是-2表示。每个样本分叉就按照阈值分叉，这儿每个样本应该有一个信息熵。
分类阈值：-2表示叶子节点，不在分子节点：
[ 0.80000001 -2. 1.75 4.94999981 1.6500001 -2.
-2. 1.54999995 -2. 5.44999981 -2. -2.
4.85000038 3.0999999 -2. -2. -2. ]
print('节点的不纯度：\n',tree.impurity)
# 不纯度为0，表示叶子节点，不会分叉。不纯度非0，表示需要分叉，分类按照每个样本的阈值
节点的不纯度：
[0.66666667 0. 0.5 0.16803841 0.04079861 0.
0. 0.44444444 0. 0.44444444 0. 0.
0.04253308 0.44444444 0. 0. 0. ]
print('左节点：-1表示叶子节点：\n',tree.children_left)
print('右节点：-1表示叶子节点：\n',tree.children_right)
# 列出决策树的每个节点的id（按照顺序排列）-1表示叶子节点。
左节点：-1表示叶子节点：
[ 1 -1 3 4 5 -1 -1 8 -1 10 -1 -1 13 14 -1 -1 -1]
右节点：-1表示叶子节点：
[ 2 -1 12 7 6 -1 -1 9 -1 11 -1 -1 16 15 -1 -1 -1]
- 决策树的树结构可视化
% matplotlib inline
import matplotlib.pyplot as plt
import numpy as np
from sklearn.tree import DecisionTreeClassifier
from sklearn import datasets
from sklearn.model_selection import train_test_split # 训练集切分
import sklearn
from sklearn import tree
from sklearn.externals.six import StringIO #数据缓冲
import pydot # 把数据转换为图像
data,target=datasets.load_iris(return_X_y=True)
#data,target=datasets.load_linnerud(return_X_y=True)
dtc=DecisionTreeClassifier(random_state=0,criterion='entropy') # 为了保证输出结果的稳定性，需要random_state固定。
dtc.fit(data,target)
buff = StringIO()
# tree.export_graphviz(dtc,out_file=buff) # export_graphviz只能导出数据
tree.export_graphviz(dtc, out_file=buff, feature_names=['特征1','特征2','特征3','特征4'], class_names=['A类','B类','C类'], filled=True, rounded=True, special_characters=True)
(graph,)= pydot.graph_from_dot_data(buff.getvalue()) # 转换为图像
graph.write_svg("iris.svg")
鸢尾花决策过程可视化
2. ID3决策算法
- 样本总体信息熵
假设在某个决策节点，有个样本，
个类别。每个类别的概率为
：
|-
比如鸢尾花数据集一共150个，共分3类，按照如下步骤计算信息熵 ：
|- （1）计算样本属于每类的概率为：
|- （2）计算信息熵为：
样本总体信息熵与训练特征无关，只与标签有关，具体代码如下：
from sklearn import datasets
import numpy as np
def calcute_total_entropy(train_label):
# train_label：总体样本的输出标签
# 获取总得样本数
total_num=len(train_label)
# 循环得到所有类别的样本总数
label_num={}
for data in train_label:
if data not in label_num:
label_num[data]=0
label_num[data]+=1
# 计算每类的概率
entropy=0.0
for cls,num in label_num.items():
prop=1.0*num/total_num
entropy+=prop *np.log2(prop)
return [-entropy,label_num.items()]
data,target=datasets.load_iris(return_X_y=True)
ent=calcute_total_entropy(target)
print(ent)
[1.584962500721156, dict_items([(0, 50), (1, 50), (2, 50)])]
from sklearn import datasets
import numpy as np
dtc=DecisionTreeClassifier(criterion='entropy')
# 使用训练样本训练
dtc.fit(data,target)
print(dtc.tree_.impurity)
[1.5849625 0. 1. 0.44506486 0.14609425 0.
0. 0.91829583 0. 0.91829583 0. 0.
0.15109697 0.91829583 0. 0. 0. ]
注意： 通过对我们与sklearn实现的结果比较，发现sklearn的对数运算使用的是以2为底的对数运算。
- 样本特征值信息熵
样本总体信息熵是所有样本按照标签值作为特征计算信息熵（分类标准按照标签分类），样本特征信息熵就是按照训练样本的某个特征值来计算信息熵（分类标准按照标签分类） ，一个特征值一个信息熵，使用这些特征熵就可以计算条件熵。
样本特征值信息熵，就是某个特征中某个值的信息熵，比如鸢尾花中4个特征，第一个特征150个取值，其中有一个取值值一样有20个，其中A类6个，B类9个，C类5个，这样就可以求出这个20个相同特征值的信息熵：， 下面通过例子来说明：
from sklearn import datasets
import numpy as np
def calcute_value_entropy(data_train, data_label, index, value):
# data_train 训练样本
# data_label 样本标签
# index，特征索引，就是训练样本中的第几个特征，从0开始。
# value，需要计算信息熵的特征值。某些特征值在样本中只有一个。这种信息熵等于0，就是不纯度为0。
total_num=0 # 某个特征值在数据集中的个数
label_num={} # 特征值按照分类统计，鸢尾花A类多少个，B类多少个，C类多少个
i=0 # 用来索引data_train与data_label对应位置的数据
# 下面只对index的特征处理，其他特征不处理
for data in data_train[:,index]:
# 只对指定的特征值进行统计
if data == value:
total_num+=1 # 特征值总数递增
# 判定类别
label=data_label[I]
if label not in label_num:
label_num[label]=0
label_num[label]+=1
# 标签对应位置下移
I+=1
# 统计特征值的分类个数，下面计算熵
entropy=0.0
for cls,num in label_num.items():
prop=1.0*num/total_num
entropy+=prop *np.log2(prop)
return [-entropy,total_num,label_num.items()]
data,target=datasets.load_iris(return_X_y=True)
#print(data)
ent=calcute_value_entropy(data,target,0,5.1)
print(ent)
[0.34883209584303193, 9, dict_items([(0, 8), (1, 1)])]
下面我们可以计算出鸢尾花某个特征的所有特征值的信息熵。
from sklearn import datasets
import numpy as np
def calcute_feature_entropy(data_train, data_label, index):
# data_train 训练样本
# data_label 样本标签
# index，特征索引，就是训练样本中的第几个特征，从0开始。
label_entropy={}
# 对训练样本遍历，统计计算每个值的信息熵(只对某个特征值统计)
for data in data_train[ :, index]:
if data not in label_entropy:
ent=calcute_value_entropy(data_train, data_label,index,data)
label_entropy[data]=ent# 只使用前面两个值，其他值可以根据情况使用
return label_entropy
data,target=datasets.load_iris(return_X_y=True)
ents=calcute_feature_entropy(data,target,0)
print(len(ents))
for k,v in ents.items():
print(k,":",v)
35
5.1 : [0.5032583347756457, 9, dict_items([(0, 8), (1, 1)])]
4.9 : [1.2516291673878228, 6, dict_items([(0, 4), (1, 1), (2, 1)])]
4.7 : [-0.0, 2, dict_items([(0, 2)])]
4.6 : [-0.0, 4, dict_items([(0, 4)])]
5.0 : [0.7219280948873623, 10, dict_items([(0, 8), (1, 2)])]
5.4 : [0.6500224216483541, 6, dict_items([(0, 5), (1, 1)])]
4.4 : [-0.0, 3, dict_items([(0, 3)])]
4.8 : [-0.0, 5, dict_items([(0, 5)])]
4.3 : [-0.0, 1, dict_items([(0, 1)])]
5.8 : [1.4488156357251847, 7, dict_items([(0, 1), (1, 3), (2, 3)])]
5.7 : [1.2987949406953985, 8, dict_items([(0, 2), (1, 5), (2, 1)])]
5.2 : [0.8112781244591328, 4, dict_items([(0, 3), (1, 1)])]
5.5 : [0.863120568566631, 7, dict_items([(0, 2), (1, 5)])]
4.5 : [-0.0, 1, dict_items([(0, 1)])]
5.3 : [-0.0, 1, dict_items([(0, 1)])]
7.0 : [-0.0, 1, dict_items([(1, 1)])]
6.4 : [0.863120568566631, 7, dict_items([(1, 2), (2, 5)])]
6.9 : [0.8112781244591328, 4, dict_items([(1, 1), (2, 3)])]
6.5 : [0.7219280948873623, 5, dict_items([(1, 1), (2, 4)])]
6.3 : [0.9182958340544896, 9, dict_items([(1, 3), (2, 6)])]
6.6 : [-0.0, 2, dict_items([(1, 2)])]
5.9 : [0.9182958340544896, 3, dict_items([(1, 2), (2, 1)])]
6.0 : [0.9182958340544896, 6, dict_items([(1, 4), (2, 2)])]
6.1 : [0.9182958340544896, 6, dict_items([(1, 4), (2, 2)])]
5.6 : [0.6500224216483541, 6, dict_items([(1, 5), (2, 1)])]
6.7 : [0.954434002924965, 8, dict_items([(1, 3), (2, 5)])]
6.2 : [1.0, 4, dict_items([(1, 2), (2, 2)])]
6.8 : [0.9182958340544896, 3, dict_items([(1, 1), (2, 2)])]
7.1 : [-0.0, 1, dict_items([(2, 1)])]
7.6 : [-0.0, 1, dict_items([(2, 1)])]
7.3 : [-0.0, 1, dict_items([(2, 1)])]
7.2 : [-0.0, 3, dict_items([(2, 3)])]
7.7 : [-0.0, 4, dict_items([(2, 4)])]
7.4 : [-0.0, 1, dict_items([(2, 1)])]
7.9 : [-0.0, 1, dict_items([(2, 1)])]
- 样本特征总体熵（条件熵）
样本特征总体上，就是固定某个特征的信息熵，为了更加容易理解，按照我们前面的定义，总体信息熵定义如下：
假设在某个决策节点，有，其中
表示属于某类别，
表示所有类别 ：
|-
我们可以把特征熵按照条件概率建模，特征信息熵定义如下：
假设某个特征的样本值不同的是个，特征值集合表示为
，则特征的总体熵（条件熵）定义如下：
|-
我们就可以计算出鸢尾花4个特征的信息熵（ 也称条件熵 ）
from sklearn import datasets
import numpy as np
# 计算某个特征中某个值的信息熵
def calcute_value_entropy(data_train, data_label, index, value):
# data_train 训练样本
# data_label 样本标签
# index，特征索引，就是训练样本中的第几个特征，从0开始。
# value，需要计算信息熵的特征值。某些特征值在样本中只有一个。这种信息熵等于0，就是不纯度为0。
total_num=0 # 某个特征值在数据集中的个数
label_num={} # 特征值按照分类统计，鸢尾花A类多少个，B类多少个，C类多少个
i=0 # 用来索引data_train与data_label对应位置的数据
# 下面只对index的特征处理，其他特征不处理
for data in data_train[:,index]:
# 只对指定的特征值进行统计
if data == value:
total_num+=1 # 特征值总数递增
# 判定类别
label=data_label[I]
if label not in label_num:
label_num[label]=0
label_num[label]+=1
# 标签对应位置下移
I+=1
# 统计特征值的分类个数，下面计算熵
entropy=0.0
for cls,num in label_num.items():
prop=1.0*num/total_num
entropy+=prop *np.log2(prop)
return [-entropy,total_num,label_num.items()]
# 计算某个特征的信息熵
def calcute_feature_entropy(data_train, data_label, index):
# data_train 训练样本
# data_label 样本标签
# index，特征索引，就是训练样本中的第几个特征，从0开始。
total_num=len(data_train) #
label_entropy={}
# 对训练样本遍历，统计计算每个值的信息熵(只对某个特征值统计)
for data in data_train[ :, index]:
if data not in label_entropy:
ent=calcute_value_entropy(data_train, data_label,index,data)
label_entropy[data]=[ ent[0], ent[1] ]
# 计算整个特征的信息熵
feature_entropy=0.0
for _, v in label_entropy.items():
prop=1.0 * v[1] / total_num
feature_entropy+=prop * v[0]
return feature_entropy
# 计算鸢尾花四个特征的信息熵
data,target=datasets.load_iris(return_X_y=True)
feature_num=data.shape[1] # 特征数
for idx in range(feature_num):
ent=calcute_feature_entropy(data,target,idx)
print(ent)
0.7080248798300983
1.07409253659755
0.1386459770753561
0.14906466204571436
- 特征信息增益
所谓信息增益值，是针对样本总体信息熵而言，起定义如下：
假设训练样本集有个特征，
表示样本特征的索引：
。
就表示第
|-
下面使用代码来说明鸢尾花的特征信息增益的计算结果（为了保证大家的阅读方便，我把所有代码汇集在一起形成一个独立完整的程序）。
from sklearn import datasets
import numpy as np
# 计算总体信息熵========================================
def calcute_total_entropy(train_label):
# train_label：总体样本的输出标签
# 获取总得样本数
total_num=len(train_label)
# 循环得到所有类别的样本总数
label_num={}
for data in train_label:
if data not in label_num:
label_num[data]=0
label_num[data]+=1
# 计算每类的概率
entropy=0.0
for cls,num in label_num.items():
prop=1.0*num/total_num
entropy+=prop *np.log2(prop)
# print('不纯度：', -entropy)
return [-entropy,label_num.items()]
# 计算某个特征中某个值的信息熵========================================
def calcute_value_entropy(data_train, data_label, index, value):
# data_train 训练样本
# data_label 样本标签
# index，特征索引，就是训练样本中的第几个特征，从0开始。
# value，需要计算信息熵的特征值。某些特征值在样本中只有一个。这种信息熵等于0，就是不纯度为0。
total_num=0 # 某个特征值在数据集中的个数
label_num={} # 特征值按照分类统计，鸢尾花A类多少个，B类多少个，C类多少个
i=0 # 用来索引data_train与data_label对应位置的数据
# 下面只对index的特征处理，其他特征不处理
for data in data_train[:,index]:
# 只对指定的特征值进行统计
if data == value:
total_num+=1 # 特征值总数递增
# 判定类别
label=data_label[I]
if label not in label_num:
label_num[label]=0
label_num[label]+=1
# 标签对应位置下移
I+=1
# 统计特征值的分类个数，下面计算熵
entropy=0.0
for cls,num in label_num.items():
prop=1.0*num/total_num
entropy+=prop *np.log2(prop)
return [-entropy,total_num,label_num.items()]
# 计算某个特征的信息熵========================================
def calcute_feature_entropy(data_train, data_label, index):
# data_train 训练样本
# data_label 样本标签
# index，特征索引，就是训练样本中的第几个特征，从0开始。
total_num=len(data_train) #
label_entropy={}
# 对训练样本遍历，统计计算每个值的信息熵(只对某个特征值统计)
for data in data_train[ :, index]:
if data not in label_entropy:
ent=calcute_value_entropy(data_train, data_label,index,data)
label_entropy[data]=[ ent[0], ent[1] ]
# 计算整个特征的信息熵
feature_entropy=0.0
for _, v in label_entropy.items():
prop=1.0 * v[1] / total_num
feature_entropy+=prop * v[0]
return feature_entropy
# 计算特征的信息增益========================================
def calcute_gain_value(data_train, data_label):
feature_num=data_train.shape[1] # 特征数
# 样本总体信息熵
total_entropy=calcute_total_entropy(data_label)
gains=[]
for idx in range(feature_num):
entropy=calcute_feature_entropy(data,target,idx)
gain=total_entropy[0]-entropy
gains.append(gain)
return gains
# 加载数据集========================================
data,target=datasets.load_iris(return_X_y=True)
iris_gains=calcute_gain_value(data,target)
print(iris_gains)
[0.8769376208910578, 0.5108699641236061, 1.4463165236458, 1.4358978386754417]
-
特征选择
根据上面计算出来的信息增益值的结果，我们可以选择具有最大信息增益值的特征作为子节点分类特征。从上面的计算结果来看，我们选择第3个特征来作为分类特征。 -
子节点分类
我们选择使用第三个特征（index=2）来做子节点分类，下面我们看下第三类特征的特征值熵的情况与信息增益值。并得到观察决策树子节点生成阈值情况：
from sklearn import datasets
import numpy as np
# 计算总体信息熵========================================
def calcute_total_entropy(train_label):
# train_label：总体样本的输出标签
# 获取总得样本数
total_num=len(train_label)
# 循环得到所有类别的样本总数
label_num={}
for data in train_label:
if data not in label_num:
label_num[data]=0
label_num[data]+=1
# 计算每类的概率
entropy=0.0
for cls,num in label_num.items():
prop=1.0*num/total_num
entropy+=prop *np.log2(prop)
# print('不纯度：', -entropy)
return [-entropy,label_num.items()]
# 计算某个特征中某个值的信息熵========================================
def calcute_value_entropy(data_train, data_label, index, value):
# data_train 训练样本
# data_label 样本标签
# index，特征索引，就是训练样本中的第几个特征，从0开始。
# value，需要计算信息熵的特征值。某些特征值在样本中只有一个。这种信息熵等于0，就是不纯度为0。
total_num=0 # 某个特征值在数据集中的个数
label_num={} # 特征值按照分类统计，鸢尾花A类多少个，B类多少个，C类多少个
i=0 # 用来索引data_train与data_label对应位置的数据
# 下面只对index的特征处理，其他特征不处理
for data in data_train[:,index]:
# 只对指定的特征值进行统计
if data == value:
total_num+=1 # 特征值总数递增
# 判定类别
label=data_label[I]
if label not in label_num:
label_num[label]=0
label_num[label]+=1
# 标签对应位置下移
I+=1
# 统计特征值的分类个数，下面计算熵
entropy=0.0
for cls,num in label_num.items():
prop=1.0*num/total_num
entropy+=prop *np.log2(prop)
return [-entropy,total_num,label_num.items()]
# 计算某个特征的信息熵========================================
def calcute_feature_entropy(data_train, data_label, index):
# data_train 训练样本
# data_label 样本标签
# index，特征索引，就是训练样本中的第几个特征，从0开始。
total_num=len(data_train) #
label_entropy={}
# 对训练样本遍历，统计计算每个值的信息熵(只对某个特征值统计)
for data in data_train[ :, index]:
if data not in label_entropy:
ent=calcute_value_entropy(data_train, data_label,index,data)
label_entropy[data]=ent
return label_entropy
# 加载数据集========================================
data,target=datasets.load_iris(return_X_y=True)
ents=calcute_feature_entropy(data,target,3)
for k,v in ents.items():
print(k,':',v)
0.2 : [-0.0, 28, dict_items([(0, 28)])]
0.4 : [-0.0, 7, dict_items([(0, 7)])]
0.3 : [-0.0, 7, dict_items([(0, 7)])]
0.1 : [-0.0, 6, dict_items([(0, 6)])]
0.5 : [-0.0, 1, dict_items([(0, 1)])]
0.6 : [-0.0, 1, dict_items([(0, 1)])]
1.4 : [0.5435644431995964, 8, dict_items([(1, 7), (2, 1)])]
1.5 : [0.6500224216483541, 12, dict_items([(1, 10), (2, 2)])]
1.3 : [-0.0, 13, dict_items([(1, 13)])]
1.6 : [0.8112781244591328, 4, dict_items([(1, 3), (2, 1)])]
1.0 : [-0.0, 7, dict_items([(1, 7)])]
1.1 : [-0.0, 3, dict_items([(1, 3)])]
1.8 : [0.41381685030363374, 12, dict_items([(1, 1), (2, 11)])]
1.2 : [-0.0, 5, dict_items([(1, 5)])]
1.7 : [1.0, 2, dict_items([(1, 1), (2, 1)])]
2.5 : [-0.0, 3, dict_items([(2, 3)])]
1.9 : [-0.0, 5, dict_items([(2, 5)])]
2.1 : [-0.0, 6, dict_items([(2, 6)])]
2.2 : [-0.0, 3, dict_items([(2, 3)])]
2.0 : [-0.0, 6, dict_items([(2, 6)])]
2.4 : [-0.0, 3, dict_items([(2, 3)])]
2.3 : [-0.0, 8, dict_items([(2, 8)])]
对上面不纯度不为0的样本子集继续递归，直到所有节点是叶子节点。
3. C4.5决策算法
-
C4.5决策算法的思想
以信息增益进行分类决策时，存在偏向于取值较多的特征的问题（因为总数多，样本概率取值其每个值的概率就小，总体值就小，从而信息增益值就大）。
为了解决这个问题，提出了使用信息增益比来作为特征选择的度量方法。
C4.5决策算法是ID3决策算法的优化，优化提现如下几个方面：
|-（1）特征选取的依据是：特征信息增益比最大；
|-（2）对决策树之后进行剪枝；
|-（3）能够处理离散型和连续型的属性类型，就是：将连续型的属性进行离散化处理；
|-（4）能够处理具有缺失属性值的训练数据； -
分裂信息熵
在介绍特征信息增益比，需要对上面的样本信息熵进行改进：
假设某个特征的样本值不同的是
|-
该信息熵为分裂信息熵，分裂信息熵与样本总体信息熵计算方式一样，只是这儿是对某个特征而言，而且概率计算方式也不同。
下面用代码来说明：
# 计算分裂信息熵
def calcute_split_entropy(data_train,index):
# data_train 训练样本
# data_label 样本标签
# index，特征索引，就是训练样本中的第几个特征，从0开始。
total_num=len(data_train) # 某个特征值在数据集中的个数
value_num={}
# 下面只对index的特征处理，其他特征不处理
for data in data_train[:,index]:
if data not in value_num:
value_num[data]=0
value_num[data]+=1
# 计算分裂熵
entropy=0.0
for _, num in value_num.items():
prop=1.0*num/total_num
entropy+=prop *np.log2(prop)
return -entropy
# 加载数据集========================================
data,target=datasets.load_iris(return_X_y=True)
ent=[
calcute_split_entropy(data,0),
calcute_split_entropy(data,1),
calcute_split_entropy(data,2),
calcute_split_entropy(data,3)]
# 打印分裂熵
print(ent)
[4.8220180883811645, 4.011709761218928, 5.033829378702226, 4.065662933799395]
- 特征信息增益比
信息增益比就是信息增益比与分裂信息熵的比值：
|-
下面可以计算鸢尾花数据的增益值比。
from sklearn import datasets
import numpy as np
# 计算总体信息熵========================================
def calcute_total_entropy(train_label):
# train_label：总体样本的输出标签
# 获取总得样本数
total_num=len(train_label)
# 循环得到所有类别的样本总数
label_num={}
for data in train_label:
if data not in label_num:
label_num[data]=0
label_num[data]+=1
# 计算每类的概率
entropy=0.0
for cls,num in label_num.items():
prop=1.0*num/total_num
entropy+=prop *np.log2(prop)
# print('不纯度：', -entropy)
return [-entropy,label_num.items()]
# 计算某个特征中某个值的信息熵========================================
def calcute_value_entropy(data_train, data_label, index, value):
# data_train 训练样本
# data_label 样本标签
# index，特征索引，就是训练样本中的第几个特征，从0开始。
# value，需要计算信息熵的特征值。某些特征值在样本中只有一个。这种信息熵等于0，就是不纯度为0。
total_num=0 # 某个特征值在数据集中的个数
label_num={} # 特征值按照分类统计，鸢尾花A类多少个，B类多少个，C类多少个
i=0 # 用来索引data_train与data_label对应位置的数据
# 下面只对index的特征处理，其他特征不处理
for data in data_train[:,index]:
# 只对指定的特征值进行统计
if data == value:
total_num+=1 # 特征值总数递增
# 判定类别
label=data_label[I]
if label not in label_num:
label_num[label]=0
label_num[label]+=1
# 标签对应位置下移
I+=1
# 统计特征值的分类个数，下面计算熵
entropy=0.0
for cls,num in label_num.items():
prop=1.0*num/total_num
entropy+=prop *np.log2(prop)
return [-entropy,total_num,label_num.items()]
# 计算某个特征的信息熵========================================
def calcute_feature_entropy(data_train, data_label, index):
# data_train 训练样本
# data_label 样本标签
# index，特征索引，就是训练样本中的第几个特征，从0开始。
total_num=len(data_train) #
label_entropy={}
# 对训练样本遍历，统计计算每个值的信息熵(只对某个特征值统计)
for data in data_train[ :, index]:
if data not in label_entropy:
ent=calcute_value_entropy(data_train, data_label,index,data)
label_entropy[data]=[ ent[0], ent[1] ]
# 计算整个特征的信息熵
feature_entropy=0.0
for _, v in label_entropy.items():
prop=1.0 * v[1] / total_num
feature_entropy+=prop * v[0]
return feature_entropy
# 计算特征的信息增益========================================
def calcute_gain_value(data_train, data_label):
feature_num=data_train.shape[1] # 特征数
# 样本总体信息熵
total_entropy=calcute_total_entropy(data_label)
gains=[]
for idx in range(feature_num):
entropy=calcute_feature_entropy(data,target,idx)
gain=total_entropy[0]-entropy
gains.append(gain)
return gains
# 计算分裂信息熵========================================
def calcute_split_entropy(data_train,index):
# data_train 训练样本
# data_label 样本标签
# index，特征索引，就是训练样本中的第几个特征，从0开始。
total_num=len(data_train) # 某个特征值在数据集中的个数
value_num={}
# 下面只对index的特征处理，其他特征不处理
for data in data_train[:,index]:
if data not in value_num:
value_num[data]=0
value_num[data]+=1
# 计算分裂熵
entropy=0.0
for _, num in value_num.items():
prop=1.0*num/total_num
entropy+=prop *np.log2(prop)
return -entropy
def calcute_all_split_entropy(data_train):
feature_num=data_train.shape[1]
ents=[]
for idx in range(feature_num):
ent=calcute_split_entropy(data_train,idx)
ents.append(ent)
return ents
# 加载数据集========================================
data,target=datasets.load_iris(return_X_y=True)
iris_gains=calcute_gain_value(data,target)
iris_split=calcute_all_split_entropy(data)
print(iris_gains)
print(iris_split)
ratio=[]
for i in range(len(iris_gains)):
ratio.append(iris_gains[i]/iris_split[I])
print(ratio)
[0.8769376208910578, 0.5108699641236061, 1.4463165236458, 1.4358978386754417]
[4.8220180883811645, 4.011709761218928, 5.033829378702226, 4.065662933799395]
[0.1818611222143841, 0.12734469703221554, 0.28731933779183344, 0.35317680340351865]
如果使用信息增益比，则分类特征选择第四个特征（[0.1818611222143841, 0.12734469703221554, 0.28731933779183344, 0.35317680340351865]）。由于评估了分裂度，对某个特征中值比较多的情况，使用分类信息熵作为分母，可以同比降低这种影响。
计算结果与sklearn一致。
- 离散化处理
如果按照上面的方式，对连续值得情况会出现很多子节点。为了避免这种情况，需要进行离散化处理。 离散处理的思路相对比较简单：
假设某个分类特征具有N个值。
|-（1）对某个分类特征的所有值进行排序（升序），得到。
|-（2）对相邻两个值取平均值，并使用这个平均值作为分类阈值，把特征的值分成两类，A={
} 与B={
}
|-（3）计算按照A、B分成两类的分类增益值，这样得到N-1个增益值；
|-（4） 取信息增益值最大那个作为分类阈值。
其中分类增益值计算公式为：
假设：A类的格式是,B类的个数是
，则信息增益为：
下面使用代码实现计算鸢尾花第一个节点的阈值，分类特征使用上面的计算结果，使用第四个特征。
注意：对于离散特征值，也可以采用二分的分组模式，每个分组的增益值最大，作为最终分组来划分直接点。
import numpy as np
from sklearn import datasets
def calcute_entrop(train_label):
# 统计类别
category_num={}
for label in train_label:
if label not in category_num:
category_num[label]=0
category_num[label]+=1
# 开始计算基尼系数
total_num=len(train_label)
gini=0.0
for _,num in category_num.items():
prop=1.0 * num/total_num
gini+=prop * ( 1.0 - prop )
return gini
def calcute_gini_split(train_data,train_label,index):
# 找到某个特征最大基尼系数的切分
data=np.hstack((train_data,train_label.reshape(train_label.shape[0],1)))
total_num=len(train_label)
gini={}
# 对index特征划分数据集
data_set=list(set(data[:,index]))
data_set=sorted(data_set)
for idx in range(len(data_set)-1):
x_=(data_set[idx] + data_set[idx+1]) /2.0
new_data = data[data[:,index].argsort()]
data1=new_data[new_data[:,index]<=x_]
data2=new_data[new_data[:,index]>x_]
gini1=calcute_gini(data1[:,-1])
gini2=calcute_gini(data2[:,-1])
gini_=1.0* len(data1) / total_num * gini1 + 1.0* len(data2) / total_num * gini2
gini[x_]=[gini_,len(data1), len(data2)]
return gini
data,target=datasets.load_iris(return_X_y=True)
#gini=calcute_gini_split(data,target,3)
#for k,v in gini.items():
# print(k,':',v)
# ====最小基尼系数
#re=min(gini.items(),key=lambda x:x[1])
for idx in range(data.shape[1]):
gini=calcute_gini_split(data,target,idx)
re=min(gini.items(),key=lambda x:x[1][0])
print(re)
0.15000000000000002 : 0.14906466204571436
0.25 : 0.1490646620457144
0.35 : 0.1490646620457144
0.45 : 0.14906466204571436
0.55 : 0.1490646620457144
0.8 : 0.14906466204571434
1.05 : 0.1490646620457144
1.15 : 0.1490646620457144
1.25 : 0.14906466204571436
1.35 : 0.14906466204571436
1.45 : 0.14906466204571436
1.55 : 0.1490646620457144
1.65 : 0.1490646620457144
1.75 : 0.14906466204571436
1.85 : 0.1490646620457144
1.95 : 0.1490646620457144
2.05 : 0.14906466204571436
2.1500000000000004 : 0.1490646620457144
2.25 : 0.1490646620457144
2.3499999999999996 : 0.14906466204571436
2.45 : 0.14906466204571436
- 剪枝
由于决策树的构建完全是依赖于训练样本，因此该决策树对训练样本能够产生完美的拟合效果。但这样的决策树容易过拟合。
解决过拟合问题的解决方案就是剪枝。，剪枝方法分为预剪枝和后剪枝两大类。
|-预剪枝：是在构建决策树的过程中，终止决策树分支，从而避免过多的节点产生。预剪枝方法虽然简单但实用性不强，因为很难精确的判断何时终止树的生长。
|-后剪枝：是在决策树构建完成之后，对那些置信度不达标的节点子树用叶子结点代替，该叶子结点的类标号用该节点子树中频率最高的类标记。
常见的后剪枝方法有：
|-CCP(Cost Complexity Pruning)
|-REP(Reduced Error Pruning)
|-PEP(Pessimistic Error Pruning)
|-MEP(Minimum Error Pruning)
剪枝的算法这里不介绍。
4.CART决策算法
CART算法与C4.5差不多，主要CART采用的是基尼系数。 对一个数据集来说，基尼系数计算方式为：
假设有个类别，第
个类别的概率为
|-
而且采用的是把数据集按照某个特征分成两部分处理，假设训练样本是
，则可以分成两个数据集
,则A特征在该划分模式下的基尼系数为：
|-
特征选择：所有二分中基尼系数最小的特征与对应的二分特征值。
- sklearnCART决策算法体验
sklearn实现的决策算法使用的就是CART算法，其典型结果就是采用二叉树。
下面是skleran二叉树决策算法的可视化结果
% matplotlib inline
import matplotlib.pyplot as plt
import numpy as np
from sklearn.tree import DecisionTreeClassifier
from sklearn import datasets
from sklearn.model_selection import train_test_split # 训练集切分
import sklearn
from sklearn import tree
from sklearn.externals.six import StringIO #数据缓冲
import pydot # 把数据转换为图像
data,target=datasets.load_iris(return_X_y=True)
# data,target=datasets.load_linnerud(return_X_y=True)
# data=data[0:100]
# target=target[0:100]
dtc=DecisionTreeClassifier(random_state=0,criterion='gini') # 为了保证输出结果的稳定性，需要random_state固定。
dtc.fit(data,target)
buff = StringIO()
# tree.export_graphviz(dtc,out_file=buff) # export_graphviz只能导出数据
tree.export_graphviz(dtc, out_file=buff, feature_names=['特征1','特征2','特征3','特征4'], class_names=['A类','B类','C类'], filled=True, rounded=True, special_characters=True)
#tree.export_graphviz(dtc, out_file=buff, feature_names=['特征1','特征2','特征3','特征4'], class_names=['A类','B类'], filled=True, rounded=True, special_characters=True)
(graph,)= pydot.graph_from_dot_data(buff.getvalue()) # 转换为图像
graph.write_svg("iris_gini.svg")
鸢尾花在基尼系数判别方式下的决策过程可视化
- 计算总体Gini系数
import numpy as np
from sklearn import datasets
def calcute_gini(train_label):
# 统计类别
category_num={}
for label in train_label:
if label not in category_num:
category_num[label]=0
category_num[label]+=1
# 开始计算基尼系数
total_num=len(train_label)
gini=0.0
for _,num in category_num.items():
prop=1.0 * num/total_num
gini+=prop * ( 1.0 - prop )
return gini
# 加载数据集
_,target=datasets.load_iris(return_X_y=True)
print(calcute_gini(target))
print(calcute_gini(target[0:100]))
print(calcute_gini(target[0:50]))
0.6666666666666667
0.5
0.0
- 计算一个数据集分成两个子集的基尼系数
import numpy as np
from sklearn import datasets
def calcute_gini(train_label):
# 统计类别
category_num={}
for label in train_label:
if label not in category_num:
category_num[label]=0
category_num[label]+=1
# 开始计算基尼系数
total_num=len(train_label)
gini=0.0
for _,num in category_num.items():
prop=1.0 * num/total_num
gini+=prop * ( 1.0 - prop )
return gini
def calcute_gini_split(train_data,train_label,index):
# 找到某个特征最大基尼系数的切分
data=np.hstack((train_data,train_label.reshape(train_label.shape[0],1)))
total_num=len(train_label)
gini={}
# 对index特征划分数据集
data_set=list(set(data[:,index]))
data_set=sorted(data_set)
for idx in range(len(data_set)-1):
x_=(data_set[idx] + data_set[idx+1]) /2.0
new_data = data[data[:,index].argsort()]
data1=new_data[new_data[:,index]<=x_]
data2=new_data[new_data[:,index]>x_]
gini1=calcute_gini(data1[:,-1])
gini2=calcute_gini(data2[:,-1])
gini_=1.0* len(data1) / total_num * gini1 + 1.0* len(data2) / total_num * gini2
gini[x_]=[gini_,len(data1), len(data2)]
return gini
data,target=datasets.load_iris(return_X_y=True)
#gini=calcute_gini_split(data,target,3)
#for k,v in gini.items():
# print(k,':',v)
# ====最小基尼系数
#re=min(gini.items(),key=lambda x:x[1])
for idx in range(data.shape[1]):
gini=calcute_gini_split(data,target,idx)
re=min(gini.items(),key=lambda x:x[1][0])
print(re)
(5.45, [0.4389063317634746, 52, 98])
(3.3499999999999996, [0.5462962962962963, 114, 36])
(2.45, [0.3333333333333333, 50, 100])
(0.8, [0.3333333333333333, 50, 100])
四、决策树的使用
- 分类
当样本根据决策树规则，路由到最后叶子节点的时候，如果最后节点不纯度为0，则直接返回类别，如果不纯度不为0，则返回概率最大的类别。
- 回归
当样本根据决策树规则，路由到最后叶子节点的时候，返回叶子节点的平均值或者中间值。
五、决策树算法实现
下面代码是直接抄袭别人的，实现的是ID3算法（使用的是纯Python，没有使用numpy）。
如果上面思路清楚后，实际实现二叉树相对来说思维比较简单。
from sklearn import datasets
import numpy as np
import math
def calcShannonEnt(trainData):
numEntries = len(trainData)
labelDic = {}
for trainLine in trainData:
currentLabel = trainLine[-1]
if currentLabel not in labelDic:
labelDic[currentLabel] = 0
labelDic[currentLabel] += 1
shannonEnt = 0.0
for key,value in labelDic.items():
prob = float(value)/numEntries
shannonEnt -= prob * math.log(prob,2)
return shannonEnt
def splitData(trainData,index,value):
subData = []
for trainLine in trainData:
if trainLine[index]==value:
reducedFeatVec = []
for i in range(0,len(trainLine),1):
if i==index:
continue
reducedFeatVec.append(trainLine[I])
subData.append(reducedFeatVec)
#print('subData',subData)
#print(len(trainData),len(subData))
return subData
def chooseBestFeature(trainData):
numFeatures = len(trainData[0])-1
baseEntropy = calcShannonEnt(trainData)
bestInfoGain = 0.0
bestFeature = -1
for i in range(0,numFeatures,1):
currentFeature = [temp[i] for temp in trainData]
uniqueValues = set(currentFeature)
newEntropy = 0.0
splitInfo = 0.0
for value in uniqueValues:
subData = splitData(trainData,i,value)
prob = float(len(subData))/len(trainData)
newEntropy += prob * calcShannonEnt(subData)
splitInfo -= prob * math.log(prob,2)
infoGain = (baseEntropy - newEntropy) / splitInfo
if infoGain > bestInfoGain :
bestInfoGain = infoGain
bestFeature = I
return bestFeature
def CreateTree(trainData):
classList = [temp[-1] for temp in trainData]
classListSet = set(classList)
if len(classListSet)==1:
return classList[0]
if len(trainData[0])==1:
return majorityCnt(classList)
bestFeature = chooseBestFeature(trainData)
myTree = {bestFeature:{}}
featureValues = [example[bestFeature] for example in trainData]
uniqueValues = set(featureValues)
for value in uniqueValues:
myTree[bestFeature][value] = CreateTree(splitData(trainData, bestFeature, value))
return myTree
def app_test(data_train,label_train,index):
# data_train：离散化数据集
# label_train: 训练数据集的标签
# index：离散化特征
# 为了避免排序产生的错乱，合并数据集与标签集
data = np.hstack((data_train,label_train.reshape(label_train.shape[0],1)))
# 按照指定特征排序（按照index排序）
return CreateTree(data)
# 加载数据集========================================
data,target=datasets.load_iris(return_X_y=True)
ent=app_test(data,target,3)
print(ent)
{3: {0.2: 0.0, 0.4: 0.0, 0.3: 0.0, 0.5: 0.0, 0.6: 0.0, 1.4: {2: {3.9: 1.0, 4.8: 1.0, 4.7: 1.0, 4.4: 1.0, 4.6: 1.0, 5.6: 2.0}}, 1.5: {2: {4.7: 1.0, 4.2: 1.0, 4.5: 1.0, 4.9: 1.0, 4.6: 1.0, 5.0: 2.0, 5.1: 2.0}}, 1.3: 1.0, 1.6: {0: {7.2: 2.0, 6.3: 1.0, 6.0: 1.0}}, 1.0: 1.0, 1.1: 1.0, 2.5: 2.0, 2.0: 2.0, 2.1: 2.0, 1.2: 1.0, 1.7: {0: {4.9: 2.0, 6.7: 1.0}}, 0.1: 0.0, 2.2: 2.0, 2.3: 2.0, 1.8: {1: {2.5: 2.0, 3.0: 2.0, 2.9: 2.0, 3.2: {0: {5.9: 1.0, 7.2: 2.0}}, 2.7: 2.0, 2.8: 2.0, 3.1: 2.0}}, 1.9: 2.0, 2.4: 2.0}}
四、决策树相关的集成算法
绝决策树与其他算法集成产生如下集成算法
|-（1）Bagging + 决策树 = 随机森林
|-（2）AdaBoost + 决策树 = 提升树
|-（3）Gradient Boosting + 决策树 = GBDT
1. 随机森林算法
（1）从原始训练集中使用Bootstraping方法随机有放回采样选出m个样本
（2）对m个样本采用决策树（也可以使用其他分类算法）建立分类器
（3）重复n次，产生n个分类器
（4）把测试样本对n个分类器执行运算，所以分类的结果中，选择分类器最多的类别为最终输出；
from sklearn.ensemble import RandomForestClassifier
from sklearn import datasets
from sklearn.model_selection import train_test_split # 训练集切分
data,target=datasets.load_iris(return_X_y=True)
train_data, test_data,train_target, test_target = train_test_split(data, target, test_size=0.4,shuffle=True)
# 使用训练样本训练
rfc = RandomForestClassifier(n_estimators=100,random_state=0)
data,target=datasets.load_iris(return_X_y=True)
rfc.fit(train_data,train_target)
print(rfc.score(test_data,test_target))
print(rfc.predict(test_data))
print(test_target)
0.9166666666666666
[0 2 2 1 1 1 0 0 0 0 2 2 2 0 1 2 1 1 2 0 2 0 2 2 2 2 2 1 2 2 2 1 2 2 1 1 1
2 2 1 0 0 1 0 2 0 1 2 1 1 2 1 1 2 1 0 2 1 0 0]
[0 2 2 1 2 1 0 0 0 0 2 1 2 0 1 2 1 1 2 0 2 0 2 2 2 2 2 1 2 2 1 1 2 2 1 1 1
2 2 1 0 0 1 0 2 0 1 2 1 1 2 1 1 1 1 0 1 1 0 0]
说明：
- 本主题，没有完整实现决策树的过程，在这里mark一下，有时间完整写一下这个算法，可以与sklearn的实现输出做一个比较。
- 随机森林等决策树相关的集成算法没有深入解释，后面在相关算法的时候，再深入说明。
- 本主题信息熵离散化二分，算出来的信息增益与信息增益比都有误差，与sklearn的结果匹配不上，估计是算某个特征的信息增益的时候，其中的标签按照是多叉方式的计算的，有时间需要调试一下。
- 实际很多机器学习的算法在sklearn都有实现，我们阐述这些原理，更多的是更好的调用二叉树。
- 可以考虑使用tensorflow实现一下，毕竟tensorflow更多的是偏向深度学习。
- 本主题没有实现多叉树与二叉树的完整实现，会单独开一个python数据结构之二叉树的主题来说明，并使用决策树作为使用背景。
