# Subspace Clustering with Sparsity and Grouping Effect

Authors: Binbin Zhang; Weiwei Wang; Xiangchu Feng
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

Subspace clustering aims to group a set of data from a union of subspaces into the subspace from which it was drawn. It has become a popular method for recovering the low-dimensional structure underlying high-dimensional dataset. The state-of-the-art methods construct an affinity matrix based on the self-representation of the dataset and then use a spectral clustering method to obtain the final clustering result. These methods show that sparsity and grouping effect of the affinity matrix are important in recovering the low-dimensional structure. In this work, we propose a weighted sparse penalty and a weighted grouping effect penalty in modeling the self-representation of data points. The experimental results on Extended Yale B, USPS, and Berkeley 500 image segmentation datasets show that the proposed model is more effective than state-of-the-art methods in revealing the subspace structure underlying high-dimensional dataset.


---

## Body

## 1. Introduction

Many high-dimensional datasets such as face images, motion trajectories, and text can be well approximated by multiple low-dimensional subspaces [1]. Recovering the low-dimensional structure underlying these datasets leads to the subspace clustering problem. It aims to group a set of data from a union of subspaces into the subspace (or cluster) from which it was drawn. It has shown promising applications in face clustering [2], motion segmentation [3], image segmentation [4], and system identification [5].LetX=[x1,…,xn]∈Rd×n be a set of sufficient sampled data vectors, whereX is the data matrix with each column corresponding to a data point, d is the feature dimension, and n is the number of data vectors. Assume that the data points are drawn from a union of k subspaces Sii=1k of unknown dimensions, respectively. Subspace segmentation aims to cluster the data into the underlying subspace from which they are drawn. Figure 1 presents an example of the subspace clustering problem.Figure 1
An example of subspace clustering.


### 1.1. Related Works

Most recent works focus on the spectral clustering-based methods [6–12]. They first learn an affinity matrix capturing the similarity between pairs of sample points from the dataset and then use a spectral clustering method such as the normalized cut (Ncut) [13] to obtain the final clustering result. The affinity matrix is generally learnt by using the self-representation of the dataset under the assumption that each data point can be approximated by a linear or affine combination of other data points. To ensure that the affinity matrix has some expected properties, the previous methods [6–12] solve the following minimization problem:(1)minZ,EZp+λEqs.t.X=XZ+E,diagZ=0,where Zp is a proper norm of the representation matrix Z=z1,…,zn=Zij∈Rn×n and is used to enforceZ to have expected property, Eq measures the error matrixE, noise, or corruption, and λ is a tradeoff parameter. The constraint diagZ=0 is optional and it is used to avoid the trivial solution. Once the optimal solution Z∗ of (1) is obtained, it is used to construct the affinity matrixA. By the theory of spectral clustering, the affinity matrix which measures the similarity between data points should be nonnegative and symmetrical. A commonly used definition is(2)A=Z∗+Z∗T2,where · denotes the element-wise absolute value of the matrix Z∗. The method of sparse subspace clustering (SSC) [6, 7] pursues the sparsest representation for each data point by using the l1-norm regularization. Low-rank representation (LRR) [2, 8] seeks for the lowest-rank representation of all data points by employing the nuclear norm · of the coefficient matrix, which can capture the global structures of the data. Least square regression (LSR) [9] uses the Frobenius norm regularization. The correlation adaptive subspace segmentation (CASS) [10] uses the trace Lasso defined by Xdiag⁡z∗ to regularize each column ofZ to gain a tradeoff effect between l1-norm and l2-norm depending on the correlation of data points. In particular, when the data are highly correlated (i.e., XTX is close to 11T), it is close to the l2-norm, while when the data are almost uncorrelated (i.e., XTX is close to I), it behaves like the l1-norm. The smooth representation (SMR) [11] and SSC with the weighting function (W-SSC) [12] use the spatial information to design the regularization term ofZ to improve the clustering results.The previous works pursue two properties of the self-representation and the resulting affinity matrix to ensure the success of subspace clustering. SSC [6, 7] and W-SSC [12] pursue sparsity. LRR [2], LSR [9], CASS [10], and SMR [11] are shown to have the grouping effect (GE, Definition 1), which tend to encourage clustering highly correlated data together. Under some ideal conditions, sparsity results in zero connection between data points from different subspaces and tends to group them into different clusters. However, SSC has the instability problem: if the data from the same subspace are highly correlated or clustered, it will only select one of the several related pieces of data at random and ignore other correlated data. Moreover, the datasets in practice not necessarily satisfy the ideal conditions. These limit the performance of SSC. W-SSC compresses the coefficients corresponding to data points spatially far away from the data in consideration by introducing a weight depending on the spatial distance between data points. However, SSC and W-SSC do not take the GE into consideration and both have the instability problem. LRR [2], LSR [9], CASS [10], and SMR [11] have the GE but they are insufficient in enforcing the sparsity.


### 1.2. Contributions

