决策树
模型
决策树的学习目标是根据给定的训练数据集，建立一个决策树，能够对实例进行正确分类。决策树算法通常是递归选择最优特征，使得这个特征能够最好的对数据进行分割。
一个决策树从根节点开始构建，选择最优特征，将数据分为K组，对每一个子组，再次从其他特征总选择最优的，直至达到退出条件，或数据基本不可再分。
生成的决策树可能出现过拟合现象，则需要剪枝。剪枝的基本原理是去除不必要的叶子节点，使得决策树从繁至简。
特征选择
如何评价一个特征是最优特征呢？
熵和条件熵
每一个特征对应一定的混乱程度，称为变量的熵，记作H(X)
H(x)=-∑Pi·log(Pi)
其中Pi是随机变量X可取的第i个值，熵值H(P)大于零小于等于log（N）
条件熵H(Y|X)定义为X给定条件下Y的条件概率分布的熵对X的数学期望；
如果说X的熵H(X)表示随机变量X的变化程度，H(Y|X)则表示，已知X时Y的变化程度，也就是在X的限定条件下Y的混乱程度。
信息增益
信息增益g(D,A) = H(D)-H(D|A)
这句话很好理解：特征值D有原始混乱程度，在引入新的信息A之后，D的混乱程度有所减小，信息增益表示特征A使得数据集D混乱程度减小的程度。信息增益值越大，则表示这一特征A越是具有分类能力，越是重要。
信息增益有时会由于取值问题产生偏差，故引入了信息增益比这一概念，
信息增益比是对信息增益的优化。
算法
生成决策树的最终结果应该是特征值和该特征值取值的
ID3
此算法即根据信息增益迭代计算在每个节点上，每个特征值的信息增益，从而选择出最佳特征，作为此节点的类别。
- 若数据集中所有实例属于同一类，则T为单节点树，返回T
- 若特征为空，将数据集T记为D中最大的类，返回该类
- 计算A中各个特征的信息增益，选择信息增益最大的特征Ag
- 若Ag的值小于阈值，回到2
- 对A的每一个可能值将D划分为非空子集，取其中最大的类作为标记
- 对第i个子节点，以Di为训练集，以A-{Ai}为特征集，递归调用1~5
C4.5
C4.5是用信息增益比代替了ID3中第三条的信息增益，其他都一样。
以上的算法用于生成分类决策树，对于每个可取的特征值，存在固定的类别，决策树还可以生成回归模型，对于取值在连续空间上的特征进行分类，选取最优分割点，将数据分成2类，CART算法生成的决策树树为二叉决策树。
CART
CART的特征节点满足对指定变量，取值为是或者否。一般地，左子树为是的分支，右子树为否的分支。
回归决策树的表达式
f(x) = ∑Cm·I(x∈Rm)
表达着这样的意义：回归树首先生成一个个特征，在特定的特种中选取一个最优分割点；模型表示在输入数据属于该单元时，返回该单元的值。
由于对于某一个固定的变量，其最优分割点是所有输入实例Xi对应的输出Yi 的算数平均值。选取最优特征和该特征的最优分割点在于求最小化值：
min[min∑(Yi-C1)^2 + min∑(Yi-C2)^2]
剪枝
对于CART树，剪枝的核心是从当前回归树的所有子树种选取【整体损失函数最小，也就是预测能力最强的】最优决策树。
