决策树可以用于分类与回归 分类 classification 与回归 regression 是机器学习中两种数值预测的形式，属于监督学习 Supervised Learning 的范围。大致区别可以用下面的表格来说明
| 属性 | 分类 | 回归 |
|---|---|---|
| 输出类型 | 离散的数据 | 连续的数据 |
| 目的 | 寻找决策面 | 寻找最优拟合曲线 |
| 评价标准 | 准确率accuracy | MSE,SSE |
属性信息选择度量
一种分裂准则，用来决定每一次的划分
信息增益
给定类标记的训练元组的数据分区D 对D中的元组分类所需要的期望信息为: $$Info(D) = -\sum_{i=1}^{m}p_{i}log_{2}(p_{i})$$ 其中，\(p_{i}\)是D中任意元组属于类\(C_{i}\)的非0概率使用以2为底的对数函数是因为信息用二进制编码。Info(D)又称为D的熵 entropy 当我们用属性A来划分后，可以得到按A来划分的期望信息： $$Info_{A}(D) = -\sum_{j=1}^{v}p_{i}\frac{|D_{j}|}{|D|}\times Info(D_{j})$$ 其中，v表示属性A下观测的不同值的数量，Dj包含D中A的值为aj的元素。简单的说就是这样划分之后的数量占比。 于是，信息增益定义为： $$Gain(A) = Info(D) - Info_{A}(D)$$ Gain(A)表示通过A上的划分我们得到了多少信息
增益率
那么考虑一种情况，每条数据都有一个独有的id，那么根据上面的信息增益，选取id作为分裂的属性信息增益应该是最大的。然而这样对于分类来说并没有任何作用。 增益率尝试使用分裂信息来将信息增益规范化 $$SplitInfo_{A}(D) = -\sum_{j=1}^{v}\frac{|D_{j}|}{|D|}\times log_{2}(\frac{|D_{j}|}{|D|})$$ 信息增益的度量基于同样划分所获得的信息，而分裂信息则考虑了该划分输出的数量。 增益率定义为： $$GainRate(A) = \frac{Gain(A)}{SplitInfo_{A}(D)}$$ 选择具有最大增益率的属性作为分裂属性。
基尼系数
基尼系数用来度量数据分区的不纯度： $$Gini(D) = 1 - \sum_{i=1}^{m}p_{i}^{2}$$
ID3
输入：训练数据集D，特征集A，阈值ϵ； 输出：决策树T。
若D中所有实例属于同一类Ck，则T为单结点树，并将类Ck作为该结点的类标记，返回T；
若A=∅，则T为单结点树，并将D中实例数最大的类Ck作为该结点的类标记，返回T;
否则，计算A中各特征对D的信息增益，选择信息增益最大的特征Ag； (1) 如果Ag的信息增益小于阈值ϵ，则置T为单结点树，并将D中实例数最大的类Ck作为该结点的类标记，返回T； (2) 否则，对Ag的每一可能值ai，依Ag=ai将D分割为若干非空子集Di，将Di中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树T，返回T；
对第i个子结点，以Di为训练集，以A−{Ag}为特征集，递归地调用步骤(1)~(3)，得到子树Ti，返回Ti。
C4.5
C4.5算法与ID3算法相似，C4.5算法是由ID3算法演进而来的。C4.5在生成的过程中，用信息增益率来选择特征。
使用悲观剪枝的算法，由完全生长的树剪去子树。使用错误率评估。使用训练集来评估错误率，通常加上惩罚项来调节。
CART
CART决策树的生成就是递归地构建二叉决策树的过程。CART决策树既可以用于分类也可以用于回归。
CART cost function for classification $$J(k, t_{k}) = \frac{m_{left}}{m}G_{left} + \frac{m_{right}}{m}G_{right}$$
Gleft/right指左右子集的不纯度，用基尼系数表示，mleft/right指左右子集的元素数量
CART使用代价复杂度剪枝算法，由完全生长的树剪去子树。 定义树的复杂度为树叶节点个数和树的错误率的函数，从树的底部开始，对每个内部节点N，计算N的子树的代价复杂度和剪去该子树，用一个树叶节点代替的代价复杂度，保留优化代价复杂度的方案。 *使用剪枝集，不同于训练集和验证集
在 Scikit-learn 中使用决策树
from sklearn.tree import DecisionTreeClassifier
from sklearn import datasets
iris = datasets.load_iris()
X = iris['data'][:, 2:]
y = iris['target']
tree_clf = DecisionTreeClassifier(max_depth=2)
tree_clf.fit(X, y)
将上面训练好的决策树可视化后，可以得到：
+--------------------------+
| petal length(cm) <= 2.45 |
| gini = 0.6667 |
| ... |
| class = setosa |
+--------------------------+
/ \
True / \ False
+--------------------------+ +--------------------------+
| gini = 0.0 | | petal length(cm) <= 1.75 |
| ... | | gini = 0.5 |
| class = setosa | | ... |
+--------------------------+ | class = versicolor |
+--------------------------+
/ \
/ \
+--------------------------+ +--------------------------+
| gini = 0.168 | | gini = 0.0425 |
| ... | | ... |
| class = versicolor | | class = virginica |
+--------------------------+ +--------------------------+