5决策树学习.ppt

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