Non-negative sparse Laplacian regularized latent multi-view subspace clustering

Abstract

Recently, in the area of artificial intelligence and machine learning, subspace clustering of multi-view data is a research hotspot. The goal is to divide data samples from different sources into different groups. We proposed a new subspace clustering method for multi-view data which termed as Non-negative Sparse Laplacian regularized Latent Multi-view Subspace Clustering (NSL2MSC) in this paper. The method proposed in this paper learns the latent space representation of multi view data samples, and performs the data reconstruction on the latent space. The algorithm can cluster data in the latent representation space and use the relationship of different views. However, the traditional representation-based method does not consider the non-linear geometry inside the data, and may lose the local and similar information between the data in the learning process. By using the graph regularization method, we can not only capture the global low dimensional structural features of data, but also fully capture the nonlinear geometric structure information of data. The experimental results show that the proposed method is effective and its performance is better than most of the existing alternatives.

Introduction

Clustering analysis is a commonly used processing and analysis tool in artificial intelligence and machine learning fields. At present, researchers have proposed a large amount of clustering analysis methods, and have been widely used. However, due to the continuous progress of data science, the rapid development of data sources and access methods, the data obtained is more and more complicated. Among them, multi-view data is a wide-ranging phenomenon. However, traditional clustering methods are mostly proposed and developed for single-view data, in the face of multi-view data clustering, the performance is not ideal. Therefore, how to design a clustering analysis algorithm for multi-view datasets is a huge challenge. In order to effectively solve the problem of multi view data clustering, researchers have proposed many multi view cluster analysis methods from many aspects.

The multi-view clustering analysis algorithm can be roughly divided into two categories: multi-view K-means clustering^1–3 and multi-view spectral clustering algorithm.^4–6 These two types of algorithms are multi-view extensions based on K-means clustering and spectral clustering algorithms, respectively. At present, multi-view k-means clustering algorithm has achieved good performance in many fields, but due to the inherent deficiency of K-means clustering algorithm, the selection of initial central data points has a greater impact on the final clustering results. This greatly limits the application of multi-view k-means clustering algorithms. The multi-view clustering algorithm based on spectral clustering can obtain relatively stable clustering performance. Therefore, many researchers have recently focused on multi-view spectral clustering algorithms.^7–9

Numerous studies have shown that high-dimensional data can usually be embedded in a specific set of low-dimensional subspaces, so the multi-view subspace learning algorithm based on spectral clustering has been widely applied and achieved good performance. Representative algorithms include multi-view subspace clustering algorithm (MSC), ⁷ diversity-induced multi-view subspace clustering algorithm (DiMSC), ⁸ and potential multi-view subspace clustering algorithm (LMSC). ⁹ The MSC ⁷ algorithm learns the self-representation coefficient matrix of each view and unifies it into a common indicator matrix to obtain the final clustering result. However, the MSC algorithm ignores the differences between different views. For this problem, the diversity-induced multi-view clustering algorithm (DiMSC) ⁸ uses the Hilbert-Schmidt independent criterion (HSIC) to learn the diversity of different views and improve the performance of clustering. However, both the MSC and DiMSC algorithms learn the self-representation coefficient matrix of the data in the original space of the data. This may greatly reduce the performance of the cluster due to possible noise in the original space of the data. Therefore, the LMSC ⁹ algorithm will potentially represent combined with subspace clustering in a unified optimization framework, the self-representation coefficient matrix is ​​learned in the potential representation space obtained by learning, which can greatly avoid the influence of noise on the clustering result and improve the clustering performance.

The LMSC ⁹ algorithm adopts low rank representation (LRR) for subspace learning. If all the data in a high dimensional space is actually located on the union of a set of linear subspaces, the LRR can be easily acquired in the data. However, in practical applications, this assumption cannot be guaranteed. The data is often embedded in a low-dimensional manifold structure. For example, widely used face images are sampled from nonlinear low-dimensional manifolds embedded in high-dimensional space. ¹⁰ Therefore, in this case, the LRR method may not be able to discover the inherent geometry and discriminant structure of the data^11,12 and this information is indispensable for practical applications.

In order to maintain the local geometry embedded in high-dimensional space, the researchers proposed a number of manifold learning algorithms, including representative manifolds, locally linear embedding (LLE), ¹³ ISOMAP, ¹⁴ and locality preserving projection (LPP) ¹⁰ neighborhood preserving embedding (NPE) ¹⁵ and Laplacian Eigenmap (LE). ¹⁶ The starting point for all these algorithms is based on the so-called local invariance, ¹⁷ which aims to estimate the geometric and topological result information of an unknown manifold from random points (scattered data).

