CART 树形模型技术概要

 

Dr. Alex YC Liu*, Dr. Dan Steinberg*

 

Tree Book

简介

CART是一个优秀的数据探测和数据分析工具. 可用来自动探测出高度复杂数据的潜在结构,重要模式和关系. 这种探测出的知识又可用来构造精确和可靠的预测模型,应用於分类客户,准确直邮,侦测通信卡及信用卡诈骗和管理信用风险.

 

CART运用直观的视窗阶面, 即方便技术人员也方便非技术人员的使用。然而在 容易的视窗阶面之下,却有着成熟的理论基础,使CART大大超越於其它的决策树方法和工具.

 

技术上讲,CART技术可称为二元回归分化技术. 因为树点总是被分为二树点并不断分化,故称为二元回归。CART分析的技术要点包括一系列规则可用於:

 

1. 分化树点

2. 确定何时完结分化

3. 为每一终结树指定类型或预测值

 

 

分化规则

 

将一个树点分化成二个子树点,CART总是问些的问题。例如,问是否信用点小於或等於600来分化母树点成二个子树点,以为回答的个例归入左树点,而为回答的个例归为右子树点。

 

 

100个回答者

100个拒答者

 

是否信用点小於或等於600

 

 

 

 

 

                            

 

80个回答者

 

20个回答者

30个拒答者

 

70个拒答者

 

 

我们如何选择分化规则呢?CART的方法是先检验分析中所有变量可生出的所有分化,再选其优者。例如,对一个有215种个例和19个变量的数据库,CART要比较215194085种可能的分化。任何的研究问题都有其有限数量分化的可能,因此,CART可以作强力搜寻而检测所有之可能组合。

 

选择一个分化

 

CART的下一阶段是根据分化质量标准来评估每一个分化。最常用的一个标准是GINI标准,基本原则是根据该分化是否有效地分隔几个类别。除GINI外,还存在5种标准常用于分类树型,另有两种用于回归树型的分化。此外,为了更有效处理数据类型的选择,CART也运用连续自变变量的线性组合来作为分化的基础。

 

 

种类确定

 

一经最佳的分化确定之后,CART对每一个子树点重复进行搜索和分化的过程,直到进一步的分化不可能继续。如果某个树点包含完全一致的个案,则无法进一步分化。当然,CART也会在其它一些情况下,比如树点包含太少个案时,而停止分化。(一般取10为标准,少于10即为太少)

 

一旦终结树点找到后,我们必须决定如何对此终结树点中的个案进行分类。最简单的分类原则是多数原则,即用数值最多的种类来确定分类(比如,前页的例子中,左树点为回答者,右树点为据答者) CART扩展了上述方法。对于每一个树点,不管是否终结点,CART都作分类。然后,再根据分类误差来调整分类原则。

 

第一代树型技术的共同特征是不断分化树点直到某种分化标准无法满足了。换而言之,当特定分化的质量低于某指定值后,该枝的分化即停止。所有枝节的分化都停止后,树形模型即成。这个技术还应用许多软件中,例如,CHAIDKNOWLEDGE SEEKER,但是它存在许多错误。CART使用完全不同的技术。

 

 

剪修树形

 

不同于试图去确定某一树点是否终结树点,CART继续所有的分化直到分化已不可能。CART一但分化出一个最大可能的树后,CART修剪去大树的一些树枝以检测不同的小树。与众不同的是,CART并未中间停止,以防漏掉中间的资讯。

 

 

测试

 

一点获得大树并得到一些小树后,CART通过比较误差和代价来确认最佳的树形模型。如有足够大的数据库,最简单的方法是将之分为学习数据和测试数据。CART用学习数据来分化树点而获得大树和小树,再用测试数据来估算误差,并用误差代价调整计算。CART可估算出大树和所有小树的误差。具有最小误差的小树就是所需要的最佳树形模型。许多研究项目可能没有足够的数据作以上述划分。分树方法需要大型数据,常比传统回归要更多个案。当数据缺少时,CART运用电脑运算密集的跨越检证法。

 

跨越检证法

 

当数据较小时,CART运用跨越检证法。这种情况下,CART用整个学习数据分化一个最大树,这是需要被修剪的树。CART然后将此学习数据分成10个大致同样大小的子数据,每个子数据都含有因变量的类似分布。CART运用头9个子数据来分化最大树,再运用第10个子数据来构造子树形的误差估计。针对9个子数据作为整体重复同样的过程10次。再把10个小型的测试数据组合起来,以此用于估算不同大小树形的误差。上述复杂过程构造出树形独立预测精确度的可靠估算。这意味,尽管没有独立的测试数据库,而我们却可以知道任何树形对任何新数据的行为。因此这一评估树形准确度的方式十分看好,CART一般运用此跨越检证法来获取小型数据库的客观计算。

 

CART 的特点

 

  1. 非参数
  2. 不需事先选好变量
  3. 定向转换自变量不影响结果
  4. 可运用于复杂数据
  5. 处理特别数点较好
  6. 可用于连续变量和类别变量的任何组合
  7. 可用变量的线性组合来分割树点
  8. 可以调整样本
  9. 可以提出变量的相互作用
  10. 可以较好处理MISSING VALUES

 

 

结论

 

CART运用完整的搜寻和电脑计算密集的测试技巧来揭示数据中的模型和关系。它可运用于任何的数据,而不需要使用者提供任何指导。如此,当你有一个数据库而不知从何开始分析时,请不妨把这一数据库交给CART。如果你听起来太不现实,也许会问:CART真能给出值得你信任的有用结果吗?回答是肯定的。当用CART的自动分析与逐步的LOGIT回归和DISCRIMINANT类别分析比较时,CART通常可在学习数据库上得到10%-15%更好的结果。

按此,可了解 SALFORD SYSTEM 工具。

 

[] 作者Dr. Alex Liu是斯坦福大学博士,Dr. Dan Steinberg 是哈佛大学博士,都是知名统计分析专家。