Adaptive Manifold Regularized Matrix Factorization for Data Clustering

1 Introduction

The task of data clustering partitions the input data samples into certain clusters such that the samples in a same group would share high similarity to each other, and it has been widely investigated in the data mining and machine learning areas [Zhang et al., 2012; Wang et al., 2013; Xu et al., 2017; Liu et al., 2017]. Since the data clustering could be regarded as a special case of classification but without any training data, the clustering results always highly depend on the data similarity learning [Nie et al., 2014]. In the past decades, many clustering algorithms have been proposed, e.g., k-means clustering [Hartigan and Wong, 1979], hierarchical clustering [Jain et al., 1999], spectral clustering [von Luxburg, 2007; Shi and Malik, 2000], subspace clustering [Vidal, 2011], and matrix factorization based methods [Ding et al., 2010]. Among which, our proposed method shares both of the advantages of the spectral clustering and matrix factorization, therefore we briefly review the related works along these two directions, respectively.

∗Corresponding author.

Spectral clustering is one of the most important clustering techniques in the literature and has demonstrated its strong capability in group objects by analyzing complex data structural information [Yang et al., 2016]. Specifically, it assumes that any two data points in the high density region of the low dimensional data manifold should share the same cluster. In order to capture the nonlinear and low dimensional manifold structure of the input data, an affinity matrix (or data similarity matrix) is required as input [He et al., 2011; Guo, 2015], and then the cluster assignment could be obtained by the spectrum of that affinity matrix. Traditionally, the Gaussian kernel function is usually employed to construct such affinity matrix [Huang et al., 2015]. In recent years, some advanced techniques have been proposed to explore some better affinity matrices or data representations, e.g., constrained Laplacian rank [Nie et al., 2016a], clustering with adaptive neighbors [Nie et al., 2014], low-rank representation [Liu et al., 2013], least squares regression [Lu et al., 2012], and robust subspace segmentation [Guo, 2015]. However, the spectral clustering is basically a two-steps approach, thus usually a simple k-means would be used after the affinity matrix has been learned, which may cause sub-optimal and unscalable clustering results due to the drawbacks inherited by the k-means clustering [Xu et al., 2016].

The non-negative matrix factorization (NMF) aims to find two non-negative matrices whose product provides a good approximation to the observation feature matrix [Liu and Tao, 2016], thus it could be used for data clustering by interpreting the two factor matrices as the cluster indicator and latent feature matrix, respectively [Ding et al., 2010; Cai et al., 2011]. In addition, various of priories have been added into the model to regularize the matrix factorization more fit for the task of data clustering, e.g., the manifold regularization [Huang et al., 2014] and sparsity constraint [Wang et al., 2015]. However, there are still following issues which may easily achieve poor performance in the matrix factorization based clustering. Firstly, as discussed above, most of exist methods directly introduce the Gaussian kernel derived Laplacian matrix for manifold regularization, while ignore to explore a more meaningful affinity matrix to better regularize the model. Secondly, the standard NMF uses the ℓ2-norm based squared residue minimization to measure the loss, which would be easily effected by the noises and outliers [Meng and la Torre, 2013; Huang et al., 2014].

In this contribution, we propose a novel adaptive manifold regularized matrix factorization (AMRMF) algorithm for data clustering, which avoids the risks mentioned in the above sections. In detail, the major advantages of the proposed algorithm are summarized as follows.

• The AMRMF model regards the clustering in a matrix factorization point of view, thus the desired data labels could be explicitly obtained from one of the factor matrices, i.e., the cluster indicator matrix. By such way, the AMRMF could always arrive at a scalable and reproduceable result in practice, which is superior to the traditional methods such as k-means and spectral clustering.
• The AMRMF model jointly learns an affinity matrix with the matrix factorization, therefore, the ideal data similarity under our assumption has been well uncovered, and the learned affinity matrix may better guide the manifold regularization to fit the clustering task. Compare to the exist graph clustering methods which directly address the Gaussian kernel function to construct the affinity matrix, the proposed AMRMF reveals a more flexible, meaningful but parameter-free way.
• The AMRMF model employs the ℓ2,1-norm to measure the loss of matrix factorization, therefore, compare to the conventional ℓ2-norm based matrix factorization, the proposed AMRMF model would not sensitive to the data noises and outliers and could be better applied to practical data mining applications.

However, since the proposed AMRMF model learns the data similarity matrix and cluster indicator simultaneously and introduces a new constraint (i.e., the ℓ2,1-norm), the conventional auxiliary function optimization method is no longer applicable for our AMRMF problem. Therefore, we have figured out a new Augmented Lagrangian Multiplier (ALM) based procedure to get the solution of our proposed objective function. The rest of the paper is structured as follows: section 2 introduces the detailed objective function of the proposed AMRMF model, section 3 presents an efficient optimization procedure to solve the AMRMF objective function. After that, the experimental results on several real world datasets are reported in section 4, followed by the conclusions in section 5.

