第7章 决策树和决策规则.ppt

7.1 信息论基础 信息论是C.E.Shannon四十年代末期，以客观概率信息为研究对象，从通信的信息传输问题中总结和开拓出来的理论。主要研究的问题 ： 信源的描述，信息的定量度量、分析与计算 信道的描述，信道传输的定量度量、分析与计算。 信源、信道与通信系统之间的统计匹配，以及通信系统的优化 —Shannon的三个编码定理。 信息论诞生五十年来，至今，仍然是指导通信技术发展的理论基础，是创新通信体制的源泉 。 香农信息(概率信息) 信息是事物运动状态或存在方式的不确定性的描述。 在通信系统中形式上传输的是消息，但实质上传输的是信息 信源数学模型 样本空间：某事物各种可能出现的不同状态，即所有可能选择的消息的集合。 对于离散消息的集合，概率测度是对每一个可能选择的消息指定一个概率。一个样本空间和它的概率测度称为一个概率空间。表示：[X，P] 在离散情况下： 其中，P(ui)为选择符号 ui作为消息的概率，称为先验概率 后验概率：条件概率 —接收端收到消息（符号） 后而发送端发的是 的概率。 自信息：消息 发生后所含有的信息量，反映了消息 发生前的不确定性： 信源熵 定义：信源各个离散消息的自信息量的数学期望（即概率加权的统计平均值）为信源的平均信息量，一般称为信源的信息熵，也叫信源熵或香农熵，有时也称为无条件熵或熵函数，简称熵。 公式： 熵函数的自变量是X,表示信源整体，实质上是无记忆信源平均不确定性的度量。 单位：以2为底，比特/符号 互信息 后验熵：当接收到输出符号V=vj后，信源的平均不确定性，即输入符号U的信息度量 条件熵：对后验熵在输出符号集V中求期望 称为信道疑义度。表示在输出端收到全部输出符号V后，对于输入端的符号集U尚存有不确定性（有疑义），这是由于存在干扰（噪声）引起的。 H(U|V)H(U)，表明接收到符号集V的所有符号后，关于输入符号U的平均不确定性减少了。 互信息：先验的不确定性减去收到输出符号集V后尚存在的不确定性，表示收信者获得的信息量,也称信息增益 7.2 ID3算法 决策树（Decision Tree）方法： 决策树方法的起源是概念学习系统CLS，然后发展到由Quiulan研制ID3方法，然后到著名的C4.5算法，C4.5算法的一个优点是它能够处理连续属性。 决策树又称为判定树，是运用于分类的一种树结构。其中的每个内部结点代表对某个属性的一次测试，每条边代表一个测试结果，叶结点代表某个类或者类的分布，最上面的结点是根结点。 7.2 ID3算法（续） ID3算法思想： 任意选取一个属性作为决策树的根结点，然后就这个属性所有的取值创建树的分支； 用这棵树来对训练数据集进行分类，如果一个叶结点的所有实例都属于同一类，则以该类为标记标识此叶结点；如果所有的叶结点都有类标记，则算法终止； 否则，选取一个从该结点到根路径中没有出现过的属性为标记标识该结点，然后就这个属性所有的取值继续创建树的分支；重复算法步骤step 2 显然，不同的属性选取顺序将生成不同的决策树。因此，适当地选取属性将生成一棵简单的决策树。在ID3算法中，采用了一种基于信息的启发式的方法来决定如何选取属性。启发式方法选取具有最高信息增益的属性，也就是说，生成最少分支决策树的那个属性。 7.2 ID3算法（续） 7.2 ID3算法（续） 7.2 ID3算法（续） 表7-1的ID3算法实例计算： 1)计算信息熵H(C) 类别Ci出现概率P(Ci)=|Ci|/|X|,|Ci|为类别Ci的样本数,|X|为总的样本数 |C1|=9,|C2|=5,|X|=14，代入上式算得H(C)=0.940bit 2)计算属性1的条件熵H(C|V) 属性1取值vj时，类别Ci的条件概率：P(Ci|vj)=|Ci|/|vj| 属性1取值v1=A, v2=B, v3=C P(v1)=5/14, P(v2)=4/14, P(v3)=5/14 取值为A的5个例子中有2个类1，3个类2，所以: P(C1|v1)=2/5 P(C2|v1)=3/5 7.2 ID3算法（续） 表7-1的ID3算法实例计算： 同理有： P(C1|v2)=4/4 P(C2|v2)=0/4 P(C1|v3)=3/5 P(C2|v1)=2/5 代入上式得： H(C|V)=0.694bit 3)计算信息增益 Gain(属性1)=H(C)- H(C|V)=0.246bit 同理可求得Gain(属性3)=0.048bit 根据增益准则，ID3算法将选择属性1做为根节点，因为该属性的信息增益最大。为了求得最优解，还应该分析属性2的信息增益，但因它是连续型数值，不能直接求，而要先进行离散化转换成