In practical application, a reasonable assumption is adopted for general production. If two data sample points are very close in the internal manifold of data distribution, then the two points are also very close in a new representation space. ¹⁸ In order to make full use of the inherent geometric structure information of data distribution, Lu et al. ¹² proposed a graph regularization LRR algorithm.

Based on the above analysis, we propose a Laplacian regularized multi-view clustering algorithm based on latent representation. At the same time, we further introduce sparse and non-negative constraints in the algorithm model to improve the performance and rationality of the algorithm.

Related works

Subspace clustering

Let $X=\left[x_1,\mathrm{ }{x}_2,\cdots ,x_N\right]\in R^{d\times N}$ denote a given dataset, where each column represents an instance of a data sample, and each row represents a feature of the data. Assume that the data set can be represented by a union of linear subspaces. The purpose of the subspace learning algorithm is to capture the subspace structure ${\left\{S_i\right\}}_{i=1}^k$ of the data set, where $S_i$ represents the $i$ -th subspace of the dataset. The subspace clustering algorithm adopts the self-expressness characteristics of data sample points that lie in linear subspaces. At present, the researchers have proposed a large number of subspace clustering algorithms, which have similar algorithm model framework which can be expressed as follows:

$${\min }_{Z,E}f\left(Z\right)+g\left(E\right)\text{s.t. }X=XZ+E$$

(1)

Where $Z$ represents a self-representation coefficient matrix, $E$ represents a noise matrix, and $f\left(Z\right)$ represents a regularization term of the coefficient matrix $Z$ . Different subspace clustering algorithms use different regularization terms for $Z$ , and each has a unique effect for $Z$ , but the commonality of such algorithms is to find the subspace structure of the data set. For example, the representative algorithm Sparse Subspace Clustering algorithm (SSC) ¹⁹ uses the $L_1$ -norm to constrain the coefficient matrix $Z$ , thereby ensuring that the obtained coefficient matrix is sparse. The Low Rank Representation algorithm (LRR) ²⁰ uses the nuclear norm constraint for $Z$ , so that the obtained coefficient matrix $Z$ is low rank. And in these algorithm models, different norms are used for different noises $E$ to reduce the influence of noise data on the final result. After obtaining the coefficient matrix $Z$ , the subspace clustering algorithm uses the spectral clustering algorithm to divide the data, and the affinity matrix is constructed as $\left(\left||Z|\right|+\left||Z^T|\right|\right)/2$ .

Multi-view subspace clustering

Multi-view datasets contain a wealth of information from multiple sources, which is very useful for clustering analysis. Therefore, studying multi-view clustering is very important. Based on the single-view subspace clustering algorithm, a low-rank tensor constrained multi-view subspace clustering (LT-MSC) ²¹ is proposed. The algorithm model can be expressed as follows:

$${\min }_{Z^v,E^v}{\Vert Z\Vert }_{\mathrm{*}}+\lambda {\Vert E\Vert }_{2\text{,}1}\text{s.t. }{X}^v=X^v{Z}^v+E^v,v=1,\mathrm{ }\cdots ,m$$

(2)

Where $Z=\mathrm{\varnothing }\left(Z^1,\cdots ,Z^m\right)$ , $E=\left[E^1,\cdots ,E^m\right]$ , $\mathrm{\varnothing }\left(·\right)$ constructs a tensor $Z$ with a dimension of $n\times n\times m$ by combining the representation coefficient matrix $Z^v$ ( $v=1,\cdots ,m$ ) of different views into one 3-order tensor. Finally, the subspace representation of each view is merged through

$$Z=\frac{1}{m}\sum _{v=1}^m\left(\left||Z^v|\right|+{\left||Z^v|\right|}^T\right)$$

(3)

However, the fusion method is too simple to fully and accurately explore the complementary information between different view data samples. At present, there are also many studies that use weight-and rules to fuse multi-view representations. However, it still cannot solve the error problem of multi-view fusion. In the single-view subspace clustering analysis algorithm, the Latent Space Sparse Subspace Clustering (LS3C) ²² algorithm can simultaneously reduce the dimensionality and sparse representation of the data set. Inspired by this idea, the work in ⁹ proposed a latent multi-view subspace clustering (LMSC), which treats different views as projections from the same latent space and performs subspace aggregation on this latent space. The LMSC model can be expressed as follows:

$${\min }_{Z,P,H,E_h,E_r}{\Vert E\Vert }_{2\text{,}1}+\lambda {\Vert Z\Vert }_{\mathrm{*}}\text{s.t. }X=PH+E_h, H=HZ+E_r, E=\left[E_h;\mathrm{ }{E}_r\right], P{P}^T=I$$

(4)

