文档介绍：第章决策树和决策规则
第一页，共23页。
本章目标
分析解决分类问题的基于逻辑的方法的特性
信息论基础
ID3算法
了解何时以及怎样用修剪方法降低决策树和复杂度
总结用决策树和决策规则表示一个分类模型的局限性
第二页，共23页。
什么是分类？
数据分类（data classfication）是数据挖掘的主要内容之一，主要是通过分析训练数据样本，产生关于类别的精确描述。这种类别通常由分类规则组成，可以用来对未来的数据进行分类和预测。
数据分类的两个步骤：
第1步：建立一个模型，描述给定的数据类集或概念集（简称训练集）
第2步：使用模型对数据进行分类。包括评估模型的分类准确性以及对类标号未知的元组按模型进行分类
训练数据
分类算法
分类规则
学****br/>测试数据
待分类数据
分类规则
模型评估
新数据分类
第三页，共23页。
信息论基础
，以客观概率信息为研究对象，从通信的信息传输问题中总结和开拓出来的理论。主要研究的问题：
信源的描述，信息的定量度量、分析与计算
信道的描述，信道传输的定量度量、分析与计算。
信源、信道与通信系统之间的统计匹配，以及通信系统的优化 —Shannon的三个编码定理。
信息论诞生五十年来，至今，仍然是指导通信技术发展的理论基础，是创新通信体制的源泉。
第四页，共23页。
香农信息(概率信息)
信息是事物运动状态或存在方式的不确定性的描述。
在通信系统中形式上传输的是消息，但实质上传输的是信息
信源
信宿
信道
消息
干扰或噪声
（发信者）
（收信者）
通信系统框图
第五页，共23页。
样本空间：某事物各种可能出现的不同状态，即所有可能选择的消息的集合。
对于离散消息的集合，概率测度是对每一个可能选择的消息指定一个概率。一个样本空间和它的概率测度称为一个概率空间。表示：[X，P]
在离散情况下：

其中，P(ui)为选择符号 ui作为消息的概率，称为先验概率
信源数学模型
第六页，共23页。
后验概率：条件概率 —接收端收到消息（符号）后而发送端发的是的概率。
自信息：消息发生后所含有的信息量，反映了消息发生前的不确定性：
第七页，共23页。
信源熵
定义：信源各个离散消息的自信息量的数学期望（即概率加权的统计平均值）为信源的平均信息量，一般称为信源的信息熵，也叫信源熵或香农熵，有时也称为无条件熵或熵函数，简称熵。
公式：
熵函数的自变量是X,表示信源整体，实质上是无记忆信源平均不确定性的度量。
单位：以2为底，比特/符号
第八页，共23页。
互信息
后验熵：当接收到输出符号V=vj后，信源的平均不确定性，即输入符号U的信息度量
条件熵：对后验熵在输出符号集V中求期望
称为信道疑义度。表示在输出端收到全部输出符号V后，对于输入端的符号集U尚存有不确定性（有疑义），这是由于存在干扰（噪声）引起的。
H(U|V)<H(U)，表明接收到符号集V的所有符号后，关于输入符号U的平均不确定性减少了。
第九页，共23页。
互信息：先验的不确定性减去收到输出符号集V后尚存在的不确定性，表示收信者获得的信息量,也称信息增益
第十页，共23页。