基于Sparse_group_lasso相关惩罚项特征选择研究

1、分类号0241.5编号论 文题目 基于Sparse group lasso相关惩罚项特征选择研究指导教师吴庆标教授学科（专业）计算数学所在学院数学科学学院提交日期二零一八年一月陈文雯作者姓名二零一八年三月答辩日期浙江大学研究生学位论文独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人己经 发表或撰写过的研究成果，也不包含为获得 浙江大学或其他教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在 论文中作了明确的说明并表示谢意。学位论文作者签名:签字日期：“国3.3学位论文版

2、权使用授权书本学位论文作者完全了解 逝江岁 有权保留并向国家有关部门或机构送 交本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权浙江大学可以 将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。（保密的学位论文在解密后适用本授权书）学位论文作者签名:导师签名筋4 j签字n期：5.上.3签字日期：公13摘 要随着近年来数据量的爆炸式增长以及大数据概念的持续升温，数据降维技 术受到了越来越多的关注。特征选择可以有效地进行数据降维，也有各种各样 的方法。许多学者使用惩罚回归的方法来进行特征的选择，其中使用最广泛 的方法之一就是Lasso

3、。目前，国内外的学者在这方面己经有很多的研究成果, 提出了包括Lasso、Group laso Fused lasso、Graph lasso在内的许多方法。本文针对Sparse group lasso算法在实际应用中存在的不足，以其为基础, 提出了算法三方面的改进：第一，改进了损失函数，在损失函数加入了组与组 之间的相关关系项，以减小模型中非零特征间的共线性现象，得到进一步稀疏 化的系数；第二，增加了数据预处理步骤，丰富了用来建立模型的数据集，目 的是希望不仅能得到各组特征各自对结果的影响，还能得到它们共同产生的影 响；第三，将算法推广到其他的线性模型，并以逻辑回归为例给出了改进之后 的损失

4、函数。最后，我们使用模拟数据来验证算法的效果，并将算法应用在一 个电影评分的数据集上。关键词：数据降维；特征选择；Lasso； Sparse group lassoAbstractWith the explosive growth of data in recent years and the continuous rise of the concept of big data, data dimension reduction technology has drawn more and more attention. Feature selection can effectively red

5、uce the dimensionality of the data. There arc also a variety of methods to select features. Many scholars use the method of regression to carry out the selection of features, one of the most widely used is lasso. At present, scholars at home and abroad have made a lot of research achievements in thi

6、s field, and some methods including lasso, group lasso； fused lasso and graph lasso have been developed.In this paper, based on the shortcomings of sparse group lasso algorithm in practical application, this paper proposes three improvements in algorithm: Firstly, the loss function is improved, and

7、the correlation between group and group is added to the loss function to reduce collinearity between non-zero features in order to achieve further sparse coefficient. Secondly, it adds data preprocessing steps and enriches the data set used to fit the model. It is hoped that not only the influence o

8、f each groups featues on the result can be obtained, but also the common influence they have on each other. Thirdly, the algorithm is extended to other linear models, and the improved loss function is given by taking logistic regression as an example. Finally, we use simulated data to validate the a

9、lgorithm and apply the algorithm to a movie-scoring dataset.Keywords: Data dimension reduction; Feature selection; Lasso; Sparse group lasso TOC o 1-5 h z 独创性声明i摘要ii HYPERLINK l bookmark4 o Current Document Abstractiii目录iv第一章绪论11.1研究背景与意义1 HYPERLINK l bookmark26 o Current Document 1.2线性变换降维方法2主成分分析2

10、1.2.2多维尺度分析31.2.3线性判别分析3独立成分分析4 HYPERLINK l bookmark29 o Current Document 1.3嵌入法51.3.1基于惩罚项的特征选择法51.3.2树模型特征选择法6 HYPERLINK l bookmark32 o Current Document 1.4国内研究综述91.5主要创新点101.6文章结构 10第二章Lasso方法的应用与研究现状12 HYPERLINK l bookmark38 o Current Document Lasse方法概述 12目录 TOC o 1-5 h z HYPERLINK l bookmark41

11、o Current Document Lasso方法应用现状12 HYPERLINK l bookmark44 o Current Document SCAD 13弹性网络13 HYPERLINK l bookmark48 o Current Document 自适应 lasso 14 HYPERLINK l bookmark51 o Current Document Relaxed lasso 15 HYPERLINK l bookmark55 o Current Document Fused lasso 16 HYPERLINK l bookmark59 o Current Documen

12、t Graphical lasso 17 HYPERLINK l bookmark63 o Current Document 树结构 Lass。 17 HYPERLINK l bookmark69 o Current Document 第三章基于Sparse group lasso相关惩罚项的特征选择研究19 HYPERLINK l bookmark72 o Current Document Grouplasso 19 HYPERLINK l bookmark79 o Current Document Sparsegroup lasso 20 HYPERLINK l bookmark83 o