In this work, we pursue both sparsity and grouping effect in modeling the self-representation of data points. Specifically, for the representation vectorzj of a data point xj, the sparsity is enforced by minimizing the l1-norm of coefficients only corresponding to data which is far away from xi. We also seek for GE by enforcing close representation vector for close data.We present an algorithm based on the Alternating Direction Method of Multipliers (ADMM) to solve our model and two subproblems have analytical solution.We test our method on the face dataset Extended Yale B and handwritten digit dataset USPS. The experimental results show that the proposed model is more effective than state-of-the-art methods in revealing the cluster structure underlying these high-dimensional datasets. We also test our method on Berkeley 500 image segmentation dataset for image segmentation; both the visual segmentation effects and segmentation metrics show that our method is better than state-of-the-art methods.


## 1.1. Related Works

Most recent works focus on the spectral clustering-based methods [6–12]. They first learn an affinity matrix capturing the similarity between pairs of sample points from the dataset and then use a spectral clustering method such as the normalized cut (Ncut) [13] to obtain the final clustering result. The affinity matrix is generally learnt by using the self-representation of the dataset under the assumption that each data point can be approximated by a linear or affine combination of other data points. To ensure that the affinity matrix has some expected properties, the previous methods [6–12] solve the following minimization problem:(1)minZ,EZp+λEqs.t.X=XZ+E,diagZ=0,where Zp is a proper norm of the representation matrix Z=z1,…,zn=Zij∈Rn×n and is used to enforceZ to have expected property, Eq measures the error matrixE, noise, or corruption, and λ is a tradeoff parameter. The constraint diagZ=0 is optional and it is used to avoid the trivial solution. Once the optimal solution Z∗ of (1) is obtained, it is used to construct the affinity matrixA. By the theory of spectral clustering, the affinity matrix which measures the similarity between data points should be nonnegative and symmetrical. A commonly used definition is(2)A=Z∗+Z∗T2,where · denotes the element-wise absolute value of the matrix Z∗. The method of sparse subspace clustering (SSC) [6, 7] pursues the sparsest representation for each data point by using the l1-norm regularization. Low-rank representation (LRR) [2, 8] seeks for the lowest-rank representation of all data points by employing the nuclear norm · of the coefficient matrix, which can capture the global structures of the data. Least square regression (LSR) [9] uses the Frobenius norm regularization. The correlation adaptive subspace segmentation (CASS) [10] uses the trace Lasso defined by Xdiag⁡z∗ to regularize each column ofZ to gain a tradeoff effect between l1-norm and l2-norm depending on the correlation of data points. In particular, when the data are highly correlated (i.e., XTX is close to 11T), it is close to the l2-norm, while when the data are almost uncorrelated (i.e., XTX is close to I), it behaves like the l1-norm. The smooth representation (SMR) [11] and SSC with the weighting function (W-SSC) [12] use the spatial information to design the regularization term ofZ to improve the clustering results.The previous works pursue two properties of the self-representation and the resulting affinity matrix to ensure the success of subspace clustering. SSC [6, 7] and W-SSC [12] pursue sparsity. LRR [2], LSR [9], CASS [10], and SMR [11] are shown to have the grouping effect (GE, Definition 1), which tend to encourage clustering highly correlated data together. Under some ideal conditions, sparsity results in zero connection between data points from different subspaces and tends to group them into different clusters. However, SSC has the instability problem: if the data from the same subspace are highly correlated or clustered, it will only select one of the several related pieces of data at random and ignore other correlated data. Moreover, the datasets in practice not necessarily satisfy the ideal conditions. These limit the performance of SSC. W-SSC compresses the coefficients corresponding to data points spatially far away from the data in consideration by introducing a weight depending on the spatial distance between data points. However, SSC and W-SSC do not take the GE into consideration and both have the instability problem. LRR [2], LSR [9], CASS [10], and SMR [11] have the GE but they are insufficient in enforcing the sparsity.


## 1.2. Contributions

In this work, we pursue both sparsity and grouping effect in modeling the self-representation of data points. Specifically, for the representation vectorzj of a data point xj, the sparsity is enforced by minimizing the l1-norm of coefficients only corresponding to data which is far away from xi. We also seek for GE by enforcing close representation vector for close data.We present an algorithm based on the Alternating Direction Method of Multipliers (ADMM) to solve our model and two subproblems have analytical solution.We test our method on the face dataset Extended Yale B and handwritten digit dataset USPS. The experimental results show that the proposed model is more effective than state-of-the-art methods in revealing the cluster structure underlying these high-dimensional datasets. We also test our method on Berkeley 500 image segmentation dataset for image segmentation; both the visual segmentation effects and segmentation metrics show that our method is better than state-of-the-art methods.


## 2. Self-Representation with Sparsity and Grouping Effect

### 2.1. Modeling

