# Relationship Matrix Nonnegative Decomposition for Clustering

Authors: Ji-Yuan Pan; Jiang-She Zhang
Journal: Mathematical Problems in Engineering
 (2011)

---

## Abstract

Nonnegative matrix factorization (NMF) is a popular tool for analyzing
the latent structure of nonnegative data. For a positive pairwise similarity
matrix, symmetric NMF (SNMF) and weighted NMF (WNMF) can be
used to cluster the data. However, both of them are not very efficient for
the ill-structured pairwise similarity matrix. In this paper, a novel model,
called relationship matrix nonnegative decomposition (RMND), is proposed
to discover the latent clustering structure from the pairwise similarity matrix.
The RMND model is derived from the nonlinear NMF algorithm. RMND
decomposes a pairwise similarity matrix into a product of three low rank
nonnegative matrices. The pairwise similarity matrix is represented as a
transformation of a positive semidefinite matrix which pops out the latent
clustering structure. We develop a learning procedure based on multiplicative
update rules and steepest descent method to calculate the nonnegative
solution of RMND. Experimental results in four different databases show
that the proposed RMND approach achieves higher clustering accuracy.


---

## Body

## 1. Introduction

Nonnegative matrix factorization (NMF) [1] has been introduced as an effective technique for analyzing the latent structure of nonnegative data such as images and documents. A variety of real-world applications of NMF has been found in many areas such as machine learning, signal processing [2–4], data clustering [5, 6], and computer vision [7].Most applications focus on the clustering aspect of NMF [8, 9]. Each sample can be represented as a linear combination of clustering centroids. Recently, a theoretic analysis has shown the equivalence between NMF and K-means/spectral clustering [10]. Symmetric NMF (SNMF) [10] is an extension of NMF. It aims at learning clustering structure from the kernel matrix or pairwise similarity matrix which is positive semidefinite. When the similarity matrix is not positive semidefinite, SNMF is not able to capture the clustering structure contained in the subspace associated with negative eigenvalues. In order to overcome the limitation, weighted NMF (SNMF) [10] is developed. In the WNMF model, the indefiniteness of the pairwise similarity matrix is passed onto a specific low-rank matrix. WNMF improves the clustering performance of SNMF. When a portion of data is labeled, it is desirable to incorporate the class labels information into WNMF in order to improve the clustering performance. To this end, a semisupervised NMF (SSNMF) [11] is studied by incorporating the domain knowledge into WNMF to extract more clustering structure information.In SNMF, WNMF, and SSNMF, the low rank approximation to the pairwise similarity matrix is used. The goal is to learn the latent clustering structure by minimizing the reconstruction error. However, since there is no prior knowledge about the data, the kernel matrix is often obtained based on pairwise Euclidean distance in the high-dimensional space. It is more sensitive to the unexpected noise. Consequently, it may produce undesirable performances in clustering tasks by minimizing the objective function from the viewpoint of reconstruction in the form as SNMF, WNMF, and SSNMF. In this paper, we present a novel model, called relationship matrix nonnegative decomposition (RMND), for data clustering tasks. The RMND model is derived from the nonlinear NMF algorithms which take advantages of kernel functions in the high-dimensional feature space. RMND decomposes a pairwise similarity matrix into a product of a positive semidefinite matrix, a distribution matrix of similarity on latent features, and an encoding matrix. The positive semidefinite matrix pops out the clustering structure and is treated as a more convincing pairwise similarity matrix by an appropriate transformation. RMND learns the correct relationship matrix adaptively. Furthermore, according to the positive semidefiniteness, the SNMF formulation is incorporated in RMND, and then a more tractable representation of pairwise similarity matrix is obtained. We develop a learning procedure for RMND to discover the latent clustering structure. Experimental results show that the proposed RMND leads to significant improvements on clustering performance.The rest of the paper is organized as follows: in Section2, we briefly review the SNMF and WNMF. In Section 3, we present the proposed RMND model and its learning procedure. Some experimental results on several datasets are shown in Section 4. Finally, conclusions and final remarks are given in Section 5.


## 2. Symmetric NMF (SNMF) and Weighted NMF (WNMF)

A pairwise similarity matrixX is a nonnegative matrix, since the pairwise similarities between different objects cannot be negative. For the kernel case, X=VTV is the standard inner-product linear kernel matrix, where V is a nonnegative data matrix with size p×n. And it can be extended to any other kernels. NMF technique is powerful to discover the latent structure in X. Since X is a symmetric matrix, Ding et al. [10] introduced the SNMF model as follows: (2.1)X≈AAT,
where A is a nonnegative matrix of size n×q whose rows denote the degrees of the samples related to the q centroids of clusters.In (2.1), AAT is a positive semidefinite matrix. When the similarity matrix X is indefinite, X has negative eigenvalues. AAT will not provide a good approximation, since AAT cannot absorb the subspace associated with negative eigenvalues. For kernel matrices, decomposition in (2.1) is feasible. However, a large number of similarity matrices are nonnegative but not positive semidefinite matrix. Ding et al. [10] introduced another improved factorization model as(2.2)X≈ASAT,
where S is a nonnegative matrix of size q×q which inherits the indefiniteness of X. The detailed update rules for A and S can be found in [10].


## 3. Relationship Matrix Nonnegative Decomposition (RMND)

### 3.1. Proposed RMND Model

