机器学习笔记—–决策树算法1

引言：今天来和大家谈谈决策树算法。决策的重要性，我想就不必我多言了吧。但是还是先请大家看一下知乎的这个问题，普通人如何通过训练提高决策能力，http://www.zhihu.com/question/49602855?location=35 ，然后我们在来聊一聊，计算机如何快速提高决策能力。我想以自己为主，计算机为辅的决策将会给我们的生活带来质的飞跃。比如我上文提到的月老算法？不就是让自己找到心怡的搞网恋对象了么。哈哈。。。。

我想能看到这篇博客的都应该知道二叉排序树吧，如图给你一个数字100，让你插进下图的二叉排序树，你如何决断?if x>8 右转？then if x>1o 继续右转？。是不是在你的思维中就会有这样的思维？这叫if then 思维，也就是编程思维。其实决策树就是这种if then 思维。不是0就是1喽。当然机器学习里的决策要考虑的比这个多得多，也复杂的多，但是核心思想就是这个，下面且听我慢慢道来。

决策树算法的分类学习过程包括两个阶段:树构造 ( Tree Building) 和树剪枝( Tree Pruning) 。

( 1) 树构造阶段。决策树采用自顶 向下的 递归方 式: 从 根 节点开始在每个节点上按照给定标准选择测试属性, 然后按照 相应属性的所有可能取值向 下建立 分枝、划分 训练样 本, 直 到 一个节点上的所有样本都被划分到同一个类, 或者某一节点中 的样本数量低于给定值时 为止。这一 阶段最 关键的 操作是 在 树的节点上选择最佳测试属性, 该属性可以将训练样本进行最 好的划分。如果利用一个特征进行分类的结果与随机分类的结果没有很大的差别，则称这个特征是没有分类能力的。经验上扔掉这样的特征对决策树学习的精度影响不大。（比如对于马蓉来说评价一个男人好坏可能就是那个男人帅一点?其实也没多帅。王宝强的老师敦煌，多金全是没有意义的特征，不参与评比？好吧，我又扯多了。。。。但是还是在这里支援一波宝强。哈哈）选择测试属性的 标准有 信息增 益、信 息增益 比、基 尼指数( Gini Index) 以及基 于距 离的 划分 等。此外, 测 试属 性 的取 值 可 以 是 连 续 的 ( Continuous) , 也 可 以 是 离 散 的 ( Discrete) , 而样本的类属性必须是离散的。

( 2) 树剪枝阶段。构造过程得到的 并不是 最简单、紧凑 的 决策树, 因为许多分枝反映的可能是训练数据中的噪声或孤立 点。树剪枝过程试图检测和去掉这种分枝, 以提高对未知数据 集进行分类时的准确性。树剪枝主要有先剪枝、后剪枝或两者 相结合的方法。树剪枝方法的 剪枝标准有最 小描述 长度原 则 ( MDL) 和期望错误率最小原 则等。前者对决 策树进 行二进 位 编码, 最佳剪枝树就是编码 所需二 进位最 少的树; 后 者计算 某 节点上的子树被 剪枝 后 出现 的期 望 错误 率, 由 此判 断是 否 剪 枝。

特征选择：

信息增益：

特征值A对训练数据集D的信息增益g（D,A），定义为集合D的经验熵H(D)与特征值A给定条件下D的经验条件熵H(D/A)之差，即：

其实意思就是，假如，给你100个人，让你猜测这一百个人中男人与女人的个数，那么我们是不是有很多种分法？我们姑且把这个不确定性设置为H(D)，现在假如又给你一个限制条件（我们设置为A），女人的个数是奇数个，那么现在是不是好判断一点了，也就是在知道A的情况下，我们对这一百个人的分类的不确定性就可以写成H(D/A)。那么就表示知道A时的信息增益。（如果还有不明白的，可以参考一下吴军大神的数学之美那本书，里面会有详细的介绍）

信息增益比：

特征A对训练数据集D的信息增益比定义为其信息增益g(D,A)与训练数据集D关于特征A的值的熵之比，即：

其实信息增益比的提出是为了解决，以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题，使用信息增益比可以对这一问题进行校正，这是特征选择的另一准则。

基尼指数：

分类问题中，假如有K个类，样本点属于第K类的概念为pk,那么概率分布的基尼指数定义为：

对于给定的样本集合D，其基尼指数为：

说明一下，是集合中属于第K类的样本子集，K是类的个数。

其中，信息增益，信息增益比，基尼指数作为特征值的判定分别衍生出了三个算法，ID3算法，C4.5算法，CART算法。至于树的剪纸过程，我会分别带到各个算法里去讲，且听下回分解。

(原创，如有转载请告知）