Robust Unsupervised Feature Selection

1 Introduction

Data is often represented by high dimensional feature vectors in many areas, such as pattern recognition, text mining, computer vision [Wang et al., 2009a][Wang et al., 2009b], and bio-informatics. In practice, not all features are relevant and important to the learning task, many of them are often correlated, redundant, or even noisy sometimes [Duda et al., ][Huawei et al., 2011], which may result in adverse effects such as over-fitting, low efficiency and poor performance. It is therefore important and necessary to reduce dimensionality. This can be usually achieved by transformation to a low dimensional space [Nie et al., 2010b][Gu et al., 2011] or feature selection. In this paper, we focus on feature selection, which aims to select discriminative and highly related features and eliminate unrelated, redundant, and noisy features with little or no supervision based on certain criteria.

During recent years, feature selection has attracted increasing attention, and many feature selection algorithms have been proposed, which can be grouped into three families: filter, wrapper, and embedded methods. Filter methods [Hall, 1999][Duda et al., ][He et al., 2006][Zhao and Liu, 2007][Masaeli et al., 2010][Huawei et al., 2011][Yang et al., 2011] select a subset of features by leveraging statistical properties of data, and are usually performed before applying classification algorithms. For wrapper methods [Kohavi and John, 1997][Guyon and Elisseeff, 2003][Rakotomamonjy, 2003], feature selection is wrapped in a learning algorithm and the classification performance on selected features is taken as the evaluation criterion. Embedded approaches [Vapnik, 1999][Zhu et al., 2004][Hou et al., 2011] perform feature selection when training the models. Wrapper and embedded methods couples feature selection with built-in classifiers tightly, which lead to less generality and extensive computation. We thus adopt the filter approach in this paper.

From the perspective of label availability, feature selection algorithms can also be classified into supervised feature selection and unsupervised feature selection. Supervised feature selection methods, such as [Duda et al., ][Nie et al., 2010a][Zhao et al., 2010][Nie et al., 2008], are usually able to effectively select good features since labels of training data, which contain the essential discriminative information for classification, can be used. However, in unsupervised scenario, label information is unavailable directly, which makes the task of feature selection more challenging.

Several unsupervised feature selection algorithms are proposed recently. A commonly used criterion in unsupervised feature learning is to select features best preserving data similarity or manifold structure constructed from the whole feature space [He et al., 2006][Zhao and Liu, 2007][Cai et al., 2010], but they fail to incorporate discriminative information implied within data, though it has been shown to be important in data analysis [Fukunaga, 1990]. Earlier unsupervised feature selection algorithms evaluate the importance of each feature individually and select feature one by one [He et al., 2006][Zhao and Liu, 2007], with a limitation that correlation among features is neglected pointed by [Zhao et al., 2010][Cai et al., 2010] which applied two-step approaches, i.e., spectral regression to unsupervised feature selection. State-of-the-arts unsupervised feature selection algorithms perform feature selection by simultaneously exploiting discriminative information and feature correlation. Unsupervised Discriminative Feature Selection (UDFS) [Yang et al.,

2011] aims to select the most discriminative features for data representation, where manifold structure is also considered. However, its orthogonal constraint on the feature selection projection matrix is unreasonable since feature weight vectors are not necessarily orthogonal with each other in nature. Nonnegative Discriminative Feature Selection (NDFS) [Li et al., 2012] performs nonnegative spectral analysis and feature selection simultaneously. One factor that is ignored in both UDFS and NDFS is that data is usually not ideally clean, and outliers or noise often exist in it. UDFS and NDFS are not robust and are vulnerable to outliers or noise. Another deficiency of UDFS and NDFS is that their computation complexity is cubic to the number of features which severely limits their applicability on high dimensional data, e.g., text data and genetic data.

Since the most discriminative information for feature selection is usually encoded in labels, it is very important to predict a good cluster indicators as pseudo labels for unsupervised feature selection [Li et al., 2012]. Another important factor which effects the performance of feature selection is the consideration of outliers and noise [Nie et al., 2010a]. Real data is usually not ideally distributed, outliers and noise often appear in the data, thus it is important or even necessary to consider robustness for unsupervised feature selection.