13、Current Document 3.3基于Sparse group lasso的相关惩罚项特征选择法 233.3.1算法步骤273.3.2扩展的线性模型273.3.3数值例子28第四章基于数据共享的Lasso方法30 HYPERLINK l bookmark100 o Current Document 4.1数据丰富型线性回归30 HYPERLINK l bookmark103 o Current Document 4.2数据共享型Lasso 31 HYPERLINK l bookmark106 o Current Document 4.3算法的应用32第五章总结和展望41主要研究 415.

14、2未来的发展方向4143参考文献47致谢表 格 TOC o 1-5 h z CPSGL和SGL在模拟数据上的的均方误差对比29CPSGLR和SGLR在模拟数据上的的均方误差对比 294.1 CPSGL和SGL在电影数据集上的稀疏程度对比33Lasso和岭回归的区别61.2常见的决策树模型8Fused lasso示意图 164.1总体回归效果344.2剧情片模型的系数344.3动作片模型的系数354.4喜剧片模型的系数354.5恐怖片模型的系数364.6各种类型电影共同的系数374.7剧情片部分的系数374.8动作片部分的系数384.9喜剧片部分的系数384.10恐怖片部分的系数39第一章绪论1

15、.1研究背景与意义数据挖掘的概念是第一次在1989年的KDD会议中提出的。经过几十年的 发展，数据挖掘技术已经深入到各行各业了。在如今这个数据社会中，生活中 处处充斥着海量的数据。如何在这些数据中提取出有用的部分进行“物尽其 用”？那么就要进行数据降维了。降维可以分为记录选取和特征选取两个方面。 记录选取较为简单，但是选择恰当的数据对结果也很重要。特征选择是目前研 究很多的一个领域，方法也很多。同时，特征工程在数据挖掘中也是一个至关 重要的环节，找到一组合适的特征，对于结果起着决定性的作用。在开发特征 的过程中，我们总是习惯于尽量多地去找可能影响结果的因素，虽然并不知道 事实上对最后结果是否有

16、影响、有着什么样的影响。然而，过多的特征往往会 造成“维度灾难”，出现过拟合的模型。同时，特征之间可能还存在着某种线 性关系，因此，进行维度的降低、维度的缩减就变得很必要了。本文主要聚焦于用特征选择来做数据降维。特征选择方法可以分为过滤法 (Filter),包装法(Wrapper),混合法(Hybrid)和嵌入法(Embeded)。过滤法按照相关性对各个特征进行评分，设定阈值或者待选择阚值的个数 再来选择特征。过滤法中比较典型的是用相关性来筛选特征，如皮尔森相关 系数、互信息等。包装法根据目标函数，每次选择若干特征，或者排除若干特 征，例如递归特征消除法。嵌入法根据某些机器学习模型来进行特征选

17、择，像 随机森林、SVM、Lasso以及岭回归等回归模型都可以进行特征选择。混合法 即是过滤法和嵌入法的混合，先用过滤方法从原始数据集中过滤出一个候选特 征子集，然后用封装方法从候选特征子集中得到特征子集。本文主要以Sparse group lasso算法为基础，对特征选择的方法进行研究与改进。1.2线性变换降维方法线性降维方法主要是为了寻求某种线性变换，将数据投影到一个低维的空 间上，并且尽可能多地保留数据的特征。1.2.1主成分分析主成分分析(Principal Component Analysis, PCA)是一种应用非常广泛 的数据降维方法，它的目标是通过某种线性投影，将高维的数据映射

18、到低维空 间，在降低数据维度的同时尽量多地保留原来数据的特征。这个算法是1901年 由Karl Pearson作为机械中主轴定理的类似首先引入的川，到了20世纪30年代, Harold Hotelling把它扩展成了一个独立的算法并为其命名。将一个数据矩阵的 协方差矩阵的特征向量按照对应特征值大小排列起来，就是这个矩阵的主成 分。我们把样本数据看作一个矩阵。对任意矩阵X = (X1,X2,.,Xp)t5协方差 矩阵为=(原=E (X - E (X) (X -剧X)有下述定理定理L2.1.设矩阵X协方差矩阵的特征值为人 A2 . Ap 0，对应的单位 正交特征向量为ei,e2,.,ep,则X的第

19、k个主成分为Yk = %Xi + 弘2又2 + . + ekpXp k = 1,2, .p)其中 = （e&i, e*2, ： e 灿），且（A： = 1； 2, .p） /= 1,2, .p）.f var（K） = cck =从cov（H,V；）=成2勺=01.2.2多维尺度分析多维尺度分析(Multi-dimcntional Scaling, MDS)凹也是较早期的一-种 数据降维方法，1958年由Togerson提出。MDS是一种研究多维空间中对象之间 相似性和差异性的一种多元统计方法，旨在将对象投射到一个N维的空间，使 得能够尽量保持对象之间的相对距离不变。MDS可以反映出影响研究对象

20、之间 关系的某个维度。假如有一个距离矩阵D0如0,2勿.001,2涉2,00可以通过这个矩阵计算出点的相对位置距离矩阵X,使得可以通过X反过 来计算距离矩阵与原距离矩阵D差距最小的不相似矩阵K ：=)nxn o MDS的 目标是找到n个向量工1,.,xn e 使得IS - Xje 1. ,n0可以使用不同的范数定义，因此可以得到不同的对(/ = 1,.皿)。可以把MDS看作一个优化问题：minXt (恒 一叼II -知)2i道秘nn k-LDA是为样本寻找一个到低维空间的映射，使得类间方差相对类内方差更 大，也就是要解决ma*四p (佛&k), subject to 伙嵩A 1,强=0,VS