LetGj be the set of indices i such that xi and xj are drawn from the same subspace or cluster and consider the representation zj=Z1jZ2j⋯ZnjTZjj=0 (the jth column ofZ) for the data xj:(3)xj=Xzj=∑iZijxi=∑i∈GjZijxi+∑i∉GjZijxiTo make zero connection between data points from different subspaces, only ∑i∉GjZij should be minimized; here Zij denotes the absolute value of Zij. However, in the scenario of subspace clustering, Gj is unknown in advance. SSC pursues sparsity by minimizing ∑i≠jZij=∑i∈GjZij+∑i∉GjZij. So it is possible for SSC to make Zij=0 if i∈Gj and cause the instability problem. It is also possible that Zij≠0 if i∉Gj, thus causing a nonzero connection between clusters. W-SSC compresses the coefficient Zij corresponding to the data points xi by introducing a weight depending on the spatial distance between xi and xj. However, SSC and W-SSC do not take the GE into consideration and both have the instability problem.In [11], the authors define the following “grouping effect.” The works in [9–11] confirm that the grouping effect tends to group highly correlated data into the same cluster and experiments show that the grouping effect improves the clustering results on several commonly used datasets [14, 15].Definition 1 (grouping effect [11]).
Given a set ofd-dimensional data points X=[x1,…,xn]∈Rd×n, a subspace representation matrix Z=[z1,…,zn]∈Rn×n has grouping effect if zi-zj2→0 whenever xi-xj2→0, ∀i≠j.Taking both the sparsity and GE into consideration of the self-representation of a data point, we propose to solve the following minimization problem:(4)minzj∑iSijZij+λ2∑iWijzi-zj22s.t.xj=Xzj,zjj=0,with(5)Wi,j=1,ifxi∈NKxjorxj∈NKxi0,otherwiseSi,j=1-Wi,j,where NK(xi) denotes the set of K-nearest neighbors of xi and W is the K-nn graph of the dataset. The first term ∑iSijZij only minimizes the coefficients corresponding to the data points that are not connected. The second term enforces close representation vectors for connected close data. These two terms enforce the representation matrix and the resulting affinity matrix to have both sparsity and GE. The sparsity encourages grouping data from different subspaces into different clusters and the GE encourages grouping highly correlated data together.Considering that1/2∑i,jWijzi-zj22=trZTLZ, where L=D-W, andD is a diagonal matrix with diagonal entries Dii=∑jWij and collecting problem (5) for all data points, we have the following problem:(6)minZS⊙Z1+λtr⁡ZTLZ,s.t.X=XZ,diagZ=0,where ⊙ denotes the element-wise product of two matrices. In case of noisy or corrupted data, we reformulate the problem as(7)minZ,ES⊙Z1+λtr⁡ZTLZ+βEls.t.X=XZ+E,diagZ=0,where the parameters λ>0 and β>0 are tuning parameters to balance the effect of the corresponding terms. The constraint diag(Z)=0 enforces that each data point be represented as a linear combination of other data points.


### 2.2. Minimization Algorithm

To solve problem (7), we first convert it into the following equivalent problem:(8)minZ,C,ES⊙Z1+λtr⁡CTLC+βEls.t.X=XC+E,C=Z-diagZ.We solve this problem by using the Alternating Direction Method of Multipliers (ADMM) [16]. The augmented Lagrangian [17] is given by(9)minZ,C,E,Y1,Y2LZ,C,E,Y1,Y2=S⊙Z1+λtr⁡CTLC+βEl+μ2X-XC-E+Y1μF2+C-Z+diagZ+Y2μF2,where Y1 and Y2 are matrices of Lagrange multipliers and μ>0 is a parameter. To find a saddle point for L, we update each of Z, C, E, Y1, and Y2 alternatively while keeping the other variables fixed.Update for
Z. We updateZ as follows:(10)Zt+1=argmin⁡Z⁡1μtS⊙Z1+12Z-diagZ-UtF2,where Ut=Ct+Y2t/μt; the solution for (10) is(11)Zt+1=Z¯-diagZ¯and Z¯ can be solved by using the soft-thresholding operator:(12)Z¯ij=sgnUijtmax⁡Uijt-Sijμt,0.Update for
C. We updateC as follows:(13)Ct+1=argmin⁡C⁡λtr⁡CTLC+μt2X-XC-Et+Y1tμtF2+C-Zt+diagZt+Y2tμtF2.This is a smooth convex program and the optimal solution condition is(14)AC+CB=D,where A=μtXTX+I, D=μtXTX-XTEt+Zt-diagZt+XTY1t-Y2t, and B=2λL. Equation (14) is a standard Sylvester equation [18], which has one unique solution.Update for
E. We updateE as follows:(15)Et+1=argmin⁡E⁡βEl+μt2X-XCt-E+Y1tμtF2.Here we usel1-norm or squared Frobenius norm to handle corruptions or noise. If l1-norm is used, the solution for (15) is(16)Eijt+1=sgn⁡X-XCt+Y1tμtijmax⁡X-XCt+Y1tμtij-βμt,0.If squared Frobenius norm is used, the solution is(17)Et+1=2β+μt-1μtX-μtXCt+Y1t.Update for
Y
1
and
Y
2. We update Y1 and Y2 as follows:(18)Y1t+1=Y1t+μtX-XCt-EtY2t+1=Y2t+μtCt-Zt+diagZt.The update for the Lagrange multipliers is a simple gradient descent step.The procedure for solving problem (7) is outlined in Algorithm 1. When the optimal solution Z∗ of problem (7) is obtained, we use (2) to construct the affinity matrixA and normalize each column vector ofA by dividing the maximum value of that column. Finally, the spectral clustering method is applied to obtain the clustering results. The computation burden is mainly focused on Algorithm 1. Let k denote the number of iterations and let the matrixX have size d×n. The complexity of updatingZ,E, and the multipliers Y1 and Y2 is, respectively, On2, Odn2, Odn2, and On2. In the process of updatingC, we used the Bartels-Stewart algorithm [18] to solve the Sylvester equation; the algorithm has a computational complexity of On3. So the total computational complexity is Okn2+kdn2+kn3. Assuming that d≤n, the complexity is O(kn3).Algorithm 1:Solving problem (7) by ADMM.
Input: data matrix X, model parameters λ and β and K.
Initialization:  Z0=C0=Y10=Y20=0, μ0=0.1,
μ
m
a
x
=
1
0
10, t=0, ρ=1.1, ε=10-5.
Output: the optimal coefficient matrix Z∗.
While not convergedo
(1) fix others and updateZ by Eq. (11) and (12);
(2) fix others and updateC by solving Eq. (14);
(3) fix others and updateE by Eq. (16) or (17);
(4) update the Lagrangian Multipliers:
Y1t+1=Y1t+μtX-XCt-Et
Y2t+1=Y2t+μtCt-Zt+diagZt
(5) update the parameterμ by μt+1=min⁡μmax,ρμt;
(6) check the convergence conditions
X-XCt-Et∞<ε
Ct-Zt+diag(Zt)∞<ε
(7)t=t+1;
end while


