了消息 ui 发生前的不确定性：
I (ui )

log
1 P(ui )

log
P(ui )
– 信源熵
• 定义：信源各个离散消息的自信息量的数学期望（即概 率加权的统计平均值）为信源的平均信息量，一般称为 信源的信息熵，也叫信源熵或香农熵，有时也称为无条 件熵或熵函数，简称熵。
• 公式：
H (X )
• 数据分类的两个步骤：
– 第1步：建立一个模型，描述给定的数据类集或概念集（简称训练集）
学习
训练数据
分类算法
分类规则
– 第2步：使用模型对数据进行分类。包括评估模型的分类准确性以及对类
标号未知的元组按模型进行分类
模型评估
新数据分类
分类规则
测试数据
待分类数据
7.1 信息论基础
• 信息论是C.E.Shannon四十年代末期，以客观概率 信息为研究对象，从通信的信息传输问题中总结和 开拓出来的理论。主要研究的问题 ：
7.2 ID3算法（续）
• ID3算法思想：
1. 任意选取一个属性作为决策树的根结点，然后就这个属性所有的 取值创建树的分支；
2. 用这棵树来对训练数据集进行分类，如果一个叶结点的所有实例 都属于同一类，则以该类为标记标识此叶结点；如果所有的叶结 点都有类标记，则算法终止；
3. 否则，选取一个从该结点到根路径中没有出现过的属性为标记标 识该结点，然后就这个属性所有的取值继续创建树的分支；重复 算法步骤step 2
概率空间。表示：[X，P]
• 在离散情况下：
U P(u)

u1,

P(u1
)
,
u2 ,, P(u2 ),,
uq P(uq )
其中，P(ui)为选择符号 ui作为消息的概率，称为先验概率
• 后验概率：条件概率P(ui | v j )—接收端收到消息
（符号） v后j 而发送端发的是 的ui概率。 • 自信息：消息 ui 发生后所含有的信息量，反映
类1 属性3 假
类2 属性3 属性3 属性3
真假
真
类2
类1
类1 类1
属性2
70~79 80~89 90~99
属性3 属性3 属性3
真假 真
假
类2 类1 类2
类1
7.2 ID3算法（续）
属性2 90~99
60~69 70~79 80~89
属性1
B
属性3 真
属性1
A
B
类1 类1
属性1
C
A
C
属性3 属性3
H (U
|vj)
E[I (ui
| vj )] E[log2
1
n
]
பைடு நூலகம்
p(ui | v j )
i1
p(ui
| v j ) log2
p(ui
| vj )
• 条件熵：对后验熵在输出符号集V中求期望
n
n
H (U |V ) E[H (U | v j )] p(v j ) p(ui | v j ) log 2 p(ui | v j )
真
假
属性1
属性3 A B
假
真
属性3 真
C
属性3 属性3
真
假
类2
类2 类1 类2 类2 类1 类1
类1
7.2 ID3算法（续）
• 表7-1的ID3算法实例计算：
1)计算信息熵H(C)
n
H (C) p(Ci ) log2 p(Ci )
i 1
类别Ci出现概率P(Ci)=|Ci|/|X|,|Ci|为类别Ci的样本数,|X|为总的样本数
第7章
决策树和决策规则
本章目标
– 分析解决分类问题的基于逻辑的方法的特性 – 信息论基础 – ID3算法 – 了解何时以及怎样用修剪方法降低决策树和复杂度 – 总结用决策树和决策规则表示一个分类模型的局限性
• 什么是分类？
– 数据分类（data classfication）是数据挖掘的主要内容之一，主要是通 过分析训练数据样本，产生关于类别的精确描述。这种类别通常由分类 规则组成，可以用来对未来的数据进行分类和预测。
I(U,V ) H(U) H(U |V )
7.2 ID3算法
• 决策树（Decision Tree）方法：
– 决策树方法的起源是概念学习系统CLS，然后发展到由Quiulan研制 ID3方法，然后到著名的C4.5算法，C4.5算法的一个优点是它能够处 理连续属性。
– 决策树又称为判定树，是运用于分类的一种树结构。其中的每个内 部结点代表对某个属性的一次测试，每条边代表一个测试结果，叶 结点代表某个类或者类的分布，最上面的结点是根结点。
消息
信源
信道
信宿
（发信者）
（收信者）
干扰或 噪声
通信系统框图
• 在通信系统中形式上传输的是消息，但实质 上传输的是信息
信源数学模型
• 样本空间：某事物各种可能出现的不同状态，即所有可能 选择的消息的集合。
• 对于离散消息的集合，概率测度是对每一个可能选择的消 息指定一个概率。一个样本空间和它的概率测度称为一个
–信源的描述，信息的定量度量、分析与计算 –信道的描述，信道传输的定量度量、分析与计算。 –信源、信道与通信系统之间的统计匹配，以及通信系统
的优化 —Shannon的三个编码定理。
• 信息论诞生五十年来，至今，仍然是指导通信技术 发展的理论基础，是创新通信体制的源泉 。
香农信息(概率信息)
• 信息是事物运动状态或存在方式的不确定性 的描述。
j 1
i 1
称为信道疑义度。表示在输出端收到全部输出符号V后，对于
输入端的符号集U尚存有不确定性（有疑义），这是由于存在
干扰（噪声）引起的。
H(U|V)<H(U)，表明接收到符号集V的所有符号后，关于输入 符号U的平均不确定性减少了。
• 互信息：先验的不确定性减去收到输出符号 集V后尚存在的不确定性，表示收信者获得的 信息量,也称信息增益
– 显然，不同的属性选取顺序将生成不同的决策树。因此，适当地 选取属性将生成一棵简单的决策树。在ID3算法中，采用了一种基 于信息的启发式的方法来决定如何选取属性。启发式方法选取具 有最高信息增益的属性，也就是说，生成最少分支决策树的那个 属性。
7.2 ID3算法（续）
属性1 A
B
属性2
属性2
70~7980~89 90~99 60~6970~7990~99
E[I (xi )]
E[log 2
1
n
]
p(xi )
i 1
p(xi ) log 2
p(xi )
• 熵函数的自变量是X,表示信源整体，实质上是无记忆信 源平均不确定性的度量。
• 单位：以2为底，比特/符号
互信息
• 后验熵：当接收到输出符号V=vj后，信源的平
均不确定性，即输入符号U的信息度量