1、第7章 稀疏大数据的维数约简第7章 稀疏大数据的维数约简 7.1 稀疏矩阵的应用及概念稀疏矩阵的应用及概念7.2 稀疏表示理论及重构稀疏表示理论及重构7.3 线性回归模型线性回归模型7.4 稀疏保持映射稀疏保持映射7.5 基于基于 Lasso的稀疏主成分的稀疏主成分7.6 稀疏判别分析稀疏判别分析第7章 稀疏大数据的维数约简7.1 稀疏矩阵的应用及概念稀疏矩阵的应用及概念1.稀疏矩阵的应用稀疏矩阵的应用 随着信息技术及网络的迅速发展,非结构化数据大量涌现,如文本、图像、音频、视频 等,其特点可归结为多样性、高维、海量、非线性以及不能为人的感知所单独处理。对非结 构化数据发现其内在关系信息丰富的
2、描述,是一个具有广泛应用背景而又迫切需要的富有 挑战性的研究课题,如识别与检索、图像识别与检索、DNA 序列提取等。第7章 稀疏大数据的维数约简2.稀疏矩阵的研究及概念稀疏矩阵的研究及概念稀疏矩阵是指非零元素占全部元素的百分比很小(5%以下)的矩阵或者是非零元素占 全部元素的百分比较大(近50%)的矩阵。由于稀疏矩阵的研究非常重要,关于其的研究成 果已有很多,本章主要介绍最经典的稀疏矩阵方法,通过将某些回归系数退化或设为0,来 达到降维的目的。第7章 稀疏大数据的维数约简7.2 稀疏表示理论及重构稀疏表示理论及重构7.2.1 范数稀疏解范数稀疏解 考虑到一个实向量x=(x1,x2,xn)Rn,
3、则所谓l2范式的数学定义为第7章 稀疏大数据的维数约简第7章 稀疏大数据的维数约简第7章 稀疏大数据的维数约简SRE的一个假设是样本点是从一个线性空间采样的,因此,其面临的 问题类似于给定限制条件y-kx=b,并分别以l2范式、l1范式最小为限制条件的两个求解 最优化问题,如图7-2所示。第7章 稀疏大数据的维数约简图7-1 l2范式、l1范式和l0范式的定义第7章 稀疏大数据的维数约简在图7-2中,x0表示寻找到的最优解,中心处的黑色箭头表示寻找最优解的过程。从 图中可以发现,在寻找最优解时,只要所求的解是稀疏的,那么以l1范式最小为限制条件总 能找到该稀疏解,相反,以l2范式最小化为限制条
4、件的求解问题虽然也能寻找到最优解,但 该解并不稀疏。稀疏表示算法的核心思想就在于在降维过程中保持原始数据稀疏线性重建的特性,因此以l1范式最小为限制条件是替代以l0范式最小为限制条件的最佳方式。第7章 稀疏大数据的维数约简图7-2 l2范式和l1范式的求解过程第7章 稀疏大数据的维数约简7.2.2 稀疏表示理论概述稀疏表示理论概述 假定样本X=x1,x2,x3,xnRDn,稀疏表示的目的是尽可能用少量的X 的 样本来表示xiX,具体的数学定义描述如下第7章 稀疏大数据的维数约简第7章 稀疏大数据的维数约简第7章 稀疏大数据的维数约简7.2.4 基于稀疏表示的算法流程 基于稀疏表示的算法流程如下
5、:(1)给定一共n 个训练样本,其中每个样本是 D 维的,那么所有的训练样本可以用 X=X1,X2,XnRDn 来表示。(2)对每个训练样本都进行归一化处理。(3)对任意输入的测试样本y,求其稀疏表示,使稀疏的l1 范数最小。第7章 稀疏大数据的维数约简(4)针对每一个类i,计算只用这个类对测试样本进行重构时的重构误差。(5)将重构误差最小的类别i作为测试样本y 的类别。第7章 稀疏大数据的维数约简7.3 线性回归模型线性回归模型令XnD=(x1,x2,xn)T是样本自变量组成的矩阵,令yn1=(y1,y2,yn)T 是 样本响应变量组成的向量。第7章 稀疏大数据的维数约简7.3.1 最小二乘
6、法最小二乘法第7章 稀疏大数据的维数约简假定X 是满 秩 矩 阵,则 此 时XTX 是 正 定 的。当 时,RSS()会取到极小值:上式有一定的局限性,使用最小二乘法来模拟估计参数的值,所能达到的精度不够,一些学者认为可通过收缩或把一些系数直接设为0可使预测精确度得到提高。第7章 稀疏大数据的维数约简7.3.2 岭回归岭回归 岭回归(RidgeRegression)的思想是对目标函数中的回归系数 上增加些限制条件来 缩小的值,其形式如下:式中,为控制收缩的参数,随着 的值不断增大,相应的回归系数的值也越来越向0 值靠拢。第7章 稀疏大数据的维数约简该式进一步改写为如下:使得第7章 稀疏大数据的
7、维数约简上式确切的显示出了目标函数中对系数大小的限制,式(7-15)中的 和式(7-16)存在着对应关系。上式进一步写成矩阵的形式,目标函数最小化公式变为第7章 稀疏大数据的维数约简第7章 稀疏大数据的维数约简上述两种回归模型公式中采用的最小二乘法和岭回归方法所得到的回归模型系数i(1iD)的值都是非零的值,说明所有自变量 X 对相应变量y 值的生成都起着一定的作 用。通常在实际的问题中,我们会最想知道哪些自变量对相应变量起着关键性作用,即哪 些变量最具有决定性,通过模型选择(变量选择),以提高回归模型的解释性和预测的精度。为了得到稀疏的回归模型系数,即部分i(1iD)的值为0,Tibshir
8、aniR.提出了lasso 回归4的方法。第7章 稀疏大数据的维数约简7.3.3 套索回归套索回归 套索回归(LassoRegression)模型算法的目标函数定义为第7章 稀疏大数据的维数约简第7章 稀疏大数据的维数约简第7章 稀疏大数据的维数约简第7章 稀疏大数据的维数约简7.4 稀疏保持映射稀疏保持映射7.4.1 稀疏保持映射原理稀疏保持映射原理 受稀疏表示的启发,qiao等人提出稀疏保持映射方法。假设样本集合为X=x1,x2,xn RD*n,xiRD,i=1,2,n。根据稀疏表示理论,SPP首先重构每 个样本xi并获取其对应的稀疏重构系数向量si。si的求取可转化为最小化问题第7章 稀
9、疏大数据的维数约简式中,I 为标量1,In 是元素全为1 的n 维列向量;si=si,1,si,i-1,0,si,i+1,si,n是n 维且第i个元素为0的列向量。第7章 稀疏大数据的维数约简由此可见,与传统的稀疏表示理论相比,SPP算法中,在为每一个样本进行稀疏重构 时,所采用的数据字典 X 是整个样本集,其中被重构样本本身的重构系数强制为0,即该 样本在对应的字典中不起作用。而得到的稀疏重构稀疏向量中较大的系数所对应的是与被 重构样本相似的样本,因此可以说该方法保留了原始样本的局部近邻信息。第7章 稀疏大数据的维数约简第7章 稀疏大数据的维数约简可以看出,两种方式的不同之处在于误差容忍度的
10、不同,方式1的误差容忍度是一个 固定的值,而方式2将si和ti同时优化,所以ti就是根据每个样本所自动调节得到的误差容 忍度。式(7-22)和式(7-23)中的l1范数最小化问题可以通过转换成标准线性规划问题来求 解,因此可对两种方式计算并优化得到每一个样本的系数向量,得到稀疏重构系数矩阵 S 定义为第7章 稀疏大数据的维数约简对系数矩阵进行降维优化,从原始的高维空间投影到低维子空间时,总是希望保留所 需要的特征信息。为探寻最优的特征向量,定义目标函数第7章 稀疏大数据的维数约简第7章 稀疏大数据的维数约简第7章 稀疏大数据的维数约简7.4.2 稀疏保持映射算法流程稀疏保持映射算法流程1.计算
11、权重矩阵计算权重矩阵 有n 个训练样本点,每个训练样本点是 D 维的,令 X=x1,x2,xn,现在重构 每一个训练样本点xj,i=1,n,找到稀疏重构稀疏向量si,使得第7章 稀疏大数据的维数约简2.计算投影矩阵计算投影矩阵 我们期望在高维空间中的特性在降维后的低维空间中可以得到很好地保持,所以类似 于近邻保持嵌入(NPE),为了保持其局部结构,定于如下目标函数化简得第7章 稀疏大数据的维数约简即该问题的最优解w 对应于以下特征值问题的d(低维空间的维数)个最大的特征值所对应 的特征向量。第7章 稀疏大数据的维数约简7.4.3 SPP优点优点(1)SPP含有 LPP和许多其他线性降维方法的优
12、点。例如,SPP是线性的,其权重矩 阵是稀疏的,所以能更有效快速的计算。(2)SPP不需要处理模型参数问题,例如在 LPP和 NPE 中近邻的大小,热核的宽度 等,因此SPP比较方便有效。(3)SPP虽然属于全局方法,但在其的稀疏表示过程中会拥有一些局部的特性。(4)能容易的被扩展成在监督的和半监督的情况下的算法。第7章 稀疏大数据的维数约简7.5 基于基于Lasso的稀疏主成分的稀疏主成分稀疏主成分分析即是为了解决这个问题而引进的一个算法。它会把主成分系数(构成 主成分时每个变量前面的系数)变的稀疏,也即是把大多数系数都变成零,通过这样一种方 式,我们就可以把主成分的主要的部分凸现出来,这样
13、主成分就会变得较为容易解释。第7章 稀疏大数据的维数约简实现主成分分析稀疏化,最终会转化为优化问题,也即对本来的主成分分析中的问题 增加一个惩罚函数。这个惩罚函数包含有稀疏度的信息。当然,最终得到的问题是 NP 困 难问题,为了解决它,我们需要采用一些方法逼近这个问题的解。这也是不同稀疏主成分 分析算法不同的由来。第7章 稀疏大数据的维数约简1.稀疏主成分原理稀疏主成分原理 受 Lasso的启发,ZouH.8等人则直接将主成分的求解问题转化为 Lasso回归问题,这样稀疏主成分的求解就有效地转化成了线性模型的变量选择问题,在此基础上再引入弹 性网(E-LasticNet)惩罚结构,就提出了基于
14、 Lasso的稀疏主成分(SimplifiedComponent TechniqueLasso,SCTLASSO)。为此,所有关于Lasso的想法都可以直接运用于稀疏主成 分了。第7章 稀疏大数据的维数约简1)基于 Lasso的简化主成分 一个很直观的想法是直接将Lasso惩罚结构应用于主成分的求解,这也正是I.T.Jolliffe9在 2003年提出SCTLASSO 的想法。SCTLASSO 可表述为如下优化问题第7章 稀疏大数据的维数约简第7章 稀疏大数据的维数约简第7章 稀疏大数据的维数约简这样主成分的求解就可以转化为线性模型的求解问题。注意当nD 且X 是列满秩 时,该定理中可取=0。
15、但当 Dn 且=0时,普通的最小二乘问题的解不唯一,这与n D 且X 不是列满秩的情形类似。引入0后,就可以得到唯一解。由此可知引入0 可以得到一个统一的处理框架。下面将更进一步推广以上结论。第7章 稀疏大数据的维数约简定理定理3:如果0由于定理3只是定理4的一种特殊情况,因此我们这里只给出定理4的证明。第7章 稀疏大数据的维数约简第7章 稀疏大数据的维数约简第7章 稀疏大数据的维数约简第7章 稀疏大数据的维数约简第7章 稀疏大数据的维数约简第7章 稀疏大数据的维数约简通过以上定理我们比较系统地给出了稀疏主成分与惩罚回归的关系。由前面的叙述可知,稀疏主成分的求解可以有效地转化为惩罚回归问题。而
16、一般的 Lasso惩罚回归问题又可以通 过最小角回归算法来解决。因此稀疏主成分的计算也可以利用最小角回归算法方便给出。第7章 稀疏大数据的维数约简第7章 稀疏大数据的维数约简2.稀疏主成分的算法稀疏主成分的算法一般的稀疏主成分算法如下:算法算法:(1)计算一般主成分的前k 个主成分对应的向量i并令A=V,1:K。(2)在给定A=(1,k)的情况下解如下的“elasticnet”回归问题:第7章 稀疏大数据的维数约简(3)对于给定的B=(1,k)计算XTXB=UDVT的SVD,并且令A=UVT。(4)重复(2)、(3)至收敛。(5)其中,1,j是一个参数,这个值是先给定一系列值计算出,再回头确定
17、最优的1,j,V是普 通的最小二乘的分量。第7章 稀疏大数据的维数约简实际上第2步求解“elasticnet”就是李永乐最小角回归算法。注意到以上算法的第2步中求解“elasticnet”回归问题时所用的惩罚是“elasticnet”,实际上这里也可以用“adaptive-Lasso”惩罚结构,由此可以得到简单自适 应 稀 疏 主 成 分(SAS-PCA)。RonZass(2006)考虑到主成分应用中更实际的一些问题提出了非负稀疏主成 分(NS-PCA)并给出了相应的算法。但是该算法相对比较复杂,并且不太方便给出选择惩 罚参数的方法。考虑到上面算法的第2步相当于 Lasso惩罚结构,直接可以用
18、最小角回归 算法求解。第7章 稀疏大数据的维数约简BradleyEfron 等人(2004)在最小角回归算法的基础上改进给出了求解非负 Lasso惩罚问题的解路径,该算法可以用来求解非负稀疏主成分(NS-PCA),不过此时的非负稀疏主成分相当于求解下面的优化问题:式中,的各分量均加上非负条件的限制。第7章 稀疏大数据的维数约简7.6 稀疏判别分析稀疏判别分析Clemmensen等人12提出稀疏判别分析(SparseDiscriminantAnalysis,SDA)算法,其 在 LDA 中加入稀疏正则项,将分类、特征选择和降维合并为一步。第7章 稀疏大数据的维数约简通过评分法进行优化后的SDA
19、的准则函数为评分向量j给每类i分配一个实数ji,i=1,2,K。Y 是一个nq 大小的评分后 的训练样本矩阵,根据Y 对预测变量矩阵XnD 进行回归分析得到大小为Dq 的参数。是一个惩罚矩阵。l1范数引入了稀疏,如 Lasso或 ElasticNet正则项。第7章 稀疏大数据的维数约简SDA 算法:(1)初始化:(2)固定 解修改的 ElasticNet问题(修改的 ElasticNet指用 代替 NaveElastic Net中的单位矩阵)第7章 稀疏大数据的维数约简(3)固定和YTY=USVT计算优化评分;(4)重复(2)和(3)直到收敛;(5)对于固定的使用式(7-42)更新,稀疏判别方向依据奇异值进行排序,从而区 分判别程度。