In the above optimization problem, $P={\left[{\left(P^1\right)}^T,\mathrm{ }\cdots ,\mathrm{ }{\left(P^m\right)}^T\right]}^T$ is a projection matrix of the multi-view data and the data set is represented as $X={\left[{\left(X^1\right)}^T,\mathrm{ }\cdots ,\mathrm{ }{\left(X^m\right)}^T\right]}^T$ , $H$ is the shared latent representation.

However, there is a problem of this method is that the complementary information between different data views is ignored, and no structural constraints are used on the representation coefficient matrix $Z$ . In addition, this kind of method needs to use the representation coefficient matrix Z to do spectral clustering to get the final clustering partition result. Therefore, the accuracy of the coefficient matrix Z of the data representation affects the accuracy of the final result.

Non-negative sparse Laplacian regularized latent multi-view subspace clustering (NSL2MSC)

In this paper, we do some research on the subspace clustering problem of multi-view latent representations. Given a multi-view data set ${\left\{\left[x_i^{\left(1\right)};\mathrm{ }\cdots ;\mathrm{ }{x}_i^{\left(V\right)}\mathrm{ }\right]\right\}}_{i=1}^N$ with $V$ different views, the number of samples is $N$ . Many studies of the researchers have shown that different data views can be represented by the same latent representation space.^2,4,7,9 Therefore, the goal of this method is to find such a common latent representation space $h$ for each data sample point.

The objective function of the proposed Non-negative Sparse Laplacian regularized Latent Multi-view Subspace Clustering (NSL2MSC) is formulated as

$${\min }_{P,H,Z,E_h,E_r}{\Vert Z\Vert }_{\mathrm{*}}+{\lambda }_1{\Vert Z\Vert }_1+{\lambda }_2{\sum }_{ij}{\Vert z_i-z_j\Vert }^2{W}_{ij}\hspace{1em}+{\lambda }_3{\Vert E_h\Vert }_{2\text{,}1}+{\lambda }_4{\Vert E_r\Vert }_{2\text{,}1}\text{s.t. }X=PH+E_h\text{, }H=HZ+E_r\text{, }P{P}^T=I\text{, }Z\ge 0$$

(5)

where $P$ and $\mathrm{ }X$ are reconstruction models aligned and the multi-view observations, respectively. $E_r$ and $E_h$ represent the errors because of the subspace representation and the latent representation respectively, $H={\left\{h_i\right\}}_{i=1}^N$ is the shared latent representation.

In the objective function, the third term is the constraint term added based on the manifold assumption. Under the manifold assumption, the relationship between the two samples can be expressed as

$$\min \mathrm{ }{\sum }_{ij}{\Vert z_i-z_j\Vert }^2{W}_{ij}$$

(6)

Where, $z_i$ and $z_j$ are respectively the coefficients matrix of sample points $x_i$ and $x_j$ under some transformations.

Manifold constraints are important for the construction of many algorithm models, such as dimension reduction algorithm, clustering algorithm and semi-supervised learning algorithm. Where $D$ is a diagonal matrix, which represents the degree of the matrix. $D_{ii}$ is the $i$ -th diagonal element, and its value is the sum of all the similarity relationship associated with $y$ , i.e. $D_{ii}={\sum }_j{W}_{ij}$ . Therefore, we can express the objective function of graph Laplacian as follows ⁹

$$L=D-W$$

In addition, the objective function of graph embedding (5) can easily be expressed as follows

$$\min \mathrm{ }tr\left(ZL{Z}^T\right)$$

Therefore, through these algebraic transformations, the model of the proposed method can be represented as the following matrix form

$${\min }_{P,H,Z,E_h,E_r}{\Vert Z\Vert }_{\mathrm{*}}+{\lambda }_1{\Vert Z\Vert }_1+{\lambda }_{2}tr\left(ZL{Z}^T\right)+{\lambda }_3{\Vert E\Vert }_{2\text{,}1}\text{s.t. }X=PH+E_h\text{, }H=HZ+E_r\text{, }\hspace{1em}E=\left[E_h;E_r\right]\text{, }P{P}^T=I\text{, }Z\ge 0$$

(7)

Model optimization

The objective function in equation (6) proposed in this paper can get a latent representation of the data and get meaningful similarity matrix from the latent representation which learns from multiple views. Although for the variables in the algorithm model, such as $P$ , $H$ , $Z$ , $E_h$ and $E_r$ , the proposed method cannot guarantee joint convexity. For each variable we can perform iterative optimization by fixing the other variables separately. For example, LADMAP ²³ algorithm is an effective optimization method to solve this problem.