## 2.1. Modeling

LetGj be the set of indices i such that xi and xj are drawn from the same subspace or cluster and consider the representation zj=Z1jZ2j⋯ZnjTZjj=0 (the jth column ofZ) for the data xj:(3)xj=Xzj=∑iZijxi=∑i∈GjZijxi+∑i∉GjZijxiTo make zero connection between data points from different subspaces, only ∑i∉GjZij should be minimized; here Zij denotes the absolute value of Zij. However, in the scenario of subspace clustering, Gj is unknown in advance. SSC pursues sparsity by minimizing ∑i≠jZij=∑i∈GjZij+∑i∉GjZij. So it is possible for SSC to make Zij=0 if i∈Gj and cause the instability problem. It is also possible that Zij≠0 if i∉Gj, thus causing a nonzero connection between clusters. W-SSC compresses the coefficient Zij corresponding to the data points xi by introducing a weight depending on the spatial distance between xi and xj. However, SSC and W-SSC do not take the GE into consideration and both have the instability problem.In [11], the authors define the following “grouping effect.” The works in [9–11] confirm that the grouping effect tends to group highly correlated data into the same cluster and experiments show that the grouping effect improves the clustering results on several commonly used datasets [14, 15].Definition 1 (grouping effect [11]).
Given a set ofd-dimensional data points X=[x1,…,xn]∈Rd×n, a subspace representation matrix Z=[z1,…,zn]∈Rn×n has grouping effect if zi-zj2→0 whenever xi-xj2→0, ∀i≠j.Taking both the sparsity and GE into consideration of the self-representation of a data point, we propose to solve the following minimization problem:(4)minzj∑iSijZij+λ2∑iWijzi-zj22s.t.xj=Xzj,zjj=0,with(5)Wi,j=1,ifxi∈NKxjorxj∈NKxi0,otherwiseSi,j=1-Wi,j,where NK(xi) denotes the set of K-nearest neighbors of xi and W is the K-nn graph of the dataset. The first term ∑iSijZij only minimizes the coefficients corresponding to the data points that are not connected. The second term enforces close representation vectors for connected close data. These two terms enforce the representation matrix and the resulting affinity matrix to have both sparsity and GE. The sparsity encourages grouping data from different subspaces into different clusters and the GE encourages grouping highly correlated data together.Considering that1/2∑i,jWijzi-zj22=trZTLZ, where L=D-W, andD is a diagonal matrix with diagonal entries Dii=∑jWij and collecting problem (5) for all data points, we have the following problem:(6)minZS⊙Z1+λtr⁡ZTLZ,s.t.X=XZ,diagZ=0,where ⊙ denotes the element-wise product of two matrices. In case of noisy or corrupted data, we reformulate the problem as(7)minZ,ES⊙Z1+λtr⁡ZTLZ+βEls.t.X=XZ+E,diagZ=0,where the parameters λ>0 and β>0 are tuning parameters to balance the effect of the corresponding terms. The constraint diag(Z)=0 enforces that each data point be represented as a linear combination of other data points.


## 2.2. Minimization Algorithm

