注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

数据挖掘

学习数据挖掘

 
 
 

日志

 
 

clementine之决策树  

2013-03-29 22:11:24|  分类: Clementine |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
clementine 自带了4种决策树算法:C5.0、CART、QUEST、CHAID算法。其中 CART、QUEST是二分支决策树, C5.0、CHAID 是多分支决策树。 CART、CHAID算法 的目标变量可以是连续的,也可以是离散的。 C5.0、QUEST算法的目标变量只能是离散的。

一   C5.0

与C5.0相似的算法有:ID3(基于信息增益度的分裂方式,只能处理离散变量),C4.5(基于信息增益率的分裂准则,避免了ID3算法中偏向多值变量的问题),C5.0的目标变量只能是离散的。关于算法的细节,可以搜索 很多资料。
执行效率和内存使用改进、适用大数据集

优点:
1)面对数据遗漏和输入字段很多的问题时非常稳健;
2)通常不需要很长的训练次数进行估计;
3)比一些其他类型的模型易于理解,模型推出的规则有非常直观的解释;
4)允许进行多次多于两个子组的分割。

字段约定:目标字段必须为分类字段。


CART算法
CART算法 是基于纯度GINI的分支。clementine中关键的问题是处理空值问题。

分类回归树
优点
(1) 可自动忽略对目标变量没有贡献的属性变量,也为判断属性变量的重要性,减少变量数据提供参考;
(2) 在面对诸如存在缺失值、变量数多等问题时C&RT 显得非常稳健(robust);
(3) 估计模型通常不用花费很长的训练时间;
 ( 4  )   推理过程完全依据属性变量的取值特点(与C5.0不同,C&RT的输出字段既可以是数值型,也可以是分类型)
(5) 比其他模型更易于理解——从模型中得到的规则能得到非常直观的解释,决策推理过程可以表示成IF…THEN的形式
(6) 目标是定类变量为分类树,若目标变量是定距变量,则为回归树;
(7) 通过检测输入字段,通过度量各个划分产生的异质性的减小程度,找到最佳的一个划分。
(8) 非常灵活,可以允许有部分错分成本,还可指定先验概率分布,可使用自动的成本复杂性剪枝来得到归纳性更强的树。

在clem中分类准则有三个,如下图所示:
clementine之决策树 - 小坏 - Do  What
 如果目标变量是类型变量,则可以选择Gini 或者Twoing ;如果目标变量是连续变量则使用 the least-square deviation (LSD)。
GINI的计算公式:
clementine之决策树 - 小坏 - Do  What
 
clementine之决策树 - 小坏 - Do  What
其中t表示节点,i,j表示类别,Pi(i)表示先验概率。,N表示数量。
clementine之决策树 - 小坏 - Do  What
 LSD(the least-square deviation)
clementine之决策树 - 小坏 - Do  What
 Nw(t) 表示节点t 的权重数,wi 表示事务的权重,fi表示事务的斌度,yi 为输出的目标值。
CHAID算法

三、CHAID:
优点:
(1)可产生多分枝的决策树
(2)目标变量可以定距或定类
(3)从统计显著性角度确定分支变量和分割值,进而优化树的分枝过程
(4)建立在因果关系探讨中,依据目标变量实现对输入变量众多水平划分

 

字段约定:输出字段特别适合为分类变量,当为连续变量时会自动分为10段处理(clem软件)

chaid算法p值的计算,关于不同类型的目标变量有不同的计算方式:

如果目标变量是连续的,则计算是基于F分布的:


clementine之决策树 - 小坏 - Do  What
 其中
clementine之决策树 - 小坏 - Do  What
P值的计算如下:
 
clementine之决策树 - 小坏 - Do  What
如果目标变量是类别变量(无序)
 1,Pearson Chi-square test

clementine之决策树 - 小坏 - Do  What
 
clementine之决策树 - 小坏 - Do  What
clementine之决策树 - 小坏 - Do  What
 
clementine之决策树 - 小坏 - Do  What
 
在没有权重的情况下:mij
 
clementine之决策树 - 小坏 - Do  What
 2,Likelihood_ratio chi_square

clementine之决策树 - 小坏 - Do  What
 
clementine之决策树 - 小坏 - Do  What
 
clementine之决策树 - 小坏 - Do  What
 
clementine之决策树 - 小坏 - Do  What
 
clementine之决策树 - 小坏 - Do  What
 如果目标变量为有序变量

clementine之决策树 - 小坏 - Do  What
 
clementine之决策树 - 小坏 - Do  What
 这个后续的计算比较负责,不列了。
P值校正,Bonferroni校正
假设I类合并为r类,其中1<r<I
clementine之决策树 - 小坏 - Do  What
 

CHAID算法迭代过程

合并步:

对于每个解释变量X,合并非显著差异的分类。如果X被选为分裂变量,X的各个最终分类将成为子节点。在分裂步用到的调整P值也是在这一步计算。

