当前位置: 首页 > 新闻及公告 > 学术专题

学术专题

机器学习之数据降维方法-PCA和LD--高性能计算部 万艺

2019-03-08

一. 背景介绍

在机器学习项目中,我们经常会遇到“维度灾难”问题,维基百科对于“维度灾难”的定义为:当数学空间维度增加时,分析和组织高维空间(通常有成百上千维)会因体积指数增加而遇到各种问题的场景。一般而言,我们认为造成“维度灾难”的主要原因有两个:

(1)    高维情形下出现的数据样本稀疏;

(2)    高维情形下距离计算困难。

而解决维度灾难通常有两个思路:

(1)    降维:包括PCALDAMDSLLE等方法,其主要思想是将原始高维特征空间里的点向一个低维空间投影,新的空间维度低于原特征空间,所以维数减少了。此过程中,原始的特征消失了,也就是特征发生了根本性的变化;

(2)    特征选择:包括相关系数,决策树(信息增益,Gini指数),正则化等方法,其主要思路是从总特征中选取部分特征出来,舍弃未被选中的特征。所以,新的特征集只是原来特征集的一个子集。

本文主要着重介绍降维里的PCALDA两种代表性方法,详细给出其算法实现过程和两种方法的差异性对比。同时,笔者也在最后的附录中给出了PCA方法的数学推导过程。

二.算法

1.      PCA-主成分分析法

PCA的主要思路是将高维空间(维)中的训练样本点通过与投影矩阵相乘映射到低维空间(d维,)中,其目标是让映射后的点尽可能的分开,即方差尽可能的大。现假设有维训练数据集,需要降到d维,下面给出PCA的具体算法步骤:

w 样本中心化:;

w 计算样本协方差矩阵:;

w 求出协方差矩阵的特征值及其对应的特征向量;

w 取最大的d个特征值对应的特征向量组成投影矩阵;

w 得到降维后的样本集合

这里需要注意的是d一般事先给定,或者可以通过开销较小的学习器交叉验证来选取较好的d值。

2.      LDA-线性判别分析法

LDA的基本思想是将训练样本(有label)中的点投影到一条直线上,使得同类样本点的投影点尽可能接近,异类样本点的投影中心尽可能远离,即投影后内类方差最小,类间方差最大,可通过下图来理解:其中表示正样例点,表示负样例点。

下面我们给出一个二分类问题使用LDA的算法例子,LDA也可以用在多分类问题上。现给定训练数据集 ,,其中,维向量。假设分别表示的样本集合,期望以及协方差矩阵,样本点投影到直线上(二分类问题中是一个维向量,多分类问题中w是一个的矩阵),则两类数据样本中心和协方差的投影可表示为。下面给出LDA的具体算法步骤:

w 计算类内散度矩阵和类间散度矩阵

w 给出优化问题:

w 通过拉格朗日乘子法和特征值(或奇异值)分解,得到上述优化问题的解:

w 对新样本点进行分类:将其投影到直线上,根据投影点的位置(计算其投影点与各类样本中心的距离)来确定新样本的类别。

三.        方法比较

下面我们对二者进行比较:

w 学习模式不同:PCA既可以用在无监督学习上,也可用于有监督学习,LDA一般用于有监督学习;

w 出发思想不同:PCA是从样本协方差出发,选择使得样本投影点具有最大方差的投影方向,LDA考虑了分类标签信息,寻求投影后同类样本尽可能接近,异类样本尽可能远离,即选择了分类性能最好方向;

w 降维后可用维度数量不同:PCA最多有维度可用(即样本原始维度),LDA最多生成(标签数-1)维子空间,与原始维度数量无关。

附录:PCA算法数学推导过程

推导中所有符号与上述PCA算法中的符号一致。当前目标是找到一个投影矩阵(正交),使得投影后的样本尽可能分散,即方差尽可能大。假设投影后的样本集为,则新空间中样本协方差可表示为,因此,该问题被归结为如下的优化问题:

给出拉格朗日函数:

求偏导使其等于0矩阵):

可见,为原始协方差矩阵的特征值。根据上式,我们可将投影后的协方差改写:

因此,越大,方差越大,我们选取前d个最大的特征值所对应的特征向量组成投影矩阵。