一 信息论基础

在说到熵之前，首先提一下信息量。

1.1 信息量的定义

某事件发生的概率小，则该事件的信息量大。

定义随机变量X的概率分布为P(X),X的信息量为：

如下图所示，一件事情发生的概率越高，其信息量越小，反之，则越大。

1.2 熵

对随机事件的信息量求期望，得到随机变量X的熵：

当对数底数是2时，单位是bit，当对数底数是e时，单位是nat(奈特)。同时，若P(x)=0，P(x)=0,则定义0log0=0。由熵定义可知，随机变量的熵只依赖于X的分布，而与X的取值无关。

1.3 两点分布的熵

当p=0或p=1时，随机变量完全没有不确定性。当p=0.5时，H(X)=1,熵取得最大值，随机变量的不确定性最大。
https://blog.****.net/qq_16000815/article/details/80902977 以上转自

以下转自https://www.cnblogs.com/kyrieng/p/8694705.html

1.4 联合熵

随机变量的取值个数越多，状态数也就越多，信息熵就越大，混乱程度就越大。当随机分布为均匀分布时，熵最大，且 0≤H(X)≤logn。稍后证明。将一维随机变量分布推广到多维随机变量分布，则其联合熵 (Joint entropy) 为：

1.5 条件熵

https://zhuanlan.zhihu.com/p/26551798

1.6 相对熵 也称KL散度 (Kullback–Leibler divergence)

1.7 信息增益

1.8 基尼不纯度

二 决策树的不同分类算法

https://www.cnblogs.com/wxquare/p/5379970.html

2.1 ID3

ID3由Ross Quinlan在1986年提出。ID3决策树可以有多个分支，但是不能处理特征值为连续的情况。决策树是一种贪心算法，每次选取的分割数据的特征都是当前的最佳选择，并不关心是否达到最优。在ID3中，每次根据“最大信息熵增益”选取当前最佳的特征来分割数据，并按照该特征的所有取值来切分，也就是说如果一个特征有4种取值，数据将被切分4份，一旦按某特征切分后，该特征在之后的算法执行中，将不再起作用，所以有观点认为这种切分方式过于迅速。ID3算法十分简单，核心是根据“最大信息熵增益”原则选择划分当前数据集的最好特征，信息熵是信息论里面的概念，是信息的度量方式，不确定度越大或者说越混乱，熵就越大。在建立决策树的过程中，根据特征属性划分数据，使得原本“混乱”的数据的熵(混乱度)减少，按照不同特征划分数据熵减少的程度会不一样。在ID3中选择熵减少程度最大的特征来划分数据（贪心），也就是“最大信息熵增益”原则。下面是计算公式，建议看链接计算信息上增益的实例。

ID3采用信息增益进行特征选择，信息增益越高的特征纯度越好。

2.2 C4.5算法

其增益率准则可能对取值数目较少的属性有所偏好。（见西瓜书）
但是C4.5使用了启发式方法，先从候选划分属性找出信息增益高于平均水平的属性。在从中选择增益高的。

2.3 Cart树

https://blog.****.net/u011067360/article/details/24871801

三 回归树原理

https://www.cnblogs.com/gczr/p/7191426.html

四 决策树防止过拟合手段

剪枝主要分为预剪枝和后剪枝。（参考西瓜书）


以及对模型进行正则化****及交叉验证等

五 模型评估

转载自 https://blog.****.net/weixin_40930842/article/details/88950043#42__160

六 sklearn参数详解

