1，决策树模型概述
决策树可以同时用于分类和回归两种业务处理。在分类问题上，表示基于特征对实例进行分类的过程。相比于朴素贝叶斯分类，决策树的优势在于不需要构造任何领域知识或参数设置。因此在实际应用中，对于探测式的知识发现，决策树更加适用。
举例如下：
决策树基于‘树’结构进行决策
每个内部节点对应某个属性上的测试。
每个分支对应于该测试的一种可能结果（即该属性的某个取值）。
每个‘叶节点’对应于一个‘预测结果’。
学习过程：通过训练样本的分来确定‘划分属性’。
预测过程：将测试示例从根节点开始，沿着划分属性所构成‘判定测试序列’下行，直到叶节点。
重点需要掌握的分类算法：ID3;C4.5；CART；RandomForest
2,算法流程与最佳属性选择
2.1决策树的基本流程
总体流程：
A，自根至叶的递归过程
B，在每个中间节点寻找一个‘划分’属性
划分的三种停止条件：
（1），当前节点包含的样本全属于同一类别。
（2），当前属性集为空，或是所有的样本在所有属性值上取值相同，无法划分。
（3），当前节点包含的样本集合为空，不能划分。
注：这里需要理解类别和属性指的概念，以西瓜为例，好瓜与坏瓜就是类别，瓜的甜度（不甜，微甜，甜）就是属性值。
那么当某个节点的西瓜全是好瓜或者坏瓜时，划分停止。
当瓜的甜度这个属性集里没有不甜，微甜，甜这些属性值，或者，不甜的瓜全是坏瓜，微甜与甜的瓜全是好瓜，那么划分也会停止。
或者甜度这个节点没有西瓜时，划分也会停止。
换成If...then的规则理解
2.2最佳属性选择方法
信息熵（entroy)是度量样本集合‘纯度’，最常用的一种指标，假定当前样本集合D中第k类样本所占的比例为Pk，则D的信息熵定义为：
信息熵的公式来源如下：
A，首先定义不确定性函数f是概率P的单调递降函数；两个独立符号所产生的不确定性应等于各自不确定性之和，即f（P1,P2)=f（P1)+f(P2)，同时满足这两个条件的函数f是对数函数，即f(P)=log(1/p)=-logp
B，在信源中，考虑的不是单一符号发生的不确定性，而是要考虑整个信源所有可能发生情况的平均不确定性。若信源符号有n种取值：U1…Ui…Un，对应概率为：P1…Pi…Pn，且各种符号的出现彼此独立。这时，信源的平均不确定性应当为单个符号不确定性-logPi的统计平均值（E），可称为信息熵，即
式中对数一般取2为底，单位为比特。但是，也可以取其它对数底，采用其它相应的单位，它们间可用换底公式换算。
信息增益直接以信息熵为基础，计算当前划分对信息熵所造成的变化。
接下来分别讲述ID3,C4.5和CART中最佳属性选择方法。
（1）ID3中使用信息增益（information gain)
信息增益指的是在一个条件下，信息不确定性减少的程度。信息增益的公式如下：
Dv的概念结合下面的西瓜例子来理解，本质上是一个样本集合。
以西瓜数据集为例，完全为划分前，好瓜与坏瓜的熵如下，为0.998。
通过‘色泽’属性划分后，属性‘色泽’的增益为6/17*1+6/17*0.918+5/17*0.722=0.889
那么‘色泽’的信息增益为0.998-0.889=0.109
(2)C4.5中使用信息增益率（gain ratio)
信息增益对取值数目较多的属性有所偏好，例如编号，他的信息增益是最大的，但是编号没有泛化能力。因此针对ID3信息增益的缺陷，产生了信息增益率的方式来选择最佳属性，用信息增益除以IV（a)来‘惩罚’属性值较多的属性。
（3）CART中使用基尼指数（gini index)
基尼指数的含义和熵很接近，基尼指数越大，包含的类别越杂乱。
注：本文为网易云课堂《机器学习微专业》学习笔记。