In order to optimize the objective function, we first introduce an auxiliary variable $J$ into the algorithm model to separate the objective function. In this way, we describe the optimization problem:

$${\min }_{P,H,Z,E_h,E_r,J}{\Vert Z\Vert }_{\mathrm{*}}+{\lambda }_1{\Vert J\Vert }_1+{\lambda }_{2}tr\left(ZL{Z}^T\right)+{\lambda }_3{\Vert E\Vert }_{2\text{,}1}\text{s.t. }X=PH+E_h\text{, }H=HZ+E_r\text{, }E=\left[E_h;E_r\right]\text{, }P{P}^T=I\text{, }Z=J\text{, }J\ge 0$$

(8)

The augmented Lagrange function of the above problem is

$$L\left(P,H,Z,E_h,E_r,J\right)={\Vert Z\Vert }_{\mathrm{*}}+{\lambda }_1{\Vert J\Vert }_1+{\lambda }_{2}tr\left(ZL{Z}^T\right)+{\lambda }_3{\Vert E\Vert }_{2\text{,}1}+\mathrm{\Phi }\left(M_1,H-HZ-E_r\right)+\mathrm{\Phi }\left(M_2,Z-J\right)+\mathrm{\Phi }\left(M_3,P-PH-E_h\right)$$

In addition, in order to facilitate the subsequent calculation and representation, we give the definitions of $\mathrm{\Phi }$ : $\mathrm{\Phi }\left(C,D\right)=\frac{\mu }{2}{\Vert D\Vert }_F^2+〈C,D〉$ , where $\mu$ is a positive penalty scalar and $〈·,\mathrm{ }·〉$ defines the matrix inner product. According to LADMAP, by fixing the other variables, the variables P, H, Z, E, J can be updated by solving the following optimization problems iteratively.

$P$ -subproblem

With the other variables fixed, we obtain the expression of $P$ by solving the following optimization problem

$$P^{*}=\arg \mathrm{\hspace{0.17em}}\min \hspace{0.17em}\Phi \left(M_3,\hspace{0.17em}X-PH-E_h\right)$$

(9)

s.t. $P{P}^T=I$

Theorem 1.

²⁴ Given the objective function ${\min }_R\mathrm{ }{\Vert Q-GR\Vert }_F^2$ s.t. $R^{T}R=R{R}^T=I$ , the optimal solution is $R=U{V}^T$ , where $U$ and $V$ are left and right singular values of SVD decomposition of $G^{T}Q$ .

The optimal solution of the $P$ -subproblem can be easily obtained as $P^T=U{V}^T$ , where $U$ and $V$ are the left and right singular values of SVD of $H{\left(M_3+X-E_h\right)}^T$ , since we have

$$P^{\mathrm{*}}=\arg \mathrm{\hspace{0.17em}}\min \mathrm{\hspace{0.17em}}\Phi \left(M_3,\hspace{0.17em}X-PH-E_h\right)=\arg \mathrm{\hspace{0.17em}}\min \mathrm{\hspace{0.17em}}\frac{\mu }{2}{\Vert X-PH-E_h+M_3\Vert }_F^2=\arg \mathrm{\hspace{0.17em}}\min \mathrm{\hspace{0.17em}}{\Vert \left(X+M_3/\mu -E_h\right)-PH\Vert }_F^2=\arg \mathrm{\hspace{0.17em}}\min \mathrm{\hspace{0.17em}}{\Vert {\left(X+M_3/\mu -E_h\right)}^T-H^T{P}^T\Vert }_F^2$$

According to theorem 1, if $P$ is an orthogonal matrix (i.e. $P^{T}P=P{P}^T=I$ ), then the optimal solution to the p-subproblem is $P^T=U{V}^T$ , where $U$ and $V$ are the left and right singular values of SVD decomposition of $H{\left(\frac{M_3}{\mu }+X-E_h\right)}^T$ . In the practical application, in order to improve the computation efficiency, we relax $P$ to row orthogonal (i.e. $P{P}^T=I$ , where $P\in R^{k\times d}$ , $k\ll d$ ), and in the practical application can also get good performance and convergence.

$H$ -subproblem

With the other variables fixed, we obtain the expression of H by solving the following optimization problem

$$H^{\mathrm{*}}=\arg \mathrm{ }\min \mathrm{ }\mathrm{\Phi }\left(M_3,\mathrm{ }X-PH-E_h\right)+\mathrm{\Phi }\left(M_1,H-HZ-E_r\right)$$

(10)

Taking the derivative with respect to H and setting it to zero, we get

$$AH+HB=C$$

(11)

