决策树

决策树就是利用if-then条件分支结构来分割数据的一种分类学习方法

信息论

信息熵

例：32个球队，其中一支夺冠的概率

其中包含的信息量应为：
H = -(p1 × log(2,p1) + p2 × log(2,p2) + … + p32 × log(2,p32))

• 其中，p1 , p2 , … , p32 分别是这 32 个球队夺冠的概率
• H是信息熵，单位是比特
• 一个系统越是混乱，信息熵就越高

当 32 个球队夺冠概率相同时，对应的信息熵等于5比特，这个例子中信息熵不可能大于5比特。

信息增益

特征A对训练数据集D的信息增益g(D,A)，定义为集合D的信息熵H(D)与特征A给定条件下D的信息条件熵H(D|A)之差，即公式为：

信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少的程度

常见决策树使用的算法

• ID3 算法：信息增益最大的准则
• C4.5算法：信息增益率
• CART算法：CART 算法的二分法可以简化决策树的规模，提高生成决策树的效率
  • 回归树：平方误差最小准则
  • 分类树：基尼系数最小准则

sklearn决策树API

class sklearn.tree.DecisionTreeClassifier(criterion=’gini’, max_depth=None,random_state=None)

• criterion：默认是’gini’系数，也可以选择信息增益的熵’entropy’
• max_depth：树的深度大小
• random_state：随机数种子

决策树的优缺点以及改进

优点：

• 简单的理解和解释，树木可视化。
• 需要很少的数据准备，其他技术通常需要数据归一化

缺点：

• 决策树学习者可以创建不能很好地推广数据的过于复杂的树，这被称为过拟合。
• 决策树可能不稳定，因为数据的小变化可能会导致完全不同的树被生成。

改进：

• 减枝CART算法
• 随机森林

随机森林

集成学习方法

• 集成学习通过建立几个模型组合的来解决单一预测问题。
• 它的工作原理是生成多个分类器/模型，各自独立地学习和作出预测。
• 这些预测最后结合成单预测，因此优于任何一个单分类的做出预测。

随机森林过程

在机器学习中，随机森林是一个包含多个决策树的分类器，并且其输出的类别是由个别树输出的类别的众数而定。

根据下列算法建造每棵树：

• 用N来表示训练用例（样本）的个数，M表示特征数目。
• 输入特征数目m，用于确定决策树上一个节点的决策结果；其中m应远小于M。
• 从N个训练用例（样本）中以有放回抽样的方式，取样N次，形成一个训练集（即bootstrap取样），并用未抽到的用例（样本）作预测，评估其误差。

为什么要有放回地抽样？
如果不是有放回的抽样，那么每棵树的训练样本都是不同的，都是没有交集的，这样每棵树都是“有偏的”，都是绝对“片面的”（当然这样说可能不对）。也就是说每棵树训练出来都是有很大的差异的；而随机森林最后分类取决于多棵树（弱分类器）的投票表决。

随机森林API

class sklearn.ensemble.RandomForestClassifier(n_estimators=10, criterion=’gini’,max_depth=None, bootstrap=True, random_state=None)

• n_estimators：integer，optional（default = 10） 森林里的树木数量
• criteria：string，可选（default =“gini”）分割特征的测量方法
• max_depth：integer或None，可选（默认=无）树的最大深度
• bootstrap：boolean，optional（default = True）是否在构建树时使用放回抽样

随机森林的优点

• 在当前所有算法中，具有极好的准确率
• 能够有效地运行在大数据集上
• 能够处理具有高维特征的输入样本，而且不需要降维
• 能够评估各个特征在分类问题上的重要性
• 对于缺省值问题也能够获得很好得结果