《面向大数据的高维数据挖掘技术》课件第7章

第7章稀疏大数据的维数约简7.1稀疏矩阵的应用及概念7.2稀疏表示理论及重构7.3线性回归模型7.4稀疏保持映射7.5基于Lasso的稀疏主成分7.6稀疏判别分析

7.1稀疏矩阵的应用及概念

1.稀疏矩阵的应用

随着信息技术及网络的迅速发展,非结构化数据大量涌现,如文本、图像、音频、视频等,其特点可归结为多样性、高维、海量、非线性以及不能为人的感知所单独处理。对非结构化数据发现其内在关系信息丰富的描述,是一个具有广泛应用背景而又迫切需要的富有挑战性的研究课题,如识别与检索、图像识别与检索、DNA序列提取等。

2.稀疏矩阵的研究及概念

稀疏矩阵是指非零元素占全部元素的百分比很小(5%以下)的矩阵或者是非零元素占全部元素的百分比较大(近50%)的矩阵。由于稀疏矩阵的研究非常重要,关于其的研究成果已有很多,本章主要介绍最经典的稀疏矩阵方法,通过将某些回归系数退化或设为0,来达到降维的目的。

7.2稀疏表示理论及重构

7.2.1范数稀疏解考虑到一个实向量x=(x1,x2,…xn)∈Rn,则所谓l2范式的数学定义为

SRE的一个假设是样本点是从一个线性空间采样的,因此,其面临的问题类似于给定限制条件y-kx=b,并分别以l2范式、l1范式最小为限制条件的两个求解最优化问题,如图7-2所示。

图7-1l2范式、l1范式和l0范式的定义

在图7-2中,x0表示寻找到的最优解,中心处的黑色箭头表示寻找最优解的过程。从图中可以发现,在寻找最优解时,只要所求的解是稀疏的,那么以l1范式最小为限制条件总能找到该稀疏解,相反,以l2范式最小化为限制条件的求解问题虽然也能寻找到最优解,但该解并不稀疏。稀疏表示算法的核心思想就在于在降维过程中保持原始数据稀疏线性重建的特性,因此以l1范式最小为限制条件是替代以l0范式最小为限制条件的最佳方式。图7-2l2范式和l1范式的求解过程

7.2.2稀疏表示理论概述

假定样本X={x1,x2,x3,…,xn}∈RD×n,稀疏表示的目的是尽可能用少量的X的样本来表示xi∈X,具体的数学定义描述如下

7.2.4基于稀疏表示的算法流程

基于稀疏表示的算法流程如下:

(1)给定一共n个训练样本,其中每个样本是D维的,那么所有的训练样本可以用X=[X1,X2,…,Xn]∈RD×n来表示。

(2)对每个训练样本都进行归一化处理。

(3)对任意输入的测试样本y,求其稀疏表示,使稀疏的l1范数最小。

(4)针对每一个类i,计算只用这个类对测试样本进行重构时的重构误差。

(5)将重构误差最小的类别i作为测试样本y的类别。

7.3线性回归模型

令XnD=(x1,x2,…,xn)T是样本自变量组成的矩阵,令yn×1=(y1,y2,…,yn)T是样本响应变量组成的向量。

7.3.1最小二乘法

假定X是满秩矩阵,则此时XTX是正定的。当

时,RSS(β)会取到极小值:

上式有一定的局限性,使用最小二乘法来模拟估计参数β的值,所能达到的精度不够,一些学者认为可通过收缩β或把一些系数直接设为0可使预测精确度得到提高。

7.3.2岭回归

岭回归(RidgeRegression)的思想是对目标函数中的回归系数β上增加些限制条件来缩小β的值,其形式如下:

式中,λ为控制β收缩的参数,随着λ的值不断增大,相应的回归系数β的值也越来越向0值靠拢。

该式进一步改写为如下:

使得

