Scalable and Accurate Online Feature Selection for Big Data
  Feature selection is important in many big data applications. Two critical
challenges closely associate with big data. Firstly, in many big data
applications, the dimensionality is extremely high, in millions, and keeps
growing. Secondly, big data applications call for highly scalable feature
selection algorithms in an online manner such that each feature can be
processed in a sequential scan. We present SAOLA, a Scalable and Accurate
OnLine Approach for feature selection in this paper. With a theoretical
analysis on bounds of the pairwise correlations between features, SAOLA employs
novel pairwise comparison techniques and maintain a parsimonious model over
time in an online manner. Furthermore, to deal with upcoming features that
arrive by groups, we extend the SAOLA algorithm, and then propose a new
group-SAOLA algorithm for online group feature selection. The group-SAOLA
algorithm can online maintain a set of feature groups that is sparse at the
levels of both groups and individual features simultaneously. An empirical
study using a series of benchmark real data sets shows that our two algorithms,
SAOLA and group-SAOLA, are scalable on data sets of extremely high
dimensionality, and have superior performance over the state-of-the-art feature
selection methods.
