# Robust Semisupervised Nonnegative Local Coordinate Factorization for Data Representation

Authors: Wei Jiang; Qian Lv; Chenggang Yan; Kewei Tang; Jie Zhang
Journal: Complexity
 (2018)

---

## Abstract

Obtaining an optimum data representation is a challenging issue that arises in many intellectual data processing techniques such as data mining, pattern recognition, and gene clustering. Many existing methods formulate this problem as a nonnegative matrix factorization (NMF) approximation problem. The standard NMF uses the least square loss function, which is not robust to outlier points and noises and fails to utilize prior label information to enhance the discriminability of representations. In this study, we develop a novel matrix factorization method called robust semisupervised nonnegative local coordinate factorization by integrating robust NMF, a robust local coordinate constraint, and local spline regression into a unified framework. We use thel2,1 norm for the loss function of the NMF and a local coordinate constraint term to make our method insensitive to outlier points and noises. In addition, we exploit the local and global consistencies of sample labels to guarantee that data representation is compact and discriminative. An efficient multiplicative updating algorithm is deduced to solve the novel loss function, followed by a strict proof of the convergence. Several experiments conducted in this study on face and gene datasets clearly indicate that the proposed method is more effective and robust compared to the state-of-the-art methods.


---

## Body

## 1. Introduction

Owing to the rapid development of data collection and storage techniques, there has been an increase in the demand for effective data representation approaches [1] to cope with image and gene information, particularly in the fields of pattern recognition, machine learning, and gene clustering. For large databases, an efficient representation of data [2–4] can improve the performance of numerous intelligent learning systems such as those used for classification and clustering analysis. In many application fields, the input samples are represented in high-dimensional form, which is infeasible for direct calculation. The efficiency and effectiveness of learning models exponentially decrease with each increase in the dimensionality of input samples, which is generally referred to as the “curse of dimensionality.” Accordingly, dimensionality reduction [5–7] is becoming increasingly important as it can overcome the curse of dimensionality, enhance the learning speed, and even offer critical insights into the essence of the issue. In general, dimensionality reduction methods can be divided into two categories: feature extraction [5, 8, 9] and selection [10–14]. Feature selection involves selecting discriminative and highly related features from an input feature set, whereas feature extraction combines original features to form new features of data variables.In recent years, there has been an increasing interest in feature extraction. Many feature extraction methods are designed to obtain a low-dimensional feature of high-dimensional data. These methods include singular value decomposition (SVD), principal component analysis (PCA) [5], nonnegative matrix factorization (NMF) [15, 16], and concept factorization (CF) [17]. Despite the different motivations of these models, they can all be interpreted as matrix decomposition, which often finds two or more low-dimensional matrices to approximate the original matrix. Factorization leads to a reduced representation of high-dimensional data and belongs to the category of methods employed for dimension reduction.Unlike PCA [5] and SVD, NMF [15, 16] factorizes a sample matrix as a product of two matrices constrained by nonnegative elements. One matrix comprises new basis vectors that reveal the semantic structure, and the other matrix can be regarded as the set of coefficients composed of linear combinations of all sample points based on the new bases. Owing to their ability to extract the most discriminative features and their feasibility in computation, many extension versions [4, 18, 19] of NMF have been developed from various perspectives to enhance the original NMF. Sparseness-constrained NMF [20] has been introduced by adding l1 norm minimization on the learned factor matrices to enhance sparsity for data representation. Fisher’s criterion [21] has been incorporated into NMF formulation and is used to achieve discriminant representation. The semi- and convex-NMF formulations [22] relax the nonnegativity constraint of NMF by allowing the basis and coefficient matrices to have mixed signs, thereby extending the applicability of the method. Liu et al. [23] proposed a constrained NMF in which the label information is incorporated into the standard NMF for data representation. Cai et al. [24] extended NMF and proposed a graph-regularized NMF (GNMF) scheme, which imposes intrinsic geometry latent in a high-dimensional dataset onto the traditional NMF using an affinity graph. Chen et al. [9] presented a nonnegative local coordinate factorization (NLCF) method that imposes locality constraint onto the original NMF to explore faithful intrinsic geometry.Traditional NMF and its variants usually adopt the square Euclidean distance to measure the approximation error. Although it has a solid theoretical foundation in mathematics and has shown encouraging performance in most cases, the square Euclidean distance is not always optimal for decomposition of a data matrix. The squared error has proved to be the best for both Gaussian and Poisson noise [25]. However, in real-world applications, data that violate the assumptions are usually involved. The squared loss is sensitive to outlier points and noises when the reconstruction error is measured. Even a single outlier point may sometimes easily dominate the objective function. In recent years, some variants have been presented to enhance the robustness of the classical NMF. A robust type of NMF that factorizes the sample matrix as the summation of two nonnegative matrices and one sparse error matrix was presented by Zhang et al. [26]. Zhang et al. [27] presented a robust NMF (RNMF) using the l2,1 norm objective function, which can deal with outlier points and noises. Zhang et al. [28] presented a robust nonnegative graph-embedding framework (RNGE) that can simultaneously cope with noisy labels, noisy data, and uneven distribution.Supervised learning algorithms [29–32] generally can achieve better performance than unsupervised learning techniques when label information is available in many applications. The motivation of semisupervised learning methods [33–38] is to employ numerous unlabeled samples as well as relatively few labeled samples to construct a better high-dimensional data analysis model. A surge of research interest in graph-based semisupervised learning techniques [37–39] [40] has recently occurred. Gaussian fields and harmonic functions (GFHF) [33] is an efficient and effective semisupervised learning methods in which the predicted label matrix is reckoned on the graph with respect to manifold smoothness and label fitness. Xiang et al. [37] presented a method called local spline regression (LSR) in which an iterative algorithm is built on local neighborhoods through spline regression. Han et al. [38] presented a model of video semantic recognition using semisupervised feature selection via spline regression (S2FS2R). These methods not only consider label information but also employ the local and global structure consistency assumption.Despite NMF’s appealing advantages, it suffers from the following problems in real-world applications: (1) data may often be contaminated by noise and outliers due to illumination (e.g., specular reflections), image noises (e.g., scanned image data), occlusion (e.g., sunglasses and scarf in front of a face), among others. Although NMF can deal with noise in the test data to some extent, it will suffer from severe performance degradation when the training samples have noise. (2) In an NMF method, a data point may be represented by the base vectors, which are far from the data point, resulting in poor clustering performance. The standard NMF does not preserve the locality during its decomposition process, whereas local line coding can preserve such properties. (3) One of the challenges for classification tasks in the real world is the lack of labeled training data. Therefore, data labeled by an expert is often used as an alternative. Unfortunately, designating labels requires considerable human effort and is thus time-consuming and difficult to manage. In addition, an accurate label may require expert knowledge. However, unlabeled samples are relatively easy to obtain.To address all the aforementioned issues, we present an efficient and effective matrix factorization framework called robust semisupervised nonnegative local coordinate factorization (RSNLCF) in which both data reconstruction functions and a local coordinate constraint regularization term are formulated in al2,1 norm manner to make our model robust to outlier points and noises. By integrating Green’s functions and a set of primitive polynomials into the local spline, the local and global label consistency of data can be characterized based on their distribution. The main work of our study and its contributions are summarized as follows:
(i)
The proposed RSNLCF model is robust to outlier points and noises as a result of employing thel2,1 norm formulations of NMF and a local coordinate constraint regularization term. In addition, to guarantee that the data representation is discriminative, local spline regression over labels is exploited.
(ii)
Unlike traditional dimension reduction approaches that treat feature extraction and selection separately, the proposed RSNLCF algorithm integrates the two aspects into a single optimization framework.
(iii)
We present an efficient algorithm to solve the presented RSNLCF model and provide the proof of rigorous convergence and correctness analysis of our model.The remainder of this paper is organized as follows. Related studies are introduced in Section2. We introduce our RSNLCF method and the optimization scheme in Section 3 and offer a convergence proof in Section 4. We describe and analyze the results of our experiments in Section 5. We conclude and discuss future work in Section 6.


## 2. Related Work

In this section, we summarize the notations and definitions of norm used in this study and briefly review NMF.


### 2.1. Notations and Definitions

Matrices and vectors are denoted by boldface capital and lowercase letters, respectively.xp=∑i=1nxip1/p denotes the lp norm of the vector x∈Rn. xi and xj denote the ith row and the jth column of matrix X=xij, respectively. xij is the element in the ith row and jth column of X, TrX denotes the trace of X if X is a square matrix, and XT denotes the transposed matrix of X. The Frobenius norm of the matrix X∈RM×N is defined as
(1)XF=∑i=1M∑j=1Nxij2.Thel2,1 norm of a matrix is defined as
(2)X2,1=∑i=1Mxi2=∑i=1M∑j=1Nxij2=TrXTDX,where D is a diagonal matrix with Dii=1/2xi2. However, xi2 could approach zero. For this case, we define Dii=1/2xi2+ε, where ε is a very small constant.Assume that the matrix samples are represented asX=xii=1L,xjj=L+1N, where xii=1L,xjj=L+1N denotes labeled and unlabeled data, respectively. The labels of xi∣i=1L are denoted as li∈1,2,…,Lc with Lc being the total number of categories. Let F∈RL×Lc be a label indicator binary matrix with the jth entry fij=1 if and only if xi is labeled with the jth class; fij=0 otherwise. We also introduce a predicted label matrix Y∈RN×Lc, where each row is the predicted label vector of the data xi.


### 2.2. NMF

Given a nonnegative matrixX∈R+M×N, each column of X is a sample point. The main idea of NMF is to find two nonnegative matrices U=uik∈R+M×K and V=vjk∈R+K+N that minimize the Euclidean distance between X and UV. The corresponding optimization problem is as follows:
(3)minU,VX−UVF2s.t.U≥0,V≥0,where ·F is the Frobenius norm. To solve the objective function, Lee and Seung [15] proposed an iterative multiplicative updating algorithm as follows:
(4)ujkt+1←ujktXVTjkUVVTjk,vkit+1←vkitUTXkiUTUVki.By NMF, each column ofU and ui can be viewed as the basis, while the matrix V can be treated as the set of the coefficients. Each sample point xi is approximated by a linear combination of the K bases, weighted by components of V.


