数据挖掘中的分类预测之决策树算法.docx

《数据挖掘中的分类预测之决策树算法.docx》由会员分享，可在线阅读，更多相关《数据挖掘中的分类预测之决策树算法.docx（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据挖掘中的分类预测之决策树算法分类与预测餐饮企业经常会碰到下面的问题怎样预测将来一段时间内哪些顾客会流失哪些顾客最有可能成为VIP客户怎样预测一种心产品的销售量和在哪种类型的客户中会较受欢送除此之外餐厅经理需要通过数据分析来解析具有某些特征的顾客的消费习惯/这些都是分类与预测的例子。常见的分类预测算法贝叶斯贝叶斯Bayes分类算法是一类利用概率统计知识进展分类的算法如朴素贝叶斯NaiveBayes算法。这些算法主要利用Bayes定理来预测一个未知类别的样本属于各个类别的可能性选择其中可能性最大的一个类别作为该样本的最终类别。决策树决策树是用于分类以及预测的主要技术之一决策树学习是以实例为根底

2、的归纳学习算法它着眼于从一组无次序、无规那么的实例中推理出以决策树表示的分类规那么。人工神经网络人工神经网络ArtificialNeuralNetworksANN是一种应用类似于大脑神经突触联接的构造进展信息处理的数学模型。在这种模型中大量的节点或者称神经元或者单元之间互相联接构成网络即神经网络以到达处理信息的目的。支持向量机支持向量机SVMSupportVectorMachine是Vapnik根据统计学习理论提出的一种新的学习方法43它的最大特点是根据构造风险最小化准那么以最大化分类间隔构造最优分类超平面来进步学习机的泛化才能较好地解决了非线性、高维数、部分极小点等问题。决策树简介决策树(D

3、ecisionTree)是一个预测模型他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象而每个分叉途径那么代表的某个可能的属性值而每个叶结点那么对应从根节点到该叶节点所经历的途径所表示的对象的值。决策树仅有单一输出假设欲有复数输出可以建立独立的决策树以处理不同输出。数据挖掘中决策树是一种经常要用到的技术可以用于分析数据同样可以以用来作预测。例如记录根据上述数据构造出如下决策树信息熵、条件熵以及信息增益信息熵信息熵也称为香农熵是随机变量的期望。度量信息的不确定程度。信息的熵越大信息就越不容易搞清楚。处理信息就是为了把信息搞清楚就是熵减少的经过。决定信息的不确定性或讲复杂程度主

4、要因素是概率。我们要获得随机变量D的取值结果至少要进展1次试验试验次数与随机变量D可能的取值数量(2种)的对数函数Log有联络。Log21(以2为底)。因此熵的计算公式是条件熵条件熵是通过获得更多的信息来消除一元模型中的不确定性。也就是通过二元或者多元模型来降低一元模型的熵。我们知道的信息越多信息的不确定性越小。例如只使用一元模型时我们无法根据用户历史数据中的购置频率来判断这个用户本次是否也会购置。因为不确定性太大。在参加了促销活动商品价格等信息后在二元模型中我们可以发现用户购置与促销活动或商品价格变化之间的联络。并通过购置与促销活动一起出现的概率以及不同促销活动时购置出现的概率来降低不确定性

5、。以下公式为属性A的信息条件熵。用属性A出现的概率乘以属性A确定的情况下相应分类的信息熵。信息增益信息增益用来衡量信息之间相关性的指标。用于度量属性A降低样本集合X熵的奉献大小。信息增益越大不确定性越小越适于对X分类。详细的计算方法就熵与条件熵之间的差。公式如下ID3算法原理奥卡姆剃刀OccamsRazor,OckhamsRazor又称“奥坎的剃刀是由14世纪逻辑学家、圣方济各会修士奥卡姆的威廉WilliamofOccam约1285年度至1349年度提出他在?箴言书注?2卷15题讲“切勿浪费较多东西去做用较少的东西同样可以做好的事情。简单点讲便是besimple。ID3算法IterativeD