2 Adaptive Manifold RegularizedMatrix Factorization

In this section, we present the proposed AMRMF model by first formulating the objective function of robust matrix factorization, and then introducing the steps to learn the affinity matrix simultaneously. After that, an efficient algorithm to tackle the AMRMF model is discussed in the next section. Throughout this paper, the matrix is represented as A ∈ Rp×q , in which the (i, j)-th element of A is denoted by aij, the i-th column of A is denoted by a vector ai ∈ Rp .

The trace and transpose of A are denoted by tr(A) and AT, respectively. The F-norm and ℓ2,1-norm of A are denoted by ‖A‖F and ‖A‖2,1 , respectively.

Given a data matrix X ∈ Rl×n , in which l and n are the the feature dimensionality of each sample and number of data samples, respectively. Therefore, each data sample could be denoted by xi ∈ Rl . In this paper, we propose to perform the matrix factorization on X and consider one of the factor matrices as the cluster indicator which divides X into k clusters:

where V ∈ Rl×k is the latent feature matrix (or the cluster centroid) and U ∈ Rn×k is the cluster indicator [Cai et al., 2011; Huang et al., 2014; Trigeorgis et al., 2014]. Note that in the objective function eq. (1), the loss of matrix factorization is measured by the squared residue error in the form of ℓ2-norm, therefore, the noises and outliers in the dataset with large reconstruction errors will heavily effect the matrix factorization because the errors have been enlarged. In order to relieve this issue, in this paper, we introduce the ℓ2,1-norm instead of the conventional ℓ2-norm based matrix factorization, which avoids the samples with large errors (i.e., the noises and outliers) dominate the objective function and thus makes the model more robust. Then we have the following improved matrix factorization optimization:

However, the model in eq. (2) would result in unsatisfactory clustering performance since there is no further constraints on the cluster indicator U. In the literature, the manifold regularization is often adopted to let the similar data samples fromX share the similar clustering labels [Gong et al., 2015; Zhang et al., 2015], and in most of the cases, the Laplacian regularization is incorporated with the matrix factorization [Cai et al., 2011; Huang et al., 2014]. However, in the exist works, the affinity matrix is usually computed by a predefined model (e.g., Gaussian kernel function) with carefully tuned parameters combination, which may not optimal in practice. Therefore, in this paper, we propose to learn an affinity matrix to better regularize the proposed matrix factorization in eq. (2).

To begin with the data similarity learning, we suppose that each sample xi could be linked to any other sample xj with probability sij, where sij is an element of the expected similarity matrix S. Obviously, we suggest that the similar sample pair with small distance ‖xi -xj‖22 should be assigned a high probability sij. Therefore, we have the following objective function to optimize the S which meets our assumption:

where α is the regularization parameter.

In order to further make the model benefit for clustering, we need the similarity matrix contains exact k connected components rather than all the elements have been linked together. Note that we have the equation that ∑ij ‖ui - uj‖22 sij = 2tr(U TLSU) in which LS is the Laplacian matrix computed by the learned S, according to [Chung, 1997], then, the optimization in eq. (3) could achieve an ideal neighbors assignment if we add an additional constraint rank(LS) = n - k. However, the eq. (3) with this rank constraint is hard to solve. To track this issue, we relax the problem followed by [Nie et al., 2016b]. Let σi(LS) denotes the i-th smallest eigenvalue of LS, since the LS must be positive semi-definite, then we have σi(LS) ≥ 0. Therefore, the rank constraint rank(LS) = n - k equals to ∑ki=1 σi(LS) = 0. On the other hand, we also have the fact that ∑ki=1 σi(LS) = minU tr(U TLSU), thus, we rewrite problem eq. (3) as:

Note that optimization in eq. (4) is a relaxation of eq. (3) with the rank constraint as long as γ has been set as a large enough value, in such condition, tr(U TLSU) would be forced to close to zero and thus ∑ki=1 σi(LS) = 0 would be satisfied accordingly.

Finally, by combining the eqs. (2) and (4) together with an additional regularization parameter β, we have the objective function of the proposed AMRMF clustering model:

3 AMRMF Optimization

The objective function in above eq. (5) is not convex in three variables, thus, we consider to use an Augmented Lagrangian Multiplier (ALM) method to optimize them alteratively. By introducing two auxiliary variables E = X - V U T and Z = U. The objective function can be rewritten into the following equivalent problem:

which can be solved by the following ALM problem:

where λ1 and λ2 are the Lagrangian multipliers and µ is a regularity coefficient to control the penalty for the two violation of equality constraints in eq. (7). Since the objective function above carries five variables and additional multipliers, we adopt an alternative optimization method to reduce it to a few manageable subproblems with the closed form solution, each minimizes the objective function with respect to one variable while fixing the other variables.