With $A=\mu P^{T}P$ , $B=\mu \left(Z{Z}^T-Z-Z^T+I\right)$ , $C=\left(P^T{M}_3+M_1\left(Z^T-I\right)\right)+\mu \left(P^{T}X+E_r^T-P^T{E}_h-E_r{Z}^T\right)$ .

The above equation is a Sylvester equation. In order to avoid instability, we strictly limit $A$ to be positive definite by $\widehat{A}=A+ϵI$ , where $I$ is an identity matrix and $0<ϵ\ll 1$ .

Proposition 1.

The Sylvester equation (11) has a unique solution.

Proof.

The Sylvester equation $AH+HB=C$ has a unique solution for $H$ exactly when there are no common eigenvalues of $A$ and $-B$ . Since $\widehat{A}$ is a positive definite matrix, so all of its eigenvalues are positive: ${\alpha }_i>0$ . While since $B$ is a positive semi-definite matrix, so all of its eigenvalues are nonnegative: ${\beta }_i\ge 0$ . Hence, for any eigenvalues of $A$ and $B$ , ${\alpha }_i+{\beta }_i>0$ .

Accordingly, the Sylvester equation (11) has a unique solution.

$\mathit{Z}$ -subproblem

Fix the other variables, we update $Z$ by solving the following problem

$$L_1=\arg \mathrm{ }{\min }_Z\mathrm{ }{\Vert Z\Vert }_{\mathrm{*}}+{\lambda }_{2}tr\left(ZL{Z}^T\right)+\mathrm{\Phi }\left(M_1,\mathrm{ }H-HZ-E_h\right)+\mathrm{\Phi }\left(M_2,Z-J\right)=\arg \mathrm{ }{\min }_Z\mathrm{ }{\Vert Z\Vert }_{\mathrm{*}}+{\lambda }_{2}tr\left(ZL{Z}^T\right)+\frac{\mu }{2}{\Vert Z-J_k+\frac{1}{\mu }{M}_2^k\Vert }_F^2+\frac{\mu }{2}{\Vert H-HZ-E_h^k+\frac{1}{\mu }{M}_1^k\Vert }_F^2$$

which does not have a closed-form solution. By the spirit of LADMAP,²⁵ we denote the smooth component of $L_1$ by

$$q\left(Z,E_k,J_k,M_1^k,M_2^k\right)={\lambda }_{2}tr\left(ZL{Z}^T\right)+\frac{\mu }{2}{\Vert Z-J_k+\frac{1}{\mu }{M}_2^k\Vert }_F^2+\frac{\mu }{2}{\Vert H-HZ-E_h^k+\frac{1}{\mu }{M}_1^k\Vert }_F^2$$

Then according to LADMAP, minimizing $L_1$ can be replaced by solving the following problem:

$$Z^{\mathrm{*}}=\arg \mathrm{ }{\min }_Z\mathrm{ }{\Vert Z\Vert }_{\mathrm{*}}+〈{\nabla }_{Z}q\left(Z_k\right),Z-Z_k〉+\frac{\eta }{2}{\Vert Z-Z_k\Vert }_F^2$$

(12)

where $q\left(Z,E_k,J_k,M_1^k,M_2^k\right)$ is approximated by its linearization $〈{\nabla }_{Z}q\left(Z_k\right),Z-Z_k〉$ at $Z_k$ plus a proximal term $\frac{\eta }{2}{\Vert Z-Z_k\Vert }_F^2$ and ${\nabla }_{Z}q\left(Z_k\right)$ is the gradient of $q$ w.r.t. $Z$ . As long as $\eta >2{\lambda }_2{\Vert L\Vert }_2+\mu \left(1+{\Vert H\Vert }_2^2\right)$ , where ${\Vert ·\Vert }_2$ is the spectral norm of a matrix, i.e. the largest singular value, the above replacement is valid. Then the above equation has a closed-form solution given by

$$Z_{k+1}^{\mathrm{*}}={\mathrm{\Theta }}_{{\left(\eta \right)}^{-1}}\left(Z_k-{\nabla }_{Z}q\left(Z_k\right)/\eta \right)$$

where ${\mathrm{\Theta }}_{\epsilon }\left(A\right)=U{\mathcal{S}}_{\epsilon }\left(\mathrm{\Sigma }\right)V^T$ is the singular value thresholding operator (SVT),²⁵ in which $U\mathrm{\Sigma }{V}^T$ is the singular value decomposition (SVD) of $A$ and ${\mathcal{S}}_{\epsilon }\left(\mathrm{x}\right)=\mathrm{sgn}\left(|x|\right)\mathrm{m}\mathrm{ax}\left(\left|x\right|-\epsilon ,0\right)$ is the soft thresholding operator.

$E$ -subproblem

The reconstruction error $E$ is updated by solving the following problem

