Robust Subspace Clustering with Block Diagonal Representation for Noisy Image Datasets

Abstract

As a relatively advanced method, the subspace clustering algorithm by block diagonal representation (BDR) will be competent in performing subspace clustering on a dataset if the dataset is assumed to be noise-free and drawn from the union of independent linear subspaces. Unfortunately, this assumption is far from reality, since the real data are usually corrupted by various noises and the subspaces of data overlap with each other, the performance of linear subspace clustering algorithms, including BDR, degrades on the real complex data. To solve this problem, we design a new objective function based on BDR, in which l_2,1 norm of the reconstruction error is introduced to model the noises and improve the robustness of the algorithm. After optimizing the objective function, we present the corresponding subspace clustering algorithm to pursue a self-expressive coefficient matrix with a block diagonal structure for a noisy dataset. An affinity matrix is constructed based on the coefficient matrix, and then fed to the spectral clustering algorithm to obtain the final clustering results. Experiments on several artificial noisy image datasets show that the proposed algorithm has robustness and better clustering performance than the compared algorithms.

1. Introduction

Clustering [1] is an important analysis tool in the fields of data mining and machine learning, and is widely used in motion segmentation [2,3,4], text clustering [5], image segmentation [6,7], face recognition [8], and other practical applications [9]. In brief, clustering divides unlabeled data into several clusters according to the similarity of data points. Traditional clustering methods, such as K-means, hierarchical clustering [10], and density clustering [11,12], cannot perform well on high-dimensional data. Therefore, subspace clustering algorithms for high-dimensional data get more attention in many applications. For example, in spatiotemporal data analysis, huge volumes of image and video data are high-dimensional and noisy, subspace clustering can be employed as an effective method of data preprocessing, and the clustering results help to uncover the structure of the dataset.

In the view of spectral graph theory, the key to the success of subspace clustering is to construct a coefficient matrix that can correctly reflect the spatial distribution of the data. Ideally, the coefficient matrix has a block diagonal structure, and each block is a self-representative coefficient sub-matrix for a cluster of data. Sparse subspace clustering (SSC) [13,14] and low rank subspace clustering (LRR) [15] are two representative subspace clustering algorithms used in the last decade. SSC and LRR construct coefficient matrices C by sparse representation and low rank representation of data, respectively, and then obtain the affinity matrix W from the coefficient matrix, i.e., W = (|C| + |C^T|)/2, and finally W is fed into spectral clustering to obtain clustering results. In recent years, block diagonal representation (BDR) for subspace clustering algorithms [16,17] attracted attention due to its good clustering performance. BDR introduces Laplacian rank constraint into the objective function, and obtains a more accurate block diagonal coefficient matrix than SSC and LRR. However, SSC, LRR, and BDR algorithms all belong to linear subspace clustering, the basic assumption of which is the self-expressiveness property. The self-expressiveness property assumes that each data point can be expressed as a linear combination of all the other points in the union of subspaces. Meanwhile, subspace-preserving is also a common assumption for linear subspace clustering, where each data point in a subspace can be linearly expressed by other points in the same subspace [18]. Finally, the data should be noise-free and subspaces should be independent of each other. However, these assumptions are usually far from reality, since in the process of data generation, transmission, storage, and even applications, data may be damaged, resulting in data containing noises, outliers, and even corruptions [19,20,21,22,23,24,25]. The corruptions make data deviate from the original data model. The subspaces corrupted by complex noises are beyond the self-expressiveness of independent linear subspaces, consequently, subspace clustering results will deviate from expectations. Thus, the linear subspace clustering algorithms degrade when facing corrupted datasets in reality.

Aiming at above problems, some efforts impose norm regularizations to handle various noises. Studies show that the Frobenius norm (F norm for short), l₁ norm, and l_2,1 norm can efficiently handle Gaussian noises, sparse noises, and outliers, respectively [19,26]. SSC used F norm and l₁ norm to deal with noise [13]. Favaro et al. [27] learned a new data dictionary by handling data errors through the F norm. LRR used l_2,1 norm to reduce the influence of data errors [19]. It is easy to find that these efforts achieve good results by assuming the type of errors as a prior and removing errors in the original input space by modeling them in their objective functions [28]. Unfortunately, the data in reality may be corrupted by complex noises [29], and modeling of errors should combine with more robust methods to handle the noises and uncover the subspace structure of the data set.

To solve this problem, Chen et al. [30] proposed a robust low-rank subspace clustering algorithm (RLRR), which adopts a probability density function to fit noise distribution. Liu et al. [31] proposed the latent low-rank representation subspace clustering (LatLRR) by reconstructing the representation dictionary to avoid the influence of noise and correctly represent the distribution of data subspaces. Zhang et al. [32] proposed Robust LatLRR on the basis of LatLRR to impose sparse constraints on the matrix. Similar to LatLRR, references [33,34] also learned a clean dictionary to find the data distribution structure and reduce the influence of data noise. Nie et al. [35] proposed a novel low-rank structural model for segmenting high-dimensional data. A new rank constraint is defined to learn a subspace indicator, which can capture different clusters directly from the data. These methods based on low-rank representation show good performance in dealing with the linear structure of data. Unfortunately, in practice, many datasets have nonlinear subspaces that overlap with each other. To solve this problem, the multiple kernel learning (MKL) is applied to solve nonlinear structural data modeling [36]. Moreover, low-rank kernel space clustering methods are studied to deal with the nonlinear structure of high-dimensional data [37]. These methods adaptively select or combine kernels suitable for the datasets from a set of kernels. However, if the dataset is corrupted by complex noises, maybe the selected kernel is not optimal.

