线性判别函数
模式识别系统的主要作用：判别各个模式(样本)所属的类别
用判别函数分类的概念
判别函数进行分类依赖的因素：
- 判别函数的几何性质：线性的和非线性的函数
- 判别函数的系数
两类问题的判别函数
若\(x\)是二维模式样本\(x = (x_1,x_2)^T\)，用\(x_1,x_2\)作为坐标分量，可以画出模式的平面图，若这些分属于\(\omega_1,\omega_2\)两类的模式可以用一个直线方程\(d(x) = 0\)来划分：
\[d(x) = \omega_1x_1 + \omega_2x_2 + \omega_3 = 0 \]其中\(x_1,x_2\)为坐标分量，\(\omega_1,\omega_2,\omega_3\)为参数方程，则将一个不知类别的模式代入\(d(x)\)，有：
\[d(x) \begin{cases} \gt 0 & x \in \omega_1 \\ \lt 0 & x \in \omega_2 \end{cases} \]此时\(d(x) = 0\)称为判别函数。
n维线性判别函数的一般形式
\[d(x) = \omega_1x_1 + \omega_2x_2 + \cdots + \omega_nx_n + \omega_{n + 1} = \omega_0^Tx + \omega_{n+1} \]其中\(\omega_0 = (\omega_1,\omega_2,\cdots,\omega_n)^T\)称为权向量或参数向量，\(x = (x_1,x_2,\cdots,x_n)^T\)，\(d(x)\)还可以表示为：
\[d(x) = \omega^Tx \]其中\(x = (x_1,x_2,\cdots,x_n,1)^T\)称为增广模式向量，\(\omega = (\omega_1,\omega_2,\cdots,\omega_{n+1})^T\)称为增广权向量
- 两类情况判别函数：
- 第一种多类情况：
用线性判别函数将属于\(\omega_i\)类的模式与不属于\(\omega_i\)类的模式分开，其判别函数为：
一个区域明确属于某一类的条件是除了这一类的判别函数的值大于0，其他判别函数的值均小于等于0，否则该区域为不确定区域
- 第二种多类情况：
采用每对划分，即\(\omega_i/\omega_j\)两分法，一个判别界面只能分开两种类别，其判别函数为：
如果\(d_{ij} \gt 0,\forall j \neq i\)，那么\(x \in \omega_i\)；
有一个性质\(d_{ij} = -d_{ji}\);
要分开\(M\)类模式，共需要\(M(M - 1) / 2\)个判别函数；
不确定区域：若所有\(d_{ij}(x)\)，找不到\(\forall j \neq i,d_{ij}(x) \gt 0\)的情况；
- 第三种多类情况：
第二种多类情况的特例，是没有不确定区域的\(\omega_i/\omega_j\)两分法，此时对\(M\)类情况有\(M\)个判别函数
即\(d_i(x) \gt d_j(x),\forall j \neq i,i,j = 1,2,\cdots,M\)那么\(x \in \omega_i\)，将分类的特点是将\(M\)类情况分为\(M - 1\)个两类问题
广义线性判别函数
一个训练用的模式集\(\{x\}\)，在模式集空间\(x\)中线性不可分，但在模式空间\(x^*\)中线性可分，其中\(x^*\)的各个分量是\(x\)的单值实函数，\(x^*\)的维数\(k\)高于\(x\)的维数\(n\)，即若取
\[x^* = (f_1(x),f_2(x),\cdots,f_k(x)),k \gt n \]则分类界面在\(x^*\)中是线性的，在\(x\)中是非线性的，此时只要将模式\(x\)进行非线性变换，使之变换后得到维数更高的模式\(x^*\)，就可以用线性判别函数来进行分类
一个非线性判别函数可如下表示：
其中\(\{f_i(x),i = 1,2,\cdots,k\}\)是模式\(x\)的单值实函数，若定义为广义形式：
\[x^* = (f_1(x),f_2(x),\cdots,f_k(x),1)^T \]此时有：
\[d(x^*) = \omega^Tx^* \]其中\(\omega = (\omega_1,\omega_2,\cdots,\omega_k,\omega_{k + 1})\)
fi(x)选用二次多项式函数
- \(x\)是二维的情况，即\(x = (x_1\ x_2)^T\)，判别函数为：
线性化为\(d(x^*) = \omega^Tx^*\)
\[x^* = (\begin{matrix} x_1^2 & x_1x_2 & x_2^2 & x_1 & x_2 & 1\end{matrix})^T \\ \omega = (\begin{matrix} \omega_{11} & \omega_{12} & \omega_{22} & \omega_1 & \omega_2 & \omega_3\end{matrix})^T \]此时\(x^*\)的维数为5，原维数为2
- \(x\)是\(n\)维的情况，判别函数为：
其中有平方项\(n\)个，二次项\(n(n - 1)/2\)个，一次项\(n\)个，常数项\(1\)个，总项数为：
\[n + n(n + 1) / 2 + n + 1 = (n + 1)(n + 2)/2 \gt n \]\(x^*\)的各分量的一般化形式为：
\[f_i(x) = x_{p_1}^sx_{p_2}^t,p_1,p_2 = 1,2,\cdots,n,s,t = 0,1 \]fi(x)为\(r\)次多项式函数
- \(x\)为\(n\)维模式：
判别函数\(d(x)\)可以用以下递推式给出：
常数项：\(d^{(0)}(x) = \omega_{n + 1}\)
一次项：\(d^{(1)}(x) = \sum_{p_1 = 1}^n\omega_{p_1}x_{p_1} + d^{(0)}(x)\)
二次项：\(d^{(2)}(x) = \sum_{p_1 = 1}^n\sum_{p_2 = p_1}^n\omega_{p_1p_2}x_{p_1}x_{p_2} + d^{(1)}(x)\)
\(r\)次项：\(d^{(r)}(x) = \sum_{p_1 = 1}^n\sum_{p_2 = p_1}^n\cdots\sum_{p_r = p_{r - 1}}^n\omega_{p_1p_2\cdots p_r}x_{p_1}x_{p_2}\cdots x_{p_r} + d^{(r - 1)}(x)\)
\(d(x)\)总项数为：
分段线性判别函数
分段线性判别函数的设计：最小距离分类
设\(\mu_1\)和\(\mu_2\)为两个模式类\(\omega_1\)和\(\omega_2\)的聚类中心，定义决策规则：
这时的决策面是两类期望连线的垂直平分面，这样的分类器称为最小距离分类器
模式空间和权空间
设有判别函数：\(d(x) = \omega^Tx\)，其中\(x = (x_1\ x_2\ \cdots\ \ x_n\ 1)^T,\omega = (\omega_1\ \omega_2\ \cdots\ \omega_n\ \omega_{n + 1})^T\)，判别界面为\(\omega^Tx = 0\)
Fisher线性判别
目的：在低维空间里解析上或计算上行得通的方法，在高维空间里往往行不通，降低维数有时就会成为处理实际问题的关键，考虑将\(d\)维空间的样本投影到一条直线上，形成一维空间，即把维数压缩到一维，我们需要根据实际情况找到一条最易分类的投影线，这就是Fisher判别方法要解决的基本问题
从\(d\)维空间到一维空间的一般数学变换方法：假设有一集合\(\Gamma\)包含\(N\)个\(d\)维样本\(x_1,x_2,\cdots,x_N\)，其中\(N_1\)个属于\(\omega_1\)类的样本记为子集\(\Gamma_1\),\(N_2\)个属于\(\omega_2\)类的样本记为子集\(\Gamma_2\)，若对\(x_n\)的分量做线性组合可得标量：
这样得到\(N\)个一维样本\(y_n\)组成的集合，并可分为两个子集\(\Gamma_1',\Gamma_2'\)，实际上，\(\omega\)的值是无关紧要的，重要的是\(\omega\)的方向，方向直接影响分类效果，我们希望投影以后，在一维\(Y\)空间中各类样本尽可能分得开些，即希望两类均值之差越大越好，同时希望各类样本内部尽量密集，即希望样本类内离散度越小越好
Fisher准则函数中的基本参量
在\(d\)维\(X\)空间
- 各类样本的均值向量\(m_i\)
- 样本类内离散度矩阵\(S_i\)和总样本类内离散度矩阵\(S_\omega\)
- 样本类间离散度矩阵\(S_b\)
\(S_b\)是对称半正定矩阵
在一维\(Y\)空间
- 各类样本的均值
- 样本类内离散度\(\tilde{S}_i^2\)和总样本类内离散度\(\tilde{S}_\omega\)
Fisher准则函数
\[J_F(\omega) = \frac{(\tilde{m}_1 - \tilde{m}_2)^2}{\tilde{S}_1^2 + \tilde{S}_2^2} \]希望两类均值之差越大越好，同时希望各类样本内部尽量密集，即希望样本类内离散度越小越好，所以应该寻找使\(J_F(\omega)\)尽可能大的\(\omega\)作为投影方向，下面需要将\(J_F(\omega)\)变为\(\omega\)的显函数：
首先由各类样本的均值可推出：
这样Fisher准则函数\(J_F(\omega)\)的分子可以写成：
\[\begin{aligned} (\tilde{m}_1 - \tilde{m}_2)^2 &= (\omega^Tm_1 - \omega^Tm_2)^2 \\ &= (\omega^Tm_1 - \omega^Tm_2)(\omega^Tm_1 - \omega^Tm_2)^T \\ &= (\omega^Tm_1 - \omega^Tm_2)(m_1^T\omega - m_2^T\omega) \\ &= \omega^T(m_1 - m_2)(m_1 - m_2)^T\omega = \omega^TS_b\omega \end{aligned} \]再来考察\(J_F(\omega)\)的分母与\(\omega\)的关系：
\[\begin{aligned} \tilde{S}_i^2 &= \sum_{y \in \Gamma_i'}(y - \tilde{m}_i)^2 \\ &= \sum_{x \in \Gamma_i}(\omega^Tx - \omega^Tm_i)^2 \\ &= \omega^T\left[\sum_{x \in \Gamma_i}(x - m_i)(x - m_i)^T\right]\omega \\ &= \omega^TS_i\omega \end{aligned} \]因此：
\[\tilde{S}_1^2 + \tilde{S}_2^2 = \omega^T(S_1 + S_2)\omega = \omega^TS_\omega\omega \]带到\(J_F(\omega)\)
\[J_F(\omega) = \frac{\omega^TS_b\omega}{\omega^TS_\omega\omega} \]最佳变换向量\(\omega^*\)的求取
首先使分母为非零常数：
\[\omega^TS_\omega\omega = c \neq 0 \]定义拉格朗日函数为：
\[L(\omega,\lambda) = \omega^TS_b\omega - \lambda(\omega^TS_\omega\omega) \]上式对\(\omega\)求偏导数：
\[\frac{\partial L(\omega,\lambda)}{\partial \omega} = 2(S_b\omega - \lambda S_\omega\omega) \]令偏导数为0：
\[S_b\omega^* - \lambda S_\omega\omega^* = 0 \]也就是：
\[S_b\omega^* = \lambda S_\omega\omega^* \]因为\(S_\omega\)非奇异，将上式两边左乘\(S_\omega^{-1}\):
\[S_\omega^{-1}S_b\omega^* = \lambda\omega^* \]上式为求一般矩阵\(S_\omega^{-1}S_b\)的特征值问题，\(S_b = (m_1 - m_2)(m_1 - m_2)^T\)
\[S_b\omega^* = (m_1 - m_2)(m_1 - m_2)^T\omega^* = (m_1 - m_2)R \]其中\(R = (m_1 - m_2)^T\omega^*\)是一个标量，所以\(S_b\omega^*\)总是在向量\((m_1 - m_2)\)的方向上，因此：
\[\lambda\omega^* = S_\omega^{-1}(S_b\omega^*) = S^{-1}_\omega(m_1 - m_2)R \]得到：
\[\omega^* = \frac{R}{\lambda}S^{-1}_\omega(m_1 - m_2) \]省略比例因子\(\frac{R}{\lambda}\)有：
\[\omega^* = S^{-1}_\omega(m_1 - m_2) \] 标签：lecture3,模式识别,sum,判别函数,cdots,tilde,omega,Gamma From： https://www.cnblogs.com/eryoyo/p/16726639.html