AI 版 (精华区)

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

发信人: sugy (不再灌水), 信区: AI
标  题: 决策树(一)
发信站: 饮水思源站 (Tue Jul 10 15:26:21 2001), 转信
决策树

决策树方法的起源是概念学习系统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）和 Relief。不同的度量有不同的效果，特别是对于多值属性。

--
**************************************************************************
归去来兮！田园将芜胡不归？既自以心为形役，奚惆怅而独悲？悟已往之不谏，知来
者之可追；实迷途其未远，觉今是而昨非。
归去来兮，请息交以绝游。世与我而相遗，复驾言兮焉求？悦亲戚之情话，乐琴书以
消忧。农人告余以春兮，将有事乎西畴。或命巾车，或槕孤舟。既窈窕以寻壑，亦崎
岖而经丘。木欣欣以向荣，泉涓涓而始流。羡万物之得时，感吾生之行休。
※ 来源:·饮水思源站 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]