特征选择与稀疏学习

徐淼第十一章：特征选择与稀疏学习特征特征描述物体的属性特征的分类相关特征:对当前学习任务有用的属性无关特征:与当前学习任务无关的属性西瓜的特征颜色纹理触感根蒂声音相关特征无关特征好瓜坏瓜当前任务：西瓜是否是好瓜特征选择特征选择从给定的特征集合中选出任务相关特征子集必须确保不丢失重要特征原因减轻维度灾难：在少量属性上构建模型降低学习难度：留下关键信息西瓜的特征颜色纹理触感根蒂声音相关特征无关特征好瓜坏瓜当前任务：西瓜是否是好瓜特征选择：选择当前任务相关特征特征选择的一般方法遍历所有可能的子集计算上遭遇组合爆炸，不可行可行方法产生初始候选子集评价候选子集的好坏基于评价结果产生下一个候选子集两个关键环节：子集搜索和子集评价子集搜索前向搜索：最优子集初始为空集，逐渐增加相关特征后向搜索：从完整的特征集合开始，逐渐减少特征双向搜索：每一轮逐渐增加相关特征，同时减少无关特征用贪心策略选择包含重要信息的特征子集特征集合最优子集特征集合-{𝑎𝑖}最优子集+{𝑎𝑖}从特征集合中选出最优特征𝑎𝑖当前最优子集优于上一轮最优子集？YN结束子集评价特征子集A确定了对数据集D的一个划分每个划分区域对应着特征子集A的某种取值样本标记Y对应着对数据集的真实划分通过估算这两个划分的差异，就能对特征子集进行评价；与样本标记对应的划分的差异越小，则说明当前特征子集越好信息熵是判断这种差异的一种方式常见的特征选择方法常见的特征选择方法大致分为如下三类：过滤式包裹式嵌入式将特征子集搜索机制与子集评价机制相结合，即可得到特征选择方法常见的特征选择方法常见的特征选择方法大致分为如下三类：过滤式先对数据集进行特征选择，然后再训练学习器，特征选择过程与后续学习器无关。先用特征选择过程过滤原始数据，再用过滤后的特征来训练模型。包裹式嵌入式将特征子集搜索机制与子集评价机制相结合，即可得到特征选择方法过滤式选择--Relief算法Relief(RelevantFeatures)方法是一种著名的过滤式特征选择方法。Relief算法最早由Kira提出，最初局限于两类数据的分类问题。Relief算法是一种特征权重算法(Featureweightingalgorithms)，根据各个特征和类别的相关性赋予特征不同的权重（相关统计量），权重小于某个阈值的特征将被移除。Relief算法中特征和类别的相关性是基于特征对近距离样本的区分能力。Relief的关键是如何确定权重（相关统计量）？过滤式选择--Relief算法Relief(RelevantFeatures)方法是一种著名的过滤式特征选择方法。Relief算法算法从训练集D中随机选择一个样本𝒙𝑖，然后从和𝒙𝑖同类的样本中寻找最近邻样本，称为猜中近邻（near-hit）从和𝒙𝑖不同类的样本中寻找最近邻样本，称为猜错近邻（near-miss）然后根据以下规则更新每个特征的权重：如果𝒙𝑖和猜中近邻在某个特征上的距离小于𝒙𝑖和猜错近邻上的距离，则说明该特征对区分同类和不同类的最近邻是有益的，则增加该特征的权重；反之，如果𝒙𝑖和猜中近邻在某个特征的距离大于𝒙𝑖和猜错近邻上的距离，说明该特征对区分同类和不同类的最近邻起负面作用，则降低该特征的权重。以上过程重复m次，最后得到各特征的平均权重。特征的权重越大，表示该特征的分类能力越强，反之，表示该特征分类能力越弱。Relief方法的时间开销随采样次数以及原始特征数线性增长，运行效率很高。过滤式选择--Relief算法的多类拓展Relief算法比较简单，但运行效率高，并且结果也比较令人满意，因此得到广泛应用，但是其局限性在于只能处理两类别数据1994年Kononeill进行了扩展，得到了ReliefF作算法，可以处理多类别问题，用于处理目标属性为连续值的回归问题。ReliefF算法在处理多类问题时，每次从训练样本集中随机取出一个样本𝒙𝑖从和𝒙𝑖同类的样本集中找出𝒙𝑖的k个猜中近邻样本从每个𝒙𝑖的不同类的样本集中均找出k个猜错近邻样本然后，更新每个特征的权重过滤式选择--医学数据分析实例选用的数据：威斯康星州乳腺癌数据集，数据来源美国威斯康星大学医院的临床病例报告，每条数据具有9个属性。数据处理思路：先采用ReliefF特征提取算法计算各个属性的权重，剔除相关性最小的属性，然后采用K-means聚类算法对剩下的属性进行聚类分析。过滤式选择--医学数据分析实例乳腺癌数据集特征提取采用ReliefF算法来计算各个特征的权重，权重小于某个阈值的特征将被移除，针对乳腺癌的实际情况，将对权重最小的2-3种剔除。将ReliefF算法运行20次，得到了各个特征属性的权重趋势图按照从小到大顺序排列，可知，各个属性的权重关系如下：属性9属性5属性7属性4属性2属性3属性8属性1属性6我们选定权重阀值为0.02，则属性9、属性4和属性5剔除。过滤式选择--医学数据分析实例乳腺癌数据特征分析从上面的特征权重可以看出，属性6裸核大小是最主要的影响因素，说明乳腺癌患者的症状最先表现了裸核大小上，将直接导致裸核大小的变化，其次是属性1和属性8等，后几个属性权重大小接近。几个重要的属性进行分析：块厚度属性的特征权重在0.19-25左右变动，也是权重极高的一个，说明该特征属性在乳腺癌患者检测指标中是相当重要的一个判断依据。进一步分析显示，在单独对属性6，和属性1进行聚类分析，其成功率就可以达到91.8%。包裹式选择常见的特征选择方法大致分为如下三类：过滤式包裹式直接把最终将要使用的学习器的性能作为特征子集的评价准则嵌入式将特征子集搜索机制与子集评价机制相结合，即可得到特征选择方法包裹式选择包裹式特征选择的目的就是为给定学习器选择最有利于其性能、“量身定做”的特征子集包裹式选择方法直接针对给定学习器进行优化，因此从最终学习器性能来看，包裹式特征选择比过滤式特征选择更好包裹式特征选择过程中需多次训练学习器，计算开销通常比过滤式特征选择大得多LVW（LasVegasWrapper）是一个典型的包裹式特征选择方法，LVW在拉斯维加斯方法框架下使用随机策略来进行子集搜索，并以最终分类器的误差作为特征子集评价准则包裹式选择--LVWLVW基本步骤在循环的每一轮随机产生一个特征子集在随机产生的特征子集上通过交叉验证推断当前特征子集的误差进行多次循环，在多个随机产生的特征子集中选择误差最小的特征子集作为最终解采用随机策略搜索特征子集，而每次特征子集的评价都需要训练学习器，开销很大。嵌入式选择常见的特征选择方法大致分为如下三类：过滤式特征选择过程与学习器训练过程有明显的分别包裹式嵌入式将特征选择过程与学习器训练过程融为一体，两者在同一个优化过程中完成，在学习器训练过程中自动地进行特征选择将特征子集搜索机制与子集评价机制相结合，即可得到特征选择方法嵌入式选择考虑最简单的线性回归模型，以平方误差为损失函数，并引入L2范数正则化项防止过拟合，则有将L2范数替换为L1范数，则有LASSO[Tibshirani,1996]L2范数和L1范数均有助于降低过拟合风险，但是L1范数易获得稀疏解，即w会有更少的非零分量，是一种嵌入式特征选择方法L1正则化问题的求解可使用近端梯度下降算法岭回归(ridgeregression)[TikhonovandArsenin,1977]稀疏表示将数据集D考虑成一个矩阵，每行对应一个样本，每列对应一个特征。特征选择说考虑的问题是特征具有稀疏性，即矩阵中的许多列与当前学习任务无关，通过特征选择去除这些列，则学习器训练过程仅需在较小的矩阵上进行，学习任务的难度可能有所降低，设计的计算和存储开销会减少，学得模型的可解释性也会提高。矩阵中有很多零元素，且非整行整列出现。稀疏表达的优势：数据具有稀疏性，使得大多数问题变得线性可分稀疏矩阵已有很多高效的存储方法字典学习在一般的学习任务中，数据集（如图像）往往是非稀疏的，能否将稠密表示的数据集转化为“稀疏表示”，使其享受稀疏表达的优势？为普通稠密表达的样本找到合适的字典字典学习在一般的学习任务中，数据集（如图像）往往是非稀疏的，能否将稠密表示的数据集转化为“稀疏表示”，使其享受稀疏表达的优势？为普通稠密表达的样本找到合适的字典，将样本转化为稀疏表示，这一过程称为字典学习给定数据集X，字典学习目标是字典矩阵D以及样本的稀疏向量𝛼字典学习的优化形式为𝛼,D=𝑎𝑟𝑔𝑚𝑖𝑛𝛼𝒙−D𝛼22+𝜆𝛼1采用变量交替优化策略求解字典D和稀疏向量𝛼𝑖固定字典D，为每个样本𝒙𝑖找到对应的𝛼𝑖𝑎𝑟𝑔𝑚𝑖𝑛𝛼𝒙−D𝛼22+𝜆𝛼1以𝛼𝑖为初值，更新字典D𝑚𝑖𝑛D𝒙−D𝛼𝐹2字典学习的解法常用的求解方法有K-SVD核心思想：K-SVD最大的不同在字典更新这一步，K-SVD对误差矩阵𝐄𝑖进行奇异值分解，取得最大奇异值对应的正交向量更新字典中的一个原子，同时并更新其对应的稀疏系数，直到所有的原子更新完毕，重复迭代几次即可得到优化的字典和稀疏系数。压缩感知压缩感知是由美国学者E.Candes和T.Tao于2004年首先提出的。“压缩感知”顾名思义是直接感知压缩后的信息，其目的是从尽量少的数据中提取尽量多的信息。CS理论证明了如果信号在正交空间具有稀疏性（即可压缩性），就能以远低于Nyquist采样频率的速率采样该信号，最后通过优化算法高概率重建出原信号。其基本思想是一种基于稀疏表示的信号压缩和重构技术，也可以称为压缩采样或稀疏采样。压缩感知压缩感知是由美国学者E.Candes和T.Tao于2004年首先提出的。“压缩感知”顾名思义是直接感知压缩后的信息，其目的是从尽量少的数据中提取尽量多的信息。CS理论证明了如果信号在正交空间具有稀疏性（即可压缩性），就能以远低于Nyquist采样频率的速率采样该信号，最后通过优化算法高概率重建出原信号。其基本思想是一种基于稀疏表示的信号压缩和重构技术，也可以称为压缩采样或稀疏采样。压缩感知引起了信号采样及相应重构方式的本质性变化，即：数据的采样和压缩是以低速率同步进行的，这对于降低信息获取系统的采样成本和资源都具有重要意义。由于压缩感知技术突破了传统香农采样定理的限制，其理论研究已经成为应用数学、数字信号处理、数字图像处理等领域的最热门的方向之一，同时其应用领域涉及到图像压缩、医学图像处理、生物信息处理、高光谱影像、地球物理数据分析、压缩雷达、遥感和计算机图像处理等诸多方面。长度为M的离散信号𝒙，用远小于奈奎斯特采样定理的要求的采样率采样得到长度为N的采样后信号𝒚。一般情况下，N≪M，不能利用𝒚还原𝒙，但是若存在某个线性变换Ψ，使得𝒙=Ψ𝜶，即可以近乎完美地恢复𝒙压缩感知关注的问题是如何利用信号本身具有的稀疏性，从部分观测样本𝒚中恢复原始信号𝒙。压缩感知需要解决的三个问题：感知测量（信号的稀疏表示），设计观测矩阵Ф，信号重构技术。压缩感知压缩感知压缩感知的核心问题感知测量信号的最佳稀疏域表示是压缩感知理论应用的基础和前提，只有选择合适的基Ψ表示信号才能保证信号的稀疏度，从而保证信号的恢复精度。涉及到前面介绍的稀疏编码和字典学习。设计观测矩阵Ф信号重构技术压缩感知的核心问题感知测量设计观测矩阵Ф观测矩阵Ф是压缩感知理论采样的实现部分。通过观测矩阵控制的采样使得目标信号𝒙在采样过程中即被压缩，同时保证目标信号所含有效信息不丢失，能够由压缩采样值还原出目标信号。如何设计一个平稳的、与变换基不相关、满足有限等距（RIP，即从观测矩阵中抽取的每M个列向量构成的矩阵是非奇异的）性质的观测矩阵Ф，同时保证稀疏向量从N维降维到M维时重要信息不遭破坏（即信号低速采样问题），是压缩感知的另一个重要研究内容。目前常用的测量矩