21、/c上面式子中的解及就叫做第k个判别向量。一般来说，有K-1个非平凡判别 向量。可以用淑说代替为来解决这个问题，流是对称矩阵巩的平方根，于 是变为了解一个标准的特征值问题。1.2.4独立成分分析独立成分分析(Independent Component Analysis, ICA)是主成分分析的 一种拓展，它可以只在二阶的独立性上实施，因此定义了正交的方向。独立成 分分析寻找一个能够最小化其成分之间统计独立性的线性变换|巾ICA可以 应用在数据分析与压缩、贝叶斯检测、资源定位、盲定位和解卷积方面。给定数据矩阵知ICA希望学习到一组基向量，它们以列向量的形式构成 矩阵W,满足其特征是稀疏的并且基底

22、正交。ICA的目标函数是：J四）=|W 圳 1 加入标准正交性约束后，相当于求解优化问题：mm|Rx|1; WWT = I这个问题没有简单的解析解，可以使用梯度下降法来求解。1.3嵌入法除了线性变换的方法进行降维之外还可以使用嵌入法。嵌入法主要是使用 机器学习算法和模型计算各个特征对结果的贡献程度，然后按照贡献度的大小 进行特征的选择。随着最近机器学习、人工智能的大热，这种方法也受到了更 大的关注。嵌入法中使用比较广泛的主要包括基于惩罚项的特征选择法和树模 型特征选择法。1.3.1基于惩罚项的特征选择法按照惩罚项的不同，主要有岭回归(ridge regression)和Lasso (Least

23、 Absolute Shrinkage and Selection Operator)方法，分别对应于足和h惩罚项。岭回归又叫吉洪诺夫正则化(Tikhonov regularization),命名于俄罗斯数 学家Andrey Nikolayevich Tikhonov,常用于不适定问题的正规化。它在普通最 小二次回归的基础上加入了范数约束，目标函数可以表示为miny - X/3l +aplLasso和岭回归的区别在于加入的是/范数约束，它的目标函数是min?y - XPW2 + a因为二者使用的范数约束不同，所以得到的效果不同。岭回归旨在把系数 变得更小，有关联的特征系数会被压缩得更相似；而L

24、缺so的目标是使相关性 越低的特征系数越小。图1.1: Lasso和岭回归的区别如图1.1所示，左边是Laso,右边是岭回归，图中红线和蓝色区域的切点 就是目标函数的最优解。当区域为菱形时，我们可以明显看出相比于圆性能更 容易相切到坐标轴上，这也是Lasso更适合用于特征稀疏化的原因闩。1.3.2树模型特征选择法除了基于惩罚项的特征选择法之外，应用比较广泛的特征选择法还有 树模型。最经典的决策树模型是Quinlan在1986年提出的ID3算法回。ID3结 点分裂的标准是信息增益(Information Gain)o设数据集S有s个样本，样 本中所属类别集合C有m个元素G,C2,这m个类别把S分

25、为m个子集S，S2.，Sm,其中样本$中的样本个数为心 则样本集的信息炳为inE(S) = -Pilog2Pii=l其中彷=土设s中某个属性为A, A有n个不同的属性值A把S划分为n个子集S”, s计表示0 = 1,2n)中属于类C(i =)的个数，则吕中属于G的概率为Pij =31 j + $2顼 + * * + smj则子集的信息炳为mE(Sj) = Pijlog2Piji=l故根据属性A划分后的样本集合的信息嫡为E(A) = - s以+ 为：.+”(&)j=lS则划分后的信息增益为gain(A) = E(S) - E(A)简单来说，信息增益就是分类前的信息炳减去分类后的信息嫡。ID3算

