现代机器学习 课件 第4章 特征提取与选择

第4章特征提取与选择4.1经典特征提取方法4.2经典特征选择算法4.3稀疏表示与字典学习本章小结

特征工程是指通过自动的方式从原始数据中获取有利于后期应用问题的特征的过程。特征工程承接数据获取环节与应用问题环节,对于后期应用问题的最终处理结果会产生很

大的影响。因此,特征工程也是机器学习中非常重要的一个环节,目前特征提取的方法很多,但是并没有完全通用的方法,必须根据实际问题或数据选择不同的方法。在实际应用中,特征工程包含从特征使用方案的设计到特征处理方法的选择以及特征的评价等多个具体环节,如图4.1所示。图4.1特征工程结构图

4.1经典特征提取方法

4.1.1主成分分析法主成分分析是一种高效的特征提取方法,通过正交变换将一组可能存在的相关性变量转换为一组线性不相关的变量,转换后的这组变量叫主成分。PCA最初是由KarlPearson针对非随机变量引入的,HaroldHotelling将此方法推广到随机向量的情形中。

PCA算法在运算时要用到协方差及协方差矩阵。在概率论和统计学中协方差用于衡量两个变量的总体误差,计算公式为

在进行多维数据分析时,不同维度之间的相关程度需要协方差矩阵来描述,维度之间的两两相关程度就构成了协方差矩阵,而协方差矩阵主对角线上的元素即为每个维度上的数据方差。

对于二维的数据,任意两个维度之间求其协方差,得到的4个协方差就构成了协方差矩阵:

对于正交属性空间的样本点,构造一个超平面来表达,使得所有样本点到该超平面的距离都足够近,样本点在这个超平面上的投影尽可能分散。

PCA的主要思想是极大化投影方差,为了使得在投影后的空间中数据的方差最大,依次选择数据方差最大的方向作为主分量进行投影,最大化数据的差异性,从而保留更多的原始数据信息;同时,每次选择主分量时必须保证主分量间正交(不相关)。假设输入空间χ∈Rn为n维向量的集合,特征向量x(i)∈χ,投影向量为u∈Rn且限制u的模长为1,即uTu=1,对原始特征向量x(i)进行去中心化处理,使得去中心化后的特征向量z(i)各特征分量的均值为0,如图4.2所示。图4.2PCA方法中样本点投影方向示意图

因此优化函数为

通过拉格朗日方法转换为无约束问题(其中λ为拉格朗日乘子):

对式(4-7)求导,可得

从式(4-8)可知,u是协方差矩阵S的特征向量,λ为特征值。同时有

λ也是投影后样本的方差。因此,主成分分析可以转换成一个矩阵特征值分解问题,投影向量u为矩阵的最大特征值λ对应的特征向量。

PCA算法的主要步骤如下:

(1)获取数据,假设每一个数据为一个m维的列向量,对于PCA算法中使用的数据,需要限定。假设数据结构都是线性的,这也就决定了它能进行的主元分析之间的关系也是线性的。

(2)求出数据平均值并用原数据减去均值得到:

(3)计算协方差矩阵。

(4)计算协方差矩阵的特征值与特征向量。

(5)由小到大依次排列特征值及其对应的特征向量,选取需要的维数,组成变换矩阵。特征值大对应的对角线上的元素就越大,重要性就越高,因此将特征值最大的特征向量排在最前面。

(6)计算降维后的新样本矩阵。

4.1.2线性判别方法

线性判别分析(LinearDiscriminantAnalysis,LDA)是一种监督学习的特征降维方法(PCA是一种无监督的特征降维方法),是在降维的基础上考虑了类别的因素,希望得到的投影类内方差最小,类间方差最大。

4.1.3流形学习方法

“流形”是局部具有欧几里得空间性质的空间,是欧几里得空间中的曲线、曲面等概念的推广。一个流形好比是一个d维的空间在一个m维的空间中(m>d)被扭曲之后的结果。需要注意的是,流形并不是一个形状,而是一个空间。例如一块布,将其展平可以把它看成一个二维的空间,将它进行扭曲,它就变成了一个新的流形(三维空间)。当然在展平的状态下,它也是一个流形,欧几里得空间是流形的一种特殊情况,如图

4.3所示。图4.3流形数据示意图

下面介绍两种基本的基于流形学习的降维算法。

1.等度量映射算法

