第四章线性判别函数.ppt

1、第四章线性判别函数,4.1 引言 4.2 Fisher线性判别函数 4.3 感知器准则函数 4.4 最小平方(MSE)误差准则 4.5 最小错分样本数准则 4.6 线性支持向量机,4.1 引言,Bayes 决策规则尽管是最优的，但是实现困难。原因就是要求已知类条件概率密度 和先验概率 。 模式识别的最终任务是分类，可以直接设计分类函数分类器函数。 最简单的分类函数是分类超平面。 (2-维的情形，为一条直线，3-维的情形为一个平面，高维的情形即为超平面),4.1.1 线性判别函数的基本概念,线性判别函数的一般形式为： (4.1) 其中 是一个d维特征向量(模式向量),b是一个常数，称为阈值。 注

2、意：上式中所涉及到的运算包括：,线性判别规则,如果，设 当 则，判决 x 属于第一类，即 当 则，判决 x 属于第二类，即 当 则，判决 x 属于任一类，或拒绝,对于2-类分类问题，设,关于线性判别函数的说明（1）,方程 定义了空间中的一个超平面，一般将其称为分类决策超平面。 其中向量w是该超平面的法向量。 这是由于在该超平面上任取两点， 则有 因此，有 上式说明：向量w超平面是正交的。,关于线性判别函数的说明（2）,w,关于线性判别函数的说明（3）,关于线性判别函数的说明（4）,可以把 表示为如下的形式： 因此， 当 为坐标原点时， 若 ，则原点在超平面的正侧，若 原点在超平面的负侧。,广义

3、的线性判别函数,问题：若给定一个一维的模式空间，希望的划分是 或 ，则 ； 若 ，则,解决的方法,解决的办法,通过对上图的分析，可以建立入下的一个二次判别函数： 决策规则为：,判别函数的规范化,上述的二次判别函数写成如下的一般形式，便有 选择(构造)一个适当的变换，便可以把二次判别函数变换为一次的：,其中 经过变换 后，得到一个形式上类似于线性函数的判别函数。这种方法称为广义的线性判别函数。,线性分类器的设计步骤,设计线性分类器，就是利用训练集建立线性判别函数式(4.1)，或是广义线性判别函数式。函数式中只含有两个未知的量，即权向量和惩罚项常数（阈值）。所以说线性分类器的设计过程，实质上就是寻

4、找最优的权向量以及阈值常数。 其步骤如下：,设计步骤：,已知一组具有类别标记的样本集，训练集 ； 根据实际问题确定一个准则函数，使得该函数的值能够反映分类器的性能； 利用最优化技术，求出准则函数中最优的 和 ；它们所对应的极值解即为最优的分类决策。,4.2 Fisher 线性判别方法,在传统的模式识别方法中，降维技术是被广泛研究的，这也是一个非常有效的方法，至今一直被研究者所重视。 传统的降维方法包括：Fisher线性判别方法，SMO方法等。 但是，在利用降维方法处理模式识别问题时，经常遇到一些无法克服的问题，例如，。,Fisher 线性判别方法的基本思想,Fisher线性分类器的工作原理,设

5、训练集为 ，对于2-类分类问题，其中属于 类的模式记为子集 ，它含有 个样本，属于 类的模式记为 ，它含有 个样本。 令 这样便得到了N个一维样本 ，并且分别属于两个集合 。,几个基本参量（1）,d-维空间中 各类样本均值向量 ： 样本类内离散度矩阵 和总的类内离散度矩阵 为： 样本类间离散度矩阵,几个基本参量（2）,一维Y空间 各类样本均值 ： 样本类内离散度矩阵 和总离散度矩阵 ； ；,Fisher 准则函数,希望投影变换之后，在一维Y空间内，各类样本尽可能的分得开，即两类均值之差越大越好；同时各类样本内部尽量密集，即类内离散度越小越好。 定义函数： （4.23） 要使得该函数值尽可能的大

6、，就是说使得其分母尽可能的小，同时使得其分子尽可能的大。,分析(4.23),由于 故(4.23)之分子便成为：,分析(4.23),(4.23)之分母： 因此，,分析(4.23),将上述结果代入(4.23),可以得到： (4.27) 下面求使得上式取得极大值时的条件.利用Lagrange乘子法求解。令其分母为一常数c，即,求极值,引入Lagrange函数如下： (4.28) 上式中的 为Lagrange乘子。 将上式对w求偏导，并令其为零，得,求极值,是 的极值解。由于 是一个非奇异矩阵，所以有： 而 进一步的，有 故， 而我们所要求的是w的方向，故 实际上，这是一个由d维空间到一维空间的一个映

7、射。,Fisher线性判别规则,上面的工作：把d维空间中的向量映射到一维空间；因此d维空间中的分类问题便转化为一维空间中的分类问题。 现在的问题是求出一个适当的阈值b。 实际上，只要确定一个 (将其视为阈值)，将投影点 与 进行比较，即可做出决策。,Fisher线性判别规则,(1)当维数d以及样本数N都很大时，可采用Bayes分类决策规则。 (2)可以利用先验知识，选择阈值点 ，例如：,Fisher线性判别规则,对于任意给定的未知样本 ，首先计算 ，然后计算其投影点： 决策规则为： 时，有 时，有,Fisher线性判别函数的推广,问题：如何将2-类分类的情形推广至多类分类情形？,4.3 基于距

8、离的分类决策近邻法简介,最近邻决策规则 最近邻的改进之一 k-近邻,近邻法,基本思想： 对于未知样本（输入模式、数据） ，比较该样本与所有已知样本之间的距离，并决策 与离它最近的样本同属一类。,最近邻(nearest neighbor)决策规则,设有c个类别的模式识别问题(分类问题)， 为训练集，每一类 中含有 个样本。 定义： 因此，决策规则为： 若 则，决策,最近邻的改进之一,设有c类已知类别的样本(模式)，从每一类中选择一个标准样本，例如样本均值： 定义： 按照最小距离分类原则，决策规则为： 若 则,决策规则的简化,可以将上面的决策规则进行化简： 可以进一步的简化为： 因此决策规则可以表示为：,决策函数的简化,若定义： 决策规则将如何？,k-近邻,基本思想是：观察未知样本x的k个最近邻，若这k个近邻中的多数