## 2.1. Notations and Definitions

Matrices and vectors are denoted by boldface capital and lowercase letters, respectively.xp=∑i=1nxip1/p denotes the lp norm of the vector x∈Rn. xi and xj denote the ith row and the jth column of matrix X=xij, respectively. xij is the element in the ith row and jth column of X, TrX denotes the trace of X if X is a square matrix, and XT denotes the transposed matrix of X. The Frobenius norm of the matrix X∈RM×N is defined as
(1)XF=∑i=1M∑j=1Nxij2.Thel2,1 norm of a matrix is defined as
(2)X2,1=∑i=1Mxi2=∑i=1M∑j=1Nxij2=TrXTDX,where D is a diagonal matrix with Dii=1/2xi2. However, xi2 could approach zero. For this case, we define Dii=1/2xi2+ε, where ε is a very small constant.Assume that the matrix samples are represented asX=xii=1L,xjj=L+1N, where xii=1L,xjj=L+1N denotes labeled and unlabeled data, respectively. The labels of xi∣i=1L are denoted as li∈1,2,…,Lc with Lc being the total number of categories. Let F∈RL×Lc be a label indicator binary matrix with the jth entry fij=1 if and only if xi is labeled with the jth class; fij=0 otherwise. We also introduce a predicted label matrix Y∈RN×Lc, where each row is the predicted label vector of the data xi.


## 2.2. NMF

Given a nonnegative matrixX∈R+M×N, each column of X is a sample point. The main idea of NMF is to find two nonnegative matrices U=uik∈R+M×K and V=vjk∈R+K+N that minimize the Euclidean distance between X and UV. The corresponding optimization problem is as follows:
(3)minU,VX−UVF2s.t.U≥0,V≥0,where ·F is the Frobenius norm. To solve the objective function, Lee and Seung [15] proposed an iterative multiplicative updating algorithm as follows:
(4)ujkt+1←ujktXVTjkUVVTjk,vkit+1←vkitUTXkiUTUVki.By NMF, each column ofU and ui can be viewed as the basis, while the matrix V can be treated as the set of the coefficients. Each sample point xi is approximated by a linear combination of the K bases, weighted by components of V.


## 3. The Proposed RSNLCF Framework

In this section, we introduce our novel learning method for image clustering (RSNLCF), which is used to find an effective and robust representation of data.


### 3.1. Robust Sparse NMF

The square loss function based on the Frobenius norm is used to learn the data representations in NMF. However, it is very sensitive to outlier points and noises. Therefore, our robust representation model is represented as(5)minU,VX−UV2,1+λV2,1,where λ>0 is the regularization parameter. Because the l2,1 norm reduces the components occupied by the large magnitude of error in the loss function, the corrupted samples never dominate the objective function. In this sense, the loss function X−UV2,1 is insensitive to outlier points and noises. Meanwhile, the regularization term V2,1 ensures that V is sparse in rows. This means that some of V’s rows approximate zero. Consequently, V can be considered the combination coefficient for the most discriminative features. Feature selection is then achieved by V, where only the features related to the nonzero rows in V are chosen.


### 3.2. Robust Local Coordinate Constraint

Motivated by the concept of local coordinate coding [41], we present a robust local coordinate constraint as a regularization term for image clustering. First, we define coordinate coding.Definition 1.
Coordinate coding [41] can be written as concept pair (γ, C), where C is defined as a set of anchor points with d dimensions and γ is a map of x∈Rd to γvxv∈Cγvxv. It induces the following physical approximation of x in Rd:γx=∑v∈Cγvxv.For the local coordinate coding system, NMF can be considered as coordinate coding in which the columns of the matrixU can be viewed as a set of anchor points, and each column of the coefficient matrix V represents the corresponding coordinate coding for each data point. We might further hope that each sample point is represented as a linear combination of only a few proximate anchor points. A natural assumption here would be that if xi is far away from the anchor points uk, then its coordinate coding vki with respect to uk will tend to be zero and thus achieve sparsity and locality simultaneously. The local coordinate constraint [41] can be defined as follows:
(6)minU,V∑i=1N∑k=1Kvkiuk−xi22=minU,V∑i=1Nxi1T−UΛi1/2F2,where xi denotes the ith column of X, uk is the kth column of U, vki is the coordinate of xi with respect to uk, and Λi=diagvi∈RK×K, diagvi indicates a conversion of the vector vi into a diagonal matrix in which the kth diagonal element is vki.The local coordinate constraint employs a square loss. When the dataset is corrupted by outlier points and noises, the local coordinate constraint may fail to achieve sparsity and locality simultaneously. In order to alleviate the side effect of noisy data, our robust local coordinate constraint can be formulated as(7)minU,V∑i=1Nxi1T−UΛi1/22,1,where the Frobenius norm-based square loss function has been substituted by the l2,1 norm.


### 3.3. Local Spline Regression

In this subsection, we briefly introduce local spline regression [42].GivenN data points x1,x2,…,xN sampled from the underlying submanifold M, we use set Nxi=xijj=1k to denote xi and its k−1 nearest neighbor points, where ij∈1,2,…,N, and Yi=yi1,yi2,…,yikT is the local predicted label matrix for the ith region. The task of local spline regression is to seek the predicting function gi:RM→ℝ in order to map each data point xij∈RM to the local predicted class label yij=gixij. The model of local spline regression can be expressed as
(8)mingi∑j=1kyij−gixij2+γSgi,where Sgi is a regularization term and γ>0 is a small positive regularization parameter to control the smoothness of the spline [42]. If Sgi is defined as a seminorm of a Sobolev space, gi can be solved by the following objective function [43]:
(9)gix=∑j=1dβi,jpjx+∑j=1kαi,jGi,jx,where d=CM+s−1s, in which s is the order of the partial derivatives [43]. pjxj=1d and Gi,j are a set of primitive polynomials and a Green’s function, respectively. The coefficients αi and βi can be achieved by solving the following problem:
(10)KiPiTPi0αiβi=Yi0,where Ki is a symmetrical matrix with elements Kr,c=Gr,cxir−xic, and Pi is a matrix with its elements Pi,j=pixij. The local spline regression model can then be expressed as [42]
(11)minYiYiTMiYi,where Mi is the upper left k×k submatrix of the inverse matrix of the coefficient matrix in (10). Because the local predicted label matrix Yi is a part of the global predicted label matrix Y, we can construct a selection matrix Si∈Rk×N for each Yi such that
(12)Yi=SiY,where the selection matrix Si is defined as follows:
(13)Sir,c=1,ifr=ic,0,otherwise.After the local predicted label matrices are established, we combine them by minimizing the following loss function:(14)minYi∑i=1NYiMiYi=∑i=1NYTSiTMiSiY=YTMY,where
(15)M=∑i=1NSiTMiSi.Based on the studies of [33, 34], the predicted label matrix Y of the labeled data points should be consistent with the ground truth labels matrix F. With the consistence constraints, the objective function (14) can be written as follows:
(16)minYTrYTMY+ηTrY−FTEY−F,where E is a diagonal matrix whose diagonal elements are 1 for labeled data and 0 for unlabeled data, and the elements of F are defined as follows:
(17)fij=1,ifxiislabeledasclassj,0,otherwise.Whenη is sufficiently large, the optimal solution Y to the problem (16) makes the second term approximately equal to zero. Thus, the objective function (16) guarantees local and global structural consistency over labels. All the elements of Y are restricted to be nonnegative.


### 3.4. Objective Function of RSNLCF

By combining the RNMF (5), robust local coordinate constraint (7), and semisupervised local spline regression (16) into a unified framework, we can formulate the objective function as follows:
(18)minU,VX−UV2,1+μ∑i=1Nxi1T−UΛi1/22,1+λV2,1+τTrYTMY+ηY−FTEY−F,where τ and μ are two trade-off parameters. We call (18) our proposed RSNLCF.


## 3.1. Robust Sparse NMF

The square loss function based on the Frobenius norm is used to learn the data representations in NMF. However, it is very sensitive to outlier points and noises. Therefore, our robust representation model is represented as(5)minU,VX−UV2,1+λV2,1,where λ>0 is the regularization parameter. Because the l2,1 norm reduces the components occupied by the large magnitude of error in the loss function, the corrupted samples never dominate the objective function. In this sense, the loss function X−UV2,1 is insensitive to outlier points and noises. Meanwhile, the regularization term V2,1 ensures that V is sparse in rows. This means that some of V’s rows approximate zero. Consequently, V can be considered the combination coefficient for the most discriminative features. Feature selection is then achieved by V, where only the features related to the nonzero rows in V are chosen.


## 3.2. Robust Local Coordinate Constraint

Motivated by the concept of local coordinate coding [41], we present a robust local coordinate constraint as a regularization term for image clustering. First, we define coordinate coding.Definition 1.
Coordinate coding [41] can be written as concept pair (γ, C), where C is defined as a set of anchor points with d dimensions and γ is a map of x∈Rd to γvxv∈Cγvxv. It induces the following physical approximation of x in Rd:γx=∑v∈Cγvxv.For the local coordinate coding system, NMF can be considered as coordinate coding in which the columns of the matrixU can be viewed as a set of anchor points, and each column of the coefficient matrix V represents the corresponding coordinate coding for each data point. We might further hope that each sample point is represented as a linear combination of only a few proximate anchor points. A natural assumption here would be that if xi is far away from the anchor points uk, then its coordinate coding vki with respect to uk will tend to be zero and thus achieve sparsity and locality simultaneously. The local coordinate constraint [41] can be defined as follows:
(6)minU,V∑i=1N∑k=1Kvkiuk−xi22=minU,V∑i=1Nxi1T−UΛi1/2F2,where xi denotes the ith column of X, uk is the kth column of U, vki is the coordinate of xi with respect to uk, and Λi=diagvi∈RK×K, diagvi indicates a conversion of the vector vi into a diagonal matrix in which the kth diagonal element is vki.The local coordinate constraint employs a square loss. When the dataset is corrupted by outlier points and noises, the local coordinate constraint may fail to achieve sparsity and locality simultaneously. In order to alleviate the side effect of noisy data, our robust local coordinate constraint can be formulated as(7)minU,V∑i=1Nxi1T−UΛi1/22,1,where the Frobenius norm-based square loss function has been substituted by the l2,1 norm.


