模式识别笔记-第三章(1)

作者: Xavier_NZX | 来源:发表于2018-11-05 19:49 被阅读3次

判别函数分类法

统计模式识别是模式识别学科中研究历史最长，与其他几个方向相比发展的最为成熟的理论。
统计模式识别分为聚类分析法和判别函数法两大类，聚类分析法属于非监督分类（机器学习中的非监督学习），判别函数法是监督分类。在判别函数法中，又可分为线性判别函数法、非线性判别函数法和统计决策方法等。
线性判别函数法和非线性判别函数法是几何分类法，统计决策方法是概率分类法。
所谓几何分类法，是指在特征空间中，利用矢量空间的直观概念，使用代数方程方法，对模式进行分类。因此也被称为：代数界面方程法。
所谓概率分类法，是指把模式视为随机变量的抽样，利用统计决策理论（贝叶斯决策理论）成熟的判决准则与方法，对模式样本进行分类。

3.1 判别函数

3.1.1 判别函数的定义

判别函数是直接用来对模式进行分类的决策函数，也称判决函数或决策函数。

2维判别函数
上图中d(X)为2维情况下的判别函数。
维数N=2时：判别边界为一直线。
维数N=3时：判别边界为一平面。
维数N>3时：判别边界为一(N-1)维超平面。

3.1.2 判别函数正负值的确定

判别界面的正负侧，是在训练判别函数的权值时人为确定的。
二分类情况下一般令第1类样本的函数值大于零，第2类样本的函数值小于零，并且可以推广到任意维度的欧式空间。
具体值的大小不重要（后面的学习算法会讲到）。

3.1.3 确定判别函数的两个因素

1）判别函数d(X)的几何性质
若解决一个三维线性分类问题，判别函数的线性性质决定了它的形式为：
d(X)=ω₁x₁+ω₂x₂+ω₃x₃+ω₄。
维度不超过3时往往易于确定形式，但超过3则难以通过我们的想象力来确定函数形式，这时需要依靠严格的数学方法。
2）判别函数d(X)的系数
只要确定了形式，就可以通过模式样本来确定系数。

3.2 线性判别函数

3.2.1 线性判别函数的一般形式

将3.1中的二维模式推广到n维：
d(X)=ω₁x₁+ω₂x₂+…+ω_nx_n+ω_n+1=W₀^TX+ω_n+1
也可写为增广向量形式：

增广向量形式

3.2.2 线性判别函数的性质

两类情况
两类情况
2.多类情况
对M个线性可分模式类，ω₁，ω₂，… ω_M，有三种分类方式：
1）多类情况1： $ω_{i}/\overline{ω}_{i}$ 是非两分法
每个模式类都可以通过一个单独的判别界面将自己与其他模式类分开。
是非二分法
2）多类情况2： $ω_{i}/ω_{j}$ 二分法
一个判别界面只能可以并且只能分开两个类别。 $d_{ij}(X)=W^T_{ij}X$ ，可以分开 $ω_{i}$ 和 $ω_{j}$ 。并且 $d_{ij}=-d_{ji}$ 。
两分法
3）多类情况3： $ω_{i}/ω_{j}$ 二分法的特殊情况
当 $ω_{i}/ω_{j}$ 二分法中的判别函数 $d_{ij}$ 二分法可以分解为：

$d_{ij}(X)=d_{i}(X)-d_{j}(X)=W^T_iX-W^T_jX$

那么 $d_{i}(X)>d_{j}(X)$ 就相当于多类情况2中的 $d_{ij}(X)>0$ .

总结为： $d_{i}(X)=max\{d_{k}(X),k=1,…,M\},若X∈ω_{i}$

二分类特例

3.3 广义线性判别函数

实际的模式分布不都是线性可分的，所以我们可以通过某映射将X变成X^*，把原空间中的非线性判别函数变为线性判别函数。
1.非线性多项式函数
$d(X)=\omega_1f_1(X)+\omega_2f_2(X)+…+\omega_kf_k(X)+\omega_{k+1}=\sum^{k+1}_{i=1}\omega_if_i(X)$
2.广义线性判别函数
设n维训练集{X}在模式空间X中线性不可分，其非线性判别函数为上式，定义一个新的模式向量X^*，它的分量等于f_i(X^*)：
$X^*=(f_1(X),f_2(X),…,f_k(X),1)^T$
这样（1）中的式子可以表示为：
$d(X)=W^TX^*=d(X^*)$
有两个问题：
（1）非线性变换可能非常复杂。
（2）维数大大增加，导致维数灾难。

3.4 线性判别函数的几何性质

3.4.1 模式空间与超平面

1.概念
模式空间：以n维模式向量X的n个分量为坐标变量的欧氏空间。
模式向量：点、有向线段。
线性分类：用d(X)进行分类，相当于用超平面d(X)=0把模式空间分成不同的决策区域。
2.特性
（1）单位法向量： $U=\frac{W_0}{||W_0||}$
（2）不在超平面上的模式点 $X$ 可以表示为： $X=X_p+R=X_P+r\frac{W_0}{||W_0||}$ ， $X_P$ 为 $X$ 在超平面上的投影， $r$ 是 $X$ 到超平面的垂直距离。
（3）垂直距离 $r$ ： $r=\frac{d(x)}{||W_0||}$
原点到超平面距离： $r_0=\frac{\omega_{n+1}}{||W_0||}$
由 $r_0$ 可知原点在超平面的正负侧由 $\omega_{n+1}$ 决定。
（4）当 X 在超平面的正侧时 d(X) > 0，当 X 在超平面的
负侧时 d(X) < 0

3.4.2 权空间与权向量解

（1）概念
权空间：以 $\omega_1,\omega_2,…,\omega_n,\omega_{n+1}$ 为坐标变量的n+1维欧式空间。
增广权向量： $W=(\omega_1,\omega_2,…,\omega_n,\omega_{n+1})^T$ 对应该空间中的一个点或从原点出发的有向线段。
（2）线性分类
判别函数形式已定，只需确定权向量。
设增广样本向量：
$\omega_1$ 类： $X_{11},X_{12},…,X_{1p}$
$\omega_1$ 类： $X_{21},X_{22},…,X_{2p}$
使用 $d(X)$ 将 $\omega_1$ 和 $\omega_1$ 分开，需满足
$d(X_{1i}>0), i=1,2,…, p$
$d(X_{2i}<0), i=1,2,…, q$
给 $\omega_1$ 的q个增广模式乘以（－1），统一为：
其中 $d(X)>0,X=\begin{cases} X_1i, &i=1,2,…p\\ -X_2i, &i=1,2,…q \end{cases}$
（3）解空间
每个 $d(X)=0$ 都在权空间中确定一个超平面，(p+q) 个训练模式将确定 (p+q) 个界面，每个界面都把权空间分为两个半空间，(p+q) 个正的半子空间的交空间是以权空间原点为顶点的凸多面锥。满足上面各不等式的W 必在该锥体中，即锥中每一点都是上面不等式组的解，解矢量不是唯一的，上述的凸多面锥包含了解的全体，称其为解区、解空间或解锥。