【2018-09-30】决策树

决策树发现数据模式和规则的核心是归纳算法。

决策树学习：

（1）特征选择

熵：信息量大小的度量（熵越大，随机变量的不确定性越大）

ai事件发生的概率

设随机变量（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|

Σ属性A的所有可能的值v

------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），连续的----回归树（平方误差最小化）