## 3.3. Local Spline Regression

In this subsection, we briefly introduce local spline regression [42].GivenN data points x1,x2,…,xN sampled from the underlying submanifold M, we use set Nxi=xijj=1k to denote xi and its k−1 nearest neighbor points, where ij∈1,2,…,N, and Yi=yi1,yi2,…,yikT is the local predicted label matrix for the ith region. The task of local spline regression is to seek the predicting function gi:RM→ℝ in order to map each data point xij∈RM to the local predicted class label yij=gixij. The model of local spline regression can be expressed as
(8)mingi∑j=1kyij−gixij2+γSgi,where Sgi is a regularization term and γ>0 is a small positive regularization parameter to control the smoothness of the spline [42]. If Sgi is defined as a seminorm of a Sobolev space, gi can be solved by the following objective function [43]:
(9)gix=∑j=1dβi,jpjx+∑j=1kαi,jGi,jx,where d=CM+s−1s, in which s is the order of the partial derivatives [43]. pjxj=1d and Gi,j are a set of primitive polynomials and a Green’s function, respectively. The coefficients αi and βi can be achieved by solving the following problem:
(10)KiPiTPi0αiβi=Yi0,where Ki is a symmetrical matrix with elements Kr,c=Gr,cxir−xic, and Pi is a matrix with its elements Pi,j=pixij. The local spline regression model can then be expressed as [42]
(11)minYiYiTMiYi,where Mi is the upper left k×k submatrix of the inverse matrix of the coefficient matrix in (10). Because the local predicted label matrix Yi is a part of the global predicted label matrix Y, we can construct a selection matrix Si∈Rk×N for each Yi such that
(12)Yi=SiY,where the selection matrix Si is defined as follows:
(13)Sir,c=1,ifr=ic,0,otherwise.After the local predicted label matrices are established, we combine them by minimizing the following loss function:(14)minYi∑i=1NYiMiYi=∑i=1NYTSiTMiSiY=YTMY,where
(15)M=∑i=1NSiTMiSi.Based on the studies of [33, 34], the predicted label matrix Y of the labeled data points should be consistent with the ground truth labels matrix F. With the consistence constraints, the objective function (14) can be written as follows:
(16)minYTrYTMY+ηTrY−FTEY−F,where E is a diagonal matrix whose diagonal elements are 1 for labeled data and 0 for unlabeled data, and the elements of F are defined as follows:
(17)fij=1,ifxiislabeledasclassj,0,otherwise.Whenη is sufficiently large, the optimal solution Y to the problem (16) makes the second term approximately equal to zero. Thus, the objective function (16) guarantees local and global structural consistency over labels. All the elements of Y are restricted to be nonnegative.


## 3.4. Objective Function of RSNLCF

By combining the RNMF (5), robust local coordinate constraint (7), and semisupervised local spline regression (16) into a unified framework, we can formulate the objective function as follows:
(18)minU,VX−UV2,1+μ∑i=1Nxi1T−UΛi1/22,1+λV2,1+τTrYTMY+ηY−FTEY−F,where τ and μ are two trade-off parameters. We call (18) our proposed RSNLCF.


## 4. Optimization

The objective function (18) involves the l2,1 norm, which is nonsmooth and cannot have a closed form solution. Consequently, we propose to solve it as follows.DenoteX−UV=a1,…,aMT,xi1T−UΛi1/2=b1,…,bKT and V=v1,…,vMT. When considering the nonnegative constraint on U, V, and Y, the objective function (18) could be reformulated as
(19)O=TrX−UVTAX−UV+μTr∑i=1Nxi1T−UΛi1/2Bxi1T−UΛi1/2T+λTrVTCV+τTrYTMY+ηY−FTEY−F,s.t.U∈RM×K>0,V∈RK×N>0,F∈RN×Lc>0,where A, B, and C are three diagonal matrices with their diagonal elements given as Aii=1/2ai2, Bii=1/2bi2, and Cii=1/2vi2, respectively.


### 4.1. Update Rules

The objective functionO of RSNLCF in (19) is not convex in U,V,andY together. Therefore, it is unrealistic to expect an algorithm to find the global minima. In this subsection, we describe our development of an iterative algorithm based on the Lagrangian multiplier method, which can achieve local minima. Following some algebraic steps, the objective function can be written as follows:
(20)O=TrXXTA+UVVTUTA−2XVTUTA+μ∑i=1Nxi1TΛi1xiTB−2xi1TΛiUTB+UΛiUTB+λTrVTCV+τTrYTMY+ηY−FTEY−F.To tackle the nonnegative constraint onU, V, and Y, the objective (20) can be rewritten as the Lagrangian multiplier.
(21)ℒ=TrXXTA+UVVTUTA−2XVTUTA+μ∑i=1Nxi1TΛi1xiTB−2xi1TΛiUTB+UΛiUTB+λTrVTCV+τTrYTMY+ηY−FTEY−F−TrΨUT−TrΦVT−TrΘYT,where Ψ=ψjk, Φ=ϕki, and Θ=θis are the Lagrangian multipliers. Let the partial derivatives of the objective function (21) with respect to U, V, and Y be zero. Thus, we have
(22)Ψ=2AUVVT−2AXVT−2μBXVT+2μBUH,Φ=2UTAUV−2UTAX+μG−2UTBX+D+2λCV,Θ=2τMY+2τηEY−F,where H is a diagonal matrix whose entries are row sums of V. G=g,…,gT is a K×N matrix whose columns are g=diagXTBX∈RN. D=d,…,d is a K×N matrix, and d=diagUTBU∈RK.Based on the Karush-Kuhn-Tucker conditions [44] ψjkujk=0,ϕkivki=0 and θisyis=0, we obtain
(23)AUVVTjkujk−AXVTjkujk−μBXVTjkujk+μBUHjkujk=0,2UTAUVkivki−2UTAXkivki+2λCVkivki+μG−2UTBX+Dkivki=0,MYisyis+ηEY−Fisyis=0.The corresponding equivalent formulas are as follows:(24)AUVVTjkujk2−AXVTjkujk2−uBXVTjkujk2+μBUHjkujk2=0,(25)2UTAUVkivki2−2UTAXkivki2+2λCVkivki2+μG−2UTBX+Dkivki2=0.(26)MYisyis2+ηEY−Fisyis2=0.Solving (24), (25), and (26), we obtain the following update rules, given by
(27)ujkt=1←ujktAXVT+μBXVTjkAUVVT+μBUVjk,(28)vkit=1←vkit2UTAX+μUTBXki2UTAUV+μG+μD+2λCVki,(29)yist+1←yistηEFisMY+ηEYis.In this manner, we obtain the solver for the objective function (19).


### 4.2. Convergence Analysis

In this subsection, we demonstrate that the objective function (20) converges to a local optimum by using the update rules (27), (28), and (29) after finite iterations. We adopt the auxiliary function approach [16] to prove the convergence. Here, we first introduce the definition of an auxiliary function.Definition 1.
Zq,q′ is an auxiliary function for Fq if the following properties are satisfied:
(30)Zq,q′≥Fq,Zq,q=Fq.Lemma 1.
IfZ is an auxiliary function for F, then F is nonincreasing under the update:
(31)ht+1=argminqZq,qt.Proof 1.
(32)Fqt+1≤Zqt+1,qt≤Zqt,qt=Fqt.Lemma 2.
For any nonnegative matricesA∈ℝn×n, B∈Rk×k, S∈Rn×k, S′∈Rn×k, and A,B are symmetric, and then the following inequality holds
(33)∑i=ln∑p=1kAS′BipSip2Sip′≥TrSTASB.The convergence of the algorithms is demonstrated in the following:For givenX, the optimizing objective function (20) w.r.t. V is equivalent to minimizing
(34)OV=TrVTUTAUV−2TrUTAXVT+µTrVTG−2µTrUTBXVT+µTrVTD+λTrVTCV.Theorem 1.
The following function(35)ZV,V′=∑kiUTAUV′kiVki2Vki′−2∑kiUTAXkiVki′1+logVkiVki+μ∑kiGkiVki2+V′ki22Vki′−2μ∑kiUTBXkiVki′1+logVkiVki′+μ∑kiDkiVki2+V′ki22Vki′+λ∑kiCV′kiVki2Vki′is an auxiliary function for OV.Proof 1.
In one sense,ZV,V=OV is obvious. However, we need to prove that ZV,V′≥OV. To accomplish this, we compare (34) and (35) to find out that ZV,V′≥OV.By applying Lemma2, we obtain
(36)TrUTAUVVT≤∑kiUTAUV′kiVki2Vki′,λTrVTCV≤λ∑kiCV′kiVki2Vki′.To obtain the upper bound for the third and fifth terms, we use the inequalitya2+b2≥2ab, which holds for any a, b≥0, and these third and fifth terms in OV are bounded by
(37)μTrVTG≤μ∑kiGkiVki2+V′ki22Vki′,μTrVTD≤μ∑kiDkiVki2+V′ki22Vki′.To obtain lower bounds for the remaining terms, we adopt the inequalityz≥1+logz, ∀z, and then
(38)2TrUTAXVT≥2∑kiUTAXkiVki′1+logVkiVki,2μTrUTBXVT≥2μ∑kiUTBXkiVki′1+logVkiVki′.Summing all inequalities, we can obtainZV,V′≥OV which obviously satisfies ZV,V′≥OV. Therefore, ZV,V′ is an auxiliary function of OV.Theorem 2.
The updating rule (28) can be obtained by minimizing the auxiliary function ZV,V′.Proof 1.
To find the minimum ofZV,V′, we set the derivative ∂ZV,V′/∂Vki=0 and obtain
(39)∂ZV,V′∂Vki=2UTAUV′kiVkiVki′−2UTAXkiVki′Vki+μGkiVkiVki′−μ2UTBXkiVki′Vki+μDkiVkiVki′+λ2CV′kiVkiVki′.Thus, by simple algebraic formulation, we can obtain the iterative updating rule forV as (28).Based on the properties of the auxiliary, we prove that the objective function (20) monotonically decreases under the updating vki.The converge proofs showing that updatingujk and yis can be accomplished using (27) and (29) are similar to the aforementioned.