26、法存在的缺陷在于会倾向于选择取值较多的特征，而实际并不应该选择这样 的属性。C4.5算法作为ID3的改进版本，采用信息增益率作为结点分裂的标准 7o设样本集S中某个属性为A, A有n个不同属性值化2：.,如，A把S划分 为n个子集Si,曷，则分割信息量为Splitlnfo(A)=n那么信息增益率为GainRatio(A) = 费、 7 Sphtlnfo(A)C4.5还加入了勇枝的过程，避免了出现过拟合的情况。Breinian等人在 1984年提出的回归及分类树(Classification and Regression Trees, CART)卜采用Gini指数作为结点分裂的标准，也是一种应用

27、广泛的 决策树算法。与嫡类似，总体内包含类别的杂乱程度和Gini指数成正比，因此 选择Gini指数最小的属性作为分类属性。对于样本总数为$的样本集S,切是类 别j在S中出现的概率，则样本集S的Gini指数为GiniS) = 1 j对于二分类问题，如果样本集S被某个属性A划分为两部分S和S2,分别具有&和S2个样本。则属性A划分样本集S所得的Gini指数为Gini(A) = Gini(Si) + Gini(S2)ss用树模型进行特征选择的主要思想就是，计算用每个特征进行分裂的标准，这个值越好的特征就是越重要的。如图1.2所示,就是一棵常见的决策树。图1.2：常见的决策树模型随着海量数据的增加以及

28、需求的复杂化，简单的树模型已经不能满足应 用的需要了，于是出现了一系列的集成学习树模型，如随机森林(Random forest )、GBDT (Gradient boosting decision tree )、XGBoost等 * 系列算法。 这些算法可以给特征加上一个重要度的权重，因此可以进行特征选择。 用Python语言编写的Scikit-learn模块可以很方便快速地用这些机器学习算法 做特征选择。1.4国内研究综述国内的研究者们对数据降维也有许多的研究。徐燕等人针对现存方法在文本分类降维时的不足，构造了新的高性能特征 选择函数，提出了一种基于区分类别能力的高性能特征选择方法啊，将其应

29、用 在多个语料集上，和己有的有效方法相比较，取得了更优的效果。李正欣等人针对传统的数据降维方法无法保留多元时间序列主要特征的缺 点，提出了基于共同主成分的多元时间序列降维方法。这种方法通过把各个多 元时间序列向一个公共的低维空间上投影，保持了降维空间的同构性，提高了 降维的有效性诉爪同时，该方法计算复杂度也下降了，具有良好的适用性。何进荣等人在2014年提出的基于边界判别投影的数据降维法，可以提取出 具有判别性能的低维特征。这种有监督的线性变换降维方法的思想和线性判别 分析比较类似，目标都是最小化类内距离，最大化类间距离。边界判别投影可 以很好地保持数据流形的几何结构和判别结构，并且可以降低计

30、算复杂度I爪 而它最大的优点是可以应用于超大数据集。郑思龙等人为了将降维方法更好地应用于信号处理领域，提出了基于字典 学习的非线性降维方法。用这种方法进行降维后的数据，不仅保留了原始信号 的重要特征，还可以很好地恢复出原始信号，而且在噪声较大的情况下，也有 不错的效果冯。张少龙等人借助流形学习的核框架，提出了一种融合局部线性嵌入和等距 映射的非线性降维方法。这种方法既可以保持数据点间的局部邻域关系，又可 以保持数据点间的全局距离关系；巾徐峻岭等人提出了一种基于互信息的无监督特征选择法来达到数据降维的 效果。他们使用综合考虑了相关度和冗余度的特征选择标准来评价特征的重要 度，并且可以同时处理数值

31、型和非数值型的数据。这个方法先计算出每个特征 的相关度，之后再使用向前搜索法对特征进行重要度排序1 lo张振海等人提出的基于信息炳的多标签特征选择算法是应用在分类领域 的，算法的主要思想是采用特征与标签集合的信息增益来衡量一个特征与标签 集合之间的关系，先计算每一个特征与标签集合的信息增益，之后再根据设定 的阈值来选择删除不需要的特征。经过实验验证，这种方法能够提高分类 器的预测能力。1.5主要创新点本文基于Sparse group laso算法，提出了一种改进的特征系数模型。本文 的主要创新点如下：我们目前要处理的数据集往往特征数巨大，针对这个问题，我们 在Sparse group lass

32、o的基础上改进了损失函数，在损失函数中加入了组与组之 间的相关关系惩罚项，以减小模型中特征间的共线性现象，达到进一步稀疏化 系数的目的；考虑到某些具有相同结构的小数据集，如果我们直接用这些数据拟 合一个通用的模型，可能会得到适用性不太高的模型；如果每个小数据集都各 自对应一个模型，这样的计算量会较大。在这样的情况下，我们在数据预处理 时增加一个丰富数据集的步骤，将所有类型的数据以某种方式组合在一起，使 其具有组结构，这样来共同拟合一个模型，使得不仅能得到各组特征各自对结 果的影响，还能得到它们共同产生的影响；将该模型推广到了其余线性模型，同时还将该模型同时应用于模拟 数据和一个真实的电影数据集

