机器学习-特征选择(降维) 线性判别式分析(LDA)

标签: 机器学习 特征选择 降维 | 发表时间:2013-01-27 19:50 | 作者:Kemaswill
出处:http://www.cnblogs.com/

  特征选择(亦即降维)是数据预处理中非常重要的一个步骤。对于分类来说,特征选择可以从众多的特征中选择对分类最重要的那些特征,去除原数据中的噪音。主成分分析(PCA)与线性判别式分析(LDA)是两种最常用的特征选择算法。关于PCA的介绍,可以见我的 另一篇博文。这里主要介绍线性判别式分析(LDA),主要基于Fisher Discriminant Analysis with Kernals[1]和Fisher Linear Discriminant Analysis[2]两篇文献。

  LDA与PCA的一大不同点在于,LDA是有监督的算法,而PCA是无监督的,因为PCA算法没有考虑数据的标签(类别),只是把原数据映射到一些方差比较大的方向(基)上去而已。而LDA算法则考虑了数据的标签。文献[2]中举了一个非常形象的例子,说明了在有些情况下,PCA算法的性能很差,如下图:                                   

 我们用不同的颜色标注C1,C2两个不同类别的数据。根据PCA算法,数据应该映射到方差最大的那个方向,亦即Y轴方向,但是如果映射到Y轴方向,C1,C2两个不同类别的数据将完全混合在一起,很难区分开,所以使用PCA算法进行降维后再进行分类的效果会非常差。但是使用LDA算法,数据会映射到X轴方向。

  LDA算法会考虑到数据的类别属性,给定两个类别C1、C2,我们希望找到一个向量ω,当数据映射到ω的方向上时,来自两个类的数据尽可能的分开,同一个类内的数据尽可能的紧凑。数据的映射公式为:z=ω Tx,  其中z是数据x到ω上的投影,因而也是一个d维到1维的维度归约。

  令 m 1和m 1分别表示C1类数据投影之前个投影之后的均值,易知m 1T m 1,同理m 2T m 2

  令s 1 2和s 2 2分别表示C1和C2类数据在投影之后的散布(scatter),亦即s 1 2=∑(ω Tx t-m1) 2r t,s 2 2=∑(ω Tx t-m2) 2(1-r t)其中如果x t∈C1,则r t=1,否则r t=0。

  我们希望|m 1-m 2|尽可能的大,而s 1 2+s 2 2尽可能的小, Fisher线性判别式就是最大化下面式子的ω:

  J(ω)=(m 1-m 2) 2/(s 1 2+s 2 2)     式子-1

  改写式子-1中的分子:  (m 1-m 2) 2=  (ω T m 1T m 2) 2T( m 1- m 2)( m 1- m 2) Tω=ω T S Bω

  其中 S B=( m 1- m 2)( m 1- m 2) T    式子-2

  是 类间散布矩阵(between class scatter matrix)。

  改写式子-1中的分母:

  ∑(ω Tx t-m1) 2r t=∑ω T(x t- m 1)(x t- m 1) Tωr tT S 1ω, 其中 S 1=∑r t(x t- m 1)(x t- m 1) T是C1的 类内散布矩阵(within class scatter matrix)。

  令 S W= S 1+ S 2,是 类内散布的总和,则s 1 2+s 2 2T S Wω。

  所以式子-1可以改写为:

  J(ω)=(ω T S Bω)/(ω T S Wω)    式子-3

  我们只需要使式子-3对于ω求导,然后使导数等于0,便可以求出ω的值:ω=c S W -1( m 1- m 2),其中c是一个参数,我们只对ω的方向感兴趣,所以c可以取值为1.

  另外,最后求得的 J(ω)的值等于λ k,λ kS W -1 S B的最大的特征值,而ω则是 S W -1 S B的最大特征值所对应的特征向量。

  最后有一些关于LDA算法的讨论,出自文献[1]:

  1. Fisher LDA对数据的分布做了一些很强的假设,比如每个类的数据都是高斯分布,各个类的协方差相等。虽然这些强假设很可能在实际数据中并不满足,但是Fisher LDA已经被证明是非常有效地降维算法,其中的原因是线性模型对于噪音的鲁棒性比较好,不容易过拟合。

  2. 准确的估计数据的散布矩阵是非常重要的,很可能会有较大的偏置。用式子-2进行估计在样本数据比较少(相对于维数来说)时会产生较大的变异性。

 

  参考文献:

  [1] Fisher Discriminant Analysis with Kernals. Sebastian Mika, Gunnar Ratsch, Jason Weston, Bernhadr Scholkopf, Klaus-Robert Muller.

  [2] Fisher Linear Discriminant Analysis. Max Welling.

  [3] 机器学习导论。 Ethem Alpaydin

本文链接

相关 [机器学习 特征选择 降维] 推荐:

机器学习-特征选择(降维) 线性判别式分析(LDA)

