Deep Subspace Clustering with Sparsity Prior

1 Introduction

Subspace clustering aims to seek a set of implicit lowdimensional subspaces to fit provided unlabeled highdimensional data and cluster them according to their membership to the subspaces [Vidal, 2011]. During the past decades, spectral clustering based methods [Costeira and Kanade, 1998; Shi and Malik, 2000; Ng et al., 2001] have been state-of-the-art, which perform subspace clustering in following two steps. First, build an affinity matrix (i.e. similarity graph) C to depict the relationship of the data, where Cij denotes the similarity between data points xi and xj. Second, cluster the data through clustering the eigenvectors of the graph Laplacian L = D- 12 AD- 12 , where D is a diagonal matrix with Dii = Pj Aij and A = ♣C♣ + ♣CT ♣. Clearly, performance of spectral clustering based methods critically relies on the quality of the built affinity matrix.

⇤Corresponding Author: Zhang Yi.

In recent years, many works [Nie et al., 2011; Lu et al., 2012; Elhamifar and Vidal, 2013; Liu et al., 2013; Feng et al., 2014; He et al., 2015; Peng et al., 2015; Zhang et al., 2015] have devoted to obtaining a good affinity matrix by using the self-expression of inputs. More specifically, these methods linearly represent the input X 2 Rd⇥n by solving