33、，解决现实中的问题。1.6文章结构本文的结构如下：第一章为绪论，主要引入了整个问题的背景和研究意义，介绍了国内外研 究情况，并简要概括了本文的主要创新点和文章的结构。第二章主要针对Lasso方法展开叙述，综述了Lasso目前的研究成果和已有 的算法。第三章介绍了新提出的基于Sparse group lasso的相关惩罚项特征选择法, 并给出了算法的解决方法和算法步骤，并以逻辑回归为例子，将算法推广到了 更多的线性模型，并且用模拟数据验证了算法效果。第四章在算法中又加入了一个构造组结构数据集的数据预处理办法，之后 又将新提出的算法应用于一个真实的电影数据集，用MSE和词云来对比新旧算 法的效果。

34、第五章作为结束，总结了目前研究的不足和今后的研究方向。2.1Lasso方法概述Lasso是Tibshirani在1996年提出的模型，它在普通线性回归损失函数的 基础上加入了八惩罚项，以达到将部分和结果不相关特征的系数缩小为零的目 的。Tibshirani在文献时中指出，提高普通线性回归效果的两种技术分别为 子集选择(subset selection)和岭回归(ridge regression)。子集选择的缺点是 其提供的可解释模型可变性太大，数据的一点改变都可以变成一个不同的模 型。而岭回归无法将特征的系数稀疏化，只是会使系数的取值变得平均，将具 有共线性关系特征的系数变得相似。使用Lass

35、。模型得到的特征同时达到了子 集选择以及参数估计的目的，因此应用十分广泛。根据数据结构的不同，又逐 渐演化出 了Fused lasso, Graph lasso, Group lasso 以及树结构Lasso。2.2Lasso方法应用现状考虑普通的线性回归框架。数据由长度为口的响应向量S以及nxp的特征 矩阵X组成。在许多应用中都会出现的情况，这时不能用传统的线性回 归。为了解决这个问题，Tibshirani在损失函数中加入了上范数，即La踞。方法, 即求minWy - X/3l + a/3(2.1)Bradley Efron 等人在2004 年提出的LAR (Least Angle Regr

36、ession)算法 :可以用于得到Lasso的解。Lmso同时可以进行特征选择和参数估计两个过 程，由于其能够得到系数的稀疏表示这一特性，为高维特征稀疏化这一领域提 供了一个很新颖的思想，Lasso在当时引起了很大的关注，但是还是在某些方 面会出现些难以避免的问题。Hui Zou和Trevor Hastie在文献 心中指出，在pn的时候，由于凸优 化问题的性质，最多能选出?2个特征，以及当有一些特征之间相关性较高时, Lasso倾向于只选择其中某一个特征，而不在意选中的具体是哪个特征。SCADFan和Li指出Las$o估计对于绝对值较大的系数压缩过大，可能会造成不必 要的模型偏差，并且推测La

37、sso估计不具有“哲人性质(oracle properties),给 出了一种被简称为SC AD ( Smoothly Clipped Absolute Deviation)的新方法 E* SCAD的惩罚函数定义为(2-2)(2-3)P瑚)=入1(。 入)，for some a 2 and 0SCAD得到的解可以写成S加(z)(|z| -入),(_ l)z_s2gr(z)aA)a-2】2,|z| 2A2A z aX从上面的式子可以看出，解决这个问题有两个未知的参数人和a.在实践 中，我们可以用交叉验证或者广义交叉验证来选择最优的参数。这样的话计算 复杂度较高。这个算法有很强的统计理论背景，并且

38、经过试验证明具有较高的准确率, 计算的时候时间消耗比较少，在有噪声的情况下也表现良好，但是缺陷在于造 成的偏差比较显著。2.2.2弹性网络针对原始Lasso算法的缺陷，Hui Zou等人在2005年提出了弹性网络(Elastic Net)算法18,这个算法能够筛选出一组具有相关性的特征。弹性网络的损失 函数为 TOC o 1-5 h z pP1国X/3腮+入1E |.| +入2尸徘(2.4)，=1顶=1这个过程可以被看作带惩罚项的最小二乘法。设。=人2/(扃+人2)，求上式 的最小解即求优化问题B = argminWy 一 X/3|质，p(2.5)subject to (1 - a) 5 |f