$$E^{\mathrm{*}}=\arg \mathrm{ }{\min }_E{\Vert E\Vert }_{2\text{,}1}+\mathrm{\Phi }\left(M_3,X-PH-E_h\right)+\mathrm{\Phi }\left(M_1,H-HZ-E_r\right)=\arg \mathrm{ }{\min }_E\frac{1}{\mu }{\Vert E\Vert }_{2\text{,}1}+\frac{1}{2}{\Vert E-G\Vert }_F^2$$

(13)

where $G$ is formed by vertically concatenating the matrices $\left(X-PH+M_3/\mu \right)$ and $\left(H-HZ+M_1/\mu \right)$ . This subproblem can be efficiently solved by Lemma 3.2 in. ²⁰

$J$ -subproblem

Fix the others, the Lagrange function with respect to $J$ can be written as

$$J^{\mathrm{*}}=\arg \mathrm{ }{\min }_{J\ge 0}\mathrm{ }{\lambda }_1{\Vert J\Vert }_1+\mathrm{\Phi }\left(M_2,Z-J\right)=\arg \mathrm{ }{\min }_{J\ge 0}\mathrm{ }{\lambda }_1{\Vert J\Vert }_1+\frac{\mu }{2}{\Vert J-\left(Z+M_2/\mu \right)\Vert }_F^2$$

(14)

which has the following closed-form solution:

$$J_{k+1}=\max \left\{{\mathcal{S}}_{\frac{{\lambda }_1}{\mu }}\left(Z_{k+1}+\frac{1}{\mu }{M}_2^k\right),0\right\}$$

Updating multipliers

We update the multipliers by

