"机器学习--决策树"

决策树是机器学习中比较经典的一个算法，基本思想是对有标记的样本训练集进行决策分类，形成一颗决策树，根据具体问题的划分，可以分为解决分类问题的决策树（即样本标记是离散值），和解决回归问题的决策树（样本标记是连续值）。本文分两部分，选择的实现工具是sklearn库（该库主要用的是cart算法建树过程）

一、分类问题

1.1 问题描述

已知有一些数据集$(x_1,x_2,…x_m)$,其中$x_i$为$(x_{i1},x_{i2},…x_{in})$的维向量，其标记为$y_k$。现在有一个新的数据$x$,需要判断它的标记为多少？

1.2 算法描述

决策树主要有ID3,C4.5 CART算法等方法。

1.2.1 基本思想

决策树的基本思想如下：

读入训练数据，选择训练数据中的某个特征作为分支点
按照前面选择的特征的取值，形成m个子树
再分别在m个子树上继续选择某个特征作为分支点
递归以上过程

所以问题的关键在于如何选择某个属性取当作分支点，这是上面提到的三种算法的主要区别之一。

ID3算法

ID3算法就是使用信息论里面的熵的概念来选择分支特征，意思就是我将所有的特征都跑一遍，看谁的特征的熵下降的多，就说明按这个分支进行的决策得到的结果纯度高。

$H(x)=-\sum_{i=1}^np_ilogp_i$

其中$p_i$的值通过样本的频率来确定，那么一个特征有m个取值，所以最后按这个属性进行分支后的熵就该进行个加权就行了，加权的量($q_i$)仍然是每个分支样本所占的频率：

$H_{tol}(x)=\sum_{i=1}^mq_iH_i(x)$

当然最后我要比较的是每个特征的熵的下降的量谁大，所以你还需要求出分支前的总量，然后相减

但是ID3有个问题就是对分支点的选择倾向于样本量大的分支，以及无法去判断特征值为连续值的问题。为了弥补这个问题，算法作者提出了C4.5

C4.5算法

定义增益率：

$IV(a)=-\sum_{i=1}^nw_ilogw_i$ w为特征a的取值为i的样本比上总样本数目。然后将增益的商除以这个属性的定植，就可以得到增益率。可以看出增益率的定义也有偏好，他便好那些样本量少的特征，所以在实际的运用中，是先使用ID3算法，找到一些在平均增益水平以上的特征，再在这些特征中使用增益率去找最好的特征最为分支点。相当于是先上去再下来，这样就扯平了。所以相比ID3是优化了不少。

1.2.2连续值和缺失值问题

特征值是连续值时候的处理，在ID4.5就比较自然了。假设特征a是连续值，但他的样本肯定是一列离散值，将这列离散值排序，对每个区间的中点作为特征选择，进行二分，相当于判断大于这个点和小于这个点。这样就把连续值问题转换为了离散值问题（每个值是二分的）。但是要注意的是在离散特征的分支过程中，特征将会越来越少，但连续的特征是可以多次作为分支点的。

缺失值的关键在于两点：

一是样本某些特征值缺失的情况下如何选择划分的特征

二是选定了划分特征后，对于在该特征上缺失特征的样本的处理

这两点都可以对增益率公式进行小小的加权改进就行了，加权值就是样本的频率，具体公式参考周志华老师的机器学习书籍。。。。懒得打了。。

1.2.3 剪枝处理

决策树算法非常容易出现过拟合问题，也就是样本的某些特征被强化了，这些特征并不是一般泛化模型下的特征，为了解决这个问题就需要进行剪枝处理，也就是让决策树的分支变少，一般就两种方法。

前剪枝 首先将样本集分为训练集合和测试集合（如何分类？后续会更新）。

当决策树在建树的过程中，用测试集合去做判断，如果分支后的正确率小于之前的正确率，则停止分支。似不似很简单，的确很简单。。。

后剪枝 同理首先将样本集分为训练集合和测试集合（如何分类？后续会更新）。

然后在完整的建树之后，从下往上进行剪枝，如果测试集的正确率小于剪枝前，则停止剪枝。

前剪枝容易出现欠拟合问题后剪枝的运算量又太大。那到底如何剪，请看继续往下看。。

1.2.4 CART算法

使用基尼系数来代替增益率

