决策树本质上是一个classfication 问题的监督学习算法，其结构上分为根节点和叶节点，底层python 的实现可以参考机器学习实战一书，本质上是一个递归实现。
- 伪代码的介绍
假定一个训练集合D={（x1,y1),(x2,y2),...,(xm,ym)};
属性集合A={a1,a2,...,ad}.
有三种情况下，导致递归直接返回结果：（1)当前节点包含的样本全部属于同一个类别，无需进行划分；（2)当前属性为空，或者是所有样本在所有的属性上的取值相等，无法划分；（3)当前节点包含的样本集合为空，不能划分
- 决策树划分的原则和定量值
一般而言，随着划分的不断进行，希望决策树的分支点所包含的样本尽可能的属于同一类别，即节点的纯度要高，衡量纯度的标准为信息熵
信息熵有如下的定义：假定样本集合D中的第x类样本所占的比例之和为px，则D的信息熵为：
假定离散属性a有V个可能的取值{a1,a2,...,av}，若使用a对样本集合D来进行划分，则会产生v个分支节点，其中第v个分支节点包含了D中所有在属性a上取值为av的样本，记作Dv，且考虑到不同的分支节点所包含的样本数不同，给分支节点赋予权重|Dv|/|D|，即样本数越多的分支节点的影响越大
Gain(D,a)=H[x]-(v=1到v=v的和）|Dv|/|D|*Ent(Dv)
具体来讲，当有多个属性，每一个属性都对应多个属性值，那么就计算每一个属性的信息熵，哪一个属性的信息熵大，则选择该属性为决策树的节点
- 增益率
在周志华p78有一个例子，判断是否为好瓜，有17个样本，把每一个样本进行编号，作为一列，如果把该列也作为属性，那么它的信息增益应该最大，因为这样决策树就会产生17个分支，每一个分支的节点就包含一个样本，纯度达到最大，这样的决策树准确率高，但是不具备泛化能力，无法对新样本进行有效的预测
增益率的公式为：
Gain_ratio(D,a)=Gain(D,a)/IV(a)
其中，iv(a)=-(v=1到v=v的和）|Dv|/|D|*log2|Dv|/|D| (C4.5算法）
- 基尼指数（CART Classification and regression Tree 的简称，这是一种著名决策树的学习算法，分类和回归都可以使用）
其中属性a的基尼指数定义为:
Gini_index(D,a)=(v=1 到v=v的和)|Dv|/|D|Gini(Dv)
- 对过拟合的解决方法
采用预剪枝/后剪枝的方法来进行处理
周志华p81-p83对于此讲解十分清楚，感兴趣可以去拜读一下
下面介绍sklearn 官方文档
- criterion 可以使用"gini"或者"entropy"，前者就是上文代表的基尼系数，后者代表信息增益。一般说使用默认的基尼系数"gini"就可以了，即CART算法。
- splitter 可以使用"best"或者"random"。前者在特征的所有划分点中找出最优的划分点。后者是随机的在部分划分点中找局部最优的划分点。 默认的"best"适合样本量不大的时候，而如果样本数据量非常大，此时决策树构建推荐"random"
- max_depth 决策树的最大深度， 决策树的最大深度，默认可以不输入，如果不输入的话，决策树在建立子树的时候不会限制子树的深度。一般来说，数据少或者特征少的时候可以不管这个值。如果模型样本量多，特征也多的情况下，推荐限制这个最大深度，具体的取值取决于数据的分布。常用的可以取值10-100之间
- min_samples_split 这个值限制了子树继续划分的条件，如果某节点的样本数少于min_samples_split，则不会继续再尝试选择最优特征来进行划分。 默认是2 如果样本量不大，不需要管这个值。如果样本量数量级非常大，则推荐增大这个值
- min_samples_leaf 这个值限制了叶子节点最少的样本数，如果某叶子节点数目小于样本数，则会和兄弟节点一起被剪枝。 默认是1,可以输入最少的样本数的整数
- min_weight_fraction_leaf 这个值限制了叶子节点所有样本权重和的最小值，如果小于这个值，则会和兄弟节点一起被剪枝。 默认是0，就是不考虑权重问题。一般来说，如果我们有较多样本有缺失值，或者分类树样本的分布类别偏差很大，就会引入样本权重，这时我们就要注意这个值了。
- max_leaf_nodes 通过限制最大叶子节点数，可以防止过拟合，默认是"None”，即不限制最大的叶子节点数。如果加了限制，算法会建立在最大叶子节点数内最优的决策树。如果特征不多，可以不考虑这个值，但是如果特征分成多的话，可以加以限制，具体的值可以通过交叉验证得到。
- max_features The number of features to consider when looking for the best split 用于划分选取的最大特征值的个数
methods
- apply(X, check_input=True) Returns the index of the leaf that each sample is predicted as.
- decision_path(X, check_input=True) Return the decision path in the tree
- fit(X, y, sample_weight=None, check_input=True, X_idx_sorted=None) 其中，X为样本集合，y为所属的类标签，参数sample_weight 为样本的权重，默认为None,权重相同
- get_params(deep=True) 得到评估器的参数，deep 默认为True ,表示输出所有参数
- predict_log_proba(X) Predict class log-probabilities of the input samples X. 得到预测属于某一类别的log 值
- predict_proba(X, check_input=True) Predict class probabilities of the input samples X 得到预测属于某一类别的值
- score(X, y, sample_weight=None) X为测试集， y为测试集的真实的类别标签，返回的是测试结果准确度（即多少判断正确，多少判断错误）
下面来看一个简单的demo
import sklearn
from sklearn import tree#输出决策树
x=[[0,0],[2,2]]
y=[0,1]
clf=tree.DecisionTreeClassifier()#这是用于进行分类问题
clf=clf.fit(x,y)
#print (clf.predict_proba([[1,1]]))
#print (clf.apply(x)) 返回叶节点所在位置的索引
#print (clf.predict([[3,4]]))
x=[[0,0],[2,2]]
y=[0.5,2.5]#注意这时候标签是浮点类型的，且是不连续的
clf=tree.DecisionTreeRegressor()#就要用到回归决策树分类器
clf=clf.fit(x,y)
#print (clf.predict_proba([[1,1]]))
#print (clf.apply(x)) 返回叶节点所在位置的索引
print (clf.predict([[3,4]]))
最后是一个官方的实例，结合matplotlib的呈现
import sklearn
from sklearn.tree import DecisionTreeRegressor#输出回归决策树
import numpy as np
import matplotlib.pyplot as plt
rng=np.random.RandomState(1)#其中1为伪随机种子。只要随机种子一样，那么生成的序列就相同
x=np.sort(5*rng.rand(80,1),axis=0)#其中random.rand 的用处是生成一个指定形状的数组，np.sort 参数axis默认为-1，表示按照最后一行排序
#print (x) 最终生成了一组80个由小到大排列的数
"""
>>> a = np.array([[1,4],[3,1]])
>>> np.sort(a) # sort along the last axis
array([[1, 4],
[1, 3]])
>>> np.sort(a, axis=None) # sort the flattened array
array([1, 1, 3, 4])
>>> np.sort(a, axis=0) # sort along the first axis
array([[1, 1],
[3, 4]])
"""
y=np.sin(x).ravel()#np.sin(np.pi/2)得到[[1]],ravel的作用是降维的作用
y[::5]+=3*(0.5-rng.rand(16))# 80/5=16 利用rand 产生16个一维数组
# #print (y)
regr_1=DecisionTreeRegressor(max_depth=2)
regr_2=DecisionTreeRegressor(max_depth=5)#产生两个深度不同的树
regr_1.fit(x,y)
regr_2.fit(x,y)#分别训练两棵树
#ppredict
x_test=np.arange(0.0,5.0,0.01)[:,np.newaxis]#将1行多列的数组转化为多行一列的数组
y_1=regr_1.predict(x_test)
y_2=regr_2.predict(x_test)
#picture
plt.figure()#画布搭建
plt.scatter(x,y, s=20,marker='<',edgecolor='black',c='darkorange',label='data')
"""
其中的s可以理解为点的大小，c为颜色序列,当有多个点的时候，可以接受一个颜色组成的列表，每个点的颜色按照序列颜色生成
marker 表示生成的点的形状，默认为'o'
label 图像标签
"""
plt.plot(x_test, y_1, color="cornflowerblue",label="max_depth=2", linewidth=2)
plt.plot(x_test, y_2, color="yellowgreen", label="max_depth=5", linewidth=2)
plt.xlabel("data")
plt.ylabel("target")
plt.title("Decision Tree Regression")
plt.legend()
plt.show()
最终的图像展示如下
未完待续。。。。。。
网友评论