小强学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的用法还不太一样的。 但两种效果都不错。
特点
训练数据的特征量越多，决策树就会越复杂。也容易过拟合。
训练时间也就越长。通常精度会越高。但过拟合的话精度反而会降低，甚至得不到想要的结果。所以，一定要防止过拟合。
总结
至此学习了三种监督学习算法。
其实还有下面几种：
- k-nearest neighbors，非常简单直接，易于理解，适合新手
- ataboost非常强大
- 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随机森林分类器
