线性判别分析(LDA)

设二分类样本S03P02-线性判别分析 - 图1%5C%7D%7Bi%3D1%7D%5EN%2CX_i%5Cin%5Cmathbb%7BR%7D%5Ep%2Cy_i%5Cin%5C%7B-1%2C%2B1%5C%7D#card=math&code=D%3D%5C%7B%28X_i%2Cy_i%29%5C%7D%7Bi%3D1%7D%5EN%2CX_i%5Cin%5Cmathbb%7BR%7D%5Ep%2Cy_i%5Cin%5C%7B-1%2C%2B1%5C%7D)

S03P02-线性判别分析 - 图2

设S03P02-线性判别分析 - 图3为正类样本的集合，S03P02-线性判别分析 - 图4为负类样本的集合，S03P02-线性判别分析 - 图5

基本思想

对于二分类的问题，在高维空间中直接找样本的分界比较困难，因此考虑将高维的数据点降维，映射到一条一维的直线上，在直线上可以很容易的找到一个threshold来区分不同类别。但是映射的过程会遇到一些问题，以二维为例如图
S03P02-线性判别分析 - 图6
可以映射的直线有很多，比如图中的S03P02-线性判别分析 - 图7。但是很明显将样本映射到S03P02-线性判别分析 - 图8并不能很好的区分两类，但是将样本映射到S03P02-线性判别分析 - 图9可以达到很好的效果

构造目标函数

要想办法解决上述问题。我们从图中可看到，对于效果更好的S03P02-线性判别分析 - 图10，同一类的样本点在其上投影点分布密集，但是不同类别在其上投影点分散得很开。于是我们对于这条映射直线的要求即：类内的度量小，类间的度量大
一般地，设映射的直线为S03P02-线性判别分析 - 图11，我们先定义一些量

  1. 投影前的量

    • 正样本的均值S03P02-线性判别分析 - 图12，负样本的均值S03P02-线性判别分析 - 图13
    • 正负样本的协方差矩阵分别为S03P02-线性判别分析 - 图14

  2. 投影后的量

    • 样本S03P02-线性判别分析 - 图15在直线S03P02-线性判别分析 - 图16上的投影为S03P02-线性判别分析 - 图17
    • 所有样本的投影均值为

S03P02-线性判别分析 - 图18

  • 正负样本点的投影均值分别为

S03P02-线性判别分析 - 图19

类内度量

我们可以用样本点映射到直线后类内投影点的方差作为类内度量

  • 对于正类和负类分别有

S03P02-线性判别分析 - 图20%5E2%7D%7BN1%7D%3D%5Cfrac%7B%5Csum%5Climits%7Bi%3D1%7D%5E%7BN1%7D(%5Cmu_i-%5Cmu%2B)(%5Cmui-%5Cmu%2B)%5ET%7D%7BN1%7D%5C%5C%0A%26%3D%7B1%5Cover%20N_1%7D%5Csum%7Bi%3D1%7D%5E%7BN1%7D%5Cleft(W%5ETX_i-%7B1%5Cover%20N_1%7D%5Csum%7Bj%3D1%7D%5E%7BN1%7DW%5ETX_j%5Cright)%5Cleft(W%5ETX_i-%7B1%5Cover%20N_1%7D%5Csum%7Bj%3D1%7D%5E%7BN1%7DW%5ETX_j%5Cright)%5ET%5C%5C%0A%26%3D%7B1%5Cover%20N_1%7D%5Csum%7Bi%3D1%7D%5E%7BN1%7D%5Cleft%5BW%5ET%5Cleft(X_i-%7B1%5Cover%20N_1%7D%5Csum%7Bj%3D1%7D%5E%7BN1%7DX_j%5Cright)%5Cright%5D%5Cleft%5BW%5ET%5Cleft(X_i-%7B1%5Cover%20N_1%7D%5Csum%7Bj%3D1%7D%5E%7BN1%7DX_j%5Cright)%5Cright%5D%5ET%5C%5C%0A%26%3D%7B1%5Cover%20N_1%7D%5Csum%7Bi%3D1%7D%5E%7BN1%7DW%5ET(X_i-%5Coverline%7BX%2B%7D)(Xi-%5Coverline%7BX%2B%7D)%5ETW%5C%5C%0A%26%3DW%5ET%5Cleft%5B%7B1%5Cover%20N1%7D%5Csum%7Bi%3D1%7D%5E%7BN1%7D(X_i-%5Coverline%7BX%2B%7D)(Xi-%5Coverline%7BX%2B%7D)%5ET%5Cright%5DW%5C%5C%0A%26%3DW%5ET%5CSigma%2BW%5C%5C%0A%5C%5C%0AS-%26%3DW%5ET%5CSigma-W%0A%5Cend%7Baligned%7D%0A#card=math&code=%5Cbegin%7Baligned%7D%0AS%2B%26%3D%5Cfrac%7B%5Csum%5Climits%7Bi%3D1%7D%5E%7BN_1%7D%28%5Cmu_i-%5Cmu%2B%29%5E2%7D%7BN1%7D%3D%5Cfrac%7B%5Csum%5Climits%7Bi%3D1%7D%5E%7BN1%7D%28%5Cmu_i-%5Cmu%2B%29%28%5Cmui-%5Cmu%2B%29%5ET%7D%7BN1%7D%5C%5C%0A%26%3D%7B1%5Cover%20N_1%7D%5Csum%7Bi%3D1%7D%5E%7BN1%7D%5Cleft%28W%5ETX_i-%7B1%5Cover%20N_1%7D%5Csum%7Bj%3D1%7D%5E%7BN1%7DW%5ETX_j%5Cright%29%5Cleft%28W%5ETX_i-%7B1%5Cover%20N_1%7D%5Csum%7Bj%3D1%7D%5E%7BN1%7DW%5ETX_j%5Cright%29%5ET%5C%5C%0A%26%3D%7B1%5Cover%20N_1%7D%5Csum%7Bi%3D1%7D%5E%7BN1%7D%5Cleft%5BW%5ET%5Cleft%28X_i-%7B1%5Cover%20N_1%7D%5Csum%7Bj%3D1%7D%5E%7BN1%7DX_j%5Cright%29%5Cright%5D%5Cleft%5BW%5ET%5Cleft%28X_i-%7B1%5Cover%20N_1%7D%5Csum%7Bj%3D1%7D%5E%7BN1%7DX_j%5Cright%29%5Cright%5D%5ET%5C%5C%0A%26%3D%7B1%5Cover%20N_1%7D%5Csum%7Bi%3D1%7D%5E%7BN1%7DW%5ET%28X_i-%5Coverline%7BX%2B%7D%29%28Xi-%5Coverline%7BX%2B%7D%29%5ETW%5C%5C%0A%26%3DW%5ET%5Cleft%5B%7B1%5Cover%20N1%7D%5Csum%7Bi%3D1%7D%5E%7BN1%7D%28X_i-%5Coverline%7BX%2B%7D%29%28Xi-%5Coverline%7BX%2B%7D%29%5ET%5Cright%5DW%5C%5C%0A%26%3DW%5ET%5CSigma%2BW%5C%5C%0A%5C%5C%0AS-%26%3DW%5ET%5CSigma_-W%0A%5Cend%7Baligned%7D%0A)