Furthermore, there are efforts dealing with noises in various ways for subspace clustering. Qin et al. [28] proposed a method from an energy perspective to eliminate errors in the projected space rather than the input space. They defined an energy function to measure a block in the projected space, and found the correct block with the maximal energy to lead clustering. He et al. [38] proposed the subspace clustering algorithm via half-quadratic (SCHQ) to handle noisy data. SCHQ consisted of two parts, the first one adopted l₁ norm to obtain a sparse representation of data, and the second one maximized the correlation of low-dimensional representations among a given data point and other data points to reduce the damage of noisy data to coefficient representation. Wang et al. [39] proposed a robust block diagonal representation (RBDR) method, which used a penalty matrix to adaptively weigh the reconstruction error to handle noises without prior knowledge, and thus had good clustering performance under noise conditions. The principles of these efforts are different from our study, and the performance of subspace clustering of some work (e.g., RBDR) will be compared in the following experiments.

In this study, we focus on the robust subspace clustering algorithms based on the Laplacian rank constraint, i.e., the block diagonal property. BDR assumes that the data contain Gaussian noises and fits the reconstruction errors with F norm. In fact, other types of noises, such as occlusions and outliers, may exist in the data. In this paper, l_2,1 norm is used to fit the possible outliers in the data, and is combined with the Laplacian rank constraint to improve the performance of the subspace clustering on more complex noisy datasets.

The main contributions of this paper are as follows:

(1)

The robust subspace clustering algorithm with block diagonal representation (OBDR) is proposed to handle noises, in which the noises are modeled using l_2,1 norm, and the Laplacian rank constraint is adopted to pursue a block diagonal structure of the subspace representation;

(2)

The objective function of the proposed algorithm is designed and a corresponding optimization process based on ADMM is given. The algorithm is presented and the time complexity is analyzed;

(3)

Experiments on artificial noisy digital dataset MNIST and face datasets (ORL and YaleB) show that OBDR is insensitive to noises.

Notation. We summarize the symbols and norms used in this paper, as shown in

Table 1. The notations used in each algorithm.

Notations	Descriptions
Ci,:	the i-th row of C
C:,j	the j-th column of C
Cij	the (i,j)-th element of C
CT	the transposed matrix of C
Tr(C)	the trace of the matrix C
diag(C)	a vector with its i-th element being the i-th diagonal element of C
Diag(c)	a diagonal matrix with its i-th diagonal element being i-th element of vector c
$\left|\right|C|{|}_F=\sqrt{{\displaystyle {\sum }_{ij}{C}_{ij}^2}}$	the Frobenius norm(or l2 norm) of C
$\left|\right|C|{|}_{2,1}={{\displaystyle {\sum }_i\left|\right|C_{i,:}\left|\right|}}_F$	the l2,1 norm of C
$\left|\right|C|{|}_1={\displaystyle {\sum }_{ij}|C_{ij}}|$	the l1 norm of C
$\left|\right|C|{|}_{\infty }=\max |C_{ij}|$	the l∞ norm of C

. We define the vector as italic lowercase letters, e.g., c, and the matrix as italic capital letters, e.g., C.

The rest of this paper is organized as follows: In Section 2, we propose the objective function of the robust subspace clustering with block diagonal representation (OBDR) and illustrate the framework of the OBDR. In Section 3, we solve the optimization of the objective function by ADMM and present the algorithm in details. The experimental results are introduced in Section 4, and finally Section 5 summarizes the paper.

2. The Proposed Method

BDR adds Laplacian rank constraint, namely K-block diagonal regularizer, to its objective function to control the number of connected branches of the graph, which is constructed by using the matrix W as the affinity matrix. It is proved theoretically and experimentally that a K-block diagonal regularizer can correctly represent the similarity of data and the coefficient matrix shows a block diagonal structure, which makes the BDR algorithm have good clustering performance [17].

For any matrix B, the K-block diagonal regularizer is defined as the sum of the k smallest eigenvalues of the corresponding Laplacian matrix of B (i.e., L_B = Diag(B1) − B),

$${\Vert B\Vert }_K={\displaystyle \sum _{\mathrm{i}=n-k+1}^{\mathrm{n}}{\lambda }_i\left(L_B\right)}.$$

(1)

Lu [17] defined the BDR model as following:

$$\begin{array}{l}\underset{Z,B}{\min }\frac{1}{2}{\Vert X-XZ\Vert }_F^2+\frac{\lambda }{2}{\Vert Z-B\Vert }_F^2+\gamma {\Vert B\Vert }_K,\\ s.t.diag(B)=0,B\ge 0,B=B^T.\end{array}$$

(2)

On the basis of BDR, we remodel the reconstruction error E of data X, which may contain outliers, and propose the objective function of robust subspace clustering with block diagonal representation (OBDR) as follows:

$$\begin{array}{l}\underset{Z,B,E}{\min }{\Vert E\Vert }_{\ell }+\frac{\lambda }{2}{\Vert Z-B\Vert }_F^2+\gamma {\Vert B\Vert }_K,\\ s.t.diag(B)=0,B\ge 0,B=B^T,E=X-XZ.\end{array}$$

(3)