Update S

To update S, we fix other variables except S and remove terms that are irrelevant to S. Denote dxij = ‖xi -xj‖22 , then eq. (7) becomes:

Denote duz ij = ‖zi - uj‖22 , note that the problem above is independent between different i, we can deal with following problem individually for each i:

Denote di ∈ Rn is a vector with the j-th element as dij = dxij + γβ duz ij , then the above problem can be rewritten as follows:

Update U

To update U, we fix other variables except U and remove terms that are irrelevant to U. Then eq. (7) becomes:

which can be further reduced as following:

where

Thus, we further arrives:

We then have:

where Nu and Qu are the left and right singular vectors of the economic singular value decomposition of H.

Update V

To update V , we fix other variables except V , then obtain the following objective function:

Considering that U TU = I, we can rewrite the above objective function as:

then we have V = (X - E + 1µ λ1)U.

Update E

To update E, we fixed other variables except E and remove terms that are irrelevant to E. The the objective function becomes:

Let B = X - V U T + 1µ λ1, then E can be updated as:

Update Z

Optimizing eq. (7) with respect to Z yields the equation:

Then we obtain:

The above object function can be further decomposed to element-wise optimization problem as:

Therefore, the optimal solution of above problems is:

Update ALM Parameters

Finally we need to update the ALM parameters, i.e., λ1, λ2, and µ. According to [Boyd and Vandenberghe, 2004], they should be updated as following:

4 Experimental Analysis

In this section, we evaluate the performance of the proposed AMRMF method on ten real world benchmark datasets (Table 1). In detail, we firstly introduce the datasets and experimental settings, and then compare the proposed AMRMF with the state-of-the-art clustering algorithms and provide our observations. Finally, the convergence performance of the proposed AMRMF optimization is reported based on all the involved datasets.

The data clustering experiments are conducted on ten public available benchmark datasets, including five image datasets (Caltech101 Silhouettes, COIL20, MSRA25, PalmData25, and USPS) and five non-image datasets from the UCI machine learning repository (Control, Dermatology, Ecoli, Movement, and Seeds). For each dataset, the data is formatted as a feature matrix (i.e., input X of AMRMF algorithm) with the size of number of features and number of samples, and an additional ground truth vector with the size of number of samples. The statistics of the datasets used in the clustering experiments are summarized in Table 1. After the AMRMF algorithm has ended, the predicted label vector is obtained from the cluster indicator (i.e., output U of AMRMF algorithm), and then compared with the ground truth vector for quantitative evaluation.

The following two well accepted measurements have been used as metrics:

• Clustering accuracy (ACC), which discovers the one-toone relationship between clusters and classes:

where ri and li are predicted and ground truth label of sample xi, respectively, δ(x, y) is the delta function that equals 1 if x = y and equals 0 otherwise, and map(ri) is the permutation mapping function that maps each cluster ri to the equivalent label from the dataset.

• Normalized mutual information (NMI), which measures the the quality of clusters:

where ni denotes the number of data contained in the cluster Ci(1 ≤ i ≤ k), ˆnj is the number of data belonging to the Lj(1 ≤ j ≤ k), and ni,j denotes the number of data that are in the intersection between cluster Ci and class Lj .

In the our experiment, we compare the AMRMF algorithm with k-means, Normalized Cuts (NCuts) [Shi and Malik, 2000], low-rank representation (LRR) [Liu et al., 2013], least squares regression (LSR) [Lu et al., 2012], robust subspace segmentation (RSS) [Guo, 2015], and sparse subspace clustering (SSC) [Elhamifar and Vidal, 2013]. Among which, the k-means is executed by the Matlab R2015b statistical toolbox, while the codes of others are downloaded from the authors' webpages. To obtain the best possible performance of the compared methods, the detailed experimental settings are as follows.

For k-means and NCuts, we repeat the experiments ten times and report the average results with standard deviations. In particular, we tune the Gaussian kernel parameter in the range of 10[-5:5] for NCuts. For the released codes of LRR, LSR, RSS, and SSC, since the authors have fixed the detailed parameters in the last step of k-means clustering (e.g., initialization, distance measure and number of repeats), the algorithms output relatively stable results so we need not to average their results. In detail, for LRR, we have tried the two versions of LRR uploaded by the authors, with the λ ∈ [0.001, 0.01, 0.02, 0.05, 0.1, 0.2, 1, 2, 5], and report the best results. For LSR, we have also tested two implementations by the authors, with the λ ∈ 2[-5:5] to find the best performance. For RSS, we have tuned the three regularizer weights in the same range of 2[-3:3] , respectively, which is a much wider range than the author recommended. For SSC, the parameter spaces are α ∈ 10[-5:5] , ρ ∈ [1 : 5], respectively. Finally, for the proposed AMRMF algorithm, we have tuned the regularization parameters in the same range of 10[-5:5] . Note that our proposed AMRMF algorithm outputs stable result by the suggested optimization steps, therefore, we also need not to average the reported results.