To solve problem (7), we first convert it into the following equivalent problem:(8)minZ,C,ES⊙Z1+λtr⁡CTLC+βEls.t.X=XC+E,C=Z-diagZ.We solve this problem by using the Alternating Direction Method of Multipliers (ADMM) [16]. The augmented Lagrangian [17] is given by(9)minZ,C,E,Y1,Y2LZ,C,E,Y1,Y2=S⊙Z1+λtr⁡CTLC+βEl+μ2X-XC-E+Y1μF2+C-Z+diagZ+Y2μF2,where Y1 and Y2 are matrices of Lagrange multipliers and μ>0 is a parameter. To find a saddle point for L, we update each of Z, C, E, Y1, and Y2 alternatively while keeping the other variables fixed.Update for
Z. We updateZ as follows:(10)Zt+1=argmin⁡Z⁡1μtS⊙Z1+12Z-diagZ-UtF2,where Ut=Ct+Y2t/μt; the solution for (10) is(11)Zt+1=Z¯-diagZ¯and Z¯ can be solved by using the soft-thresholding operator:(12)Z¯ij=sgnUijtmax⁡Uijt-Sijμt,0.Update for
C. We updateC as follows:(13)Ct+1=argmin⁡C⁡λtr⁡CTLC+μt2X-XC-Et+Y1tμtF2+C-Zt+diagZt+Y2tμtF2.This is a smooth convex program and the optimal solution condition is(14)AC+CB=D,where A=μtXTX+I, D=μtXTX-XTEt+Zt-diagZt+XTY1t-Y2t, and B=2λL. Equation (14) is a standard Sylvester equation [18], which has one unique solution.Update for
E. We updateE as follows:(15)Et+1=argmin⁡E⁡βEl+μt2X-XCt-E+Y1tμtF2.Here we usel1-norm or squared Frobenius norm to handle corruptions or noise. If l1-norm is used, the solution for (15) is(16)Eijt+1=sgn⁡X-XCt+Y1tμtijmax⁡X-XCt+Y1tμtij-βμt,0.If squared Frobenius norm is used, the solution is(17)Et+1=2β+μt-1μtX-μtXCt+Y1t.Update for
Y
1
and
Y
2. We update Y1 and Y2 as follows:(18)Y1t+1=Y1t+μtX-XCt-EtY2t+1=Y2t+μtCt-Zt+diagZt.The update for the Lagrange multipliers is a simple gradient descent step.The procedure for solving problem (7) is outlined in Algorithm 1. When the optimal solution Z∗ of problem (7) is obtained, we use (2) to construct the affinity matrixA and normalize each column vector ofA by dividing the maximum value of that column. Finally, the spectral clustering method is applied to obtain the clustering results. The computation burden is mainly focused on Algorithm 1. Let k denote the number of iterations and let the matrixX have size d×n. The complexity of updatingZ,E, and the multipliers Y1 and Y2 is, respectively, On2, Odn2, Odn2, and On2. In the process of updatingC, we used the Bartels-Stewart algorithm [18] to solve the Sylvester equation; the algorithm has a computational complexity of On3. So the total computational complexity is Okn2+kdn2+kn3. Assuming that d≤n, the complexity is O(kn3).Algorithm 1:Solving problem (7) by ADMM.
Input: data matrix X, model parameters λ and β and K.
Initialization:  Z0=C0=Y10=Y20=0, μ0=0.1,
μ
m
a
x
=
1
0
10, t=0, ρ=1.1, ε=10-5.
Output: the optimal coefficient matrix Z∗.
While not convergedo
(1) fix others and updateZ by Eq. (11) and (12);
(2) fix others and updateC by solving Eq. (14);
(3) fix others and updateE by Eq. (16) or (17);
(4) update the Lagrangian Multipliers:
Y1t+1=Y1t+μtX-XCt-Et
Y2t+1=Y2t+μtCt-Zt+diagZt
(5) update the parameterμ by μt+1=min⁡μmax,ρμt;
(6) check the convergence conditions
X-XCt-Et∞<ε
Ct-Zt+diag(Zt)∞<ε
(7)t=t+1;
end while


## 3. Experiments and Analysis

In this section, we evaluate the performance of the proposed method on several publicly available datasets, including Extended Yale B face dataset [14], the handwritten digits dataset USPS [15], and Berkeley 500 image segmentation dataset [19]. We also compare our method with several state-of-the-art methods: SSC [7], LRR [2], LSR [9], CASS [10], and SMR [11]. We use the source codes provided by the authors and tune the parameters of each method to achieve the best performance for fair comparison. We define the affinity matrix by using (2).For the Extended Yale B and USPS datasets, we use the subspace clustering error to evaluate the performance of the methods:(19)error=NerrorNtotal,where Nerror denotes the number of misclassified points and Ntotal denotes the total number of points. For the Berkeley 500 image segmentation dataset, three metrics for comparing pairs of image segmentations are used: PRI (probabilistic rand index) [20], VOI (variation of information) [21], and GCE (global consistency error) [22]. The value of PRI is within [0,1] and the higher value shows the better segmentation performance. The value of VOI is within [0,+∞) and the lower value shows the better segmentation performance. The value of GCE is within [0,1] and the lower value shows the better performance.


### 3.1. Datasets and Experimental Settings