criterion : string, optional (default=”gini”)	字符型，可选，默认’gini’分裂节点的衡量准则，默认‘gini’,还支持信息增益的交叉熵（‘entropy’）
splitter : string, optional (default=”best”)l	用于在每个节点处选择拆分的策略。 支持的策略是“最佳”选择最佳分割和“随机”选择最佳随机分割。
max_depth : int or None, optional (default=None)	树的最大深度。 如果为None，则扩展节点直到所有叶子都是纯的或直到所有叶子包含少于min_samples_split样本
min_samples_split : int, float, optional (default=2)	拆分内部节点所需的最小样本数：如果是int，则将min_samples_spli视为最小数字。如果是float，则min_samples_split是一个分数，ceil（min_samples_split * n_samples）是每个分割的最小样本数。更改版本0.18：添加了分数的浮点值。
min_samples_leaf	叶子节点所需的最小样本数。 只有在每个左右分支中留下至少min_samples_leaf训练样本时，才会考虑任何深度的分裂点。 这可能具有平滑模型的效果，尤其是在回归中。如果是int，则将min_samples_leaf视为最小数字。如果是float，则min_samples_leaf是一个分数，ceil（min_samples_leaf * n_samples）是每个节点的最小样本数。更改版本0.18：添加了分数的浮点值。
min_weight_fraction_leaf: float，optional（默认= 0。）	在叶节点处的权重总和（所有输入样本）的最小加权分数。 当未提供sample_weight时，样本具有相同的权重。
max_features int, float, string or None, optional (default=None)	寻找最佳分割时要考虑的功能数量：如果是int，则在每次拆分时考虑max_features特征。如果是float，则max_features是一个分数，并且在每次拆分时都会考虑int（max_features* n_features）要素。如果是“auto”，则max_features = sqrt（n_features）。如果是“sqrt”，max_features = sqrt（n_features）。如果是“log2”，则max_features = log2（n_features）。如果为None，则max_features = n_features。 注意：在找到节点样本的至少一个有效分区之前，搜索分割不会停止，即使它需要有效地检查超过max_features的功能。
random_state：int, RandomState instance or None, optional (default=None)	如果是int，则random_state是随机数生成器使用的种子; 如果是RandomState实例，则random_state是随机数生成器; 如果为None，则随机数生成器是np.random使用的RandomState实例。
max_leaf_nodes : int or None, optional (default=None)	以最佳方式使用max_leaf_nodes种植树。 最佳节点定义为杂质的相对减少。 如果为None则无限数量的叶节点。
min_impurity_decrease：float，optional（默认= 0。）	如果该分裂导致杂质的减少大于或等于该值，则将分裂节点。
min_impurity_split float, (default=1e-7)	树木生长早期停止的门槛。 如果节点的杂质高于阈值，节点将分裂，否则它是叶子。
class_weight : dict, list of dicts, “balanced” or None, default=None	与{class_label：weight}形式的类相关联的权重。 如果没有给出，所有类都应该有一个权重。 对于多输出问题，可以按与y列相同的顺序提供dicts列表。
presort : bool, optional (default=False)	是否预先分配数据以加快拟合中最佳分割的发现。 对于大型数据集上的决策树的默认设置，将其设置为true可能会降低培训过程的速度。 当使用较小的数据集或受限深度时，这可以加速训练。

七 python绘制决策树

# To support both python 2 and python 3
from __future__ import division, print_function, unicode_literals

# Common imports
import numpy as np
import os

# to make this notebook's output stable across runs
np.random.seed(42)

# To plot pretty figures
%matplotlib inline
import matplotlib as mpl
import matplotlib.pyplot as plt
mpl.rc('axes', labelsize=14)
mpl.rc('xtick', labelsize=12)
mpl.rc('ytick', labelsize=12)

# Where to save the figures
PROJECT_ROOT_DIR = "."


def image_path(fig_id):
    return os.path.join(PROJECT_ROOT_DIR,fig_id)

def save_fig(fig_id, tight_layout=True):
    print("Saving figure", fig_id)
    if tight_layout:
        plt.tight_layout()
    plt.savefig(image_path(fig_id) + ".png", format='png', dpi=300)

from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier

iris = load_iris()
X= iris.data[:,2:]
y= iris.target 

tree_clf = DecisionTreeClassifier(max_depth=2)
tree_clf.fit(X,y)

from sklearn.tree import export_graphviz
export_graphviz(
 
tree_clf,
 
out_file=image_path("iris_tree.dot"),
 
feature_names=iris.feature_names[2:],
 
class_names=iris.target_names,
 
rounded=True,
 
filled=True
 
)

在程序命令行使用该指令

得到决策树图