决策树发现数据模式和规则的核心是归纳算法。
决策树学习：
（1）特征选择
熵：信息量大小的度量（熵越大，随机变量的不确定性越大）
设随机变量（X，Y）联合分布P(X,Y)，条件熵H(Y|X)：表示在已知随机变量X的的条件下，随机变量Y的不确定性。
特征A对训练数据集D的信息增益，g(D,A)定义为集合D的经验熵：g(D,A)=H(D)-H(D|A)
互信息：H(Y)与H(Y|X)的差
决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
（2）决策树生成
----ID3算法
训练样本集合S，样本不同的类C1，C2，C3....Cn，则样本s属于类Ci的概率为：
P(si)=|Ci|/|S|
------C4.5算法
输入：训练数据集D，特征集A，阈值e
输出：决策树T
→如果D中所有实例都属于同一类型Ck，则置为单节点树，并将Ck作为该节点的类，返回T
→如果A为空，则置T为单节点书并将D中实例数最大的类Ck作为该节点的类，返回T
→否则，计算A中各特征对D的信息增益比，选择信息增益比最大的特征Ag
→如果Ag的信息增益比小于阈值e，则置为单节点树，并将D中实例数最大的类Ck作为该节点的类，返回T
→否则，对Ag的每一可能值ai，依Ag=ai将D分割为子集若干非空Di，将Di中实例数最大的类作为标记，构建子节点，由子节点及其子节点构成树T，返回T
→对节点i，以Di为训练集，以A→{Ag}为特征集，递归调用上述过程，得到子树Ti，返回Ti
（3）决策树修剪
极小化决策树整体的损失函数或代价函数。
设树的叶节点个数|T|，t是T的叶节点，则该叶节点有Nt个样本点，其中k类的样本点有Ntk
Ht(T)为叶节点t上的经验熵，α大于等于0损失函数：
经验熵：
树的剪枝算法：
输入：生成算法产生的整棵树T，参数α
输出：修剪后的子树Tα
计算每个节点的经验熵
递归地从树的叶节点向上回缩（设一组叶节点回缩到其父节点之前与之和的损失函数，如果Cα(Ta)与Cα(Tb)，如果Cα(Ta)小于等于Cα(Tb)，剪枝）
返回上一步，直至不能继续为止，得到损失函数最小的子树T
CART树(决策树生成，决策树剪枝)
目标变量是类别的------分类树（Ｇini index），连续的----回归树（平方误差最小化）