## 4.1. Update Rules

The objective functionO of RSNLCF in (19) is not convex in U,V,andY together. Therefore, it is unrealistic to expect an algorithm to find the global minima. In this subsection, we describe our development of an iterative algorithm based on the Lagrangian multiplier method, which can achieve local minima. Following some algebraic steps, the objective function can be written as follows:
(20)O=TrXXTA+UVVTUTA−2XVTUTA+μ∑i=1Nxi1TΛi1xiTB−2xi1TΛiUTB+UΛiUTB+λTrVTCV+τTrYTMY+ηY−FTEY−F.To tackle the nonnegative constraint onU, V, and Y, the objective (20) can be rewritten as the Lagrangian multiplier.
(21)ℒ=TrXXTA+UVVTUTA−2XVTUTA+μ∑i=1Nxi1TΛi1xiTB−2xi1TΛiUTB+UΛiUTB+λTrVTCV+τTrYTMY+ηY−FTEY−F−TrΨUT−TrΦVT−TrΘYT,where Ψ=ψjk, Φ=ϕki, and Θ=θis are the Lagrangian multipliers. Let the partial derivatives of the objective function (21) with respect to U, V, and Y be zero. Thus, we have
(22)Ψ=2AUVVT−2AXVT−2μBXVT+2μBUH,Φ=2UTAUV−2UTAX+μG−2UTBX+D+2λCV,Θ=2τMY+2τηEY−F,where H is a diagonal matrix whose entries are row sums of V. G=g,…,gT is a K×N matrix whose columns are g=diagXTBX∈RN. D=d,…,d is a K×N matrix, and d=diagUTBU∈RK.Based on the Karush-Kuhn-Tucker conditions [44] ψjkujk=0,ϕkivki=0 and θisyis=0, we obtain
(23)AUVVTjkujk−AXVTjkujk−μBXVTjkujk+μBUHjkujk=0,2UTAUVkivki−2UTAXkivki+2λCVkivki+μG−2UTBX+Dkivki=0,MYisyis+ηEY−Fisyis=0.The corresponding equivalent formulas are as follows:(24)AUVVTjkujk2−AXVTjkujk2−uBXVTjkujk2+μBUHjkujk2=0,(25)2UTAUVkivki2−2UTAXkivki2+2λCVkivki2+μG−2UTBX+Dkivki2=0.(26)MYisyis2+ηEY−Fisyis2=0.Solving (24), (25), and (26), we obtain the following update rules, given by
(27)ujkt=1←ujktAXVT+μBXVTjkAUVVT+μBUVjk,(28)vkit=1←vkit2UTAX+μUTBXki2UTAUV+μG+μD+2λCVki,(29)yist+1←yistηEFisMY+ηEYis.In this manner, we obtain the solver for the objective function (19).


## 4.2. Convergence Analysis

In this subsection, we demonstrate that the objective function (20) converges to a local optimum by using the update rules (27), (28), and (29) after finite iterations. We adopt the auxiliary function approach [16] to prove the convergence. Here, we first introduce the definition of an auxiliary function.Definition 1.
Zq,q′ is an auxiliary function for Fq if the following properties are satisfied:
(30)Zq,q′≥Fq,Zq,q=Fq.Lemma 1.
IfZ is an auxiliary function for F, then F is nonincreasing under the update:
(31)ht+1=argminqZq,qt.Proof 1.
(32)Fqt+1≤Zqt+1,qt≤Zqt,qt=Fqt.Lemma 2.
For any nonnegative matricesA∈ℝn×n, B∈Rk×k, S∈Rn×k, S′∈Rn×k, and A,B are symmetric, and then the following inequality holds
(33)∑i=ln∑p=1kAS′BipSip2Sip′≥TrSTASB.The convergence of the algorithms is demonstrated in the following:For givenX, the optimizing objective function (20) w.r.t. V is equivalent to minimizing
(34)OV=TrVTUTAUV−2TrUTAXVT+µTrVTG−2µTrUTBXVT+µTrVTD+λTrVTCV.Theorem 1.
The following function(35)ZV,V′=∑kiUTAUV′kiVki2Vki′−2∑kiUTAXkiVki′1+logVkiVki+μ∑kiGkiVki2+V′ki22Vki′−2μ∑kiUTBXkiVki′1+logVkiVki′+μ∑kiDkiVki2+V′ki22Vki′+λ∑kiCV′kiVki2Vki′is an auxiliary function for OV.Proof 1.
In one sense,ZV,V=OV is obvious. However, we need to prove that ZV,V′≥OV. To accomplish this, we compare (34) and (35) to find out that ZV,V′≥OV.By applying Lemma2, we obtain
(36)TrUTAUVVT≤∑kiUTAUV′kiVki2Vki′,λTrVTCV≤λ∑kiCV′kiVki2Vki′.To obtain the upper bound for the third and fifth terms, we use the inequalitya2+b2≥2ab, which holds for any a, b≥0, and these third and fifth terms in OV are bounded by
(37)μTrVTG≤μ∑kiGkiVki2+V′ki22Vki′,μTrVTD≤μ∑kiDkiVki2+V′ki22Vki′.To obtain lower bounds for the remaining terms, we adopt the inequalityz≥1+logz, ∀z, and then
(38)2TrUTAXVT≥2∑kiUTAXkiVki′1+logVkiVki,2μTrUTBXVT≥2μ∑kiUTBXkiVki′1+logVkiVki′.Summing all inequalities, we can obtainZV,V′≥OV which obviously satisfies ZV,V′≥OV. Therefore, ZV,V′ is an auxiliary function of OV.Theorem 2.
The updating rule (28) can be obtained by minimizing the auxiliary function ZV,V′.Proof 1.
To find the minimum ofZV,V′, we set the derivative ∂ZV,V′/∂Vki=0 and obtain
(39)∂ZV,V′∂Vki=2UTAUV′kiVkiVki′−2UTAXkiVki′Vki+μGkiVkiVki′−μ2UTBXkiVki′Vki+μDkiVkiVki′+λ2CV′kiVkiVki′.Thus, by simple algebraic formulation, we can obtain the iterative updating rule forV as (28).Based on the properties of the auxiliary, we prove that the objective function (20) monotonically decreases under the updating vki.The converge proofs showing that updatingujk and yis can be accomplished using (27) and (29) are similar to the aforementioned.


## 5. Experiments and Discussion

We systematically evaluated the performance of our presented RSNLCF method and compared it to the popular clustering methods.


### 5.1. Datasets

Three standard face datasets and the gene dataset were selected to evaluate different methods. The four datasets are described as follows:(i)
Extended YaleB dataset: the extended YaleB dataset contains 2414 frontal face images of 38 individuals. In this dataset, the size of each face image is 192 × 168 and each image was acquired from 64 illuminate conditions and nine individual poses. Each image was resized to 32 × 32 in our experiments.
(ii)
ORL face dataset: the OR dataset contains 400 images of 40 individuals. All images were captured at different times and with different variations including lighting, face expressions (open and closed eyes, smiling, and not smiling), and specific facial details (glasses and no glasses). The original images had a size of 92 × 112. Each image was rescaled to 32 × 32.
(iii)
AR dataset: the AR dataset contains over 4000 frontal face images of 126 individuals (70 men and 56 women) with different facial expressions, illumination conditions, and occlusions (sunglasses and scarf). All individuals participated in two photo sessions, and 26 images of each individual were captured. Each image was scaled to 32 × 32.
(iv)
Leukemia dataset: the leukemia dataset contains data related to and samples of acute myelogenous leukemia (AML) and acute lymphoblastic leukemia (ALL). ALL can be further classified as T and B subtypes. This dataset consists of 5000 genes in 38 set of tumor data and contains 19 samples of B cell ALL B, eight samples of T cell ALL T, and 11 samples of AML.


### 5.2. Experimental Design

In this section, we describe our evaluation metrics, the compared methods, and our parameter selection.


#### 5.2.1. Evaluation Metrics

In our experiments, two widely used metrics (i.e., accuracy (Acc) and normalized mutual information (NMI)) were adopted to evaluate the clustering results [45]. We evaluated the algorithms by comparing the cluster labels of each data point with its label provided by the dataset. The Acc metric is defined as follows:
(40)Acc=∑i=1nδmapri,lin,where n refers to the total number of samples, ri denotes the cluster label of xi, and li is the true class label. In addition, δx,y is the delta function that is equal to 1 if x=y and 0 otherwise, and mapri is the mapping function that maps the obtained label ri to the equivalent label from the dataset. The best mapping function can be determined by using the Kuhn-Munkres algorithm [46]. The value of Acc is equal to 1 if and only if the clustering result and the true label are identical. The second measure is the NMI, which is adopted in order to evaluate the quality of clusters. Given a clustering result, the NMI is defined as follows:
(41)NMI=∑i=1c∑j=1cni,jlogni,j/nin^j∑i=1cnilogni/n∑j=1cn^jlogn^j/n,where ni denotes the number of images contained in the ith cluster Ci based on clustering results, n^j is the number of images belonging to the Cj′, and ni,j is the number of images that are in the intersection of Ci andCj′.


#### 5.2.2. Compared Methods

To verify the clustering performance of our RSNLCF, several popular methods were compared using the same dataset. The methods are listed as follows:(i)
RNMF usingl2,1 norm [27]
(ii)
Semisupervised graph-regularized NMF (semi-GNMF) [24]
(iii)
Constrained NMF (CNMF) [16]
(iv)
Local centroid-structured NMF (LCSNMF) [47]
(v)
Unsupervised robust seminonnegative graph embedding through thel2,1 norm (URNGE) [28]
(vi)
Nonnegative local coordinate factorization (NLCF) [9]
(vii)
Our proposed RSNLCFSample images are shown in Figure1.Figure 1
Sample images. (a) Extended YaleB dataset, (b) ORL dataset with random pixel corruption, (c) ORL dataset with random block occlusions, and (d) AR dataset with contiguous occlusions by sunglasses and scarves.
(a)
(b)
(c)
(d)


#### 5.2.3. Parameter Selection

