模式识别课程(四)-线性分类器/线性判别函数

2019-11-04 本文已影响0人阿瑟_TJRS

确定性简单模式
从要解决的问题和训练样本出发，直接求出判别函数。
有些方法可事先确定判别函数的形式，通过训练样本确定其中的参数。如：SVM ，神经网络
也称为基于数据的模式识别方法(或统计模式识别的几何方法)

线性判别函数

基于样本直接设计分类器的三个基本要素

确定分类器即判别函数的类型
确定分类器设计的目标或准则
设计算法利用样本数据寻找最优的函数参数
形式化定义：
在判别函数集 $\{g(\theta),\theta \in \Theta \}$ 中，确定待定参数 $\theta ^{*}$ ，使得目标函数 $L(\theta)$ 最小/大：
$L(\theta ^{*})=\underset{\theta}{min}L(\theta)$

判别函数的定义

直接用来对样本进行分类判决的函数
若两类样本可以用一个方程 $g(x)=0$ 来划分，则 $g(x)$ 为判别函数/决策函数/判决函数， $g(x)=0$ 为决策面

如上图：

一般形式

线性判别函数由输入向量x的各分量的线性组合构成
矩阵形式表示为： $g(X)=W^TX+W_0$ , $W_0$ 称为偏置
$X=\begin{bmatrix} x_1\\ x_2\\ ...\\ x_d \end{bmatrix},W=\begin{bmatrix} W_1\\ W_2\\ ...\\ W_d \end{bmatrix}$
如果将偏置项也整合到矩阵中的话，可以表示为： $g(X)=W^T$ ，称为增广表示形式
$X=\begin{bmatrix} 1\\ x_1\\ x_2\\ ...\\ x_d \end{bmatrix},W=\begin{bmatrix} W_0\\ W_1\\ W_2\\ ...\\ W_d \end{bmatrix}$
关于判别函数存在以下两种情况

针对二分类问题，即类别有2个如上图，对于d维数据， $d-1$ 维的超平面把 $d$ 维输入空间中归为 $w_1$ 的点与归为 $w_2$ 的点分开。
权向量的性质： $W$ 和决策面正交，确定了决策面的方向。 对任一点X及其在决策面上的投影 $X_{\perp}$ ，有:
$X=X_{\perp}+r\frac{W}{||W||}$ , $g(X)=W^TX+W_0$ ,
且 $g(X_{\perp})=W^TX_{\perp}+W_0$
将X代入函数式中：
$g(X)=W^T(X_{\perp}+r\frac{W}{||W||})+W_0$
$=W^TX_{\perp}+r\frac{W^TW}{||W||}+W_0$
$=r||W||$
$r=\frac{g(x)}{||W||}$
其中 $r$ 是 $X$ 到决策面的垂直距离， $\frac{W}{||W||}$ 是 $W$ 方向上的单位向量。
任一点到决策面的垂直距离维 $r=\frac{g(x)}{||W||}$
$\color{red}{g(x)给出了点到判别面的距离的度量}$
原点到决策面的垂直距离为 $-\frac{W_0}{||W||}$
$\color{red}{w_0决定了判别面的位置}$
多类问题
给定c(c>2)个类别的样本集合，三种划分方式：

$\color{red}{1对其他 (one-versus-the-rest)}$ ,转化为c个两分类问题 存在不能确定区域
$\color{red}{1对1 (one-versus-one)}$ ，c(c-1)/2个二元判别函数
c类判别函数

广义线性判别函数

线性判别函数 $g(X)=W_0+\sum_{i=1}^dw_ix_i$ ：加入更高次的项，得到多项式判别函数： $g(x)=\sum_{i=1}^{\hat{d}}w_iy_i(X),g(X)=W^Ty$
$y=\sum w_{ij}x_ix_j$
$y_i(X)$ 将d维空间上的点映射到 $\hat{d}$ 维的y空间上的点，
导致维度灾难： $\hat{d}>d$ ，即向高维空间映射，
相应补救措施：强制加入大的 margin( 或训练样本之间的“间隔等措施，如支持向量机。这样处理基于假设：映射到高维空间并不给数据附加任何错误的结构及相关性）

Fisher线性判别分析

1936年R.A.Fisher提出线性判别分析(Linear Discriminant Analysis,LDA),从降低维度的角度考察线性分类模型。

目标：寻找有利于分类的投影方向.通过调整权向量w ，我们可以选择让类别之间分开最大的一个投影。
对于二分类问题，其思想是选择投影方向，使投影后两类相隔尽可能远，而同时每一类内部的样本又尽可能聚集。
在原样本空间中(二分类)，两类的类均值向量：

$m_2=\frac{1}{n_2}\sum_{X_i \in D_2}X_i$
当使用权重向量 $W$ 投影时， $类间分离程度$ 的最简单度量方式是 $类均值投影之后的距离$
$\widetilde{m_1}-\widetilde{m_2}=W^T(m_1-m_2)$ ,最大化该距离即可
$\widetilde{m_k}=\sum_{X_i \in D_i}W^TX_i$ 表示投影后的类均值向量，
均值投影的问题在于没有考虑类内的数据离散度
Fisher提出：通过最大化一个函数，使投影后的类间分离性最大，同时又能使每类的类内分离性较小。
投影后的类内离散度(使用方差表示)如下：
$\widetilde{s_k^2}=\sum_{X_i \in D_k}(W^TX_i-\widetilde{m_k})$
类内的总离散度是 $\widetilde{s_1^2}+\widetilde{s_2^2}$
$\color{red}{Fisher 准则函数定义为类间离散度与类内离散度之比。}$
$J_F(W)=\frac{(\widetilde{m_1}-\widetilde{m_2})^2}{\widetilde{s_1^2}+\widetilde{s_2^2}}$
将公式转换成为原空间的表示
$J_F(W)=\frac{W^TS_BW}{W^TS_WW}$
$S_B=(m_2-m_1)(m_2-m_1)^T$ 表示原空间类间离散度矩阵
$S_W=\sum_{i=1}^2\sum_{X\in D_i}(X-m_i)(X-m_i)^T$ 表示原空间类内离散度矩阵
$W^*=\underset{W}{argmax}J_F(W)=S_W^{-1}(m_2-m_1)$
对于准则函数 $J_F(W)$ 求其最大值，对W求导并令其等于0：

相应判别函数为：
若

练习

利用Fisher判别解决二分类

感知机算法

Rosenblatt于1962年提出，是一个二分类的线性模型，输入特征向量X，输出类别[t],分别为+1和-1
$y(X)=f(W^T\phi(X))$
非线性激活函数f()： $f(a)=\left\{\begin{matrix} +1,a\geqslant 0\\ -1,a<0 \end{matrix}\right.$