1、决策树和决策规则决策树和决策规则第第7章章本章目标本章目标 分析解决分类问题的基于逻辑的方法的特性分析解决分类问题的基于逻辑的方法的特性 信息论基础信息论基础 ID3算法算法 了解何时以及怎样用修剪方法降低决策树和复杂度了解何时以及怎样用修剪方法降低决策树和复杂度 总结用决策树和决策规则表示一个分类模型的局限性总结用决策树和决策规则表示一个分类模型的局限性 什么是分类？数据分类（data classfication）是数据挖掘的主要内容之一，主要是通过分析训练数据样本，产生关于类别的精确描述。这种类别通常由分类规则组成，可以用来对未来的数据进行分类和预测。数据分类的两个步骤：第1步：建立一个模
2、型，描述给定的数据类集或概念集（简称训练集）第2步：使用模型对数据进行分类。包括评估模型的分类准确性以及对类标号未知的元组按模型进行分类训练数据分类算法分类规则学习测试数据待分类数据分类规则模型评估新数据分类7.1 信息论基础 信息论是C.E.Shannon四十年代末期，以客观概率信息为研究对象，从通信的信息传输问题中总结和开拓出来的理论。主要研究的问题：信源的描述，信息的定量度量、分析与计算 信道的描述，信道传输的定量度量、分析与计算。信源、信道与通信系统之间的统计匹配，以及通信系统的优化 Shannon的三个编码定理。信息论诞生五十年来，至今，仍然是指导通信技术发展的理论基础，是创新通信体
3、制的源泉。香农信息(概率信息)信息是事物运动状态或存在方式的不确定性的描述。在通信系统中形式上传输的是消息，但实质上传输的是信息信源信宿信道消息干扰或噪声（发信者）（收信者）通信系统框图 样本空间：某事物各种可能出现的不同状态，即所有可能选择的消息的集合。对于离散消息的集合，概率测度是对每一个可能选择的消息指定一个概率。一个样本空间和它的概率测度称为一个概率空间。表示：X，P 在离散情况下：其中，P(ui)为选择符号 ui作为消息的概率，称为先验概率先验概率)(,),(),(,)(2121qquPuPuPuuuuPU信源数学模型 后验概率后验概率：条件概率 接收端收到消息（符号）后而发送端发的
4、是 的概率。自信息：消息 发生后所含有的信息量，反映了消息 发生前的不确定性：)|(jivuPjviuiuiu)(log)(1log)(iiiuPuPuI 信源熵 定义：信源各个离散消息的自信息量的数学期望（即概率加权的统计平均值）为信源的平均信息量，一般称为信源的信息熵，也叫信源熵或香农熵，有时也称为无条件熵或熵函数，简称熵。公式：熵函数的自变量是X,表示信源整体，实质上是无记忆信源平均不确定性的度量。单位：以2为底，比特/符号)(log)()(1log)()(212iniiiixpxpxpExIEXH互信息 后验熵：当接收到输出符号V=vj后，信源的平均不确定性，即输入符号U的信息度量 条
5、件熵：对后验熵在输出符号集V中求期望称为信道疑义度。表示在输出端收到全部输出符号V后，对于输入端的符号集U尚存有不确定性（有疑义），这是由于存在干扰（噪声）引起的。H(U|V)H(U)，表明接收到符号集V的所有符号后，关于输入符号U的平均不确定性减少了。)|(log)|()|(1log)|()|(212jinijijijijvupvupvupEvuIEvUH)|(log)|()()|()|(211jinijinjjjvupvupvpvUHEVUH 互信息互信息：先验的不确定性减去收到输出符号集V后尚存在的不确定性，表示收信者获得的信息量,也称信息增益)|()(),(VUHUHVUI7.2 ID
6、3算法 决策树（Decision Tree）方法：决策树方法的起源是概念学习系统CLS，然后发展到由Quiulan研制ID3方法，然后到著名的C4.5算法，C4.5算法的一个优点是它能够处理连续属性。决策树又称为判定树，是运用于分类的一种树结构。其中的每个内部结点代表对某个属性的一次测试，每条边代表一个测试结果，叶结点代表某个类或者类的分布，最上面的结点是根结点。7.2 ID3算法（续）ID3算法思想：1.任意选取一个属性作为决策树的根结点，然后就这个属性所有的取值创建树的分支；2.用这棵树来对训练数据集进行分类，如果一个叶结点的所有实例都属于同一类，则以该类为标记标识此叶结点；如果所有的叶结
7、点都有类标记，则算法终止；3.否则，选取一个从该结点到根路径中没有出现过的属性为标记标识该结点，然后就这个属性所有的取值继续创建树的分支；重复算法步骤step 2显然，不同的属性选取顺序将生成不同的决策树。因此，适当地选取属性将生成一棵简单的决策树。在ID3算法中，采用了一种基于信息的启发式的方法来决定如何选取属性。启发式方法选取具有最高信息增益的属性，也就是说，生成最少分支决策树的那个属性。7.2 ID3算法（续）属性1属性2A7079类18089属性3类2假9099类2属性26069属性3类1真7079属性3类1假9099属性3类1真B属性27079属性38089属性39099属性3类2真
8、类1假类2真类1假7.2 ID3算法（续）属性2属性1A8089属性3类1真属性16069属性3类1真7079属性3类1属性1类2B属性1属性3属性3属性3类2类1A类2真类2假BCC假9099A真B类1真属性3C类1假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.940bit2)计算属性1的条件熵H(C|V)属性1取值vj时，类别Ci的条件概率：P(Ci|vj)=|Ci|/|vj|属性1取值v1=A,v2
9、=B,v3=CP(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)(log)()(21iniiCpCpCH)|(log)|()()|(211jinijinjjvCpvCpvpVCH7.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.694bit3)计算信息增益Gain(属性1)=H(C)-H(C|V)=0.246bit同理可求得Gain(属性
10、3)=0.048bit根据增益准则，ID3算法将选择属性1做为根节点，因为该属性的信息增益最大。为了求得最优解，还应该分析属性2的信息增益，但因它是连续型数值，不能直接求，而要先进行离散化转换成分类型的数据。7.3 修剪决策树 决策树修剪的主要任务是抛弃一个或更多的子树，并用叶子替换这些子树，使决策树简单化。在替换这些子树时，我们期望算法降低预测误差率来提高分类模型的质量 剪枝操作有两种策略:预剪枝：在树生成过程中判断是否还继续扩展决策树。若停止扩展，相当于剪去该结点以下的分枝后剪枝：对于生成好的树剪去某些结点和分枝 C4.5算法遵循基于误差的后剪枝，也叫悲观修剪，即如果使用叶子或树枝代替原来
11、的子树后，误差率能够下降，则就使用此叶子或树枝代替原来的子树。7.3 修剪决策树（续）准备知识：二项式分布 在医学领域中，有一些随机事件是只具有两种互斥结果的离散型随机事件，称为二项分类变量（dichotomous variable），如对病人治疗结果的有效与无效，某种化验结果的阳性与阴性，接触某传染源的感染与未感染等。二项分布（binomial distribution）就是对这类只具有两种互斥结果的离散型随机事件的规律性进行描述的一种概率分布。考虑只有两种可能结果的随机试验，当成功的概率（）是恒定的，且各次试验相互独立，这种试验在统计学上称为贝努里试验（Bernoulli trial）。如
12、果进行n次贝努里试验，取得成功次数为X（X=0,1,n）的概率可用下面的二项分布概率公式来描述：其中 表示在n次实验中出现X的各种组合情况XnXXnXP)1()()()(Xn7.3 修剪决策树（续）决策树的子树如图所示，这里根节点是关于属性A的3个可能值1，2，3的检验。根节点的子节点是用相应的类和参数(|Ti|,E)表示的叶。问题是估计修剪子树并用它的替换根结点作为一个新的归纳根节点的概率类1(16,1)7.3 修剪决策树（续）如一个叶结点覆盖N个实例，其中E个为错误的，对于具有信任度CF的实例，计算一个2项式分布UCF(E,N)，即是实例误判的概率，那么N个实例误判的数目为N*UCF(E,
13、N)。子树的错误数目为所有叶结点的总和。设CF为25%，从统计表中可查出E的上限置信极限：U25%(0,6)=0.206,U25%(0,9)=0.143,U25%(0,1)=0.750,U25%(1,16)=0.157则子树的实例误判数目为：6*U25%(0,6)+9*U25%(0,9)+1*U25%(0,1)=3.257若以一个叶子“类1(16,1)”代替子树，则误判数目为：16*U25%(1,16)=16*0.157=2.5126FTI64TSH=tT4U=tTHY=t then calss A。该规则覆盖3个实例，其中2个判断正确，1个误判。则误判概率为UCF(1,3)=69%。设删除其中各个条件之后的误判概率如表所示则选择误判概率最小的条件，即FTI64，从原来条件中删除此条件，规则变为：if TSH6TSH=tT4U=tTHY=t then calss A重复上述过程，直到最后的误判概率大于前面规则的误判概率为止删除的条件删除的条件Y1+Y2E1+E2UCF(E1+E2,Y1+E1+Y2+E2)TSH63155%FTI646134%TSH=t2169%T4U=t2169%THY=t35997%