Some parameters had to be tuned in the evaluated algorithms. To compare different algorithms fairly, we ran them using different parameters and chose the best average performance obtained for comparison. We set the number of clusters to be the same as the true number of categories on three image datasets and the leukemia dataset. Note that there was no parameter selection for RNMF and CNMF when the number of clusters was given. The regularization parameters were searched over the grid {0.001, 0.01, 0.1, 1, 10, 100, 1000} for semi-GNMF, URNGE, NLCF, and RSNLCF. The neighborhood sizek to build the graph was chosen from 1,2,…,10, and the 0-1 weighting scheme was adopted for its simplicity in the graph-based methods of semi-GNMF and URNGE. We applied the approach presented in literature [16] to adjust automatically the value of λ for LCSNMF.


### 5.3. Face Clustering under Illumination Variations

The robustness of the approaches to illumination changes was tested widely with the extended YaleB dataset. Figure1(a) shows some samples from this dataset. We used only the frontal face images of the first 18 individuals. Our experiments were performed with various numbers of clusters. For the fixed cluster number k, the images of k categories from the extended YaleB dataset were randomly selected and mixed for evaluation. For semisupervised methods semi-GNMG, CNMF, and URNGE, eight face images per individual were randomly chosen as labeled samples; the rest of the dataset was used as unlabeled samples. On the clustering set, the compared methods were used to achieve new data representations. For a fair comparison, we used k-means to cluster samples based on the new data representations. The results of k-means are related to initialization. We repeated the experiments 20 times with different initialization parameters. The clustering results were measured by the commonly used evaluation metrics, Acc and NMI. Table 1 shows the detailed clustering results on different clustering numbers. The final row shows the average clustering accuracy (NMI) over k. Compared with the second best method, our method (RSNLCF) achieves an 11.41% improvement in clustering accuracy. For mutual information, it achieved a 10.63% improvement over the second best algorithm.Table 1
Clustering performance on the extended YaleB dataset.
k
RNMF
Semi-GNMF
CNMF
LCSNMF
URNGE
NLCF
RSNLCF
Acc (%)
2
78.43 ± 16.23
90.47 ± 15.25
76.61 ± 15.34
92.25 ± 17.34
91.02 ± 18.83
89.54 ± 13.26
96.25 ± 15.64
4
69.52 ± 15.01
84.85 ± 14.43
65.62 ± 12.36
88.75 ± 14.76
86.33 ± 16.76
83.03 ± 12.74
94.63 ± 14.53
6
53.45 ± 5.55
82.36 ± 9.63
63.74 ± 6.75
86.14 ± 4.94
84.23 ± 5.66
77.64 ± 13.24
92.37 ± 9.85
8
52.76 ± 3.46
83.71 ± 7.81
65.42 ± 6.41
85.79 ± 6.91
85.39 ± 5.78
75.83 ± 7.33
90.18 ± 6.63
10
53.24 ± 3.47
77.05 ± 4.17
63.68 ± 5.25
78.04 ± 5.79
74.58 ± 2.43
70.42 ± 4.87
88.31 ± 4.14
12
55.11 ± 4.53
72.84 ± 3.15
63.25 ± 4.34
75.65 ± 4.36
73.34 ± 2.76
71.72 ± 7.23
87.26 ± 3.56
14
52.05 ± 3.26
71.57 ± 2.24
61.58 ± 3.86
73.91 ± 3.43
72.16 ± 2.14
68.52 ± 2.13
87.11 ± 2.34
16
51.97 ± 3.17
67.85 ± 2.45
59.91 ± 3.42
69.35 ± 3.82
68.35 ± 1.82
65.46 ± 3.14
85.67 ± 3.16
18
51.53 ± 3.32
67.58 ± 3.01
57.33 ± 2.97
71.64 ± 3.58
69.09 ± 2.23
65.83 ± 3.71
85.32 ± 3.01
Avg.
57.56
77.59
64.13
80.17
78.28
74.22
89.69
NMI (%)
2
82.91 ± 18.13
92.51 ± 18.52
78.81 ± 16.28
94.36 ± 19.84
93.35 ± 17.46
91.71 ± 17.15
98.46 ± 14.75
4
72.63 ± 17.92
87.24 ± 16.35
71.58 ± 13.41
92.71 ± 15.14
90.78 ± 15.46
85.53 ± 15.94
96.38 ± 13.52
6
63.42 ± 5.21
85.91 ± 6.47
68.37 ± 8.86
90.25 ± 9.48
86.13 ± 6.48
82.82 ± 12.03
94.35 ± 7.51
8
62.14 ± 2.96
86.86 ± 3.72
70.54 ± 7.97
89.37 ± 8.16
88.73 ± 6.52
80.34 ± 5.02
93.82 ± 5.73
10
64.06 ± 3.01
84.25 ± 3.26
69.72 ± 6.33
87.54 ± 5.42
86.82 ± 4.36
79.16 ± 2.92
92.73 ± 6.22
12
63.41 ± 3.05
80.82 ± 2.33
68.98 ± 4.64
85.28 ± 5.37
84.94 ± 4.53
80.47 ± 3.77
90.69 ± 4.91
14
58.99 ± 2.11
79.34 ± 3.44
67.67 ± 5.78
84.91 ± 4.98
83.12 ± 3.98
77.55 ± 1.76
90.43 ± 3.01
16
57.23 ± 2.17
77.85 ± 2.97
65.98 ± 4.58
82.11 ± 4.12
81.66 ± 3.54
76.46 ± 2.44
89.27 ± 4.62
18
55.59 ± 2.03
77.51 ± 2.25
64.67 ± 3.98
83.79 ± 4.43
82.36 ± 3.28
77.59 ± 1.99
89.21 ± 4.75
Avg.
64.49
86.02
69.59
87.81
86.43
81.29
97.06


### 5.4. Face Clustering under Pixel Corruptions

Two experiments were designed to test the robustness of RSNLCF against random pixel corruptions on the ORL face dataset. For the semisupervised algorithms of semi-GNMG, CNMF, URNGE, and RSNLCF, three images per individual were randomly chosen as labeled samples, and the remaining images were used as unlabeled samples. In the first experiment, each image was corrupted by replacing the pixel value with independent and identically distributed samples whose lower and upper bounds were the minimum and maximum pixel value of the image, respectively. The corrupted pixels of each image varied from 10 to 90% in increments of 10%. Figure1(b) shows several examples. Because the corrupted pixels were randomly selected for each test sample, we repeated the experiments 20 times. Figure 2 displays the recognition accuracies over different levels of corruption. The recognition accuracies of the methods decreased rapidly as the level of corruption increased. From Figure 2, which depicts the recognition accuracies, we can observe that the proposed method consistently outperformed the others. When the samples had a high percentage of pixel corruption, the methods failed to obtain improved recognition performance because of inadequate discriminative information.Figure 2
Clustering Acc and NMI curves across percentages of corrupted pixels of each image for the compared methods on the ORL dataset.
(a)
Acc results
(b)
NMI resultsIn the second experiment, 40% of the pixels randomly selected from each sample were replaced by setting the pixel value as 255. The number of corrupted samples of each individual is gradually increased from 10 to 90%. We conducted the evaluations 20 times at different corruption percentages and computed the average recognition accuracies of Acc and NMI. Figure3 illustrates clustering Acc and NMI curves of RSNLCF and the proposed method’s six competitors versus the percentage of corrupted images. From Figure 3, which depicts the comparison results on the ORL dataset, we can clearly see that the RSNLCF obtained the best recognition accuracy in all situations.Figure 3
Clustering Acc and NMI curves across percentages of corrupted images for the compared methods on the ORL dataset.
(a)
Acc results
(b)
NMI results


### 5.5. Face Clustering under Contiguous Occlusions

We validated the robustness of RSNLCF against partial block occlusions (see Figure1(c) for examples). Two experiments were conducted on the ORL face dataset. For the semisupervised algorithms of semi-GNMG, CNMF, URNGE, and RSNLCF, we randomly selected three samples from each category and used their category number as the label information. The first experiment was performed with a fixed contiguous block occlusion size of 40 × 40 pixels. We chose r of the face samples of each individual for occlusion, with r varying from 10 to 90%. The position of the block was randomly selected. The evaluations were performed 20 times for each r, and the means of Acc and NMI were recorded. Figure 4 shows the means of clustering Acc and NMI of the compared methods on different percentages of corrupted images. As shown in Figure 4, the performances of NMF, RNMF, semi-GNMF, CNMF, URNGE, and NLCF were lower than that of RSNLCF. With an increasing number of occluded samples, the clustering accuracy of RSNLCF dropped and thus matched expectations considerably.Figure 4
Clustering Acc and NMI curves of the compared methods on percentages of corrupted images with random block occlusions for the ORL dataset.
(a)
Acc results
(b)
NMI resultsIn the second experiment, we simulated various levels of contiguous occlusions in each image by using an unrelated image of sizep×p with p∈5,10,20,…,80. The evaluations were conducted 20 times at each occlusion level, and the average Acc and NMI curves were recorded. Figure 5 plots clustering Acc and NMI results of the compared methods under different occlusion levels. Although the clustering accuracy of each method degraded with each increment in occlusion level, RSNLCF consistently exceeded other methods. When the occlusion size increased to 50 × 50, the occluding part dominated the image and caused the clustering performance to diminish rapidly.Figure 5
Clustering Acc and NMI curves of the compared methods under different occlusion levels with each image in the ORL dataset.
(a)
Acc results
(b)
NMI results


### 5.6. Face Clustering under Real Occlusions