$\left|\right|\cdot |{|}_{\ell }$ is an alternative regularization method for handling different types of noise. In general, F norm is selected to deal with Gaussian noises and slight sparse noises in the data, meanwhile, sparse noises can be better processed by $\left|\right|\cdot |{|}_1$. In the case of corruptions or outliers, $\left|\right|\cdot |{|}_{2,1}$ is a better choice. For different noises, appropriate regularization methods can effectively reduce the sensitivity of the algorithm to noisy data and improve the robustness of the algorithm.

Aiming at handling outliers, we select $\left|\right|\cdot |{|}_{2,1}$ to replace $\left|\right|\cdot |{|}_{\ell }$ in Equation (3),

$$\begin{array}{l}\underset{Z,B,E}{\min }{\Vert E\Vert }_{2,1}+\frac{\lambda }{2}{\Vert Z-B\Vert }_F^2+\gamma {\Vert B\Vert }_K,\\ s.t.diag(B)=0,B\ge 0,B=B^T,E=X-XZ.\end{array}$$

(4)

Next, we use the augmented Lagrange multiplier method ALM [40,41] to rewrite Equation (4) and define the objective function F (Z, B, E) as follows:

$$\begin{array}{l}\underset{Z,B,E}{\min }F(Z,B,E)=\frac{\mu }{2}{\Vert X-XZ-E+\frac{\mathrm{\Lambda }}{\mu }\Vert }_F^2+{\Vert E\Vert }_{2,1}+\frac{\lambda }{2}{\Vert Z-B\Vert }_F^2+\gamma {\Vert B\Vert }_K,\\ s.t.diag(B)=0,B\ge 0,B=B^T.\end{array}$$

(5)

where μ and Λ are the penalty parameter and Lagrange multiplier, respectively. Equation (5) shows that, OBDR not only uses l_2,1 norm to handle outliers, but also uses F norm to deal with Gaussian noise and slight sparse noise.

Following [42,43], we summarize the framework of the OBDR in Figure 1. The objective function of OBDR retains the self-expressiveness and subspace preserving property in the first term of F (Z, B, E), and the Laplacian rank constraint in the last term. Moreover, the noises are separated from the input data X in the first term of F (Z, B, E) and modeled by the l_2,1 norm in the second term. The optimized self-expressive matrix Z is used to calculate the affinity matrix W = (|Z| + |Z^T|)/2, and then, W is fed to spectral clustering to get the clustering result.

3. Optimization of the Objective Function

Firstly, $\left|\right|B|{|}_K$ is rewritten as a convex optimization problem [17],

$$\begin{array}{l}\left|\right|B|{|}_K=\underset{V}{\min }\langle L_B,V\rangle ,\\ s.t.0\preccurlyeq V\preccurlyeq I,tr\left(V\right)=K.\end{array}$$

(6)

Then, Equation (5) is equivalent to

$$\begin{array}{l}\min J(Z,B,E)=\frac{\mu }{2}{\Vert X-XZ-E+\frac{\mathsf{\Lambda }}{\mu }\Vert }_F^2+\left|\right|E|{|}_{2,1}+\frac{\lambda }{2}{\Vert Z-B\Vert }_F^2+\gamma \langle Diag(B1)-B,V\rangle \\ s.t.diag(B)=0,B\ge 0,B=B^T,0\preccurlyeq V\preccurlyeq I,tr\left(V\right)=K.\end{array}$$

(7)

Finally, the ADMM method is adopted to solve the variables E, Z, B, and V. The optimization consists of four sub-problems as follows:

(1) Update E with fixed Z, B, and V

E is updated as:

$$E^{t+1}=\underset{E}{\arg \min }\frac{\mu }{2}{\Vert X-XZ-E+\frac{\mathrm{\Lambda }}{\mu }\Vert }_F^2+{\Vert E\Vert }_{2,1}.$$

(8)

To solve Equation (8), the following theorem is introduced.

Theorem 1 

([44]). Given a matrix A = [a₁, a₂, …, a_i, …], solve the following problem:

$$\underset{W}{\min }\sigma {\Vert W\Vert }_{2,1}+\frac{1}{2}{\Vert W-A\Vert }_F^2$$

(9)

then, the optimal solution W* of Equation (9) can be solved column by column, and the i-th column of W* as follows:

$$W^{*}(:,i)=\{\begin{array}{l}\frac{\Vert a_i\Vert -\sigma }{\Vert a_i\Vert }{a}_i,if\sigma <\Vert a_i\Vert ,\\ 0,otherwise.\end{array}$$

(10)

According to Theorem 1, we rewrite Equation (8) as:

$$E^{t+1}=\underset{E}{\arg \min }\frac{1}{2}{\Vert E-(X-XZ+\frac{\mathrm{\Lambda }}{\mu })\Vert }_F^2+\frac{1}{\mu }{\Vert E\Vert }_{2,1}.$$

(11)

Let $A=X-XZ+\frac{\mathrm{\Lambda }}{\mu }$, and A = [a₁, a₂, …, a_i, …], the optimal solution E* is given:

$$E^{*}(:,i)=\{\begin{array}{l}\frac{\Vert a_i\Vert -\frac{1}{\mu }}{\Vert a_i\Vert }{a}_i,if\frac{1}{\mu }<\Vert a_i\Vert ,\\ 0,otherwise.\end{array}$$

(12)

(2) Update Z with fixed E, B, and V

Z is updated as:

$$Z^{t+1}=\underset{Z}{\arg \min }\frac{\mu }{2}{\Vert X-XZ-E+\frac{\mathsf{\Lambda }}{\mu }\Vert }_F^2+\frac{\lambda }{2}{\Vert Z-B\Vert }_F^2.$$

(13)

Since $\left|\right|A|{|}_F^2=Tr(A^{T}A)$, we define the function f and transform it as follows:

$$\begin{array}{l}f(Z)=\frac{\mu }{2}{\Vert X-XZ-E+\frac{\mathrm{\Lambda }}{\mu }\Vert }_F^2+\frac{\lambda }{2}{\Vert Z-B\Vert }_F^2\\ \hspace{1em}=\frac{\mu }{2}Tr({(X-XZ-E+\frac{\mathrm{\Lambda }}{\mu })}^T(X-XZ-E+\frac{\mathrm{\Lambda }}{\mu }))\\ \hspace{1em}+\frac{\lambda }{2}Tr({(Z-B)}^T(Z-B)).\end{array}$$

(14)

Take the derivative of Equation (14), we obtain:

$$\frac{\partial f}{\partial Z}=\mu \left(X^{T}XZ-X^{T}X+X^{T}E-X^T\frac{\mathrm{\Lambda }}{\mu }\right)+\lambda \left(Z-B\right).$$

(15)

Set Equation (15) to 0, then

$$\left(\mu X^{T}X+\lambda I\right)Z=\mu X^{T}X-\mu X^{T}E+X^T\mathrm{\Lambda }+\lambda B.$$

We derive Z,

$$Z={\left(\mu X^{T}X+\lambda I\right)}^{-1}\left(\mu X^{T}X-\mu X^{T}E+X^T\mathrm{\Lambda }+\lambda B\right).$$

(16)

(3) Update B with fixed E, Z, and V

B is updated as:

$$\begin{array}{l}{B}^{t+1}=\underset{B}{\arg \min }\frac{\lambda }{2}{\Vert Z-B\Vert }_F^2+\gamma \langle Diag(B1)-B,V\rangle \\ s.t.diag(B)=0,B\ge 0,B=B^T.\end{array}$$

According to the reference [17], the closed-form solution of B is given as:

$$B^{t+1}={\left[(\widehat{A}+{\widehat{A}}^T)/2\right]}_{+}$$

(17)

where ${\left[A\right]}_{+}=\max \left(A,0\right)$, $A=Z-\frac{\gamma }{\lambda }(diag(V)1^T-V)$,$\widehat{A}=A-Diag(diag(A))$.

(4) Update V with fixed E, B, and Z

V is updated as:

$$V^{t+1}=\underset{V}{\arg \min }\langle Diag\left(B1\right)-B,V\rangle s.t.0\preccurlyeq V\preccurlyeq I,tr\left(V\right)=K.$$

(18)

Equation (18) can be solved as follows [17]:

$$V^{t+1}=U{U}^T$$

(19)

where $U\in R^{\mathrm{n}*K}$ consists of the K eigenvectors associated with the first K smallest eigenvalues of Diag(B1) − B.

The process of OBDR is summarized as Algorithm 1.

Algorithm 1 OBDR

Input: X, λ, γ, ρ  Initialization: V = 0, B = 0, Z = 0, E = 0, Λ = 0, μ = 10−3, μmax = 108, ε = 10−6, t = 0, Maxloop = 500.  1. WHILE t < Maxloop DO  2.  Update E by Equation (12);  3.  Update Z by Equation (16);  4.  Update B by Equation (17);  5.  Update V by Equation (19);  6.  Update Λ, Λ = Λ + μ(X − XZ − E);  7.  Update μ, μ = min(ρμ, μmax);  8.  if Max(${\Vert Z^{t+1}-Z\Vert }_{\infty }$,${\Vert B^{t+1}-B\Vert }_{\infty }$,${\Vert X-XZ-E\Vert }_{\infty }$) < ε, break;  9.  t = t + 1;  10. END.  Ouput: Z, B

μ is the parameter for updating the Lagrange multiplier Λ, and its initial value is usually within (10⁻⁸, 10⁻³). Parameter ρ directly affects the update times of the algorithm. Generally, the larger ρ is, the higher the efficiency of the algorithm will be. However, large ρ will cause the variables to change greatly and miss the optimal solution; on the contrary, lowering ρ can bring high variable accuracies and good results but also takes a lot of time [45]. Considering both the updating efficiency and clustering results, we set the maximum number of iterations (Maxloop) in Algorithm 1 to 500 and set ρ according to the datasets to ensure an accurate coefficient matrix Z. Then the affinity matrix W = (|Z| + |Z^T|)/2 is calculated and fed into spectral clustering to get the clustering result.

The computation complexity of OBDR includes two parts, i.e., the process of updating E, Z, B, and V, and spectral clustering. Because the time complexity of eigenvector decomposition and spectral clustering is O (n³), and the time complexity of updating variables is O (Tn³), where T is iterative times, the total time complexity of OBDR is O (Tn³).

4. Experiments and Discussions

4.1. Experimental Datasets

In order to evaluate the robustness of the proposed algorithm, we test four artificial data sets under noises, including outliers, masking noises, Gaussian noises, and a mixture of various noises. We restrict our discussions and experiments to the following corruption processes:

(1)

Outliers: For a given data set, outliers are data that are beyond all subspaces of this data, i.e., outliers come from different data models, rather than a simple situation that is floating between subspaces [19], so we select small samples from different data sets to simulate outliers for a given data set;

(2)

Masking noises: A fraction of an image is masked by setting the elements of the masked position to 0 [46];

(3)

Additive Gaussian noises: $\tilde{x}|x~N(x,{\sigma }^{2}I)$ for an image x [46].

The details of noisy data sets are described as follows:

(1)

Dataset1 for outliers (D₁)

We conduct experiments on the MNIST dataset for k = {2, 4, 6} digits, respectively. For each k, we randomly select 100 images for each digit, down sample each image to 28 × 28 pixels and vectorize it as a vector of length 784. Therefore, the size of Dataset1 is 784 × 100 k, for k = {2, 4, 6}. After that, we randomly replace a fraction p = {1%, 3%, 5%, 10%} of Dataset1 with images from ORL, which were cropped to the same size as digits, i.e., 784-length vectors. Finally, we normalize each column vector to have a unit length. Two clusters in Dataset1 are shown in Figure 2. Dataset1 is denoted as D₁ for simplicity, D₂~D₄ are defined similarly.

(2)

Dataset2 for masking noise (D₂)

On the ORL dataset, we conduct clustering experiments for k = {10, 20, 30} people. For each k, we randomly pick k people from ORL, each of which has 10 images and the images are down sampled to 32 × 32 pixels. Then, we perform masking operations for each people. We randomly corrupt 4 out of 10 photos with mask size 5 × 5 at random positions, then a test dataset with 40% corrupted images is produced. Repeat the masking operations with mask sizes 8 × 8 and 10 × 10 to have two more test datasets. Furthermore, we test the noise-free dataset as a benchmark. Finally, we vectorize images and normalize each vector to have a unit length. Some images are shown in Figure 3.

(3)

Dataset3 for Gaussian noise (D₃)

The extended YaleB dataset contains 38 people, each of which contains 64 frontal face images under different Lambertian conditions. We conduct clustering experiments on the YaleB for k = {3, 5, 8} people. For each k, we randomly pick k people, each of which has 64 images. The images are down sampled to 32 × 32 pixels and vectorized as a vector of length 1024. Next, we randomly add Gaussian noise N (0.1, 0.01) to a fraction p = {10%, 20%, 30%} of vectors. Similarly, we test the noise-free dataset as a benchmark. Some images from YaleB as shown in Figure 4.

(4)

Dataset4 for mixture noise (D₄)

In practice, a data set may be corrupted by various noises simultaneously and the performance of data clustering is seriously damaged [26,47]. On the basis of Dataset1~Dataset3, we add three kinds of data noises with a ratio of 1: 1: 1 to the ORL. Specifically, for each people, we randomly pick one image to add masking noise with mask size 10 × 10 and one image to add Gaussian noise N(0.1, 0.01), respectively, and then replace one image with a cropped MNIST image with 32 × 32 pixels. So, there are three corrupted images for each people. On the Dataset4, we also conduct clustering experiments for k = {10, 20, 30} people.

4.2. Experimental Setup

ACC [17] and NMI [48] were used to evaluate the clustering performance of algorithms under noises.

Let U = [u₁, u₂, …, u_n], V = [v₁, v₂, …, v_n] represent the real labels and the clustering labels of all data, respectively. ACC is defined as follows:

$$\mathrm{ACC}(U,\mathrm{V})=\frac{1}{n}{\displaystyle \sum _{i=1}^{n}ind(u_i,g(v_i))}$$

(20)

where u_i and v_i denote the real label and the clustering label of the i-th data point, respectively, ind(x, y) = 1 if x = y, and 0 otherwise. The function g(.) maximizes the ACC by permuting the labels V to match the labels U.

NMI is defined as follows:

$$\mathrm{NMI}(U,V)=\frac{{\displaystyle {\sum }_{\mathrm{i}=1}^R{\displaystyle {\sum }_{j=1}^{T}P(p_i\cap q_j)\log \frac{P(p_i\cap q_j)}{P(p_i)P(q_j)}}}}{-[{\displaystyle {\sum }_{i=1}^{R}P(p_i)\log P(p_i)}+{\displaystyle {\sum }_{j=1}^{T}P(q_j)\log P(q_j)}]/2}.$$

(21)

P(c) = |c|/n denotes the probability that the data points belong to the cluster c, where |c| is the cardinality of c, p_i is the set of data points with the real label u_i, while q_j is the set with the clustering label v_j. R and T represent the number of real labels and output labels of data, respectively.

The value ranges of ACC and NMI are [0, 1], and the higher the ACC and NMI, the better the performance.

We picked five algorithms for comparison, and the algorithms are described as follows:

SSC [13]: The sparse subspace clustering algorithm, which uses sparse representation among data to obtain clustering results;

LRR [19]: The low rank subspace clustering algorithm, which uses low rank representation among data to obtain clustering results;

BDR [17]: Subspace clustering by block diagonal representation, the coefficient matrix obtained by BDR presents a block diagonal structure;

SBDR [16]: Structured block diagonal representation for subspace clustering. On the basis of BDR, SBDR added additional a subspace structure constraint;

RBDR [39]: Block diagonal representation learning for robust subspace clustering for handling data noise.

All the codes used in the experiment were released by the authors. For the parameter(s) in each algorithm, we searched the optimal values within the range of [10⁻⁵, 10⁵] to ensure the good performance on most test sets. The parameters are shown in

Table 2. The parameter values used in each algorithm.

Datasets	SSC	LRR	BDR	SBDR	RBDR	OBDR
D1	α = 20	λ = 0.45	λ = 70 γ = 0.1	λ = 100 γ = 10 δ = 1	λ = 1 × 10−4 γ = 1 × 10−4	λ = 70 γ = 0.1 ρ = 2
D2, D4	α = 100	λ = 1.45	λ = 70 γ = 0.1	λ = 100 γ = 0.1 δ = 1 × 10−5	λ = 1 × 10−3 γ = 1 × 10−4	λ = 70 γ = 0.1 ρ = 1.05
D3	α = 20	λ = 0.85	λ = 10 γ = 0.1	λ = 70 γ = 0.1 δ = 0.1	λ = 1 × 10−4 γ = 1 × 10−5	λ = 10 γ = 1 × 10−3 ρ = 1.45

.

All experiments were run on a computer equipped with an Intel Core I3-10100 processor, 8 G memory, and Windows10 operating system.

4.3. Experimental Results

We run 10 trials on each test set, and the averaged ACC and NMI are shown in

Table 3. ACCs of algorithms on Dataset1~Dataset4.

Datasets	#Subjects	Noise Level	SSC	LRR	BDR	SBDR	RBDR	OBDR
D1	2	Clean	0.8685	0.8955	0.9230	0.9245 1	0.8425	0.8965
		1%	0.6355	0.8955	0.6715	0.8465	0.9230	0.8910
		3%	0.5566	0.7085	0.5110	0.5115	0.6945	0.8805
		5%	0.5090	0.5105	0.5090	0.5120	0.6945	0.8645
		10%	0.5735	0.5185	0.5720	0.5180	0.6870	0.6975
	4	Clean	0.6420	0.7368	0.7712	0.7548	0.6202	0.7560
		1%	0.6515	0.7232	0.6222	0.6352	0.6020	0.7183
		3%	0.5735	0.6038	0.6153	0.6295	0.5453	0.6358
		5%	0.5623	0.5968	0.6095	0.6213	0.4370	0.5930
		10%	0.3640	0.5777	0.4040	0.5590	0.2892	0.5767
	6	Clean	0.5712	0.6235	0.6077	0.6437	0.6100	0.6423
		1%	0.5495	0.5528	0.5828	0.5460	0.5828	0.6073
		3%	0.5113	0.5465	0.5758	0.5570	0.5758	0.5682
		5%	0.5183	0.5368	0.5452	0.6042	0.3832	0.5607
		10%	0.3023	0.4640	0.2582	0.4525	0.1840	0.5398
D2	10	Clean	0.8000	0.8760	0.8820	0.8820	0.5470	0.8830
		5 × 5	0.7440	0.8550	0.8590	0.8640	0.7990	0.8700
		8 × 8	0.6440	0.7800	0.7460	0.7690	0.6150	0.7830
		10 × 10	0.6480	0.7490	0.6120	0.6030	0.4980	0.6850
	20	Clean	0.7650	0.7940	0.8135	0.8155	0.3975	0.8350
		5 × 5	0.6660	0.7680	0.7835	0.7950	0.7070	0.8220
		8 × 8	0.6150	0.6910	0.6375	0.6560	0.5090	0.6905
		10 × 10	0.5935	0.6020	0.5085	0.5130	0.4205	0.5625
	30	Clean	0.7307	0.7903	0.8143	0.8370	0.2423	0.8543
		5 × 5	0.6370	0.7627	0.7913	0.7970	0.6747	0.8317
		8 × 8	0.5840	0.6530	0.6233	0.6670	0.4827	0.6923
		10 × 10	0.5850	0.6107	0.5047	0.5363	0.4120	0.5857
D3	3	Clean	0.6495	0.9638	0.9664	0.9303	0.3327	0.9824
		10%	0.6489	0.4898	0.7495	0.8059	0.3221	0.8729
		20%	0.6101	0.4394	0.7330	0.7479	0.2466	0.7947
		30%	0.5681	0.3351	0.6628	0.6016	0.1889	0.6686
	5	Clean	0.5962	0.7163	0.7987	0.7941	0.4210	0.8687
		10%	0.5300	0.6069	0.5966	0.7050	0.3210	0.7622
		20%	0.4206	0.4287	0.5572	0.5841	0.2567	0.5962
		30%	0.3859	0.3087	0.4563	0.5222	0.2212	0.5269
	8	Clean	0.5115	0.7094	0.8687	0.9127	0.2882	0.8468
		10%	0.5626	0.6160	0.6409	0.7411	0.2511	0.7568
		20%	0.4495	0.5039	0.6149	0.7000	0.1889	0.7080
		30%	0.4102	0.4127	0.5564	0.6221	0.1876	0.6268
D4	10		0.5880	0.2621	0.6580	0.6511	0.5315	0.6905
	20		0.6003	0.3285	0.5796	0.6121	0.4762	0.6188
	30		0.5682	0.3562	0.5802	0.6000	0.4935	0.6062

¹ The best ACC on each test set is shown in bold.

and

Table 4. NMIs of algorithms on Dataset1~Dataset4.

Datasets	#Subjects	Noise Level	SSC	LRR	BDR	SBDR	RBDR	OBDR
D1	2	Clean	0.4991	0.6078	0.6707	0.7173 2	0.5649	0.6242
		1%	0.2302	0.5919	0.2876	0.5840	0.5528	0.6063
		3%	0.0858	0.3252	0.0066	0.0066	0.3298	0.5594
		5%	0.0047	0.0053	0.0047	0.0047	0.3259	0.4863
		10%	0.0649	0.0051	0.0044	0.0048	0.2860	0.2366
	4	Clean	0.4154	0.5842	0.6133	0.6821	0.4849	0.5507
		1%	0.5702	0.5688	0.5534	0.6065	0.4822	0.5292
		3%	0.5128	0.4777	0.5283	0.5803	0.3456	0.4590
		5%	0.4768	0.4641	0.5100	0.5631	0.1989	0.4442
		10%	0.0947	0.4222	0.4024	0.4744	0.0503	0.4182
	6	Clean	0.4255	0.5589	0.5623	0.6533	0.5623	0.5774
		1%	0.5468	0.5047	0.5325	0.6008	0.5325	0.5258
		3%	0.4859	0.4876	0.5037	0.5662	0.5037	0.4841
		5%	0.4844	0.4742	0.4644	0.5883	0.2605	0.4658
		10%	0.1254	0.3832	0.1475	0.4651	0.0221	0.4379
D2	10	Clean	0.8662	0.8976	0.8952	0.9047	0.6324	0.9176
		5 × 5	0.7726	0.8839	0.8793	0.8812	0.8229	0.8958
		8 × 8	0.6804	0.7917	0.7819	0.7981	0.6242	0.8008
		10 × 10	0.6564	0.7493	0.6346	0.6259	0.5225	0.6957
	20	Clean	0.8571	0.8732	0.8821	0.8941	0.5541	0.9009
		5 × 5	0.7643	0.8439	0.8635	0.8761	0.7861	0.8840
		8 × 8	0.7135	0.7644	0.7282	0.7479	0.6246	0.7646
		10 × 10	0.6943	0.6954	0.6264	0.6342	0.5572	0.6548
	30	Clean	0.8561	0.8829	0.9023	0.9144	0.4277	0.9221
		5 × 5	0.7745	0.8543	0.8813	0.8895	0.7913	0.8989
		8 × 8	0.7281	0.7602	0.7459	0.7766	0.6387	0.7900
		10 × 10	0.7228	0.7295	0.6626	0.6805	0.5974	0.7046
D3	3	Clean	0.4188	0.8712	0.8130	0.4870	0.2130	0.8851
		10%	0.4008	0.2657	0.5454	0.3702	0.2454	0.6236
		20%	0.3573	0.1741	0.4949	0.3082	0.1800	0.5637
		30%	0.3126	0.0200	0.4427	0.3215	0.1042	0.3843
	5	Clean	0.4224	0.7805	0.5714	0.6398	0.3714	0.8190
		10%	0.4703	0.5853	0.4749	0.4872	0.2749	0.5723
		20%	0.3817	0.3917	0.4856	0.4606	0.1856	0.4908
		30%	0.3463	0.2234	0.4470	0.4507	0.1470	0.4109
	8	Clean	0.4420	0.6417	0.5438	0.7066	0.2545	0.5757
		10%	0.5266	0.5351	0.4895	0.5647	0.2372	0.5979
		20%	0.4449	0.4240	0.4523	0.5982	0.1675	0.4959
		30%	0.3917	0.3253	0.4420	0.4658	0.1420	0.5457
D4	10		0.6362	0.3120	0.6299	0.6413	0.5500	0.6360
	20		0.6810	0.5065	0.6500	0.6488	0.5121	0.6541
	30		0.7030	0.5542	0.6741	0.6760	0.5935	0.6912

² The best NMI on each test set is shown in bold.

, respectively, the best ACC and NMI on each test set are shown in bold.

We observe that for each pair of algorithm and dataset, both the ACC and NMI decrease generally with the increasing of the noise levels, which verifies that the noise will hurt the performance of each algorithm. For the dataset D₁, in terms of ACC and NMI, no algorithm achieved the best performance in all test cases. The main reason for these phenomena is that D₁ is a dataset with outliers, which are data from different data models, rather than a simple situation that is floating between subspaces [19]. All the algorithms try to express the outliers in the subspaces of the main body of the data, but the randomness of the outliers and the distinct differences between them make the expression more uncertain, and then the performance of some algorithms decreases abruptly or even increases with the increasing of the noise levels. For example, the ACC of SBDR decreases from 0.8465 to 0.5115 when the noise level increases from 1% to 3%, and the ACC of RBDR increases from 0.8425 to 0.9230 when the noise level increases from 0 to 1%. Similar things happen with the NMI results. However, with regard to ACC and NMI, the performance of OBDR decreases gradually and monotonically with the increasing noise levels, which shows the stability of OBDR on the noisy data with outliers. Additionally, among these algorithms, the SBDR and the OBDR are the top two algorithms in terms of both ACC and NMI. Specifically, in terms of ACC, the OBDR wins in six test cases, and the second best one is the SBDR, which wins in four cases. However, in terms of NMI, the SBDR wins in 11 cases, and the second best one is OBDR, which wins in 3 cases. The two algorithms work in different ways. The SBDR pursues the structure of subspaces at the expense of long running time (see Figure 5), and achieves the best NMIs in most cases on D₁. However, the OBDR models the outliers and separates the noises from the subspaces, thus it has the second better performance. On the datasets D₂ and D₃, the OBDR has significant advantages over the compared algorithms, including the SBDR with regard to ACC and NMI. As the dataset D₄ is concerned, when the data set is corrupted by various noises simultaneously, the OBDR wins in all the three cases in terms of ACC, while the SSC wins in two out of three cases with regard to NMI.

Moreover, we report the wins/ties/losses (W/T/L) and average ranks to record times of best performance and overall performance of the algorithms, respectively. From

Table 5. W/T/L, average ranks and p-values.

		SSC	LRR	BDR	SBDR	RBDR	OBDR	p-Value
ACC	W/T/L	0/0/42	6/0/36	1/1/40	5/0/37	1/1/40	28/0/14 3
	Av. ranks	4.65	3.65	3.33	2.73	5.24	1.50	1.0 × 10−21
NMI	W/T/L	2/0/40	4/0/38	2/0/40	14/0/28	1/0/41	19/0/23
	Av. ranks	4.12	3.55	3.52	2.42	5.20	2.19	1.2 × 10−14

³ The best performance is shown in bold.

, we observe that, in view of W/T/L, OBDR performs significantly better than other algorithms on the test datasets. Specifically, the OBDR wins in 28 and 19 out of the 42 cases in terms of ACC and NMI, respectively, which are higher than that of other algorithms. In terms of average rank, we observe that OBDR is better than the others. Lower ranks are better, and OBDR is the algorithm with the lowest average ranks in terms of ACC and NMI (average rank = 1.50 and 2.19, respectively), and SBDR is the second lowest one (average rank = 2.73 and 2.42, respectively). Meanwhile, we calculate the p-values of the Friedman test [49] for statistical comparison between the six algorithms. The results are shown in Table 5. In terms of both ACC and NMI, Friedman test results are significant at α = 0.05 significance level. Thus, the six algorithms perform significantly different from each other at the test datasets.

As shown in Table 3, Table 4 and Table 5, on the noisy data sets, both ACC and NMI of OBDR obtained the most times of best performance and the best average ranks, thus OBDR can handle various data noise corruptions better than the compared algorithms. Furthermore, we conduct pairwise comparisons using the Nemenyi multiple comparison test [50], as shown in

Table 6. The p-values of using the Nemenyi multiple comparison test on Dataset1~Dataset4.

		SSC	LRR	BDR	SBDR	RBDR
ACC	LRR	0.0729	-	-	-	-
	BDR	0.0153	0.9952	-	-	-
	SBDR	3.4 × 10−5	0.3353	0.6725	-	-
	RBDR	0.7094	0.0005	4.5 × 10−5	1.1 × 10−8	-
	OBDR	2.0 × 10−13	7.8 × 10−6	0.0001	0.0319	7.1 × 10−14
NMI	LRR	0.7273	-	-	-	-
	BDR	0.6911	1.0000	-	-	-
	SBDR	0.0004	0.0623	0.0729	-	-
	RBDR	0.0849	0.0007	0.0006	1.3 × 10−10	-
	OBDR	3.4 × 10−5	0.0114	0.0139	0.9938	2.5 × 10−12

. We observe that at the significance hypothesis level α = 0.05, OBDR is significantly different from all compared algorithms in terms of ACC, and significantly different from all compared algorithms except SBDR in terms of NMI, indicating that the SBDR is also robust to data noises. In addition, RBDR does not show good clustering performance, possibly due to its special preprocessing methods of data sets [39]. Overall, the OBDR outperforms the compared algorithms with regard to the evaluation metrics.

Figure 5 records the computational time of algorithms on Dataset1~Dataset4 with the maximum number of clusters, i.e., Dataset1(6), which denotes Dataset1 with six subjects. It can be seen that SBDR achieves good performance but needs to take a long time to update the subspace structure matrix.

4.4. Parameter Analysis

Fixing the number of iterations of Algorithm 1, ρ will directly affect the clustering performance of OBDR. In this section, we search the optimal values of ρ in OBDR on different data sets. We use noise-free data with the maximum number of clusters in Dataset1~Dataset3 as the test sets, such as Dataset1(6). The maximum iteration times of OBDR is set to 500, and the values of λ and γ are set as Table 2. The effect of ρ on OBDR is shown in Figure 6.

Based on Figure 6, ρ is set to 2.0, 1.05, and 1.45 on Dataset1, Dataset2 (Dataset4), and Dataset3, respectively. After fixing ρ, we also conduct the experiments to test the sensitivity of λ and γ. The results are shown in Figure 7. From Figure 7, we can see that OBDR is more sensitive to λ than γ on all three datasets. It is observed that OBDR has steady clustering performance when λ is within [1, 100], and the parameter values in Table 2 are sound for the three datasets.

5. Conclusions

In this paper, we proposed the robust subspace clustering with block diagonal representation algorithm (OBDR). OBDR reduces the influence of noises on the construction of the coefficient matrix via l_2,1 norm and F norm, recovers the block diagonal spatial structure distribution of data by the Laplacian rank constraint, and thus improves the clustering performance. Experiments on several artificial noisy datasets demonstrate the effectiveness of OBDR in dealing with complex noises. In this study, the OBDR is evaluated on the noisy face datasets and handwritten digit datasets, and the results show that the OBDR has advantages over the compared algorithms with regard to the evaluation metrics. Moreover, the OBDR can be applied in other subspace clustering tasks, such as motion segmentation, image segmentation, and object clustering. In the future, we plan to investigate subspace clustering with deep learning on more high dimensional data. Since the deep learning network can transform the input data into a low dimensional latent space [51,52,53,54,55,56], combining of OBDR and the deep learning network (e.g., AutoEncoder) is worthy of careful study.