等度量映射认为高维空间的直线距离在低维嵌入流形中是不可达的,因此,高维空间映射到低维空间以后,应该用样本间的测地线距离代替欧氏距离来保持样本间的流形结构,样本之间邻近的点依然邻近,较远的点仍然相隔较远。如图4.4所示,高维空间中的AB直线距离并不准确,反而AB曲线的长度作为长度看起来更靠谱。这个低维嵌入流行上两点的距离是“测地线”距离。测地线距离是流形上的两点沿流形曲面的最短距离。图4.4-测地线距离示意图

等度量映射算法步骤:

2.局部线性嵌入

局部线性嵌入与等度量映射试图保持近邻样本之间距离不同,局部线性嵌入目的是保持邻域内样本之间的线性表示关系。假定样本点xi的坐标能够通过它的邻域样本xj,xk,xl

的坐标通过线性组合而重构出来,即

局部线性嵌入希望式(4-10)的线性表示关系在低维空间中得以保持。

局部线性嵌入算法步骤:

(1)对每个样本xi寻找它的k近邻集合Qi,对于属于Qi的近邻样本通过式(4-11)计算wij,否则,权重wij为0。

(2)令(W)ij=wij,计算B=(I-W)T(I-W)。

(3)对矩阵B做特征值分解。

(4)取Λ为d'个最小特征值所构成的对角矩阵,ZT为相应的特征向量矩阵,则矩阵Z为样本集在低维空间的投影。

4.2经典特征选择算法

在机器学习中,将数据的属性称为特征。对原始数据进行处理以后,有时数据的维度会特别大,但是有些维度对当前问题没有帮助,甚至会产生巨大的计算量;无关特征和冗余特征对模型的精度也产生影响,导致维数灾难,所以需要对数据进行降维。特征选择是从数据的原始特征集中,选择一个“重要”的子集,以改进下游任务的性能或者降低下游任务的计算复杂度,是机器学习中重要的降维方法,具体见图4.5。图4.5特征选择框架

4.2.1特征选择基本步骤

从初始的特征集合中选取一个包含了所有重要信息的特征子集,若没有任何领域知识作为先验假设,最简单直接的方法就是遍历所有可能的子集。然而这在计算上是不可行的,因为这样做会遭遇组合爆炸,特征个数稍多就无法进行。可行的做法是首先产生一个“候选子集”,评价出它的好坏,给予评价结果,然后再产生下一个候选子集,再对其进行评价……这个过程持续进行下去,直至无法找到更好的候选子集为止。

显然,这里涉及两个关键环节:

(1)如何根据评价结果获取下一个候选特征子集。

(2)如何评价候选子集的好坏。

特征选择方法包括两个环节:第一个环节是特征子集搜索,第二个环节是特征子集评价。特征选择方法必须将特征子集搜索机制与特征子集评价机制相结合才能达到期望的效

果。常见的特征选择方法大致可以分为三类:过滤式、包裹式和嵌入式。

1.过滤式选择

过滤式选择先对数据集进行特征选择,然后再训练学习器,特征选择过程与后续学习器无关。这相当于先用特征选择对初始特征进行“过滤”,再用过滤后的特征来训练模型。

Relief是一种典型的过滤式特征选择算法,该算法设计了一个“相关统计量”来度量征的重要性。特该统计量是一个向量,其每个分量分别对应一个初始特征,而特征子集的重

要性则是由子集中每个特征所对应的相关统计量分量之和来决定的。于是,最终只需要指定一个阈值τ,然后选择比τ大的相关统计量分量所对应的特征即可;也可指定预选取的特征个数k,然后选择相关统计量分量最大的k个特征。

2.包裹式选择

与过滤式选择不考虑后续学习器不同,包裹式选择直接把最终将要使用的学习器的性能作为特征子集的评价准则。换言之,包裹式选择的目的就是为给定学习器选择最有利于其性能、“量身定做”的特征子集。

拉斯维加斯包裹算法是一个典型的包裹式选择算法。它在拉斯维加斯算法框架下使用随机策略来进行子集搜索,并以最终分类器的误差为特征子集评价准则,其算法流程如图4.6所示。图4.6LVW算法流程

