模式分类之线性判别函数

模式识别系统的主要作用
判别各个模式所属的类别

对一个两类问题的判别，就是将模式x划分成ω1和ω2两类

线性判别函数

这时，若这些分属于ω1和ω2两类的模式可用一个直线方程d(x)=0来划分
d(x) = w1x1 + w2x2 + w3 = 0
其中x1、x2为坐标变量，w1、w2、w3为参数方程，则将一个不知类别的模式代入d(x)，有
- 若d(x) > 0，则 
- 若d(x) < 0，则 
此时，d(x)=0称为判别函数。

用判别函数进行模式分类依赖的两个因素
（1）判别函数的几何性质：线性的和非线性的函数。
线性的是一条直线；
非线性的可以是曲线、折线等；
线性判别函数建立起来比较简单（实际应用较多）；
非线性判别函数建立起来比较复杂。（训练也很复杂）
（2）判别函数的系数：判别函数的形式确定后，主要就是确定判别函数的系数问题。
只要被研究的模式是可分的，就能用给定的模式样本集来确定判别函数的系数。

多类情况1
用线性判别函数将属于ωi类的
模式与不属于ωi类的模式分开，

分几类就有几个判别函数，只要有一个判别函数大于零（条件成立），则分为某一类

不确定区域由两两交集组成，把一类和其他的分开

多类情况2
采用每对划分，即ωi/ωj两分法，
此时一个判别界面只能分开两种类别，
但不能把它与其余所有的界面分开。

仅仅判断两类（单纯的仅两类 是否能分开）

重要性质：dij = -dji

不确定区域由所有的交集组成，把类两两进行分开

多类情况3（多类情况2的特例）
这是没有不确定区域的ωi/ωj两
分法。假若多类情况2中的dij可分解
成：dij(x) = di(x) - dj(x) = (wi – wj)Tx，
则dij(x)>0相当于di(x)>dj(x)， ，
这时不存在不确定区域。

所有的判别函数交于一点，对于M类就有M个判别函数

某一类判别函数越大，就越趋于分到那一类

对于M类模式的分类，多类情况1需要M个判别函数，而多类情况2需要M*(M-1)/2个判别函数，

当M较大时，后者需要更多的判别式（这是多类情况2的一个缺点）。

采用多类情况1时，每一个判别函数都要把一种类别的模式与其余M-1种类别的模式分开，而不是将一种类别的模式仅于另一种类别的模式分开。
由于一种模式的分布要比M-1种模式的分布更为聚集，因此多类情况2对模式是线性可分的可能性比多类情况1更大一些（这是多类情况2的一个优点）。

线性判别函数简单，容易实现；
非线性判别函数复杂，不容易实现；
若能将非线性判别函数转换为线性判别函数，则有利于模式分类的实现。

基本思想
设有一个训练用的模式集{x}，在模式空间x中线性不可分，但在模式空间x*中线性可分，其中x*的各个分量是x的单值实函数，x*的维数k高于x的维数n，即若取
x* = (f1(x), f2(x), …., fk(x)), k>n
则分类界面在x*中是线性的，在x中是非线性的，此时只要将模式x进行非线性变换，使之变换后得到维数更高的模式x*，就可以用线性判别函数来进行分类。

广义线性判别函数的描述
一个非线性判别函数可如下表示：
 
其中{fi(x), i = 1,2,…,k}是模式x的单值实函数。若定义成广义形式：
x* = (f1(x), f2(x), …, fk(x), 1)T
此时有：
d(x*) = wTx*，其中w = (w1, w2, …, wk, wk+1)T
该式表明，非线性判别函数已被变换成广义线性，因此只讨论线性判别函数不会失去一般性意义。

广义线性判别函数的意义
线性的判别函数
fi(x)选用二次多项式函数
x是二维的情况
x是n维的情况
fi(x)选用r次多项式函数， x是n维的情况
[例子]
d(x)的总项数
说明
d(x)的项数随r和n的增加会迅速增大，即使原来模式x的维数不高，若采用次数r较高的多项式来变换，也会使变换后的模式x*的维数很高，给分类带来很大困难。
实际情况可只取r=2，或只选多项式的一部分，例如r=2时只取二次项，略去一次项，以减少x*的维数。

分段线性判别函数