Both SNMF and WNMF are powerful methods for learning the clustering structure from a pairwise similarity matrix or a kernel matrix. If the data from different latent classes are well separated,X would be approximately a block diagonal matrix. It is easy to find the clustering structure by SNMF and WNMF in that case. Thus, AAT and ASAT would be approximately block diagonal matrices. SNMF and WNMF learn good approximation for X. This is the simplest case in data clustering. In many real applications, data from different latent classes often crossly corrupt. Then, X is not a block diagonal matrix although the data is rearranged appropriately. By minimizing the reconstruction error in (2.1) and (2.2), SNMF and WNMF would not find favorable clustering structure. The reason is AAT and ASAT would be approximately block diagonal matrices for good clustering. Consequently, it is desirable to build a new model for finding correct clustering structure and approximating X well at the same time.Recently, NMF has been extended to nonlinear nonnegative component analysis algorithms (referred as KNMF) by Zafeiriou and Petrou [12]. KNMF is proposed to model efficiently the nonlinearities that are present in most real-life applications. The idea of KNMF is to perform NMF in the high-dimensional feature space. Specifically, KNMF is to find a set of nonnegative weights and nonnegative basis vectors such that the nonlinearly mapped training vectors can be written as linear combinations of nonlinear mapped nonnegative basis vectors. Let ϕ:ℛ+p→Ϝ be a mapping that projects data vi to a Hilbert space Ϝ of arbitrary dimensionality. KNMF attempts to find a set of q vectors wj∈ℛ+p and a set of nonnegative weights hji such that  (3.1)VΦ≈WΦH,
where VΦ=[ϕ(v1),…,ϕ(vn)] and WΦ=[ϕ(w1),…,ϕ(wq)]. The nonlinear mapping is related to a kernel function with the operation as k(vi,vj)=ϕ(vi)Tϕ(vj). The detailed algorithms for directly learning W and H can be found in [12].In this paper, we focus on the convex nonlinear nonnegative component analysis algorithm (referred as CKNMF) in [12]. Instead of finding both W and H simultaneously, Zafeiriou and Petrou followed the similar lines as convex-NMF [9] and assumed that the centroid ϕ(wj) is in the space spanned by the columns of VΦ. Formally, ϕ(wj) can be written as (3.2)ϕ(wj)=m1jϕ(v1)+⋯+mnjϕ(vn)=∑l=1nmljϕ(vl),
where mlj≥0 and ∑l=1nmlj=1. This means that the centroid ϕ(wj) can be interpreted as a convex weighted combination of certain data point ϕ(vl). Using (3.2), approximation (3.1) is reformulated in the matrix form as  (3.3)VΦ≈VΦMH⟹X≈XMH,
where X is the kernel matrix with the entry xij=k(vi,vj)=ϕ(vi)Tϕ(vj). Equation (3.3) provides a new decomposition of kernel matrix. Each matrix has the explicit interpretation. X is the relationship matrix between different objects based on a certain kernel function, each column of M denotes the relationship distribution on certain latent feature according to the property of convex combinations, and H is the encoding coefficient matrix. In particular, we rewrite (3.3) in an entry form as  (3.4)xij≈∑r=1n∑s=1qxirmrshsj=∑s=1q(XM)ishsj.
It can be noted from (3.4) that (XM)is represents the weighted average relationship measure correlated to object i on the sth latent feature, and then the relationship measure between object i and j is a linear combination of the weighted average relationship measures on the latent features.However, (3.3) or (3.4) is not convincible for clustering tasks, since the kernel matrix X cannot represent the relationship between different objects faithfully. It is more desirable to discover the latent relationship adaptively. Consequently, we replace the X in the right hand side in (3.3) by a latent relationship matrix (3.5)X≈RMH,
where R denotes the correct relationship matrix. From (3.5), the correct relationship matrix R would be adaptively learned from the kernel matrix X. X is a linear transformation of R. A relationship matrix R, which pops out the latent clustering structure, is approximately a block diagonal matrix under suitable rearrangement on samples. It would be a positive semidefinite matrix. SNMF model is reasonable to learn a low rank representation of matrix R. Thus, we derive our new model, referred as relationship matrix nonnegative decomposition (RMND), as follows: (3.6)X≈AATMH,
where A is a nonnegative matrix whose rows denote the degrees of the samples related to the centroids of clusters. The corresponding optimization problem of RMND is given by (3.7)min⁡A,M,HD=12‖X-AATMH‖2s.t.A≥0,M≥0,H≥0,∑imij=1,∀j=1,2,…,q.
The objective function D of RMND in (3.7) is not convex for A, M, and H simultaneously. Therefore, it is unrealistic to expect an algorithm to find the global minimum of D. As it is known that AATMH=AATMUU-1H, where U is a diagonal matrix with ujj=∑imij, the normalization on M can be easily handled after M is updated. Therefore, we only consider the nonnegativity constraints on the factors. When A is fixed, let γjk and ψjk be the Lagrange multiplier for constraints mjk≥0 and hjk≥0, respectively. We define matrix Γ=[γjk] and Ψ=[ψjk], then the Lagrange multiplier ℒ is  (3.8)L=12‖X-AATMH‖2+Tr⁡(ΓMT)+Tr⁡(ΨHT),
where ∥·∥ denotes the Euclidean norm and Tr(·) is the trace function. The partial derivatives of ℒ with respect to M and H are (3.9)∂L∂M=AATAATMHHT-AATXHT+Γ,∂L∂H=MTAATAATMH-MTAATX+Ψ.
Using the KKT conditions γjkmjk=0 and ψjkhjk=0, we get the following equations: (3.10)(AATAATMHHT)jkmjk-(AATXHT)jkmjk=0,(MTAATAATMH)jkhjk-(MTAATX)jkhjk=0.
The above equations lead to the following multiplicative update rules:  (3.11)mjk⟵mjk(AATXHT)jk(AATAATMHHT)jk,hjk⟵hjk(MTAATX)jk(MTAATAATMH)jk.For factor matrixA, the corresponding partial derivatives of D is (3.12)∂D∂A=AATMHHTMTA+MHHTMTAATA-XHTMTA-MHXA.
Our algorithm essentially takes a step in the direction of the negative gradient and, subsequently, projects onto the constraint space, making sure that the taken step is small enough that the objective function D is reduced at every step. The learning procedure for RMND can be summarized as Algorithm 1.Algorithm 1:Relationship matrix nonnegative decomposition (RMND).
Input: Positive matrix X∈ℛn×n, and a positive integer q.Output: Nonnegative factor matrices A∈ℛn×q, M∈ℛn×q and H∈ℛq×n.Learning Procedure(S1)  InitializeA, M and H to random positive matrices, and normalize each column of A to one.(S2)  Repeat the iterations until convergence:(1)H←H⊗(MTAATX)⊘(MTAATAATMH).(2)M←M⊗(AATXHT)⊘(AATAATMHHT).(3)M←MU-1 and H←UH where U is a diagonal matrix with ujj=∑imij.(4) Repeatedly select small positive constantμA until the objective function is decreased.(i)Ã:=A-μA∂D∂A.(ii) Project each column ofÃ to be nonnegative vector with unit L2 norm.(5)A:=Ã.Above, ⊗ and ⊘ denote elementwise multiplication and division, respectively.