where d denotes the dimensionality of inputs, n is the data size, C 2 Rn⇥n corresponds to the self-expression of X, k · kF denotes the Frobenius norm, and R(C) denotes a prior structured regularization on C. The major difference among these methods lies in the choice of R(C). For example, sparse subspace clustering (SSC) [Elhamifar and Vidal, 2013] and low rank representation (LRR) [Liu et al., 2013] encourage C to be sparse and low rank by adopting `1- and nuclear-norm as R(·), respectively. Once obtaining C, those methods build an affinity matrix as A = ♣C♣+♣CT ♣ and apply spectral clustering [Ng et al., 2001] over A to cluster data.

Although those approaches have shown encouraging performance, we observe that they suffer from the following limitations. First, most of existing methods strive for building high-quality affinity matrix while ignore the importance of low-dimensional representation derived from the affinity matrix. In fact, most of them simply use several eigenvectors (w.r.t. leading eigenvalues) of L as the low-dimensional representation of data X. This is identical to Laplacian Eigenmap (LE) [Belkin and Niyogi, 2003] in essence. In other words, those spectral clustering based methods perform subspace clustering through 1) building an affinity matrix; 2) performing LE on the affinity matrix to produce low dimensional representations; and 3) clustering the representations. It still remains open whether there is a better way to embed the affinity matrix into low-dimensional spaces and recover the latent subspaces therein, and we believe investigating data embedding schemes in depth will significantly boost the clustering performance. The second limitation of those methods is due to their intrinsic linearity and they cannot handle data with significant non-linearity well. To address this issue, some kernel extensions of existing methods have been proposed, e.g., kernel sparse subspace clustering (KSSC) [Patel and Vidal, 2014] and kernel low rank representation (KLRR) [Xiao et

• (b) Architecture of the proposed PARTY.

Figure 1: Comparison on architectures of PARTY and subspace clustering methods: (a) a popular architectures of existing subspace clustering methods with L being the graph Laplacian and (b) the architecture of PARTY. In (b), H(m) denotes the output of the m-th layer, with m = 1↪ 2↪ · · · ↪M and H(0) denotes inputs. PARTY is complementary to existing subspace clustering methods. Thus, one can directly perform k-means or other existing clustering methods on the compact representationH( M2 ) . The major difference between these two architectures is colored.

al., 2015]. They compute the representation in a kernel space rather than the original space. However, the performance of these kernel based methods heavily relies on the choice of kernel function, while a golden rule for choosing the kernel functions is still absent in practice.

Motivated by the fact that representation learning is vital to the subspace clustering and deep learning is one of the most powerful representation learning approaches [Hinton and Salakhutdinov, 2006; Krizhevsky et al., 2012], we propose a novel subspace clustering framework based on a deep learning model, namely, deeP subspAce clusteRing with sparsiTY prior (PARTY). The proposed method achieves subspace clustering by computing the sparse reconstruction relation from the input space, learning a neural network with locality and globality of data set, and clustering the compact representation learned by our neural network. The basic idea of PARTY is illustrated in Fig. 1. One can observe that PARTY significantly differs from the existing subspace clustering approaches in the following aspects: 1) PARTY directly learns low-dimensional representation of data instead of relying on an affinity matrix; 2) PARTY possesses a multilayer structure, which offers stronger ability to model nonlinearity of the data; 3) Although being partially similar to stacked Auto-Encoder (SAE), PARTY not only considers the locality for reconstructing input data, but also incorporates the structured global prior in representation learning; 4) In contrast to kernel-based methods, PARTY provides explicit transformations and better scalability as it avoids loading all the data to calculate the kernel function; 5) PARTY is compatible with both k-means and most of existing subspace clustering methods. When applying k-means on the outputs of PARTY, we theoretically demonstrate that under mild conditions, PARTY performs in a similar way to spectral clustering. When combined with spectral clustering, PARTY actually performs latent subspace clustering like [Patel et al., 2013], by learning the latent space via hierarchically stacked nonlinear transformations.

2 RelatedWorks

In this section, we briefly discuss some existing works in subspace clustering and deep learning, respectively.

Subspace Clustering: Recently, many subspace clustering methods have been proposed [Elhamifar and Vidal, 2013; Liu et al., 2013; Patel et al., 2013; Patel and Vidal, 2014; Peng et al., 2015; Lu et al., 2012; Favaro et al., 2011; Yuan et al., 2016; Yu et al., 2015; Hu et al., 2014b], of which the major difference is the way to obtain the affinity matrix. More specifically, these methods use the linear reconstruction coefficients to build the affinity matrix, by enforcing different constraints on the coefficients. However, these approaches are linear models, which cannot model the nonlinearity of data in many practical situations. To address this problem, [Patel and Vidal, 2014] and [Xiao et al., 2015] proposed kernel SSC (KSSC) and kernel LRR (KLRR), respectively. However, how to choose appropriate kernel for these kernel-based methods is usually unclear in practice.

Unlike these subspace clustering approaches, our method learns multiple hierarchical nonlinear transformations (in the neural network) to map the input into another space so that the nonlinearity can be incorporated into the obtained lowdimensional representation, thus resulting a better clustering performance. To the best of our knowledge, this is the first deep subspace clustering framework.

Deep Learning: With the impressive power of learning representations, deep learning has achieved huge success in numerous applications, especially in the scenario of supervised learning, e.g. image classification [Krizhevsky et al., 2012], metric learning [Hu et al., 2014b], image super-resolution [Wang et al., 2015], etc. In contrast, less works investigated the applications with unsupervised learning scheme, such as subspace clustering. To the best of our knowledge, there are only two recent works [Ma et al., 2014; Tian et al., 2014] that apply the existing Auto-Encoder (AE) for clustering. They mainly differ in the input of the neural network. Specifically, [Ma et al., 2014] directly encodes the representation from raw data, whereas [Tian et al., 2014] feeds a predefined affinity matrix to the neural network. Due to the absence of comparison with state-of-the-art subspace clustering such as SSC [Elhamifar and Vidal, 2013] and LRR [Liu et al., 2013], it remains unknown whether these two works are relatively effective for subspace clustering. Since unsupervised deep learning remains an open issue, it could be better to incorporate domain knowledge and the merits of previous works to develop new unsupervised deep model as suggested by [Bengio et al., 2013].

Different from these two methods, our framework is based on a new neural network which preserves both locality and globality. To be exact, the locality is considered by minimizing the reconstruction error of the sample itself, while the globality is guaranteed by minimizing the reconstruction error of using the whole data set to reconstruct each sample. Such a framework is complementary to existing subspace clustering methods and deep learning approaches, because it incorporates the advantages (i.e. structure prior) of existing subspace clustering methods into the framework deep learning. As a result, it is well expected that the proposed neural network can achieve satisfactory performance while handling unlabeled data. To our best of knowledge, this is the first work to introduce the global structure prior into neural network for unsupervised learning.

3 Deep Subspace Clustering with Sparsity Prior

In this section, we elaborate on the details of the proposed PARTY model for subspace clustering. PARTY clusters data in the following three steps: computing the sparsity prior from raw data, learning a neural network to map the input into a latent space, and clustering the low-dimensional data representations into multiple subspaces. We will first explain how PARTY is specifically designed for these steps and then present the algorithm for optimizing the PARTY model.

3.1 The DeepModel of PARTY

The neural network within PARTY consists of M + 1 layers for performing M nonlinear transformations, where M is an even number, the first M◁2 hidden layers are encoders to learn a set of compact representation (i.e., dimension reduction) and the last M◁2 layers are decoders to progressively reconstruct the input. For ease of presentation, we first provide the following definitions. Let h(0) i = xi 2 Rd denote one input sample to the first layer and

be the output of the m-th layer, where m = 1↪ 2↪ · · · ↪M indexes the layer of network and g(·) is a nonlinear activation function, dm denotes the dimension of the output at the m-th layer, W(m) 2 Rdm⇥dm-1 and b(m) 2 Rdm denote the weights and bias associated with the m-th layer, respectively. Thus, given xi as the input of the first layer, h(M) i (i.e. the output of the top layer) is the reconstruction of xi, while h( M2 ) i is the desired low-dimensional representation of xi. Furthermore, for a collection of n given samples X = [x1↪ ▷ ▷ ▷ ↪ xn] 2 Rd⇥n , the corresponding outputs of our neural network is denoted by

The objective of PARTY is to minimize the data reconstruction error and simultaneously preserve the global sparsity prior C in the representation learning. With the definitions above, these targets can be formally stated as:

where λ1 and λ2 are positive tradeoff parameters.

The terms ¶Ji♦3i=1 are designed for different goals. Intuitively, the first termJ1 is designed to consider the locality by minimizing the reconstruction errors w.r.t. the input itself. In other words, the input acts as a supervisor to learn a compact representation H( M2 ) . J2 is designed based on the so-called manifold assumption [Roweis and Saul, 2000] which states that the reconstruction relation (e.g., the structure prior) is invariant to different feature spaces. In this paper, we mainly consider the sparsity prior in C = [c1↪ c2↪ · · · ↪ cn] which is obtained by solving the following problem:

where k·k1 denotes the `1-norm that is usually used to achieve sparsity, cii is the i-th entry of the column vector ci, and the constraint avoids the degenerated solution.

