Algorithm 版 (精华区)

发信人: ssos (存在与虚无), 信区: Algorithm
标  题: 数据挖掘采用技术（一）：决策树
发信站: 哈工大紫丁香 (2001年06月14日16:05:22 星期四), 站内信件

决策树方法的起源是概念学习系统CLS，然后发展到ID3方法而为高潮，最后又演化为能
处理连续属性的C4.5。有名的决策树方法还有CART和Assistant。
决策树构造的输入是一组带有类别标记的例子，构造的结果是一棵二叉或多叉树。二叉
树的内部节点（非叶子节点）一般表示为一个逻辑判断，如形式为(ai = vi )的逻辑判
断，其中ai 是属性，vi是该属性的某个属性值；树的边是逻辑判断的分支结果。多叉树
（ID3）的内部节点是属性，边是该属性的所有取值，有几个属性值，就有几条边。树的
叶子节点都是类别标记。
构造决策树的方法是采用自上而下的递归构造。以多叉树为例，它的构造思路是，如果
训练例子集合中的所有例子是同类的，则将之作为叶子节点，节点内容即是该类别标记
。否则，根据某种策略选择一个属性，按照属性的各个取值，把例子集合划分为若干子
集合，使得每个子集上的所有例子在该属性上具有同样的属性值。然后再依次递归处理
各个子集。这种思路实际上就是“分而治之”（divide-and-conquer）的道理。二叉树
同理，差别仅在于要选择一个好的逻辑判断。
属性选择
构造好的决策树的关键在于如何选择好的逻辑判断或属性。对于同样一组例子，可以有
很多决策树能符合这组例子。人们研究出，一般情况下或具有较大概率地说，树越小则
树的预测能力越强。要构造尽可能小的决策树，关键在于选择恰当的逻辑判断或属性。
由于构造最小的树是NP-难问题，因此只能采取用启发式策略选择好的逻辑判断或属性。
属性选择依赖于各种对例子子集的不纯度（impurity）度量方法。不纯度度量方法包括
信息增益（informatin gain）、信息增益比（gain ratio）、Gini-index、距离度量（
distance measure）、J-measure、G统计、χ2统计、证据权重（weight of evidence）
、最小描述长（MLP）、正交法（ortogonality measure）、相关度（relevance）和 R
elief。不同的度量有不同的效果，特别是对于多值属性。
噪声与剪枝
真实世界的数据（数据开采的对象显然就是真实世界数据）一般不可能是完美的，①可
能某些属性字段上缺值（missing values）；②可能缺少必须的数据而造成数据不完整
；③可能数据不准确含有噪声甚至是错误的。我们在此主要讨论噪声问题。
基本的决策树构造算法没有考虑噪声，生成的决策树完全与训练例子拟合。有噪声情况
下，完全拟合将导致过分拟合（overfitting），即对训练数据的完全拟合反而不具有很
好的预测性能。剪枝是一种克服噪声的技术，同时它也能使树得到简化而变得更容易理
解。有两种剪枝策略：向前剪枝（forward pruning）和向后剪枝（backward pruning）
。向前剪枝方法是，在生成树的同时决定是继续对不纯的训练子集进行划分还是停机。
向后剪枝方法是一种两阶段法：拟合－化简（fitting-and-simplifying），首先生成与
训练数据完全拟合的一棵决策树，然后从树的叶子开始剪枝，逐步向根的方向剪。剪枝
时要用到一个测试数据集合（tuning set或adjusting set），如果存在某个叶子剪去后
能使得在测试集上的准确度或其它测度不降低（不变得更坏），则剪去该叶子；否则停
机。理论上讲，向后剪枝好于向前剪枝，但计算复杂度大。剪枝过程中一般要涉及一些
统计参数或阈值，如停机阈值；有人提出了一种和统计参数无关的基于最小描述长（MD
L）的有效剪枝法。
值得注意的是，剪枝并不是对所有的数据集都好，就象最小树并不是最好（具有最大的
预测率）的树。当数据稀疏时，要防止过分剪枝（over-pruning）。从某种意义上讲，
剪枝也是一种偏向（bias），对有些数据效果好而有的数据则效果差。
子树复制和碎片问题
由于属性间存在相关性和多项性（一个结果可由多个条件决定）。例如，如布尔函数f
= x1x2+x3x4中属性x1和x2，或属性x3和x4间不是相互独立的、而是存在相关性；另外，
该布尔函数有多个乘积项 x1x2和x3x4。出现这种情况时，生成的决策树会有子树复制问
题（replication problem）。复制现象导致决策树不易理解，同时还导致碎片问题：当
树很大时，会造成数据集的划分越来越小，从而预测越差。
解决子树复制和碎片问题的方法主要是采取特征构造。特征构造一般计算复杂度高，为
了降低特征构造的代价，先是选取重要特征（或去除不相关特征）形成初始相关特征集
，再在该初始特征集的基础上构造新的复杂特征（初始相关特征的各种组合）。
另外，最近研究人员又提出了一种新的表示方法－决策图（decision graph）。决策图
中没有冗余结点，具有可读性，既解决了复制问题，同时还能解决碎片问题。
--

   
<<社会契约论>>是一本好书,应当多读几遍
风味的肘子味道不错,我还想再吃它      

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