贝叶斯决策法
线性判别法 监督模式识别 方法 判别函数法 非线性判别法 近邻法
决策树法
贝叶斯决策法
核心思想：根据对象归于某个模式的概率来进行决策分类 问题：已知对象的特征x，以及n个类别ω 1~ω n，求对象属 于哪个类别
贝叶斯公式：
P i x
p x i P i p x
其他分类方法
决策树算法
一个典型的决策树算法为ID3方法，其基础是香农信息论中 的信息熵 信息熵：信息论告诉我们，如果一个事件有k种可能的结果， 每种结果对应的概率为Pi，则对事件结果进行观察的信息熵 为
I P 1 log 2 P 1P 2 log 2 P 2 Pk log2 Pk Pi log2 Pi
i 1 k
其他分类方法
决策树算法
问题： 根据用户的—— 年龄（youth/middleaged/senior） 收入（high/medium/low） 是否学生（yes/no） 信用评级（excellent/fair） 判断其是否会买电脑（yes/no） 利用所提供的14个训练样本以及ID3 算法建立决策树
其他分类方法
核心思想：近朱者赤，近墨者黑
最近邻法和K-近邻法
• 最近邻算法：以离未知样本 最近的样本作为唯一判决依 据 • K-近邻算法（KNN）：以离 未知样本最近的k个样本作为 判决依据
核心问题：k的选择以及计 算速度的优化
其他分类方法
பைடு நூலகம்决策树算法
非数值特征：颜色，性别，年龄等没有数值意义的变量，也 可以称为属性 决策树算法： 利用一定训练样本， 从数据中“学习”出 决策规则
决策树算法
第三步： 求出各属性的信息熵减少量（或信息 增益），使用信息增益最大的属性作 为根节点 第四步： 使用递归的方法扩展树的节点，递归 终止条件为后继节点只包含一类样本
决策树算法存在过拟合的问题， 需要通过剪枝的方法来控制决策 树的规模
Thanks
对象 G x S y
LM
y’
基于数据的模式识别方法
基于数据的模式识别方法可以分为两种：监督模式识别和 非监督模式识别 监督模式识别：基于一定数量的类别已知的训练样本建立 分类器，也是模式识别的主要方法
非监督模式识别：事先不知道要划分什么类别，更没有类 别已知的样本用作训练，主要进行聚类分析
监督模式识别方法
• 步骤四，P(“3”|样本)~P(“3”)*P(样本|“3”)
贝叶斯决策法
朴素贝叶斯分类器 • P(<1,3>=1|”3”)可以采用最 大似然估计： c 1, 3 1,"3" P 1, 3 1 | "3" c "3" • 若采用最大似然估计，朴素贝叶 斯分类器对于稀疏数据非常敏感 • 设想若训练样本中所有“3”在 <1,3>处都没有值，那么计算得 到的后验概率等于零！
模式识别的方法
模式识别方法主要分为基于知识的方法和基于数据的方法 基于知识的方法：根据人们已知的关于研究对象的知识， 整理出若干描述特征与类别关系的准则，对未知样本通过 这些知识推理决策其类别。主要利用先验的知识 基于数据的方法：不利用先验知识，完全依靠训练样本来 建立样本与模式之间的联系，属于一种机器学习的分类方 法。基于数据的方法是模式识别最主要的方法
j 1
m
即根据 P i P x j | i 的最大值来进行分类决策
j 1
m
arg max P i P x j | i
j 1
m
贝叶斯决策法
朴素贝叶斯分类器 假定要计算该样本属于“3”的概率 • 步骤一，通过训练样本估计 先验概率P(“3”) • 步骤二，通过训练样本估计 P(<1,3>=1|”3”), P(<1,4>=1|”3”),… • 步骤三，通过独立假设计算 类条件概率P(样本|“3”) =P(<1,3>=1|”3”)* P(<1,4>=1|”3”)…
, i 1, 2..., n
P(ωi)：先验概率 p(x|ωi)：类条件概率密度 p(x)：总体概率密度 P(ωi|x)：后验概率
贝叶斯决策法
样本的错误率：
最小错误率决策法
p e | x P i | x , x j
i j
决策的错误率：样本错误概率的期望
P e P e | x p x dx
改用其他估计方法来 进行平滑处理！
贝叶斯决策法
拉普拉斯估计
• 假如投一次硬币，正面朝上，如何估计正面朝上的概率？ • 假如投100次硬币，有80次正面朝上，如何估计正面朝上 的概率？ • 假如投100万次硬币，有80万次正面朝上，如何估计正面 朝上的概率？ 启发： 1.在进行估计之前，我们有一些先验的期望 2.若样本数量很少，我们应该更依赖先验期望 3.若样本数量很多，我们应该更依赖数据
非线性分类器
有时候最优分类面并非线性平面，此时可以使用非线性判别 函数来进行分类
二次判别函数
分段线性函数
非线性分类器
支持向量机
核心思想：将非线性判别函数转换为广义线性判别函数，然 后在线性空间里求解最优分类平面
1 x1 x12
核函数
2 2 x2 x2
核函数目前没有一个通 用的选择方法
线性分类器
Fisher线性判别
• 核心思想：使投影后两类相隔尽量远，而同时每一类内部 的样本又尽可能聚集。通过最优化方法求解该最优投影方 向 • Fisher线性判别法只能得到最优投影方向即权向量，阈值 向量需要进一步求解
线性分类器
•
g x wT x 0
感知器算法
g y T y
最小错误率决策法即让P(e)达到最小。由于p(x)是固定的， 所以等价于对于所有x都让P(e|x)取最小。由样本x的错误率 计算公式可知，最小错误率决策等价于如下一种决策：
若 P i | x max P
j 1,...,n
| x 则
j
x i
贝叶斯决策法
根据贝叶斯公式：
最小错误率决策法
P i x
p x i P i p x
, i 1, 2..., n
重点讨论离散概率模型下的概率估计方法
贝叶斯决策法
朴素贝叶斯分类器
朴素贝叶斯分类器（Naive Bayes Classifier）：假定特征 各分量是相互独立的，因此类条件概率可写为
P x | P x1, x2 ,..., xm | P x j |
判别函数法
核心思想：根据训练样本确定一个判别函数g(x)，根据g(x) 的值来对未知样本进行分类 线性分类器：判别函数的形式是线性的
两类情况：
g x wT x 0
T i
多类情况： gi x w x i 0
核心问题是如何根据训练样 本确定权向量和阈值向量
非线性分类器：判别函数的形式是非线性的
Pattern Recognition Methods Using Supervised Learning
基于监督学习的模式识别方法
模式与模式识别
模式：模式是对某些感兴趣的客体的定量的或结构的描述， 模式类是具有某些共同特性的模式的集合。在模式识别学 科中，常常不区分“模式”和“模式类”
模式识别：把对象根据其特征划分到若干类别中适当的一 类 • 模式指的并不是事物本身，而是对事物的一种描述，也就 是我们从事物获得的信息 • 模式识别的过程就是建立分类器的过程 • 一些模式识别的例子：语音识别，字符与文字识别，人脸 识别等等
c x, y k PLAP,k x | y c y k X
|X|为x的取值个数，k为待定参数
贝叶斯决策法
arg max P i P x j | i
j 1 m
NBC的优缺点
• 优点：算法复杂度低，不要求很大的训练样本数量 • 缺点：要求特征分量满足条件独立条件，但很多时候这种 条件不能满足 • 改进：树增广朴素贝叶斯分类器（TAN）；贝叶斯增广朴 素贝叶斯分类器（BAN） 贝叶斯决策法依赖于样本的概率密度模型，当概率 密度模型难以估计时很难建立分类器。
其他分类方法
决策树算法
第一步： 计算总的信息熵 是否买电脑5次no，9次yes
第二步： 计算各属性的信息熵，以年龄为例 youth共出现5次，3次no2次yes
类似得到middleaged和senior的信 息熵分别为0和0.971。因此年龄属性 的信息熵为
其他属性的信息熵计算方法类似
其他分类方法
T zi 0 , i 1,
,N
线性分类器
•
感知器算法
T zi 0 , i 1, , N
可以使用迭代方法求解
线性分类器
•
感知器算法
感知器算法只能解决线性可分问题
线性分类器
最优分类超平面与线性SVM
• 支持平面 • 支持向量 • 最优分类超平面 • 线性支持向量机（SVM） 线性不可分时引入惩罚 函数进行求解