机器学习笔记-决策树算法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时的信息增益。（如果还有不明白的，可以参考一下吴军大神的数学之美那本书，里面会有详细的介绍）