We evaluated the robustness of RSNLCF against real malicious occlusions. The AR dataset adopted in this experiment contains 2600 frontal face images from 100 individuals (50 males and 50 females from two photo sessions). Figure1(d) shows some face samples with real occlusions by sunglasses and scarf. Note that because RNMF, LCSNMF, and NLCF are unsupervised algorithms, we did not compare them here. In this experiment, we randomly selected r face images per individual as labeled samples, in which r was varied from four to 18, respectively, in increments of two. The remaining images were unlabeled samples. For each configuration, we conducted 20 test runs with each method. The mean and the standard deviation of clustering accuracy were recorded. Table 2 tabulates the detailed clustering results by Acc and NMI on the AR dataset and shows our algorithm achieved 8.55, 12.82, and 14.53% Acc improvement over URNGE, CNMF, and semi-GNMF, respectively.Table 2
Clustering performances on the AR dataset.
r
Acc (%)
NMI (%)
Semi-GNMG
CNMF
URNGE
RSNLCF
Semi-GNMG
CNMF
URNGE
RSNLCF
4
58.29 ± 3.74
55.93 ± 3.72
63.28 ± 3.94
82.29 ± 2.54
68.65 ± 5.34
67.79 ± 3.51
72.37 ± 4.29
86.27 ± 2.28
6
64.53 ± 3.62
60.56 ± 4.54
69.06 ± 4.31
86.07 ± 4.19
72.49 ± 3.38
68.28 ± 4.43
76.85 ± 4.32
89.46 ± 4.93
8
67.37 ± 3.22
69.17 ± 3.93
74.19 ± 3.71
87.25 ± 2.68
78.13 ± 3.67
80.33 ± 3.25
81.24 ± 2.36
91.57 ± 2.28
10
74.87 ± 4.13
76.57 ± 2.76
79.73 ± 2.38
88.48 ± 3.85
83.48 ± 3.36
84.52 ± 2.37
87.63 ± 3.48
92.84 ± 3.58
12
79.38 ± 3.03
82.32 ± 2.83
88.01 ± 3.52
92.64 ± 2.23
85.21 ± 2.02
88.32 ± 3.76
90.27 ± 3.52
94.12 ± 2.93
14
85.95 ± 3.31
90.58 ± 2.53
91.49 ± 2.36
93.54 ± 2.17
88.27 ± 2.37
92.46 ± 2.43
92.34 ± 2.86
96.43 ± 3.54
16
86.39 ± 3.71
91.35 ± 4.54
92.92 ± 2.42
94.83 ± 2.79
89.38 ± 2.58
93.25 ± 3.38
93.94 ± 2.48
97.07 ± 2.72
18
88.83 ± 3.27
92.82 ± 4.55
94.73 ± 2.67
96.71 ± 2.35
91.03 ± 2.64
94.38 ± 3.46
95.52 ± 2.69
98.91 ± 2.76
Avg.
75.70
77.41
81.68
90.23
82.46
83.67
86.27
93.33For NMI, the recognition rate of RSNLCF was 7.06, 9.66, and 10.87% higher than URNGE, CNMF, and semi-GNMF, respectively.


### 5.7. Gene Data Clustering on the Leukemia Dataset

Finally, we assessed clustering performance on the leukemia dataset. The gene expression dataset was rather challenging in terms of clustering issues, because it contains numerous features but only a few samples. We filtered out genes with max/min < 15 and max − min < 500, leaving a total of 1999 genes. Note that because RNMF, LCSNMF, and NLCF are unsupervised algorithms, we did not compare them here. For each category of data, c=2,3,4,5,6,7,8 samples were randomly chosen and labeled, with the remaining samples being unlabeled. As the samples were randomly selected, for each c, we repeated each experiment 20 times and calculated the average clustering accuracy. Figure 6 plots clustering Acc and NMI results of the compared methods under different numbers of labeled samples. We can observe that our RSNLCF approach achieved the best clustering performance of all the compared approaches.Figure 6
Clustering Acc and NMI curves of the compared methods under different numbers of labeled samples for the leukemia dataset.
(a)
Acc results
(b)
NMI results


### 5.8. Parameter Sensitivity

In our proposed method, several parameters were tuned beforehand. We observed that RSNLCF is insensitive toτ in the range of [10−3,103]. Accordingly, we fixed η to be 106 and τ to be 10 for both the extended YaleB and leukemia datasets. To study the sensitivity of RSNLCF with respect to the remaining parameters (i.e., μ and λ), we varied these parameters. In the experiment, we plotted the Acc and NMI of RSNLCF with respect to μ and λ. Figures 7 and 8 show clearly the 3D results of RSNLCF. The horizontal axes are the parameters μ and λ, and the vertical axis represents the clustering accuracy of RSNLCF. In the 3D graphs, the square/circle marker indicates the best μ/λ for varying μ/λ. Next to each marker at the cross point is a digit number representing the value of Acc or NMI. We can notice from Figures 7 and 8 that the clustering performance varied with different combinations of μ and λ. However, it is unknown theoretically how to choose the best parameter. The regularization parameters should be associated with the characteristics of the dataset.Figure 7
Clustering accuracy of the proposed method with respect to the parametersμ and λ on the extended YaleB dataset.
(a)
Acc results
(b)
NMI resultsFigure 8
Clustering accuracy of the proposed method with respect to the parametersμ and λ on the leukemia dataset.
(a)
Acc results
(b)
NMI results


### 5.9. Convergence Analysis

In the previous section, we proved the convergence of our presented method. In our study, an experiment was performed to compare all algorithms’ speed of convergence on the extended YaleB and leukemia datasets. The two parametersμ and λ were both fixed at 10. The time is measured using a computer with Intel Core™ I7 2600 and 16 GB memory. Figure 9 demonstrated the objective function value versus computational time for different algorithms. The horizontal and vertical axes here represent training times and the value of the objective function, respectively. We can observe from Figure 9 that the objective function value of all algorithms decreases steadily with the time increase, and RSNLCF requires less time than other graph-based methods, demonstrating that the proposed method was effective and efficient.Figure 9
The curve of objective function value versus computational time on the extended YaleB and leukemia datasets. (a) RNMF, (b) semi-GNMF, (c) CNMF, (d) LCSNMF, (e) URNGE, (f) NLCF, and (g) RSNLCF.
(a)
(b)
(c)
(d)
(e)
(f)
(g)


### 5.10. Overall Observations and Discussion

In our experiments, we considered several groups of experiments based on different databases, where the extended YaleB mainly involved illumination changes, the ORL database focused on pixel corruptions and block occlusions, the AR database included face images with different facial variations, sunglasses, and scarf occlusions, and the leukemia dataset contained a large number of features but only a few samples. From the aforementioned experimental results, we gained the following several attractive insights:(i)
In most cases, the performance of CNMF was usually lower than that of the graph-based approach, which demonstrates the superiority of intrinsic geometrical structure representation in discovering potential discriminative information.
(ii)
Regardless of the datasets, our RSNLCF algorithm outperformed all six other methods. The reason lies in the fact that RSNLCF is designed for simultaneous application to local and global consistencies over labels simultaneously to uncover an underlying subspace structure. In addition, RSNLCF proved robust to outlier points and noises as a result of employing thel2,1 norm formulations of NMF and the local coordinate constraint regularization term.
(iii)
Future research on this topic will include how to use multicore processors [48, 49] to accelerate our proposed method and how to extend the idea of semisupervised learning to the existing clustering algorithms.


## 5.1. Datasets

Three standard face datasets and the gene dataset were selected to evaluate different methods. The four datasets are described as follows:(i)
Extended YaleB dataset: the extended YaleB dataset contains 2414 frontal face images of 38 individuals. In this dataset, the size of each face image is 192 × 168 and each image was acquired from 64 illuminate conditions and nine individual poses. Each image was resized to 32 × 32 in our experiments.
(ii)
ORL face dataset: the OR dataset contains 400 images of 40 individuals. All images were captured at different times and with different variations including lighting, face expressions (open and closed eyes, smiling, and not smiling), and specific facial details (glasses and no glasses). The original images had a size of 92 × 112. Each image was rescaled to 32 × 32.
(iii)
AR dataset: the AR dataset contains over 4000 frontal face images of 126 individuals (70 men and 56 women) with different facial expressions, illumination conditions, and occlusions (sunglasses and scarf). All individuals participated in two photo sessions, and 26 images of each individual were captured. Each image was scaled to 32 × 32.
(iv)
Leukemia dataset: the leukemia dataset contains data related to and samples of acute myelogenous leukemia (AML) and acute lymphoblastic leukemia (ALL). ALL can be further classified as T and B subtypes. This dataset consists of 5000 genes in 38 set of tumor data and contains 19 samples of B cell ALL B, eight samples of T cell ALL T, and 11 samples of AML.


## 5.2. Experimental Design

In this section, we describe our evaluation metrics, the compared methods, and our parameter selection.


### 5.2.1. Evaluation Metrics

In our experiments, two widely used metrics (i.e., accuracy (Acc) and normalized mutual information (NMI)) were adopted to evaluate the clustering results [45]. We evaluated the algorithms by comparing the cluster labels of each data point with its label provided by the dataset. The Acc metric is defined as follows:
(40)Acc=∑i=1nδmapri,lin,where n refers to the total number of samples, ri denotes the cluster label of xi, and li is the true class label. In addition, δx,y is the delta function that is equal to 1 if x=y and 0 otherwise, and mapri is the mapping function that maps the obtained label ri to the equivalent label from the dataset. The best mapping function can be determined by using the Kuhn-Munkres algorithm [46]. The value of Acc is equal to 1 if and only if the clustering result and the true label are identical. The second measure is the NMI, which is adopted in order to evaluate the quality of clusters. Given a clustering result, the NMI is defined as follows:
(41)NMI=∑i=1c∑j=1cni,jlogni,j/nin^j∑i=1cnilogni/n∑j=1cn^jlogn^j/n,where ni denotes the number of images contained in the ith cluster Ci based on clustering results, n^j is the number of images belonging to the Cj′, and ni,j is the number of images that are in the intersection of Ci andCj′.


### 5.2.2. Compared Methods

To verify the clustering performance of our RSNLCF, several popular methods were compared using the same dataset. The methods are listed as follows:(i)
RNMF usingl2,1 norm [27]
(ii)
Semisupervised graph-regularized NMF (semi-GNMF) [24]
(iii)
Constrained NMF (CNMF) [16]
(iv)
Local centroid-structured NMF (LCSNMF) [47]
(v)
Unsupervised robust seminonnegative graph embedding through thel2,1 norm (URNGE) [28]
(vi)
Nonnegative local coordinate factorization (NLCF) [9]
(vii)
Our proposed RSNLCFSample images are shown in Figure1.Figure 1
Sample images. (a) Extended YaleB dataset, (b) ORL dataset with random pixel corruption, (c) ORL dataset with random block occlusions, and (d) AR dataset with contiguous occlusions by sunglasses and scarves.
(a)
(b)
(c)
(d)


