决策树（decision tree）算法

*机器学习中分类和预测算法的评估：

• 准确率
• 速度
• 强壮性
• 可规模性
• 可解释性

1.什么是决策树/判定树（decision tree）？

       判定树是一个类似于流程图的树结：其中，每个内部节点表示在一个属性上的测试，每个分支代表一个属性输出，而每个树叶节点代表类或类分布。树的最顶层是根节点。

2.熵（entropy）概念

      信息是一个抽象的概念，那应该如何度量信息呢？

      1948年，香农提出了“信息熵”的概念

      一条信息的信息量大小和他的不确定性有直接关系，要搞清楚一键非常非常不确定的事情或者是我们一无所知的事情，需要了解大量信息==>信息量的度量就等于不确定性的多少

       例子：猜世界杯冠军，假如一无所知，才多少次？

       每一个队夺冠的几率是不相等的

       比特（bit）来衡量信息的多少

       在信源中，考虑的不是某一单个符号发生的不确定性，而是要考虑这个信源所有可能发生情况的平均不确定性。若信源符号有n种取值：U1…Ui…Un，对应概率为：P1…Pi…Pn，且各种符号的出现彼此独立。这时，信源的平均不确定性应当为单个符号不确定性-logPi的统计平均值（E），可称为信息熵：

       式中对数一般取2为底，单位为比特。但是，也可以取其它对数底，采用其它相应的单位，它们间可用换底公式换算。

       变量的不确定越大，熵也就越大。

3.决策树归纳算法（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作为第一个根节点。

4.ID3算法总结 

• 树以代表训练样本的单个结点开始（步骤1）
• 如果样本都在同一个类，则该结点成为树叶，并用该类标号（步骤2和3）
• 否则，算法使用成为信息增益的基于熵的地量作为启发信息，选择能够最好地将样本分类的属性（步骤6）。该属性成为该节点的“测试”或“判定”属性（步骤7）。
• 在算法的该版本中，所有的属性都是分类的，即离散值，连续属性必须离散化。
• 对测试属性的每个已知的值，创建一个分枝，并据此划分样本（步骤8-10）。
• 算法使用同样的过程，递归地形成每个划分上的样本判定树，一旦一个属性出现在一个结点上，就不必该结点的任何后代上考虑它（步骤13）。
• 递归划分步骤仅当下列条件之一成立停止：
• （a）给定结点的所有样本属于同一类（步骤2和3）。
• （b）没有剩余属性可以用来进一步划分样本（步骤4）。在此情况下，使用多数表决（步骤5）。
• 这涉及将给定的结点转换成树叶，并用样本中的多数所在的类标记它。替换地，可以存放结点样本的类分布。
• （c）分枝，test_attribute = a,没有样本（步骤11）。在这种情况下，以samples中的多数类创建一个树叶（步骤12）

5.其他算法

      C4.5 :Quinlan

      Classification and Regression Trees（CART）

      共同点：都是贪心算法，自上而下

      区别：属性选择度量方法不同（C4.5->(gain ratio)，CART->(gini index),ID3->(Information Gain)）

      如何避免overfitting呢？—>①先剪枝，②后剪枝

6.决策树的优点：

• 决策树易于理解和实现，人们在在学习过程中不需要使用者了解很多的背景知识，这同时是它的能够直接体现数据的特点，只要通过解释后都有能力去理解决策树所表达的意义。
• 对于决策树，数据的准备往往是简单或者是不必要的，而且能够同时处理数据型和常规型属性，在相对短的时间内能够对大型数据源做出可行且效果良好的结果。
• 易于通过静态测试来对模型进行评测，可以测定模型可信度；如果给定一个观察的模型，那么根据所产生的决策树很容易推出相应的逻辑表达式。

7.决策树的缺点：

• 对连续性的字段比较难预测。
• 对有时间顺序的数据，需要很多预处理的工作。
• 当类别太多时，错误可能就会增加的比较快。
• 一般的算法分类的时候，只是根据一个字段来分类。