《5决策树学习剖析》由会员分享，可在线阅读，更多相关《5决策树学习剖析（18页珍藏版）》请在金锄头文库上搜索。
1、1,决策树学习,什么是决策树 决策树（Decision Tree）又称为判定树，是运用于分类的一种树结构。其中每个结点代表一个属性，每条边代表属性值。,2,天气类型,温度,假日,没有售完,售完,中,假日,售完,没有售完,没有售完,温度,没有售完,售完,中,没有售完,决策树学习,3,交通条件,1,3,6,8,11,15,17 居住区类型,正 7，12，16，19，20,P,决策树学习,2，4，5，9，10，13，14，18 有无工业区,判断是否应该在特定位置建造新酒吧/饭馆的决策树,4,决策树学习,5,决策树学习,决策树学习算法的基本思想描述如下： step 1任意选取一个属性作为决策树的根结点
2、，然后 就这个属性所有的取值创建树的分支； step 2用这棵树来对训练数据集进行分类，如果一个 叶结点的所有实例都属于同一类，则以该类为 标记标识此叶结点；如果所有的叶结点都有 类标记，则算法终止； step 3否则，选取一个从该结点到根路径中没有出现过 的属性为标记标识该结点，然后就这个属性所有 取值继续创建树的分支；重复算法步骤step 2。,6,决策树学习,这个算法一定可以创建一棵基于训练数据集的正确的决策树，然而，这棵决策树不一定是简单的。显然，不同的属性选取顺序将生成不同的决策树。因此，适当地选取属性将生成一棵简单的决策树。在ID3算法中，采用了一种基于信息的启发式方法来决定如何选
3、取属性。启发式方法选取具有最高信息量的属性，也就是说，生成最少分支决策树的那个属性。,7,决策树学习,ID3算法 ID3即决策树归纳（Induction of Decision Tree）。 ID3算法思想 由训练数据集中全体属性值生成的所有决策树的集合称为搜索空间，该搜索空间是针对某一特定问题而提出的。系统根据某个评价函数决定搜索空间中的哪一个决策树是“最好”的。评价函数一般依据分类的准确度和树的大小来决定决策树的质量。如果两棵决策树都能准确地在测试集进行分类，则选择较简单的那棵。相对而言，决策树越简单，则它对未知数据的预测性能越佳。,8,决策树学习,属性选择度量 ID3算法在树的每个结点上
4、以信息增益作为度量来选择测试属性。这种度量称为属性选择度量的优良性度量。选择具有最高信息增益的属性作为当前结点的测试属性。该属性使得对结果划分中的样本分类所需要的信息量最小，并确保找到一棵简单的（但不一定是最简单的）决策树。,9,决策树学习,信息增益(Information Gain) 指标的原理来自于信息论。1948年，香农（C. E. Shannon）提出了信息论。其中给出了关于信息量（Information）和熵（Entropy）的定义，熵实际上是系统信息量的加权平均，也就是系统的平均信息量。,10,决策树学习,熵（Entropy）： 给定了c个分类，对属性a来说，如果在所有的例子中，它
5、都拥有值v，那么它的熵E就可以定义如下,例中表明，树的根节点具有20个训练例子，在这些例子中，共有两个类别正，负，其中11个例子分类为正，9个例子分类为负。目标分类可以看作拥有两个取值的一个属性，,其中，pi是在第i类中属性a取值为v的概率。,11,决策树学习,信息增益（Information Gain）： 某属性的信息增益就是按照该属性对训练例子进行划分所带来的熵的期望减少量,其中，T是训练例子集合，Tj是属性A取值为j的训练例子集合， 为T的一个子集,12,决策树学习,城市属性有两个取值是，否， 对于属性值“是”，共有7个正例，3个负例； 对于属性值“否”，共有4个正例，6个负例； I(城
6、市)=(10/20)(-7/10log2(7/10)-3/10log2(3/10) +(10/20)(-4/10log2(4/10) -6/10log2(6/10) =0.926,13,决策树学习,信息增益（Information Gain）： 某属性的信息增益就是按照该属性对训练例子进行划分所带来的熵的期望减少量,城市属性的信息增益是； Gain(T，城市)=E(T)-I(城市) =0.993-0.926 =0.067,其中，T是训练例子集合，Tj是属性A取值为j的训练例子集合， 为T的一个子集,14,决策树学习,熵是一个衡量系统混乱程度的统计量。熵越大，表示系统越混乱。分类的目的是提取系统
7、信息，使系统向更加有序、有规则组织的方向发展。所以自然而然的，最佳的分裂方案是使熵减少量最大的分裂方案。熵减少量就是Information Gain，所以，最佳分裂就是使Gain(A)最大的分裂方案。,交通条件属性拥有最大的信息增益，所以将其作为树的根节点。,15,决策树学习,16,决策树学习,17,决策树学习,决策树可用做分类器，每一个叶节点表示一个类别，其类标由多数表决法产生。内部节点表示属性，分支表示相应的同性值。这种树还可解释为一个规则集合。通过选择“最好”属性作为根节点来对决策树进行学习。确定好根节点后，就需要向根节点添加若干个分支，一个分支对应于一个属性值，根据与不同属性值的匹配结果将训练例子分别赋给相应的分支。在每个分支下都创建一对应的新节点，然后将其作为新的根节点，在每个节点上重复执行整个过程。“最好”属性可以采用多种方式进行选取，比较常用的度量是熵。,18,决策树学习,为以下分类计算对应的熵，并计算出x和y的信息增益。,
