随机决策树

机器学习简介及决策树算法介绍黄恺一、什么是机器学习•机器学习是专门研究计算机怎样模拟或实现人类的学习行为，以获取新的知识或技能，重新组织已有的知识结构使之不断改善自身的性能。机器学习是人工智能的核心，它的目的是让极其具有自我改良的能力，用通俗的话来讲，就是具有学习的能力。机器学习与数据挖掘•相似点：都是数据分析的工具•不同点：数据挖掘是一种观念，即是从海量数据中发掘有用的信息；机器学习是数据挖掘的一种工具。机器学习是从方法而言的，数据挖掘是从目的而言的。关于机器学习的一些重要信息•数据集：UCI，亚马逊的publicdatasets•牛人：吴恩达，唐杰等关于机器学习的一些重要信息•书籍：《机器学习实战》•重要的会议、期刊：KDD，JMLR非监督学习半监督学习监督学习机器学习分类（一）监督学习•训练集——预测模型——对测试集进行判断•比如：贝叶斯分类，支持向量机分类聚类拟合机器学习分类（二）决策树•一种树状的图形结构，包括判断模块和终止模块。对输入数据进行一定的处理之后生成一种树形结构，可以对未知的事物按照属性进行分类的一种算法。树是有向树，以训练集的一个属性作为节点，这个属性对应的一个值做边。•它是机器学习算法的一种，一般都是自上而下生成，每个决策或事件都可能引出两个或多个事件，导致不同的结果。把这种决策分支化成图形很像一棵树的枝干，故称决策树。有4个人和他们的属性如下姓名性别年龄肤色小李男5黄小张男10黄小红女7黄Michael男12白•更一般的决策树是，给定某未知事物的一些属性，通过构建完成的决策树可以预测这个事物具体是哪一类。这个决策树是对隐形眼睛分类的，通过给定一个人眼睛的属性tearRate，astigmatic，prescript和age和它们的值，如normal,no,young,myope，则可以判断这个人适合的隐形眼镜是softID3决策树的优缺点•优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关的特征数据•缺点：可能会产生过度匹配问题，不能处理连续型属性随机决策树•决策树可以演化出一些新的适应不同场合的算法，比如随机决策树，模型树等•ID3决策树在选取分类属性的时候是通过计算每种属性的信息增益（熵）来得到需要分类的属性的，随机决策树在处理连续型属性的时候也保留了这样的特点。随机决策树•具体来说，就是在选取哪个属性进行划分的时候，使用随机函数来得到属性的编号。如果该属性是离散型属性，则消耗这个属性，将数据集按照这个离散型属性不同的取值划分成2个或两个以上的子集，再分别进行处理；如果选取到的是一个连续型属性，则计算在该属性下按照任意一个取值选取划分点，将数据集分成两部分，分别计算每种结果产生的信息增益。最后，按照哪个划分点划分产生的信息增益大，就选取哪个划分点。离散型连续型信息增益（香农熵的改变）•熵定义为信息的期望值。如果待分类事物可能划分在多个分类中，则符号x_i的信息定义为：l(x_i)=-log(p(x_i))•其中p(x_i)是选择该分类的概率信息增益•为了计算熵，需要计算所有可能值包含的信息期望值，通过下面的式子得到：•H=-Σp(x_i)log(p(x_i))实验•数据集：UCI上的adult数据集中的一小部分•数据集介绍：–该数据集共33520条信息，每条信息包括14个属性和一个分类–分类是用来判断某个人的年收入是5W美元以上还是以下的–属性有：年龄，工作类型，文凭，受教育年限，婚姻状况，职业，关系，人种，性别，资本收益，资本损失，每周工作时间，祖籍等共14个属性–实验的时候我分别取了前28个、前500个数据做实验。由于属性数量太大，我们使用前50个数据的所有14个属性，前500个数据的前5种属性。最后，为了验证本算法的正确性，选择了数据集的前2094个数据作训练集，另外选了379条数据作为测试集，用前面2094个数据得出的决策树来对这379条数据进行预测，并计算准确率实验•实验环境：windows7+python3.3IDLE+matplotlib(绘图工具)•实验方法：•1.从txt文档读取数据•2.编写计算某个数据集的香农熵的函数calcShannonEnt()•3.编写根据离散型属性将数据集划分成子集的函数splitDataSet()（此函数将消耗属性）•4.编写根据连续型属性将数据集划分成子集的函数cutDataSet_lessThan()和cutDataSet_moreThan()（此函数不消耗属性）•5.选择最佳划分点函数（对于连续型属性）chooseBestSplitPoint()：如果选择的是连续型属性，选择某个值进行划分，使划分之后产生最多的信息增益实验•6.编写构造决策树的递归函数createTree()：如果只剩一个属性供划分，则构造一个叶子节点（即终止模块），返回最多的那个分类；如果只剩一条信息，则构造一个叶子节点，返回它的分类值；否则根据现有属性的个数，随机选择一个属性，如果1.选择到的是离散型属性，则消耗这个属性，将数据集按照这个属性的不同取值划分成若干个子集，再在每个子集上递归调用构造决策树函数createTree()；2.选择到的是连续型属性，则分别根据这个属性的所有可能取值将数据集划分成两个子集，即这个属性的值大于等于选取的这个值或小于选取的这个值的子集，分别计算信息增益，选择得到信息增益最大的那个值作为真正的划分点，将数据集划分为两个子集，再分别在子集上调用createTree()函数实验•画出决策树：使用python插件matplotlib的注释工具画决策树（只使用前50条数据）•注：这是选择前28条数据画出的决策树。随机决策树每次画的图可能不一样取300条数据时画出的决策树实验结果•用2094条数据作出了决策树，由于节点太多，画出来没有意义。在长度为397条数据作的测试集验证准确率。实验的结果是，最终共有291条数据预测正确，正确率为：291/397=0.733•如果以这2094条数据自身作为测试集，正确率为100%，这说明随机决策树在这方面的性能还是很好的。实验代码•代码：E:\python33\src\random_Decision_Tree.py和E:\python33\src\treePlotter.py演示完毕•谢谢！