### 5.2.3. Parameter Selection

Some parameters had to be tuned in the evaluated algorithms. To compare different algorithms fairly, we ran them using different parameters and chose the best average performance obtained for comparison. We set the number of clusters to be the same as the true number of categories on three image datasets and the leukemia dataset. Note that there was no parameter selection for RNMF and CNMF when the number of clusters was given. The regularization parameters were searched over the grid {0.001, 0.01, 0.1, 1, 10, 100, 1000} for semi-GNMF, URNGE, NLCF, and RSNLCF. The neighborhood sizek to build the graph was chosen from 1,2,…,10, and the 0-1 weighting scheme was adopted for its simplicity in the graph-based methods of semi-GNMF and URNGE. We applied the approach presented in literature [16] to adjust automatically the value of λ for LCSNMF.


## 5.2.1. Evaluation Metrics

In our experiments, two widely used metrics (i.e., accuracy (Acc) and normalized mutual information (NMI)) were adopted to evaluate the clustering results [45]. We evaluated the algorithms by comparing the cluster labels of each data point with its label provided by the dataset. The Acc metric is defined as follows:
(40)Acc=∑i=1nδmapri,lin,where n refers to the total number of samples, ri denotes the cluster label of xi, and li is the true class label. In addition, δx,y is the delta function that is equal to 1 if x=y and 0 otherwise, and mapri is the mapping function that maps the obtained label ri to the equivalent label from the dataset. The best mapping function can be determined by using the Kuhn-Munkres algorithm [46]. The value of Acc is equal to 1 if and only if the clustering result and the true label are identical. The second measure is the NMI, which is adopted in order to evaluate the quality of clusters. Given a clustering result, the NMI is defined as follows:
(41)NMI=∑i=1c∑j=1cni,jlogni,j/nin^j∑i=1cnilogni/n∑j=1cn^jlogn^j/n,where ni denotes the number of images contained in the ith cluster Ci based on clustering results, n^j is the number of images belonging to the Cj′, and ni,j is the number of images that are in the intersection of Ci andCj′.


## 5.2.2. Compared Methods

To verify the clustering performance of our RSNLCF, several popular methods were compared using the same dataset. The methods are listed as follows:(i)
RNMF usingl2,1 norm [27]
(ii)
Semisupervised graph-regularized NMF (semi-GNMF) [24]
(iii)
Constrained NMF (CNMF) [16]
(iv)
Local centroid-structured NMF (LCSNMF) [47]
(v)
Unsupervised robust seminonnegative graph embedding through thel2,1 norm (URNGE) [28]
(vi)
Nonnegative local coordinate factorization (NLCF) [9]
(vii)
Our proposed RSNLCFSample images are shown in Figure1.Figure 1
Sample images. (a) Extended YaleB dataset, (b) ORL dataset with random pixel corruption, (c) ORL dataset with random block occlusions, and (d) AR dataset with contiguous occlusions by sunglasses and scarves.
(a)
(b)
(c)
(d)


## 5.2.3. Parameter Selection

Some parameters had to be tuned in the evaluated algorithms. To compare different algorithms fairly, we ran them using different parameters and chose the best average performance obtained for comparison. We set the number of clusters to be the same as the true number of categories on three image datasets and the leukemia dataset. Note that there was no parameter selection for RNMF and CNMF when the number of clusters was given. The regularization parameters were searched over the grid {0.001, 0.01, 0.1, 1, 10, 100, 1000} for semi-GNMF, URNGE, NLCF, and RSNLCF. The neighborhood sizek to build the graph was chosen from 1,2,…,10, and the 0-1 weighting scheme was adopted for its simplicity in the graph-based methods of semi-GNMF and URNGE. We applied the approach presented in literature [16] to adjust automatically the value of λ for LCSNMF.


## 5.3. Face Clustering under Illumination Variations

The robustness of the approaches to illumination changes was tested widely with the extended YaleB dataset. Figure1(a) shows some samples from this dataset. We used only the frontal face images of the first 18 individuals. Our experiments were performed with various numbers of clusters. For the fixed cluster number k, the images of k categories from the extended YaleB dataset were randomly selected and mixed for evaluation. For semisupervised methods semi-GNMG, CNMF, and URNGE, eight face images per individual were randomly chosen as labeled samples; the rest of the dataset was used as unlabeled samples. On the clustering set, the compared methods were used to achieve new data representations. For a fair comparison, we used k-means to cluster samples based on the new data representations. The results of k-means are related to initialization. We repeated the experiments 20 times with different initialization parameters. The clustering results were measured by the commonly used evaluation metrics, Acc and NMI. Table 1 shows the detailed clustering results on different clustering numbers. The final row shows the average clustering accuracy (NMI) over k. Compared with the second best method, our method (RSNLCF) achieves an 11.41% improvement in clustering accuracy. For mutual information, it achieved a 10.63% improvement over the second best algorithm.Table 1
Clustering performance on the extended YaleB dataset.
k
RNMF
Semi-GNMF
CNMF
LCSNMF
URNGE
NLCF
RSNLCF
Acc (%)
2
78.43 ± 16.23
90.47 ± 15.25
76.61 ± 15.34
92.25 ± 17.34
91.02 ± 18.83
89.54 ± 13.26
96.25 ± 15.64
4
69.52 ± 15.01
84.85 ± 14.43
65.62 ± 12.36
88.75 ± 14.76
86.33 ± 16.76
83.03 ± 12.74
94.63 ± 14.53
6
53.45 ± 5.55
82.36 ± 9.63
63.74 ± 6.75
86.14 ± 4.94
84.23 ± 5.66
77.64 ± 13.24
92.37 ± 9.85
8
52.76 ± 3.46
83.71 ± 7.81
65.42 ± 6.41
85.79 ± 6.91
85.39 ± 5.78
75.83 ± 7.33
90.18 ± 6.63
10
53.24 ± 3.47
77.05 ± 4.17
63.68 ± 5.25
78.04 ± 5.79
74.58 ± 2.43
70.42 ± 4.87
88.31 ± 4.14
12
55.11 ± 4.53
72.84 ± 3.15
63.25 ± 4.34
75.65 ± 4.36
73.34 ± 2.76
71.72 ± 7.23
87.26 ± 3.56
14
52.05 ± 3.26
71.57 ± 2.24
61.58 ± 3.86
73.91 ± 3.43
72.16 ± 2.14
68.52 ± 2.13
87.11 ± 2.34
16
51.97 ± 3.17
67.85 ± 2.45
59.91 ± 3.42
69.35 ± 3.82
68.35 ± 1.82
65.46 ± 3.14
85.67 ± 3.16
18
51.53 ± 3.32
67.58 ± 3.01
57.33 ± 2.97
71.64 ± 3.58
69.09 ± 2.23
65.83 ± 3.71
85.32 ± 3.01
Avg.
57.56
77.59
64.13
80.17
78.28
74.22
89.69
NMI (%)
2
82.91 ± 18.13
92.51 ± 18.52
78.81 ± 16.28
94.36 ± 19.84
93.35 ± 17.46
91.71 ± 17.15
98.46 ± 14.75
4
72.63 ± 17.92
87.24 ± 16.35
71.58 ± 13.41
92.71 ± 15.14
90.78 ± 15.46
85.53 ± 15.94
96.38 ± 13.52
6
63.42 ± 5.21
85.91 ± 6.47
68.37 ± 8.86
90.25 ± 9.48
86.13 ± 6.48
82.82 ± 12.03
94.35 ± 7.51
8
62.14 ± 2.96
86.86 ± 3.72
70.54 ± 7.97
89.37 ± 8.16
88.73 ± 6.52
80.34 ± 5.02
93.82 ± 5.73
10
64.06 ± 3.01
84.25 ± 3.26
69.72 ± 6.33
87.54 ± 5.42
86.82 ± 4.36
79.16 ± 2.92
92.73 ± 6.22
12
63.41 ± 3.05
80.82 ± 2.33
68.98 ± 4.64
85.28 ± 5.37
84.94 ± 4.53
80.47 ± 3.77
90.69 ± 4.91
14
58.99 ± 2.11
79.34 ± 3.44
67.67 ± 5.78
84.91 ± 4.98
83.12 ± 3.98
77.55 ± 1.76
90.43 ± 3.01
16
57.23 ± 2.17
77.85 ± 2.97
65.98 ± 4.58
82.11 ± 4.12
81.66 ± 3.54
76.46 ± 2.44
89.27 ± 4.62
18
55.59 ± 2.03
77.51 ± 2.25
64.67 ± 3.98
83.79 ± 4.43
82.36 ± 3.28
77.59 ± 1.99
89.21 ± 4.75
Avg.
64.49
86.02
69.59
87.81
86.43
81.29
97.06


## 5.4. Face Clustering under Pixel Corruptions

Two experiments were designed to test the robustness of RSNLCF against random pixel corruptions on the ORL face dataset. For the semisupervised algorithms of semi-GNMG, CNMF, URNGE, and RSNLCF, three images per individual were randomly chosen as labeled samples, and the remaining images were used as unlabeled samples. In the first experiment, each image was corrupted by replacing the pixel value with independent and identically distributed samples whose lower and upper bounds were the minimum and maximum pixel value of the image, respectively. The corrupted pixels of each image varied from 10 to 90% in increments of 10%. Figure1(b) shows several examples. Because the corrupted pixels were randomly selected for each test sample, we repeated the experiments 20 times. Figure 2 displays the recognition accuracies over different levels of corruption. The recognition accuracies of the methods decreased rapidly as the level of corruption increased. From Figure 2, which depicts the recognition accuracies, we can observe that the proposed method consistently outperformed the others. When the samples had a high percentage of pixel corruption, the methods failed to obtain improved recognition performance because of inadequate discriminative information.Figure 2
Clustering Acc and NMI curves across percentages of corrupted pixels of each image for the compared methods on the ORL dataset.
(a)
Acc results
(b)
NMI resultsIn the second experiment, 40% of the pixels randomly selected from each sample were replaced by setting the pixel value as 255. The number of corrupted samples of each individual is gradually increased from 10 to 90%. We conducted the evaluations 20 times at different corruption percentages and computed the average recognition accuracies of Acc and NMI. Figure3 illustrates clustering Acc and NMI curves of RSNLCF and the proposed method’s six competitors versus the percentage of corrupted images. From Figure 3, which depicts the comparison results on the ORL dataset, we can clearly see that the RSNLCF obtained the best recognition accuracy in all situations.Figure 3
Clustering Acc and NMI curves across percentages of corrupted images for the compared methods on the ORL dataset.
(a)
Acc results
(b)
NMI results