### 3.2. Computational Complexity Analysis

In this subsection, we discuss the extra computational cost of our proposed algorithm in comparison with SNMF and WNMF. We count the arithmetic operations for each algorithm. Based on the updating rules in [10], it is not hard to count the arithmetic operations of each iteration in SNMF and WNMF. For GNMF, the steepest descent method is used to update factor matrix A. We use the bipartition to determine the small positive constant μA. Let N1 be the maximum iteration number in the steepest descent method. We summary the computational operation counts for each iteration in Table 1. Suppose that the algorithms stop after N2 iterations and the overall cost for both SNMF and WNMF is (3.13)O(N2qn2).
The overall cost for RMND is (3.14)O(N2N1qn2).
Then, the overall cost of SNMF, WNMF, and RMND is related to qn2, where n is the number of samples. Much time is needed for large-scale data clustering tasks. For RMND, its overall cost is also effected by the maximum iteration number N1 in the steepest descent method. Nevertheless, RMND will be shown that it is capable of improving the clustering performance in Section 4. We will develop algorithms for fast convergence and low computational complexity in the future work.Table 1
Computational operation counts for each iteration in SNMF, WNMF, and RMND.
MethodFladd*flmlt⋆fldiv∘overallSNMFqn2+2q2n+2qnqn2+2q2n+2qnqnO(qn2)WNMF2qn2+4q2n+2qn+2q32qn2+4q2n+2qn+2q3+q2qn+q2O(qn2)RMND(1+4N1)qn2+(10+9N1)q2n+(4+4N1)qn+(4+3N1)q3+N1q+N1n2(1+4N1)qn2+(10+9N1)q2n+(4+3N1)qn+(4+3N1)q3+N1n2(3+N1)qnO(N1qn2)*fladd: a floating-point addition.⋆flmlt: a floating-point multiplication.  ∘fldiv: a floating-point division.


## 3.1. Proposed RMND Model