In light of all these factors, we propose a new unsupervised feature selection algorithm, i.e., Robust Unsupervised Feature Selection (RUFS). We perform robust clustering and robust feature selection simultaneously to select the most important and discriminative features for unsupervised learning. Specifically, cluster indicators are generated by local learning regularized robust nonnegative matrix factorization, which is also a novel robust clustering method itself but we focus on unsupervised feature selection in this paper. Local learning [Gu and Zhou, 2009] is used in robust clustering which incorporates both discriminative information and the geometric structure and is good at clustering data on manifold. We impose an orthogonal constraint on the cluster indicator matrix to ensure that the learned cluster indicators are much closer to the true cluster labels. We then simultaneously perform robust feature selection using learned cluster indicators. RUFS exploits the discriminative information and feature correlation in a joint framework. Aiming at feature selection, joint l2,1 norms minimization is utilized to learn a robust feature selection matrix which is sparse in rows. In order for the proposed RUFS be practical for real world applications, we present a (projected) limited-memory BFGS based iterative algorithm to solve the optimization problem of RUFS. Experiments on different real world datasets show that the RUFS outperforms the state-of-the-arts.

To summarize, the main contributions of this paper include:

• A Robust Unsupervised Feature Selection (RUFS) algorithm is proposed, where robust clustering and robust feature selection are simultaneously performed.
• A local learning regularized robust nonnegative matrix factorization with orthogonal constraint is proposed to learn the pseudo cluster indicator labels, which encodes both discriminative information and the geometric struc-

ture on manifold and eliminate the adverse effect of outliers and noise.

• A (projected) limited-memory BFGS based iterative algorithm is presented to efficiently solve RUFS in terms of both memory cost and computation complexity.

2 Notations and Preliminaries

Throughout this paper, matrices are written as boldface capital letters and vectors are denoted as boldface lowercase letters. For matrixM = (mij), its i-th row, j-th column are denoted by mi ,mj respectively. ‖M‖F is the Frobenius norm of M and Tr [M] is the trace of M if M is square. For any matrixM∈ Rr×t , its l2,1-norm is defined as

Assume that we have n samples X = {xi}ni=1 . Let X = [x1, · · · , xn]T denote the data matrix with each row being a data feature vector, in which xi ∈ Rd is the feature descriptor of the i-th sample. Suppose these n data samples are sampled from c classes and denote Y = [y1, · · · , yn]T ∈ {0, 1}n×c , where yn ∈ {0, 1}c×1 is the cluster indicator vector for sample xi. The scaled cluster indicator matrix [Yang et al., 2011][Li et al., 2012] G is defined as

where gi is the scaled cluster indicator of xi. We thus have

where Ic ∈ Rc×c is an identity matrix.

2.1 Local learning regularization

According to [Bottou and Vapnik, 1992], searching a good predictor f in a global way might not be a good strategy because the function set f (x) may not contain a good predictor for the entire input space. However, it is much easier to produce good predictions on some local regions of the input space and it is usually more effective to minimize prediction cost for each region. [Gu and Zhou, 2009] introduced a good way to construct the local predictors, and we will use it as our local learning regularization term.

Denoting N (xi) as the neighborhood of xi, the local learning regularization aims to minimize the sum of prediction errors between the local prediction from N (xi) and the cluster assignment of xi:

where f k i (xi) is the locally predicted label for k-th cluster from N (xi), λ is a positive parameter, Ki is the kernel matrix defined on the neighborhood of xi, i.e., N (xi), with size of ni, ki is the kernel vector defined between xi and N (xi), gk i is the cluster assignments of N (xi), I ∈ Rn×n is an identity matrix, and A ∈ Rn×n is defined by

3 The Objective Function

In this section, we present the objective function of the proposed Robust Unsupervised Feature Selection (RUFS) algorithm. To select discriminative features for unsupervised learning, learning accurate pseudo cluster labels are very important. NDFS [Li et al., 2012] uses spectral clustering to predict the labels. In this work, however, we propose to utilize local learning regularized robust nonnegative matrix factorization with orthogonal constraint to learn the pseudo cluster labels. The reason is three folds. First, since spectral clustering relies on similarity matrix computed from the original feature space. Thus unrelated or noisy features will have an adverse effect on clustering and henceforth hurt feature selection performance. Although nonnegative matrix factorization [Lee et al., 1999] decomposes the data matrix in the original feature space, the adverse effect will be mainly accumulated in the learned cluster centers and won't hurt the indicators severely. Second, a robust clustering algorithm that considers outliers and noise usually improves the clustering performance [Kong et al., 2011]. Third, researchers [Bottou and Vapnik, 1992][Wu and Scholkopf, 2007][Gu and Zhou, 2009] have shown that local learning is more effective than learning a good predictor in a global way since the function set may not contain a good predictor for the entire input space. Thus we use the local learning regularization to encode the discriminative information and the geometric structure via local predictors, which results in good clustering performance particularly on data embedded on manifold.