则总体的类内度量为

S03P02-线性判别分析 - 图21W%0A%5Cend%7Baligned%7D%0A#card=math&code=%5Cbegin%7Baligned%7D%0AS%26%3DS%2B%2BS-%5C%5C%0A%26%3DW%5ET%28%5CSigma%2B%2B%5CSigma-%29W%0A%5Cend%7Baligned%7D%0A)

类间度量

我们可以用样本点映射到直线后正类的投影均值与负类投影均值间的距离作为类间度量

S03P02-线性判别分析 - 图22%5E2%5C%5C%0A%26%3D%5Cleft(%5Cfrac%7B%5Csum%7Bi%3D1%7D%5E%7BN_1%7DW%5ETX_i%7D%7BN_1%7D-%5Cfrac%7B%5Csum%7Bi%3D1%7D%5E%7BN2%7DW%5ETX_i%7D%7BN_2%7D%5Cright)%5E2%5C%5C%0A%26%3D%5BW%5ET(%5Coverline%7BX%2B%7D-%5Coverline%7BX-%7D)%5D%5E2%5C%5C%0A%26%3DW%5ET(%5Coverline%7BX%2B%7D-%5Coverline%7BX-%7D)(%5Coverline%7BX%2B%7D-%5Coverline%7BX-%7D)%5ETW%0A%5Cend%7Baligned%7D%0A#card=math&code=%5Cbegin%7Baligned%7D%0Ad%5E2%26%3D%7C%7C%5Cmu%2B-%5Cmu-%7C%7C%5E2%3D%28%5Cmu%2B-%5Cmu-%29%5E2%5C%5C%0A%26%3D%5Cleft%28%5Cfrac%7B%5Csum%7Bi%3D1%7D%5E%7BN1%7DW%5ETX_i%7D%7BN_1%7D-%5Cfrac%7B%5Csum%7Bi%3D1%7D%5E%7BN2%7DW%5ETX_i%7D%7BN_2%7D%5Cright%29%5E2%5C%5C%0A%26%3D%5BW%5ET%28%5Coverline%7BX%2B%7D-%5Coverline%7BX-%7D%29%5D%5E2%5C%5C%0A%26%3DW%5ET%28%5Coverline%7BX%2B%7D-%5Coverline%7BX-%7D%29%28%5Coverline%7BX%2B%7D-%5Coverline%7BX_-%7D%29%5ETW%0A%5Cend%7Baligned%7D%0A)

目标函数

我们的目的是类间距离尽量大而类内的距离尽量小，那么根据类内度量和类间度量即可构造一个目标函数