Extended Yale B. Extended Yale B is a face dataset that consists of 192×168-pixel cropped face images of 38 human subjects under varying poses and illuminations. Each subject has 64 frontal faces. To reduce the computational cost and memory requirements of all algorithms, each face image is downsampled to 32×32 pixels and rearranged into a 1024-dimensional vector. To study the effect of the number of subjects on the clustering performance of different methods, we divide the 38 subjects into four groups: 1 to 10, 11 to 20, 21 to 30, and 31 to 38; for the first three groups (each group has 10 subjects in all), we test all methods on 2, 3, 5, 8, and 10 subjects; for the last group (has 8 subjects), we perform experiments on 2, 3, 5, and 8 subjects. Finally, the mean and median clustering errors of different number of subjects are reported for each method to evaluate their performance.USPS. USPS is a database of handwritten digits. It consists of 10 subjects, corresponding to 10 handwritten digits, 0–9. There are 9298 images, with each image having 16×16 pixels. We use the first 100 images of each digit in experiment.Berkeley 500. Berkeley 500 is an image dataset consisting of 500 multiple natural images for segmentation. It covers a variety of scene categories in nature, such as portraits, animals, landscape, and beaches. It also provides ground truth segmentation results of all the images obtained by several human subjects. We select 50 images from this dataset in experiment for image segmentation. We first partition each image into superpixels using the method presented in [23]. Then we extract the Color Histogram (CH), Local Binary Pattern (LBP), and Histogram of Gradient (HOG) features of each superpixel and obtained the dataX. Finally, we use our subspace clustering method to cluster the superpixels into several regions.


### 3.2. Parameter Setting

There are three model parameters,λ, β, and K, affecting the performance of our method. In the following, we analyze the effect of these three parameters on the clustering performance. We choose the first 10 subjects of Extend Yale B and USPS as the test database. We first test the influence of K. Figure 2 shows the clustering error rate varying with the size of neighborhood K from 3 to 9 on Extend Yale B database, with λ=0.1 and β=0.5. It shows that our method performs best with K=6. On USPS, we have the same result. So we take K=6 in all experiments.Figure 2
The clustering error varies with the size of neighborhoodK.Figure3 shows how the clustering error rate of the proposed method depends on the parameter λ, with several fixed values of β on the datasets Extend Yale B (a) and USPS (b). We applied our method on the first 10 subjects of Extend Yale B and all subjects of USPS. For Extend Yale B, one can observe that for β=0.2 and β=0.5 the proposed method performs well with λ∈0,1.5. We set β=0.5 because the error rate behaves more stably with respect to λ. So we set β=0.5 and λ=0.1 because the error rate obtains the smallest value in this case. For USPS, the clustering error rate behaves relatively stably with respect to λ when β=1 or β=1.2. We set β=1 and λ=0.1 because this leads to the smallest error rate.Figure 3
The clustering error rate varies with the parametersλ and β on Extend Yale B dataset (a) and USPS dataset (b).
(a)
(b)


### 3.3. Experimental Results

It should be noted that the Extend Yale B dataset is challenging for subspace clustering due to heavy corruptions in the data. To show the effectiveness, we select all the face images in test. We use thel1-norm to measure the representation error matrixE, and we set λ=0.1, β=0.5, and K=6. We divide the 38 subjects into four groups: 1 to 10, 11 to 20, 21 to 30, and 31 to 38; for the first three groups (each group has 10 subjects in all), we test all methods on 2, 3, 5, 8, and 10 subjects; for the last group (has 8 subjects), we perform experiments on 2, 3, 5, and 8 subjects. Finally, we calculate the mean and median clustering error rates of the four groups. The clustering error rates by all methods in comparison are presented in Table 1. The shapes of affinity matrices of 5 subjects obtained by all methods are illustrated in Figure 4. Our method obtains an affinity matrix which is most close to block diagonal and obtains the lowest error rate in case of multiple subjects. The clustering error rates of LRR, LSR, CASS, and SMR increase quickly when the number of subjects increases. This is mainly because their affinity matrices are not strictly block diagonal, thus leading to grouping data from different subspaces into the same cluster. Due to the sparsity between clusters, the performance of SSC degenerates very slowly as the number of subjects increases. But our method behaves most stably with respect to the number of subjects and it consistently obtains the lowest clustering error rate among all methods.Table 1
The clustering error rate (%) of Extended Yale B dataset.
SSC
LRR
LSR
CASS
SMR
Ours
2 subjects
Mean
0.00
4.08
3.53
0.00
4.87
0.00
Median
0.00
3.91
2.23
0.00
3.91
0.00
3 subjects
Mean
1.43
6.51
6.05
0.69
6.70
1.30
Median
0.78
4.69
4.69
0.00
6.25
0.26
5 subjects
Mean
3.15
9.04
6.95
2.02
14.00
2.06
Median
1.92
4.93
4.28
2.30
14.69
1.62
8 subjects
Mean
6.93
18.24
24.21
18.36
24.91
3.26
Median
4.20
30.47
21.86
16.40
24.90
3.58
10 subjects
Mean
10.29
35.89
30.66
22.65
29.38
2.91
Median
10.52
35.62
30.47
21.54
29.22
2.78Figure 4
Affinity matrices of 5 subjects from Extend Yale B dataset by different methods.
(a)
SSC
(b)
LRR
(c)
LSR
(d)
CASS
(e)
SMR
(f)
OURSFor USPS dataset, we perform the clustering experiment on all data points of all subjects. We use the Frobenius norm to measure the representation error matrix, and we setλ=0.1, β=1, and K=6. Table 2 presents the clustering error rates, which shows that our method performs best and it reduces the clustering error rate of other methods greatly.Table 2
The clustering error rate (%) of USPS dataset.
SSC
LRR
LSR
CASS
SMR
Ours
13.50
22.60
26.10
18.00
12.70
8.60For the Berkeley 500 image segmentation dataset, we select 50 images randomly for image segmentation and use three metrics (PRI, VOI, and GCE) for objective assessment of the methods used. Because of the variety of structures underlying the natural images, we tune the parameters to achieve the best results. Table3 shows the values of the three metrics averaged on the 50 images. We can see that our method can obtain a PRI of 0.8745, a VOI of 1.0068, and a GCE of 0.0886, which distinctly outperforms other methods. The detailed values of the three metrics on the 50 images are shown in Figure 5. Some examples of the segmentation results obtained by our method are shown in Figure 6 for visual assessment. It can be seen that the segmentation results produced by our method are similar to the ground truth and are visually satisfying.Table 3
The average metrics of PRI, VOI, and GCE on Berkeley 500 image segmentation dataset.
SSC
LRR
LSR
CASS
SMR
Ours
PRI
0.8118
0.8410
0.8460
0.8531
0.8546
0.8745
VOI
1.3151
1.2166
1.2205
1.1557
1.1449
1.0068
GCE
0.1495
0.1369
0.1360
0.1265
0.1186
0.0886Figure 5
The values of the three metrics, PRI (higher is better), VOI (lower is better), and GCE (lower is better), on the 50 images produced by SSC, LRR, LSR, CASS, SMR, and our method. (a) PRI, (b) VOI, and (c) GCE.
(a)
(b)
(c)Figure 6
Some segmentation results of the Berkeley 500 dataset by our method.In all, the experimental results on the three datasets show that, by taking both sparsity and grouping effect into consideration, our method is more efficient in recovering the subspace structure underlying high-dimensional dataset.