Both SNMF and WNMF are powerful methods for learning the clustering structure from a pairwise similarity matrix or a kernel matrix. If the data from different latent classes are well separated,X would be approximately a block diagonal matrix. It is easy to find the clustering structure by SNMF and WNMF in that case. Thus, AAT and ASAT would be approximately block diagonal matrices. SNMF and WNMF learn good approximation for X. This is the simplest case in data clustering. In many real applications, data from different latent classes often crossly corrupt. Then, X is not a block diagonal matrix although the data is rearranged appropriately. By minimizing the reconstruction error in (2.1) and (2.2), SNMF and WNMF would not find favorable clustering structure. The reason is AAT and ASAT would be approximately block diagonal matrices for good clustering. Consequently, it is desirable to build a new model for finding correct clustering structure and approximating X well at the same time.Recently, NMF has been extended to nonlinear nonnegative component analysis algorithms (referred as KNMF) by Zafeiriou and Petrou [12]. KNMF is proposed to model efficiently the nonlinearities that are present in most real-life applications. The idea of KNMF is to perform NMF in the high-dimensional feature space. Specifically, KNMF is to find a set of nonnegative weights and nonnegative basis vectors such that the nonlinearly mapped training vectors can be written as linear combinations of nonlinear mapped nonnegative basis vectors. Let ϕ:ℛ+p→Ϝ be a mapping that projects data vi to a Hilbert space Ϝ of arbitrary dimensionality. KNMF attempts to find a set of q vectors wj∈ℛ+p and a set of nonnegative weights hji such that  (3.1)VΦ≈WΦH,
where VΦ=[ϕ(v1),…,ϕ(vn)] and WΦ=[ϕ(w1),…,ϕ(wq)]. The nonlinear mapping is related to a kernel function with the operation as k(vi,vj)=ϕ(vi)Tϕ(vj). The detailed algorithms for directly learning W and H can be found in [12].In this paper, we focus on the convex nonlinear nonnegative component analysis algorithm (referred as CKNMF) in [12]. Instead of finding both W and H simultaneously, Zafeiriou and Petrou followed the similar lines as convex-NMF [9] and assumed that the centroid ϕ(wj) is in the space spanned by the columns of VΦ. Formally, ϕ(wj) can be written as (3.2)ϕ(wj)=m1jϕ(v1)+⋯+mnjϕ(vn)=∑l=1nmljϕ(vl),
where mlj≥0 and ∑l=1nmlj=1. This means that the centroid ϕ(wj) can be interpreted as a convex weighted combination of certain data point ϕ(vl). Using (3.2), approximation (3.1) is reformulated in the matrix form as  (3.3)VΦ≈VΦMH⟹X≈XMH,
where X is the kernel matrix with the entry xij=k(vi,vj)=ϕ(vi)Tϕ(vj). Equation (3.3) provides a new decomposition of kernel matrix. Each matrix has the explicit interpretation. X is the relationship matrix between different objects based on a certain kernel function, each column of M denotes the relationship distribution on certain latent feature according to the property of convex combinations, and H is the encoding coefficient matrix. In particular, we rewrite (3.3) in an entry form as  (3.4)xij≈∑r=1n∑s=1qxirmrshsj=∑s=1q(XM)ishsj.
It can be noted from (3.4) that (XM)is represents the weighted average relationship measure correlated to object i on the sth latent feature, and then the relationship measure between object i and j is a linear combination of the weighted average relationship measures on the latent features.However, (3.3) or (3.4) is not convincible for clustering tasks, since the kernel matrix X cannot represent the relationship between different objects faithfully. It is more desirable to discover the latent relationship adaptively. Consequently, we replace the X in the right hand side in (3.3) by a latent relationship matrix (3.5)X≈RMH,
where R denotes the correct relationship matrix. From (3.5), the correct relationship matrix R would be adaptively learned from the kernel matrix X. X is a linear transformation of R. A relationship matrix R, which pops out the latent clustering structure, is approximately a block diagonal matrix under suitable rearrangement on samples. It would be a positive semidefinite matrix. SNMF model is reasonable to learn a low rank representation of matrix R. Thus, we derive our new model, referred as relationship matrix nonnegative decomposition (RMND), as follows: (3.6)X≈AATMH,
where A is a nonnegative matrix whose rows denote the degrees of the samples related to the centroids of clusters. The corresponding optimization problem of RMND is given by (3.7)min⁡A,M,HD=12‖X-AATMH‖2s.t.A≥0,M≥0,H≥0,∑imij=1,∀j=1,2,…,q.
The objective function D of RMND in (3.7) is not convex for A, M, and H simultaneously. Therefore, it is unrealistic to expect an algorithm to find the global minimum of D. As it is known that AATMH=AATMUU-1H, where U is a diagonal matrix with ujj=∑imij, the normalization on M can be easily handled after M is updated. Therefore, we only consider the nonnegativity constraints on the factors. When A is fixed, let γjk and ψjk be the Lagrange multiplier for constraints mjk≥0 and hjk≥0, respectively. We define matrix Γ=[γjk] and Ψ=[ψjk], then the Lagrange multiplier ℒ is  (3.8)L=12‖X-AATMH‖2+Tr⁡(ΓMT)+Tr⁡(ΨHT),
where ∥·∥ denotes the Euclidean norm and Tr(·) is the trace function. The partial derivatives of ℒ with respect to M and H are (3.9)∂L∂M=AATAATMHHT-AATXHT+Γ,∂L∂H=MTAATAATMH-MTAATX+Ψ.
Using the KKT conditions γjkmjk=0 and ψjkhjk=0, we get the following equations: (3.10)(AATAATMHHT)jkmjk-(AATXHT)jkmjk=0,(MTAATAATMH)jkhjk-(MTAATX)jkhjk=0.
The above equations lead to the following multiplicative update rules:  (3.11)mjk⟵mjk(AATXHT)jk(AATAATMHHT)jk,hjk⟵hjk(MTAATX)jk(MTAATAATMH)jk.For factor matrixA, the corresponding partial derivatives of D is (3.12)∂D∂A=AATMHHTMTA+MHHTMTAATA-XHTMTA-MHXA.
Our algorithm essentially takes a step in the direction of the negative gradient and, subsequently, projects onto the constraint space, making sure that the taken step is small enough that the objective function D is reduced at every step. The learning procedure for RMND can be summarized as Algorithm 1.Algorithm 1:Relationship matrix nonnegative decomposition (RMND).
Input: Positive matrix X∈ℛn×n, and a positive integer q.Output: Nonnegative factor matrices A∈ℛn×q, M∈ℛn×q and H∈ℛq×n.Learning Procedure(S1)  InitializeA, M and H to random positive matrices, and normalize each column of A to one.(S2)  Repeat the iterations until convergence:(1)H←H⊗(MTAATX)⊘(MTAATAATMH).(2)M←M⊗(AATXHT)⊘(AATAATMHHT).(3)M←MU-1 and H←UH where U is a diagonal matrix with ujj=∑imij.(4) Repeatedly select small positive constantμA until the objective function is decreased.(i)Ã:=A-μA∂D∂A.(ii) Project each column ofÃ to be nonnegative vector with unit L2 norm.(5)A:=Ã.Above, ⊗ and ⊘ denote elementwise multiplication and division, respectively.


## 3.2. Computational Complexity Analysis