上式确切的显示出了目标函数中对系数β大小的限制,式(7-15)中的λ和式(7-16)存在着对应关系。上式进一步写成矩阵的形式,目标函数最小化公式变为

上述两种回归模型公式中采用的最小二乘法和岭回归方法所得到的回归模型系数βi

(1≤i≤D)的值都是非零的值,说明所有自变量X对相应变量y值的生成都起着一定的作用。通常在实际的问题中,我们会最想知道哪些自变量对相应变量起着关键性作用,即哪些变量最具有决定性,通过模型选择(变量选择),以提高回归模型的解释性和预测的精度。为了得到稀疏的回归模型系数,即部分βi(1≤i≤D)的值为0,TibshiraniR.提出了lasso回归[4]的方法。

7.3.3套索回归

套索回归(LassoRegression)模型算法的目标函数定义为

7.4稀疏保持映射

7.4.1稀疏保持映射原理受稀疏表示的启发,qiao等人提出稀疏保持映射方法。假设样本集合为X=[x1,x2,…,xn

]∈RD*n,xi∈RD,i=1,2,…,n。根据稀疏表示理论,SPP首先重构每个样本xi并获取其对应的稀疏重构系数向量si。si的求取可转化为最小化问题

式中,I为标量1,In

是元素全为1的n维列向量;si=[si,1,…,si,i-1,0,si,i+1,…,si,n]是n维且第i个元素为0的列向量。

由此可见,与传统的稀疏表示理论相比,SPP算法中,在为每一个样本进行稀疏重构时,所采用的数据字典X是整个样本集,其中被重构样本本身的重构系数强制为0,即该样本在对应的字典中不起作用。而得到的稀疏重构稀疏向量中较大的系数所对应的是与被重构样本相似的样本,因此可以说该方法保留了原始样本的局部近邻信息。

可以看出,两种方式的不同之处在于误差容忍度的不同,方式1的误差容忍度是一个固定的值,而方式2将si和ti同时优化,所以ti就是根据每个样本所自动调节得到的误差容忍度。

式(7-22)和式(7-23)中的l1范数最小化问题可以通过转换成标准线性规划问题来求解,因此可对两种方式计算并优化得到每一个样本的系数向量,得到稀疏重构系数矩阵S定义为

对系数矩阵进行降维优化,从原始的高维空间投影到低维子空间时,总是希望保留所需要的特征信息。为探寻最优的特征向量,定义目标函数

7.4.2稀疏保持映射算法流程

1.计算权重矩阵

有n个训练样本点,每个训练样本点是D维的,令X=[x1,x2,…,xn],现在重构每一个训练样本点xj,i=1,…,n,找到稀疏重构稀疏向量si,使得

2.计算投影矩阵

我们期望在高维空间中的特性在降维后的低维空间中可以得到很好地保持,所以类似于近邻保持嵌入(NPE),为了保持其局部结构,定于如下目标函数

化简得

即该问题的最优解w对应于以下特征值问题的d(低维空间的维数)个最大的特征值所对应的特征向量。

7.4.3SPP优点

(1)SPP含有LPP和许多其他线性降维方法的优点。例如,SPP是线性的,其权重矩阵是稀疏的,所以能更有效快速的计算。

(2)SPP不需要处理模型参数问题,例如在LPP和NPE中近邻的大小,热核的宽度等,因此SPP比较方便有效。

(3)SPP虽然属于全局方法,但在其的稀疏表示过程中会拥有一些局部的特性。

(4)能容易的被扩展成在监督的和半监督的情况下的算法。

7.5基于Lasso的稀疏主成分

稀疏主成分分析即是为了解决这个问题而引进的一个算法。它会把主成分系数(构成主成分时每个变量前面的系数)变的稀疏,也即是把大多数系数都变成零,通过这样一种方式,我们就可以把主成分的主要的部分凸现出来,这样主成分就会变得较为容易解释。