## 5.5. Face Clustering under Contiguous Occlusions

We validated the robustness of RSNLCF against partial block occlusions (see Figure1(c) for examples). Two experiments were conducted on the ORL face dataset. For the semisupervised algorithms of semi-GNMG, CNMF, URNGE, and RSNLCF, we randomly selected three samples from each category and used their category number as the label information. The first experiment was performed with a fixed contiguous block occlusion size of 40 × 40 pixels. We chose r of the face samples of each individual for occlusion, with r varying from 10 to 90%. The position of the block was randomly selected. The evaluations were performed 20 times for each r, and the means of Acc and NMI were recorded. Figure 4 shows the means of clustering Acc and NMI of the compared methods on different percentages of corrupted images. As shown in Figure 4, the performances of NMF, RNMF, semi-GNMF, CNMF, URNGE, and NLCF were lower than that of RSNLCF. With an increasing number of occluded samples, the clustering accuracy of RSNLCF dropped and thus matched expectations considerably.Figure 4
Clustering Acc and NMI curves of the compared methods on percentages of corrupted images with random block occlusions for the ORL dataset.
(a)
Acc results
(b)
NMI resultsIn the second experiment, we simulated various levels of contiguous occlusions in each image by using an unrelated image of sizep×p with p∈5,10,20,…,80. The evaluations were conducted 20 times at each occlusion level, and the average Acc and NMI curves were recorded. Figure 5 plots clustering Acc and NMI results of the compared methods under different occlusion levels. Although the clustering accuracy of each method degraded with each increment in occlusion level, RSNLCF consistently exceeded other methods. When the occlusion size increased to 50 × 50, the occluding part dominated the image and caused the clustering performance to diminish rapidly.Figure 5
Clustering Acc and NMI curves of the compared methods under different occlusion levels with each image in the ORL dataset.
(a)
Acc results
(b)
NMI results


## 5.6. Face Clustering under Real Occlusions

We evaluated the robustness of RSNLCF against real malicious occlusions. The AR dataset adopted in this experiment contains 2600 frontal face images from 100 individuals (50 males and 50 females from two photo sessions). Figure1(d) shows some face samples with real occlusions by sunglasses and scarf. Note that because RNMF, LCSNMF, and NLCF are unsupervised algorithms, we did not compare them here. In this experiment, we randomly selected r face images per individual as labeled samples, in which r was varied from four to 18, respectively, in increments of two. The remaining images were unlabeled samples. For each configuration, we conducted 20 test runs with each method. The mean and the standard deviation of clustering accuracy were recorded. Table 2 tabulates the detailed clustering results by Acc and NMI on the AR dataset and shows our algorithm achieved 8.55, 12.82, and 14.53% Acc improvement over URNGE, CNMF, and semi-GNMF, respectively.Table 2
Clustering performances on the AR dataset.
r
Acc (%)
NMI (%)
Semi-GNMG
CNMF
URNGE
RSNLCF
Semi-GNMG
CNMF
URNGE
RSNLCF
4
58.29 ± 3.74
55.93 ± 3.72
63.28 ± 3.94
82.29 ± 2.54
68.65 ± 5.34
67.79 ± 3.51
72.37 ± 4.29
86.27 ± 2.28
6
64.53 ± 3.62
60.56 ± 4.54
69.06 ± 4.31
86.07 ± 4.19
72.49 ± 3.38
68.28 ± 4.43
76.85 ± 4.32
89.46 ± 4.93
8
67.37 ± 3.22
69.17 ± 3.93
74.19 ± 3.71
87.25 ± 2.68
78.13 ± 3.67
80.33 ± 3.25
81.24 ± 2.36
91.57 ± 2.28
10
74.87 ± 4.13
76.57 ± 2.76
79.73 ± 2.38
88.48 ± 3.85
83.48 ± 3.36
84.52 ± 2.37
87.63 ± 3.48
92.84 ± 3.58
12
79.38 ± 3.03
82.32 ± 2.83
88.01 ± 3.52
92.64 ± 2.23
85.21 ± 2.02
88.32 ± 3.76
90.27 ± 3.52
94.12 ± 2.93
14
85.95 ± 3.31
90.58 ± 2.53
91.49 ± 2.36
93.54 ± 2.17
88.27 ± 2.37
92.46 ± 2.43
92.34 ± 2.86
96.43 ± 3.54
16
86.39 ± 3.71
91.35 ± 4.54
92.92 ± 2.42
94.83 ± 2.79
89.38 ± 2.58
93.25 ± 3.38
93.94 ± 2.48
97.07 ± 2.72
18
88.83 ± 3.27
92.82 ± 4.55
94.73 ± 2.67
96.71 ± 2.35
91.03 ± 2.64
94.38 ± 3.46
95.52 ± 2.69
98.91 ± 2.76
Avg.
75.70
77.41
81.68
90.23
82.46
83.67
86.27
93.33For NMI, the recognition rate of RSNLCF was 7.06, 9.66, and 10.87% higher than URNGE, CNMF, and semi-GNMF, respectively.


## 5.7. Gene Data Clustering on the Leukemia Dataset

Finally, we assessed clustering performance on the leukemia dataset. The gene expression dataset was rather challenging in terms of clustering issues, because it contains numerous features but only a few samples. We filtered out genes with max/min < 15 and max − min < 500, leaving a total of 1999 genes. Note that because RNMF, LCSNMF, and NLCF are unsupervised algorithms, we did not compare them here. For each category of data, c=2,3,4,5,6,7,8 samples were randomly chosen and labeled, with the remaining samples being unlabeled. As the samples were randomly selected, for each c, we repeated each experiment 20 times and calculated the average clustering accuracy. Figure 6 plots clustering Acc and NMI results of the compared methods under different numbers of labeled samples. We can observe that our RSNLCF approach achieved the best clustering performance of all the compared approaches.Figure 6
Clustering Acc and NMI curves of the compared methods under different numbers of labeled samples for the leukemia dataset.
(a)
Acc results
(b)
NMI results


## 5.8. Parameter Sensitivity

In our proposed method, several parameters were tuned beforehand. We observed that RSNLCF is insensitive toτ in the range of [10−3,103]. Accordingly, we fixed η to be 106 and τ to be 10 for both the extended YaleB and leukemia datasets. To study the sensitivity of RSNLCF with respect to the remaining parameters (i.e., μ and λ), we varied these parameters. In the experiment, we plotted the Acc and NMI of RSNLCF with respect to μ and λ. Figures 7 and 8 show clearly the 3D results of RSNLCF. The horizontal axes are the parameters μ and λ, and the vertical axis represents the clustering accuracy of RSNLCF. In the 3D graphs, the square/circle marker indicates the best μ/λ for varying μ/λ. Next to each marker at the cross point is a digit number representing the value of Acc or NMI. We can notice from Figures 7 and 8 that the clustering performance varied with different combinations of μ and λ. However, it is unknown theoretically how to choose the best parameter. The regularization parameters should be associated with the characteristics of the dataset.Figure 7
Clustering accuracy of the proposed method with respect to the parametersμ and λ on the extended YaleB dataset.
(a)
Acc results
(b)
NMI resultsFigure 8
Clustering accuracy of the proposed method with respect to the parametersμ and λ on the leukemia dataset.
(a)
Acc results
(b)
NMI results


## 5.9. Convergence Analysis

In the previous section, we proved the convergence of our presented method. In our study, an experiment was performed to compare all algorithms’ speed of convergence on the extended YaleB and leukemia datasets. The two parametersμ and λ were both fixed at 10. The time is measured using a computer with Intel Core™ I7 2600 and 16 GB memory. Figure 9 demonstrated the objective function value versus computational time for different algorithms. The horizontal and vertical axes here represent training times and the value of the objective function, respectively. We can observe from Figure 9 that the objective function value of all algorithms decreases steadily with the time increase, and RSNLCF requires less time than other graph-based methods, demonstrating that the proposed method was effective and efficient.Figure 9
The curve of objective function value versus computational time on the extended YaleB and leukemia datasets. (a) RNMF, (b) semi-GNMF, (c) CNMF, (d) LCSNMF, (e) URNGE, (f) NLCF, and (g) RSNLCF.
(a)
(b)
(c)
(d)
(e)
(f)
(g)


## 5.10. Overall Observations and Discussion

In our experiments, we considered several groups of experiments based on different databases, where the extended YaleB mainly involved illumination changes, the ORL database focused on pixel corruptions and block occlusions, the AR database included face images with different facial variations, sunglasses, and scarf occlusions, and the leukemia dataset contained a large number of features but only a few samples. From the aforementioned experimental results, we gained the following several attractive insights:(i)
In most cases, the performance of CNMF was usually lower than that of the graph-based approach, which demonstrates the superiority of intrinsic geometrical structure representation in discovering potential discriminative information.
(ii)
Regardless of the datasets, our RSNLCF algorithm outperformed all six other methods. The reason lies in the fact that RSNLCF is designed for simultaneous application to local and global consistencies over labels simultaneously to uncover an underlying subspace structure. In addition, RSNLCF proved robust to outlier points and noises as a result of employing thel2,1 norm formulations of NMF and the local coordinate constraint regularization term.
(iii)
Future research on this topic will include how to use multicore processors [48, 49] to accelerate our proposed method and how to extend the idea of semisupervised learning to the existing clustering algorithms.


## 6. Conclusion

In this study, we proposed a novel matrix decomposition method (RSNLCF) to learn an efficient representation for data in a semisupervised learning scenario. An efficient iterative algorithm for RSNLCF was also presented. The convergence of the presented method was theoretically proved. Extensive experiments over diverse datasets demonstrated that the presented method is quite effective and robust at learning an efficient data representation for clustering tasks. More importantly, experimental results revealed that our optimization algorithm quickly converges, indicating that our method can be utilized to solve practical problems.



---

*Source: 7963210-2018-08-01.xml*