需注意的是,由于LVW算法中特征子集搜索采用了随机策略,而每次特征子集评价都需训练学习器,计算开销大,因此算法设置了停止学习条件控制参数T。然而,整个LVW算法是基于拉斯维加斯算法框架,若初始特征数量很多(即|A|很大)、T设置较大,则算法可能运行很长时间都达不到停止条件。换言之,若有运行时间限制,则有可能给不出解。

3.嵌入式选择

在过滤式选择和包裹式选择方法中,特征选择过程与机器学习训练过程有明显的分别,而嵌入式选择则不同,它将特征选择过程与学习器训练过程融为一体,两者在同一个优化过程中完成,即在学习器训练过程中自动地进行了特征选择。

4.2.2特征选择搜索策略

从一组数量为m的特征中选择出数量为d(d<m)的一组最优特征,用于后面分类器的设计。

1.最优搜索算法

从m个特征中挑选出d个特征,所有可能的组合数为

若要找到最优的特征组合,必须对所有的组合情况加以比较(穷举法)。一种不需要进行穷举但仍能取得最优解的方法是分支定界法。这是一种自顶向下的方法,即从包括所有候选特征开始,逐步去掉不被选中的特征。这种方法具有回溯的过程,能够考虑到所有可能的组合。

分支定界法的基本思想:设法将所有可能的特征选择组合构建成一个树状的结构,按照特定的规律对树进行搜索,使得搜索过程尽可能早地可以达到最优解而不必遍历整

个树。

要做到这一点,一个基本的要求是准则判据对特征具有单调性,即,如果有互相包含的特征组的序列,若特征子集具有下列包含关系:ψ1⊃ψ2⊃…⊃ψn,则可分性判据满足:

1)树的构造过程

(1)计算每个节点下面的子节点个数。

其中,i为树结构中的基数,ri为当前节点对应的待选特征子集中特征的个数。

(2)计算当前节点所有可能的删除情况所对应的JD值。

(3)将JD值按从小到大的顺序排列,从左到右生成qi个子节点。

2)树的搜索过程

(1)设置可分性判据值的界值。初始为0,搜索过程中,该值被不断更新,该值达到最大,不被更新时,算法结束,输出对应特征子集。

(2)每层搜索过程从右开始,针对一节点不断生成子节点,直至最大层数(JD≥B),更新界值,进行回溯操作;若JD<B,同样执行回溯操作。

分支定界法可以寻找到全局最优并且特定的挑选舍弃策略,可以减少计算量,但当特征维数m非常大时,搜索最优解的时间复杂度还是非常大的;而且可分性判据必须满足单调性。

2.次优搜索算法

1)单独最优特征组合

最简单的特征选择方法就是对每一个特征单独计算类别可分性判据,根据单个特征的数据值排队,选择其中前d个特征。只有特征的判据值满足下面两式时,利用该方法才可以选出当前判据下的最优的特征组合:

或

2)顺序前进法

顺序前进法是最简单的自下而上的搜索方法:每次从待选特征中选择出一个特征,使其与已选的特征组合在一起所得的判据值最大,直到特征数满足要求为止

3)顺序后退法

顺序后退法是一种自上而下的方法,从全体特征开始,每次删除一个特征,所剔除的特征应使仍然保留的特征组合的判据值最大,直至剩余的特征数满足要求为止。

4)增l减r法

顺序前进法的一个缺点是,某个特征一旦被选中就不能被剔除;顺序后退法的一个缺点是,某个特征一旦被剔除就不能再重新被选中。两种方法都是根据局部最优的准则挑选

或者剔除特征,这样就可能导致选择不到最优的特征组合。一种改善的方法是将两种做法结合起来,在选择或剔除过程中引入一个回溯的步骤,使得依据局部准则选择或剔除的某

个特征有机会因为与其他特征间的组合作用而重新被考虑。

3.基于优化的特征选择方法

特征选择问题是个组合优化问题,因此可以使用解决优化问题的方法来实现特征选择。

遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。

遗传算法模拟自然选择和自然遗传中发生的繁殖、交叉和基因突变现象,从随机初始化的候选解出发,按照某种指标从解群中选取较优的个体,利用遗传算子(选择、交叉、变

异)对这些个体进行组合,产生新的候选解群,重复此过程,直到满足某种收敛指标为止。基本遗传算法又称简单遗传算法或标准遗传算法,是由Goldberg总结出来的一种最基本的遗传算法,其遗传操作过程简单,容易理解,是其他复杂遗传算法的雏形和基础。