线性判别函数在进行分类决策时是最简单有效的，但在实际应用中，常常会出现不能用线性判别函数直接进行分类的情况。
采用广义线性判别函数的概念，可以通过增加维数来得到线性判别，但维数的大量增加会使在低维空间里在解析和计算上行得通的方法在高维空间遇到困难，增加计算的复杂性。
引入分段线性判别函数的判别过程，它比一般的线性判别函数的错误率小，但又比非线性判别函数简单。

最小距离分类

设μ1和μ2为两个模式类ω1和ω2的聚类中心，定义决策规则：
 
这时的决策面是两类期望连线的垂直平分面，这样的分类器称为最小距离分类器。

模式空间
对一个线性方程w1x1+w2x2+w3x3=0，它在三维空间(x1 x2 x3)中是一个平面方程式，w=(w1 w2 w3)T是方程的系数。
把w向量作为该平面的法线向量，则该线性方程决定的平面通过原点且与w垂直。

x作为变量，w作为系统，求法向量，判断正负，看看是否属于对应分类

权空间
若将方程x1w1+x2w2+w3=0绘在权向量w=(w1 w2 w3)T的三维空间中，则x=(x1 x2 1)T为方程的系数。
若以x向量作为法线向量，则该线性方程所决定的平面为通过原点且与法线向量垂直的平面，它同样将权空间划分为正、负两边。
在系数x不变的条件下，若w值落在法线向量离开平面的一边，则wTx>0，若w值落在法线向量射向平面的一边，则wTx <0。

x作为系数，w作为变量，

Fisher线性判别

类内越紧密，类间分的越开。

l  Fisher准则函数中的基本参量

1. 在d维X空间

（1）各类样本的均值向量m_i

（2）样本类内离散度矩阵S_i和总样本类内离散度矩阵S_w

其中S_w是对称半正定矩阵，而且当N>d时通常是非奇异的。

（3）样本类间离散度矩阵S_b

S_b是对称半正定矩阵。

2. 在一维Y空间

（1）各类样本的均值

（2）样本类内离散度和总样本类内离散度

l  Fisher准则函数

Fisher准则函数定义为：

  

其中，是两类均值之差，是样本类内离散度。显然，应该使J_F(w)的分子尽可能大而分母尽可能小，即应寻找使J_F(w)尽可能大的w作为投影方向。但上式中并不显含w，因此须设法将J_F(w)变成w的显函数。

由各类样本的均值可推出：

这样，Fisher准则函数J_F(w)的分子可写成：

现在再来考察J_F(w)的分母与w的关系：

因此，

将上述各式代入J_F(w)，可得：

其中S_b为样本类间离散度矩阵，S_w为总样本类内离散度矩阵。

l  最佳变换向量w*的求取

 

为求使取极大值时的w*，可以采用Lagrange乘数法求解。令分母等于非零常数，即：

定义Lagrange函数为：

其中λ为Lagrange乘子。将上式对w求偏导数，可得：

令偏导数为零，有；

即

其中w*就是J_F(w)的极值解。因为S_w非奇异，将上式两边左乘，可得：

上式为求一般矩阵的特征值问题。利用的定义，将上式左边的写成：

其中为一标量，所以总是在向量的方向上。因此λw*可写成：

从而可得：

由于我们的目的是寻找最佳的投影方向，w*的比例因子对此并无影响，因此可忽略比例因子R/λ,有：

l  Lagrange乘数法（详见相关数学文献）

Lagrange乘数法是一种在等式约束条件下的优化算法，其基本思想是将等式约束条件下的最优化问题转化为无约束条件下的最优化问题。

问题：设目标函数为

y=f(x)，x=(x₁, x₂, …, x_n)

求其在m(m<n)个约束条件

g_k(x)=0，k=1,2,…,m

下的极值。

描述：引进函数

其中λ_k，k=1,2,…,m为待定常数。将L当作n+m个变量x₁, x₂, …, x_n和λ₁, λ₂, …, λ_m的无约束的函数，对这些变量求一阶偏导数可得稳定点所要满足的方程：

·基于最佳变换向量w*的投影

–w*是使Fisher准则函数JF(w)取极大值时的解，也就是d维X空间到一维Y空间的最佳投影方向。有了w*，就可以把d维样本x投影到一维，这实际上是多维空间到一维空间的一种映射，这个一维空间的方向w*相对于Fisher准则函数JF(w)是最好的。

–利用Fisher准则，就可以将d维分类问题转化为一维分类问题，然后，只要确定一个阈值T，将投影点yn与T相比较，即可进行分类判别。

这个还是要自己去研究，这样写好像效果不好

这个坑到这里就停了