Tables 2 and 3 summarize the clustering performance for each method on ten datasets. We can see that AMRMF algorithm outperforms other clustering methods in most of the cases. In particular, the Caltech101 Silhouettes is a large dataset which has rarely been considered for clustering experiment. The significant performance on all these datasets, especially the Caltech101 Silhouettes, meets the advantages of our proposed method. To emphasize, the superiority of AMRMF algorithm arises in the following aspects. Firstly, the objective function combines the matrix factorization and similarity learning into a single framework, by which an effective affinity matrix has been optimized and it could be further benefit for the clustering task. Besides, the introduced ℓ2,1-norm helps to alleviate the data noises and outliers issues that are common among other clustering methods, which brings positive effects into the proposed clustering model.

Also from the experimental results above, we have the following detailed observations.

The basic data clustering algorithms, i.e., k-means and NCuts, present poor clustering rates with large variations (in many times greater than 0.05 in ACC and 0.03 in NMI, respectively) on all the datasets. In detail, the k-means algorithm presents larger variations compares to NCuts on most of the datasets, which makes the clustering results impossible to be reproduced in practice. In fact, the NCuts could be viewed as the k-means clustering but in a new representation rather than the raw input data, since the clustering accuracies of NCuts always outperform the k-means as shown in table 2, we could know that it is crucial to seek a better feature representation (or data similarity).

The advanced algorithms, i.e., LRR, LSR, RSS and SSC, which could be understood as to learn a better affinity matrix for spectral clustering (or consider the learned affinity matrix itself as a better feature representation for clustering), usually show respectable improvements compare to the basic algorithms mentioned above. For those algorithms, we have also experimentally found that the variations on clustering accuracies have been greatly reduced even use the free k-means (without any parameter settings) for final clustering. However, it is also observed that for some datasets, the clustering accuracies are comparable or even lower than the basic algorithms, e.g., in the Caltech101 Silhouettes dataset, the mean ACC of NCuts reaches 0.5731 while the SSC only achieves 0.5637.

The proposed AMRMF algorithm arrives at the best ACCs for nine datasets (only failed on the dataset of Movement with less than 0.01 of ACC), and such results could be accurately reproduced, compared to the basic algorithms (k-means and NCuts, the results of which have large variations) and advanced algorithms (LRR, LSR, RSS and SSC, the results of which are relatively stable but actually the identical reproduction couldn't be guaranteed). Furthermore, the proposed AMRMF algorithm has obtained the best NMI on seven datasets (only failed on the datasets of Movement and PalmData25 with less than 0.01 and lower than RSS with 0.04 on the Caltech101 Silhouettes dataset. However, AMRMF leads its competitors around 0.1 for many times (e.g., the metric of ACC on the datasets of COIL20 and Ecoli), which confirms the superior performance of the proposed algorithm.

Finally, we would like to present the convergence performance of the proposed AMRMF optimization on the ten datasets, as illustrated in Figure 1. In each sub-figure, the transverse axis indicates the number of iterations from 1 to 100, while the longitudinal axis shows the error of objective function value in eq. (5) between iterations. It is clear that the AMRMF optimization often converges at stable values in less than ten iterations, which suggests that the proposed AMRMF optimization is very efficient in practice.

5 Conclusion

In this paper, we propose an adaptive manifold regularized matrix factorization (AMRMF) algorithm for joint learning the data affinity matrix and data clustering. The AMRMF is based on the idea of spectral clustering and low-rank matrix factorization. In order to overcome the point that the affinity matrix is always model based and may not optimal, i.e., computed by a predefined model with carefully tuned parameters combination, the proposed AMRMF aims to learn an affinity matrix jointly with the data clustering framework by considering it as an additional regularization. In this way, the learned affinity matrix could better guide the matrix factorization in a manifold point of view. Furthermore, the ℓ2,1norm is applied to the matrix factorization to obtain the robust solution against the noises and outliers. Experimental results on numerous of datasets demonstrate the superior performance of the proposed method in accuracy and stability perspectives. For future work, the proposed method could be further extended to its more generalized version, which could deal with the out-of-sample problem and be employed for big data clustering [Cai and Chen, 2015].

Acknowledgments

This work is supported by the National Natural Science Foundation of China under grants 61401317 and 61471274, the Australian Research Council Projects FT-130101457, DP140102164, and LP-150100671, and the Hong Kong Scholars Program and Hong Kong Government General Research Fund Scheme under grant 152202/14E.