【机器学习】决策树

决策树(Decision Tree）是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。

特点：

属于非参数学习
支持多分类
有很好的解释性

参数化学习 &非参数化学习

算法本身是否对原始数据的分布提出假设

参数化： 线性回归
非参数化： KNN、SVM、逻辑回归、决策树

不会对原始数据提出假设的算法，可能会出现高方差；
会对原始数据提出假设的算法，可能会出现高偏差；

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets

iris = datasets.load_iris()

x = iris.data[:, 2:]
y = iris.target

from sklearn.tree import DecisionTreeClassifier

dTree = DecisionTreeClassifier(max_depth=2, criterion='gini')
dTree.fit(x, y)


def plot_decision_boundary(model, axis):
    x0, x1 = np.meshgrid(
        np.linspace(axis[0], axis[1], int((axis[1] - axis[0]) * 100)),
        np.linspace(axis[2], axis[3], int((axis[3] - axis[2]) * 100))
    )
    x_new = np.c_[x0.ravel(), x1.ravel()]
    y_predict = model.predict(x_new)
    zz = y_predict.reshape(x0.shape)
    from matplotlib.colors import ListedColormap
    custopm_map = ListedColormap(['#EF9A9A', '#FFF59D', '#90CAF9'])
    plt.contour(x0, x1, zz, cmap=custopm_map)


plot_decision_boundary(dTree, axis=[0.5, 7.5, 0, 3])

plt.scatter(x[y == 0, 0], x[y == 0, 1], color='r')
plt.scatter(x[y == 1, 0], x[y == 1, 1], color='g')
plt.scatter(x[y == 2, 0], x[y == 2, 1], color='b')
plt.show()

最优维度划分

信息熵

信息熵：不得不提香农这个大写的人啦！信息论里面的知识。在信息论里面，信息熵衡量信息量的大小，也就是对随机变量不确定度的一个衡量。熵越大，不确定性越大；信息熵是信息杂乱程度的量化。

#信息熵
def entropy(p):
    return -p*np.log2(p)-(1-p)*np.log2(1-p)

消除不确定信息程度越高，信息量越大；反之，越小。
m是m种消息
信息量I=log₂（m）

需要解决的问题：
1.使用哪个特征进行划分；
2.在划分时，用多大的数值进行；

基尼系数

总体内包含的类别越杂乱，GINI指数就越大（跟熵的概念很相似）。

#基尼系数
def gini(y):
    result=1.0
    counter=Counter(y)
    for num in counter.values():
        p=num/len(y)
        result-=p**2
    return result

信息熵 vs 基尼系数

1.信息熵的计算速度比基尼稍慢；
2.sklearn中默认是基尼系数；
3.大多数时两者没有特别的优劣。

决策树解决过拟合方案

如果决策树过于庞大，分支太多，可能造成过拟合。对应训练样本都尽可能的分对，也许样本本身就存在异常点呢？

指定深度d
节点的min_sample
节点熵值或者gini值小于阙值

熵和基尼值的大小表示数据的复杂程度，当熵或者基尼值过小时，表示数据的纯度比较大，如果熵或者基尼值小于一定程度数，节点停止分裂。
当所以特征都用完了
指定节点个数

当节点的数据量小于一个指定的数量时，不继续分裂。两个原因：一是数据量较少时，再做分裂容易强化噪声数据的作用；二是降低树生长的复杂性。提前结束分裂一定程度上有利于降低过拟合的影响

树剪枝：降低复杂度，减小过拟合
预剪枝：在决策树生成过程中，减少划分
后剪枝：先生成完整的决策树，再裁剪

随机森林

Bootstraping: 有放回采样

Bagging:有放回采样n个样本，建立分类器

一次采样一颗树，多次采样多棵树，构成一片森林，多个分类器共同决定。当有一个test时，代入所以的决策树，共同决策。

随机性的解释：

1. 数据的随机性

为每个树选取训练数据，随机按照比列有放回选择数据集

2. 特征的随机性

按照比列选取特征的个数