l2, 1-Norm Regularized Discriminative Feature Selection for Unsupervised Learning

Introduction

In many areas, such as computer vision, pattern recognition and biological study, data are represented by high dimensional feature vectors. Feature selection aims to select a subset of features from the high dimensional feature set for a compact and accurate data representation. It has twofold role in improving the performance for data analysis. First, the dimension of selected feature subset is much lower, making the subsequential computation on the input data more efficient. Second, the noisy features are eliminated for a better data representation, resulting in a more accurate clustering and classification result. During recent years, feature selection has attracted much research attention. Several new feature selection algorithms have been proposed with a variety of applications.

Feature selection algorithms can be roughly classified into two groups, i.e., supervised feature selection and unsupervised feature selection. Supervised feature selection algorithms, e.g., Fisher score [Duda et al., 2001] , robust regression [Nie et al., 2010], sparse multi-output regression [Zhao et al., 2010] and trace ratio [Nie et al., 2008], usually select features according to labels of the training data. Because discriminative information is enclosed in labels, supervised feature selection is usually able to select discriminative features. In unsupervised scenarios, however, there is no label information directly available, making it much more difficult to select the discriminative features. A frequently used criterion in unsupervised learning is to select the features which best preserve the data similarity or manifold structure derived from the whole feature set [He et al., 2005; Zhao and Liu, 2007; Cai et al., 2010]. However, discriminative information is neglected though it has been demonstrated important in data analysis [Fukunaga, 1990].

Most of the traditional supervised and unsupervised feature selection algorithms evaluate the importance of each feature individually [Duda et al., 2001; He et al., 2005; Zhao and Liu, 2007] and select features one by one. A limitation is that the correlation among features is neglected [Zhao et al., 2010; Cai et al., 2010]. More recently, researchers have applied the two-step approach, i.e., spectral regression, to supervised and unsupervised feature selection [Zhao et al., 2010; Cai et al., 2010]. These efforts have shown that it is a better way to evaluate the importance of the selected features jointly. In this paper, we propose a new unsupervised feature selection algorithm by simultaneously exploiting discriminative information and feature correlations. Because we utilize local discriminative information, the manifold structure is considered too. While [Zhao et al., 2010; Cai et al., 2010] also select features in batch mode, our algorithm is a one-step approach and it is able to select the discriminative features for unsupervised learning. We also propose an efficient algorithm to optimize the problem.

The Objective Function

In this section, we give the objective function of the proposed Unsupervised Discriminative Feature Selection (UDFS) algorithm. Later in the next section, we propose an efficient algorithm to optimize the objective function. It is worth mentioning that UDFS aims to select the most discriminative features for data representation, where manifold structure is considered, making it different from the existing unsupervised feature selection algorithms.

Denote X = {x1, x2, ..., xn} as the training set, where xi ∈ Rd (1 ≤ i ≤ n) is the i-th datum and n is the total number of training data. In this paper, I is identity matrix. For a constant m, 1m ∈ Rm is a column vector with all of its elements being 1 and Hm = I - 1m 1m1Tm ∈ Rm×m. For an arbitrary matrix A ∈ Rr×p , its ℓ2,1-norm is defined as

Suppose the n training data x1, x2, ..., xn are sampled from c classes and there are ni samples in the i-th class. We define yi ∈ {0, 1}c×1(1 ≤ i ≤ n) as the label vector of xi. The j-th element of yi is 1 if xi belongs to the j-th class, and 0 otherwise. Y = [y1, y2, ..., yn]T ∈ {0, 1}n×c is the label matrix. The total scatter matrix St and between class scatter matrix Sb are defined as follows [Fukunaga, 1990].

where μ is the mean of all samples, μi is the mean of samples in the i-th class, ni is the number of samples in the i-th class, ˜X = XHn is the data matrix after being centered, and G = [G1, ..., Gn]T = Y (Y T Y )-1/2 is the scaled label matrix. A well-known method to utilize discriminative information is to find a low dimensional subspace in which Sb is maximized while St is minimized [Fukunaga, 1990].

