降维算法2_LDA

LDA(线性判别分析)基本原理

LDA思想

LDA是监督学习的降维、分类技术,可以用一句话概括思想:投影后类内方差最小,类间方差最大。

如下图所示,给定数据样例集,设法将样例投影到直线上,使得同类样例投影点尽可能近、异类样例的投影点尽可能远离:


图 1. LDA 二维示意图

下图的两种投影方式,那一种满足我们的标准?

图 2. 两种不同的投影方式  

右图,原因是投影后,蓝色和红色数据各自较为集中,且类别之间的距离明显。(左图在边界处数据混杂

LDA如何用来分类?

在对新的样本进行分类时,将其投影到同样的投影线上,再根据投影点的位置来确定样本的类别。

LDA原理及流程



对于具体数据的实例

目标:求解投影向量\mathbf{w}​ ,二维情况下​\mathbf{w}=\begin{pmatrix}w_{11}\\w_{12}\end{pmatrix}\mathbf{X}=\begin{pmatrix}x_{11}&x_{21}&...&x_{m1}\\x_{12}&x_{22}&...&x_{m2}\end{pmatrix}

X​,shape:(2,m)表示样本矩阵,即2个维度,m个样本。每一列表示一个样本,每一行表示该样本在这一维度上的取值。例如:\mathbf{x}​中的第一列表示第一个样本在第一个维度上的取值​,在第二个维度上的取值为​,以此类推。

对第​个样本\mathbf{x}​:​\mathbf{x}=\begin{pmatrix}x_{i1}\\x_{i2} \end{pmatrix}

图中的y可计算,对于样本在投影向量上的投影结果的值为:y=\mathbf{w}^T\mathbf{x}=|\mathbf{w}|*|\mathbf{x}|*cos(\theta)=|\mathbf{x}|*cos(\theta)​,​\mathbf{w}可以理解为这条过原点直线的单位方向向量,​\theta\mathbf{w、x}的夹角。

给定两个类别:

X1 : shape:(m,2)一般将样本按行排列,每列表示维度,可以理解为\mathbf{x}​的转置,表示m个样本,2两个维度,图中每个点表示

X2 :    描述同X1

均值向量\mu_i​: shape:(2,1) 将m个样本取每个维度的均值,按列排列,得到均值均值向量​ \mu_i

协方差矩阵\sum_i​: \frac{1}{m-1}X_i^TX_i​ shape:(2,2) (维度x维度)

样本中心在直线上的投影\mathbf{w}^T\mu_i​ :shape:(1,2)x(2,1)= (1,1)常量

同类样本投影点的协方差:\mathbf{w}^T\sum_i\mathbf{w}​:shape:(1,2)x(2,2)x(2,1) = (1,1)常量 ,表示将同类样本投影后,两个维度的协方差。

对于n维情况,由于我们是多维向低维投影,则此时投影到的低维空间就不是一条直线,而是一个超平面了。假设我们投影到的低维空间的维度为d,对应的基向量为(w_1,w_2,...,w_d)​,基向量组成的矩阵为​\mathbf{w}_{(n,d)}

此时同类样本投影点的协方差\mathbf{w}^T\sum_i\mathbf{w} ​  shape: (d,n)x(n,n)x(n,d)=(d,d) ,表示投影后dxd的协方差矩阵。

程序

算法流程总结

输入:数据集D={\{(x_1,y_1),(x_2,y_2),...,(x_m,y_m)\}},​,其中任意样本​x_i为n维向量,​y_i\in{\{C_1,C_2,...,C_k\}}为样本对应的标签,降维到的维度d。

输出:降维后的样本集​D^`

1) 计算类内散度矩阵​S_w

2) 计算类间散度矩阵​S_b

3) 计算矩阵​S_w^-S_b

4) 计算​的S_w^-S_b最大的​d个特征值对应的​个特征向量(w_1,w_2,...,w_d)​,得到投影矩阵​W

5) 对样本集中的每一个样本特征x_i​,转换为新的样本​z_i=W^Tx_i

6) 得到输出样本集​D^`={\{(z_1,y_1),(z_2,y_2),...,(z_m,y_m)\}}

实际上LDA除了可以用于降维以外,还可以用于分类。一个常见的LDA分类基本思想是假设各个类别的样本数据符合高斯分布,这样利用LDA进行投影后,可以利用极大似然估计计算各个类别投影数据的均值和方差,进而得到该类别高斯分布的概率密度函数。当一个新的样本到来后,我们可以将它投影,然后将投影后的样本特征分别带入各个类别的高斯分布概率密度函数,计算它属于这个类别的概率,最大的概率对应的类别即为预测类别

PCA、LDA区别

相同点:

1)两者均可以对数据进行降维。

2)两者在降维时均使用了矩阵特征分解的思想。

3)两者都假设数据符合高斯分布

不同点

1.LDA是有监督的降维方法,而PCA是无监督的降维方法n

2.LDA降维最多降到类别数k-1的维数,而PCA没有这个限制。

3.LDA除了可以用于降维,还可以用于分类。

4.LDA选择分类性能最好的投影方向,而PCA选择样本点投影具有最大方差的方向。这点可以从下图形象的看出,在某些数据分布下LDA比PCA降维较优。


当然,某些某些数据分布下PCA比LDA降维较优,如下图所示:

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 215,539评论 6 497
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,911评论 3 391
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 161,337评论 0 351
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,723评论 1 290
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,795评论 6 388
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,762评论 1 294
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,742评论 3 416
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,508评论 0 271
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,954评论 1 308
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,247评论 2 331
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,404评论 1 345
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,104评论 5 340
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,736评论 3 324
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,352评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,557评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,371评论 2 368
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,292评论 2 352