With the optimal solution of (5), J2 guarantees the globality because the reconstruction relation over the whole data set is preserved into the hidden representation. Lastly, J3 is a regularization term to avoid over-fitting. Noticed that, the objective (4) with nonlinear function g(·) can intrinsically avoid trivial solutions such as W(m) = [I O] and W(m) = [I O]T where I is an identity matrix and O is an all-zero matrix.

Our neural network model uses the input as self-supervisor to learn compact representation and simultaneously exploits the sparsity prior for ensuring invariance of the underlying manifold (non-linear subspace) structure in the progressively learned representations. The learned representation is fully adaptive to these local and global structures and favorable for the following clustering process.

3.2 Optimization

We now demonstrate how PARTY model can be optimized efficiently via stochastic sub-gradient descent. For convenience of developing the algorithm, we rewrite (4) in the following sample-wise form:

Recall the definition of h(m) i in (2). Applying chain rule, we can express the sub-gradients of (6) w.r.t. W(m) and b(m) as follows:

where ∆(m) is defined as

and ⇤(m) is given by

Here ⊙ denotes element-wise multiplication, g0 (·) is the derivative of the activation function g(·), h(0) i = xi, and z(m) i =W(m)h(m-1) i +b(M) .

Using the stochastic sub-gradient descent algorithm, we update ¶W(m) ↪ b(m) ♦Mm=1 as follows until convergence:

and

where θ > 0 is the learning rate which is typically set to a small value such as 2-10 in our experiments.

Algorithm 1 summarizes the detailed procedure for optimizing PARTY.

Algorithm 1 Deep Subspace Clustering with Sparsity Prior

Input: A given data set X, and the tradeoff parameters λ1, λ2.

Initialize ¶W(m) ↪ b(m) ♦Mm=1, and H0 = X.

// Obtain the sparsity prior:

Compute the sparsity prior C over X via solving (5).