Our proposed robust clustering via local learning differs from [Kong et al., 2011] in that local learning is involved during the clustering procedure and standardized orthogonal constraint is imposed on the indicator matrix so that arbitrary scaling and trivial solutions could be avoided and more ideal pseudo cluster labels could be learned.

Given the proposed robust clustering with local learning, RUFS aims to solve the following optimization problem:

where ν, α, β ∈ R+ are parameters. Robust feature selection is performed through jointly minimizing the last two terms (joint l2,1 norms minimization), which is able to handle outliers and noise in data. The l2,1 norm imposed on the feature selection matrix W guarantees the property of sparseness in rows. More specifically, wj shrinks to zero if the j-th feature is less correlated to the pseudo labels G. We can thus filter out the features corresponding to zero rows of Wwhen performing feature selection.

Since Y by definition is a 0 or 1 matrix, the optimization of Eq. (6) is an NP-hard problem [Shi and Malik, 2000]. A commonly used strategy is to relax it to continuous values while keeping the key property, we thus constraint G to be orthonormal by columns, and the original optimization problem is relaxed to

where the first two terms learn the pseudo cluster labels using robust orthogonal nonnegative matrix factorization via local learning regularization while the last two terms simultaneously learn the feature selection matrix by joint l2,1 norms minimization.

By solving optimization problem (7), we learn three components of the robust unsupervised feature selection model, i.e., the pseudo cluster labels G which is very close to the ideal scaled label indicators, the cluster centers F in the original whole feature space, and the feature selection matrix (or projection matrix for regression) Wwhich is sparse in rows.

4 Optimization Algorithm

In the era of big data, high dimensional data is prevalent and the number of features is usually very high (otherwise, we may not need feature selection), for example, text data, genetic data, or image data with high resolution. In such cases, both UDFS and NDFS will be prohibitively slow since they share the computation complexity of O (d3 ) and memory complexity of O (d2 ). For practical use of unsupervised feature selection, we require algorithms to be able to handle large number of features and large number of data samples which are not only computionally efficient but also save memory.

Limited-memory quasi-Newton methods [Nocedal and Wright, 1999] are among the best candidates for solving large scale optimization problems when Hessian matrices cannot be computed at a reasonable cost or are not sparse. These methods maintain simple and compact approximations of Hessian matrices using only a few vectors that represent the approximations implicitly. Despite these modest storage requirements, they often yield an acceptable (albeit linear) rate of convergence. In this section, we present an iterative algorithm to efficiently solve Eq. (7) using L-BFGS [Liu and Nocedal, 1989] and projected L-BFGS [Benson and More, 2001] methods.

To solve RUFS, we first rewrite the optimization problem as follows

where ζ is a parameter to control the orthogonality condition. In practice, ζ should be large enough to insure the orthogonality satisfied. We first define the objective function

denoting

the partial derivatives of L (G,F,W) w.r.t. G,F, and W can be obtained

where ⊗ is the Kronecker product, ⊘ is the element-wise division, and 1 is an all 1 matrix. Solutions of problem (8) satisfy the Kuhn-Tucker conditions

The projection operator

can be helpful because (G∗ ,F∗ ,W∗ ) is a solution of problem (8) if and only if

Given a tolerance τ, an approximate solution to problem (8) is any matrix triplet (G, F,W) such that

In next subsection, we will present a limited-memory BFGS based alternating iterative algorithm to efficiently solve problem (8).

4.1 Limited-memory BFGS

Recall that each step of the BFGS method has the form