6、ichotomiser3迭代二叉树3代是一个由RossQuinlan创造的用于决策树的算法。这个算法便是建立在上述所介绍的奥卡姆剃刀的根底上越是小型的决策树越优于大的决策树besimple简单理论。尽管如此该算法也不是总是生成最小的树形构造而是一个启发式算法。OK从信息论知识中我们知道期望信息越小信息增益越大进而纯度越高。ID3算法的核心思想就是以信息增益度量属性选择选择分裂后信息增益(很快由下文你就会知道信息增益又是怎么一回事)最大的属性进展分裂。该算法采用自顶向下的贪心搜索遍历可能的决策树空间。算法流程对当前样本集合计算所有属性的信息增益选择信息增益最大的属性作为测试属性把测试属性取值一样

7、的样本划为同一个子样本集假设子样本集的类别属性只含有单个属性那么分支为叶子节点判断其属性之并标上相应的符号然后返回调用途否那么对子样本集递归调用本算法。缺点由于ID3决策树算法采用信息增益作为选择测试属性的标准会偏向于选择取值较多的即所谓的高度分支属性而这类属性并不一定是最优属性。并且其只能处理离散属性对于连续类型属性需要对其进展离散化。为解析决倾向于选择高度分支属性的问题采用信息增益率作为选择测试属性的标准这样便有了C4.5决策树算法。常用的还有CART,SLIQ,SPRINT,PUBLIC等。决策树实例这是一家高尔夫球俱乐部的历史数据里面记录了不同天气状况用户来打高尔夫球的历史记录。我们要

8、做的是通过构建决策树来预测用户是否会来打高尔夫球。这里用户是否来打球是一个一元模型具有不确定性熵值很高。我们无法仅通过Yes以及No的频率来判断用户明天是否会来。因此需要借助天气的信息来减少不确定性。下面分别记录到了4种天气情况我们通过计算条件熵以及互信息来开场构建决策树的第一步构建根决策点。构建根决策节点构建根决策点的方法就是寻找4种天气情况中与打高尔夫球相关性最高的一个。首先我们来看PlayGolf这个一元模型的熵来看看这件事的不确定性有多高.一元模型的熵即信息熵在一元模型中仅通过历史数据的概率来看预测PlayGolf是一件非常不确定的事情在14条历史数据中打球的概率为64%不打球的概率为

9、36%。熵值到达了0.940。这与之前抛硬币的例子很像。在无法改变历史数据的概率时我们需要借助更多的信息来降低不确定性。也就是计算条件熵。二元模型条件熵计算二元模型的条件熵需要知道PlayGolf与4种天气情况一起出现的概率和在不同天气情况下PlayGolf出现的条件概率。下面我们分别来计算这两类概率。出现概率条件概率条件熵信息增益在已知PlayGolf的一元模型熵以及不同天气条件下的二元模型熵后。我们就可以通过信息增益来度量哪种天气与PlayGolf的相关性最高了。构建根节点在整个决策树中Outlook因为与PlayGolf的相关性最高所以作为决策树的根节点。以Outlook作为根节点后决策

10、树出现了三个分支分别是Outlook的三个不同的取值SunnyOvercast以及Rainy。其中Overcast所对应的PlayGolf都是Yes因此这个分支的叶子节点为Yes。构建分支节点另外两个分支我们将使用以及前面一样的方法通过计算熵条件熵以及信息增益来挑选下一个分支的决策节点。通过将决策树中每个决策点复原为原始数据表可以发现每一个决策点都对应了一张数据表。从根决策节点开场我们通过计算熵寻找与PlayGolf最相关的天气信息来建立决策点及分支并反复迭代这一经过。直到最终构建完好的决策树。使用决策树进展预测文章开场的时候我们讲过决策树是用来进展分类以及预测的。详细经过如下。当我们构建好决

11、策树后当有新的信息发送时我们利用已有的决策树逻辑对新的信息构造进展判断。当信息的内容与决策树一致时就进入下一分支进展判断并通过叶子节点获得分类的结果。例如当新的一天开场时我们就可以通过4个天气特征来判断用户是否会来打高尔夫球。以下是详细预测流程的示意图首先寻找新信息中的根决策节点Outlook根据Outlook的取值进入到Sunny分支在Sunny分支中继续判断下一决策点Windy的取值新的信息中Windy的取值为FALSE根据决策树中的逻辑返回Yes。因此在新信息中通过对天气情况的判断预测用户会来打高尔夫球。随机森林决策树是建立在已知的历史数据及概率上的一课决策树的预测可能会不太准确进步准确

