一种利用Screening加速技巧的Lasso算法

作     者：邱俊洋 潘志松 易磊 陶蔚 张梁梁 QIU Junyang;PAN Zhisong;YI Lei;TAO Wei;ZHANG Liangliang

作者机构：中国人民解放军理工大学指挥信息系统学院南京210007 

出 版 物：《计算机工程与应用》 (Computer Engineering and Applications)

年 卷 期：2018年第54卷第4期

页      面：135-140页

学科分类：08[工学] 081104[工学-模式识别与智能系统] 0811[工学-控制科学与工程] 

基　　金：国家自然科学基金(No.61273296) 江苏省自然科学基金青年基金面上项目(No.BK20140075) 

主　　题：Lasso算法 Screening加速技巧 稀疏特征选择 高维数据 

摘      要：Lasso(Least absolute shrinkage and selection operator)是目前广为应用的一种稀疏特征选择算法。经典的Lasso算法通过对高维数据进行特征选择一定程度上降低了计算开销,然而,求解Lasso问题目前仍面临诸多困难与挑战,例如当特征维数和样本数量非常大时,甚至无法将数据矩阵加载到主存储器中。为了应对这一挑战,Screening加速技巧成为近年来研究的热点。Screening可以在问题优化求解之前将稀疏优化结果中系数必然为0的无效特征筛选出来并剔除,从而极大地降低数据维度,在不损失问题求解精度的前提下,加速稀疏优化问题的求解速度。首先推导了Lasso的对偶问题,根据对偶问题的特性得出基于对偶多面投影的Screening加速技巧,最后将Screening加速技巧引入Lasso特征选择算法,并在多个高维数据集上进行实验,通过加速比、识别率以及算法运行时间三个指标验证了Screening加速技巧在Lasso算法上的良好性能。