// Optimization:

for m= 1↪ 2 · · · ↪M do

end Do forward propagation to get ¶H(m) ♦Mm=1 via (2).

while not converge do

Randomly select a data point xi and let h0i = xi,

for i = 1↪ 2↪ · · · ↪ n do

for m= 1↪ 2 · · · ↪M do

end Compute h(m)

i via (2).

for m=M↪M -1 · · · ↪ 1 do

end Calculate the gradient using (7)-(10).

for m= 1↪ 2↪ · · · ↪M do

end UpdateW(m) and b(m) via (11)-(12).

end end

// Clustering:

Obtain the segmentation of data by clustering based on H( M2 ) . Output: ¶W(m) ↪ b(m) ♦Mm=1 and the clustering result.

3.3 Implementation Details

In our experiments, we use g = tanh as the activation function which is defined as follows:

and the corresponding derivative is calculated by

Regarding the initialization of ¶W(m) ↪ b(m) ♦Mm=1 , we adopt the pre-training and fine-tuning strategy [Hinton and Salakhutdinov, 2006].

3.4 Connection to PriorWorks

We here provide two ways to understand our proposed PARTY method. Firstly, PARTY can be treated as a general form of the classical Auto-Encoder. Moreover, with several simplifications, PARTY can be deemed as a variant of spectral clustering (SC) algorithms.

Connection between AE and PARTY:

The AE has been widely used in various applications including clustering [Tian et al., 2014; Ma et al., 2014] which use the input as the supervisor to learn a compact representation and then perform kmeans over the representation to obtain the segmentation of data. The proposed PARTY reduces to the the standard AE if λ1 in (4) is set as 0, i.e. without the sparsity prior. In this sense, PARTY augments AE by considering the valuable relations among different samples (i.e. structure prior) and can provide superior performance in the scenario of unsupervised learning as shown in our experiments.

Connection between SC and PARTY:

Most spectral clustering based methods obtain the segmentation of data by performing kmeans on the eigenvectors corresponding to the largest eigenvalues of the Laplacian L as aforementioned.

Remark 1 If we adopt g(z) = z, λ1 ! +1, M = 2 in (4) and add a mild constraint for avoiding trivial solutions, then our learnt compact representation H? will be the solution of

Interestingly, H⇤ is also optimal to

which is exactly the problem of spectral clustering [Ng et al., 2001] but with different choice of L. Specifically, L = C+CT -CCT for our method, whereas L = D- 12AD- 12 (Dii = Pj Aij) for the spectral clustering method.

4 Experiments

In this section, we compare the proposed PARTY with 13 popular subspace clustering methods on several image data sets in terms of 5 evaluation metrics.

4.1 Experimental Settings

