任务三-决策树算法梳理

信息论基础（熵 联合熵 条件熵 信息增益 基尼不纯度）

熵

本是热力学中表征物质状态的参量之一，用符号S表示，其物理意义是体系混乱程度的度量。对于机器学习算法来说，熵指代香农熵，是一种不确定性度量。它是表示随机变量不确定的度量，是对所有可能发生的事件产生的信息量的期望。

联合熵

联合熵就是度量一个联合分布的随机系统的不确定度。

条件熵

条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。

信息增益

表示特征X使得类Y的不确定性减少的程度。（分类后的专一性，希望分类后的结果是同类在一起）
其中 I 为不纯度的度量，关于 N 的计算是划分后的个数加权。
I 为熵（Entropy）的时候，Delta 为信息增益。

基尼不存度

基尼不存度是指来自集合的某种结果随机应用于集合中某一数据的预期误差。（如果集合中所有结果属于同一类，则误差为0）

决策树的不同分类算法（ID3算法、C4.5、CART分类树）的原理及应用场景

ID3算法

内部使用信息熵以及信息增益来进行构建,每次迭代选择信息增益最大的特征属性作为分割属性。只支持离散的特征属性

• 优点：决策树构建速度快，实现简单
• 缺点：算法依赖样本中出现次数较多的特征属性,但是出现次数最多的属性并不一定最优

C4.5算法

使用信息增益率来构建,在树的构建过程中会进行剪枝操作的优化,能够自动完成对连续属性的离散化处理。选择信息增益率大的属性进行分割

• 优点：准确率较高,实现简单
• 缺点：对数据集需要进行多次顺序扫描和排序,效率较低。

CART算法

使用基尼系数作为数据纯度的量化指标来构建,选择GINI增益率来分割，越大的即作为当前数据集的分割属性.可用于分类和回归。（二叉树构建）

回归树原理

决策树防止过拟合手段

剪枝是决策树学习算法对付过拟合的主要手段。决策树剪枝的基本策略有“预剪枝”和“后剪枝”。

预剪枝

指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶节点。

后剪枝

指先从训练集生成一颗完整的决策树，然后自底向上地对非结点进行考察，若讲该结点对应的子树替换成叶节点能带来决策树泛化性能的提升，则将该子树替换成叶节点。

模型评估

自助法（bootstrap）：
训练集是对于原数据集的有放回抽样，如果原始数据集N，可以证明，大小为N的自助样本大约包含原数据63.2%的记录。当N充分大的时候，1-（1-1/N）^(N) 概率逼近 1-e^(-1)=0.632。抽样 b 次，产生 b 个bootstrap样本，则，总准确率为（accs为包含所有样本计算的准确率。

准确度的区间估计：
将分类问题看做二项分布，则有：
令 X 为模型正确分类，p 为准确率，X 服从均值 Np、方差 Np（1-p）的二项分布。acc=X/N为均值 p，方差 p（1-p）/N 的二项分布。acc 的置信区间：

sklearn参数详解，Python绘制决策树

DecisionTreeRegressor(criterion=“mse”,
            splitter=“best”,
            max_depth=None,
            min_samples_split=2,
            min_samples_leaf=1,
            min_weight_fraction_leaf=0.,
            max_features=None,
            random_state=None,
            max_leaf_nodes=None,
            min_impurity_decrease=0.,
            min_impurity_split=None,
            presort=False)

参数含义

criterion:string, optional (default=“mse”)

它指定了切分质量的评价准则。默认为’mse’(mean squared error)。

splitter:string, optional (default=“best”)

它指定了在每个节点切分的策略。有两种切分策咯：

1. splitter=‘best’:表示选择最优的切分特征和切分点。
2. splitter=‘random’:表示随机切分。

max_depth:int or None, optional (default=None)

指定树的最大深度。如果为None，则表示树的深度不限，直到
每个叶子都是纯净的，即叶节点中所有样本都属于同一个类别，
或者叶子节点中包含小于min_samples_split个样本。

min_samples_split:int, float, optional (default=2)

整数或者浮点数，默认为2。它指定了分裂一个内部节点(非叶子节点)

需要的最小样本数。如果为浮点数(0到1之间)，最少样本分割数为ceil(min_samples_split * n_samples)

min_samples_leaf:int, float, optional (default=1)

整数或者浮点数，默认为1。它指定了每个叶子节点包含的最少样本数。

如果为浮点数(0到1之间)，每个叶子节点包含的最少样本数为ceil(min_samples_leaf * n_samples)

min_weight_fraction_leaf:float, optional (default=0.)

它指定了叶子节点中样本的最小权重系数。默认情况下样本有相同的权重。

max_feature:int, float, string or None, optional (default=None)

可以是整数，浮点数，字符串或者None。默认为None。

1. 如果是整数，则每次节点分裂只考虑max_feature个特征。
2. 如果是浮点数(0到1之间)，则每次分裂节点的时候只考虑int(max_features * n_features)个特征。
3. 如果是字符串’auto’,max_features=n_features。
4. 如果是字符串’sqrt’,max_features=sqrt(n_features)。
5. 如果是字符串’log2’,max_features=log2(n_features)。
6. 如果是None，max_feature=n_feature。

random_state:int, RandomState instance or None, optional (default=None)

1. 如果为整数，则它指定了随机数生成器的种子。
2. 如果为RandomState实例，则指定了随机数生成器。
3. 如果为None，则使用默认的随机数生成器。

max_leaf_nodes:int or None, optional (default=None)

1. 如果为None，则叶子节点数量不限。
2. 如果不为None，则max_depth被忽略。

min_impurity_decrease:float, optional (default=0.)

如果节点的分裂导致不纯度的减少(分裂后样本比分裂前更加纯净)大于或等于min_impurity_decrease，则分裂该节点。

min_impurity_split:float

树生长过程中早停止的阈值。如果当前节点的不纯度高于阈值，节点将分裂，否则它是叶子节点。
这个参数已经被弃用。用min_impurity_decrease代替了min_impurity_split。

presort： bool, optional (default=False)

指定是否需要提前排序数据从而加速寻找最优切分的过程。设置为True时，对于大数据集
会减慢总体的训练过程；但是对于一个小数据集或者设定了最大深度的情况下，会加速训练过程。

属性

feature_importances: array of shape = [n_features]

特征重要性。该值越高，该特征越重要。
特征的重要性为该特征导致的评价准则的（标准化的）总减少量。它也被称为基尼的重要性

maxfeature: int

max_features推断值。

nfeatures：int

执行fit的时候，特征的数量。

noutputs : int

执行fit的时候，输出的数量。

Notes

控制树大小的参数的默认值（例如max_depth，min_samples_leaf等）导致完全成长和未剪枝的树，
这些树在某些数据集上可能表现很好。为减少内存消耗，应通过设置这些参数值来控制树的复杂度和大小。

方法

decision_path(X)

返回X的决策路径

fit(X, y)

在数据集(X,y)上使用决策树模型

get_params([deep])

获取模型的参数

predict(X)

预测数据值X的标签

predict_log_proba(X)

返回每个类别的概率值的对数

predict_proba(X)

返回每个类别的概率值（有几类就返回几列值）

score(X,y)

返回给定测试集和对应标签的平均准确率

参考资料

西瓜书

cs229吴恩达机器学习课程

李航统计学习

谷歌搜索