In this subsection, we discuss the extra computational cost of our proposed algorithm in comparison with SNMF and WNMF. We count the arithmetic operations for each algorithm. Based on the updating rules in [10], it is not hard to count the arithmetic operations of each iteration in SNMF and WNMF. For GNMF, the steepest descent method is used to update factor matrix A. We use the bipartition to determine the small positive constant μA. Let N1 be the maximum iteration number in the steepest descent method. We summary the computational operation counts for each iteration in Table 1. Suppose that the algorithms stop after N2 iterations and the overall cost for both SNMF and WNMF is (3.13)O(N2qn2).
The overall cost for RMND is (3.14)O(N2N1qn2).
Then, the overall cost of SNMF, WNMF, and RMND is related to qn2, where n is the number of samples. Much time is needed for large-scale data clustering tasks. For RMND, its overall cost is also effected by the maximum iteration number N1 in the steepest descent method. Nevertheless, RMND will be shown that it is capable of improving the clustering performance in Section 4. We will develop algorithms for fast convergence and low computational complexity in the future work.Table 1
Computational operation counts for each iteration in SNMF, WNMF, and RMND.
MethodFladd*flmlt⋆fldiv∘overallSNMFqn2+2q2n+2qnqn2+2q2n+2qnqnO(qn2)WNMF2qn2+4q2n+2qn+2q32qn2+4q2n+2qn+2q3+q2qn+q2O(qn2)RMND(1+4N1)qn2+(10+9N1)q2n+(4+4N1)qn+(4+3N1)q3+N1q+N1n2(1+4N1)qn2+(10+9N1)q2n+(4+3N1)qn+(4+3N1)q3+N1n2(3+N1)qnO(N1qn2)*fladd: a floating-point addition.⋆flmlt: a floating-point multiplication.  ∘fldiv: a floating-point division.


## 4. Numerical Experiments

We evaluate the performance of five different methods, RMND,K-means clustering, spectral clustering (SpeClus) [13], SNMF, and WNMF, in a task of data clustering. In RMND, once A is learned, we denote X̂=ÂÂT, where Â is the modification of A with normalized rows. We apply K-means clustering on A, H and the factor matrices learned by SNMF and WNMF on X̂. Finally, the best clustering results of RMND is obtained.


### 4.1. Datasets