S03P02-线性判别分析 - 图23%3D%5Cfrac%7BW%5ET(%5Coverline%7BX%2B%7D-%5Coverline%7BX-%7D)(%5Coverline%7BX%2B%7D-%5Coverline%7BX-%7D)%5ETW%7D%7BW%5ET(%5CSigma%2B%2B%5CSigma-)W%7D%0A#card=math&code=J%28W%29%3D%5Cfrac%7BW%5ET%28%5Coverline%7BX%2B%7D-%5Coverline%7BX-%7D%29%28%5Coverline%7BX%2B%7D-%5Coverline%7BX-%7D%29%5ETW%7D%7BW%5ET%28%5CSigma%2B%2B%5CSigma-%29W%7D%0A)

求解方法

令S03P02-线性判别分析 - 图24，称为类内散度矩阵(within-class scatter matrix)
令S03P02-线性判别分析 - 图25(%5Coverline%7BX%2B%7D-%5Coverline%7BX-%7D)%5ET#card=math&code=Sb%3D%28%5Coverline%7BX%2B%7D-%5Coverline%7BX-%7D%29%28%5Coverline%7BX%2B%7D-%5Coverline%7BX_-%7D%29%5ET)，称为类间散度矩阵(between-class scatter matrix)
则有

S03P02-线性判别分析 - 图26%3D%5Cfrac%7BW%5ETS_bW%7D%7BW%5ETS_wW%7D%3D(W%5ETS_bW)(W%5ETS_wW)%5E%7B-1%7D%5C%5C%0A%5Cfrac%7B%5Cpartial%20J(W)%7D%7B%5Cpartial%20W%7D%3D2S_bW(W%5ETS_wW)%5E%7B-1%7D%2B(W%5ETS_bW)%5B-2(W%5ETS_wW)%5E%7B-2%7DS_wW%5D%3D0%5C%5C%0A%5CRightarrow%20S_bW(W%5ETS_wW)-(W%5ETS_bW)S_wW%3D0%5C%5C%0A%5CRightarrow%20S_wW%3D%5Cfrac%7BW%5ETS_wW%7D%7BW%5ETS_bW%7DS_bW%5C%5C%0A%5CRightarrow%20W%3D%5Cfrac%7BW%5ETS_wW%7D%7BW%5ETS_bW%7DS_w%5E%7B-1%7DS_bW%0A%5Cend%7Bgathered%7D%0A#card=math&code=%5Cbegin%7Bgathered%7D%0AJ%28W%29%3D%5Cfrac%7BW%5ETS_bW%7D%7BW%5ETS_wW%7D%3D%28W%5ETS_bW%29%28W%5ETS_wW%29%5E%7B-1%7D%5C%5C%0A%5Cfrac%7B%5Cpartial%20J%28W%29%7D%7B%5Cpartial%20W%7D%3D2S_bW%28W%5ETS_wW%29%5E%7B-1%7D%2B%28W%5ETS_bW%29%5B-2%28W%5ETS_wW%29%5E%7B-2%7DS_wW%5D%3D0%5C%5C%0A%5CRightarrow%20S_bW%28W%5ETS_wW%29-%28W%5ETS_bW%29S_wW%3D0%5C%5C%0A%5CRightarrow%20S_wW%3D%5Cfrac%7BW%5ETS_wW%7D%7BW%5ETS_bW%7DS_bW%5C%5C%0A%5CRightarrow%20W%3D%5Cfrac%7BW%5ETS_wW%7D%7BW%5ETS_bW%7DS_w%5E%7B-1%7DS_bW%0A%5Cend%7Bgathered%7D%0A)

因为确定这条直线只需要确定法向量的方向即S03P02-线性判别分析 - 图27的方向即可，因此不需要确定S03P02-线性判别分析 - 图28长度，那么可以用如下方法求解

S03P02-线性判别分析 - 图29(%5Coverline%7BX%2B%7D-%5Coverline%7BX-%7D)%5ETW%5C%5C%0A%26%5Cpropto%20Sw%5E%7B-1%7D(%5Coverline%7BX%2B%7D-%5Coverline%7BX-%7D)%0A%5Cend%7Baligned%7D%5C%5C%0A%5CRightarrow%20W%3DS_w%5E%7B-1%7D(%5Coverline%7BX%2B%7D-%5Coverline%7BX-%7D)%0A%5Cend%7Bgathered%7D%0A#card=math&code=%5Cbegin%7Bgathered%7D%0A%5Cbegin%7Baligned%7D%0AW%26%5Cpropto%20S_w%5E%7B-1%7DS_bW%5C%5C%0A%26%5Cpropto%20S_w%5E%7B-1%7D%28%5Coverline%7BX%2B%7D-%5Coverline%7BX-%7D%29%28%5Coverline%7BX%2B%7D-%5Coverline%7BX-%7D%29%5ETW%5C%5C%0A%26%5Cpropto%20S_w%5E%7B-1%7D%28%5Coverline%7BX%2B%7D-%5Coverline%7BX-%7D%29%0A%5Cend%7Baligned%7D%5C%5C%0A%5CRightarrow%20W%3DS_w%5E%7B-1%7D%28%5Coverline%7BX%2B%7D-%5Coverline%7BX_-%7D%29%0A%5Cend%7Bgathered%7D%0A)