ch11特征选择与稀疏学习 周志华ppt课件.ppt
徐淼,第十一章：特征选择与稀疏学习,特征,特征描述物体的属性特征的分类相关特征: 对当前学习任务有用的属性无关特征: 与当前学习任务无关的属性冗余特征*: 其所包含信息能由其他特征推演出来,*为简化讨论，本章暂不涉及冗余特征,例子：西瓜的特征,西瓜的特征,颜色纹理触感根蒂声音,相关特征,无关特征,好瓜,坏瓜,当前任务：西瓜是否是好瓜,特征选择,特征选择从给定的特征集合中选出任务相关特征子集必须确保不丢失重要特征原因减轻维度灾难：在少量属性上构建模型降低学习难度：留下关键信息,例子：判断是否好瓜时的特征选择,西瓜的特征,颜色纹理触感根蒂声音,相关特征,无关特征,好瓜,坏瓜,当前任务：西瓜是否是好瓜,特征选择：选择当前任务相关特征,特征选择的一般方法,遍历所有可能的子集计算上遭遇组合爆炸，不可行可行方法,两个关键环节：子集搜索和子集评价,子集搜索,前向搜索：逐渐增加相关特征后向搜索：从完整的特征集合开始，逐渐减少特征双向搜索：每一轮逐渐增加相关特征，同时减少无关特征,用贪心策略选择包含重要信息的特征子集,特征集合,当前最优子集优于上一轮最优子集？,Y,N,前向搜索,最优子集初始为空集，特征集合初始时包括所有给定特征,结束,子集评价,特征子集确定了对数据集的一个划分每个划分区域对应着特征子集的某种取值样本标记对应着对数据集的真实划分,通过估算这两个划分的差异，就能对特征子集进行评价；与样本标记对应的划分的差异越小，则说明当前特征子集越好,用信息熵进行子集评价,常见的特征选择方法,常见的特征选择方法大致分为如下三类：过滤式包裹式嵌入式,将特征子集搜索机制与子集评价机制相结合，即可得到特征选择方法,过滤式选择,Relief (Relevant Features) 方法 Kira and Rendell, 1992为每个初始特征赋予一个“相关统计量”，度量特征的重要性特征子集的重要性由子集中每个特征所对应的相关统计量之和决定设计一个阈值，然后选择比阈值大的相关统计量分量所对应的特征或者指定欲选取的特征个数，然后选择相关统计量分量最大的指定个数特征如何确定相关统计量？,先用特征选择过程过滤原始数据，再用过滤后的特征来训练模型；特征选择过程与后续学习器无关,Relief方法中相关统计量的确定,Relief方法的多类拓展,Relief方法是为二分类问题设计的，其扩展变体Relief-FKononenko, 1994能处理多分类问题,包裹式选择,包裹式特征选择的目的就是为给定学习器选择最有利于其性能、“量身定做”的特征子集包裹式选择方法直接针对给定学习器进行优化，因此从最终学习器性能来看，包裹式特征选择比过滤式特征选择更好包裹式特征选择过程中需多次训练学习器，计算开销通常比过滤式特征选择大得多,包裹式选择直接把最终将要使用的学习器的性能作为特征子集的评价准则,LVW包裹式特征选择方法,基本步骤在循环的每一轮随机产生一个特征子集在随机产生的特征子集上通过交叉验证推断当前特征子集的误差进行多次循环，在多个随机产生的特征子集中选择误差最小的特征子集作为最终解* *若有运行时间限制，则该算法有可能给不出解,LVW（Las Vegas Wrapper）Liu and Setiono, 1996 在拉斯维加斯方法框架下使用随机策略来进行子集搜索，并以最终分类器的误差作为特征子集评价准则,嵌入式选择,嵌入式特征选择是将特征选择过程与学习器训练过程融为一体，两者在同一个优化过程中完成，在学习器训练过程中自动地进行特征选择,岭回归 (ridge regression) Tikhonov and Arsenin, 1977,易获得稀疏解，是一种嵌入式特征选择方法,等值线即取值相同的点的连线,近端梯度下降（Proximal Gradient Descend，简称PGD）解法Boyd and Vandenberghe, 2004,L1正则化问题的求解(2),L1正则化问题的求解(3),稀疏表示,将数据集考虑成一个矩阵，每行对应一个样本，每列对应一个特征矩阵中有很多零元素，且非整行整列出现稀疏表达的优势：文本数据线性可分存储高效,能否将稠密表示的数据集转化为“稀疏表示”，使其享受稀疏表达的优势？,字典学习,为普通稠密表达的样本找到合适的字典，将样本转化为稀疏表示，这一过程称为字典学习,字典学习的解法(2),为了不破坏 的稀疏性， 仅保留非零元素， 仅保留 与 非零元素的乘积项,压缩感知,数据传输中，能否利用接收到的压缩、丢包后的数字信号，精确重构出原信号？压缩感知 (compressive sensing) Cndes et al., 2006, Donoho, 2006 为解决此类问题提供了新的思路.,能否利用部分数据恢复全部数据？,如傅里叶变换，余弦变换，小波变换等,限定等距性,压缩感知的优化目标和解法,矩阵补全,客户对书籍的喜好程度的评分,“矩阵补全”技术解决此类问题,能否将表中已经通过读者评价得到的数据当作部分信号，基于压缩感知的思想恢复出完整信号从而进行书籍推荐呢？从题材、作者、装帧等角度看（相似题材的书籍有相似的读者），表中反映的信号是稀疏的，能通过类似压缩感知的思想加以处理。,矩阵补全的优化问题和解法,本章小结,