where αk is the step length and Hk is the inverse Hessian approximation. Since Hk will generally be dense, the cost of storing and manipulating it is prohibitive when the number of variables is large. To circumvent this problem, limitedmemory BFGS computes a modified version of Hk implicitly by storing a certain number (say, m) of most recent correction pairs using a two-loop recursive procedure to compute the product Hk∇f efficiently [Nocedal and Wright, 1999]. The limited-memory BFGS algorithm can thus be stated formally shown in Algorithm 1. When nonnegative constraints

Algorithm 1 L-BFGS

Input: Staring point x0 and an integer m > 0

k ← 0

repeat

Compute pk ← -Hk∇fk using a two-loop recursion Compute xk+1 ← xk + αkpk, where αk is chosen to satisfy the Wolfe conditions

if k > m then

Discard the vector pair {sk-m, yk-m}

end if

until ‖∇fk‖ ≤ τ

Output: xk

are imposed, a projected version of limited-memory BFGS algorithm is required. There are various projected limitedmemory BFGS algorithms, here we choose BMLVM algorithm [Benson and More, 2001] for its faster speed than LBFGS-B [Byrd et al., 1995] and ease of use.

4.2 RUFS Algorithm

We adopt an alternating optimization (AO) strategy to solve RUFS and list it in Algorithm 3. Following the convergence analysis for a general AO approach, the convergence of Algorithm 3 can be shown to be locally and q-linearly convergent [Bezdek and Hathaway, 2003].

4.3 Complexity Analysis

The two-loop recursion scheme requires O(4tmdc) for computing W and F and O(4tmnc) for computing G, so we have O(4tm(2d + n)c) scaler multiplications where t is the total number of inner iterations of Algorithm 3. According to Eq. (10) ∼ Eq. (12), computing partial gradients w.r.t. W, F, and G are tG ∗ O(3ndc + cn2 ), tF ∗ O(2ndc), and tW ∗ O(2ndc) respectively, where tA is the total number of inner iterations of Algorithm 3 computing matrix A. Evaluation of objective function values requires about #lineSearchIter ∗ O(2ncd + 2cn2 ). Note that the O(cn2 ) part is inevitable due to the local learning regularization term (UDFS and NDFS also share the O(cn2 ) part due to local discriminative analysis). The computation of projection operation can be ignored compared to the computation of gradients and objective function values because only boolean operations are performed. The memory complexity of RUFS is O(n2 )+O(c2 )+O(nc)+O(dc)+O(nd) ∼ O(n2 )+O(nd), which is dominated by O(n2 ) when data matrix is sparse (e.g., for text data). Note that both UDFS and NDFS require O(d2 ) +O(n2 ) memory cost and O(d3 ) +O(cn2 ) computation complexity, which will be prohibitively slow when d the original feature size is very large.

Algorithm 2 BMLVM

Input: Staring point x0 and an integer m > 0 k ← 0 repeat Compute pk ← -Hk∇fk using a two-loop recursion if 〈TΩ (Hk∇fk) , ∇fk〉 > 0 then pk ← -TΩ (Hk∇fk) elsepk ← -TΩ∇fk end if Compute xk+1 ← [xk + αkpk]+, where αk is chosen to satisfy the Wolfe conditions if k > m then Discard the vector pair {sk-m, yk-m} end if Save sk ← xk+1 - xk, yk ← TΩ∇fk+1 - TΩ∇fk k ← k + 1 until ‖TΩ∇fk‖ ≤ τ Output: xk

Algorithm 3 RUFS

Input: X ∈ Rn×d , ν, α, β, c, and p

Construct L from Eq. (4) Initialize G0 (e.g., by K-means) Initialize F0 ← [(GTG)-1 GTX]+ Initialize W0 k ← 0 repeat Fixing Gk, computeWk+1 from Algorithm 1 given Gk, Wk, α, β Fixing Fk andWk+1, compute Gk+1 from Algorithm 2 given Gk, Fk, Wk+1L, ν, and α Fixing Gk+1, compute Fk+1 from Algorithm 2 given Gk+1, Fk

Output: Sort all d features according to ‖wjk ‖2 in descending order and select the top p ranked features.

5 Experiments

In this section, we conduct experiments to evaluate RUFS. Following previous unsupervised feature selection work [Cai et al., 2010][Yang et al., 2011][Li et al., 2012], we only evaluate the performance of RUFS for feature selection on clustering due to space limit.

