文档介绍：决策树ID3算法决策树是对数据进行分类,以此达到预测的目的。该决策树方法先根据训练集数据形成决策树,如果该树不能对所有对象给出正确的分类,那么选择一些例外加入到训练集数据中,重复该过程一直到形成正确的决策集。决策树代表着决策集的树形结构。决策树由决策结点、分支和叶子组成。决策树中最上面的结点为根结点,每个分支是一个新的决策结点,或者是树的叶子。每个决策结点代表一个问题或决策,通常对应于待分类对象的属性。每一个叶子结点代表一种可能的分类结果。沿决策树从上到下遍历的过程中,在每个结点都会遇到一个测试,对每个结点上问题的不同的测试输出导致不同的分支,最后会到达一个叶子结点,这个过程就是利用决策树进行分类的过程,利用若干个变量来判断所属的类别。2(ID3算法:ID3算法是由Quinlan首先提出的。该算法是以信息论为基础,以信息熵和信息增益度为衡量标准,从而实现对数据的归纳分类。以下是一些信息论的基本概念:定义1:若存在n个相同概率的消息,则每个消息的概率p是1/n,一个消息传递的信息量为Log2(n)定义2:若有n个消息,其给定概率分布为P=(p1,p2„pn),则由该分布传递的信息量称为P的熵,记为I(p)=-(i=1ton求和)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=1ton求和)((|Ti|/|T|)Info(Ti))定义5:信息增益度是两个信息量之间的差值,其中一个信息量是需确定T的一个元素的信息量,另一个信息量是在已得到的属性X的值后需确定的T一个元素的信息量,信息增益度公式为:Gain(X,T)=Info(T)-Info(X,T)为方便理解,在此举例说明算法过程,具体算法其实很简单,呵呵:某市高中一年级(共六个班)学生上学期期末考试成绩数据库。其中学生考试成绩属性有:学籍号、语文、数学、英语、物理、化学,如下表所示,本例子的目的是利用决策树技术研究学生物理成绩的及格与否可以由哪些属性决定学号语文数学英语物理化学176716871812716563727436081678780467847161785647672647267380665867762817852798747847605696268637467107273734960„„„„„„„„„„„„第一步:对数据进行规范化处理。将上表中的数据规范化,用0表示成绩小于60分,1表示成绩大于或等于60分,得到下表:学号语文数学英语物理化学176716871812716563727436081678780467847161785647672647267380665867762817852798747847605696268637467107273734960„„„„„„„„„„„„第二步:选取训练实例集。从所有学生中进行抽样,将抽样数据作为训练集,共计有161条记录。经统计,在这161条记录的训练集中单科成绩及格人数和不及格人数如下表所示:语文数学英语物理化学及格8257343239不及格79104127129122第三步:利用信息增益度选取最能区别训练集中实例的属性。首先计算课程物理所含有的信息量。由表4可知物理及格人数P=32,不及格人数N=129,则可得到:Info(T)=I(32,129)=-[(32/161)Log2(32/161)+(129/161)Log2(129/161)]=,课程语文所包含的总信息量。经统计,语文和物理有如下表所示的统计数据:成绩搭配人数语文成绩=1且物理成绩=128语文成绩=1且物理成绩=054语文成绩=0且物理成绩=14语文成绩=0且物理成绩=075可得到:Info(X,T)=)=(i=1ton求和)((|Ti|/|T|)Info(Ti))=(82/161)I(28,54)+(79/161)I(4,75)=:Gain(X,T)=Info(T)-Info(X,T)=-=,结果如下表所示::创建一个树结点,并创建该结点的子链,每个子链代表所选属性的一个唯一值。使用子链的值进一步