$$\left\{\begin{array}{c}{M}_1=M_1+\mu \left(H-HZ-E_r\right)\\ M_2=M_2+\mu \left(Z-J\right)\\ M_3=M_3+\mu \left(X-PH-E_h\right)\end{array}\right.$$

The entire algorithm is summarized in Algorithm 1.

Algorithm 1: Optimization Algorithm for the proposed NSL2MSC method
Input: Multi-view matrices: $\left\{X^{\left(1\right)},\mathrm{ }\cdots ,X^{\left(V\right)}\right\}$ ; parameter ${\lambda }_1$ , ${\lambda }_2$ and ${\lambda }_3$ ; the dimension $K$ of the latent representation $H$ .
Initialize: $P=0$ , $E_r=0$ , $E_h=0$ , $J=Z=0$ , $M_1=0$ , $M_2=0$ , $M_3=0$ , $\mu ={10}^{-6}$ , $\rho =1.1$ , $ϵ={10}^{-4}$ , ${\max }_{\mu }={10}^6$ ; Initialize $H$ with random values.
While not converged do
Update variables $P,H,Z,E,J$ according to subproblem 1–5;
Update multipliers $M_1,\mathrm{\hspace{0.17em}}{M}_2,\mathrm{\hspace{0.17em}}{M}_3$ according to subproblem 6;
Update the parameter $\mu$ by $\mu =\min \left(\rho \mu ,{\max }_{\mu }\right)$ ;
Check the convergence condition: ${\Vert X-PH-E_h\Vert }_{\mathrm{\infty }}<ϵ$ , ${\Vert H-HZ-E_r\Vert }_{\mathrm{\infty }}<ϵ$ , ${\Vert J-Z\Vert }_{\mathrm{\infty }}<ϵ$ .
End
Output: $\mathit{Z},\mathit{H},\mathit{P},\mathit{E}$

Complexity and convergence

The method proposed in this paper is optimized through six subproblems. The complete algorithm is shown in algorithm 1. Where, the time complexity of solving the $P$ -subproblem is $\mathrm{O}\left(k^{2}d+d^3\right)$ , $k$ , $d$ and $n$ respectively represent the latent space dimensions, the total dimensions of multi-view data features, and the number of data samples. To solve the $J$ -subproblem, the time complexity is $O\left(n^3\right)$ . To solve the $H$ -subproblem, Bartels Stewart algorithm was used to solve Sylvester equation, and the time complexity was $O\left(k^3\right)$ . To solve the $Z$ -subproblem, the main task is to compute the inverse of the matrix, and the time complexity is $O\left(n^3\right)$ . For $E$ subproblems and Lagrange multiplier calculations, the main task is to calculate matrix multiplication, with the time complexity $O\left(\mathit{dkn}+k{n}^2\right)$ . Thus, the total time complexity of each iteration is $O\left(k^{2}d+d^3+k^3+n^3+\mathit{dkn}+k{n}^2\right)$ . The total time complexity can be expressed as $O\left(d^3+n^3\right)$ because of $k\ll d$ . It is difficult to prove the convergence of the algorithm, but the effect of the algorithm on the real dataset shows that the algorithm proposed in this paper has strong convergence and stability even if $H$ is randomly initialized.

Experiments

Experimental setting

Dataset description

We chose four real datasets (MSRCV1,³ Extended YaleB, Still DB, ²⁶ BBCSport ⁵ ) as test data to verify the effectiveness of the proposed method. The basic information for the four datasets is as follows:

– The MSRCV1 dataset contains 240 images in 8 classes. In this experiment, we selected 7 classes of them, such as tree, building, air-plane, cow, face, car and bicycle. In the experiment, we extracted 6 features of each image, namely CENT (view1), CMT (view2), GIST (view3), HOG (view4), LBP (view5) and SIFT (view6). And use these features to make up 6 different views.

– The Extended Yale-B dataset contains a total of 2414 face images of 38 people, each with 64 near frontal images under different illuminations. In the experiment, we select the first 10 classes as the final dataset, which has 640 frontal face images in total, we chose three features of the image, intensity (view1), LBP (view2) and Gabor (view3) to form 3 different views of the dataset.

– The still DB dataset contains 467 images in 6 classes. In the experiment, we extract three features of each image: sift bow (view1), color sift bow (view2) and shape context bow (view3) to form three different views of the dataset.

– The BBCSport dataset contains sports news in five subject areas, all of which are from the BBC sports website and are associated with two views.

Compared methods

We compare the algorithm proposed in this paper with the state-of-the- art algorithm proposed recently. The compared algorithms are as follows:

– SPC: The standard spectral clustering algorithm. In the experiment, we choose the view with the most information to do the spectral clustering.

– LRR ²⁰ : The low rank representation. In the experiment, we run the LRR algorithm on each single view and record the best clustering results.

– Co-Reg SPC ⁴ : In this method, the clustering method is combined with regularization to make the corresponding data points in the same cluster.

– RMSC ⁵ : This method first clusters each view, and then uses the shared low-rank transition probability matrix to integrate them to get better clustering results.

– FCMSC²⁷: The algorithm deals with the problem that multiple views have different statistic properties and simply concatenating them directly cannot derive a satisfied clustering performance.

– LMSC ⁹ : This method searches for latent representations and reconstructs the data according to the learned latent representations.

Experimental results

Performance comparison

To evaluate the characteristics of each algorithm, we adopt four evaluation indexes, NMI (normalized mutual information), ACC (accuracy), F-measure and RI (rand index). For the 5 compared algorithms in the experiment, we adjust all parameters to the best performance in the corresponding paper. In the experiment, for all experimental data sets, the dimension of latent space of the proposed algorithm is set to $K=500$ , and the value range of three parameters ${\lambda }_1,{\lambda }_2,{\lambda }_3$ is from $\left\{1e^{-3},1e^{-2},1e^{-1},1\text{,}1e^1,1e^2,1e^3\right\}$ .

For each algorithm, we run it 30 times independently and give the mean value and standard deviation.

The detailed clustering results of the proposed algorithm and the comparison algorithm on four real datasets are shown in Tables 1–4.

Table 1.

Clustering results on the MSRCV1 dataset.

Method	NMI		ACC		F-Measure		RI
	Mean	Std	Mean	Std	Mean	Std	Mean	Std
SPC	0.5961	0.0267	0.6831	0.0441	0.5566	0.0414	0.8698	0.0089
LRR	0.5235	0.0153	0.6063	0.0025	0.4743	0.0056	0.8612	0.0007
Co-Reg SPC	0.6056	0.0134	0.6993	0.0123	0.5581	0.0203	0.9025	0.0028
RMSC	0.5987	0.0059	0.7161	0.0072	0.6092	0.0151	0.8886	0.0023
FCSMC	0.6852	0.0031	8.8213	0.0117	0.6906	0.0139	0.9071	0.0032
LMSC	0.6724	0.0117	0.8121	0.0115	0.6713	0.0159	0.9027	0.0017
NSL2MSC	0.7206	0.0121	0.8469	0.0101	0.7037	0.0126	0.9258	0.0026

Table 2.

Clustering results on the Extended Yale B dataset.

Method	NMI		ACC		F-Measure		RI
	Mean	Std	Mean	Std	Mean	Std	Mean	Std
SPC	0.3807	0.0115	0.3815	0.0349	0.3049	0.0117	0.2347	0.0139
LRR	0.6345	0.0048	0.6286	0.0145	0.5263	0.0069	0.4511	0.0019
Co-Reg SPC	0.1819	0.0054	0.2073	0.0076	0.1703	0.0008	0.0882	0.0006
RMSC	0.1627	0.0119	0.1868	0.0136	0.1672	0.0107	0.0718	0.0123
FCSMC	0.7175	0.0104	0.6269	0.0140	0.5853	0.0097	0.5764	0.0167
LMSC	0.7231	0.0111	0.7328	0.0152	0.6259	0.0082	0.5825	0.0121
NSL2MSC	0.8026	0.0117	0.7818	0.0120	0.7406	0.0038	0.7121	0.0058

Table 3.

Clustering results on the still DB dataset.

Method	NMI		ACC		F-Measure		RI
	Mean	Std	Mean	Std	Mean	Std	Mean	Std
SPC	0.1056	0.0075	0.2928	0.0065	0.2222	0.0073	0.7319	0.0063
LRR	0.1125	0.0026	0.3146	0.0041	0.2473	0.0051	0.7353	0.0008
Co-Reg SPC	0.1055	0.0018	0.2701	0.0028	0.2317	0.0039	0.7414	0.0004
RMSC	0.1188	0.0063	0.2917	0.0197	0.2383	0.0204	0.7359	0.0051
FCSMC	0.1406	0.0072	0.3187	0.0021	0.2728	0.0046	0.7428	0.0056
LMSC	0.1418	0.0036	0.3289	0.0031	0.2709	0.0058	0.7426	0.0002
NSL2MSC	0.1521	0.0047	0.3442	0.0058	0.2838	0.0062	0.7569	0.0006

Table 4.

Clustering results on the BBCSport dataset.

Method	NMI		ACC		F-Measure		RI
	Mean	Std	Mean	Std	Mean	Std	Mean	Std
SPC	0.7084	0.0058	0.8005	0.0332	0.7633	0.0035	0.8919	0.0008
LRR	0.6983	0.0022	0.7913	0.0035	0.7715	0.0028	0.8816	0.0015
Co-Reg SPC	0.7242	0.0008	0.7556	0.0057	0.7722	0.0013	0.8930	0.0006
RMSC	0.8133	0.0102	0.8428	0.0139	0.8772	0.0090	0.9265	0.0027
FCSMC	0.8352	0.0104	0.8785	0.0041	0.8849	0.0053	0.9377	0.0019
LMSC	0.8263	0.0071	0.9031	0.0052	0.8871	0.0071	0.9465	0.0006
NSL2MSC	0.8536	0.0063	0.9436	0.0067	0.9048	0.0066	0.9617	0.0011

Table 1 shows the clustering results on the MSRCV1 data set. On the MSRCV1 dataset, we can see that the proposed method is much better than the compared method. The reason behind this is that the latent representation space learned can make better use of multiple views of data.

Table 2 shows the clustering performance on the Extended YaleB dataset. The clustering performance of most algorithms on this dataset is poor, the main reason is that the illumination changes greatly in the dataset, which seriously affects the clustering performance. However, the NSL2MSC algorithm proposed in this paper has achieved better results. It is 7.95%, 4.9%, 11.47% and 12.96% higher than LMSC algorithm in NMI, ACC, F-measure and RI indexes, respectively.

Table 3 shows the clustering results on the still DB dataset. The clustering performance of each algorithm is not very good. However, from the four indicators, the NSL2MSC algorithm proposed in this paper has achieved relatively promising clustering results.

Table 4 shows the clustering results on BBCSport dataset. The clustering performance of NSL2MSC proposed in this paper is at least 2% higher than that of RMSC. Compared with LMSC method, our NSL2MSC method still achieves better result.

Parameters effect

In the NSL2MSC algorithm model proposed in this paper, there are several regularization parameters. Next, the Extended YaleB data set is taken as an example to test the effect of the four parameters ${\lambda }_1,{\lambda }_2,{\lambda }_3$ and $K$ on ACC and NMI. We change one parameter while fixing the other. Figure 1 shows the ACC and NMI results for different parameter settings on the Extended Yale B dataset. It clearly can be seen that the results show that in a large range of parameters, the NSL2MSC algorithm is superior to other algorithms.

Figure 1.

The parameter effect of ${\mathit{\lambda }}_1,{\mathit{\lambda }}_2,{\mathit{\lambda }}_3$ and $\mathbf{K}$ on Extended Yale-B dataset with ACC and NMI metrics, respectively.

Conclusion

In this paper, a new multi view subspace clustering method was proposed, which is called NSL2MSC. The main innovation of this algorithm lies in the use of graph regularization to make full use of the complementary information among views in the process of learning multi view latent subspace representation. In this way, this method can not only represent the global information of the data, but also can capture the local geometric structure information of the data. A large number of image clustering experiments show the effectiveness of this method.