1  如果变量X只有一类,停止计算并且设置调整P1

2  如果变量X2类,跳到第8步。

3  如果X大于等于2类,找出X中合适的并且具有最小显著差异的两对类别(顺序型变量中相邻的两类为合适的,对于名义变量,任意两类都合适)。最小显著差异的两类指的是在统计检验中具有最大的P(应用一对分类)。

4  对于具有最大P值的一对分类,检查该P是否大于用户设定的显著水平a1(合并点)。如果大于a1,这一对分类合并为一个合成类。这时候变量X便形成了一个新的分类。如果不大于a1,跳到第7步。

5  (可选)如果新形成的合成类包含了三个以上原始类,则找出合成类中最优的二分类点(P值最小的),假如对应的P不大于用户设定的显著水平a2(合并分裂点),执行该分裂。

6  返回第2步。

7  (可选)任何具有太少观察值(小于用户设定的最小分割大小)的类别将合并到与其最为相似(具有最大的P值)的其他类别中。

8  应用Bonferroni方法计算合并好的分类的调整P值(应用所有分类)。

分裂步:

每个解释变量的最优分裂值已经在合并步中确定,分裂步则要确定哪个解释变量作为分裂节点。通过比较每个解释变量的调整P值可以确定最优分裂变量,调整P值在合并步中已经计算出来。

1  选择具有最小调整P值的解释变量。

2  如果该调整P小于等于用户设定的显著水平a3,则使用该解释变量分裂节点。否则,不分裂并且考虑作为叶子节点。

注:分裂步的P值和合并步的P值不同点在于合并步只需要一对分类计算P值,分裂步需要所有分类计算P值。

穷举型CHAID算法:

合并步使用了穷举搜索过程去合并任何一对相似类,直到只剩下一对。

合并步:

1  如果变量X只有一类,停止计算并且设置调整P1

2  index=0.基于目前X的分类计算P值。称Ppindex=p0)。

3  找出X中符合规则并且具有最小显著差异的两对类别。最小显著差异的两类指的是在统计检验中具有最大的P(应用一对分类)。

4  合并第3步确定的具有最大P值的分类对为一个合成类。(区别点)

5  (可选)如果新形成的合成类包含了三个以上原始类,则找出合成类中最优的二分类点(P值最小的),如果对应的P值比前一步中合并此合成类的P值大,执行该分裂。(Clementine没有这一步)

6  更新index=index+1,基于目前X的分类计算新的P值,并赋予pindex)。

7  重复第3步到第6步直到只剩两大类。在所有的index中,找到使pindex)值最小的分类方式。

8  (可选)任何具有太少观察值(小于用户设定的最小分割大小)的类别将合并到与其最为相似(具有最大的P值)的其他类别中。

9  应用Bonferroni方法计算合并好的分类的调整P值(应用所有分类)。

注:CHAID算法不同点在于,没有用户设定的显著水平a1a2,只需要a3.

 ---------------------------------------------

它的基本算法是一个不断合并和拆分的过程,每一个自变量每个水平都要两两配对比较,如果两个类别相似的话就划归为一类。相似的标准就是和正常的分布比较(即认为两类的响应率是一样的)进行χ2检验,如果比较的结果是没有差别的话,就合并为一组,如果有差别就不能够划分为一组。然而当合并完成后,还要考虑到拆分问题,因为我们只涉及两两比较,而没有考虑到多项比较,可能某些类别经过多元比较之后有差别但却分在同一类。拆分反复进行,直到每一个划分的类别中两两类别之间没有差异。

对等级和连续变量和类别的变量拆分标准是不一样的。对于类别数据拆分是两两比较,对于连续变量和等级变量,需要首先分析数据的分布趋势找到一些变化大的拐点,然后根据这样一些拐点进行拆分,之后只能是相邻的类别被合并,而不是每一个一样的点都被合并。比如,年龄为10岁的和年龄为55岁的人群,如果他们对因变量的预测是一样的,但是因为他们不相邻,所以他们会被划分到不同的类别当中。由于类别变量、等级变量以及连续变量的拆分方法不同,如果我们在研究中不做区分,结果会很不准确。



QUEST算法

优点:运算过程比CR&T更简单有效
QUEST 节点可提供用于构建决策树的二元分类法,此方法的设计目的是减少大型 C&R决策树分析所需的处理时间,同时减小分类树方法中常见的偏
向类别较多预测变量的趋势。预测变量字段可以是数字范围的,但目标字段必须是分类的。所有分割都是二元的。

字段约定:输出(目标)字段必须为二值分类型变量(如果是多值得转化为二值)

对这个算法 不怎么感兴趣


参考资料:1,http://www.cnblogs.com/tippoint/archive/2012/03/02/2376671.html
                  2,http://blog.sina.com.cn/s/blog_6ce00d7b0100v4tz.html
  评论这张
 
阅读(2508)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017