## 3.1. Datasets and Experimental Settings

Extended Yale B. Extended Yale B is a face dataset that consists of 192×168-pixel cropped face images of 38 human subjects under varying poses and illuminations. Each subject has 64 frontal faces. To reduce the computational cost and memory requirements of all algorithms, each face image is downsampled to 32×32 pixels and rearranged into a 1024-dimensional vector. To study the effect of the number of subjects on the clustering performance of different methods, we divide the 38 subjects into four groups: 1 to 10, 11 to 20, 21 to 30, and 31 to 38; for the first three groups (each group has 10 subjects in all), we test all methods on 2, 3, 5, 8, and 10 subjects; for the last group (has 8 subjects), we perform experiments on 2, 3, 5, and 8 subjects. Finally, the mean and median clustering errors of different number of subjects are reported for each method to evaluate their performance.USPS. USPS is a database of handwritten digits. It consists of 10 subjects, corresponding to 10 handwritten digits, 0–9. There are 9298 images, with each image having 16×16 pixels. We use the first 100 images of each digit in experiment.Berkeley 500. Berkeley 500 is an image dataset consisting of 500 multiple natural images for segmentation. It covers a variety of scene categories in nature, such as portraits, animals, landscape, and beaches. It also provides ground truth segmentation results of all the images obtained by several human subjects. We select 50 images from this dataset in experiment for image segmentation. We first partition each image into superpixels using the method presented in [23]. Then we extract the Color Histogram (CH), Local Binary Pattern (LBP), and Histogram of Gradient (HOG) features of each superpixel and obtained the dataX. Finally, we use our subspace clustering method to cluster the superpixels into several regions.


## 3.2. Parameter Setting

There are three model parameters,λ, β, and K, affecting the performance of our method. In the following, we analyze the effect of these three parameters on the clustering performance. We choose the first 10 subjects of Extend Yale B and USPS as the test database. We first test the influence of K. Figure 2 shows the clustering error rate varying with the size of neighborhood K from 3 to 9 on Extend Yale B database, with λ=0.1 and β=0.5. It shows that our method performs best with K=6. On USPS, we have the same result. So we take K=6 in all experiments.Figure 2
The clustering error varies with the size of neighborhoodK.Figure3 shows how the clustering error rate of the proposed method depends on the parameter λ, with several fixed values of β on the datasets Extend Yale B (a) and USPS (b). We applied our method on the first 10 subjects of Extend Yale B and all subjects of USPS. For Extend Yale B, one can observe that for β=0.2 and β=0.5 the proposed method performs well with λ∈0,1.5. We set β=0.5 because the error rate behaves more stably with respect to λ. So we set β=0.5 and λ=0.1 because the error rate obtains the smallest value in this case. For USPS, the clustering error rate behaves relatively stably with respect to λ when β=1 or β=1.2. We set β=1 and λ=0.1 because this leads to the smallest error rate.Figure 3
The clustering error rate varies with the parametersλ and β on Extend Yale B dataset (a) and USPS dataset (b).
(a)
(b)


