⌛️本文状态:已完结✔️
注:1. 编写实验的代码只需看3.3的求解结果即可。 2. 理解算法理论时,注意区分“投影向量的方向”和“投影的方向”。
本博中线性判别都以二分类问题为例。多分类问题都可以通过以下三种方法转化为二分类问题。
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称为类内总离散度矩阵。
(因为J_F(w)有上界,因此最佳投影方向一定存在)
无约束最优化:$\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. $$
使用Lagrange乘子法求解,结果为,
其中
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。
$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准则函数达到极值点。
使用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