免规则采集器列表算法( 从这篇开始，我将介绍决策树泰坦尼克号船员生存预测应用)

　　免规则采集器列表算法(

从这篇开始，我将介绍决策树泰坦尼克号船员生存预测应用)

　　数据挖掘系列决策树分类算法

　　从本文开始，我将介绍分类问题，主要介绍决策树算法、朴素贝叶斯、支持向量机、BP神经网络、惰性学习算法、随机森林和自适应增强算法、分类模型选择和结果评估。

　　本文首先介绍了分类问题的一些基础知识，然后主要介绍了决策树算法的原理和实现，最后用决策树算法做了一个泰坦尼克号船员生存预测应用。

　　一、分类基本介绍

　　分类问题自古以来就出现在我们的生活中。分类是数据挖掘的一个重要分支，在医学疾病识别、垃圾邮件过滤、垃圾邮件拦截、客户分析等各个方面都有广泛的应用。分类问题可以分为两类： 分类：分类是指对离散数据进行分类，比如根据一个人的笔迹判断一个人是男是女。这里只有两个类别，类别是一个离散的集合空间{Male ,female.

　　预测：预测是指对连续数据进行分类，比如预测明天8点的天气湿度。天气的湿度随时变化。8点钟的天气是一个特定的数值，不属于有限的采集空间。预测也称为回归分析，广泛应用于金融领域。

　　离散数据和连续数据的*敏*感*词*性，因此转换为连续处理方法；天气和湿度值的分段处理也转化为离散数据。

　　数据分类分为两步：

　　构建模型，使用训练数据集训练分类器；使用构建的分类器模型对测试数据进行分类。

　　一个好的分类器具有很好的泛化能力，即不仅可以在训练数据集上达到很高的准确率，而且可以在以前从未见过的测试数据集上达到很高的准确率。如果一个分类器只在训练数据上表现良好，而在测试数据上表现不佳，则该分类器已经过拟合了。它只是记录了训练数据，并没有捕捉到整个数据空间的特征。

　　二、决策树分类

　　决策树算法是通过树的分支结构来实现分类的。下图是决策树的示例。树的内部节点代表对某个属性的判断，节点的分支就是对应的判断结果；叶节点代表一个类标签。

　　上表是预测一个人是否会购买电脑的决策树。使用这棵树，我们可以对新记录进行分类。从根节点（年龄）开始，如果一个人的年龄是中年，我们直接判断这个人会买电脑。如果他是青少年，他需要进一步判断他是否是学生；如果他是老人，他需要进一步判断他的信用等级，直到叶节点可以确定记录类型。

　　决策树算法有一个优点，就是可以生*敏*感*词*们可以直接理解的规则。这是贝叶斯、神经网络等算法所不具备的特性；决策树的准确率也比较高，不需要背景知识。分类是一种非常有效的算法。决策树算法的变种有很多，包括ID3、C4.5、C5.0、CART等，但基本都差不多。我们先来看看决策树算法的基本思想：

　　算法：GenerateDecisionTree(D,attributeList)根据训练数据记录D生成决策树。

　　输入：数据记录D，收录类标签的训练数据集；

　　属性列表attributeList，候选属性集，用于判断内部节点中的属性。

　　属性选择方法AttributeSelectionMethod()，选择最佳分类属性的方法。

　　输出：决策树。

　　过程：

　　构造一个节点N；

　　如果数据记录 D 中的所有记录都具有相同的类别标签（表示为类别 C）：

　　然后将节点N标记为叶子节点为C，返回节点N；

　　如果属性列表为空：

　　然后将节点N标记为叶子节点作为D中类标签最多的类，并返回节点N；

　　调用 AttributeSelectionMethod(D,attributeList) 选择最佳分割准则 splitCriterion；

　　将节点 N 标记为最佳分裂准则 splitCriterion；

　　如果分裂属性的值是离散的，并且允许决策树分裂成多个分支：

　　从属性列表中减去split属性，attributeLsit -= splitAttribute;

　　为每个拆分属性取值 j：

　　D中满足j的记录集为Dj；

　　如果 Dj 为空：

　　然后新建一个叶子节点F，将其标记为D中类标签最多的类，将节点F挂在N下；

　　除此以外：

　　递归调用GenerateDecisionTree(Dj,attributeList)得到子树节点Nj，并将Nj挂在N下；

　　返回节点N；

　　算法的1、2、3步非常明显。后面会介绍步骤4的最佳属性选择函数。只有知道它才能找到一个判据，根据判断节点得到的子步骤 树的类别尽可能纯，这里的纯只收录一个类别标签；第五步，根据分裂准则设置节点N的测试表达式。第六步，构建多叉决策树时，离散属性在节点N及其子树中只使用一次，然后从可用属性列表中删除。例如，在上图中，使用属性选择函数，确定的最佳拆分属性是年龄。age有3个值，每个值对应一个分支。后面不会用到age这个属性。算法的时间复杂度为O(k*|D|*log(|D|))，k为属性个数，|D| 是记录集 D 中的记录数。

　　三、属性选择方法

　　属性选择法总是选择最好的属性作为分裂最多的属性，也就是让每个分支记录的类别尽可能的纯。它按照一定的标准对属性列表中的所有属性进行排序，以选择最佳属性。有很多方法可以选择属性。这里介绍三种常用的方法：信息增益、增益比、基尼指数。

　　信息增益

　　信息增益是基于香农的信息论，它找到的属性R有这样一个特点：属性R分裂前后的信息增益比其他属性最大。该信息的定义如下：

　　其中m代表数据集D中类别C的数量，Pi代表D中任意一条记录属于Ci的概率，计算时Pi=（D/|D|中Ci类别集合中的记录数） . Info(D) 表示将数据集 D 的不同类别分开所需的信息量。

　　如果你了解信息论，就会知道上面的信息Info其实就是信息论中的熵。熵代表不确定性的度量。如果某个数据集类别的不确定性越高，其熵就会越大。例如，我们将一个立方体A抛向空中，记住它落地时碰到地面的表面是f1，f1的值为{1,2,3,4,5,6}，熵为f1 是熵(f1)= -(1/6*log(1/6)+…+1/6*log(1/6))=-1*log(1) /6)=2.@ = -(1/4*log(1/4)+1/4*log(1/4)+1/4*log(1/ 4)+1/4*log( 1/4)) =-log(1/4)=2; 如果换成球C，记住碰到地面的表面当它落地时是f3，显然不管你怎么把它扔到地上，