Recently, some researchers proposed two different new algorithms to exploit local discriminative information [Sugiyama, 2006; Yang et al., 2010b] for classification and image clustering, demonstrating that local discriminative information is more important than global one. Inspired by this, for each data point xi, we construct a local set Nk(xi) comprising xi and its k nearest neighbors xi1 , ..., xik . Denote Xi = [xi, xi1 , ..., xik ] as the local data matrix. Similar to (2) and (3), the local total scatter matrix S(i) t and between class scatter matrix S (i) b of Nk(xi) are defined as follows.

where ˜ Xi = XiHk+1 and G(i) = [Gi,Gi1 , ...,Gik ]T . For the ease of representation, we define the selection matrix Si ∈ {0, 1}n×(k+1) as follows.

where Fi = {i, i1, ..., ik}. In this paper, it remains unclear how to define G because we are focusing on unsupervised learning where there is no label information available. In order to make use of local discriminative information, we assume there is a linear classifier W ∈ Rd×c which classifies each data point to a class, i.e., Gi = W T xi. Note that Gi,Gi1 , ...,Gik are selected fromG, i.e., G(i) = S T i G. Then we have

It is worth noting that the proposed algorithm is an unsupervised one. In other words, G defined in (7) is the output of the algorithm, i.e., Gi = W T xi, but not provided by the human supervisors. If some rows of W shrink to zero, W can be regarded as the combination coefficients for different features that best predict the class labels of the training data. Next, we give the approach which learns a discriminative W for feature selection. Inspired by [Fukunaga, 1990; Yang et al., 2010b], we define the local discriminative score DSi of xi as

where λ is a parameter and λI is added to make the term ( ˜ Xi ˜X T i + λI ) invertible. Clearly, a larger DSi indicates that W has a higher discriminative ability w.r.t. the datumxi. We intend to train a W corresponding to the highest discriminative scores for all the training data x1, ..., xn. Therefore we propose to minimize (9) for feature selection.

Considering that the data number in each local set is usually small, GT(i)Hk+1G(i) is added in (9) to avoid overfitting. The regularization term ‖W‖2,1 controls the capacity of W and also ensures that W is sparse in rows, making it particularly suitable for feature selection. Substituting DSi in (9) by (8), the objective function of our UDSF is given by

where the orthogonal constraint is imposed to avoid arbitrary scaling and avoid the trivial solution of all zeros. Note that the first term of (10) is equivalent to the following 1 :

Meanwhile we have

Therefore, the objective function of UDFS is rewritten as

1 It can be also interpreted in regression view [Yang et al., 2010a].

where

Denote wi as the i-th row of W, i.e., W = [w1 , ...wd ]T , the objective function shown in (11) can be also written as

We can see that many rows of the optimal W corresponding to (13) shrink to zeros 2 . Consequently, for a datum xi, x′i = W T xi is a new representation of xi using only a small set of selected features. Alternatively, we can rank each feature fi|di=1 according to ∥∥wi∥∥2 in descending order and select top ranked features.

Optimization of UDFS Algorithm

The ℓ2,1-norm minimization problem has been studied in several previous works, such as [Argyriou et al., 2008; Nie et al., 2010; Obozinski et al., 2008; Liu et al., 2009; Zhao et al., 2010; Yang et al., 2011]. However, it remains unclear how to directly apply the existing algorithms to optimizing our objective function, where the orthogonal constraint W T W = I is imposed. In this section, inspired by [Nie et al., 2010], we give a new approach to solve the optimization problem shown in (11) for feature selection. We first describe the detailed approach of UDFS algorithm in Algorithm 1 as follows.

Algorithm 1: The UDFS algorithm.

5 Set t = 0 and initialize D0 ∈ Rd×d as an identity matrix; 6 repeat

• 7 Pt = M + γDt; 8 Wt = [p1, ..., pc] where p1, ..., pc are the eigenvectors of Pt corresponding to the first c smallest eigenvalues;

• 11 until Convergence;
• 12 Sort each feature fi |di=1 according to ∥∥wi t ∥∥2 in descending order and select the top ranked ones.

Below, we briefly analyze Algorithm-1 proposed in this section. From line 1 to line 4, it computes M defined in

2 Usually, many rows of the optimal W are close to zeros.