5.1 Datasets

The evaluation is performed on 6 benchmark real world datasets including ORL (AT&T) 1 , COIL20 2 , Binary Alphadigits 3 , UMIST 4 , Isolet1 5 , and WebKB4 [Gu and Zhou, 2009]. Detailed information is summarized in Table 1.

5.2 ComparedMethods

We compare RUFS with the following unsupervised feature selection algorithms.

1. Baseline: All original features are adopted.
2. LS: Laplacian Score [He et al., 2006] which selects features that best preserve the local manifold structure.
3. MCFS: Mutli-Cluster Feature Selection [Cai et al., 2010] where features are selected using spectral regression with l1-norm regularization.
4. UDFS: Unsupervised Discriminative Feature Selection [Yang et al., 2011] which exploits local discriminative information and feature correlations simultaneously and considers the manifold structure as well.
5. NDFS: Nonnegative Discriminative Feature Selection [Li et al., 2012] where features are selected by a joint framework of nonnegative spectral analysis and l2,1-norm regularized regression.

5.3 Experiment Setup

Following previous work, two widely used evaluation metrics, i.e., Accuracy (ACC) and Normalized Mutual Information (NMI) are used in this paper.

There are some parameters to be set. Following previous work, for LS, MCFS, UDFS, NDGS, and RUFS, we fix k = 5 for all the datasets to specify the neighborhood size. To fairly compare different unsupervised feature selection methods, we tune the parameters for all methods by a "grid-search" strategy from {10-6 ,10-4 , . . . , 104 , 106}. The number of selected features are set as {50, 100, 150, . . . 300} for all datasets. Best clustering results from the optimal parameters are reported for all the algorithms. In the evaluation, we use K-means to cluster samples based on the selected features. Since K-means depends on initialization, following previous work, we repeat clustering 20 times with random initialization for each setup. The average results with standard deviation are reported.

1 http://www.cl.cam.ac.uk/research/dtg/attarchive/facedatabase.html

2 http://www.cad.zju.edu.cn/home/dengcai/Data/MLData.html

3 http://www.cs.nyu.edu/∼roweis/data.html

4 http://www.sheffield.ac.uk/eee/research/iel/research/face

5 http://archive.ics.uci.edu/ml/datasets/ISOLET

5.4 Results and Discussion

We list the experimental results of different methods in Table 2 and Table 3. We observe from the clustering results that feature selection is important and effective. Not only can number of features be significantly reduced which makes posterior processing more efficient, but clustering performance can also be greatly improved. A new observation is that robust analysis is important for unsupervised learning. Consideration of outliers and noise usually improves the performance of feature selection, which has also been observed in supervised scenario. At last, RUFS achieves the best performance. This can be mainly explained by the following reasons. First, joint learning is performed between robust label learning and robust feature selection. Second, local learning is exploited which results in more accurate pseudo labels. Third, outliers and noise are considered during processes of both label learning and feature learning, so that more accurate and discriminative pseudo labels can be obtained.

We also study the sensitiveness of parameters. Due to space limit, we only report the results on BinaryAlphadigits dataset with ν = 10 (sensitiveness under other values of ν is similar) on Figure 1. The experimental results show that our method is not very sensitive to α and β with wide ranges. However, the performance is relatively sensitive to the number of selected features, which is still an open problem.

We finally compare the running time of UDFS, NDFS, and RUFS in Table 4 on COIL20 and WebKB4 datasets (other datasets have either a smaller sample size or a smaller feature size). The calculations are performed using an Intel(R) Core(TM) i7 CPU M620 @ 2.67GHz with 4.00GB memory and 64-bit Windows 7 operating system. The empirical results in Table 4 are consistent with the theoretical analysis.

6 Conclusion

We propose a new robust unsupervised feature selection approach called RUFS, which jointly performs robust label learning via local learning regularized robust orthogonal nonnegative matrix factorization and robust feature learning via joint l2,1-norms minimization. To make RUFS be applicable for large scale feature selection tasks, we present a (projected) limited-memory based iterative algorithm to solve it. Experimental results on different real world datasets validate the effectiveness of the proposed method.

Acknowledgments

This material is based upon work supported by the National Science Foundation under Grant Number CNS-1027965.