遗传算法的基本步骤:

(1)初始化,t=0,随机地产生一个包含L条不同染色体的种群M(0)。

(2)计算当前种群M(t)中每一条染色体的适应度f(m)。

(3)按照选择概率P(f(m))对种群中的染色体进行采样,由采样出的染色体经过一定的操作繁殖出下一代染色体,组成下一代的种群M(t+1)。

(4)回到(2),直到达到终止条件,输出适应度最大的染色体作为找到的最优解。终止条件通常是某条染色体的适应度达到设定的阈值。

在第(3)步产生后代的过程中,有两个最基本的操作,一是重组(recombination)。重组也称交叉(crossover),是指两条染色体配对,并在某个随机的位置上以一定的重组概率Pco进行交叉,互换部分染色体,这也就是遗传算法中模拟有性繁殖的过程。另一个基本操作是突变(mutation)。每条染色体的每一个位置都有一定的概率Pmut发生突变(从0变成1或从1变成0)。

4.2.3特征选择评价准则

要进行特征选择,首先要确定选择的准则,也就是如何评价选出的一组特征。确定了评价准则后,特征选择问题就变成从D个特征中选择出使准则函数最优的d个特征(d<D)

的搜索问题。

从概念上,我们希望选择出的特征能够最有利于分类,因此,利用分类器的错误率作为准则是最直接的想法。但是,这种准则在很多实际问题中并不一定可行:从理论上,即使概率密度函数已知,错误率的计算也非常复杂,而实际中多数情况下样本的概率密度未知,分类器的错误率计算就更困难;如果用样本对错误率进行实验估计,则由于需要采用交叉验证等方法,将大大增加计算量。

因此,需要定义与错误率有一定关系但又便于计算的类别可分性准则Jij,用来衡量在一组特征下第i类和第j类之间的可分程度。这样的判据应该满足以下几个要求:

(1)判据应该与错误率(或错误率的上界)有单调关系,这样才能较好地反映分类目标。

(2)当特征独立时,判据对特征应该具有可加性,即

这里Jij是第i类和第j类的可分性准则函数,Jij越大,两类的分离程度就越大,x1,x2,…,xd是一系列特征变量。

(3)判据应该具有以下度量特性:

(4)理想的判据应该对特征具有单调性,即加入新的特征不会使判据减小,即

1.基于几何度量的可分性判据

在第3章中,Fisher线性判别采用了使样本投影到一维后类内离散度尽可能小、类间离散度尽可能大的准则来确定最佳的投影方向,这其实就是一个直观的类别可分性判据。考虑到特征选择的情况,这一思想可以用来定义一系列基于几何距离的判据。

直观上考虑,可以用两类中任意两两样本间的距离的平均来代表两个类之间的距离。现在推导多类情况下的这种判据。

2.基于概率分布的可分性判据

下面列出几种概率距离度量。

1)Bhattacharyya距离

直观地分析可以看出,当两类概率密度函数完全重合时,JB=0;当两类概率密度完全没有交叠时,JB=∞。

2)散度

两类概率密度函数的似然比对于分类是一个重要的度量。人们在似然比的基础上定义了以下的散度作为类别可分性的度量:

3.基于熵函数的可分性判据

熵的概念最早起源于物理学,用于度量一个热力学系统的无序程度。在信息论里则叫信息量,即熵是对不确定性的度量。从控制论的角度来看,应叫不确定性。在信息世界,熵

越大,意味着传输的信息越多;熵越小,意味着传输的信息越少。在判断某些特征的类别可分性时,可以观察该特征对于类别判断的不确定程度,因此引入了熵的概念。

熵函数满足下列条件:

4.3稀疏表示与字典学习4.3.1稀疏表示稀疏表示是一种信号表示方法,它从基本信号集合中尽可能地选取少的基本信号,通过这些基本信号的线性组合来表示特定的信号。通过稀疏表示可以获得更为简洁的信号表示方式,从而使我们更容易地获取信号中所蕴含的信息,更方便进一步对信号进行加工处理。这些基本信号被称作原子,是从过完备字典中选出来的,而过完备字典则是由个数超过信号维数的原子聚集而来的。任一信号在不同的原子组合下有不同的稀疏表示。

假设我们用一个m×n的矩阵表示数据集Y,每一列代表一个样本,每一行代表样本的一个属性,一般