## 3.3. Experimental Results

It should be noted that the Extend Yale B dataset is challenging for subspace clustering due to heavy corruptions in the data. To show the effectiveness, we select all the face images in test. We use thel1-norm to measure the representation error matrixE, and we set λ=0.1, β=0.5, and K=6. We divide the 38 subjects into four groups: 1 to 10, 11 to 20, 21 to 30, and 31 to 38; for the first three groups (each group has 10 subjects in all), we test all methods on 2, 3, 5, 8, and 10 subjects; for the last group (has 8 subjects), we perform experiments on 2, 3, 5, and 8 subjects. Finally, we calculate the mean and median clustering error rates of the four groups. The clustering error rates by all methods in comparison are presented in Table 1. The shapes of affinity matrices of 5 subjects obtained by all methods are illustrated in Figure 4. Our method obtains an affinity matrix which is most close to block diagonal and obtains the lowest error rate in case of multiple subjects. The clustering error rates of LRR, LSR, CASS, and SMR increase quickly when the number of subjects increases. This is mainly because their affinity matrices are not strictly block diagonal, thus leading to grouping data from different subspaces into the same cluster. Due to the sparsity between clusters, the performance of SSC degenerates very slowly as the number of subjects increases. But our method behaves most stably with respect to the number of subjects and it consistently obtains the lowest clustering error rate among all methods.Table 1
The clustering error rate (%) of Extended Yale B dataset.
SSC
LRR
LSR
CASS
SMR
Ours
2 subjects
Mean
0.00
4.08
3.53
0.00
4.87
0.00
Median
0.00
3.91
2.23
0.00
3.91
0.00
3 subjects
Mean
1.43
6.51
6.05
0.69
6.70
1.30
Median
0.78
4.69
4.69
0.00
6.25
0.26
5 subjects
Mean
3.15
9.04
6.95
2.02
14.00
2.06
Median
1.92
4.93
4.28
2.30
14.69
1.62
8 subjects
Mean
6.93
18.24
24.21
18.36
24.91
3.26
Median
4.20
30.47
21.86
16.40
24.90
3.58
10 subjects
Mean
10.29
35.89
30.66
22.65
29.38
2.91
Median
10.52
35.62
30.47
21.54
29.22
2.78Figure 4
Affinity matrices of 5 subjects from Extend Yale B dataset by different methods.
(a)
SSC
(b)
LRR
(c)
LSR
(d)
CASS
(e)
SMR
(f)
OURSFor USPS dataset, we perform the clustering experiment on all data points of all subjects. We use the Frobenius norm to measure the representation error matrix, and we setλ=0.1, β=1, and K=6. Table 2 presents the clustering error rates, which shows that our method performs best and it reduces the clustering error rate of other methods greatly.Table 2
The clustering error rate (%) of USPS dataset.
SSC
LRR
LSR
CASS
SMR
Ours
13.50
22.60
26.10
18.00
12.70
8.60For the Berkeley 500 image segmentation dataset, we select 50 images randomly for image segmentation and use three metrics (PRI, VOI, and GCE) for objective assessment of the methods used. Because of the variety of structures underlying the natural images, we tune the parameters to achieve the best results. Table3 shows the values of the three metrics averaged on the 50 images. We can see that our method can obtain a PRI of 0.8745, a VOI of 1.0068, and a GCE of 0.0886, which distinctly outperforms other methods. The detailed values of the three metrics on the 50 images are shown in Figure 5. Some examples of the segmentation results obtained by our method are shown in Figure 6 for visual assessment. It can be seen that the segmentation results produced by our method are similar to the ground truth and are visually satisfying.Table 3
The average metrics of PRI, VOI, and GCE on Berkeley 500 image segmentation dataset.
SSC
LRR
LSR
CASS
SMR
Ours
PRI
0.8118
0.8410
0.8460
0.8531
0.8546
0.8745
VOI
1.3151
1.2166
1.2205
1.1557
1.1449
1.0068
GCE
0.1495
0.1369
0.1360
0.1265
0.1186
0.0886Figure 5
The values of the three metrics, PRI (higher is better), VOI (lower is better), and GCE (lower is better), on the 50 images produced by SSC, LRR, LSR, CASS, SMR, and our method. (a) PRI, (b) VOI, and (c) GCE.
(a)
(b)
(c)Figure 6
Some segmentation results of the Berkeley 500 dataset by our method.In all, the experimental results on the three datasets show that, by taking both sparsity and grouping effect into consideration, our method is more efficient in recovering the subspace structure underlying high-dimensional dataset.


## 4. Conclusion

The state-of-the-art methods show that sparsity and grouping effect of the affinity matrix are useful in clustering. In this work, we enforce both requirements in modeling the self-representation of data points. The experimental results on Extended Yale B, USPS, and Berkeley 500 image segmentation datasets show the requirements of sparsity and grouping effect and the proposed model is more effective than state-of-the-art methods in revealing the cluster structure underlying high-dimensional dataset.



---

*Source: 4787039-2017-03-22.xml*