引子：一些机器学习算法（如线性回归）创建的模型需要拟合所有的样本数据。
问题：
1：数据特征众多且其间关系繁杂而密切，构建全局模型比较困难。
2：真实世界的数据多数是非线性的，无法用全局线性模型拟合。
解决方法：
将数据集划分为多个易于建模的子数据集，子数据集可以用各种技术建模。依然难以建模的子数据集可以继续划分。在这种划分方式下，树结构和回归法相当有用。

ID3

概述：ID3决策树可以有多个分支，但是不能处理特征值为连续的情况。决策树是一种贪心算法，每次选取的分割数据的特征都是当前的最佳选择，并不关心是否达到最优。在ID3中，每次根据“最大信息熵增益”选取当前最佳的特征来分割数据，并按照该特征的所有取值来切分，一旦按某特征切分后，该特征在之后的算法执行中，将不再起作用。ID3算法核心是根据“最大信息熵增益“原则选择划分当前数据集的最好特征。在建立决策树的过程中，根据特征属性划分数据，使得原本“混乱”的数据的熵(混乱度)减少，按照不同特征划分数据熵减少的程度会不一样。在ID3中选择熵减少程度最大的特征来划分数据（贪心），也就是“最大信息熵增益”原则。

ID3算法缺点：

1. ID3不能直接处理连续型特征。
2. 数据集切分过于迅速。
3. 信息增益作为特征选择标准的缺陷：信息增益在特征值多的特征上计算结果大于特征值少的特征，这会导致 ID3 偏向选择有较多分枝的特征，而该特征不一定是最优的选择。

CART

CART是分类回归树。

1. 决策树模型是将输入空间划分成若干个区域。CART是二叉树，每一次将区域二分，子区域递归。

2. CART树的损失函数： \(Loss = \min_{j, s}[\min_{c_1}L(y^{(i)}, c_1) + \min_{c_2}L(y^{(i)}, c_2)]\)

\(c_m\)是子区域上的均值： \(c_m = \frac{1}{N_m}\sum_{x_i \in R_m(j, s))}y_i, \ \ \ x \in R_m, \ \ m = 1, 2\)

\(x^(j)\): 选择第j个特征作为切分变量

s：选择该特征的特征值s作为切分点

\(R_m\)：划分出的子区域

所以在CART模型中，我们需要遍历输入特征\(x^{(j)}\)，找到最佳划分点s，即损失函数值最小。

CART算法

对于分类问题，采用基尼系数选择最优特征，同时决定该特征的最优划分点。

对于回归问题，常选用L2距离作为损失函数\(L(y^{(i)}, c)\)，这种回归树称为最小二乘回归树。

• 选择(j, s)

• 用选定的(j, s)划分区域并输出相应区域的均值

• 在两个子区域上递归1， 2步骤直到满足终止条件

• 将输入空间划分为M个区域\(R_1, R_2 ,..., R_M\)，生成决策树

Read more: