模式识别从0构建—Fisher线性判别
本博中线性判别都以二分类问题为例。多分类问题都可以通过以下三种方法转化为二分类问题。
- 一对多：每一类与其他类之间可用一个判别平面把一个类分开，这种情况，M类可有M个判别函数。这种方法的缺点是：有比较大的模糊地带、面临数据不均衡问题。
- 两两分类：每一类和其他类之间可分别用判别平面分开。这种情况，M类会有M(M-1)/2个判别平面。
- 最大值法：每类都有一个判别函数，将样本代入每个判别函数，判别函数最大的那个类别为样本所属类别。M类有M个判别函数。
注：编写实验的代码只需看3.3的求解结果即可。理解算法理论时，注意区分“投影向量的方向”和“投影的方向”。
一、基本思想
Fisher线性判别是把线性分类器的设计分为两步，一是确定最优的方向，二是在这个方向上确定分类阈值。
——from 《模式识别（第三版）》P66
Fisher判别问题就可以看作是把所有样本都投影到一个方向上，然后在这个一维空间中确定一个分类的阈值。而通过这个阈值点且与投影向量的方向垂直的超平面就是两类的分类面。（参考自：微信公众号Mine2me）
希望投影后的数据满足：
- 两类之间的距离尽可能远
- 每一类自身尽可能紧凑
用数学（数据的统计性质）来表达就是，投影后两类均值的差要大（分子），两类的类内离散度之和要小（分母）。即，
$$
\begin{eqnarray}
J_F(w)&=&\frac{(\mu_1-\mu_2)^2}{\sigma_1^2+\sigma_2^2}\\
w_{opt}&=&\arg\max J_F(w)
\end{eqnarray}
$$
其中，
$$
\begin{eqnarray}
\mu_i&=&w^Tm_i\\
\sigma^2_i&=&\sum(w^Tx-\mu_i)^2\\
&=&w^T\sum(x-m_i)(x-m_i)^Tw\\
&=&w^TS_iw
\end{eqnarray}
$$
其中 $m_i=\frac{1}{N}\sum{x},i=1,2$ 叫做 均值向量；$S_i=\sum((x-m_i)(x-m_i)^T) ,i=1,2$叫做 离散度矩阵。（离散度矩阵在形式上与协方差矩阵很相似，但协方差矩阵 $E(\frac{1}{n}\sum_{i=1}^{n}(x_i-\bar{x})(x_i-\bar{x})^T)$ 是一种总体期望值，而离散度矩阵只是表示有限个样本在空间分布的离散程度。）
二、推导和化简
$$
\begin{eqnarray}
J_F(w)&=&\frac{(\mu_1-\mu_2)^2}{\sigma_1^2+\sigma_2^2}\\
&=&\frac{(w^Tm_1-w^Tm_2)^2}{w^TS_1w+w^TS_2w}\\
&=&\frac{w^T(m_1-m_2)(m_1-m_2)^Tw}{w^T(S_1+S_2)w}\\
&=&\frac{w^TS_bw}{w^TS_ww}
\end{eqnarray}
$$
其中，
$S_b=(m_1-m_2)(m_1-m_2)^T$称为类间离散度矩阵；
$S_w=S_1+S_2$称为类内总离散度矩阵。
三、求解
3.1 求解要求：
- 类内总离散度矩阵$S_w$正定，即样本数>维数。
- 类内总离散度矩阵$S_w$可逆
（因为$J_F(w)$有上界，因此最佳投影方向一定存在）
3.2 求解目标：
无约束最优化：$\max{\dfrac{w^TS_bw}{w^TS_ww}}$ ，
等价于带约束的最优化，
$$
\left\{\begin{array}{cc}\max{w^TS_bw}\\
s.t.\ w^TS_ww=1
\end{array}\right.
$$
3.3 求解结果：
使用Lagrange乘子法求解，结果为，
$$
w_{opt}=\frac{c}{\lambda}S_w^{-1}(m_1-m_2)
$$
其中$\frac{c}{\lambda}$可以忽略，因为我们只考虑投影向量的方向而不考虑大小。
$S_w=S_1+S_2$，$S_i=\sum((x-m_i)(x-m_i)^T) ,i=1,2$；
$m_i=\frac{1}{N}\sum{x},i=1,2$；
投影后，以投影向量的方向为坐标轴，投影向量的模为单位长度，数据的均值（$n_1,n_2$是两类样本的个数）
$b=\dfrac{n_1\mu_1+n_2\mu_2}{n_1+n_2}，其中\mu_i=w^Tm_i$
直角坐标系中，决策面方程为：$w_{opt}^Tx-b=0$。
3.4 对结果的理解：
$w_{opt}=S_w^{-1}(m_1-m_2)$；$m_1-m_2$是一向量，对与$(m_1-m_2)$平行的投影向量可使两均值点的距离最远。
但是如果从使类间分得较开，同时又使类内密集程度较高这样一个综合指标来看，则需根据两类样本的分布离散程度对投影方向作相应的调整，
这就体现在对$m_1-m_2$向量按$S_w^{-1}$作一线性变换，从而使Fisher准则函数达到极值点。
四、MATLAB实验
使用fisher线性判别器完成了对两类样本的分类，蓝线为决策面，蓝线代表的方向为投影方向。红线为样本点投影到的直线。
算法的关键代码如下：
% p1为类别1的样本，p2为类别2的样本
m1 = mean(p1,2);
m2 = mean(p2,2);
S1 = (p1-m1)*(p1-m1)';
S2 = (p2-m2)*(p2-m2)';
Sw = S1 + S2;
w_opt = inv(Sw)*(m1-m2);
b = w_opt'*(m1+m2)/2; % 至此，求出最佳投影方向
%--------------------------------------
% GIRLdatatest为待测点
y_dot = zeros(length(GIRLdatatest),1);
for i=1:length(GIRLdatatest)
y_dot(i,1) = w_opt' * GIRLdatatest(i,1:2)';
if(y_dot(i,1)>b)
GIRLdatatest(i,3)=1;
else
GIRLdatatest(i,3)=0;
end
end % 完成分类
%-----------------------------------------
x1 = linspace(fmin,fmax,100)';
n = size(x1,1);
X1 = zeros(n,1);
tX1 = zeros(n,1);
syms x2 y1 y2;
for i=1:n
x=[x1(i,1);x2];
y1 = w_opt' * x - b; %求决策面
t_wopt = [w_opt(2);-w_opt(1)];
y2 = t_wopt' * x; %求投影到的直线
a1 = solve(y1,x2);
a2 = solve(y2,x2);
if size(a1,1)~=0
X1(i,1)=a1(1,1);
end
if size(a2,1)~=0
tX1(i,1)=a2(1,1);
end
end % 求决策面和投影直线完整实验代码已上传到Github
