1. 什么是决策树/判定树（decision tree)?
判定树是一个类似于流程图的树结构：其中，每个内部结点表示在一个属性上的测试，每个分支代表一个属性输出，而每个树叶结点代表类或类分布。树的最顶层是根结点。
2. 构造决策树的基本算法
3. 熵（entropy）概念
香农指出，一条信息的信息量和它的不确定性之间有着直接的关系。因此可以使用信息熵来描述信息量的多少。
信息熵的定义为：设一个随机变量X，其可能的m种取值为x1,x2,⋯,xm，对于每一种取值的概率为：p1,p2,⋯,pm，那么随机变量X的不确定度，即信息熵，用H(X)表示：
变量的不确定性越大，熵也就越大
4. 决策树归纳算法 （ID3）
1970-1980， J.Ross. Quinlan, ID3算法
选择属性判断结点
信息获取量(Information Gain)：Gain(A) = Info(D) - Infor_A(D)
通过A来作为节点分类获取了多少信息
类似，Gain(income) = 0.029, Gain(student) = 0.151, Gain(credit_rating)=0.048
因为年龄（age）的信息获取量最大，所以选择age作为第一个根节点
不断重复上面的过程继续往下分，直到某一分支的样本都在同一个类（全部是yes或全部是no），则该结点成为树叶，并用该类标号。
当分到最后没有剩余属性可以用来进一步划分样本时，使用多数表决，将给定的结点转换成树叶，并用样本中的多数所在的类标记它（少数服从多少原则）。
5. 其他算法：
C4.5: Quinlan
Classification and Regression Trees (CART): (L. Breiman, J. Friedman, R. Olshen, C. Stone)
共同点：都是贪心算法，自上而下(Top-down approach)
区别：属性选择度量方法不同： C4.5 （gain ratio), CART(gini index), ID3 (Information Gain)
6. 树剪枝叶
避免overfitting：分的太细，深度太深，在训练集上表现的很好，但是在测试集上就表现的不理想。
解决方法：
- 先剪枝
分到一定的深度，纯度达到一定百分比，就不继续往下分了。 - 后剪枝
先把树建好，在根据一定的标准，剪掉最低下的叶子。
7. 决策树的优点：
直观，便于理解，小规模数据集有效
8.决策树的缺点：
处理连续变量不好
类别较多时，错误增加的比较快
可规模性一般
【注】：本文为麦子学院机器学习课程的学习笔记
