AI 版 (精华区)

发信人: yale (AI*PP*心如止水), 信区: AI
标  题: 决策树（2）
发信站: 哈工大紫丁香 (2003年12月19日16:10:46 星期五), 站内信件

发信人: sugy (不再灌水), 信区: AI
标  题: 决策树(二)
发信站: 饮水思源站 (Tue Jul 10 15:26:40 2001), 转信
噪声与剪枝
真实世界的数据（数据开采的对象显然就是真实世界数据）一般不可能是完美的，
①可能某些属性
字段上缺值（missing values）；②可能缺少必须的数据而造成数据不完整；③可
能数据不准确含 有噪声甚至是错误的。我们在此主要讨论噪声问题。
基本的决策树构造算法没有考虑噪声，生成的决策树完全与训练例子拟合。有噪声
情况下，完全拟合将导致过分拟合（overfitting），即对训练数据的完全拟合反而不具
有很好的
预测性能。剪枝是一种克服噪声的技术，同时它也能使树得到简化而变得更容易理解。
有两种剪枝策
略：向前剪枝（ forward pruning）和向后剪枝（backward pruning）。向前剪枝方法
是，在生成
树的同时决定是继续对不纯的训练子集进行划分还是停机。向后剪枝方法是一种两阶段
法：拟合－化
简（fitting-and-simplifying），首先生成与训练数据完全拟合的一棵决策树，然后从
树的叶子开
始剪枝，逐步向根的方向剪。剪枝时要用到一个测试数据集合（tuning set或adjustin
g set），如
果存在某个叶子剪去 后能使得在测试集上的准确度或其它测度不降低（不变得更坏），
则剪去该叶子；
否则停机。理论上讲，向后剪枝好于向前剪枝，但计算复杂度大。剪枝过程中一般要涉
及一些统计
参数或阈值，如停机阈值；有人提出了一种和统计参数无关的基于最小描述长（MDL）的
有效剪枝
法。
值得注意的是，剪枝并不是对所有的数据集都好，就象最小树并不是最好（具有最
大的预测率）的树。当数据稀疏时，要防止过分剪枝（over-pruning）。从某种意义上
讲，剪枝也
是一种偏向（bias），对有些数据效果好而有的数据则效果差。
子树复制和碎片问题
由于属性间存在相关性和多项性（一个结果可由多个条件决定）。例如，如布尔函
数f = x1x2+x3x4中属性x1和x2，或属性x3和x4间不是相互独立的、而是存在相关性；另

外，该布尔函数有多个乘积项 x1x2和x3x4。出现这种情况时，生成的决策树会有子树复
制问题（
replication problem）。复制现象导致决策树不易理解，同时还导致碎片问题：当树很
大时，
会造成数据集的 划分越来越小，从而预测越差。
解决子树复制和碎片问题的方法主要是采取特征构造。特征构造一般计算复杂度高
，为了降低特征构造的代价，先是选取重要特征（或去除不相关特征）形成初始相关特
征集，再在
该初始特征集的基础上构造新的复杂特征（初始相关特征的各种组合）。
另外，最近研究人员又提出了一种新的表示方法－决策图（decision graph）。决
策图中没有冗余结点，具有可读性，既解决了复制问题，同时还能解决碎片问题。
--
**************************************************************************
归去来兮！田园将芜胡不归？既自以心为形役，奚惆怅而独悲？悟已往之不谏，知来
者之可追；实迷途其未远，觉今是而昨非。
归去来兮，请息交以绝游。世与我而相遗，复驾言兮焉求？悦亲戚之情话，乐琴书以
消忧。农人告余以春兮，将有事乎西畴。或命巾车，或槕孤舟。既窈窕以寻壑，亦崎
岖而经丘。木欣欣以向荣，泉涓涓而始流。羡万物之得时，感吾生之行休。
※ 来源:·饮水思源站 bbs.sjtu.edu.cn·[FROM: 211.80.39.110]
--
※ 转寄:·饮水思源 bbs.sjtu.edu.cn·[FROM: 202.118.239.104]


--
As we know,there are known knowns.There are things we know we know.
We also know there are known unknowns. That is to say
We know there are somethings we do not know.
But there are also unknown unknowns, the ones we don't know we don't know
               -Rumsfeld

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.239.104]