监督学习---决策树

1. 决策树 (Decision Tree): 是一种树形归纳分类算法,通过对训练集数据的学习，挖掘出一定的规则，用于对测试集数据进行预测。

2. 决策树的学习目标：根据给定的训练数据集构建一个决策树模型，使它能够对实例进行正确的分类。

3. 决策树的结构：
   决策树提供了一种展示在什么条件下会得到什么类别这种规则的方法.
   决策树包括：根节点，内部节点，分支和叶子节点， eg：
   
   每个内部结点代表对某个属性的一次测试，每条分支代表一个测试结果，叶结点代表某个类.

4. 决策树学习的具体做法：每次选择feature时，都挑选择当前条件下最优的那个feature作为划分规则，即局部最优的feature。
   如何划分属性最优？
   我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”越来越高，可以高效地从根结点到达叶结点，得到决策结果
   

5. 信息增益-----信息熵
   “信息熵”用来描述信息的不确定性
   
   信息熵的计算公式：
   
   个人对信息熵的理解：看结果分成几类,对其各自种类所占的比例进行相关的计算(利用信息熵公式）。例如西瓜：结果是好瓜还是坏瓜坏瓜 （n=2)，再例如买电脑还是不买电脑，他们各自所占的比例又是多少。
   
   

6. 信息增益—条件熵：运用概率论的相关理论知识
   

7. 信息增益
   公式：信息增益 = 信息熵 - 条件熵
   个人理解信息增益的作用：对比各个属性的信息增益，而后对其进行排序，信息增益大的属性，越靠近根节点，依次类推

8. 信息增益率：

公式：

增益率准则对可取值数目较少的属性有所偏好
而信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题

扩展：著名的 C4.5决策树算法 综合了信息增益准则和信息率准则的特点：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的

9. 信息熵，条件熵与信息增益的运用例子：
   
   解：对图片进行优化：
   
   （1）求根结点的信息熵：结果（好瓜/坏瓜）：
   
   
   （2）求条件熵：以色泽为例
   看图分析色泽：
   

先求出色泽的三个分支的信息熵，再求色泽下各自的条件熵以获得色泽的条件熵总和

色泽条件熵的总和

（3）色泽的信息增益：

（4）信息增益率：
A. 由（3）得 ：色泽的信息增益Gain(D,色泽)= 0.109
B.青绿占色泽的 6/17
乌黑占色泽的 6/17
浅白占色泽的 5/17

C. 属性“色泽”的信息增益率为：

10. 案例一：
对西瓜–好瓜/坏瓜进行处理得出决策树模型

（1）分别求出不同属性的信息增益，方法如上面第8点所示，则可得：

其中，纹理>脐部>根蒂>敲声>触感
（2）建立决策树模型：


11. 案例二
买不买电脑问题进行处理以建立决策树模型

解：（1）买不买电脑的信息熵：
不买电脑（否）占了 5/14
买电脑（否）占了 9/14
则可得买不买电脑的信息熵：

（2）求各个属性的信息增益：

==> 以年龄这一属性为例：
A. 看图分析年龄

B. 年龄的条件熵的计算：

（3）年龄的信息增益的计算：

（4）同理可得：
Gain(收入）=0.029
Gain(学生）=0.152
Gain(信用）=0.048
则可得：年龄>学生>信用>收入
=>根节点：年龄

构建决策树：