接下来介绍分类问题。 主要介绍决策树算法、朴素贝叶斯、支持向量机、BP神经网络、懒惰学习算法、随机森林和自适应增强算法、分类模型选择和结果评估。 共7篇，欢迎关注和交流。
本文首先介绍了分类问题的一些基本知识，然后主要论述决策树算法的原理、实现，最后利用决策树算法进行泰坦尼克号船员生存预测应用。
一、分类基本介绍类呼唤朋友，人呼唤人，分类问题自古以来就出现在我们的生活中。 分类是数据挖掘中的一个重要分支，广泛应用于医学疾病识别、垃圾邮件过滤、垃圾邮件拦截、客户分析等各个方面。 问题可分为两大类：
分类：分类是指离散数据的分类，例如，根据一个人的笔迹判别这是男是女，这里只有两个类别，类别是离散的集合空间{男、女}。 预测是指对连续的数据进行分类。 例如，预测明天8点天气的湿度状况。 天气的湿度随时在变化。 8点的天气是具体值，不属于有限集合空间。 预测又称回归分析，广泛应用于金融领域。 离散数据和连续数据的处理方法不同，但实际上他们之间是相互转换的。 例如，根据比较的某个特征值判断，如果值大于0.5则视为男性，如果值小于等于0.5则视为女性，从而可以转换为连续处理方式。 逐步处理天气湿度值会转换为离散数据。
数据的分类分为两个步骤。
建立模型，利用训练数据集训练分类器利用所建立的分类器模型对测试数据进行分类。 优秀的分类器具有很好的泛化能力，不仅可以在训练数据集上达到很高的正确率，而且在从未见过的测试数据集上也能达到很高的正确率。 如果一个分类器在训练数据上很好，但在测试数据上很烂，那么这个分类器已经拟合好了，只是把训练数据写下来，没有抓住整个数据空间的特征。
二、决策树分类决策树算法根据树的分支结构进行分类。 下图显示了一个决策树示例，它表示树中内部节点对某个属性的判断，并且该节点的分支是相应的判断结果。 叶子的节点表示一个类标。
上表是预测某人是否购买电脑的决策树。 利用这棵树，你可以对新的记录进行分类。 根据根节点(年龄)，如果一个人的年龄是中年，就需要直接判断这个人是否购买电脑，如果是青少年，就需要进一步判断他是否是学生。 如果是老年人，则需要进一步判断信用等级，直到叶节点能够判定记录的类别。
决策树算法是贝叶斯、神经网络等算法所没有的特性，具有能够制定人直接理解的规则的优点，决策树的精度也高，而且能够在不了解背景知识的情况下进行分类，因此是非常有效的算法。 决策树算法有ID3、C4.5、C5.0、CART等多种变种，但其基础都相似。 看看决策树算法的基本思路。
算法：根据通用诊断列表(d，属性列表)训练数据记录d生成决策树。 输入：训练数据集，包括数据记录d、集群目标； 属性列表attributeList，候选属性集，用于内部节点判断的属性.属性选择方法AttributeSelectionMethod (，选择最佳分类属性的方法.输出：决策树1根.过程：构建节点n； 数据记录d的所有记录的类标签相同时(标记为类c )，将节点n标记为叶节点c，返回节点n； 属性列表为空时：将节点n作为叶节点标记为d中类标签最多的类，返回节点n； 调用attributeselectionmethod(d，attributeList )选择最佳分裂准则splitCriterion； 将节点n标记为最佳分裂准则“分裂剪辑”； 如果分裂属性值离散，决策树可以进行多个分裂。 从属性列表中减去分裂属性后，attributeLsit -=splitAttribute； 将每个分裂属性值j:记d满足j的记录的集合设为Dj； 如果Dj为空，则创建新的叶节点f，标记d中类标签最多的类，并将节点f悬挂在n下； 否则，递归调用generatedecisiontree(DJ，attributeList )得到子树节点Nj，将Nj挂在n下； 返回节点n； 算法的1、2、3个步骤很明显，步骤4的最佳属性选择函数在后面会特别介绍，现在只知道它能找到一个标准，通过判断节点得到的子树的类尽可能的纯。 步骤5根据分裂准则设置节点n的测试表达式。 在步骤6中，在对应构建多叉决策树时，在节点n及其子树中只使用一次离散属性，使用后从可用属性列表中删除。 例如，在上图中，使用属性选择函数来确定最佳分裂属性是年龄。 年龄有三个值，每个值对应一个分支，年龄属性以后不再使用。 算法的时间复杂度为o(k*|D|*log )|D|)，k为属性数，|D|为记录集d的记录数。
trong>三、属性选择方法属性选择方法总是选择最好的属性最为分裂属性，即让每个分支的记录的类别尽可能纯。它将所有属性列表的属性进行按某个标准排序，从而选出最好的属性。属性选择方法很多，这里我介绍三个常用的方法：信息增益（Information gain）、增益比率（gain ratio）、基尼指数（Gini index）。
信息增益（Information gain）信息增益基于香浓的信息论，它找出的属性R具有这样的特点：以属性R分裂前后的信息增益比其他属性最大。这里信息的定义如下：
其中的m表示数据集D中类别C的个数，Pi表示D中任意一个记录属于Ci的概率，计算时Pi=(D中属于Ci类的集合的记录个数/|D|)。Info(D)表示将数据集D不同的类分开需要的信息量。
如果了解信息论，就会知道上面的信息Info实际上就是信息论中的熵Entropy，熵表示的是不确定度的度量，如果某个数据集的类别的不确定程度越高，则其熵就越大。比如我们将一个立方体A抛向空中，记落地时着地的面为f1，f1的取值为{1,2,3,4,5,6}，f1的熵entropy(f1)=-(1/6*log(1/6)+...+1/6*log(1/6))=-1*log(1/6)=2.58；现在我们把立方体A换为正四面体B，记落地时着地的面为f2，f2的取值为{1,2,3,4}，f2的熵entropy(1)=-（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，显然不管怎么扔着地都是同一个面，即f3的取值为{1}，故其熵entropy(f3)=-1*log(1)=0。可以看到面数越多，熵值也越大，而当只有一个面的球时，熵值为0，此时表示不确定程度为0，也就是着地时向下的面是确定的。
有了上面关于熵的简单理解，我们接着讲信息增益。假设我们选择属性R作为分裂属性，数据集D中，R有k个不同的取值{V1,V2,...,Vk}，于是可将D根据R的值分成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年龄(D)最小，即以年龄分裂后，分得的结果中类标最纯，此时已年龄作为根结点的测试属性，根据青少年、中年、老年分为三个分支：
注意，年龄这个属性用过后，之后的操作就不需要年龄了，即把年龄从attributeList中删掉。往后就按照同样的方法，构建D1,D2,D3对应的决策子树。ID3算法使用的就是基于信息增益的选择属性方法。
增益比率（gain ratio）信息增益选择方法有一个很大的缺陷，它总是会倾向于选择属性值多的属性，如果我们在上面的数据记录中加一个姓名属性，假设14条记录中的每个人姓名不同，那么信息增益就会选择姓名作为最佳属性，因为按姓名分裂后，每个组只包含一条记录，而每个记录只属于一类（要么购买电脑要么不购买），因此纯度最高，以姓名作为测试分裂的结点下面有14个分支。但是这样的分类没有意义，它没有任何泛化能力。增益比率对此进行了改进，它引入一个分裂信息：
增益比率定义为信息增益与分裂信息的比率：
我们找GainRatio最大的属性作为最佳分裂属性。如果一个属性的取值很多，那么SplitInfoR(D)会大，从而使GainRatio(R)变小。不过增益比率也有缺点，SplitInfo(D)可能取0，此时没有计算意义；且当SplitInfo(D)趋向于0时，GainRatio(R)的值变得不可信，改进的措施就是在分母加一个平滑，这里加一个所有分裂信息的平均值：
基尼指数（Gini index）基尼指数是另外一种数据的不纯度的度量方法，其定义如下：
其中的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)增量最大的属性作为最佳分裂属性。
总结
本来打算还讲一下实现的，今天要回家，帮家里收下谷子，本来买的前天的票的，台风影响京广线没走成，先写到这里，收拾东西去。9月30回来，再总结一下实现和实践，并持续后面的话题，欢迎持续关注。
参考文献：
[1]：HanJiaWei. Data Mining: concept and techniques.
感谢关注，欢迎回帖交流。
转载请注明出处：www.cnblogs.com/fengfenggirl
转载于:https://www.cnblogs.com/fengfenggirl/p/classsify_decision_tree.html