机器学习之决策树学习笔记

决策树

一颗决策树重要组成部分，分为根节点、非叶子节点，叶子节点，分支。
根节点：第一个节点
非叶子节点（决策点）：代表测试的节点，对数据属性的测试
分支：代表测试的条件
叶子节点：代表分类后所获得的分类标记，最后的结果

决策树的构造过程：

构造决策树的过程分为训练阶段和测试阶段；训练阶段需要从给定的训练集数据中构造一颗决策树；测试阶段是将测试数据在构造出的决策树上进行测试。
那重点问题就来了，如果要构造一颗决策树，那决策树中的根节点如何进行确定呢？

衡量标准–熵

熵代表一个物体内部的混乱程度，对应到我们的数据中就是数据的混乱程度，如果数据越纯，混乱程度就越小，熵值越小；如果数据越杂乱，混乱程度就越大，熵值越大。熵值的大小就代表不确定性越大。

熵的公式

pi为i的概率
数据集A={1,1,1,1,1,1,2,2,2,3}，出现1的概率是6/10，2的概率是3/10,3的概率是1/10，根据熵的计算公式：

A数据集的熵等于 1.295

数据集B={1,1,1,1,1,2,2,2,3,4}，出现1的概率是5/10，2的概率是3/10,3的概率是1/10，4的概率是1/10；根据熵的计算公式：

B数据集的熵等于 1.685

对比而言，B的熵>A的熵，B的数据混乱程度大于A。

决策树的目的就是为了尽可能的用少的步骤得到好的结果。

通常我们可以算出原label的熵值，然后算出不同属性对应label的熵值；用原熵-（属性中不同值对应label的熵值*不同值得概率之和），这样就可以算出信息增益。

有些无关属性可能熵值为0，是的信息增益非常大；为了避免这种情况的干扰，引入信息增益率。

信息增益率= 信息增益/属性自身熵值

属性自身熵是不同值得熵值，可能还是比较难理解。那就用最经典的天气和打球的例子吧

样本中有14条数据，yes有9个，no有5个，那么原熵等于

结果为：0.940

举一个outlook的例子，

outlook属性的自身分为三种值，分别为sunny,overcast,rainy，它们对应的概率是5/14，4/14，5/14
,outlook的自身熵为

结果为：1.577

outlook中sunny的熵：
结果为：0.971
outlook中overcast的熵：

结果为：0
outlook中rainy的熵：

结果为：0.971

属性中不同值对应label的熵值*不同值得概率之和=5/140.971+04/14+5/140.971=0.693
outlook信息增益：=原熵（0.94）-属性中不同值对应label的熵值不同值得概率之和（0.693）=0.247
outlook信息增益率=outlook信息增益（0.247）/outlook的自身熵（1.577）=0.157

算清楚一个属性的信息增益和信息增益率之后，就可以算其他的，将算出的结果进行比较就可以选出根节点。其他的节点也可以通过该方法找出来。

除了上熵还可以用Gini系数来表示

决策树构造好之后，如何评价一个决策树可以用评价函数：C(T)=

Nt：叶子节点中样本数量
H(t):叶子节点的熵值

优化决策树的两种方式：
预剪枝：在构建决策树的过程时，提前停止剪枝。（可以设置决策树的深度）
后剪枝：决策树构建完成之后，然后剪枝

评价剪枝效果函数C(t)+&|Tleaf| ，前面的是评价函数，后面的是叶子节点的个数。叶子节点个数越多，损失越大。（&可以自行指定）

个人学习笔记，有不正确的地方欢迎大家指出，相互学习！