39、t| + oc t for some t，=1j=l其中(1 - a)Iftl + a E-=1度被称作弹性网络惩罚项，这就是La%o和岭回归惩罚项的一个凸组合。弹性网络可以看作是Lasso的一种概化，是一种 拟合与特征提取非常有效的模型。根据文献卜句的结果，弹性网络参数估计的结果有以下定理：定理2.2.1.给定数据(坊X),则弹性网络的参数估计等于B = QTgmin*(X 二f )3 一 2X/3 + %|i容易得出(las so) = argminl3T( 0且Ann(7_1)/2 oo0 则包适应 Lasso 一定满足：I.变量选择的连续性：limnP(A =A) = 12渐近正态，性

40、：据01)攻)f N(W x C)Relaxed lasso针对Lass。在特征数远大于样本数时的稀疏高维数据收敛较慢的缺点， Meinshausen提出了一种Relaxed lasso 网 算法作为改进。假设入 0,oo), (0川n8械=argminpn E(K - X?伊侦人)2 + |问|1(2.7)i=l其中是集合Ma g1,.,p的指示函数Me I,.,p、0, k 4.但项=牛(2.8)Relaxed lasso也可以很容易扩展到其他广义线性模型上。设1(,3)是在参 数白下的负log似然函数，则就是估计州=argminpeMxK/3) + 钏 0lh其中3 e Mx可以理解为和

41、要求及=0, v& t Mx等价。通过实验验证，Relied laBso能生成更加稀疏的模型，而且在高维数据下， 准确度总是不低于传统的方法，并且计算复杂度也更低。经过证实，Relaxed l%so在有许多噪声的条件下，如果参数人和。选择恰当，它的收敛率不会受到噪 声的影响。而这两个参数的选择一般是通过交叉验证来进行的。如图2.1所示, 参数f决定了在特征数何随n增长的收敛率。Fused lassoTibshirani等人在2005年提出的Fused lasso 川方法是针对当特征是按照 某种具有特殊意义的顺序排列起来时的一种算法，这个方法在特征数远大于样 本数时尤其有效，并且经过证实，在基因

42、调控网络推断上的应该效果较好.时。 Fused lasso定义为求解B = argminfiy 一 XP|%(2.9)subject to (1 a)|6si and 2 i ft-i - s2j=lj2第一个约束是为了使系数稀疏化，第二个约束是为了使得相邻的两个特征之间 的差别稀疏化。但是这个方法的缺点就是当数据很多时运算速度很慢。图 2.1: Fused lasso示意图如图2.2所示，在二维的情况下，Fused 1瞬s。就是寻求损失函数平方和的轮 廓第一次满足&|历| = si且为例-妇| = %。Graphical iasso如果数据是图的结构，Meinshausen和Buhlmann

43、提出的基于Lasso的Neighborhood selection方法对于高维图2.?具有良好的计算性能。Neighborhood selection分别估计了图中每个结点的条件独立限制因此也等同于对高斯线性模 型做了变量选择。这个方法对于高维图是连续的，连续性就可以转移到惩罚参 数的选择。考虑一个p维多变量正态分布的随机变量X = （Xi,Xs.,X&N3）其中包括了如Xi作为响应变量，Xk:2k 1,2 1.2,./ 。结点还满足以下条件：(1)来自同一层的结点不重叠，换句话说就是，楣=尹知1 j, k 0,求解1d ni= minxf(x) = -|x- v|2 + 人工词|吃 11(2

44、.12)1=0 j=0将上述的公式记为办(时，这个方法的特点是：无论例)是否光滑，()都是连续可微的；7Fx(&)是个非扩张算子。研究显示，Moreau-Yosida正规化方法对于许多优化算法起到了关键性的 作用。这个方法的效果和效率都非常不错，并且可以应用在许多计算视觉和生 物信息方面。第三章基于Sparse group lasso相关惩罚项的特征选择研究近年来国内外的学者也对Group lasso算法进行了许多研究与应用。针对数 据存在噪声的情况，Elyaderani等人提出了 一个解袂的新思路32。Ochiai等 人将Group lasso应用于最近大热的深度学习框架中33,经过改进的算

45、法能够 成功地选出可以有效进行分类的隐藏层结点。Qingyang Li等人将Group lasso应 用到了阿兹海默症的基因学习中”，由于数据维度较大，现有的算法效率不 高，加入了Group lasso后在疾病的诊断上有着很好的效果，并且这是第一个结 合了Group lasso特征选择法的离散特征选择模型。同时，Group lasso应用在信 用评分上也有较高的准确性，并且可解释性较强3邓Group lasso在许多回归问题中，某个解释变量可能是以一组变量的形式表示的，也就 是说，某些特征在成组出现的时候才具有意义，最典型的应用就是在生物统计 分析中，有的性状是由多个基因控制的，需要多个基因组

