《海量数据挖掘-王永利》稀疏支持向量机的安全有效筛选.docVIP

稀疏支持向量机的安全有效筛选 摘要：支持向量机（）鲁棒预测模型，它能够有效的移除并保存信号。它能够一组预先定义的参数来有效的学习一个解，因此模型选择提供了的支持。支持向量机已经被成功应用于包括文本挖掘、生物信息学和图像处理的大量数据挖掘应用中。的出现了一个新的挑战个样本和特征大规模数据的模型选择。在本文中一种新颖的筛选技术来加速化的-SVM的模型选择，并且的提升了它的稳定性。该技术准确确定出一个的最优解下的非活跃特征，并在训练前将它们移除。技术并不同情况下的非活跃特征筛选提供了闭式解。每个所移除的特征都是最优解所得到的非活跃特征。因此当的被该技术所选择的特征时，能够达到使用全部集合的相同结果。因为技术能够移除大量的非活跃特征，所以它能够极大的增加的效率。五个高数据集上的实验结果了所提出技术的 关键字：支持向量机选择 稀疏预测算法强有力的工具来分析高维并产生高度可解释和稳健 性结果5,11]。一般来说化的预测建模算法能够被形式化为这里模型，损失函数，正则化参数来平衡损失和正则项。当损失或者平方形式来用损失函数，产生的稀疏模型就是化的4,18,2,6,16]。一个L1正则的空白最大和软阈值来同时执行模型拟合和噪声特征移除。它成功用于包括文本挖掘、生物信息学和图像处理的大量数据挖掘应用中。其他的15,8,1]，L1正则的两个大的优点。第一个定义了一个凸问题因此不需要对原问题有任何松弛来达到一个最优解。是优化简单的，并且一个良好实现的的能够快速处理千万个样本和特征的大规模问题 正则化参数值一个的至关重要的。为了较好的性能，使用模型选择选择一个合适的。例如给定一系列正则化参数对应的解为这些解可以并且最好的解可以通过预先定义一个准则来选择，例如准确率或者的模型得到的曲线面积 大数据分析需要一个标准来进行预测建模。当海量时，选择的计算代价是应该被禁止的直觉上的问题是第选择的解被用于来加速计算。对asso而言[11]，答案了领先的筛选技术来加速模型选择17,7,14,12,10].关键的思想是给定一个解，可以下的解的特征中具有那些。通过大量的特征，计算代价可以被大大降低。 为asso设计了筛选7]，在L1正则化的只有非常少的研究工作7]提出了一种安全的化的筛选了一种新颖的，用于加速的模型选择。该技术变分不等式一个精致的，它可以被用于计算筛选特征的边界。移技术所除的特征是在最优解下的非活跃的。，筛选是“”。五个高维数据库上的实验结果表明所提出的筛选技术移除大量非活跃特征能够加速化的-SVM。 L1正则化的 假设是一个包含了个样本的数据集，（维度）特征 假设个类别标签，令维权重向量，令个松弛变量为偏置和正则化参数。1正则化的原始形式定义为： ） （）了一个凸规划问题，具有非平滑的，这使得它的解是稀疏的。为给定的式（）最优解。中具有非零值的特征都被称为活跃特征其他被称作活跃特征。令维对偶变量。通过拉格朗日乘子3]，得到（1）对偶问题： ） ，是对角矩阵通过，式（）为： ） 原始的的，原始变量是对偶中，对偶变量。当，获得 （4） 之间的关系为： ） 之间的关系为： ） 式（）使得最小给定，可以通过一个闭式解得到： ） 表示正样本和负样本的数量。当，式（）问题的最优解可以被写为： ） 。进入模型的第一个特征于在具有最大模元素。 的安全筛选 （）了下的一个特征活跃的必要条件。另一方面对于任 意的特征如果则一定是最优解下的非活跃特征。给定的值，这一条件可以被用于开发用于移除特征的筛选规则来加速的训练。这里关键就是计算特征上界一个特征的上界那么它就可以被安全的移除。计算的代价低于训练的因此筛选可以训练前移除大量非活跃特征极大降低计算代价为了的值，必须要一个了闭凸集上界值计算通过在来化 建立凸集 等式3)和变分不等式9]建立一个闭凸集限制命题 优化问题的变分不等式 命题3.1 令为下述凸优化问题一个最优解： 连续可微，闭凸集那么变分不等式成立： 的证明参见9]。 给定，假定有一个并且它对应的解的引入原因是当并且已知时，用于约束一个的紧凸集限制值。 令和分别为定义在式（）问题和下的最优解。，且凸优化问题（）上和分别应用命题结果 （9） ） 在式（9）替换在式（10）替换如下结果： 11） 2） 上述等式中，和是已知的。因此式（）了一个空间而式（）。因为满足两个，所以它居于半空间和超球体的交叠部分。显然这一区域是一个闭凸集，并且它可以被用作。图了二维空间下一个例子。在图中，式（）蓝线的区域，式（）红色圆内的区域，部分表示 除了式（）的球，还可以组合（））导出一系列超球体假设（）最优解，并且验证如下问题的最优解： ） 式（）和下应用可以得到如下