小强学AI之 - 3决策树（Decision Tree）

简介

决策树也是一种监督学习的算法，和贝叶斯，SVM类似。 既然是“树”，很自然的想到了二分。其实决策树就是根据特征值对数据集进行二分，二分后的节点称为了节点。对于每个节点上的样本可以再根据下一个特征值继续进行二分。以此类推。直到节点样本数量达到分类器参数值min_samples_split。 当然，这里只是形象的理解，其实，决策树还有更牛的地方，就是它可以计算最合理的使用特征值的顺序。以达到最佳的分类效果（后面会提到相关的两个概念，熵和信息增益）。

举例

如图，图中的数据并不能线性分割，此时，可以增加特征阈值，实现数据的二分。二分后的数据均可再线性可分。如下：

用法

用法参考： sklean-Decision Tree 使用方法如下：

# 从sklearn库导入类tree from sklearn import tree # 构造决策树分类器，最小样本分割数设置为40 clf = tree.DecisionTreeClassifier(min_samples_split=40) # 训练分类器（或者说对分类器进行数据拟合） clf.fit(features_train, labels_train) # 提供测试集查看分类器的精度 pred = clf.predict(features_test) # 导入sklearn库，metrics类中的accuracy_score方法 from sklearn.metrics import accuracy_score # 计算分类器的精度 acc = accuracy_score(pred, labels_test) print acc

决策树分类器参数：

class sklearn.tree.DecisionTreeClassifier(criterion='gini', splitter='best', max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features=None, random_state=None, max_leaf_nodes=None, min_impurity_split=1e-07, class_weight=None, presort=False)

其中，最小分割样本min_samples_split是指，当节点样本数小于等于此值时，将不再对此节点进行分类 实验证明，min_samples_split过小时，会导致过拟合，进而导致最后的精度反而降低。所以要合理选择参数min_samples_split的值。（PS.又是调参）

熵

entropy熵，它是测量样本中的不纯度（杂质度）。 引入其它变量特征可用来提高样本纯度。 熵公式：

其中，Pi是样本中，类i的比例，然后对所有类求和。 举例：（假设不考虑最小样本分割数量）在节点Nx有4个样本，样本中分别有2个样本属于A，2个样本属于B。那么，节点Nx的熵为：

熵与纯度是反义的。 有两种极端情况： 1.所有样本属于同一类，熵为0，纯度最高 2.所有样本均匀分布在各类中，熵为1，纯度最低

信息增益

熵是如何影响决策树绘制边界的。答案是，信息增益。 信息增益(Information Gain)是指，父项熵减去分割父项后生成的子项的熵的加权平均，用公式表示如下：

决策树的原理。决策树在进行训练时，考虑所有的训练样本和可用的所有的特征，然后根据特征计算信息增益，找到信息增益最大的特征，然后以这个特征进行分割。 同样举上面的例子： 我们已经知道节点Nx的熵为1，假设以Nx节点为父节点，依据特征Feature1进行对父项分割，得到子节点Ny和Nz。其中Ny中有2个样本属于A，1个样本属于B。然后，在Nz节点只有一样本，而这个样本属于B。 那么，节点Ny的熵是：

由于节点Nz只有一个样本，所有样本属于同一类，熵为0。 那么，如果根据Feature1分类的话，信息增益为：

假设， 我们使用特征Feature2分类，得到的信息增益为0.1 使用特征Feature3分类，得到的信息增益为1 那么，决策树可能会选择按特征Feature3分类。 决策树在进行训练时就是在计算最大的信息增益。它要考虑所有的样本数据及所有的特征。所以速度会慢。

对于参数criterion（规则），决策树分类器默认使用的是规则是gini。这也是一个测试不纯度的指标。也支持熵和信息增益。但需要手动输入。

所以决策树中的默认值gini还是和熵entopy的用法还不太一样的。 但两种效果都不错。

特点

训练数据的特征量越多，决策树就会越复杂。也容易过拟合。 训练时间也就越长。通常精度会越高。但过拟合的话精度反而会降低，甚至得不到想要的结果。所以，一定要防止过拟合。

总结

至此学习了三种监督学习算法。 其实还有下面几种： 1. k-nearest neighbors，非常简单直接，易于理解，适合新手 2. ataboost非常强大 3. random forest 后面两种是集成方法。它们一般是在很多决策树基础上建立的元分类器。所有会有很多分类器集合在一起，做出最后的决定。比如，ataboost需要结合决策树使用，建立在决策树基础上。 后两种算法类似，只是算法有点不同。

以上算法都来自于scikit-learn库。 具体可参考： K-NEAREST NEIGHBORS IN SCIKIT-LEARN sklearn - 1.11. Ensemble methods集成方法 sklearn - sklearn.ensemble.AdaBoostClassifier adaboost分类器 sklearn - 3.2.4.3.1. sklearn.ensemble.RandomForestClassifier随机森林分类器