(12). From line 6 to line 11, it optimizes the objective function shown in (13). Next, we verify that the proposed iterative approach, i.e., line 6 to line 11 in Algorithm 1, converges to the optimal W corresponding to (13). We begin with the following two Lemmas.

Lemma 1. For any two non-zero constants a and b, the following inequality holds [Nie et al., 2010].

Proof. The detailed proof is similar as that in [Nie et al., 2010]. □

Lemma 2. The following inequality holds provided that vi t |ri=1 are non-zero vectors, where r is an arbitrary number [Nie et al., 2010].

Proof. Substituting a and b in (14) by ∥∥vi t+1 ∥∥22 and ∥∥vi t ∥∥22 respectively, we can see that the following inequality holds for any i.

Summing (16) over i, it can be seen that (15) holds □.

Next, we show that the iterative algorithm shown in Algorithm-1 converges by the following theorem.

Theorem 1. The iterative approach in Algorithm 1 (line 6 to line 11) monotonically decreases the objective function value of min W T W=I T r(W T MW ) + γ ∑di=1 ∥∥wi ∥∥2 in each iteration 3 .

Proof. According to the definition of Wt in line 8 of Algorithm 1, we can see that

Therefore, we have

3 When computing Dt+1, its diagonal element dii = 1 2‖wit ‖2 . It is worthy noting that in practice, ∥∥wi t ∥∥2 could be very close to zero but not zero. However, ∥∥wi t ∥∥2 can be zero theoretically. In this case, we can follow the traditional regularization way and define dii = 1 2‖wit‖2+ς , where ς is a very small constant. When ς → 0 it is easy to see that 1 2‖wit‖2+ς approximates 1 2‖wit‖2 .

Then we have the following inequality

Meanwhile, according to Lemma 2, ∑i ∥∥wi t ∥∥2

∑i ‖wi 2‖wi t-1‖2 ≤ ∑i ∥∥wi t-1∥∥2 - ∑i ‖wi 2‖wi t-1‖2 . Therefore, we have the following inequality:

which indicates that the objective function value of min W T W=I T r(W T MW ) + γ ∑di=1 ∥∥wi ∥∥2 monotonically decreases using the updating rule in Algorithm 1. □

According to Theorem 1, we can see that the iterative approach in Algorithm 1 converges to the optimal W corresponding to (13). Because k is much smaller than n, the time complexity of computing M defined in (12) is about O(n2 ). To optimize the objective function of UDFS, the most time consuming operation is to perform eigen-decomposition of Pt. Note that Pt ∈ Rd×d . The time complexity of this operation is O(d3 ) approximately.

Experiments

In this section, we test the performance of UDFS proposed in this paper. Following [He et al., 2005; Cai et al., 2010], we test the performance of the proposed algorithm in terms of clustering.

Experiment Setup

In our experiment, we have collected a diversity of 6 public datasets to compare the performance of different unsupervised feature selection algorithms. These datasets include three face image datasets, i.e., UMIST 4 , FERET 5 and YALEB [Georghiades et al., 2001], one gait image dataset, i.e., USF HumanID [Sarkar et al., 2005], one spoken letter recognition data, i.e., Isolet1 6 and one hand written digit image dataset, i.e., USPS [Hull, 1994]. Detailed information of the six datasets is summarized in Table 1.

We compare UDFS proposed in this paper with the following unsupervised feature selection algorithms.

4 http://images.ee.umist.ac.uk/danny/database.html

5 http://www.frvt.org/FERET/default.htm

6 http://www.ics.uci.edu/ mlearn/MLSummary.html

• All Features which adopts all the features for clustering. It is used as the baseline method in this paper.
• Max Variance which selects the features corresponding to the maximum variances.
• Laplacian Score [He et al., 2005] which selects the features most consistent with the Gaussian Laplacian matrix.
• Feature Ranking [Zhao and Liu, 2007] which selects features using spectral regression.
• Multi-Cluster Feature Selection (MCFS) [Cai et al., 2010] which selects features using spectral regression with ℓ1-norm regularization.

