机器学习课程笔记（五）

三种划分边界的算法之三：Desicion Tree

Desicion Tree是把非线性的问题转化为多重线性问题进行处理的方法。

在以上的例子中，两类不同的点无法以一个线性的边界划分，但是通过问三个问题，就把边界以三条线段组合的方式描绘出来了。

在实际中，可能会遇到这样的情况：很多时候即使把分割的边界选得很细致，也无法做到在边界出只包含一类点。因此这个时候要设置一个阈值，当所包含的点的数量低于阈值时即停止划分。此外还有其它一些参数，具体可参考以下文档：

DT的参数介绍：http://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html#sklearn.tree.DecisionTreeClassifier

关于DT，还有一个问题是：选择何种分类方法。因为对于同一组数据可能有不同的分类法。

数据点只有两类，但是可以选择的维度有三个：grade\bumpiness\speed limit。

这时候要考虑每一种分类方法的信息增益（information gain),而为了计算它，要使用信息熵(Entropy)的概念。

信息熵的定义如下：

信息增益的定义如下：

其中pi代表不同类别的点对应的概率，计算时要先分别计算每一个节点的熵，加权平均后得到这种分类方法的熵，然后用初始节点的熵减去它，就是信息增益。在选择分类方法时应该选择信息增益最大的。