We use five datasets for evaluating the clustering performance of algorithms. The detailed description for the datasets is listed below.(1)
JAFFE [14] is a face database often used in the literature of face recognition. JAFFE database contains 213 face images from 10 different persons under varying in facial expression.(2)
Coil20 is a dataset consisting of 1440 images from 20 classes under varying in rotations (http://www1.cs.columbia.edu/CAVE/software/softlib/coil-20.php). For simplicity, the first 10 classes are used in our experiments.(3)
reuters dataset [15] is from the news articles of the Reuters newswire. Reuters-21578 corpus contains 21,578 documents in 135 categories. We use the data preprocessed by Cai et al. [15]. The documents with multiple category labels are discarded and the dataset with 8067 documents in the largest 30 categories is derived. Then, we randomly select at most 5 categories for efficiency.(4)
USPS is a dataset of handwritten digits from 0 to 9 (http://www.zjucadcg.cn/dengcai/Data/MLData.html). These image data have been preprocessed by Cai et al. [15]. The USPS dataset used here consists of mixed-sign data. The first 100 samples from each class are used in our experiments.


### 4.2. Evaluation Metrics for Clustering and Kernel Function

In all these methods, we setq, the dimensionality of feature subspace, to be equal to the number of classes of datasets. Two performance measures (clustering accuracy and normalized mutual information) are used to evaluate the clustering performance of algorithms. If we denote the true label for the ith data to be ci, and the estimated label ĉi, the clustering accuracy can be computed by ∑i=1n(δ(ci,ĉi)/n), where δ(x,y)=1 for x=y and δ(x,y)=0 for x≠y. The clustering accuracy achieves maximum value 1 when clustering results are perfect. Let T be the set of clusters obtained from the ground truth and T′ obtained from our algorithm. The normalized mutual information measure is defined by  (4.1)NMI=MI(T,T′)max⁡⁡(H(T),H(T′)),
where MI(T,T′) is the mutual information between T and T′, H(T) and H(T′) denote the entropies of T and T′, respectively. The value of NMI varies between 0 and 1. The greater the normalized mutual information, the better the clustering quality.In our experiments, we use Gaussian kernel function to calculate the kernel matrix. And then, we evaluate the clustering performance of different algorithms. For comparison, the same kernel matrix has been used in our experiments. The Gaussian kernel function used here is as follows:(4.2)g(y,z)=e-∥y-z∥2/2t2,
where t is a parameter. X is given by  (4.3)xij={e-∥vi-vj∥2/2t2,vi∈Nl(vj)orvj∈Nl(vi),0,otherwise,
where t is a heat kernel parameter [16] and Nl(vj) denotes a set of l nearest neighbors of vj. For simplicity, we present a tunable way to set t as a square average distance between different samples [17] (4.4)t=m2n2∑i,j‖vi-vj‖2,
where m is a scale factor.


### 4.3. Experimental Results on the JAFFE Dataset

To demonstrate how our method improves the performance of data clustering, we firstly set the number of nearest neighborsl=n-1, the scale factor m=1, where n is the number of samples. Then, the pairwise similarity matrix X is the weighted adjacency matrix of the fully connected graph similar to those in spectral clustering. Figure 1 displays the pairwise similarity matrix obtained from the JAFFE dataset. It can be noted that X is ill structured. In order to discover the latent clustering structure, we apply RMND, SNMF, and WNMF algorithms to obtain the decomposition form of X, respectively. The factor matrices are randomly initialized by the values in the range [0, 1]. Figure 2 shows that objective function value decreases with increasing iteration number. It can be noted that the reconstruction error of RMND is smaller than those of SNMF and WNMF after 500 iterations. Figures 3, 4, and 5 display the estimated pairwise similarity matrix of SNMF, WNMF, and RMND algorithms, respectively. The estimated pairwise similarity matrix learned by RMND is more highly structured. RMND produces better representations of kernel matrix than SNMF and WNMF. SNMF and WNMF have similar representations of X when the algorithms are convergent.Figure 1
The pairwise similarity matrixX obtained from the JAFFE dataset.Figure 2
Objective function values as a function of the number of iterations for RMND, SNMF, and WNMF on theJAFFE dataset.Figure 3
Estimated pairwise similarity matrix by applying SNMF to theJAFFE dataset.Figure 4
Estimated pairwise similarity matrix by applying WNMF to theJAFFE dataset.Figure 5
Estimated pairwise similarity matrix by applying RMND to theJAFFE dataset.


### 4.4. Clustering Performance Comparison

Tables2, 3, and 4 show the experimental results on the Coil20, Reuters, and USPS datasets with the number of nearest neighbors l=n-1 and the scale factor m=1, respectively. The evaluations are conducted with different numbers of classes, ranging from 4 to 12 for the Coil20 dataset, 2 to 5 for the Reuters dataset, and 2 to 10 for the USPS dataset. The cluster number indicates the class number used for experiments. In our experiments, the first k classes in the database are used. For each given class number k, 20 independent tests are conducted under different initializations. For the Reuters dataset, different randomly chosen classes are used. And the average performance is calculated over these 20 tests. For each test, K-means algorithm is applied 5 times with different start points, and the best result in terms of the objective function of K-means is recorded. From these tables, it can be noticed that RMND yields the best average clustering results on the three datasets although the clustering accuracy of RMND is a little smaller than those of other methods for certain cases of class numbers.Table 2
Clustering accuracy and normalized mutual information ofK-means, spectral clustering (SpeClus), SNMF, WNMF, and RMND on the Coil20 dataset.
Cluster numberClustering accuracyNormalized mutual informationkK-meansSpeClusSNMFWNMFRMNDK-meansSpeClusSNMFWNMFRMND40.66020.67360.67000.66820.68110.51730.54940.52450.53260.557860.48070.48160.46700.48520.50540.45720.46690.42830.43420.445680.51280.54120.49670.47020.54440.53120.56320.53460.49400.5634100.53550.55940.55430.51040.55320.60480.60020.60800.56320.6055avg.0.54730.56400.54700.53350.57100.52760.54490.51350.50600.5431Table 3
Clustering accuracy and normalized mutual information ofK-means, spectral clustering (SpeClus), SNMF, WNMF, and RMND on the Reuters dataset.
Cluster numberClustering accuracyNormalized mutual informationkK-meansSpeClusSNMFWNMFRMNDK-meansSpeClusSNMFWNMFRMND20.63250.79090.76650.70230.84570.16210.41190.33220.25840.529430.55360.69260.68570.65380.80220.24270.49990.49160.43910.624240.53010.62160.57660.53750.66340.28930.50640.41380.30970.529150.43660.58880.56350.46320.58170.23250.55670.47540.29500.5047ave.0.53820.67350.65060.58920.72330.23280.49370.42830.32460.5469Table 4
Clustering accuracy and normalized mutual information ofK-means, spectral clustering (SpeClus), SNMF, WNMF, and RMND on the USPS dataset.
Cluster numberClustering accuracyNormalized mutual informationkK-meansSpeClusSNMFWNMFRMNDK-meansSpeClusSNMFWNMFRMND20.96500.96500.96500.96600.99000.81350.81350.96500.96600.990030.88670.84670.87000.84020.89120.69170.63800.66890.66560.718940.80150.78500.80570.79340.84210.64300.59040.60120.61180.663450.83920.77000.78640.76860.83540.68260.61470.62520.61950.658660.73300.73000.72060.69280.73250.61400.61100.59210.56330.606170.71940.71860.71550.67870.73310.60410.60630.59250.56560.611680.71990.73020.71940.70250.74630.62390.63200.62320.59870.649490.69320.73580.69370.67020.70070.59020.64060.59100.56400.5922100.63430.68600.65270.62160.67250.55560.60230.55670.53330.5605ave.0.77690.77410.76990.74820.79380.64650.63880.64620.63200.6723


### 4.5. Clustering Performance Evaluation on Various Pairwise Similarity Matrix

In graph embedding methods, the pairwise similarity matrix (also referred as affinity matrix) has been widely used. In this subsection, we test our algorithm under different adjacency graph constructions to show how the different graph structures will affect the clustering performance. The number of nearest neighbors used in this paper defines the locality of graph. In Figures6 and 7, we show the relationship between the average clustering accuracies and normalized mutual information versus different numbers of nearest neighbors under 20 independent runs and the scale factor m=1, respectively. As can be seen, RMND performs better when the number of nearest neighbors is larger than 60 and the maximum achieved clustering accuracy is 86.62% when 190 nearest neighbors are used in (4.3). The normalized mutual information is better after l>150, and the maximum normalized mutual information is 0.8429 at l=210. For SNMF and WNMF, the best clustering accuracies are 84.55% and 82.82%, respectively, and the best normalized mutual information are 0.8373 and 0.8214, respectively. This implies that RMND is more suitable to discover the clustering structure contained in smoothed pairwise similarity matrix.Figure 6
Clustering accuracies derived by applying RMND, SNMF, and WNMF on theJAFFE database versus different number of nearest neighbors.Figure 7
Normalized mutual information derived by applying RMND, SNMF, and WNMF on theJAFFE database versus different number of nearest neighbors.Note that the choice of parameters in (4.4) is still an open problem. To this end, we explore the range of possible values of the scale factor m to determine the heat kernel parameter. Specifically, m is taken from {0.2,0.4,…,2.0}. Figures 8 and 9 show the clustering accuracies and normalized mutual information on the JAFFE dataset under different scale factors. n-1 nearest neighbors are used in this experiment. As m increases, the performance decreases. The reason might be that the difference between different pairwise similarity is small for larger value of m. The pairwise similarity matrix becomes more and more ill structured. Nevertheless, RMND leads to better clustering performance compared with SNMF and WNMF.Figure 8
Clustering accuracies derived by applying RMND, SNMF, and WNMF on theJAFFE database versus different scale factor m.Figure 9
Normalized mutual information derived by applying RMND, SNMF, and WNMF on theJAFFE database versus different scale factor m.


## 4.1. Datasets

We use five datasets for evaluating the clustering performance of algorithms. The detailed description for the datasets is listed below.(1)
JAFFE [14] is a face database often used in the literature of face recognition. JAFFE database contains 213 face images from 10 different persons under varying in facial expression.(2)
Coil20 is a dataset consisting of 1440 images from 20 classes under varying in rotations (http://www1.cs.columbia.edu/CAVE/software/softlib/coil-20.php). For simplicity, the first 10 classes are used in our experiments.(3)
reuters dataset [15] is from the news articles of the Reuters newswire. Reuters-21578 corpus contains 21,578 documents in 135 categories. We use the data preprocessed by Cai et al. [15]. The documents with multiple category labels are discarded and the dataset with 8067 documents in the largest 30 categories is derived. Then, we randomly select at most 5 categories for efficiency.(4)
USPS is a dataset of handwritten digits from 0 to 9 (http://www.zjucadcg.cn/dengcai/Data/MLData.html). These image data have been preprocessed by Cai et al. [15]. The USPS dataset used here consists of mixed-sign data. The first 100 samples from each class are used in our experiments.


## 4.2. Evaluation Metrics for Clustering and Kernel Function

In all these methods, we setq, the dimensionality of feature subspace, to be equal to the number of classes of datasets. Two performance measures (clustering accuracy and normalized mutual information) are used to evaluate the clustering performance of algorithms. If we denote the true label for the ith data to be ci, and the estimated label ĉi, the clustering accuracy can be computed by ∑i=1n(δ(ci,ĉi)/n), where δ(x,y)=1 for x=y and δ(x,y)=0 for x≠y. The clustering accuracy achieves maximum value 1 when clustering results are perfect. Let T be the set of clusters obtained from the ground truth and T′ obtained from our algorithm. The normalized mutual information measure is defined by  (4.1)NMI=MI(T,T′)max⁡⁡(H(T),H(T′)),
where MI(T,T′) is the mutual information between T and T′, H(T) and H(T′) denote the entropies of T and T′, respectively. The value of NMI varies between 0 and 1. The greater the normalized mutual information, the better the clustering quality.In our experiments, we use Gaussian kernel function to calculate the kernel matrix. And then, we evaluate the clustering performance of different algorithms. For comparison, the same kernel matrix has been used in our experiments. The Gaussian kernel function used here is as follows:(4.2)g(y,z)=e-∥y-z∥2/2t2,
where t is a parameter. X is given by  (4.3)xij={e-∥vi-vj∥2/2t2,vi∈Nl(vj)orvj∈Nl(vi),0,otherwise,
where t is a heat kernel parameter [16] and Nl(vj) denotes a set of l nearest neighbors of vj. For simplicity, we present a tunable way to set t as a square average distance between different samples [17] (4.4)t=m2n2∑i,j‖vi-vj‖2,
where m is a scale factor.


## 4.3. Experimental Results on the JAFFE Dataset

To demonstrate how our method improves the performance of data clustering, we firstly set the number of nearest neighborsl=n-1, the scale factor m=1, where n is the number of samples. Then, the pairwise similarity matrix X is the weighted adjacency matrix of the fully connected graph similar to those in spectral clustering. Figure 1 displays the pairwise similarity matrix obtained from the JAFFE dataset. It can be noted that X is ill structured. In order to discover the latent clustering structure, we apply RMND, SNMF, and WNMF algorithms to obtain the decomposition form of X, respectively. The factor matrices are randomly initialized by the values in the range [0, 1]. Figure 2 shows that objective function value decreases with increasing iteration number. It can be noted that the reconstruction error of RMND is smaller than those of SNMF and WNMF after 500 iterations. Figures 3, 4, and 5 display the estimated pairwise similarity matrix of SNMF, WNMF, and RMND algorithms, respectively. The estimated pairwise similarity matrix learned by RMND is more highly structured. RMND produces better representations of kernel matrix than SNMF and WNMF. SNMF and WNMF have similar representations of X when the algorithms are convergent.Figure 1
The pairwise similarity matrixX obtained from the JAFFE dataset.Figure 2
Objective function values as a function of the number of iterations for RMND, SNMF, and WNMF on theJAFFE dataset.Figure 3
Estimated pairwise similarity matrix by applying SNMF to theJAFFE dataset.Figure 4
Estimated pairwise similarity matrix by applying WNMF to theJAFFE dataset.Figure 5
Estimated pairwise similarity matrix by applying RMND to theJAFFE dataset.


## 4.4. Clustering Performance Comparison

Tables2, 3, and 4 show the experimental results on the Coil20, Reuters, and USPS datasets with the number of nearest neighbors l=n-1 and the scale factor m=1, respectively. The evaluations are conducted with different numbers of classes, ranging from 4 to 12 for the Coil20 dataset, 2 to 5 for the Reuters dataset, and 2 to 10 for the USPS dataset. The cluster number indicates the class number used for experiments. In our experiments, the first k classes in the database are used. For each given class number k, 20 independent tests are conducted under different initializations. For the Reuters dataset, different randomly chosen classes are used. And the average performance is calculated over these 20 tests. For each test, K-means algorithm is applied 5 times with different start points, and the best result in terms of the objective function of K-means is recorded. From these tables, it can be noticed that RMND yields the best average clustering results on the three datasets although the clustering accuracy of RMND is a little smaller than those of other methods for certain cases of class numbers.Table 2
Clustering accuracy and normalized mutual information ofK-means, spectral clustering (SpeClus), SNMF, WNMF, and RMND on the Coil20 dataset.
Cluster numberClustering accuracyNormalized mutual informationkK-meansSpeClusSNMFWNMFRMNDK-meansSpeClusSNMFWNMFRMND40.66020.67360.67000.66820.68110.51730.54940.52450.53260.557860.48070.48160.46700.48520.50540.45720.46690.42830.43420.445680.51280.54120.49670.47020.54440.53120.56320.53460.49400.5634100.53550.55940.55430.51040.55320.60480.60020.60800.56320.6055avg.0.54730.56400.54700.53350.57100.52760.54490.51350.50600.5431Table 3
Clustering accuracy and normalized mutual information ofK-means, spectral clustering (SpeClus), SNMF, WNMF, and RMND on the Reuters dataset.
Cluster numberClustering accuracyNormalized mutual informationkK-meansSpeClusSNMFWNMFRMNDK-meansSpeClusSNMFWNMFRMND20.63250.79090.76650.70230.84570.16210.41190.33220.25840.529430.55360.69260.68570.65380.80220.24270.49990.49160.43910.624240.53010.62160.57660.53750.66340.28930.50640.41380.30970.529150.43660.58880.56350.46320.58170.23250.55670.47540.29500.5047ave.0.53820.67350.65060.58920.72330.23280.49370.42830.32460.5469Table 4
Clustering accuracy and normalized mutual information ofK-means, spectral clustering (SpeClus), SNMF, WNMF, and RMND on the USPS dataset.
Cluster numberClustering accuracyNormalized mutual informationkK-meansSpeClusSNMFWNMFRMNDK-meansSpeClusSNMFWNMFRMND20.96500.96500.96500.96600.99000.81350.81350.96500.96600.990030.88670.84670.87000.84020.89120.69170.63800.66890.66560.718940.80150.78500.80570.79340.84210.64300.59040.60120.61180.663450.83920.77000.78640.76860.83540.68260.61470.62520.61950.658660.73300.73000.72060.69280.73250.61400.61100.59210.56330.606170.71940.71860.71550.67870.73310.60410.60630.59250.56560.611680.71990.73020.71940.70250.74630.62390.63200.62320.59870.649490.69320.73580.69370.67020.70070.59020.64060.59100.56400.5922100.63430.68600.65270.62160.67250.55560.60230.55670.53330.5605ave.0.77690.77410.76990.74820.79380.64650.63880.64620.63200.6723


## 4.5. Clustering Performance Evaluation on Various Pairwise Similarity Matrix

In graph embedding methods, the pairwise similarity matrix (also referred as affinity matrix) has been widely used. In this subsection, we test our algorithm under different adjacency graph constructions to show how the different graph structures will affect the clustering performance. The number of nearest neighbors used in this paper defines the locality of graph. In Figures6 and 7, we show the relationship between the average clustering accuracies and normalized mutual information versus different numbers of nearest neighbors under 20 independent runs and the scale factor m=1, respectively. As can be seen, RMND performs better when the number of nearest neighbors is larger than 60 and the maximum achieved clustering accuracy is 86.62% when 190 nearest neighbors are used in (4.3). The normalized mutual information is better after l>150, and the maximum normalized mutual information is 0.8429 at l=210. For SNMF and WNMF, the best clustering accuracies are 84.55% and 82.82%, respectively, and the best normalized mutual information are 0.8373 and 0.8214, respectively. This implies that RMND is more suitable to discover the clustering structure contained in smoothed pairwise similarity matrix.Figure 6
Clustering accuracies derived by applying RMND, SNMF, and WNMF on theJAFFE database versus different number of nearest neighbors.Figure 7
Normalized mutual information derived by applying RMND, SNMF, and WNMF on theJAFFE database versus different number of nearest neighbors.Note that the choice of parameters in (4.4) is still an open problem. To this end, we explore the range of possible values of the scale factor m to determine the heat kernel parameter. Specifically, m is taken from {0.2,0.4,…,2.0}. Figures 8 and 9 show the clustering accuracies and normalized mutual information on the JAFFE dataset under different scale factors. n-1 nearest neighbors are used in this experiment. As m increases, the performance decreases. The reason might be that the difference between different pairwise similarity is small for larger value of m. The pairwise similarity matrix becomes more and more ill structured. Nevertheless, RMND leads to better clustering performance compared with SNMF and WNMF.Figure 8
Clustering accuracies derived by applying RMND, SNMF, and WNMF on theJAFFE database versus different scale factor m.Figure 9
Normalized mutual information derived by applying RMND, SNMF, and WNMF on theJAFFE database versus different scale factor m.


## 5. Conclusions and Future Work

We have presented a novel relationship matrix nonnegative decomposition (RMND) model for data clustering task. The RMND model is formulated by decomposing a pairwise similarity into a product of three low-rank nonnegative matrices which have explicit interpretation. The correct relationship matrix is adaptively learned from the pairwise similarity matrix by RMND. We develop a learning procedure based on multiplicative update rules and steepest descent method to calculate the nonnegative solution of RMND. Extensive numerical experiments confirm that (1) RMND provides a favorable low-rank representation of pairwise similarity matrix. (2) By using an appropriate kernel function, the ability of RMND, SNMF, and WNMF to deal with mixed-signed data makes them useful for many applications in contrast to original NMF. (3) RMND improves the clustering performance of SNMF and WNMF.Further future work includes the following topics. The first is to develop algorithms for fast convergence and better solution in terms of minimizing the objective function. The second is to investigate the ability of RMND on different kinds of kernel functions.



---

*Source: 864540-2011-05-05.xml*