For LS, MCFS and UDFS, we fix k, which specifies the size of neighborhood, at 5 for all the datasets. For LS and FR, we need to tune the bandwidth parameter for Gaussian kernel, and for MCFS and UDFS we need to tune the regularization parameter. To fairly compare different unsupervised feature selection algorithms, we tune these parameters from {10-9, 10-6, 10-3, 1, 103, 106 , 109}. We set the number of selected features as {50, 100, 150, 200, 250, 300} for the first five datasets. Because the total feature number of USPS is 256, we set the number of selected features as {50, 80, 110, 140, 170, 200} for this dataset. We report the best results of all the algorithms using different parameters. In our experiment, each feature selection algorithm is first performed to select features. Then K-means clustering algorithm is performed based on the selected features. Because the results of K-means clustering depend on initialization, it is repeated 20 times with random initializations. We report the average results with standard deviation (std).

Two evaluation metrics, i.e., Accuracy (ACC) and Normalized Mutual Information (NMI), are used as evaluation metrics in this paper. Denote qi as the clustering results and pi as the ground truth label of xi. ACC is defined as follows.

where δ(x, y) = 1 if x = y; δ(x, y) = 0 otherwise, and map(qi) is the best mapping function that permutes clustering labels to match the ground truth labels using the KuhnMunkres algorithm. A larger ACC indicates better performance. Given two variables P and Q, NMI is defined in (19).

where I (P,Q) is the mutual information between P and Q, and H (P ) and H (Q) are the entropies of P and Q [Strehl and Ghosh, 2002]. Denote tl as the number of data in the cluster Cl (1 ≤ l ≤ c) according to clustering results and ˜ th be the number of data in the h-th ground truth class (1 ≤ h ≤ c). NMI is defined as follows [Strehl and Ghosh, 2002]:

where tl,h is the number of samples that are in the intersection between the cluster Cl and the h-th ground truth class. Again, a larger NMI indicates a better clustering result.

Experimental Results and Discussion

First, we compare the performance of different feature selection algorithms. The experiment results are shown in Table 2 and Table 3. We can see from the two tables that the clustering results of All Features are better than those of Max Variance. However, because the feature number is significantly reduced by performing Max Variance for feature selection, resulting in the subsequential operation, e.g., clustering, faster. Therefore, it is more efficient. The results from other feature selection algorithms are generally better than All Features and also more efficient. Except for Max Variance, all of the other feature selection algorithms are non-linear approaches. We conclude that local structure is crucial for feature selection in many applications, which is consistent with previous work on feature selection [He et al., 2005]. We can also see from the two tables that MCFS gains the second best performance. Both Feature Ranking [Zhao and Liu, 2007] and MCFS [Cai et al., 2010] adopt a two-step approach, i.e, spectral regression, for feature selection. The difference is that Feature Ranking analyzes features separately and selects features one after another but MCFS selects features in batchmode. This observation validates that it is a better way to analyze data features jointly for feature selection. Finally, we observe that the UDFS algorithm proposed in this paper obtains the best performance. There are two main reasons for this. First, UDFS analyzes features jointly. Second, UDFS simultaneously utilizes discriminative information and local structure of data distribution.

Next, we study the performance variation of UDFS with respect to the regularization parameter γ in (11) and the number of selected features. Due to the space limit, we use the three face image datasets as examples. The experimental results are shown in Fig.1. We can see from Fig.1 that the performance is not very sensitive to γ as long as it is smaller than 1. However, the performance is comparatively sensitive to the number of selected features. How to decide the number of selected features is data dependent and still an open problem.

Conclusion

While it has been shown in many previous works that discriminative information is beneficial to many applications, it is not that straightforward to utilize it in unsupervised learning due to the lack of label information. In this paper, we have proposed a new unsupervised feature selection algorithm which is able to select discriminative features in batch mode. An efficient algorithm is proposed to optimize the ℓ2,1-norm regularized minimization problem with orthogonal constraint. Different from existing algorithms which select the features which best preserve data structure of the whole feature set, UDFS proposed in this paper is able to select discriminative feature for unsupervised learning. We show that it is a better way to select discriminative features for data representation and UDFS outperforms the existing unsupervised feature selection algorithms.

Acknowledgement

This work is supported by ARC DP1094678 and partially supported by the FP7-IP GLOCAL european project.