1.什么是决策树？

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

2. 熵（Entropy）的概念：

抽象的“信息”该如何来度量？

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

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

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

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

3. 决策树归纳算法流程（ID3）

树以代表训练样本的单个结点开始。

如果样本都在同一个类中，则该结点成为树叶结点，并用该类标号。

否则，算法使用称为“信息增益”的基于熵的度量作为启发信息，选择能够最好地将样本分类的属性。该属性成为该结点的“测试”或“判定”属性。

在该版本的算法中，所有的属性都是分类的，即离散值。连续值属性必须进过离散化。

对测试属性的每个已知的值，创建一个分支，并据此划分样本。

算法使用同样的过程，递归地形成每个划分上的样本判定树。一旦一个属性出现在一个结点上，就不必在该结点的任何后代上考虑它。

递归划分步骤仅当下列条件之一成立时停止：

（a）给定结点的所有样本属于同一类。

（b）没有剩余属性可以用来进一步划分样本。在此情况下，使用多数表决。这涉及将给定的结点转换成树叶结点，并用样本中的多数所在的类来标记它。替换地，可以存放结点样本的类分布。

c）分枝：t e s t _ a t t r i b u t e = a i test\_attribute = a_{i}test_attribute=a i