46、合在一起表达出某种 性状，这时基因作为特征就是成组出现的。假设特征被分为了m个不同的组, Yuan和Lin (2007)提出的方法Group lasso 11可用来解决这样有分组特征的 回归问题。设有m组的特征，X,.，(时分别为各组特征矩阵，每组特征 数分别为趴,“m。设向1, K为dxd的对称正定矩阵，我们定 义：hll/%,(3.1)/=11=1Yuan和Lin在文献中使用Kj =是P)单位矩阵。则原 问题转化为求： TOC o 1-5 h z ？nm冲2吃阮-对必)脂+ A 面皮)|2(3.2)/I1=1其中X是X的列子矩阵，对应组1的预测变量，伊)是组1的系数向量。这 个方法的稀疏性

47、由调整参数入决定，若每组的特征都只有一个，则变成了普通 的Lgso问题。这种思想同样可以应用到最小角回归(Least Angle Regression, LAR )、 非负garrotte上。这些算法在非组结构的数据上已经有不错的效果了，在进行 这种改进后对于组结构数据的特征选择更是有效。但是这个方法仍然存在一定的缺陷。由于Group lasso给出了稀疏的组 特征，如果模型中包含某一个组的特征，则这个组中所有特征的系数都非 零。作者还指出，虽然Group lasso在结果上表现不错，但是它不是分段线性 的，所以在大数据集上计算量很大。作者将Group lasso和Group LAR、Grou

