专业企业网站设计网络公司,wordpress 导航标签,手机什么app做网站,vshtml5网站开发机器学习第11章——特征选择与稀疏学习 11.特征选择与稀疏学习11.1子集搜索与评价子集搜索子集评价 11.2 过滤式选择11.3 包裹式选择11.4 嵌入式选择11.5 稀疏表示与字典学习稀疏表示字典学习 11.6 压缩感知 11.特征选择与稀疏学习
11.1子集搜索与评价 特征#xff1a;描述物… 机器学习第11章——特征选择与稀疏学习 11.特征选择与稀疏学习11.1子集搜索与评价子集搜索子集评价 11.2 过滤式选择11.3 包裹式选择11.4 嵌入式选择11.5 稀疏表示与字典学习稀疏表示字典学习 11.6 压缩感知 11.特征选择与稀疏学习
11.1子集搜索与评价 特征描述物体的属性 特征的分类 相关特征:对当前学习任务有用的属性无关特征:与当前学习任务无关的属性 特征选择 从给定的特征集合中选出任务相关特征子集必须确保不丢失重要特征 原因 减轻维度灾难:在少量属性上构建模型降低学习难度:留下关键信息
如果按一般的思想遍历特征的所有可能子集会在计算上遭遇组合爆炸所以可行的方法是子集搜索和子集评价
产生初始候选子集评价候选子集的好坏基于评价结果产生下一个候选子集对其继续进行评价
子集搜索
用贪心策略选择包含重要信息的特征子集
前向搜索最优子集初始为空集逐渐增加相关特征 后向搜索从完整的特征集合开始逐渐减少特征双向搜索每一轮逐渐增加相关特征同时减少无关特征
但这样的子集搜索会可能会导致失去全局最优解的问题这是贪心算法不可避免的
子集评价 特征子集A确定了对数据集D的一个划分每个划分区域对应着特征子集A的某种取值 { D 1 , D 2 , . . . , D V } \{D^1,D^2,...,D^V\} {D1,D2,...,DV} 样本标记Y对应着对数据集的真实划分 通过估算这两个划分的差异就能对特征子集进行评价;与样本标记对应的划分的差异越小则说明当前特征子集越好 信息熵是判断这种差异的一种方式熵越大说明数据越混乱 E n t ( D ) − ∑ i 1 ∣ y ∣ p k log 2 p k Ent(D)-\sum_{i1}^{|y|}p_k\log_2p_k Ent(D)−i1∑∣y∣pklog2pk 信息增益 G a i n ( A ) E n t ( D ) − ∑ v 1 V ∣ D v ∣ ∣ D ∣ E n t ( D v ) Gain(A)Ent(D)-\sum_{v1}^V\frac{|D^v|}{|D|}Ent(D^v) Gain(A)Ent(D)−v1∑V∣D∣∣Dv∣Ent(Dv) 信息增益越大说明这次的划分使数据变得比较规整是有帮助的具体定义和例子见https://blog.csdn.net/m0_53694086/article/details/140758015
将特征子集搜索机制与子集评价机制相结合即可得到特征选择方法过滤式、包裹式、嵌入式
11.2 过滤式选择
先对数据集进行特征选择然后再训练学习器特征选择过程与后续学习器无关。先用特征选择过程过滤原始数据再用过滤后的特征来训练模型。 Relief方法 是一种特征权重算法根据各个特征和类别的相关性赋予特征不同的权重相关统计量权重小于某个阈值的特征将被移除。特征和类别的相关性是基于特征对近距离样本的区分能力。关键在于确定权重相关统计量 算法实现 从训练集D中随机选择一个样本 x i x_i xi然后 从和 x i x_i xi同类的样本中寻找最近邻样本称为猜中近邻 从和 x i x_i xi不同类的样本中寻找最近邻样本称为猜错近邻 然后根据以下规则更新每个特征的权重 如果 x i x_i xi和猜中近邻在某个特征上的距离小于 x i x_i xi和猜错近邻上的距离则说明该特征对区分同类和不同类的最近邻是有益的则增加该特征的权重; 反之如果 x i x_i xi和猜中近邻在某个特征的距离大于 x i x_i xi和猜错近邻上的距离说明该特征对区分同类和不同类的最近邻起负面作用则降低该特征的权重。 以上过程重复m次最后得到各特征的平均权重。 特征的权重越大表示该特征的分类能力越强反之表示该特征分类能力越弱。 Relief方法的时间开销随采样次数以及原始特征数线性增长运行效率很高。
记 猜中近邻 : x i , n h , 猜错近邻 : x i , n m 猜中近邻:x_{i,nh},猜错近邻:x_{i,nm} 猜中近邻:xi,nh,猜错近邻:xi,nm 对第j个特征属性的相关统计量为 δ j ∑ i { − d i f f ( x i j , x i , n h j ) 2 d i f f ( x i j , x i , n m j ) 2 } d i f f ( 表示两点属性值的距离的差异 ) { 两样本属性值相同记为 0 , 否则记为 1 , 属性值为离散型 两样本属性值间的距离 , 属性值为连续型 \delta^j\sum_i\{-diff(x^j_i,x_{i,nh}^j)^2diff(x^j_i,x_{i,nm}^j)^2\}\\ diff(表示两点属性值的距离的差异) \begin{cases} 两样本属性值相同记为0,否则记为1, 属性值为离散型 \\ 两样本属性值间的距离, 属性值为连续型 \\ \end{cases} δji∑{−diff(xij,xi,nhj)2diff(xij,xi,nmj)2}diff(表示两点属性值的距离的差异){两样本属性值相同记为0,否则记为1,两样本属性值间的距离,属性值为离散型属性值为连续型 δ j 0 说明第 j 个特征有益加一定的权重 δ j 0 说明第 j 个特征无益减一定的权重 \delta^j0说明第j个特征有益加一定的权重\\ \delta^j0说明第j个特征无益减一定的权重 δj0说明第j个特征有益加一定的权重δj0说明第j个特征无益减一定的权重 Relief是对二分类问题设计的所以在后来在多分类问题中进行了调整 每次从训练样本集中随机取出一个样本 x i x_i xi 从和 x i x_i xi同类的样本集中找出 x i x_i xi的1个猜中近邻样本 从每个 x i x_i xi的不同类的样本集中均找出k-1个猜错近邻样本 然后更新每个特征的权重 δ j ∑ i − d i f f ( x i j , x i , n h j ) 2 ∑ l ≠ k ( p l × d i f f ( x i j , x i , n m j ) 2 ) p l 为第 l 类样本在数据集 D 中所占的比例 \delta^j\sum_i-diff(x^j_i,x_{i,nh}^j)^2\sum_{l\neq k}\big(p_l\times diff(x^j_i,x_{i,nm}^j)^2\big)\\ p_l为第l类样本在数据集D中所占的比例 δji∑−diff(xij,xi,nhj)2lk∑(pl×diff(xij,xi,nmj)2)pl为第l类样本在数据集D中所占的比例
11.3 包裹式选择
直接把最终将要使用的学习器的性能作为特征子集的评价准则
包裹式特征选择的目的就是为给定学习器选择最有利于其性能、“量身定做”的特征子集包裹式选择方法直接针对给定学习器进行优化因此从最终学习器性能来看包裹式特征选择比过滤式特征选择更好包裹式特征选择过程中需多次训练学习器计算开销通常比过滤式特征选择大得多LVW是一个典型的包裹式特征选择方法LVW在拉斯维加斯方法框架下使用随机策略来进行子集搜索并以最终分类器的误差作为特征子集评价准则LVW基本步骤 在循环的每一轮随机产生一个特征子集在随机产生的特征子集上通过交叉验证推断当前特征子集的误差进行多次循环在多个随机产生的特征子集中选择误差最小的特征子集作为最终解 采用随机策略搜索特征子集而每次特征子集的评价都需要训练学习器开销很大。
11.4 嵌入式选择
过滤式和包裹式的特征选择过程与学习器训练过程有明显的分别而嵌入式将特征选择过程与学习器训练过程融为一体两者在同一个优化过程中完成在学习器训练过程中自动地进行特征选择 算法实现 考虑最简单的线性回归模型以平方误差为损失函数并引入 L 2 范数正则化项 L_2范数正则化项 L2范数正则化项 防止过拟合则有 min w ∑ i 1 m ( y i − w T x i ) 2 λ ∣ ∣ w ∣ ∣ 2 2 \min_w\sum_{i1}^m(y_i-w^Tx_i)^2\lambda||w||^2_2 wmini1∑m(yi−wTxi)2λ∣∣w∣∣22 将 L 2 范数替换为 L 1 范数 L_2范数替换为L_1范数 L2范数替换为L1范数 则有 min w ∑ i 1 m ( y i − w T x i ) 2 λ ∣ ∣ w ∣ ∣ 1 \min_w\sum_{i1}^m(y_i-w^Tx_i)^2\lambda||w||_1 wmini1∑m(yi−wTxi)2λ∣∣w∣∣1 L 2 L_2 L2范数和 L 1 L_1 L1范数均有助于降低过拟合风险但是 L 1 L_1 L1范数易获得稀疏解即w会有更少的非零分量是一种嵌入式特征选择方法 L 1 L_1 L1正则化问题的求解可使用近端梯度下降算法
11.5 稀疏表示与字典学习
稀疏表示
稀疏表示 将数据集D考虑成一个矩阵每行对应一个样本每列对应一个特征。特征选择所考虑的问题是特征具有稀疏性即矩阵中的许多列与当前学习任务无关通过特征选择去除这些列则学习器训练过程仅需在较小的矩阵上进行学习任务的难度可能有所降低设计的计算和存储开销会减少学得模型的可解释性也会提高。矩阵中有很多零元素且非整行整列出现。 稀疏表达的优势: 数据具有稀疏性使得大多数问题变得线性可分稀疏矩阵已有很多高效的存储方法
字典学习 为普通稠密表达的样本找到合适的字典将样本转化为稀疏表示这—过程称为字典学习 采用变量交替优化策略求解 字典 D 和稀疏向量 α i 字典D和稀疏向量\alpha_i 字典D和稀疏向量αi 固定字典D为每个样本 x i x_i xi找到对应的 α i \alpha_i αi a r g min α ∣ ∣ x − D α ∣ ∣ 2 2 λ ∣ ∣ α ∣ ∣ 1 arg \min_{\alpha}||x-D\alpha||^2_2\lambda||\alpha||_1 argαmin∣∣x−Dα∣∣22λ∣∣α∣∣1 以 α i \alpha_i αi为初值更新字典D min D ∣ ∣ x − D α ∣ ∣ F 2 \min_{D}||x-D\alpha||^2_F Dmin∣∣x−Dα∣∣F2 常用的求解方法有K-SVD 核心思想:K-SVD最大的不同在字典更新这一步K-SVD对误差矩阵 E i E_i Ei进行奇异值分解取得最大奇异值对应的正交向量更新字典中的一个原子同时并更新其对应的稀疏系数直到所有的原子更新完毕重复迭代几次即可得到优化的字典和稀疏系数。 ∣ ∣ Y − D X ∣ ∣ F 2 ∣ ∣ Y − ∑ j 1 K d j X F j ∣ ∣ F 2 ∣ ∣ ( Y − ∑ j ≠ k d j X T j ) − f k X T k ∣ ∣ F 2 ∣ ∣ E k − d k X T k ∣ ∣ F 2 ||Y-DX||^2_F\bigg|\bigg|Y-\sum_{j1}^Kd_jX_F^j\bigg|\bigg|^2_F\\ \bigg|\bigg|\bigg(Y-\sum_{j\neq k}d_jX_T^j\bigg)-f_kX^k_T\bigg|\bigg|^2_F\\ ||E_k-d_kX_T^k||^2_F ∣∣Y−DX∣∣F2 Y−j1∑KdjXFj F2 (Y−jk∑djXTj)−fkXTk F2∣∣Ek−dkXTk∣∣F2
11.6 压缩感知
“压缩感知”是直接感知压缩后的信息其目的是从尽量少的数据中提取尽量多的信息。压缩理论证明了如果信号在正交空间具有稀疏性(即可压缩性)就能以远低于奈奎斯特采样频率的速率采样该信号最后通过优化算法高概率重建出原信号。其基本思想是一种基于稀疏表示的信号压缩和重构技术也可以称为压缩采样或稀疏采样。
压缩感知引起了信号采样及相应重构方式的本质性变化即:数据的采样和压缩是以低速率同步进行的这对于降低信息的采样成本和资源都具有重要意又。
由于压缩感知技术突破了传统香农采样定理的限制其理论研究已经成为应用数学、数字信号处理、数字图像处理等领域的最热门的方向之一同时其应用领域涉及到图像压缩、医学图像处理、生物信息处理、高光谱影像、地球物理数据分析、压缩雷达、遥感和计算机图像处理等诸多方面。 长度为M的离散信号x用远小于奈奎斯特采样定理的要求的采样率采样得到长度为N的采样后信号y。一般情况下NM不能利用y还原x但是 若存在某个线性变换Ψ使得x Ψα即可以近乎完美地恢复x压缩感知关注的问题是如何利用信号本身具有的稀疏性从部分观测样本y中恢复原始信号x。压缩感知需要解决的三个问题:感知测量信号的稀疏表示)设计观测矩阵ϕ信号重构技术。 核心问题 感知测量 信号的最佳稀疏域表示是压缩感知理论应用的基础和前提只有选择合适的基Ψ表示信号才能保证信号的稀疏度从而保证信号的恢复精度。涉及到前面介绍的稀疏编码和字典学习。 设计观测矩阵ϕ 观测矩阵ϕ是压缩感知理论采样的实现部分。通过观测矩阵控制的采样使得目标信号x在采样过程中被压缩同时保证目标信号所含有效信息不丢失能够由压缩采样值还原出目标信号。如何设计一个平稳的、与变换基不相关、满足有限等距RIP,即从观测矩阵中抽取的每M个列向量构成的矩阵是非奇异的性质的观测矩阵ϕ同时保证稀疏向量从N维降维到M维时重要信息不遭破坏即信号低速采样问题是压缩感知的另一个重要研究丙容。目前常用的测量矩阵主要有高斯随机矩阵、伯努利随机矩阵二值随机矩阵、局部哈达玛矩阵、局部傅里叶矩阵、Chirp序列、Altop序列、托普利兹矩阵等。 信号重构技术 重构算法是从采样值求解最优化问题寻找到目标信号最优解。 在压缩感知理论中,由于观测值M远小于信号x的长度N因此信号重构的核心在于如何求解欠定方程组 y Φ Ψ x y\Phi\Psi x yΦΨx 如果信号是稀疏或可压缩的且观测矩阵ϕ具有有限等距RIP性质那么从M个观测值中精确恢复信号x是可能的。 信号重构的常用方法: l 0 l_0 l0 范数非凸优化问题贪婪算法如匹配追踪、正交匹配追踪算法等 l 1 l_1 l1范数凸优化问题线性规划方法进行求解如基追踪、梯度投影稀疏重构算法 l p l_p lp范数非凸优化问题:通过p范数优化问题求解来找到信号的“最优”逼近 Bayesian方法基思想是首先合理假设未知的信号系数具有某种稀疏性的先验概率分布然后根据压缩观测信号对未知系数的后验概率分布进行推理。该类方法还能够估计出重构问题的解的误差范围这一优点是传统优化方法所不具备的
