《决策树分类和预测算法的原理及实现.docx》由会员分享，可在线阅读，更多相关《决策树分类和预测算法的原理及实现.docx（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、决策树分类和预测算法的原理及实现蓝鲸算法决策树是一种通过对历史数据进展测算实现对新数据进展分类以及预测的算法。简单来讲决策树算法就是通过对已有明确结果的历史数据进展分析寻找数据中的特征。并以此为根据对新产生的数据结果进展预测。决策树由3个主要局部组成分别为决策节点分支以及叶子节点。其中决策树最顶部的决策节点是根决策节点。每一个分支都有一个新的决策节点。决策节点下面是叶子节点。每个决策节点表示一个待分类的数据类别或者属性每个叶子节点表示一种结果。整个决策的经过从根决策节点开场从上到下。根据数据的分类在每个决策节点给出不同的结果。构造决策树是一个复杂的工作。下面我们将介绍决策树中的ID3算法以及“
2、信息熵的概念。并手工创立一个简单的决策树用以讲明整个构建的经过以及思路。ID3算法构造决策树的方法有很多种ID3是其中的一种算法。ID3算法最早是由罗斯昆(J.RossQuinlan)1975年度在悉尼大学提出的一种分类预测算法核心是“信息熵。ID3算法认为“互信息高的属性是好属性通过计算历史数据中每个类别或者属性的“信息熵获得“互信息并选择“互信息最高的类别或者属性作为决策树中的决策节点将类别或者属性的值做为分支继续进展分裂。不断重复这个经过直到生成一棵完好的决策树。信息熵的含义及分类信息熵是信息论中的一个重要的指标是由香农在1948年度提出的。香农借用了热力学中熵的概念来描绘信息的不确定性
3、。因此信息学中的熵以及热力学的熵是有联络的。根据CharlesH.Bennett对MaxwellsDemon的重新解释对信息的销毁是一个不可逆经过所以销毁信息是符合热力学第二定律的。而产生信息那么是为系统引入负(热力学)熵的经过。所以信息熵的符号与热力学熵应该是相反的。简单的讲信息熵是衡量信息的指标更确切的讲是衡量信息的不确定性或者混乱程度的指标。信息的不确定性越大熵越大。决定信息的不确定性或讲复杂程度主要因素是概率。决策树中使用的与熵有关的概念有三个信息熵条件熵以及互信息。下面分别来介绍这三个概念的含义以及计算方法。信息熵是用来衡量一元模型中信息不确定性的指标。信息的不确定性越大熵的值也就越
4、大。而影响熵值的主要因素是概率。这里所讲的一元模型就是指单一事件而不确定性是一个事件出现不同结果的可能性。例如抛硬币可能出现的结果有两个分别是正面以及反面。而每次抛硬币的结果是一个非常不确定的信息。因为根据我们的经历或历史数据来看一个均匀的硬币出现正面以及反面的概率相等都是50%。因此很难判断下一次出现的是正面还是反面。这时抛硬币这个事件的熵值也很高。而假如历史数据告诉我们这枚硬币在过去的100次试验中99次都是正面也就是讲这枚硬币的质量不均匀出现正面结果的概率很高。那么我们就很容易判断下一次的结果了。这时的熵值很低只有0.08。我们把抛硬币这个事件看做一个随机变量S它可能的取值有2种分别是正
5、面x1以及反面x2。每一种取值的概率分别为P1以及P2。我们要获得随机变量S的取值结果至少要进展1次试验试验次数与随机变量S可能的取值数量(2种)的对数函数Log有联络。Log21(以2为底)。因此熵的计算公式是在抛硬币的例子中我们借助一元模型自身的概率也就是前100次的历史数据来消除了判断结果的不确定性。而对于很多现实生活中的问题那么无法仅仅通过自身概率来判断。例如对于天气情况我们无法像抛硬币一样通过晴天雨天以及雾霾在历史数据中出现的概率来判断明天的天气因为天气的种类很多并且影响天气的因素也有很多。同理对于网站的用户我们也无法通过他们的历史购置频率来判断这个用户在下一次访问时是否会完成购置。
6、因为用户是的购置行为存在着不确定性要消除这些不确定性需要更多的信息。例如用户历史行为中的广告创意促销活动商品价格配送时间等信息。因此这里我们不能只借助一元模型来进展判断以及预测了需要获得更多的信息并通过二元模型或者更高阶的模型解析用户的购置行为与其他因素间的关系来消除不确定性。衡量这种关系的指标叫做条件熵。条件熵是通过获得更多的信息来消除一元模型中的不确定性。也就是通过二元或者多元模型来降低一元模型的熵。我们知道的信息越多信息的不确定性越小。例如只使用一元模型时我们无法根据用户历史数据中的购置频率来判断这个用户本次是否也会购置。因为不确定性太大。在参加了促销活动商品价格等信息后在二元模型中我们
7、可以发现用户购置与促销活动或商品价格变化之间的联络。并通过购置与促销活动一起出现的概率以及不同促销活动时购置出现的概率来降低不确定性。计算条件熵时使用到了两种概率分别是购置与促销活动的结合概率P(c)以及不同促销活动出现时购置也出现的条件概率E(c)。以下是条件熵E(T,X)的计算公式。条件熵的值越低讲明二元模型的不确定性越小。互信息是用来衡量信息之间相关性的指标。当两个信息完全相关时互信息为1不相关时为0。在前面的例子中用户购置与促销活动这两个信息间的相关性终究有多高我们可以通过互信息这个指标来度量。详细的计算方法就熵与条件熵之间的差。用户购置的熵E(T)减去促销活动出现时用户购置的熵E(T
8、,X)。以下为计算公式熵条件熵以及互信息是构建决策树的三个关键的指标。下面我们将通过一个维基百科中的实例讲明创立决策树的经过。构建决策树实例这是一家高尔夫球俱乐部的历史数据里面记录了不同天气状况用户来打高尔夫球的历史记录。我们要做的是通过构建决策树来预测用户是否会来打高尔夫球。这里用户是否来打球是一个一元模型具有不确定性熵值很高。我们无法仅通过Yes以及No的频率来判断用户明天是否会来。因此需要借助天气的信息来减少不确定性。下面分别记录到了4种天气情况我们通过计算条件熵以及互信息来开场构建决策树的第一步构建根决策点。构建根决策节点构建根决策点的方法就是寻找4种天气情况中与打高尔夫球相关性最高的
9、一个。首先我们来看PlayGolf这个一元模型的熵来看看这件事的不确定性有多高.一元模型的熵在一元模型中仅通过历史数据的概率来看预测PlayGolf是一件非常不确定的事情在14条历史数据中打球的概率为64%不打球的概率为36%。熵值到达了0.940。这与之前抛硬币的例子很像。在无法改变历史数据的概率时我们需要借助更多的信息来降低不确定性。也就是计算条件熵。二元模型条件熵计算二元模型的条件熵需要知道PlayGolf与4种天气情况一起出现的结合概率和在不同天气情况下PlayGolf出现的条件概率。下面我们分别来计算这两类概率。结合概率以上是经过分别计算后4种天气情况与PlayGolf同时出现的结合
10、概率值。条件概率同时我们也分别计算出了4种天气情况下不同取值时PlayGolf的条件概率值。并通过结合概率与条件概率求得4种天气情况与PlayGolf间的条件熵。互信息在已知PlayGolf的一元模型熵以及不同天气条件下的二元模型熵后。我们就可以通过互信息来度量哪种天气与PlayGolf的相关性最高了。通过互信息的值可以发现4种天气中Outlook的值最大。讲明Outlook与PlayGolf的相关性最高。因此我们选择Outlook作为决策树的根节点来构建决策树。构建根节点在整个决策树中Outlook因为与PlayGolf的相关性最高所以作为决策树的根节点。以Outlook作为根节点后决策树出
11、现了三个分支分别是Outlook的三个不同的取值SunnyOvercast以及Rainy。其中Overcast所对应的PlayGolf都是Yes因此这个分支的叶子节点为Yes。(后面构建分支决策节点时会看到)另外两个分支我们将使用以及前面一样的方法通过计算熵条件熵以及互信息来挑选下一个分支的决策节点。构建分支决策节点下面我们继续构建SunnyOvercast以及Rainy这三个分支的决策节点首先来看下Overcast节点这个节点只有一种结果因此无需在继续分裂。构建分支节点Outlook节点Overcast分支在Outlook根节点下的Overcast分支中PlayGolf只有一种结果Yes因此
12、Overcast分支停顿分裂。叶子节点的值为Yes。Outlook节点Sunny分支在Outlook根节点下的Sunny分支中单独形成了另一个表。此时由于Outlook和作为决策树的根节点了因此所需考虑的天气情况为3种我们继续对这个表确定决策节点。从3种天气情况中找出Sunny分支下的决策节点。方法及步骤以及前面一致计算熵条件熵以及互信息并以互信息最大的作为Sunny分支的决策节点进展分裂。首先计算PlayGolf的一元模型熵可以看到在Sunny这一分支中根据PlayGolf自身的历史数据No以及Yes的概率分布为40%以及60%熵值为0.971。具有极高的不确定性。因此我们继续计算条件熵。以
13、下是三种天气情况分别与PlayGolf的结合概率以及条件概率计算结果。这里可以看到Wind有些与众不同Wind为FALSE时都为PlayGolf的值都为Yes。通过计算获得三种天气情况与PlayGolf的条件概率其中Wind的值为0。互信息计算三种天气情况与PlayGolf的互信息值也就是相关性。值越大相关性越高。三种天气中Wind的互信息值最高为0.971。讲明Sunny分支下Wind以及PlayGolf的相关性最高。因此选择Wind作为Sunny分支的决策节点。构建分支决策节点(Windy)在Outlook根节点的Sunny分支下经过计算互信息的值Wind与PlayGolf相关性最高因此W
14、ind作为Sunny的决策节点。Wind有两个分支分别为FALSE以及TRUE。当Wind为FALSE时PlayGolf的结果为Yes。Wind为TRUE时结果为No。Outlook节点Rainy分支Outlook根节点还有一个分支是Rainy。以下是Outlook下Rainy的分支数据表。我们从这个表中挑选出Rainy分支下的决策节点。由于Outlook和作为决策树的根节点Wind成为了Sunny分支下的决策节点因此我们需要考虑的天气情况就只剩下两种Temp以及Humidity。首先计算在Rainy分支下PlayGolf的熵。从历史数据看No以及Yes的概率为60%以及40%熵为0.971一
15、元模型依靠自身概率的不确定性较高。参加两个天气情况的信息来计算条件熵。通过计算两种天气情况与PlayGolf的结合概率以及条件概率发现情况与Sunny分支类似。Humidity应该与PlayGolf的相关性较高。通过计算获得Temp以及Humidity与PlayGolf的条件熵其中Humidity与PlayGolf的条件熵为0。互信息PlayGolf熵减去两种天气与PlayGolf的条件熵获得互信息的值。Humidity值最大讲明相关性最高。因此Humidity被选为Rainy分支的决策节点。构建分支决策节点(Humidity)在Outlook的Rainy分支下Humidity作为决策节点有两
16、个分支分别为High以及Normal。所有High分支都对应PlayGolf的No所有Normal分支都对应了PlayGolf的Yes。因此停顿继续分裂。到此为止我们通过PlayGolf与天气情况的历史数据构建了决策树。下面我们在从较高的维度来看下整个决策树与历史数据表间的关系。数据表与决策树通过将决策树中每个决策点复原为原始数据表可以发现每一个决策点都对应了一张数据表。从根决策节点开场我们通过计算熵寻找与PlayGolf最相关的天气信息来建立决策点及分支并反复迭代这一经过。直到最终构建完好的决策树。使用决策树进展预测文章开场的时候我们讲过决策树是用来进展分类以及预测的。详细经过如下。当我们构
17、建好决策树后当有新的信息发送时我们利用已有的决策树逻辑对新的信息构造进展判断。当信息的内容与决策树一致时就进入下一分支进展判断并通过叶子节点获得分类的结果。例如当新的一天开场时我们就可以通过4个天气特征来判断用户是否会来打高尔夫球。以下是详细预测流程的示意图首先寻找新信息中的根决策节点Outlook根据Outlook的取值进入到Sunny分支在Sunny分支中继续判断下一决策点Windy的取值新的信息中Windy的取值为FALSE根据决策树中的逻辑返回Yes。因此在新信息中通过对天气情况的判断预测用户会来打高尔夫球。通过随机森林进步准确率决策树是建立在已知的历史数据及概率上的一课决策树的预测可能会不太准确进步准确率最好的方法是构建随机森林(RandomForest)。所谓随机森林就是通过随机抽样的方式从历史数据表中生成多张抽样的历史表对每个抽样的历史表生成一棵决策树。由于每次生成抽样表后数据都会放回到总表中因此每一棵决策树之间都是独立的没有关联。将多颗决策树组成一个随机森林。当有一条新的数据产生时让森林里的每一颗决策树分别进展判断以投票最多的结果作为最终的判断结果。以此来进步正确的概率。via:tuicoolEnd.:/36dsj/archives/44255数据文字工