48、p non-negative garrotte 进行比较，发现Group non-negative garrotte 是计算最快 的一种组结构算法。Sparse group lasso虽然Group lass。给出了稀疏的组特征，但有时我们想要同时满足组内和 组间的稀疏性。举个例子，如果特征是各种基因，同时我们想要识别出某种 基因表达。基于这样的需求，Noah Simon等人于2013年又提出了Sparse group lasso算法I，-1 0若有m组特征数据，Sparse group lasso的损失函数是：-mmmm顽g - E X%脂 + (1 v|/5(i)|2 + aX(3(3.3

49、)!=1其中。 0,1它是Lasso和Group lasso惩罚项的凸组合，这个模型实际上就是最初的Lasso和Group lasso的一个结合。这个模型与Zou和Hastie在2005年 提出的弹性网络模型很类似，只是它的|2惩罚项在零点不可微，所以有些组 的系数可能全部都为零。上式是一个凸函数，所以可以通过次梯度公式来解决 这个优化问题。对于第k个组，优化解摩*）一定满足上乂了厂入）=（1 oi）Xp,十 aXu其中r（T）是y除了第k组之外所有拟合值的残差:门*）= -； X（）lk(3.4)(3.5)砂/H舛|26 (M : |冲2 1)砰)/ 08(蛤=o(3-6)四和分别是肪叫2和

50、|网|1的次梯度Uj =(3-7)可以看出，如果满足(3-8)|5(XWTr/n,A)|2 Jg) for all x and G*(E = J(E3： zjk+i = argminxGkT)4： k = k + l,go on to step 2 if not convergent从G(x)需要满足的条件可以推出J(z/c+i) G大仪L+i) J。人3拾)J(:cQ这样就保证了我们在优化。(z)的过程中也在不停地优化J(z)采用MM算法来最小化Sparse group lasso的损失函数，先假设是一个固定点，满足，（一幻,8） J 1侦（-Bo） + （S - 时丁V, %） + 2|/

51、3 0o|履（3.13）其中t应该足够小，使得二次项在损失函数的Hessian矩阵中占据主导作用。将惩罚项加入其中有M(们=Z(r(_*),0o) + 0 - o)TVZ(7(_jk), 80)1(3-14)+ 旁 115 Ml + (1 。)人 |1列2 + allWIh我们的目标就是要找到一个B来最小化上面的式子，这个问题又等价于M(8) 211 一(为 - ，(尸(_a：o)H3 + (1 。)入11 倒2 +。入|倒1(3.15)Sparse group lasso的算法步骤归纳如下：Algorithm 2 Sparse group lasso算法步骤1： Step 1.(Outer

52、loop) Cyclically iterate through the groups;at each group (k) execute step 22： Step 2.Check if the groups coefficients are identically 0 by seeing if they satisfy|S(X(fc)r?*(_*；), aA)|2 (1 - a)A3： If not,execute step 34： Step 3.(Inner loop) Until convergence iterate:5： e =甜)&沁=竺 Z) =(1 一我;3)场海)+$( -

53、Wi),竺3.3 基于Sparse group lasso的相关惩罚项特征选择法由于现在的数据往往特征数巨大，我们需要进一步地稀疏化系数。基于这种需求，我们提出了基于Sparse group lasso的相关惩罚项特征选择法, 在Sparse group lasso的基础上再加入了 一个惩罚项。设S=(X,g)定义一个数据集，其中y是九x 1的响应向量，X是nxp的预 测矩阵，分为了M个组，n是观测值的数量，p是预测变量数。新提出的损失函 数是：M1=11 M+ 京 E，(视X(W)- X(”)砰他(3.16)M+。人111 + (1 a)X |根()|2Z=1其中(质)是组1和v之间的相关系

54、数的绝对值。使用的解决方法和Simon等人提出的Sparse group lasso的一样，因为损失 函数的改变并不会影响它的一些特性。由于损失函数和Santos等人在文献 :T中提出的有相似之处，可以使用相似的解决方法。针对这样的问题，一般采用近梯度方法(Proximal gradient menthod)2来解决。近梯度方法的优化函数为F(勿)=/(游+，(时其中g(z)是凸函数，六时是可微凸函数，和g(z)是从F(z)分离的函数。先求一个proximal函数pro：Eg(x) = argm嗣如(g3) +- z监)当g(z) = 0时,proxg(x) = Q7，gm诂n(*|n 切分=

55、rr；当g(.Q = A时, pro.Tg(.T)= argminfier(fi - .r|) = R(rr)；当g(z) = t|*lh 时, ?wo.t9(.t)可采 用 soft-thresholding 算法。此时优化问题变成了求解%(抄t 一益/(/T)算法步骤归纳如下：Algorithm 3 proximal gradient算法步骤1： Given ykiXkP 6 (0,1)2： Let A := A*13： repeat4： Let z := proxXg(yk -入/(*)5： break if f(z) Xa、1 1（3.21）0 bXa可微部分f由无惩罚项的损失函数和相

56、关系数惩罚项构成，因此，（3.17）可 以重写为：为+1。：= pmXg(0K)- 珂/农)- proxgbk+1(l) (3.22)(2(位)=见(位)+ (% )(3.23)(仇(鼠=- XSX()(3.24)9 M（:）.扃=/”）T s（X伊）-X（“俨）（3.25）tl=lr（_z）是y的残差：r（T）= g - X（W（3.26）在（3.23）中，以）必（为）和寸（异斗（时分别代表标准的最小二乘项和我们新 加入的相关系数惩罚项。结合公式（3.22） （3.25）,最终的更新公式为：为+1)= (1 -（1 a）人|顷板+尸：赫）|2)+(S(板如入)+(3.27)根据文献,在某个给

57、定的迭代中，如果-，个除了组，之外的残差小于个阈值，那么整个组的参数都为零。这个条件可以写成:|S(X(DR(t), aA)|2 (1 - q)A n 舛)=0(3.28)3.3.1算法步骤我们的解决方法分为组内和组外两部分。对于某个给定的组，我们先用公 式(3.28)进行判断。若成立，则这组的系数全部为0,反之不全为0,我们再进 行接下来的组内迭代部分。具体的算法步骤归纳如下：Algorithm 4 CPSGL算法步骤一1： initialize 为=02： input 夕，X = (X。)，X(2),., XW), A, a, kmax3： for each group Z = 1,2,.

58、, M do do4； if |S(X)，r(_2),s)|2 (1 - ot)X then5： 砰)=06： else7： while number of iterations k 数据共享型Lasso (Data shared lasso) 等。4.1数据丰富型线性回归假设有一个高质量观测值的小数据集，以及一个有成本较低观测值的大数 据集。它们有相似但是不相同的统计特征。Aiyou Chen等人受到谷歌一个应用 的启发，提出了数据丰富型线性回归(Data enriched linear regression) 3lo 他们的小数据集是一组由概率样本选择的消费者，分享了人们的互联网浏览记 录

59、以及电视的观看记录数据。另一组更大的数据集没有经过概率样本选择，但 是加入了数据收集的过程。目标是对来自小数据集的人群做出个预测。如果 数据在两个数据集中的分布是相同的，简单地将这两个数据集合在一起就可以 了。如果大数据集和小的完全不一样，直接将大数据集加入小数据集就是无益 的。Data enriched linear regression是简单将两个数据集合并和分别拟合不同模 型之间的一种混合。使用收缩方法来作为对于两个不同的回归模型之间差别的 惩罚项。使用的惩罚项和调整策略，都显示出这个算法对于小的数据集更感兴 趣，目标是使用来自大数据集的可能有偏差的数据来丰富对小数据的分析。考虑一个响应

60、变量为Y 6 R,预测变量X E踏的线性模型。小数据集的模 型为Yi =+ , i E S假设大数据集的数据服从Yi = X我0 + g) + 勺3 6 B小数据集的样本数量为n，大数据集的样本数量为N。有几类兴趣的出发 点。首先举个例子，S中Y总体来说都和B中的Y有差别，但是有相似的趋势。 也就是说，也许只有t的截距部分是非零的。更普遍地，X中某些但不是所有 的部分的影响可能在两个数据集中是不同的。可以在7的每个部分应用假设检 验，但是计算量巨大。设Xs ee 6 IK%均=X*Xs,Vb = X卷Xb基本的方法是将所有数据合并，再在T上加一个收缩惩罚项。我们就是最小化(焉 一 X*Y +