决策树算法之一 分类回归树(C&RT)

shiyiming

From SAS_Miner's blog on Sina

<p><span LANG="EN-US" STYLE="FonT-siZe: 10.5pt; FonT-FAMiLY: 'Times new roman'; mso-font-kerning: 1.0pt; mso-ansi-language: en-Us; mso-fareast-language: ZH; mso-bidi-language: Ar-sA; mso-fareast-font-family: 宋体" XML:LANG="EN-US" TWFFAN="done"><span LANG="EN-US" STYLE="FonT-siZe: 10.5pt; FonT-FAMiLY: 'Times new roman'; mso-font-kerning: 1.0pt; mso-ansi-language: en-Us; mso-fareast-language: ZH-Cn; mso-bidi-language: Ar-sA; mso-fareast-font-family: 宋体" XML:LANG="EN-US" TWFFAN="done"><font COLOR="#0000FF">分类回归树&nbsp; classification and regression
tree(C&amp;RT)</FONT></SPAN></SPAN><font COLOR="#0000FF">&nbsp; racoon</FONT></P>
<p><span LANG="EN-US" STYLE="FonT-siZe: 10.5pt; FonT-FAMiLY: 'Times new roman'; mso-font-kerning: 1.0pt; mso-ansi-language: en-Us; mso-fareast-language: ZH; mso-bidi-language: Ar-sA; mso-fareast-font-family: 宋体" XML:LANG="EN-US" TWFFAN="done"><font COLOR="#0000FF">优点<br />
（1）可自动忽略对目标变量没有贡献的属性变量，也为判断属性变量的重要性，减少变量数据提供参考；<br />
（2）在面对诸如存在缺失值、变量数多等问题时C&amp;RT 显得非常稳健（robust）；<br />
（3）估计模型通常不用花费很长的训练时间；<br />
&nbsp; (4) 推理过程完全依据属性变量的取值特点（与
C5.0不同，C&amp;RT的输出字段既可以是数值型，也可以是分类型）<br />
（5）比其他模型更易于理解——从模型中得到的规则能得到非常直观的解释，决策推理过程可以表示成&nbsp;&nbsp;
IF…THEN的形式<br />
（6）目标是定类变量为分类树，若目标变量是定距变量，则为回归树；<br />
（7）通过检测输入字段，通过度量各个划分产生的异质性的减小程度，找到最佳的一个划分。<br />
（8）非常灵活，可以允许有部分错分成本，还可指定先验概率分布，可使用自动的成本复杂性剪枝来得到归纳性更强的树。</FONT></SPAN></P>
<p><span LANG="EN-US" STYLE="FonT-siZe: 10.5pt; FonT-FAMiLY: 'Times new roman'; mso-font-kerning: 1.0pt; mso-ansi-language: en-Us; mso-fareast-language: ZH; mso-bidi-language: Ar-sA; mso-fareast-font-family: 宋体" XML:LANG="EN-US" TWFFAN="done"><font COLOR="#0000FF">决策树生长的核心是确定决策树的分枝准则。<br />
一、&nbsp;如何从众多的属性变量中选择一个当前的最佳分支变量；<br />
也就是选择能使异质性下降最快的变量。<br />
异质性的度量：GINI、TWOING、least squared deviation。<br />
前两种主要针对分类型变量，LSD针对连续性变量。</FONT></SPAN></P>
<p><span LANG="EN-US" STYLE="FonT-siZe: 10.5pt; FonT-FAMiLY: 'Times new roman'; mso-font-kerning: 1.0pt; mso-ansi-language: en-Us; mso-fareast-language: ZH; mso-bidi-language: Ar-sA; mso-fareast-font-family: 宋体" XML:LANG="EN-US" TWFFAN="done"><font COLOR="#0000FF">代理划分、加权划分、先验概率</FONT></SPAN></P>
<p><span LANG="EN-US" STYLE="FonT-siZe: 10.5pt; FonT-FAMiLY: 'Times new roman'; mso-font-kerning: 1.0pt; mso-ansi-language: en-Us; mso-fareast-language: ZH; mso-bidi-language: Ar-sA; mso-fareast-font-family: 宋体" XML:LANG="EN-US" TWFFAN="done"><font COLOR="#0000FF">二、&nbsp;如何从分支变量的众多取值中找到一个当前的最佳分割点（分割阈值）。<br />

(1)&nbsp;分割阈值：<br />
A、数值型变量——对记录的值从小到大排序，计算每个值作为临界点产生的子节点的异质性统计量。能够使异质性减小程度最大的临界值便是最佳的划分点。<br />

