精华内容
下载资源
问答
  • 写在前面:本文很详细的说明了决策树分类和预测算法的原理,并以某高尔夫球俱乐不同的天气状况下是否来打球为例进行分析。比较详尽,谢谢作者声明可以注明出处进行转载,让更多的人分享到这份知识。 算法决策树...

    转载自 http://www.36dsj.com/archives/44255


    写在前面:本文很详细的说明了决策树分类和预测算法的原理,并以某高尔夫球俱乐不同的天气状况下是否来打球为例进行分析。比较详尽,谢谢作者声明可以注明出处进行转载,让更多的人分享到这份知识。


    算法决策树是一种通过对历史数据进行测算实现对新数据进行分类和预测的算法。简单来说决策树算法就是通过对已有明确结果的历史数据进行分析,寻找数据中的特征。并以此为依据对新产生的数据结果进行预测。

    决策树由3个主要部分组成,分别为决策节点,分支,和叶子节点。其中决策树最顶部的决策节点是根决策节点。每一个分支都有一个新的决策节点。决策节点下面是叶子节点。每个决策节点表示一个待分类的数据类别或属性,每个叶子节点表示一种结果。整个决策的过程从根决策节点开始,从上到下。根据数据的分类在每个决策节点给出不同的结果。

    构造决策树是一个复杂的工作。下面我们将介绍决策树中的ID3算法和“信息熵”的概念。并手工创建一个简单的决策树,用以说明整个构建的过程和思路。


    ID3算法

    构造决策树的方法有很多种,ID3是其中的一种算法。ID3算法最早是由罗斯昆(J. Ross Quinlan)1975年在悉尼大学提出的一种分类预测算法,核心是“信息熵”。ID3算法认为“互信息”高的属性是好属性,通过计算历史数据中每个类别或属性的“信息熵”获得“互信息”,并选择“互信息”最高的类别或属性作为决策树中的决策节点,将类别或属性的值做为分支继续进行分裂。不断重复这个过程,直到生成一棵完整的决策树。


    信息熵的含义及分类

    信息熵是信息论中的一个重要的指标,是由香农在1948年提出的。香农借用了热力学中熵的概念来描述信息的不确定性。因此信息学中的熵和热力学的熵是有联系的。根据Charles H. Bennett对Maxwell’s Demon的重新解释,对信息的销毁是一个不可逆过程,所以销毁信息是符合热力学第二定律的。而产生信息,则是为系统引入负(热力学)熵的过程。 所以信息熵的符号与热力学熵应该是相反的 。


    简单的说信息熵是衡量信息的指标,更确切的说是衡量信息的不确定性或混乱程度的指标。信息的不确定性越大,熵越大。决定信息的不确定性或者说复杂程度主要因素是概率。决策树中使用的与熵有关的概念有三个:信息熵,条件熵和互信息。下面分别来介绍这三个概念的含义和计算方法。


    信息熵是用来衡量一元模型中信息不确定性的指标。信息的不确定性越大,熵的值也就越大。而影响熵值的主要因素是概率。这里所说的一元模型就是指单一事件,而不确定性是一个事件出现不同结果的可能性。例如抛硬币,可能出现的结果有两个,分别是正面和反面。而每次抛硬币的结果是一个非常不确定的信息。因为根据我们的经验或者历史数据来看,一个均匀的硬币出现正面和反面的概率相等,都是50%。因此很难判断下一次出现的是正面还是反面。这时抛硬币这个事件的熵值也很高。而如果历史数据告诉我们这枚硬币在过去的100次试验中99次都是正面,也就是说这枚硬币的质量不均匀,出现正面结果的概率很高。那么我们就很容易判断下一次的结果了。这时的熵值很低,只有0.08。


    我们把抛硬币这个事件看做一个随机变量S,它可能的取值有2种,分别是正面x1和反面x2。每一种取值的概率分别为P1和P2。 我们要获得随机变量S的取值结果至少要进行1次试验,试验次数与随机变量S可能的取值数量(2种)的对数函数Log有联系。Log2=1(以2为底)。因此熵的计算公式是:

    在抛硬币的例子中,我们借助一元模型自身的概率,也就是前100次的历史数据来消除了判断结果的不确定性。而对于很多现实生活中的问题,则无法仅仅通过自身概率来判断。例如:对于天气情况,我们无法像抛硬币一样通过晴天,雨天和雾霾在历史数据中出现的概率来判断明天的天气,因为天气的种类很多,并且影响天气的因素也有很多。同理,对于网站的用户我们也无法通过他们的历史购买频率来判断这个用户在下一次访问时是否会完成购买。因为用户是的购买行为存在着不确定性,要消除这些不确定性需要更多的信息。例如用户历史行为中的广告创意,促销活动,商品价格,配送时间等信息。因此这里我们不能只借助一元模型来进行判断和预测了,需要获得更多的信息并通过二元模型或更高阶的模型了解用户的购买行为与其他因素间的关系来消除不确定性。衡量这种关系的指标叫做条件熵。


    条件熵是通过获得更多的信息来消除一元模型中的不确定性。也就是通过二元或多元模型来降低一元模型的熵。我们知道的信息越多,信息的不确定性越小。例如,只使用一元模型时我们无法根据用户历史数据中的购买频率来判断这个用户本次是否也会购买。因为不确定性太大。在加入了促销活动,商品价格等信息后,在二元模型中我们可以发现用户购买与促销活动,或者商品价格变化之间的联系。并通过购买与促销活动一起出现的概率,和不同促销活动时购买出现的概率来降低不确定性。


    计算条件熵时使用到了两种概率,分别是购买与促销活动的联合概率P(c),和不同促销活动出现时购买也出现的条件概率E(c)。以下是条件熵E(T,X)的计算公式。条件熵的值越低说明二元模型的不确定性越小。

    互信息是用来衡量信息之间相关性的指标。当两个信息完全相关时,互信息为1,不相关时为0。在前面的例子中用户购买与促销活动这两个信息间的相关性究竟有多高,我们可以通过互信息这个指标来度量。具体的计算方法就熵与条件熵之间的差。用户购买的熵E(T)减去促销活动出现时用户购买的熵E(T,X)。以下为计算公式:

    熵,条件熵和互信息是构建决策树的三个关键的指标。下面我们将通过一个 维基百科 中的实例说明创建决策树的过程。


    构建决策树实例

    这是一家高尔夫球俱乐部的历史数据,里面记录了不同天气状况用户来打高尔夫球的历史记录。我们要做的是通过构建决策树来预测用户是否会来打高尔夫球。这里用户是否来打球是一个一元模型,具有不确定性,熵值很高。我们无法仅通过Yes和No的频率来判断用户明天是否会来。因此,需要借助天气的信息来减少不确定性。下面分别记录到了4种天气情况,我们通过计算条件熵和互信息来开始构建决策树的第一步:构建根决策点。


    构建根决策节点

    构建根决策点的方法就是寻找4种天气情况中与打高尔夫球相关性最高的一个。首先我们来看Play Golf这个一元模型的熵,来看看这件事的不确定性有多高.


    一元模型的熵

    在一元模型中,仅通过历史数据的概率来看预测Play Golf是一件非常不确定的事情,在14条历史数据中,打球的概率为64%,不打球的概率为36%。熵值达到了0.940。这与之前抛硬币的例子很像。在无法改变历史数据的概率时,我们需要借助更多的信息来降低不确定性。也就是计算条件熵。

    二元模型条件熵

    计算二元模型的条件熵需要知道Play Golf与4种天气情况一起出现的联合概率,以及在不同天气情况下Play Golf出现的条件概率。下面我们分别来计算这两类概率。


    联合概率

    以上是经过分别计算后4种天气情况与Play Golf同时出现的联合概率值。


    条件概率

    同时我们也分别计算出了4种天气情况下,不同取值时Play Golf的条件概率值。并通过联合概率与条件概率求得4种天气情况与Play Golf间的条件熵。


    互信息

    在已知Play Golf的一元模型熵和不同天气条件下的二元模型熵后。我们就可以通过互信息来度量哪种天气与Play Golf的相关性最高了。

    通过互信息的值可以发现,4种天气中Outlook的值最大。说明Outlook与Play Golf的相关性最高。因此我们选择Outlook作为决策树的根节点来构建决策树。


    构建根节点

    在整个决策树中,Outlook因为与Play Golf的相关性最高,所以作为决策树的根节点。以Outlook作为根节点后,决策树出现了三个分支,分别是Outlook的三个不同的取值Sunny,Overcast和Rainy。其中Overcast所对应的Play Golf都是Yes,因此这个分支的叶子节点为Yes。(后面构建分支决策节点时会看到)另外两个分支我们将使用和前面一样的方法,通过计算熵,条件熵和互信息来挑选下一个分支的决策节点。


    构建分支决策节点

    下面我们继续构建Sunny,Overcast和Rainy这三个分支的决策节点,首先来看下Overcast节点,这个节点只有一种结果,因此无需在继续分裂。


    构建分支节点

    Outlook 节点Overcast分支

    在Outlook根节点下的Overcast分支中,Play Golf只有一种结果Yes,因此Overcast分支停止分裂。叶子节点的值为Yes。


    Outlook 节点Sunny分支

    在Outlook根节点下的Sunny分支中,单独形成了另一个表。此时由于Outlook以及作为决策树的根节点了,因此所需考虑的天气情况为3种,我们继续对这个表确定决策节点。从3种天气情况中找出Sunny分支下的决策节点。方法及步骤和前面一致,计算熵,条件熵和互信息,并以互信息最大的作为Sunny分支的决策节点进行分裂。

    首先计算Play Golf的一元模型熵,可以看到在Sunny这一分支中根据Play Golf自身的历史数据 No和Yes的概率分布为40%和60%,熵值为0.971。具有极高的不确定性。因此我们继续计算条件熵。

    以下是三种天气情况分别与Play Golf的联合概率和条件概率计算结果。这里可以看到Wind有些与众不同,Wind为FALSE时都为Play Golf的值都为Yes。

    通过计算获得三种天气情况与Play Golf的条件概率,其中Wind的值为0。


    互信息

    计算三种天气情况与Play Golf的互信息值,也就是相关性。值越大相关性越高。三种天气中Wind的互信息值最高,为0.971。说明Sunny分支下Wind和Play Golf的相关性最高。因此选择Wind作为Sunny分支的决策节点。


    构建分支决策节点(Windy)

    在Outlook根节点的Sunny分支下,经过计算互信息的值Wind与Play Golf相关性最高,因此Wind作为Sunny的决策节点。Wind有两个分支,分别为FALSE和TRUE。当Wind为FALSE时,Play Golf的结果为Yes。Wind为TRUE时结果为No。


    Outlook 节点Rainy分支

    Outlook根节点还有一个分支是Rainy。以下是Outlook下Rainy的分支数据表。我们从这个表中挑选出Rainy分支下的决策节点。由于Outlook以及作为决策树的根节点,Wind成为了Sunny分支下的决策节点,因此我们需要考虑的天气情况就只剩下两种Temp和Humidity。

    首先计算在Rainy分支下Play Golf的熵。从历史数据看No和Yes的概率为60%和40%,熵为0.971,一元模型依靠自身概率的不确定性较高。加入两个天气情况的信息来计算条件熵。

    通过计算两种天气情况与Play Golf的联合概率和条件概率发现,情况与Sunny分支类似。Humidity应该与Play Golf的相关性较高。

    通过计算获得Temp和Humidity与Play Golf的条件熵,其中Humidity与Play Golf的条件熵为0。


    互信息

    Play Golf熵减去两种天气与Play Golf的条件熵获得互信息的值。Humidity值最大,说明相关性最高。因此Humidity被选为Rainy分支的决策节点。


    构建分支决策节点(Humidity)

    在Outlook的Rainy分支下,Humidity作为决策节点有两个分支,分别为High和Normal。所有High分支都对应Play Golf的No,所有Normal分支都对应了Play Golf的Yes。因此停止继续分裂。

    到此为止我们通过Play Golf与天气情况的历史数据构建了决策树。下面我们在从较高的维度来看下整个决策树与历史数据表间的关系。


    数据表与决策树

    通过将决策树中每个决策点还原为原始数据表可以发现,每一个决策点都对应了一张数据表。从根决策节点开始,我们通过计算熵寻找与Play Golf最相关的天气信息,来建立决策点及分支,并反复迭代这一过程。直到最终构建完整的决策树。


    使用决策树进行预测

    文章开始的时候我们说过,决策树是用来进行分类和预测的。具体过程如下。当我们构建好决策树后,当有新的信息发送时,我们利用已有的决策树逻辑对新的信息结构进行判断。当信息的内容与决策树一致时,就进入下一分支进行判断,并通过叶子节点获得分类的结果。例如,当新的一天开始时,我们就可以通过4个天气特征来判断用户是否会来打高尔夫球。以下是具体预测流程的示意图,首先寻找新信息中的根决策节点Outlook,根据Outlook的取值进入到Sunny分支,在Sunny分支中继续判断下一决策点Windy的取值,新的信息中Windy的取值为FALSE,根据决策树中的逻辑返回Yes。因此在新信息中通过对天气情况的判断预测用户会来打高尔夫球。

    通过随机森林提高准确率

    决策树是建立在已知的历史数据及概率上的,一课决策树的预测可能会不太准确,提高准确率最好的方法是构建随机森林(Random Forest)。所谓随机森林就是通过随机抽样的方式从历史数据表中生成多张抽样的历史表,对每个抽样的历史表生成一棵决策树。由于每次生成抽样表后数据都会放回到总表中,因此每一棵决策树之间都是独立的没有关联。将多颗决策树组成一个随机森林。当有一条新的数据产生时,让森林里的每一颗决策树分别进行判断,以投票最多的结果作为最终的判断结果。以此来提高正确的概率。


    Sharing is one of the best learning, is a happy thing, share at the moment of mood, come on!

    欢迎转发到朋友圈或分享给好友


    展开全文
  • 决策树是一种通过对历史数据进行测算实现对新数据进行分类和预测的算法。简单来说决策树算法就是通过对已有明确结果的历史数据进行分析,寻找数据中的特征。并以此为依据对新产生的数据结果进行预测决策树由3...

    决策树是一种通过对历史数据进行测算实现对新数据进行分类和预测的算法。简单来说决策树算法就是通过对已有明确结果的历史数据进行分析,寻找数据中的特征。并以此为依据对新产生的数据结果进行预测。

    决策树由3个主要部分组成,分别为决策节点,分支,和叶子节点。其中决策树最顶部的决策节点是根决策节点。每一个分支都有一个新的决策节点。决策节点下面是叶子节点。每个决策节点表示一个待分类的数据类别或属性,每个叶子节点表示一种结果。整个决策的过程从根决策节点开始,从上到下。根据数据的分类在每个决策节点给出不同的结果。

    决策树结构图2

    构造决策树是一个复杂的工作。下面我们将介绍决策树中的ID3算法和“信息熵”的概念。并手工创建一个简单的决策树,用以说明整个构建的过程和思路。

    ID3算法

    构造决策树的方法有很多种,ID3是其中的一种算法。ID3算法最早是由罗斯昆(J. Ross Quinlan)1975年在悉尼大学提出的一种分类预测算法,核心是“信息熵”。ID3算法认为“互信息”高的属性是好属性,通过计算历史数据中每个类别或属性的“信息熵”获得“互信息”,并选择“互信息”最高的类别或属性作为决策树中的决策节点,将类别或属性的值做为分支继续进行分裂。不断重复这个过程,直到生成一棵完整的决策树。

    信息熵的含义及分类

    信息熵是信息论中的一个重要的指标,是由香农在1948年提出的。香农借用了热力学中熵的概念来描述信息的不确定性。因此信息学中的熵和热力学的熵是有联系的。根据Charles H. Bennett对Maxwell’s Demon的重新解释,对信息的销毁是一个不可逆过程,所以销毁信息是符合热力学第二定律的。而产生信息,则是为系统引入负(热力学)熵的过程。所以信息熵的符号与热力学熵应该是相反的

    简单的说信息熵是衡量信息的指标,更确切的说是衡量信息的不确定性或混乱程度的指标。信息的不确定性越大,熵越大。决定信息的不确定性或者说复杂程度主要因素是概率。决策树中使用的与熵有关的概念有三个:信息熵,条件熵和互信息。下面分别来介绍这三个概念的含义和计算方法。

    信息熵

    信息熵是用来衡量一元模型中信息不确定性的指标。信息的不确定性越大,熵的值也就越大。而影响熵值的主要因素是概率。这里所说的一元模型就是指单一事件,而不确定性是一个事件出现不同结果的可能性。例如抛硬币,可能出现的结果有两个,分别是正面和反面。而每次抛硬币的结果是一个非常不确定的信息。因为根据我们的经验或者历史数据来看,一个均匀的硬币出现正面和反面的概率相等,都是50%。因此很难判断下一次出现的是正面还是反面。这时抛硬币这个事件的熵值也很高。而如果历史数据告诉我们这枚硬币在过去的100次试验中99次都是正面,也就是说这枚硬币的质量不均匀,出现正面结果的概率很高。那么我们就很容易判断下一次的结果了。这时的熵值很低,只有0.08。

    熵1

    我们把抛硬币这个事件看做一个随机变量S,它可能的取值有2种,分别是正面x1和反面x2。每一种取值的概率分别为P1和P2。我们要获得随机变量S的取值结果至少要进行1次试验,试验次数与随机变量S可能的取值数量(2种)的对数函数Log有联系。Log2=1(以2为底)。因此熵的计算公式是:

    1

    在抛硬币的例子中,我们借助一元模型自身的概率,也就是前100次的历史数据来消除了判断结果的不确定性。而对于很多现实生活中的问题,则无法仅仅通过自身概率来判断。例如:对于天气情况,我们无法像抛硬币一样通过晴天,雨天和雾霾在历史数据中出现的概率来判断明天的天气,因为天气的种类很多,并且影响天气的因素也有很多。同理,对于网站的用户我们也无法通过他们的历史购买频率来判断这个用户在下一次访问时是否会完成购买。因为用户是的购买行为存在着不确定性,要消除这些不确定性需要更多的信息。例如用户历史行为中的广告创意,促销活动,商品价格,配送时间等信息。因此这里我们不能只借助一元模型来进行判断和预测了,需要获得更多的信息并通过二元模型或更高阶的模型了解用户的购买行为与其他因素间的关系来消除不确定性。衡量这种关系的指标叫做条件熵。

    条件熵

    条件熵是通过获得更多的信息来消除一元模型中的不确定性。也就是通过二元或多元模型来降低一元模型的熵。我们知道的信息越多,信息的不确定性越小。例如,只使用一元模型时我们无法根据用户历史数据中的购买频率来判断这个用户本次是否也会购买。因为不确定性太大。在加入了促销活动,商品价格等信息后,在二元模型中我们可以发现用户购买与促销活动,或者商品价格变化之间的联系。并通过购买与促销活动一起出现的概率,和不同促销活动时购买出现的概率来降低不确定性。

    互信息1

    计算条件熵时使用到了两种概率,分别是购买与促销活动的联合概率P(c),和不同促销活动出现时购买也出现的条件概率E(c)。以下是条件熵E(T,X)的计算公式。条件熵的值越低说明二元模型的不确定性越小。

    2

    互信息

    互信息是用来衡量信息之间相关性的指标。当两个信息完全相关时,互信息为1,不相关时为0。在前面的例子中用户购买与促销活动这两个信息间的相关性究竟有多高,我们可以通过互信息这个指标来度量。具体的计算方法就熵与条件熵之间的差。用户购买的熵E(T)减去促销活动出现时用户购买的熵E(T,X)。以下为计算公式:

    3

    熵,条件熵和互信息是构建决策树的三个关键的指标。下面我们将通过一个维基百科中的实例说明创建决策树的过程。

    构建决策树实例

    这是一家高尔夫球俱乐部的历史数据,里面记录了不同天气状况用户来打高尔夫球的历史记录。我们要做的是通过构建决策树来预测用户是否会来打高尔夫球。这里用户是否来打球是一个一元模型,具有不确定性,熵值很高。我们无法仅通过Yes和No的频率来判断用户明天是否会来。因此,需要借助天气的信息来减少不确定性。下面分别记录到了4种天气情况,我们通过计算条件熵和互信息来开始构建决策树的第一步:构建根决策点。

    原始数据表

    构建根决策节点

    构建根决策点的方法就是寻找4种天气情况中与打高尔夫球相关性最高的一个。首先我们来看Play Golf这个一元模型的熵,来看看这件事的不确定性有多高.

    一元模型的熵

    在一元模型中,仅通过历史数据的概率来看预测Play Golf是一件非常不确定的事情,在14条历史数据中,打球的概率为64%,不打球的概率为36%。熵值达到了0.940。这与之前抛硬币的例子很像。在无法改变历史数据的概率时,我们需要借助更多的信息来降低不确定性。也就是计算条件熵。

    target

    1

    二元模型条件熵

    计算二元模型的条件熵需要知道Play Golf与4种天气情况一起出现的联合概率,以及在不同天气情况下Play Golf出现的条件概率。下面我们分别来计算这两类概率。

    联合概率

    P

    以上是经过分别计算后4种天气情况与Play Golf同时出现的联合概率值。

    条件概率

    E1

    同时我们也分别计算出了4种天气情况下,不同取值时Play Golf的条件概率值。并通过联合概率与条件概率求得4种天气情况与Play Golf间的条件熵。

    2条件熵

    互信息

    在已知Play Golf的一元模型熵和不同天气条件下的二元模型熵后。我们就可以通过互信息来度量哪种天气与Play Golf的相关性最高了。

    3

    通过互信息的值可以发现,4种天气中Outlook的值最大。说明Outlook与Play Golf的相关性最高。因此我们选择Outlook作为决策树的根节点来构建决策树。

    Gain

    构建根节点

    在整个决策树中,Outlook因为与Play Golf的相关性最高,所以作为决策树的根节点。以Outlook作为根节点后,决策树出现了三个分支,分别是Outlook的三个不同的取值Sunny,Overcast和Rainy。其中Overcast所对应的Play Golf都是Yes,因此这个分支的叶子节点为Yes。(后面构建分支决策节点时会看到)另外两个分支我们将使用和前面一样的方法,通过计算熵,条件熵和互信息来挑选下一个分支的决策节点。

    level outlook1

    构建分支决策节点

    下面我们继续构建Sunny,Overcast和Rainy这三个分支的决策节点,首先来看下Overcast节点,这个节点只有一种结果,因此无需在继续分裂。

    Outlook节点Overcast分支

    在Outlook根节点下的Overcast分支中,Play Golf只有一种结果Yes,因此Overcast分支停止分裂。叶子节点的值为Yes。

    table

    Outlook节点Sunny分支

    在Outlook根节点下的Sunny分支中,单独形成了另一个表。此时由于Outlook以及作为决策树的根节点了,因此所需考虑的天气情况为3种,我们继续对这个表确定决策节点。从3种天气情况中找出Sunny分支下的决策节点。方法及步骤和前面一致,计算熵,条件熵和互信息,并以互信息最大的作为Sunny分支的决策节点进行分裂。

    table

    首先计算Play Golf的一元模型熵,可以看到在Sunny这一分支中根据Play Golf自身的历史数据 No和Yes的概率分布为40%和60%,熵值为0.971。具有极高的不确定性。因此我们继续计算条件熵。

    target

    以下是三种天气情况分别与Play Golf的联合概率和条件概率计算结果。这里可以看到Wind有些与众不同,Wind为FALSE时都为Play Golf的值都为Yes。

    P&E

    通过计算获得三种天气情况与Play Golf的条件概率,其中Wind的值为0。

    条件熵

    互信息

    计算三种天气情况与Play Golf的互信息值,也就是相关性。值越大相关性越高。三种天气中Wind的互信息值最高,为0.971。说明Sunny分支下Wind和Play Golf的相关性最高。因此选择Wind作为Sunny分支的决策节点。

    Gain

    构建分支决策节点(Windy)

    在Outlook根节点的Sunny分支下,经过计算互信息的值Wind与Play Golf相关性最高,因此Wind作为Sunny的决策节点。Wind有两个分支,分别为FALSE和TRUE。当Wind为FALSE时,Play Golf的结果为Yes。Wind为TRUE时结果为No。

    level windy

    Outlook节点Rainy分支

    Outlook根节点还有一个分支是Rainy。以下是Outlook下Rainy的分支数据表。我们从这个表中挑选出Rainy分支下的决策节点。由于Outlook以及作为决策树的根节点,Wind成为了Sunny分支下的决策节点,因此我们需要考虑的天气情况就只剩下两种Temp和Humidity。

    table1

    首先计算在Rainy分支下Play Golf的熵。从历史数据看No和Yes的概率为60%和40%,熵为0.971,一元模型依靠自身概率的不确定性较高。加入两个天气情况的信息来计算条件熵。

    target

    通过计算两种天气情况与Play Golf的联合概率和条件概率发现,情况与Sunny分支类似。Humidity应该与Play Golf的相关性较高。

    P&E1

    通过计算获得Temp和Humidity与Play Golf的条件熵,其中Humidity与Play Golf的条件熵为0。

    条件熵

    互信息

    Play Golf熵减去两种天气与Play Golf的条件熵获得互信息的值。Humidity值最大,说明相关性最高。因此Humidity被选为Rainy分支的决策节点。

    Gain1

    构建分支决策节点(Humidity)

    在Outlook的Rainy分支下,Humidity作为决策节点有两个分支,分别为High和Normal。所有High分支都对应Play Golf的No,所有Normal分支都对应了Play Golf的Yes。因此停止继续分裂。

    level humidty

    到此为止我们通过Play Golf与天气情况的历史数据构建了决策树。下面我们在从较高的维度来看下整个决策树与历史数据表间的关系。

    数据表与决策树

    通过将决策树中每个决策点还原为原始数据表可以发现,每一个决策点都对应了一张数据表。从根决策节点开始,我们通过计算熵寻找与Play Golf最相关的天气信息,来建立决策点及分支,并反复迭代这一过程。直到最终构建完整的决策树。

    决策树(表)

    决策树(图)

    使用决策树进行预测

    文章开始的时候我们说过,决策树是用来进行分类和预测的。具体过程如下。当我们构建好决策树后,当有新的信息发送时,我们利用已有的决策树逻辑对新的信息结构进行判断。当信息的内容与决策树一致时,就进入下一分支进行判断,并通过叶子节点获得分类的结果。例如,当新的一天开始时,我们就可以通过4个天气特征来判断用户是否会来打高尔夫球。以下是具体预测流程的示意图,首先寻找新信息中的根决策节点Outlook,根据Outlook的取值进入到Sunny分支,在Sunny分支中继续判断下一决策点Windy的取值,新的信息中Windy的取值为FALSE,根据决策树中的逻辑返回Yes。因此在新信息中通过对天气情况的判断预测用户会来打高尔夫球。

    应用决策树

    通过随机森林提高准确率

    Random Forest

    决策树是建立在已知的历史数据及概率上的,一课决策树的预测可能会不太准确,提高准确率最好的方法是构建随机森林(Random Forest)。所谓随机森林就是通过随机抽样的方式从历史数据表中生成多张抽样的历史表,对每个抽样的历史表生成一棵决策树。由于每次生成抽样表后数据都会放回到总表中,因此每一棵决策树之间都是独立的没有关联。将多颗决策树组成一个随机森林。当有一条新的数据产生时,让森林里的每一颗决策树分别进行判断,以投票最多的结果作为最终的判断结果。以此来提高正确的概率。

    —【所有文章及图片版权归 蓝鲸(王彦平)所有。欢迎转载,但请注明转自“蓝鲸网站分析博客”。】—



    Read more: http://bluewhale.cc/2016-03-20/decision-tree.html#ixzz45sHhOL6u
    展开全文
  • 第四章 分类和预测;第四章 分类和预测;第四章 分类和预测;4.1 分类和预测的定义;4.1 分类和预测的定义示例;4.1 分类和预测的定义;4.1 分类和预测的定义;第一步建立模型;第二步使用模型;第四章 分类和预测;4.2 数据...
  • python3 学习使用随机森林分类器 梯度提升决策树分类 的api,并将他们单一决策树预测结果做出对比 附上我的git,欢迎大家来参考我其他分类器的代码:https://github.com/linyi0604/MachineLearning 首先,了解...

     

    python3 学习使用随机森林分类器 梯度提升决策树分类 的api,并将他们和单一决策树预测结果做出对比

    附上我的git,欢迎大家来参考我其他分类器的代码: https://github.com/linyi0604/MachineLearning

     

    首先,了解一下决策树的优缺点:

    决策树与其他分类算法相比的优缺点

    优点:

    1.直观,决策树可以提供可视化,便于理解;
    2.适用于小规模数据;
    3.数据的准备往往是简单或者不必要的,
    4.对相关特征数据的处理;
    缺点:
    1. 连续变量处理不好,也就是说当数据中存在连续变量的属性时,决策树表现并不是很好;
    2. 特征属性增加时,错误增加的比较快;
    3. 不稳定性,一点点的扰动或者改动都可能改动整棵树,我们想要的分类器对噪声是健壮的
    4. 当数据出现不相关的特征,表现不是很好。

    5. 很容易在训练数据中生成复杂的树结构,造成过拟合(overfitting)。

     

    复制代码

      1 import pandas as pd
      2 from sklearn.cross_validation import train_test_split
      3 from sklearn.feature_extraction import DictVectorizer
      4 from sklearn.tree import DecisionTreeClassifier
      5 from sklearn.metrics import classification_report
      6 from sklearn.ensemble import RandomForestClassifier, GradientBoostingClassifier
      7 
      8 '''
      9 集成分类器:
     10 综合考量多个分类器的预测结果做出考量。
     11 这种综合考量大体上分两种:
     12     1 搭建多个独立的分类模型,然后通过投票的方式 比如 随机森林分类器
     13         随机森林在训练数据上同时搭建多棵决策树,这些决策树在构建的时候会放弃唯一算法,随机选取特征
     14     2 按照一定次序搭建多个分类模型,
     15         他们之间存在依赖关系,每一个后续模型的加入都需要现有模型的综合性能贡献,
     16         从多个较弱的分类器搭建出一个较为强大的分类器,比如梯度提升决策树
     17         提督森林决策树在建立的时候尽可能降低成体在拟合数据上的误差。
     18         
     19 下面将对比 单一决策树 随机森林 梯度提升决策树 的预测情况
     20 
     21 '''
     22 
     23 '''
     24 1 准备数据
     25 '''
     26 # 读取泰坦尼克乘客数据,已经从互联网下载到本地
     27 titanic = pd.read_csv("./data/titanic/titanic.txt")
     28 # 观察数据发现有缺失现象
     29 # print(titanic.head())
     30 
     31 # 提取关键特征,sex, age, pclass都很有可能影响是否幸免
     32 x = titanic[['pclass', 'age', 'sex']]
     33 y = titanic['survived']
     34 # 查看当前选择的特征
     35 # print(x.info())
     36 '''
     37 <class 'pandas.core.frame.DataFrame'>
     38 RangeIndex: 1313 entries, 0 to 1312
     39 Data columns (total 3 columns):
     40 pclass    1313 non-null object
     41 age       633 non-null float64
     42 sex       1313 non-null object
     43 dtypes: float64(1), object(2)
     44 memory usage: 30.9+ KB
     45 None
     46 '''
     47 # age数据列 只有633个,对于空缺的 采用平均数或者中位数进行补充 希望对模型影响小
     48 x['age'].fillna(x['age'].mean(), inplace=True)
     49 
     50 '''
     51 2 数据分割
     52 '''
     53 x_train, x_test, y_train, y_test = train_test_split(x, y, test_size=0.25, random_state=33)
     54 # 使用特征转换器进行特征抽取
     55 vec = DictVectorizer()
     56 # 类别型的数据会抽离出来 数据型的会保持不变
     57 x_train = vec.fit_transform(x_train.to_dict(orient="record"))
     58 # print(vec.feature_names_)   # ['age', 'pclass=1st', 'pclass=2nd', 'pclass=3rd', 'sex=female', 'sex=male']
     59 x_test = vec.transform(x_test.to_dict(orient="record"))
     60 
     61 '''
     62 3.1 单一决策树 训练模型 进行预测
     63 '''
     64 # 初始化决策树分类器
     65 dtc = DecisionTreeClassifier()
     66 # 训练
     67 dtc.fit(x_train, y_train)
     68 # 预测 保存结果
     69 dtc_y_predict = dtc.predict(x_test)
     70 
     71 '''
     72 3.2 使用随机森林 训练模型 进行预测
     73 '''
     74 # 初始化随机森林分类器
     75 rfc = RandomForestClassifier()
     76 # 训练
     77 rfc.fit(x_train, y_train)
     78 # 预测
     79 rfc_y_predict = rfc.predict(x_test)
     80 
     81 '''
     82 3.3 使用梯度提升决策树进行模型训练和预测
     83 '''
     84 # 初始化分类器
     85 gbc = GradientBoostingClassifier()
     86 # 训练
     87 gbc.fit(x_train, y_train)
     88 # 预测
     89 gbc_y_predict = gbc.predict(x_test)
     90 
     91 
     92 '''
     93 4 模型评估
     94 '''
     95 print("单一决策树准确度:", dtc.score(x_test, y_test))
     96 print("其他指标:\n", classification_report(dtc_y_predict, y_test, target_names=['died', 'survived']))
     97 
     98 print("随机森林准确度:", rfc.score(x_test, y_test))
     99 print("其他指标:\n", classification_report(rfc_y_predict, y_test, target_names=['died', 'survived']))
    100 
    101 print("梯度提升决策树准确度:", gbc.score(x_test, y_test))
    102 print("其他指标:\n", classification_report(gbc_y_predict, y_test, target_names=['died', 'survived']))
    103 
    104 '''
    105 单一决策树准确度: 0.7811550151975684
    106 其他指标:
    107               precision    recall  f1-score   support
    108 
    109        died       0.91      0.78      0.84       236
    110    survived       0.58      0.80      0.67        93
    111 
    112 avg / total       0.81      0.78      0.79       329
    113 
    114 随机森林准确度: 0.78419452887538
    115 其他指标:
    116               precision    recall  f1-score   support
    117 
    118        died       0.91      0.78      0.84       237
    119    survived       0.58      0.80      0.68        92
    120 
    121 avg / total       0.82      0.78      0.79       329
    122 
    123 梯度提升决策树准确度: 0.790273556231003
    124 其他指标:
    125               precision    recall  f1-score   support
    126 
    127        died       0.92      0.78      0.84       239
    128    survived       0.58      0.82      0.68        90
    129 
    130 avg / total       0.83      0.79      0.80       329
    131 
    132 '''
    展开全文
  • 决策树(Decision Tree)是一种基本的分类与回归方法。本文会讨论决策树中的分类树与回归树,后续文章会继续讨论决策树的BoostingBagging的相关...用决策树分类,从根结点开始,对实例的某一特征进行测试,根据测...

    分类目录:《深入理解机器学习》总目录
    相关文章:
    基于决策树的模型(一)分类树和回归树
    基于树的模型(二):集成学习之Bagging和Random Forest
    基于树的模型(三):集成学习之GBDT和XGBoost
    基于树的模型(四):随机森林的延伸——深度森林(gcForest)
    基于树的模型(五):从零开始用Python实现ID3决策树
    基于树的模型(六):Python实现CART决策树并利用Tkinter构建GUI对决策树进行调优
    基于树的模型(七):RF/XGBoost等算法实践与决策树Scala实践等(材料准备中)


    决策树(Decision Tree)是一种基本的分类与回归方法,当决策树用于分类时称为分类树,用于回归时称为回归树。本文主要讨论决策树中的分类树与回归树的一些基本理论,后续文章会继续讨论决策树的BoostingBagging相关方法。

    决策树由结点和有向边组成。结点有两种类型:内部结点和叶结点,其中内部结点表示一个特征或属性,叶结点表示一个类。一般的,一棵决策树包含一个根结点、若干个内部结点和若干个叶结点。叶结点对应于决策结果,其他每个结点则对应于一个属性测试。每个结点包含的样本集合根据属性测试的结果被划分到子结点中,根结点包含样本全集,从根结点到每个叶结点的路径对应了一个判定测试序列。在下图中,圆和方框分别表示内部结点和叶结点。决策树学习的目的是为了产生一棵泛化能力强,即处理未见示例能力强的决策树。
    j决策树图示

    分类树

    分类树是一种描述对实例进行分类的树形结构。在使用分类树进行分类时,从根结点开始,对实例的某一特征进行测试,根据测试结果,将实例分配到其子结点。这时,每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配,直至达到叶结点。最后将实例分到叶结点的类中。

    假设给定训练数据集:
    D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } D=\{(x_1, y_1), (x_2, y_2), ..., (x_N, y_N)\} D={(x1,y1),(x2,y2),...,(xN,yN)}其中, x i = ( x i ( 1 ) , x i ( 2 ) , . . . , x i ( n ) ) T , x_i=(x_i^{(1)}, x_i^{(2)}, ..., x_i^{(n)})^T, xi=(xi(1),xi(2),...,xi(n))T,为输入实例,即特征向量, n n n为特征个数, i = 1 , 2 … , N i=1,2…,N i=12N N N N为样本容量, y i ∈ { 1 , 2 , . . . , K } y_i \in \{ 1, 2, ..., K\} yi{1,2,...,K}为类标。分类树学习的目标是根据给定的训练数据集构建一个决策树模型,使它能够对实例进行正确的分类。

    决策树学习本质上是从训练数据集中归纳出一组分类规则。与训练数据集不相矛盾的决策树(即能对训练数据进行正确分类的决策树)可能有多个,也可能一个也没有。我们需要的是一个与训练数据矛盾较小的决策树,同时具有很好的泛化能力。从另一个角度看,决策树学习是由训练数据集估计条件概率模型。基于特征空间划分的类的条件概率模型有无穷多个,我们选择的条件概率模型应该不仅对训练数据有很好的拟合,而且对未知数据有很好的预测。

    决策树学习用损失函数表示这一目标,其损失函数通常是正则化的极大似然函数,决策树学习的策略是以损失函数为目标函数的最小化。当损失函数确定以后,学习问题就变为在损失函数意义下选择最优决策树的问题。因为从所有可能的决策树中选取最优决策树是NP完全问题,所以现实中决策树学习算法通常采用启发式方法,近似求解这一最优化问题。这样得到的决策树是次最优的。

    决策树分类算法
    输入:
    \qquad 训练集: D = ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯   , ( x N , y N ) D = {(x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N)} D=(x1,y1),(x2,y2),,(xN,yN)
    \qquad 属性集: A = a 1 , a 2 , ⋯   , a n A = {a_1, a_2, \cdots, a_n} A=a1,a2,,an
    过程:
    \qquad 函数 T r e e G e n e r a t e ( D , A ) TreeGenerate(D, A) TreeGenerate(D,A)
    输出:
    \qquad 以node为根节点的决策树
    算法:
    ( 1 ) 生成结点根node
    ( 2 ) if D D D中样本全属于同一类别 C k C_k Ck then
    ( 3 ) \quad 将node标记为 C k C_k Ck类叶结点
    ( 4 ) \quad return
    ( 5 ) end if
    ( 6 ) if A = ∅ A = \varnothing A= OR D D D中样本在 A A A上取值相同 then
    ( 7 ) \quad 将node标记为叶结点,其类别标记为 D D D中样本数最多的类
    ( 8 ) \quad return
    ( 9 )end if
    (10)从 A A A中选择最优划分属性 a ∗ a_* a
    (11)for a ∗ a_* a 的每一个值 a ∗ v a_*^v av do
    (12) \quad 为node生成一个分支:令 D v D_v Dv表示 D D D中在 a ∗ a_* a上取值为 a ∗ v a_*^v av的样本子集
    (13) \quad if D v D_v Dv为空 then
    (14) \qquad 将分支结点标记为叶结点,其类别标记为 D D D中样本最多的类
    (15) \qquad return
    (16) \quad else
    (17) \qquad T r e e G e n e r a t e ( D v , A − { a ∗ } ) TreeGenerate(D_v, A - \{a_*\}) TreeGenerate(Dv,A{a})为分支结点
    (18) \quad end if
    (19)end for

    决策树学习的算法通常是一个递归地选择最优特征,并根据该特征对训练数据进行分割,使得对各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分,也对应着决策树的构建。开始,构建根结点,将所有训练数据都放在根结点。选择一个最优特征,按照这一特征将训练数据集分割成子集,使得各个子集有一个在当前条件下最好的分类。如果这些子集已经能够被基本正确分类,那么构建叶结点,并将这些子集分到所对应的叶结点中去,如果还有子集不能被基本正确分类,那么就对这些子集选择新的最优特征,继续对其进行分割,构建相应的结点。如此递归地进行下去,直至所有训练数据子集被基本正确分类,或者没有合适的特征为止。最后每个子集都被分到叶结点上,即都有了明确的类。这就生成了一棵决策树。

    从上述过程中就可以看出,决策树的生成是一个递归过程。在决策树基本算法中,有三种情形会导致递归返回

    1. 当前结点包含的样本全属于同一类别,无需划分
    2. 当前属性集为空,或是所有样本在所有属性上取值相同,无法划分
    3. 当前结点包含的样本集合为空,不能划分

    在第二种情形下,我们把当前结点标记为叶结点,并将其类别设定为该结点所含样本最多的类别。在第三种情形下,同样把当前结点标记为叶结点,但将其类别设定为其父结点所含样本最多的类别。这两种情形的处理实质不同:第二种情况是在利用当前结点的后验分布,而第三种情况则是把父结点的样本分布作为当前结点的先验分布

    以上方法生成的决策树可能对训练数据有很好的分类能力,但对未知的测试数据却未必有很好的分类能力,即可能发生过拟合现象。我们需要对已生成的树自下而上进行剪枝,将树变得更简单,从而使它具有更好的泛化能力。具体地,就是去掉过于细分的叶结点,使其回退到父结点,甚至更高的结点,然后将父结点或更高的结点改为新的叶结点。如果特征数量很多,也可以在决策树学习开始的时候,对特征进行选择,只留下对训练数据有足够分类能力的特征。

    可以看出,决策树学习算法包含特征选择决策树的生成决策树的剪枝过程。由于决策树表示一个条件概率分布,所以深浅不同的决策树对应着不同复杂度的概率模型。决策树的生成对应于模型的局部选择,决策树的剪枝对应于模型的全局选择。决策树的生成只考虑局部最优,相对地,决策树的剪枝则考虑全局最优。

    决策树模型呈树形结构,在分类问题中,表示基于特征对实例进行分类的过程。它可以认为是if-then规则的集合,也可以认为是定义在特征空间与类空间上的条件概率分布。分类树具有良好的可读性与分类速度快的优点。分类树在学习时,利用训练数据,根据损失函数最小化的原则建立分类树模型,在预测时,对新的数据,利用分类树模型进行分类。决策树学习通常包括3个步骤:特征选择、决策树的生成和决策树的修剪。

    决策树与if-then规则

    可以将决策树看成一个if-then规则的集合:由决策树的根结点到叶结点的每一条路径构建一条规则,路径上内部结点的特征对应着规则的条件,而叶结点的类对应着规则的结论。决策树的路径或其对应的if-then规则集合具有一个重要的性质——互斥并且完备。这就是说,每一个实例都被一条路径或一条规则所覆盖,而且只被一条路径或一条规则所覆盖。这里所谓覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件。

    决策树与条件概率分布

    决策树还表示给定特征条件下类的条件概率分布。这一条件概率分布定义在特征空间的一个划分上。将特征空间划分为互不相交的单元或区域,并在每个单元定义一个类的概率分布就构成了一个条件概率分布。决策树的一条路径对应于划分中的一个单元。决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。假设 X X X为表示特征的随机变量, Y Y Y为表示类的随机变量,那么这个条件概率分布可以表示为 P ( Y ∣ X ) P(Y|X) PYX X X X取值于给定划分下单元的集合, Y Y Y取值于类的集合。各叶结点(单元)上的条件概率往往偏向某一个类,即属于某一类的概率较大。决策树分类时将该结点的实例强行分到条件概率大的那一类去。

    决策树的优缺点
    • 计算复杂度不高
    • 对中间缺失值不敏感
    • 解释性强,在解释性方面甚至比线性回归更强
    • 与传统的回归和分类方法相比,决策树更接近人的决策模式
    • 可以用图形表示,非专业人士也可以轻松理解
    • 可以直接处理定性的预测变量而不需创建哑变量
    • 决策树的预测准确性一般比回归和分类方法弱,但可以通过用集成学习方法组合大量决策树,显著提升树的预测效果

    特征选择

    特征选择在于选取对训练数据具有分类能力的特征。这样可以提高决策树学习的效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别,则称这个特征是没有分类能力的。经验上扔掉这样的特征对决策树学习的精度影响不大。比如,我们希望构建一棵决策树来根据不同人的各种属性来预测每个人性别,那么对于属性“头发的长度”可能就要比属性“头发的颜色”所能包含的信息更多。因为一般来说,男生的头发要比女生的头发短,所以我们希望“头发的长度”这个属性处于决策树的上部。随着划分过程不断进行,我们希望决策树的分支结点所包含的样本尽可能属于同一类别,即结点的“纯度”(purity)越来越高。

    信息增益

    为了便于说明信息增益,先给出熵与条件熵的定义。在信息论与概率统计中,熵(entropy)是表示随机变量不确定性的度量。设 X X X是一个取有限个值的离散随机变量,其概率分布为:
    P ( X = x i ) = p i , i = 1 , 2 , ⋯   , n P(X = x_i) = p_i, i = 1, 2, \cdots, n P(X=xi)=pi,i=1,2,,n
    则随机变量 X X X的熵定义为:
    H ( X ) = − ∑ i = 1 n p i log ⁡ p i H(X) = -\sum_{i = 1}^n p_i \log p_i H(X)=i=1npilogpi
    在上式中,若 p i = 0 p_i = 0 pi=0,则定义 p i log ⁡ p i = 0 p_i \log p_i = 0 pilogpi=0。通常,上式中的对数以 2 2 2为底或以 e e e为底(自然对数),这时熵的单位分别称作比特(bit)或纳特(nat).由定义可知,熵只依赖于 X X X的分布,而与 X X X的取值无关,所以也可将 X X X的熵记作 H ( p ) H(p) H(p),即:
    H ( p ) = − ∑ i = 1 n p i log ⁡ p i H(p) = -\sum_{i = 1}^n p_i \log p_i H(p)=i=1npilogpi
    由此可见,熵越大,随机变量的不确定性就越大。从熵的定义可验证
    0 ≤ H ( p ) ≤ log ⁡ n 0 \leq H(p) \leq \log n 0H(p)logn
    当随机变量只取两个值,例如1,0时,即 X X X的分布为:
    P ( X = 1 ) = p , P ( X = 0 ) = 1 − p , 0 ≤ p ≤ 1 P(X = 1) = p,\quad P(X = 0) = 1-p, \quad 0≤p≤1 P(X=1)=p,P(X=0)=1p,0p1
    其熵为:
    H ( p ) = − p log ⁡ 2 p − ( 1 − p ) log ⁡ 2 ( 1 − p ) H(p) = -p \log_2 p - (1 - p)\log_2 (1 - p) H(p)=plog2p(1p)log2(1p)
    这时,熵 H ( p ) H(p) H(p)随概率 p p p变化的曲线如下图所示(单位为比特):
    熵的变化曲线
    p = 0 p = 0 p=0 p = 1 p = 1 p=1 H ( p ) = 0 H(p) = 0 H(p)=0,随机变量完全没有不确定,当 p = 0.5 p = 0.5 p=0.5时, H ( p ) = 1 H(p) = 1 H(p)=1,熵取值最大,随机变量不确定性最大。

    设有随机变量 ( X , Y ) (X, Y) (X,Y),其联合概率分布为:

    P ( X = x i , Y = y i ) = p i j { i = 1 , 2 , ⋯   , n j = 1 , 2 , ⋯   , m P(X = x_i, Y = y_i) = p_{ij} \quad \begin{cases} i = 1, 2, \cdots, n \\ j = 1, 2, \cdots, m \end{cases} P(X=xi,Y=yi)=pij{i=1,2,,nj=1,2,,m

    条件熵 H ( Y ∣ X ) H(Y|X) H(YX)表示在已知随机变量 X X X的条件下随机变量 Y Y Y的不确定性。随机变量 X X X给定的条件下随机变量 Y Y Y的条件熵(conditional entropy) H ( Y ∣ X ) H(Y|X) H(YX),定义为 X X X给定条件下 Y Y Y的条件概率分布的熵对 X X X的数学期望:
    H ( Y ∣ X ) = ∑ i = 1 n p i H ( Y ∣ X = x i ) H(Y|X) = \sum_{i = 1}^n p_iH(Y|X = x_i) H(YX)=i=1npiH(YX=xi)

    其中, p i = P ( X = x i ) , i = 1 , 2 , ⋯   , n p_i = P(X = x_i), i = 1, 2, \cdots, n pi=P(X=xi),i=1,2,,n

    当熵和条件熵中的概率由数据估计(如极大似然估计)得到时,所对应的熵与条件熵分别称为经验熵(empirical entropy)和经验条件熵(empirical conditional entropy)。此时,如果有0概率,令 0 log ⁡ 0 = 0 0\log0 = 0 0log0=0

    信息增益(information gain)表示得知特征 X X X的信息而使得类 Y Y Y的信息的不确定性减少的程度。特征 a ∗ a_* a对训练数据集 D D D的信息增益 g ( D , a ∗ ) g(D, a_*) g(D,a),定义为集合 D D D的经验熵 H ( D ) H(D) H(D)与特征 a ∗ a_* a给定条件下 D D D的经验条件熵 H ( D ∣ a ∗ ) H(D|a_*) H(Da)之差,即:
    g ( D , a ∗ ) = H ( D ) − H ( D ∣ a ∗ ) g(D, a_*) = H(D) - H(D|a_*) g(D,a)=H(D)H(Da)
    一般地,熵 H ( Y ) H(Y) H(Y)与条件熵 H ( Y ∣ X ) H(Y|X) H(YX)之差称为互信息(mutual information)。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

    决策树学习应用信息增益准则选择特征。给定训练数据集 D D D和特征 a ∗ a_* a,经验熵 H ( D ) H(D) H(D)表示对数据集 D D D进行分类的不确定性。而经验条件熵 H ( D ∣ a ∗ ) H(D|a_*) H(Da)表示在特征 a ∗ a_* a给定的条件下对数据集 D D D进行分类的不确定性。那么它们的差,即信息增益,就表示由于特征 a ∗ a_* a而使得对数据集 D D D的分类的不确定性减少的程度。显然,对于数据集 D D D而言,信息增益依赖于特征,不同的特征往往具有不同的信息增益,信息增益大的特征具有更强的分类能力。

    根据信息增益准则的特征选择方法:对训练数据集(或子集) D D D,计算其每个特征的信息增益,并比较它们的大小,选择信息增益最大的特征。

    设训练数据集为 D D D ∣ D ∣ |D| D表示其样本容量,即样本个数。设有 K K K个类 C k C_k Ck k = 1 , 2 , ⋯   , K k=1, 2, \cdots, K k=1,2,,K ∣ C k ∣ |C_k| Ck为属于类 C k C_k Ck的样本个数, ∑ k = 1 K ∣ C k ∣ = ∣ D ∣ \sum_{k=1}^K |C_k| = |D| k=1KCk=D。设特征 a ∗ a_* a V V V个不同的取值 { a ∗ 1 , a ∗ 2 , ⋯   , a ∗ V } \{ a_*^1, a_*^2, \cdots, a_*^V\} {a1,a2,,aV},根据特征 a ∗ a_* a的取值将 D D D划分为 V V V个子集 D 1 , D 2 , ⋯   , D V D_1, D_2, \cdots, D_V D1,D2,,DV ∣ D t ∣ |D_t| Dt D t D_t Dt的样本个数, ∑ i = 1 n ∣ D t ∣ = ∣ D ∣ \sum_{i=1}^n|D_t|=|D| i=1nDt=D。记子集 D i D_i Di中属于类 C k C_k Ck的样本的集合为 D i k D_{ik} Dik。即 D i k = D i ∩ C k D_{ik} = D_i \cap C_k Dik=DiCk ∣ D i k ∣ |D_{ik}| Dik D i k D_{ik} Dik的样本个数。于是计算信息增益的方法如下:

    信息增益
    输入:训练数据集 D D D和特征 a ∗ a_* a
    输出:特征 a ∗ a_* a对训练数据集 D D D的信息增益 g ( D , a ∗ ) g(D, a_*) g(D,a)
    1.计算数据集 D D D的经验熵 H ( D ) H(D) H(D) H ( D ) = − ∑ k = 1 K C k D log ⁡ 2 C k D H(D) = -\sum_{k=1}^K \frac{C_k}{D}\log_2\frac{C_k}{D} H(D)=k=1KDCklog2DCk
    2.计算特征 A A A对数据集 D D D的经验条件熵 H ( D ∣ A ) H(D|A) H(DA) H ( D ∣ A ) = ∑ i = 1 n ∣ D i ∣ D H ( D i ) = − ∑ i = 1 n ∣ D i ∣ D ∑ k = 1 K D i k D i log ⁡ 2 D i k D i H(D|A) = \sum_{i=1}^n\frac{|D_i|}{D}H(D_i)=-\sum_{i=1}^n\frac{|D_i|}{D}\sum_{k=1}^K\frac{D_{ik}}{D_i}\log_2\frac{D_{ik}}{D_i} H(DA)=i=1nDDiH(Di)=i=1nDDik=1KDiDiklog2DiDik
    3.计算信息增益: g ( D , a ∗ ) = H ( D ) − H ( D ∣ a ∗ ) g(D, a_*) = H(D) - H(D|a_*) g(D,a)=H(D)H(Da)

    一般而言,信息增益越大,则意味着使用特征 a ∗ a_* a来进行划分所获得的“纯度提升”越大。因此,我们可用信息增益来进行决策树的划分属性选择,即在上述决策树分类算法第10行使用 a ∗ = arg  max ⁡ a ∈ A g ( D , a ) a_* = \text{arg}\ \max_{a \in A}g(D, a) a=arg maxaAg(D,a)选择最优划分属性。著名的ID3决策树学习算法就是以信息增益为准则来选择划分属性。

    ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征,递归地构建决策树。具体方法是:从根结点开始,对结点计算所有可能的特征的信息增益,选择信息增益最大的特征作为结点的特征,由该特征的不同取值建立子结点。之后,再对子结点递归地调用以上方法,构建决策树,直到所有特征的信息增益均很小或没有特征可以选择为止,最终得到一个决策树。ID3相当于用极大似然法进行概率模型的选择

    ID3算法
    输入:训练数据集 D D D,特征集 A A A,阈值 ϵ \epsilon ϵ
    输出:决策树 T T T
    1.若 D D D中所有实例属于同一类 C k C_k Ck,则 T T T为单结点树,并将类 C k C_k Ck作为该结点的类标记,返回决策树 T T T
    2.若 A = ∅ A = \varnothing A=,则 T T T为单结点树,并将 D D D中实例数最大的类 C k C_k Ck,作为该结点的类标记,返回决策树 T T T
    3.否则,计算 A A A中各特征对 D D D的信息增益,选择信息增益最大的特征 a ∗ a_* a
    4.如果 a ∗ a_* a的信息增益小于阈值 ϵ \epsilon ϵ,则置 T T T为单结点树,并将 D D D中实例数最大的类 C k C_k Ck作为该结点的类标记,返回决策树 T T T
    5.否则,对 a ∗ a_* a的每一可能值 a ∗ v a_*^v av,依 a ∗ = a ∗ v a_* = a_*^v a=av D D D分割为若干非空子集 D v D_v Dv,将 D v D_v Dv中实例数最大的类作为标记,构建子结点,由结点及其子结点构成决策树 T T T,返回决策树 T T T
    6.对第 v v v个子结点,以 D v D_v Dv为训练集,以 A − { a ∗ } A - \{a_*\} A{a}为特征集,递归地调用第(1)步~第(5)步,得到子树 T v T_v Tv,并返回子树 T v T_v Tv

    信息增益率

    信息增益值的大小是相对于训练数据集而言的,并没有绝对意义。在训练数据集的经验熵大的时候,信息增益值会偏大。反之,信息增益值会偏小。使用信息增益率(information gain ratio)可以对这一问题进行校正。这是特征选择的另一准则。特征 a ∗ a_* a对训练数据集 D D D的信息增益率 g g ( D , a ∗ ) g_g(D, a_*) gg(D,a)定义为其信息增益 g ( D , a ∗ ) g(D, a_*) g(D,a)与训练数据集 D D D的经验熵 H ( D ) H(D) H(D)之比:
    g g ( D , a ∗ ) = g ( D , a ∗ ) H ( D ) g_g(D, a_*) = \frac{g(D, a_*)}{H(D)} gg(D,a)=H(D)g(D,a)

    如前文所说,信息增益准则对可取值数目较多的属性有所偏好,为减少这种偏好可能带来的不利影响,著名的C4.5决策树算法不直接使用信息增益来选择划分属性,而是使用信息增益率来选择最优划分属性。

    C4.5算法
    输入:训练数据集 D D D,特征集 A A A,信息增益率阈值 ϵ \epsilon ϵ,信息增益阈值 α \alpha α
    输出:决策树 T T T
    1.若 D D D中所有实例属于同一类 C k C_k Ck,则 T T T为单结点树,并将类 C k C_k Ck作为该结点的类标记,返回决策树 T T T
    2.若 A = ∅ A = \varnothing A=,则 T T T为单结点树,并将 D D D中实例数最大的类 C k C_k Ck,作为该结点的类标记,返回决策树 T T T
    3.否则,计算 A A A中各特征对 D D D的信息增益和信息增益率,在信息增益大于 α \alpha α的特征中选择信息增益率最大的特征 a ∗ a_* a
    4.如果 a ∗ a_* a的信息增益率小于阈值 ϵ \epsilon ϵ,则置 T T T为单结点树,并将 D D D中实例数最大的类 C k C_k Ck作为该结点的类标记,返回决策树 T T T
    5.否则,对 a ∗ a_* a的每一可能值 a ∗ v a_*^v av,依 a ∗ = a ∗ v a_* = a_*^v a=av D D D分割为若干非空子集 D v D_v Dv,将 D v D_v Dv中实例数最大的类作为标记,构建子结点,由结点及其子结点构成决策树 T T T,返回决策树 T T T
    6.对第 v v v个子结点,以 D v D_v Dv为训练集,以 A − { a ∗ } A - \{a_*\} A{a}为特征集,递归地调用第(1)步~第(5)步,得到子树 T v T_v Tv,并返回子树 T v T_v Tv

    需注意的是,信息增益率准则对可取值数目较少的属性有所偏好,因此,C4.5算法并不是直接选择增益率最大的候选划分属性,而是使用了一个启发式的方法选择最优划分属性:先从候选划分属性中找出信息增益高于平均水平的属性,再从中选择增益率最高的.。

    连续值处理

    实际的任务中常会遇到连续属性,对于全部为连续属性的样本来说,我们一般使用回归决策树来处理。C4.5算法则采用了二分法对连续属性进行处理。由于连续属性的可取值数目不再有限,因此,不能直接根据连续属性的可取值来对结点进行划分。此时,连续属性离散化技术可派上用场。最简单的策略是采用二分法对连续属性进行处理。

    给定样本集 D D D和连续属性 a a a,假定 a a a D D D上出现了 n n n个不同的取值,将这些值从小到大进行排序,记为 { a 1 , a 2 , a 3 , ⋯   , a n } \{a_1, a_2, a_3, \cdots, a_n\} {a1,a2,a3,,an}。基于划分点 t t t可将 D D D分为子集 D t + D_t^+ Dt+ D t − D_t^- Dt,其中 D t + D_t^+ Dt+包含那些在属性 a a a上取值大于 t t t的样本,而 D t − D_t^- Dt则包含那些在属性 a a a上取值不大于 t t t的样本。显然,对相邻的属性取值 a i a^i ai a i + 1 a^{i + 1} ai+1来说, t t t在区间 [ a i , a i + 1 ) [a^i, a^{i + 1}) [ai,ai+1)中取任意值所产生的划分结果相同.因此,对连续属性 a a a,我们可考察包含 n − 1 n-1 n1个元素的候选划分点集合:
    T a = { a i + a i + 1 2   ∣   1 ≤ i ≤ n − 1 } T_a = \{\frac{a^i + a^{i + 1}}{2} \ | \ 1 \leq i \leq n - 1\} Ta={2ai+ai+1  1in1}

    即把区间 [ a i , a i + 1 ) [a^i, a^{i + 1}) [ai,ai+1)的中位点 a i + a i + 1 2 \frac{a^i + a^{i + 1}}{2} 2ai+ai+1作为候选划分点。然后,我们就可像离散属性值一样来考察这些划分点,选取最优的划分点进行样本集合的划分:
    G a i n ( D , a ) = max ⁡ t ∈ T a G a i n ( D , a , t ) = max ⁡ t ∈ T a E n t ( D ) − ∑ λ ∈ { − , + } D t λ D E n t ( D t λ ) \begin{aligned} Gain(D, a) &= \max_{t \in T_a} Gain(D, a, t)\\ & = \max_{t \in T_a} Ent(D) - \sum_{\lambda \in \{-, +\}} \frac{D^\lambda _t}{D}Ent(D^\lambda _t) \end{aligned} Gain(D,a)=tTamaxGain(D,a,t)=tTamaxEnt(D)λ{,+}DDtλEnt(Dtλ)

    其中 G a i n ( D , a , t ) Gain(D, a, t) Gain(D,a,t)是样本集 D D D基于划分点 t t t二分后的信息增益。于是,我们就可选择使 G a i n ( D , a , t ) Gain(D, a, t) Gain(D,a,t)最大化的划分点。

    缺失值处理

    现实任务中常会遇到不完整样本,即样本的某些属性值缺失。且在属性数目较多的情况下,有时会有大量样本出现缺失值。如果简单地放弃不完整样本,仅使用无缺失值的样本来进行学习,显然是对数据信息极大的浪费。显然,有必要考虑利用有缺失属性值的训练样例来进行学习。

    划分属性的选择

    给定训练集 D D D和属性 a a a,令 D ~ \tilde{D} D~表示 D D D中在属性 a a a上没有缺失值的样本子集。显然,我们仅可根据 D ~ \tilde{D} D~来判断属性 a a a的优劣。假定属性 a a a V V V个可取值 { a 1 , a 2 , a 3 , ⋯   , a V } \{a^1, a^2, a^3, \cdots, a^V\} {a1,a2,a3,,aV},令 D ~ v \tilde{D}^v D~v表示 D ~ \tilde{D} D~中在属性 a a a上取值为 a v a^v av的样本子集, D ~ k \tilde{D}_k D~k表示 D ~ \tilde{D} D~中属于第 k k k ( k = 1 , 2 , 3 , ⋯   , K ) (k = 1, 2, 3, \cdots, K) (k=1,2,3,,K)的样本子集,则显然有 D ~ = ⋃ k = 1 K D ~ k \tilde{D} = \bigcup^K_{k = 1}\tilde{D}_k D~=k=1KD~k D ~ = ⋃ v = 1 V D ~ v \tilde{D} = \bigcup^V_{v = 1}\tilde{D}^v D~=v=1VD~v。假定我们为每个样本 x x x赋予一个权重 ω x \omega_x ωx,并定义:
    ρ = ∑ x ∈ D ~ ω x ∑ x ∈ D ω x p ~ k = ∑ x ∈ D ~ k ω x ∑ x ∈ D ~ ω x r ~ v = ∑ x ∈ D ~ v ω x ∑ x ∈ D ~ ω x \begin{aligned} \rho & = \frac{\sum_{x \in \tilde{D}}\omega_x}{\sum_{x \in D}\omega_x}\\ \tilde{p}_k & = \frac{\sum_{x \in \tilde{D}_k}\omega_x}{\sum_{x \in \tilde{D}}\omega_x}\\ \tilde{r}_v & = \frac{\sum_{x \in \tilde{D}^v}\omega_x}{\sum_{x \in \tilde{D}}\omega_x} \end{aligned} ρp~kr~v=xDωxxD~ωx=xD~ωxxD~kωx=xD~ωxxD~vωx

    直观地看,对于属性 a a a ρ \rho ρ表示无缺失值样本所占的比例, p ~ k \tilde{p}_k p~k表示无缺失值样本中第 k k k类所占的比例, r ~ v \tilde{r}_v r~v则表示无缺失值样本中在属性 a a a上取值 a v a^v av的样本所占的比例。基于上述定义,我们可将信息增益的计算式推广为:
    G a i n ( D , a ) = ρ × G a i n ( D ~ , a ) = ρ × ( E n t ( D ~ ) − ∑ x = 1 V r ~ v E n t ( D ~ v ) ) \begin{aligned} Gain(D, a) &= \rho \times Gain(\tilde{D}, a)\\ & = \rho \times (Ent(\tilde{D}) - \sum_{x = 1}^V \tilde{r}_v Ent(\tilde{D}^v)) \end{aligned} Gain(D,a)=ρ×Gain(D~,a)=ρ×(Ent(D~)x=1Vr~vEnt(D~v))

    对样本进行划分

    根据上面的定义,若样本 x x x在划分属性 a a a上的取值已知,则将 x x x划入与其取值对应的子结点,且样本权值在子结点中保持为 ω x \omega_x ωx。若样本 x x x在划分属性 a a a上的取值未知,则将 x x x同时划入所有子结点,且样本权值在与属性值 a v a^v av对应的子结点中调整为 r ~ v × ω x \tilde{r}_v \times \omega_x r~v×ωx。直观地看,这就是让同一个样本以不同的概率划入到不同的子结点中去。

    基尼指数

    数据集 D D D的纯度还可用基尼值来度量:
    G i n i ( D ) = ∑ k = 1 K p k ( 1 − p k ) = 1 − ∑ k = 1 K p k 2 Gini(D) = \sum^K_{k=1}p_k(1 - p_k) = 1 - \sum^K_{k=1}p_k^2 Gini(D)=k=1Kpk(1pk)=1k=1Kpk2

    其中, K K K为类别数, p k p_k pk为样本点属于第 k k k类的概率。对于二类分类问题,若样本点属于第1个类的概率是 p p p,则概率分布的基尼指数为:
    G i n i ( D ) = 2 p ( 1 − p ) Gini(D) = 2p(1 - p) Gini(D)=2p(1p)

    直观来说, G i n i ( D ) Gini(D) Gini(D)反映了从数据集 D D D中随机抽取两个样本,其类别标记不一致的概率。因此, G i n i ( D ) Gini(D) Gini(D)越小,则数据集 D D D的纯度越高。对于属性 a a a的基尼指数定义为:
    G i n i _ i n d e x ( D , a ) = ∑ v = 1 V D v D G i n i ( D v ) Gini\_index(D, a) = \sum^V_{v = 1}\frac{D^v}{D}Gini(D^v) Gini_index(D,a)=v=1VDDvGini(Dv)

    CART算法中,我们在候选属性集合 A A A中,选择那个使得划分后基尼指数最小的属性作为最优划分属性,即: a ∗ = arg min ⁡ a ∈ A G i n i _ i n d e x ( D , a ) a_* = \text{arg}\min_{a \in A}Gini\_index(D, a) a=argminaAGini_index(D,a)

    在二类分类问题中,基尼指数 G i n i ( D ) Gini(D) Gini(D)、熵 H ( p ) H(p) H(p)的一半,和分类误差率的关系:
    特征选择方法对比
    其中,横坐标表示概率 p p p,纵坐标表示损失。可以看出基尼指数和熵的一半的曲线很接近,都可以近似地代表分类误差率。

    分类树的剪枝

    剪枝(pruning)是决策树学习算法对付“过拟合”的主要手段。在决策树学习中,为了尽可能正确分类训练样本,结点划分过程将不断重复,有时会造成决策树分支过多,这时就可能因为对训练样本学习得“太好”了,以致于把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合。因此,可通过主动去掉一些分支来降低过拟合的风险。决策树剪枝的基本策略有预剪枝后剪枝

    预剪枝

    预剪枝是指在决策树生成过程中,对每个结点在划分前先进行估计,若当前结点的划分不能带来决策树泛化性能提升,则停止划分并将当前结点标记为叶结点。停止决策树生长常用方法:

    1. 定义一个高度,当决策树达到该高度时就停止决策树的生长
    2. 达到某个节点的实例具有相同的特征向量,即使这些实例不属于同一类,也可以停止决策树的生长。这个方法对于处理数据的数据冲突问题比较有效。
    3. 定义一个阈值,当达到某个节点的实例个数小于阈值时就可以停止决策树的生长
    4. 定义一个阈值,通过计算每次扩张对系统性能的增益,并比较增益值与该阈值大小来决定是否停止决策树的生长。

    后剪枝

    后剪枝则是先从训练集生成一棵完整的决策树,然后自底向上地对非叶结点进行考察,若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升,则将该子树替换为叶结点。相比于预剪枝,后剪枝更常用,因为在预剪枝中精确地估计何时停止树增长很困难。

    错误率降低剪枝(REP,Reduced-Error Pruning)

    错误率降低剪枝方法是一种比较简单的后剪枝的方法。在该方法中,可用的数据被分成两个样例集合:首先是训练集,它被用来形成学习到的决策树,另一个是与训练集分离的验证集,它被用来评估这个决策树在后续数据上的精度,确切地说是用来评估修剪这个决策树的影响。学习器可能会被训练集中的随机错误和巧合规律所误导,但验证集合不大可能表现出同样的随机波动。所以验证集可以用来对过度拟合训练集中的虚假特征提供防护检验。

    错误率降低剪枝方法考将树上的每个节点作为修剪的候选对象,再决定是对该节点进行剪枝:

    1. 删除以此结点为根的子树
    2. 使其成为叶子结点
    3. 当修剪后的树对于验证集合的性能不比修剪前的树的性能差时,则确认删除该结点,否则恢复该节点

    因为训练集合的过拟合,使得验证集合数据能够对其进行修正,反复进行上面的操作,从底向上的处理结点,删除那些能够提高验证集合的精度的结点,直到进一步修剪会降低验证集合的精度为止。

    错误率降低剪枝方法是最简单的后剪枝方法之一,不过由于使用独立的测试集,原始决策树相比,修改后的决策树可能偏向于过度修剪。这是因为一些不会再次在测试集中出现的很稀少的训练集实例所对应的分枝在剪枝过程中往往会被剪枝。尽管错误率降低剪枝方法有这个缺点,不过错误率降低剪枝方法仍然作为一种基准来评价其它剪枝算法的性能。它对于两阶段决策树学习方法的优点和缺点提供了一个很好的学习思路。由于验证集合没有参与决策树的构建,所以用错误率降低剪枝方法剪枝后的决策树对于测试样例的偏差要好很多,能够解决一定程度的过拟合问题。

    悲观错误剪枝(PEP,Pesimistic-Error Pruning)

    悲观错误剪枝方法是根据剪枝前后的错误率来判定子树的修剪。它不需要像错误率降低修剪方法那样,需要使用部分样本作为测试数据,而是完全使用训练数据来生成决策树,并进行剪枝,即决策树生成和剪枝都使用训练集

    该方法引入了统计学中连续修正的概念弥补错误率降低剪枝方法中的缺陷,在评价子树的训练错误公式中添加了一个常数,即假定每个叶子结点都自动对实例的某个部分进行错误的分类。

    把一颗具有多个叶子节点的子树的分类用一个叶子节点来替代的话,在训练集上的误判率肯定是上升的,但是在新数据上不一定。于是我们把子树的误判计算加上一个经验性的惩罚因子来做是否剪枝的考量指标。对于一个叶子节点,它覆盖了 N N N个样本,其中有 E E E个错误,那么该叶子节点的错误率为 E + 0.5 N \frac{E + 0.5}{N} NE+0.5。这个 0.5 0.5 0.5就是惩罚因子,那么一颗子树,它有 L L L个叶子节点,那么该子树的误判率估计为:
    ∑ E i + 0.5 ∗ L ∑ N i \frac{\sum E_i +0.5 * L}{\sum N_i} NiEi+0.5L

    这样的话,我们可以看到一棵子树虽然具有多个子节点,但由于加上了惩罚因子,所以子树的误判率计算未必占到便宜。剪枝后内部节点变成了叶子节点,其误判个数 E E E也需要加上一个惩罚因子,变成 E + 0.5 E+0.5 E+0.5,那么子树是否可以被剪枝就取决于剪枝后的错误 E + 0.5 E+0.5 E+0.5在的标准误差内。对于样本的误差率 e e e,我们可以根据经验把它估计成各种各样的分布模型,比如二项式分布、正态分布等。如果 E + 0.5 < E i + S E ( E i ) E+0.5 < E_i + SE(E_i) E+0.5<Ei+SE(Ei)则对 i i i进行剪枝。

    代价复杂度剪枝(CCP,Cost-Complexity Pruning)

    代价复杂度剪枝算法为子树 T t T_t Tt定义了代价和复杂度,以及一个可由用户设置的衡量代价与复杂度之间关系的参数 α α α。其中,代价指在剪枝过程中因子树 T t T_t Tt被叶节点替代而增加的错分样本,复杂度表示剪枝后子树 T t T_t Tt减少的叶结点数, α α α则表示剪枝后树的复杂度降低程度与代价间的关系,定义为:
    α = R ( t ) − R ( T t ) ∣ N t ∣ − 1 \alpha = \frac{R(t) - R(T_t)}{|N_t| - 1} α=Nt1R(t)R(Tt)

    其中, ∣ N t ∣ |N_t| Nt是子树 T t T_t Tt中的叶节点数, R ( t ) = r ( t ) ∗ p ( t ) R(t) = r(t) * p(t) R(t)=r(t)p(t)为结点 t t t的错误代价, r ( t ) r(t) r(t)为结点 t t t的错分样本率, p ( t ) p(t) p(t)为落入结点 t t t的样本占所有样本的比例, R ( T t ) = ∑ R ( i ) R(T_t) = \sum R(i) R(Tt)=R(i)是子树 T t T_t Tt错误代价, i i i为子树 T t T_t Tt的叶节点。

    1. 对于完全决策树 T T T的每个非叶结点计算 α α α值,循环剪掉具有最小 α α α值的子树,直到剩下根节点,得到一系列的剪枝树 { T 0 , T ‘ 1 , T 2 , ⋯   , T m } \{ T_0, T_`1, T_2, \cdots, T_m \} {T0,T1,T2,,Tm},其中 T 0 T_0 T0为原有的完全决策树, T m T_m Tm为根结点, T i + 1 T_{i +1} Ti+1为对 T i T_i Ti进行剪枝的结果
    2. 从子树序列中,根据真实的误差估计选择最佳决策树
    REPPEPCCP
    剪枝方式自底向上自顶向下自底向上
    计算复杂度 O ( n ) O(n) O(n) O ( n ) O(n) O(n) O ( n 2 ) O(n^2) O(n2)
    误差估计测试集上误差估计使用连续纠正标准误差

    回归树

    建立回归树的过程大致可以分为两步:

    1. 将预测变量空间( X 1 , X 2 , X 3 , ⋯   , X p X_1, X_2, X_3, \cdots, X_p X1,X2,X3,,Xp)的可能取值构成的集合分割成 J J J个互不重叠的区域 { R 1 , R 2 , R 3 , ⋯   , R J } \{ R_1, R_2, R_3, \cdots, R_J\} {R1,R2,R3,,RJ}
    2. 对落入区域 R j R_j Rj的每个观测值作同样的预测,预测值等于 R j R_j Rj上训练集的各个样本取值的算术平均数。

    比如,在第一步中得到两个区域 R 1 R_1 R1 R 2 R_2 R2 R 1 R_1 R1中训练集的各个样本取值的算术平均数为10, R 2 R_2 R2中训练集的各个样本取值的算术平均数为20。则对给定的观测值 X = x X = x X=x,若 x ∈ R 1 x \in R_1 xR1,给出的预测值为10,若 x ∈ R 2 x \in R_2 xR2,则预测值为20。

    所以,类似于上述决策树分类算法的第(10)步,关键在于如何构建区域划分 { R 1 , R 2 , R 3 , ⋯   , R J } \{ R_1, R_2, R_3, \cdots, R_J\} {R1,R2,R3,,RJ}。事实上,区域的形状是可以为任意形状的,但出于模型简化和增强可解释性的考虑,这里将预测变量空间划分成高维矩形,我们称这些区域为称盒子。划分区域的目标是找到使模型的残差平方和 R S S RSS RSS最小的矩形区域 { R 1 , R 2 , R 3 , ⋯   , R J } \{ R_1, R_2, R_3, \cdots, R_J\} {R1,R2,R3,,RJ} R S S RSS RSS的定义为:
    R S S = ∑ j = 1 J ∑ i ∈ R j ( y i − y ^ R j ) 2 RSS = \sum^J_{j=1} \sum_{i \in R_j}(y_i - \hat{y}_{R_j})^2 RSS=j=1JiRj(yiy^Rj)2

    其中, y ^ R j \hat{y}_{R_j} y^Rj是第 j j j个矩形区域中训练集中各个样本取值的算术平均数。但是,要想考虑将特征空间划分为 J J J个矩形区域的所有可能性,在计算上是不可行的。因此一般采用一种自上而下的贪婪法:递归二又分裂。“自上而下”指的是它从树顶端开始依次分裂预测变量空间,每个分裂点都产生两个新的分支。“贪婪”意指在建立树的每一步中,最优分裂确定仅限于某一步进程,而不是针对全局去选择那些能够在未来进程中构建出更好的树的分裂点。

    在执行递归二又分裂时,先选择预测变量 X j X_j Xj和分割点 s s s,将预测变量空间分为两个区域 { X ∣ X j < s } \{ X|X_j <s \} {XXj<s} { X ∣ X j ≥ s } \{ X|X_j \geq s \} {XXjs},使 R S S RSS RSS尽可能地减小。也就是说,考虑所有预测变量 X 1 , X 2 , X 3 , ⋯   , X p X_1, X_2, X_3, \cdots, X_p X1,X2,X3,,Xp和与每个预测变量对应的 s s s的取值,然后选择预测变量和分割点,使构造出的树具有最小的 R S S RSS RSS。更详细地,对 j j j s s s,定义一对半平面:
    R 1 ( j , s ) = { X ∣ X j < s } 和 R 2 ( j , s ) = { X ∣ X j ≥ s } R_1(j, s) = \{ X|X_j <s \} \quad \text{和} \quad R_2(j, s) = \{ X|X_j \geq s \} R1(j,s)={XXj<s}R2(j,s)={XXjs}

    寻找 j j j s s s,使得下式最小:
    ∑ x i ∈ R 1 ( j , s ) ( y i − y ^ R 1 ) 2 + ∑ x i ∈ R 2 ( j , s ) ( y i − y ^ R 2 ) 2 \sum_{x_i \in R_1(j, s)}(y_i - \hat{y}_{R_1})^2 + \sum_{x_i \in R_2(j, s)}(y_i - \hat{y}_{R_2})^2 xiR1(j,s)(yiy^R1)2+xiR2(j,s)(yiy^R2)2

    重复上述步骤,寻找继续分割数据集的最优预测变量和最优分割点,使随之产生的区域中的 R S S RSS RSS达到最小。此时被分割的不再是整个预测变量空间,而是之前确定的两个区域之一。如此一来就能得到3个区域。接着进一步分割3个区域之一以最小化 R S S RSS RSS。这一过程不断持续,直到符合某个停止准则,如我们在分类决策树中讨论到的前剪枝中的停止准则。

    区域 { R 1 , R 2 , R 3 , ⋯   , R J } \{ R_1, R_2, R_3, \cdots, R_J\} {R1,R2,R3,,RJ}产生后,就可以确定某一给定的测试数据所属的区域,并用这一区域训练集的各个样本取值的算术平均数作为与测试进行预测。

    f回归树实例

    回归树的剪枝

    上述方法生成的回归树会在训练集中取得良好的预测效果,却很有可能造成数据的过拟合,导致在测试集上效果不佳。原因在于这种方法产生的树可能过于复杂。一棵分裂点更少、规模更小(区域 { R 1 , R 2 , R 3 , ⋯   , R J } \{ R_1, R_2, R_3, \cdots, R_J\} {R1,R2,R3,,RJ}的个数更少)的树会有更小的方差和更好的可解释性(以增加微小偏差为代价)。针对上述问题,一种可能的解决办法是:仅当分裂使残差平方和 R S S RSS RSS的减小量超过某阈值时,才分裂树结点。这种策略能生成较小的树,但可能产生过于短视的问题,一些起初看来不值得的分裂却可能之后产生非常好的分裂。也就是说在下一步中, R S S RSS RSS会大幅减小。

    因此,更好的策略是生成一棵很大的树 T 0 T_0 T0,然后通过后剪枝得到子树。直观上看,剪枝的目的是选出使测试集预测误差最小的子树。子树的测试误差可以通过交叉验证或验证集来估计。但由于可能的子树数量极其庞大,对每一棵子树都用交叉验证来估计误差太过复杂。因此需要从所有可能的子树中选出一小部分再进行考虑。在回归树中,我们一般使用代价复杂度剪枝(CCP,Cost-Complexity Pruning),也称最弱联系剪枝(Weakest Link Pruning)。这种方法不是考虑每一棵可能的子树,而是考虑以非负调整参数 α \alpha α标记的一系列子树。每一个 α \alpha α的取值对应一棵子树 T ∈ T 0 T \in T_0 TT0,当 α \alpha α一定时,其对应的子树使下式最小:
    ∑ m = 1 ∣ T ∣ ∑ x i ∈ R m ( y i − y ^ R m ) 2 + α ∣ T ∣ \sum_{m=1}^{|T|} \sum_{x_i \in R_m}(y_i - \hat{y}_{R_m})^2 + \alpha |T| m=1TxiRm(yiy^Rm)2+αT

    这里的 ∣ T ∣ |T| T表示树 T T T的结点数, R m R_m Rm是第 m m m个终端结点对应的矩形(预测向量空间的一个子集), y ^ R m \hat{y}_{R_m} y^Rm是与 R m R_m Rm对应的预测值,也就是 R m R_m Rm中训练集的平均值。调整系数 α \alpha α在子树的复杂性和与训练数据的契合度之间控制权衡。当 α = 0 \alpha = 0 α=0时,子树 T T T等于原树 T 0 T_0 T0,因为此时上式只衡量了训练误差。而当 α \alpha α增大时,终端结点数多的树将为它的复杂付出代价,所以使上式取到最小值的子树会变得更小。

    α \alpha α从0开始逐渐增加时,树枝以一种嵌套的、可预测的模式被修剪,因此获得与 α \alpha α对应的所有子树序列是很容易的。可以用交又验证或验证集确定 α \alpha α,然后在整个数据集中找到与之对应的子树:

    回归决策树算法
    1.利用递归二叉分裂在训练集中生成一额大树,只有当终端结点包含的观测值个数低于某个最小值时才停止。
    2.对大树进行代价复杂性剪枝,得到一系列最优子树,子树是 α \alpha α的函数。
    3.利用 K K K折交叉验诞选择 α \alpha α。具体做法是将训练集分为 K K K折。对所有 k = 1 , 2 , 3 , ⋯   , K k=1, 2, 3, \cdots, K k=1,2,3,,K,对训练集上所有不属于第 k k k折的数据重复第(1)步~第(2)步得到与 α \alpha α对应的子树,并求出上述子树在第 k k k折上的均方预测误差。
    4.每个 α \alpha α会有相应的 K K K个均方预测误差,对这 K K K个值求平均,选出使平均误差最小的 α \alpha α
    5.找出选定的 α \alpha α在第(2)步中对应的子树。

    决策树的基础即是上文所述的分类决策树与回归决策树,其预测准确性一般比回归和分类方法弱,但可以通过用集成学习方法组合大量决策树,显著提升树的预测效果,这些方法我将会在接下来的文章中继续阐述,欢迎关注学习讨论!

    展开全文
  • 决策树分类(decision tree classification)python实现

    万次阅读 多人点赞 2018-04-22 16:48:47
    决策树分类很符合人类分类时的思想,决策树分类时会提出很多不同的问题,判断样本的某个特征,然后综合所有的判断结果给出样本的类别。例如下图的流程即为一个典型的决策树分类的流程图,这个流程图用来简略的判断一...
  • 纯手些代码,python,线性分类决策树 MS泰坦尼克号的沉没是历史上最臭名昭着的沉船之一。 1912年4月15日,在首航期间,泰坦尼克号撞上一座冰山后沉没,2224名乘客机组人员中有1502人遇难。 这一耸人听闻的...
  • 决策树预测 在虹膜数据集上使用决策树分类器进行预测
  • 滑坡灾害预测受多种因素影响,其中降雨等不确定因素存在难以获取数据及有效处理等难题,为提高滑坡危险性预测的准确率,根据滑坡灾害发生相关理论及决策树分类原理,提出了基于不确定决策树算法在滑坡危险性预测的...
  • 决策树分类

    千次阅读 2017-02-08 10:06:49
    分类方法用于预测数据对象的离散类别;而预测则用于预测数据对象的连续取值;
  • GBDT决策树集成学习残差预测和分类

    千次阅读 2017-04-10 11:06:36
     关于决策树decision tree的组合模型有两种:random forest GBDT (gradient boosting decision tree)。上一篇我们说了《理解随机森林》,这次我们来说下以下GBDT的理论模型,后面还有连续的两片分别将GBDT之...
  • 美国收入预测Adult数据集决策树分类

    千次阅读 2020-04-16 14:15:07
    在这里插入代码片 """ 该脚本创建分类树实现美国收入的预测 ...从决策树到随机森林https://zhuanlan.zhihu.com/p/28217071 """ import pandas as pd import numpy as np # from plotnine import * import matplot...
  • 决策树分类数据挖掘

    千次阅读 2019-01-13 20:41:26
    ※写在前面的思考: ...决策树分类方法采用自顶向下的递归形式(实质就是分而治之),在决策树的内部节点进行属性值的比较并根据不同的属性值判断从该结点向下的分支,在决策树的叶节点得到结论。所以...
  • 根据温度、盐度、PH值溶解氧的含量,建立C4.5决策树预测模型,实现对水质进行评价
  • Python实现决策树分类回归

    千次阅读 2019-04-25 22:06:26
    有用请点赞,没用请差评。 欢迎分享本文,转载请保留出处。 在上一篇博客的基础上增加了使用决策树进行预测的功能(Decision_tree类有稍微改变)。 预测函数其实可以使用递归来实现,但是... 使用决策树分类 ...
  • 使用Java实现的ID3决策树,内含数据文件及ID3类的源代码。实现了决策树分类,结果存储为XML文件,以及基于模型进行的分类预测
  • 决策树分类

    万次阅读 2017-08-25 11:44:38
    决策树分类器的基本流程我们通过学习并构造分类器 。这里给出一个相当经典且流行的分类器——决策树分类器。 为什么这样评价这个分类器呢?因为构造这个分类器不需要任何领域的知识,也不需要任何的参数设置。因此...
  • 决策树分类算法

    千次阅读 2016-10-26 15:56:22
    最近在学习数据挖掘,算法的重要性可想而知,先学习下理论,本篇是关于决策树算法,参考了一些博客,觉得写的非常不错。后面会结合代码来实现这些算法,并尝试着使用mahout等框架来使用这些算法解决实际的问题
  • 在机器学习中,决策树是一个预测模型,他代表的是对象属性与对象值之间的一种映射关系。Entropy = 系统的凌乱程度,使用算法ID3, C4.5C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。 决策树是一种树...
  • 基于大数据的理念数据挖掘技术,通过对2003-2013年小麦蚜虫发生程度与瓢虫、寄生蜂、日最高气压、日照时数等18种变量关系的决策树分析,构建了分类模型。经分析发现,日照时数与小麦蚜虫的发生程度关联度最高,...
  • 决策树预测算法 创建决策树分类器并以图形方式对其进行可视化。 ●目的是,如果我们向该分类器提供任何新数据,它将能够相应地预测正确的分类。
  • Python 决策树预测 分类算法

    千次阅读 2017-09-26 14:59:38
    安装pandaspip3 install pandas数据加载清洗import os import numpy as np import pandas as pd home_folder = os.path.expanduser("~")#os.path.expanduser(path) 把path中包含的"~""~user"转换成用户目录 data...
  • class sklearn.tree.DecisionTreeClassifier... 参考: DecisionTreeClassifier官方文档 scikit-learn中决策树分类DecisionTreeClassifier参数 决策树调参说明 如果觉得内容不错,请扫码关注微信公众号,获取更多内容
  • R语言 决策树--预测模型

    千次阅读 2017-02-19 17:15:49
    决策树,算法的目标是建立分类预测模型或回归预测模型,是一种预测模型,按目标不同可以细分为分类树回归树,因为在展示的时候,类似于一棵倒置的树而得名。如下图: 基本概念: 根节点:如上图中最上方,一棵...
  • 决策树分类常见问题及评价指标

    千次阅读 2020-01-17 13:33:27
    决策树分类常见问题及评价指标 1. 数据属性问题 常见离散属性: 二元属性,标称属性,适合决策树分类算法。 数值型等连续型属性: 如年龄,身高,血压,在进行分类时采用连续属性离散化,即分段分区间的形式,才能...
  • matlab开发-交叉验证局部分析显示的决策树和预测模型。此代码实现分类树,并为每个目标类绘制ROC曲线。
  • 决策树分类——matlab程序

    千次阅读 2018-03-28 17:00:50
    %% 使用ID3决策树算法预测销量高低 clc; clear ; %% 数据预处理 disp('正在进行数据预处理...'); [matrix,attributes_label,attributes] = id3_preprocess(); %% 构造ID3决策树,其中id3()为自定义函数 disp('数据...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 55,264
精华内容 22,105
关键字:

决策树分类和预测