- - 博客园_首页
  特征选择(亦即降维)是数据预处理中非常重要的一个步骤. 对于分类来说,特征选择可以从众多的特征中选择对分类最重要的那些特征,去除原数据中的噪音. 主成分分析(PCA)与线性判别式分析(LDA)是两种最常用的特征选择算法. 关于PCA的介绍,可以见我的 另一篇博文. 这里主要介绍线性判别式分析(LDA),主要基于Fisher Discriminant Analysis with Kernals[1]和Fisher Linear Discriminant Analysis[2]两篇文献.

机器学习五步走

- - 我爱机器学习
经常会有人问“我该如何在机器学习方面更进一步,我不知道我接下来要学什么了. 一般我都会给出继续钻研教科书的答案. 每当这时候我都会收到一种大惑不解的表情. 但是进步确实就是持续的练习,保持较强的求知欲,并尽你可能的完成具有挑战性的工作. 因为他是为数不多的几种可以让你真真让你获取坚实知识的媒介. 是的,你可以选择选一门课,注册MOOC,参加一些讨论班.

机器学习之路

- - 我爱机器学习
自从答应简二毛博士将自己的机器学习历程和心得分享给大家至今,转眼间半年已经过去了,感谢简博士分享和开源精神的鼓舞,这也正是本系列关于机器学习介绍博客的动力来源. 之前有些网友,师弟们问我,学习机器学习怎么入手,从看什么书开始. 如果你只愿意看一本书,那么推荐Bishop的PRML,全名Pattern Recognition and Machine Learning. 这本书是机器学习的圣经之作,尤其对于贝叶斯方法,介绍非常完善.

机器学习算法Boosting

- - 标点符
机器学习通常会被分为2大类:监督学习和非监督学习. 在监督学习中,训练数据由输入和期望的输出组成,然后对非训练数据进行预测输出,也就是找出输入x与输出y之间的函数关系F:y = F(x). 根据输出的精确特性又可以分为分类和回归. 分类和回归的区别在于输出变量的类型. 定量输出称为回归,或者说是连续变量预测.

Mahout实现的机器学习算法

- - ITeye博客
使用命令:mahout -h.   在Mahout实现的机器学习算法见下表:. EM聚类(期望最大化聚类). 并行FP Growth算法. 并行化了Watchmaker框架. 非Map-Reduce算法. 扩展了java的Collections类. Mahout最大的优点就是基于hadoop实现,把很多以前运行于单机上的算法,转化为了MapReduce模式,这样大大提升了算法可处理的数据量和处理性能.

国内的机器学习几个人

- - 丕子
转: http://blog.csdn.net/playoffs/article/details/7588597. 推荐几个机器学习和数据挖掘领域相关的中国大牛:. 李航:http://research.microsoft.com/en-us/people/hangli/,是MSRA Web Search and Mining Group高级研究员和主管,主要研究领域是信息检索,自然语言处理和统计学习.

Apache Mahout 0.8 发布,机器学习库

- - 开源中国社区最新新闻
Apache Mahout 0.8 发布了,Apache Mahout 是 Apache Software Foundation (ASF) 开发的一个全新的开源项目,其主要目标是创建一些可伸缩的机器学习算法,供开发人员在 Apache 在许可下免费使用. 该项目已经发展到了它的最二个年头,目前只有一个公共发行版.

Ruby的机器学习项目

- - 阳志平的网志-技术类
作者是辉瑞公司的小牛,可惜烂尾了. 我在改啊改啊,可惜现在是商业项目,暂时不能放出改掉的部分. 对了,顺便做个小广告,去年组织翻译的一本小书:社会网络分析:方法与实践. 已经上市了,感兴趣的可以翻翻:. 社会网络分析:探索关系背后的科学与技术. treat:自然语言处理. 类似于igraph,也是桥接处理nlp.

机器学习该如何入门

- - CSDN博客综合推荐文章
  对于这个问题的解释,说实话我很有压力,因为在分享篇文章之前就有朋友告诉我,这个百度上一搜一大片,还需要你讲吗. 正如同一千个读者眼里有一千个林黛玉一样,我解释的当然是我个人自从读研到工作这么多年对机器学习的学习到应用过程的独特见解.   首先我们看下图了解一下机器学习在AI(Artificial Intelligence 人工智能)领域的地位.

[译] 理解机器学习技术

- - IT瘾-dev
第1讲 理解机器学习技术. 学完本模块的内容,读者将能够:. 讨论机器学习的技术和商业应用. 学完本讲的内容,读者将能够:. 解释各类机器学习方法和算法. “机器学习领域的突破,其价值10倍于微软. 你是否曾经为计算机能够下象棋或者机器人能够完成复杂任务而感到惊奇. 一旦你理解了机器如何学习和适应各种问题、提供合适的解决方案时,这些看上去很复杂的问题实际上相当简单.