Groups-Keeping Solution Path Algorithm for Sparse Regression with Automatic Feature Grouping
Groups-Keeping Solution Path Algorithm for Sparse Regression with Automatic Feature Grouping
复制标题
DOI：
10.1145/3097983.3098010
复制
发表时间：
2017-08
期刊：
影响因子：
--
通讯作者：
Bin Gu;Guodong Liu;Heng Huang
中科院分区：
文献类型：
--
作者：
Bin Gu;Guodong Liu;Heng Huang
特征选择是数据挖掘最重要的研究课题之一，有着广泛的应用。在实际问题中，特征通常具有组结构来影响结果。因此，自动识别同质特征组对于高维数据分析至关重要。八角形收缩聚类回归算法（OSCAR）是一种重要的稀疏回归算法，它通过1模和成对的1∞模对特征进行自动分组和选择。然而，由于惩罚的过于复杂的表示（特别是成对的r∞范数），到目前为止OSCAR还没有解路径算法，这对调整模型非常有用。为了解决这一挑战，本文提出了一种组保持解路径算法来求解OSCAR模型（OscarGKPath）。给定一组齐次特征组和一个精度界ε， OscarGKPath可以在保持特征组不变的情况下，在正则化参数区间内拟合解。将多个这样的区间组合即可得到整个解路径。证明了OscarGKPath生成的解路径中的所有解都能严格满足给定的精度界ε。在基准数据集上的实验结果不仅证实了我们的OscarGKPath算法的有效性，而且与现有的批处理算法相比，我们的OscarGKPath算法在交叉验证方面具有优势。
Feature selection is one of the most important data mining research topics with many applications. In practical problems, features often have group structure to effect the outcomes. Thus, it is crucial to automatically identify homogenous groups of features for high-dimensional data analysis. Octagonal shrinkage and clustering algorithm for regression (OSCAR) is an important sparse regression approach with automatic feature grouping and selection by ℓ1 norm and pairwise ℓ∞ norm. However, due to over-complex representation of the penalty (especially the pairwise ℓ∞ norm), so far OSCAR has no solution path algorithm which is mostly useful for tuning the model. To address this challenge, in this paper, we propose a groups-keeping solution path algorithm to solve the OSCAR model (OscarGKPath). Given a set of homogenous groups of features and an accuracy bound ε, OscarGKPath can fit the solutions in an interval of regularization parameters while keeping the feature groups. The entire solution path can be obtained by combining multiple such intervals. We prove that all solutions in the solution path produced by OscarGKPath can strictly satisfy the given accuracy bound ε. The experimental results on benchmark datasets not only confirm the effectiveness of our OscarGKPath algorithm, but also show the superiority of our OscarGKPath in cross validation compared with the existing batch algorithm.