$Gni(D)=1-\sum_{i=1}^np_i^2$

$p_i$为第i个类别的概率，上面式子值越大说明这个样本的不纯度越大。

类别的概率一般通过该类别样本出现的频率去近似估计。

实际上CART算法可以看作是ID3或者C4.5的一种近似，CART算法为运算简单，一般我们就将某个特征分为两类，分类的依据是基尼系数最小的组合。

算法输入是训练集D，基尼系数的阈值，样本个数阈值。

输出是决策树T。

我们的算法从根节点开始，用训练集递归的建立CART树。

对于当前节点的数据集为D，如果样本个数小于阈值或者没有特征，则返回决策子树，当前节点停止递归。
计算样本集D的基尼系数，如果基尼系数小于阈值，则返回决策树子树，当前节点停止递归。
计算当前节点现有的各个特征的各个特征值对数据集D的基尼系数，对于离散值和连续值的处理方法和基尼系数见上面公式。缺失值的处理方法和上篇的C4.5算法里描述的相同。
在计算出来的各个特征的各个特征值对数据集D的基尼系数中，选择基尼系数最小的特征A和对应的特征值a。根据这个最优特征和最优特征值，把数据集划分成两部分D1和D2，同时建立当前节点的左右节点，做节点的数据集D为D1，右节点的数据集D为D2.
对左右的子节点递归的调用1-4步，生成决策树。

对于生成的决策树做预测的时候，假如测试集里的样本A落到了某个叶子节点，而节点里有多个训练样本。则对于A的类别预测采用的是这个叶子节点里概率最大的类别。

1.3 程序实现

sklearn中的决策树使用的是CART算法实现的。

分类决策树对应的类是

DecisionTreeClassifier

回归决策时对应的类是

DecisionTreeRegressor

1.3.1参数注意

DecisionTreeClassifier

特征选择标准criterion：可以使用”gini”或者”entropy”，前者代表基尼系数，后者代表信息增益。一般说使用默认的基尼系数”gini”就可以了，即CART算法。除非你更喜欢类似ID3, C4.5的最优特征选择方法。
特征划分点选择标准splitter：可以使用”best”或者”random”。前者在特征的所有划分点中找出最优的划分点。后者是随机的在部分划分点中找局部最优的划分点。默认的”best”适合样本量不大的时候，而如果样本数据量非常大，此时决策树构建推荐”random”
划分时考虑的最大特征数max_features：可以使用很多种类型的值，默认是”None”,意味着划分时考虑所有的特征数；如果是”log2”意味着划分时最多考虑$log_2N$ 个特征；如果是”sqrt”或者”auto”意味着划分时最多考虑$\sqrt{N}$ 个特征。如果是整数，代表考虑的特征绝对数。如果是浮点数，代表考虑特征百分比，即考虑（百分比xN）取整后的特征数。其中N为样本总特征数。一般来说，如果样本特征数不多，比如小于50，我们用默认的”None”就可以了，如果特征数非常多，我们可以灵活使用刚才描述的其他取值来控制划分时考虑的最大特征数，以控制决策树的生成时间。
决策树最大深max_depth： 决策树的最大深度，默认可以不输入，如果不输入的话，决策树在建立子树的时候不会限制子树的深度。一般来说，数据少或者特征少的时候可以不管这个值。如果模型样本量多，特征也多的情况下，推荐限制这个最大深度，具体的取值取决于数据的分布。常用的可以取值10-100之间。
内部节点再划分所需最小样本数min_samples_split： 这个值限制了子树继续划分的条件，如果某节点的样本数少于min_samples_split，则不会继续再尝试选择最优特征来进行划分。默认是2.如果样本量不大，不需要管这个值。如果样本量数量级非常大，则推荐增大这个值。我之前的一个项目例子，有大概10万样本，建立决策树时，我选择了min_samples_split=10。可以作为参考。
叶子节点最少样本数min_samples_leaf：这个值限制了叶子节点最少的样本数，如果某叶子节点数目小于样本数，则会和兄弟节点一起被剪枝。默认是1,可以输入最少的样本数的整数，或者最少样本数占样本总数的百分比。如果样本量不大，不需要管这个值。如果样本量数量级非常大，则推荐增大这个值。之前的10万样本项目使用min_samples_leaf的值为5，仅供参考。
叶子节点最小的样本权重和min_weight_fraction_leaf：这个值限制了叶子节点所有样本权重和的最小值，如果小于这个值，则会和兄弟节点一起被剪枝。默认是0，就是不考虑权重问题。一般来说，如果我们有较多样本有缺失值，或者分类树样本的分布类别偏差很大，就会引入样本权重，这时我们就要注意这个值了。
最大叶子节点数max_leaf_nodes：通过限制最大叶子节点数，可以防止过拟合，默认是”None”，即不限制最大的叶子节点数。如果加了限制，算法会建立在最大叶子节点数内最优的决策树。如果特征不多，可以不考虑这个值，但是如果特征分成多的话，可以加以限制，具体的值可以通过交叉验证得到。
类别权重class_weight：指定样本各类别的的权重，主要是为了防止训练集某些类别的样本过多，导致训练的决策树过于偏向这些类别。这里可以自己指定各个样本的权重，或者用“balanced”，如果使用“balanced”，则算法会自己计算权重，样本量少的类别所对应的样本权重会高。当然，如果你的样本类别分布没有明显的偏倚，则可以不管这个参数，选择默认的”None”
节点划分最小不纯度min_impurity_split：这个值限制了决策树的增长，如果某节点的不纯度(基尼系数，信息增益，均方差，绝对差)小于这个阈值，则该节点不再生成子节点。即为叶子节点。
数据是否预排序presort：这个值是布尔值，默认是False不排序。一般来说，如果样本量少或者限制了一个深度很小的决策树，设置为true可以让划分点选择更加快，决策树建立的更加快。如果样本量太大的话，反而没有什么好处。问题是样本量少的时候，我速度本来就不慢。所以这个值一般懒得理它就可以了。