Baseline Algorithms: We compare PARTY with SSC [Elhamifar and Vidal, 2013], LRR [Liu et al., 2013], low rank based subspace clustering (LRSC) [Favaro et al., 2011], least square regression (LSR) [Lu et al., 2012], smooth representation clustering (SMR) [Hu et al., 2014a], kernel SSC (KSSC) [Patel and Vidal, 2014], kernel LRR (KLRR) [Xiao et al., 2015], latent subspace sparse subspace clustering (LS3C) [Patel et al., 2013] and stacked sparse autoencoders (SAE) [Ma et al., 2014; Tian et al., 2014]. Among these methods, both KSSC and KLRR have two versions based on the radial basis function / the polynomial function, which are denoted by KSSC1 / KSSC2 and KLRR1 / KLRR2, respectively. LSR has also two variants which are denoted by LSR1 and LSR2. Moreover, we investigate the performance of SAE with the sigmoid function (SAEg) and the saturating linear transfer function (SAEs). For a fair comparison, we adopt the same `1-solver (i.e. the Homotopy solver [Yang et al., 2010]) to achieve sparsity for SSC, KSSC, and our method.

In all experiments, we train the SAE and our PARTY with five layers at which consists of 300-200-150-200-300 neurons. As PARTY is complementary to existing clustering methods, we investigate the performance of PARTY with two clustering methods for an extensive investigation, i.e. kmeans and SSC, where the corresponding methods are denoted by PARTYk and PARTYs. For fair comparisons, we report the best result of all the evaluated methods achieved with their optimal parameters. For our PARTY with the tradeoff parameters, λ1 and λ2. We fix λ2 = 10-3 for all data sets and experimentally choose λ1.

Data Sets: We carry our experiments using three real-world data sets, i.e. Extended Yale database B (YaleB) [Georghiades et al., 2001], COIL20 image data set [Nene et al., 1996], and the BF0502 data set [Sivic et al., 2009]. The used YaleB consists of 2,414 samples from 38 individuals, where each image is with size of 192 ⇥ 168. The COIL20 data set contains 1,440 samples distributed over 20 objects, where each image is with the size of 32 ⇥ 32. The used BF0502 data set [Xiao et al., 2015] contains 1200 facial images detected from the TV series "Buffy the Vampire Slayer", where each category includes 200 samples.

For a comprehensive study, other than the raw data (i.e. gray value), we also extract the following two features from YaleB and COIL20 for evaluations, i.e. dense scale-invariant feature transform (DSIFT) [Lowe, 2004] and the histogram of oriented gradients (HOG) [Dalal and Triggs, 2005]. For computational efficiency, we perform PCA to reduce the feature dimension of all data sets to 300.

Evaluation Criteria: We adopt five metrics to evaluate the clustering quality, i.e. Accuracy, normalized mutual information (NMI), the adjusted rand index (ARI), Precision, and Fscore. Higher value of these metrics indicates better performance. For each data set, we repeat each algorithm five times and report the mean and the standard deviation of these metrics.

4.2 Comparison with State of The Art

In this section, we first evaluate the performance of PARTY on two image databases, i.e. the COIL20 object images and the YaleB facial images. Tables 1 and 2 report the results which show the superiority of our method. 1) On the COIL20, the Accuracy of PARTYs is 2.36% and 4.42% at least higher than that of the other methods regarding to DISFT and HOG. 2) On the YaleB, PARTYs again achieves the best results, of which the Accuracy is 4.78% and 4.14% higher than the second best method w.r.t. these two features. 3) In most cases, PARTYs outperforms PARTYk, which may attribute to that the former performs subspace clustering in the latent space instead of the original space and the latent space is more discriminative than the original one.

4.3 DeepModel vs. ShallowModels

We investigate the performance of our neural network with different depths on the BF0502 data set. Specifically, we report the performance of PARTY with five layers (M = 4) and three layers (M = 2), respectively. In the case of M = 2, the network is with the neurons of 300-150-300. In the experiment, we fix the parameter λ1 of PARTY as 10-2 and 10-3 for M = 2 and M = 4, respectively. Moreover, we report the result of SSC as a baseline.

Fig. 2 shows that a deeper model will bring a better performance to our method. For example, PARTYs4 is 3.75%, 6.05%, 8.59%, 7.87%,7.11% higher than PARTYs2 regarding to Accuracy, NMI, ARI, Precision, and Fscore, respectively. Moreover, PARTYs remarkably outperforms SSC and the advantage is more distinct when a deeper network is built.

4.4 Influence of Activation Functions

In this section, we report the performance of our model with four different activation functions on the YaleB data set. The used activation functions includes tanh, sigmoid, non-saturating sigmoid (nssigmoid), and softplus which is the smooth version of the rectified linear unit (ReLU) [Krizhevsky et al., 2012]. From Fig. 3, we can see that the tanh function outperforms the other three activation functions in the tests and the nssigmoid function achieves the second best result which is very close to the best one.

5 Conclusion

In this paper, we proposed a deep learning based subspace clustering method which simultaneously considers the locality and globality of data set. Extensive experimental results have shown that our method remarkably outperforms 13 state-of-the-art subspace clustering methods in terms of five evaluation metrics. Our deep learning based framework is general and not limited to the sparsity prior. We plan to incorporate other structure priors such as low rank in future.

Acknowledgments

The authors would like to thank the anonymous reviewers for their valuable comments and suggestions to improve the quality of this paper. X. Peng is supported by A*STAR Industrial Robotics Programme - Distributed Sensing and Perception under SERC grant 1225100002, J. Feng is supported by NUS startup grant R263000C08133, and Z. Yi is supported by National Nature Science Foundation of China under grant No. 61432012.