B、分类型变量——列出划分为两个子集的所有可能组合，计算每种组合下生成子节点的异质性。同样，找到使异质性减小程度最大的组合作为最佳划分点。<br />

&nbsp;&nbsp;<br />
三、&nbsp;决策树停止生长的条件<br />
满足以下一个即停止生长。<br />
（1）&nbsp;节点达到完全纯性；<br />
（2）&nbsp;数树的深度达到用户指定的深度；<br />
（3）&nbsp;节点中样本的个数少于用户指定的个数；<br />
（4）&nbsp;异质性指标下降的最大幅度小于用户指定的幅度。</FONT></SPAN></P>
<p><span LANG="EN-US" STYLE="FonT-siZe: 10.5pt; FonT-FAMiLY: 'Times new roman'; mso-font-kerning: 1.0pt; mso-ansi-language: en-Us; mso-fareast-language: ZH; mso-bidi-language: Ar-sA; mso-fareast-font-family: 宋体" XML:LANG="EN-US" TWFFAN="done"><font COLOR="#0000FF">剪枝：完整的决策树对训练样本特征的描述可能“过于精确”（受噪声数据的影响），缺少了一般代表性而无法较好的用对新数据做分类预测，出现
”过度拟合“。<br />
——移去对树的精度影响不大的划分。使用 成本复杂度方法，即同时度量错分风险和树的复杂程度，使二者越小越好。<br />
剪枝方式：<br />
A、&nbsp;预修剪（prepruning）：停止生长策略<br />
B、后修剪（postpruning）：在允许决策树得到最充分生长的基础上，再根据一定的规则，自下而上逐层进行剪枝。<br />
预测：<br />
回归树——预测值为叶节点目标变量的加权均值<br />
分类树——某叶节点预测的分类值应是造成错判损失最小的分类值。</FONT></SPAN></P>
<p><span LANG="EN-US" STYLE="FonT-siZe: 10.5pt; FonT-FAMiLY: 'Times new roman'; mso-font-kerning: 1.0pt; mso-ansi-language: en-Us; mso-fareast-language: ZH; mso-bidi-language: Ar-sA; mso-fareast-font-family: 宋体" XML:LANG="EN-US" TWFFAN="done"><font COLOR="#0000FF">四、&nbsp;模型评价：<br />
减少在冒险因素或损失因素方面的不确定性。<br />
不仅包括不同模型的比较，而且还要对模型产生结果的商业价值进行比较。<br />
模型评价的角度<br />
-风险（risk）<br />
-收益（gain）<br />
-利润（profits）</FONT></SPAN></P>
<p>&nbsp;</P>
<p>&nbsp;</P>
<p><span LANG="EN-US" STYLE="FonT-siZe: 10.5pt; FonT-FAMiLY: 'Times new roman'; mso-font-kerning: 1.0pt; mso-ansi-language: en-Us; mso-fareast-language: ZH; mso-bidi-language: Ar-sA; mso-fareast-font-family: 宋体" XML:LANG="EN-US" TWFFAN="done"><font COLOR="#0000FF">clementine&nbsp; 流程图 ：</FONT></SPAN></P>
<p>&nbsp;</P>
<p><span LANG="EN-US" STYLE="FonT-siZe: 10.5pt; FonT-FAMiLY: 'Times new roman'; mso-font-kerning: 1.0pt; mso-ansi-language: en-Us; mso-fareast-language: ZH; mso-bidi-language: Ar-sA; mso-fareast-font-family: 宋体" XML:LANG="EN-US" TWFFAN="done"><a HREF="http://blog.photo.sina.com.cn/showpic.html#url=http://static10.photo.sina.com.cn/orignal/4b62a627h7671dfffed99&amp;690" TARGET="_blank"><img SRC="http://static10.photo.sina.com.cn/bmiddle/4b62a627h7671dfffed99&amp;690" TWFFAN="done" /></A><a HREF="http://blog.photo.sina.com.cn/showpic.html#url=http://static4.photo.sina.com.cn/orignal/4b62a627h7671dd484893&amp;690" TARGET="_blank"></A></SPAN></P><div style="border-top: 1px solid rgb(203, 217, 217); padding-top: 20px; padding-bottom: 10px;">
<p><br><a href="http://move.blog.sina.com.cn/admin/blogmove/blogmove_msn.php" target="_blank">MSN空间完美搬家到新浪博客!</a></p></div>