　　有了上面对熵的简单理解，我们再来说说信息增益。假设我们选择属性 R 作为分割属性。在数据集D中，R有k个不同的值{V1,V2,...,Vk}，所以可以根据R的值将D分为k组{D1,D2,...,Dk} ，经过R分割后，将数据集D的不同类别分开所需的信息量为：

　　信息增益定义为分裂前后，两者信息量的唯一区别：

　　信息增益 Gain(R) 表示属性 R 为分类带来的信息量。我们寻找 Gain 的最大属性，使分类尽可能的纯粹，即最有可能将不同的类分开。但是，我们发现Info(D)的所有属性都是一样的，所以求最大Gain可以转化为求最新的InfoR(D)。这里引入Info(D)只是为了说明其背后的原理，为了便于理解，我们在实现过程中不需要计算Info(D)。例如，数据集D如下：

　　记录 ID 年龄输入等级 学生信用等级 是否购买电脑 1 青年高或不公平 2 青年高或好 否 3 中年高 否 一般 4 老年 否 一般 5 老年低 是 一般 6 老年低是 否 7 中 低年龄好 8 青少年 不公平 否 9 青少年低 是 一般 10 老年 是 正常 11 青少年 是 12 中年好 是 13 中年 高 正常 14 年长不好 否

　　这个数据集根据一个人的年龄、收入、他是否是学生和信用等级来确定他是否会购买计算机。即最后一栏“是否买电脑”是品类标准。现在我们使用信息增益来选择最佳分类属性，并计算信息量除以年龄：

　　整个公式由三个项组成。第一个学期是青年，14条记录中有5条是青年，其中2条（占2/5）购买电脑，3条（占3/5）@）>条不买电脑。第二项是中年，第三项是老年，同理还有：

　　可以得出，Info age(D)最小，即按age分割后，结果是最纯的类别。此时以年龄作为根节点的测试属性，按照青年、中年、老年分为三个分支。：

　　注意使用age属性后，后续操作不需要age，即从attributeList中删除age。以后按照同样的方法构造D1、D2、D3对应的决策子树。ID3算法使用基于信息增益来选择属性的方法。

　　增益比

　　信息增益选择方法有一个很大的缺陷。它总是倾向于选择具有更多属性值的属性。如果我们在上面的数据记录中添加一个姓名属性，假设14条记录中每个人的姓名都不同，那么信息Gain会选择姓名作为最好的属性，因为按姓名拆分后，每组只收录一条记录，并且每条记录只属于一个类别（要么买电脑要么不买），所以纯度最高，名称作为test split节点下有14个分支。但是这样的分类是没有意义的，它具有任何泛化能力。增益比对此进行了改进，它引入了一个拆分消息：

　　增益比定义为信息增益与分裂信息的比值：

　　我们找到具有最大 GainRatio 的属性作为最佳拆分属性。如果一个属性的值很多，那么SplitInfoR(D)就会很大，从而使得GainRatio(R)变小。但是，增益比也有缺点。SplitInfo(D)可以取0，没有计算意义；当 SplitInfo(D) 趋于 0 时，GainRatio(R) 的值变得不可靠。改进措施是在分母上加一。平滑，在此处添加所有拆分信息的平均值：

　　基尼系数

　　基尼指数是另一种衡量数据不纯性的指标，其定义如下：

　　其中m仍表示数据集D中类别C的个数，Pi表示D中任意一条记录属于Ci的概率，计算时Pi=(D中属于Ci类别的集合中记录数/| D|)。如果所有记录都属于同一类，则P1=1，Gini(D)=0，此时杂质最低。在CART（Classification and Regression Tree）算法中，使用基尼指数构造二叉决策树。对于每个属性，枚举其属性的非空真子集。属性R分裂后的基尼系数为：

　　D1是D的非空真子集，D2是D1在D中的补集，即D1+D2=D。对于属性R，有多个真子集，即GiniR(D)有多个值，但我们选择最小值作为R的基尼指数。最后：

　　我们将 Gini(R) 增加最大的属性作为最佳分割属性。/view/19848.html