DecisionTreeRegressor

特征选择标准criterion:可以使用”mse”或者”mae”，前者是均方差，后者是和均值之差的绝对值之和。推荐使用默认的”mse”。一般来说”mse”比”mae”更加精确。除非你想比较二个参数的效果的不同之处。
类别权重class_weight：不适合回归树

from sklearn import tree
X = [[0, 0], [1, 1]]
Y = [0, 1]
clf = tree.DecisionTreeClassifier()
clf = clf.fit(X, Y)

clf.predict([[2., 2.]])
clf.predict_proba([[2., 2.]])        #计算属于每个类的概率

1.3.2决策树的可视化

安装开源代软件： graphviz

安装pydotplus:

由于无法在anaconda中还没有更新库pydotplus所以需要用pip安装：

打开终端

source activate python3
pip install pydotplus

画决策树：

import pydotplus 
dot_data = tree.export_graphviz(clf, out_file=None) 
graph = pydotplus.graph_from_dot_data(dot_data) 
graph.write_pdf("tree.pdf")

二、回归问题

使用决策树解决回归问题的算法只能通过CART算法来解决。

首先我们要知道CART算法可以建立分类树或者回归树，分类树返回的值是离散值，回归树返回的值时连续值。

CART回归树和分类树的区别主要在于两点：

特征的连续值的处理方式不同
预测的方式不同

CART分类树的特征的连续值处理方式前面已经说过了，CART回归树的特征的连续值的处理是找到一点s,s将a特征样本集合划分为D1，D2，s满足: $min[min\sum_{x_i\in D1}(y_i-c_1)^2+min\sum_{x_i \in D2}(y_i-c_2)^2]$ 找最小的那个s，再找最小的属性a。

最后预测的时候，如果预测落在的叶子节点中有多个训练样本，则取训练样本的均值或者或者中位数作为输出。

#用回归决策树去模拟sin函数，随机生成一百个点去看下拟合状态
from sklearn import tree
import math
import matplotlib.pyplot as plt
import numpy as np
import random
x=[math.sin(i) for i in np.arange(0,10,0.1)]
y=[i for i in np.arange(0,10,0.1)]
plt.plot(y,x)
a=np.zeros((len(x),1))
for index,i in enumerate(y):
    a[index]=[i]   
reg=tree.DecisionTreeRegressor()
reg.fit(a,x)
y1=[]
for i in range(100):
    tmp=random.uniform(0,10)
    y1.append(tmp)
b=np.zeros((len(y1),1))
for index,i in enumerate(y1):
    b[index]=[i]
c=reg.predict(b)
plt.scatter(y1,c)