文档介绍：决策树 ID3 算法决策树是对数据进行分类,以此达到预测的目的。该决策树方法先根据训练集数据形成决策树,如果该树不能对所有对象给出正确的分类,那么选择一些例外加入到训练集数据中,重复该过程一直到形成正确的决策集。决策树代表着决策集的树形结构。决策树由决策结点、分支和叶子组成。决策树中最上面的结点为根结点,每个分支是一个新的决策结点,或者是树的叶子。每个决策结点代表一个问题或决策, 通常对应于待分类对象的属性。每一个叶子结点代表一种可能的分类结果。沿决策树从上到下遍历的过程中,在每个结点都会遇到一个测试,对每个结点上问题的不同的测试输出导致不同的分支,最后会到达一个叶子结点,这个过程就是利用决策树进行分类的过程,利用若干个变量来判断所属的类别。 算法: ID3 算法是由 Quinlan 首先提出的。该算法是以信息论为基础,以信息熵和信息增益度为衡量标准,从而实现对数据的归纳分类。以下是一些信息论的基本概念: 定义 1 :若存在 n 个相同概率的消息,则每个消息的概率 p是1/n ,一个消息传递的信息量为 Log2(n) 定义 2 :若有 n 个消息,其给定概率分布为 P=(p1,p2 …pn) ,则由该分布传递的信息量称为 P的熵,记为 I(p)=-(i=1 ton求和)piLog2(pi) 。定义 3:若一个记录集合 T根据类别属性的值被分成互相独立的类 C1C2..Ck ,则识别 T 的一个元素所属哪个类所需要的信息量为 Info(T)=I(p) ,其中 P为 C1C2 …Ck的概率分布,即 P=(|C1|/|T|, …..|Ck|/|T|) 定义 4 :若我们先根据非类别属性 X 的值将 T 分成集合 T1,T2 …Tn ,则确定 T中一个元素类的信息量可通过确定 Ti的加权平均值来得到,即Info(Ti) 的加权平均值为: Info(X, T)=(i=1 ton求和)((|Ti|/|T|)Info(Ti)) 定义 5:信息增益度是两个信息量之间的差值,其中一个信息量是需确定 T的一个元素的信息量,另一个信息量是在已得到的属性 X的值后需确定的 T一个元素的信息量,信息增益度公式为: Gain(X, T)=Info(T)-Info(X, T) 为方便理解,在此举例说明算法过程,具体算法其实很简单,呵呵: 某市高中一年级(共六个班)学生上学期期末考试成绩数据库。其中学生考试成绩属性有:学籍号、语文、数学、英语、物理、化学,如下表所示,本例子的目的是利用决策树技术研究学生物理成绩的及格与否可以由哪些属性决定学号语文数学英语物理化学 ********** 27165637274 36081678780 46784716178 56476726472 67380665867 76281785279 87478476056 96268637467 107273734960 ………………………………第一步:对数据进行规范化处理。将上表中的数据规范化,用0表示成绩小于 60分,1表示成绩大于或等于 60分, 得到下表: 学号语文数学英语物理化学 ********** 27165637274 36081678780 46784716178 56476726472 67380665867 76281785279 87478476056 962686