深度学习知识点汇总-机器学习基础（8）

2.8 LDA的算法原理和算法步骤

输入：数据集 $D={(\boldsymbol x_1,\boldsymbol y_1),(\boldsymbol x_2,\boldsymbol y_2),...,(\boldsymbol x_m,\boldsymbol y_m)}$ ，其中样本 $\boldsymbol x_i$ 是 $n$ 维向量， $\boldsymbol y_i \in {0, 1}$ ，降维后的目标维度 $d$ 。

定义以下符号:

$N_j(j=0,1)$ 为第 $j$ 类样本个数；
$X_j(j=0,1)$ 为第 $j$ 类样本的集合；
$u_j(j=0,1)$ 为第 $j$ 类样本的均值向量；
$\boldsymbol \sigma_j(j=0,1)$ 为第 $j$ 类样本的协方差矩阵。

其中
$u_j = \frac{1}{N_j} \sum_{\boldsymbol x\epsilon X_j}\boldsymbol x \\ \boldsymbol \sigma_j = \sum_{\boldsymbol x\epsilon X_j}(\boldsymbol x-u_j)(\boldsymbol x-u_j)^T$

假设投影直线是向量 $\boldsymbol w$ ，对任意样本 $\boldsymbol x_i$ ，它在直线 $w$ 上的投影为 $\boldsymbol w^T x_i$ ，两个类别的中心点 $u_0$ , $u_1$ 在直线 $w$ 的投影分别为 $\boldsymbol w^Tu_0$ 、 $\boldsymbol w^Tu_1$ 。

LDA的目标

类间距离尽量大。两类别的数据中心间的距离 $| \boldsymbol w^Tu_0 - \boldsymbol w^Tu_1 |^2_2$ 尽量大
类内距离尽量小。同类样本投影点的协方差 $\boldsymbol w^T \boldsymbol \sigma_0 \boldsymbol w$ 、 $\boldsymbol w^T \boldsymbol \sigma_1 \boldsymbol w$ 尽量小。

定义类内散度矩阵
$S_w = \boldsymbol \sigma_0 + \boldsymbol \sigma_1 = \sum_{\boldsymbol x\epsilon X_0}(\boldsymbol x-u_0)(\boldsymbol x-u_0)^T + \sum_{\boldsymbol x\epsilon X_1}(\boldsymbol x-u_1)(\boldsymbol x-u_1)^T$

类间散度矩阵 $S_b = (u_0 - u_1)(u_0 - u_1)^T$

据上分析，优化目标为
$\mathop{\arg\max}_\boldsymbol w J(\boldsymbol w) = \frac{| \boldsymbol w^Tu_0 - \boldsymbol w^Tu_1 |^2_2}{\boldsymbol w^T \boldsymbol \sigma_0\boldsymbol w + \boldsymbol w^T \boldsymbol \sigma_1\boldsymbol w} = \frac{\boldsymbol w^T(u_0-u_1)(u_0-u_1)^T\boldsymbol w}{\boldsymbol w^T(\boldsymbol \sigma_0 + \boldsymbol \sigma_1)\boldsymbol w} = \frac{\boldsymbol w^TS_b\boldsymbol w}{\boldsymbol w^TS_w\boldsymbol w}$

根据广义瑞利商的性质，矩阵 $S^{-1}_{w} S_b$ 的最大特征值为 $J(\boldsymbol w)$ 的最大值，矩阵 $S^{-1}_{w} S_b$ 的最大特征值对应的特征向量即为 $\boldsymbol w$ 。

LDA算法降维流程如下：
输入：数据集 $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$ 。

输出：降维后的数据集 $\overline{D}$ 。

步骤：

计算类内散度矩阵 $S_w$ 。
计算类间散度矩阵 $S_b$ 。
计算矩阵 $S^{-1}_wS_b$ 。
计算矩阵 $S^{-1}_wS_b$ 的最大的 $d$ 个特征值。
计算 $d$ 个特征值对应的 $d$ 个特征向量，记投影矩阵为 $W$ 。
转化样本集的每个样本，得到新样本 $P_i = W^Tx_i$ 。
输出新样本集 $\overline{D} = { (p_1,y_1),(p_2,y_2),...,(p_m,y_m) }$

LDA是个二分类的降维方法。

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 213,047评论 6赞 492
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 90,807评论 3赞 386
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 158,501评论 0赞 348
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 56,839评论 1赞 285
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 65,951评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 50,117评论 1赞 291
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,188评论 3赞 412
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,929评论 0赞 268
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,372评论 1赞 303
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,679评论 2赞 327
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,837评论 1赞 341
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,536评论 4赞 335
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,168评论 3赞 317
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,886评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,129评论 1赞 267
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 46,665评论 2赞 362
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 43,739评论 2赞 351

深度学习知识点汇总-机器学习基础（8）

2.8 LDA的算法原理和算法步骤

推荐阅读更多精彩内容