实现主成分分析稀疏化,最终会转化为优化问题,也即对本来的主成分分析中的问题增加一个惩罚函数。这个惩罚函数包含有稀疏度的信息。当然,最终得到的问题是NP困难问题,为了解决它,我们需要采用一些方法逼近这个问题的解。这也是不同稀疏主成分分析算法不同的由来。

1.稀疏主成分原理

受Lasso的启发,ZouH.[8]等人则直接将主成分的求解问题转化为Lasso回归问题,这样稀疏主成分的求解就有效地转化成了线性模型的变量选择问题,在此基础上再引入弹性网(E-LasticNet)惩罚结构,就提出了基于Lasso的稀疏主成分(SimplifiedComponentTechniqueLasso,SCTLASSO)。为此,所有关于Lasso的想法都可以直接运用于稀疏主成分了。

1)基于Lasso的简化主成分

一个很直观的想法是直接将Lasso惩罚结构应用于主成分的求解,这也正是I.T.Jolliffe[9]在2003年提出SCTLASSO的想法。SCTLASSO可表述为如下优化问题

这样主成分的求解就可以转化为线性模型的求解问题。注意当n>D且X是列满秩时,该定理中可取λ=0。但当D>n且λ=0时,普通的最小二乘问题的解不唯一,这与n>D且X不是列满秩的情形类似。引入λ>0后,就可以得到唯一解。由此可知引入λ>0可以得到一个统一的处理框架。下面将更进一步推广以上结论。

定理3:如果∀λ>0

由于定理3只是定理4的一种特殊情况,因此我们这里只给出定理4的证明。

通过以上定理我们比较系统地给出了稀疏主成分与惩罚回归的关系。由前面的叙述可知,稀疏主成分的求解可以有效地转化为惩罚回归问题。而一般的Lasso惩罚回归问题又可以通过最小角回归算法来解决。因此稀疏主成分的计算也可以利用最小角回归算法方便给出。

2.稀疏主成分的算法

一般的稀疏主成分算法如下:

算法:

(1)计算一般主成分的前k个主成分对应的向量αi并令A=V[,1:K]。

(2)在给定A=(α1,…,αk)的情况下解如下的“elasticnet”回归问题:

(3)对于给定的B=(β1,…,βk)计算XTXB=UDVT的SVD,并且令A=UVT。

(4)重复(2)、(3)至收敛。

(5)

其中,λ1,j是一个参数,这个值是先给定一系列值计算出β,再回头确定最优的λ1,j,V︿是普通的最小二乘的分量。

实际上第2步求解“elasticnet”就是李永乐最小角回归算法。

注意到以上算法的第2步中求解“elasticnet”回归问题时所用的惩罚是“elasticnet”,实际上这里也可以用“adaptive-Lasso”惩罚结构,由此可以得到简单自适应稀疏主成分(SAS-PCA)。RonZass(2006)考虑到主成分应用中更实际的一些问题提出了非负稀疏主成分(NS-PCA)并给出了相应的算法。但是该算法相对比较复杂,并且不太方便给出选择惩罚参数的方法。考虑到上面算法的第2步相当于Lasso惩罚结构,直接可以用最小角回归算法求解。

BradleyEfron等人(2004)在最小角回归算法的基础上改进给出了求解非负Lasso惩罚问题的解路径,该算法可以用来求解非负稀疏主成分(NS-PCA),不过此时的非负稀疏主成分相当于求解下面的优化问题:

式中,β的各分量均加上非负条件的限制。

7.6稀疏判别分析

Clemmensen等人[12]提出稀疏判别分析(SparseDiscriminantAnalysis,SDA)算法,其在LDA中加入稀疏正则项,将分类、特征选择和降维合并为一步。

通过评分法进行优化后的SDA的准则函数为

评分向量θj给每类i分配一个实数θji,i=1,2,…,K。Yθ是一个n×q大小的评分后的训练样本矩阵,根据Yθ对预测变量矩阵Xn×D进行回归分析