概述
决策树是一个有监督学习的一种算法，可以实现分类和回归任务。
决策树算法的本质是树形结构，可以看作是遵循if-then规则的集合。
决策树构建
1.特征选择
2.数据集最佳切分函数
3.切分数据集
1.特征选择
特征选择就是根据哪个特征来划分特征空间，其目的是选择对训练数据有分类能力的特征。那么如何选择最优的特征来划分呢？一般来说，随着划分过程的进行，最后决策树中的分支节点所包含的样本应该同属于一个类别。
衡量类别中样本的度量方式有：香农熵，增益率，基尼系数
ID3:信息增益
C4.5：信息增益率
CART: Gini系数
香农熵：
假设当前有n类样本，第i类样本为Xi，那么Xi的信息定义为：
image.png
熵：
image.png
信息增益：
信息增益指的是父节点的熵和其下所有子节点总信息熵的差。
计算公式：
image.png
2.最佳切分函数
根据最大信息增益，选择特征对训练数据进行切分。最大信息增益指的是信息下降最快的方向。
3.切分数据集
根据第二步，开始对数据集进行切分，直到最后没有可选择的特征切分，或者类别相同，即信息熵为0的时候。