12、率最好的方法是构建随机森林(RandomForest)。所谓随机森林就是通过随机抽样的方式从历史数据表中生成多张抽样的历史表对每个抽样的历史表生成一棵决策树。由于每次生成抽样表后数据都会放回到总表中因此每一棵决策树之间都是独立的没有关联。将多颗决策树组成一个随机森林。当有一条新的数据产生时让森林里的每一颗决策树分别进展判断以投票最多的结果作为最终的判断结果。以此来进步正确的概率。使用Mahout进展RandomForests实现数据集例如1,1.52101,13.64,4.49,1.10,71.78,0.06,8.75,0.00,0.00,12,1.51761,13.89,3.60,1.36,

13、72.73,0.48,7.83,0.00,0.00,13,1.51618,13.53,3.55,1.54,72.99,0.39,7.78,0.00,0.00,14,1.51766,13.21,3.69,1.29,72.61,0.57,8.22,0.00,0.00,15,1.51742,13.27,3.62,1.24,73.08,0.55,8.07,0.00,0.00,16,1.51596,12.79,3.61,1.62,72.97,0.64,8.07,0.00,0.26,17,1.51743,13.30,3.60,1.14,73.09,0.58,8.17,0.00,0.00,18,1.5175

14、6,13.15,3.61,1.05,73.24,0.57,8.24,0.00,0.00,19,1.51918,14.04,3.58,1.37,72.08,0.56,8.30,0.00,0.00,110,1.51755,13.00,3.60,1.36,72.99,0.57,8.40,0.00,0.11,1./上传数据集$hadoopfs-putglass.txt/user/ubuntu/glass.txt/生成描绘文件ubuntumaster:/algorithm$mahoutdescribe-p/user/ubuntu/glass.txt-fglass.info-dI9NLMAHOUT_LOC

15、ALisnotset;addingHADOOP_CONF_DIRtoclasspath.Runningonhadoop,using/home/ubuntu/cloud/hadoop-2.7.2/bin/hadoopandHADOOP_CONF_DIR/home/ubuntu/cloud/hadoop-2.7.2/etc/hadoopMAHOUT-JOB:/home/ubuntu/cloud/mahout-0.10.1/mahout-examples-0.10.1-job.jar17/01/1402:53:49WARNMahoutDriver:Nodescribe.propsfoundoncla

16、sspath,willusecommand-lineargumentsonly17/01/1402:53:49INFODescribe:Generatingthedescriptor.17/01/1402:53:50INFODescribe:generatingthedataset.17/01/1402:53:51INFODescribe:storingthedatasetdescription17/01/1402:53:51INFOMahoutDriver:Programtook1584ms(Minutes:0.0264)/生成随机森林$mahoutbuildforest-d/user/ub

17、untu/glass.txt-dsglass.info-sl3-ms3-p-t5-ooutput.17/01/1403:05:50INFOHadoopUtil:Deletinghdfs:/master:9000/user/ubuntu/output17/01/1403:05:50INFOBuildForest:BuildTime:0h0m15s8617/01/1403:05:50INFOBuildForest:ForestnumNodes:20317/01/1403:05:50INFOBuildForest:ForestmeannumNodes:4017/01/1403:05:50INFOBu

18、ildForest:ForestmeanmaxDepth:917/01/1403:05:50INFOBuildForest:Storingtheforestin:output/forest.seq17/01/1403:05:50INFOMahoutDriver:Programtook16124ms(Minutes:0.2687333333333333)/对随机森林进展评估$mahouttestforest-i/user/ubuntu/glass.txt-dsglass.info-moutput-mr-a-otest.17/01/1403:09:48INFOTestForest:Summary-

19、CorrectlyClassifiedInstances:19189.2523%IncorrectlyClassifiedInstances:2310.7477%TotalClassifiedInstances:214ConfusionMatrix-abcdef-Classifiedas6811000|70a16681001|76b25111000|17c30001003|13d5000081|9e61110026|29f7Statistics-Kappa0.7707Accuracy89.2523%Reliability72.3985%Reliability(standarddeviation)0.3365Weightedprecision0.897Weightedrecall0.8925WeightedF1score0.891417/01/1403:09:48INFOMahoutDriver:Programtook18829ms(Minutes:0.3138166666666667)lusic01