Self-Representative Manifold Concept Factorization with Adaptive Neighbors for Clustering

1 Introduction

Data clustering is an important and significant research topic which has been widely studied in various applications, such as image segmentation [Shi and Malik, 2000], document analysis [Hammouda and Kamel, 2004] [Cai et al., 2011], gene selection [Jiang et al., 2004] and so on. It aims to partition a dataset into different groups based on similarities among data points such that the data points which share high similarities are assigned into the same group while the dissimilar data points are in different groups. In the past decades, a number of clustering algorithms have been proposed, including K-means [Hartigan and Wong, 1979], spectral clustering [von Luxburg, 2007] [Liu et al., 2015], subspace clustering [Vidal, 2011] [Wang and Xu, 2016], and matrix-factorizationbased algorithms [Wang and Zhang, 2013] [Hong et al., 2016], etc.

∗Corresponding author.

Among the above methods, the matrix-factorization-(MF)- based methods have become popular in recent few years. Given a data matrix X, the basic goal of MF is to find two or more low-rank matrix factors whose product provides a good approximation to the original matrix X. For the MF-based clustering, one of the matrix factors can be considered as an ensemble of cluster prototypes that reveals the potential semantic structure, while the other matrix factor can be referred as the coefficient matrix that indicates the clustering results, which meets the psychological and physiological interpretation of part-based representation in human brain. Therefore, in real-world applications, the dimensionality of the decomposed matrix factors is set to the number of clusters, which is usually much smaller than that of the original one. This fact gives rise to compact representation of the data points, which can facilitate other learning tasks such as clustering and classification. The most representative algorithms of MF include Nonnegative Matrix Factorization (NMF) [Lee and Seung, 2001], Concept Factorization (CF) [Xu and Gong, 2004] [Cai et al., 2011], Principal Component Analysis (PCA) and so on.

In particular, the NMF is different from the other matrixfactorization-based approaches since it enforces a constraint that all the elements of the matrix factors should be equal or greater than zero. One of the major advantages of NMF over other methods is that the inherent data nonnegativity is preserved by the NMF method, as a result of constraints that produce nonnegative lower rank factors. These factors can be interpreted as semantic features or patterns in the collection of data. Thus, data with common features can be viewed as a cluster [Shahnaz et al., 2006]. In NMF, the clustering result can be easily obtained. Previous works have proved that NMF is superior to other MF-based methods in document clustering [Xu et al., 2003] [Shahnaz et al., 2006] and image clustering [Kim and Park, 2008]. However, there are two major limitations of NMF. First, it is still unclear how to optimally perform clustering tasks by NMF method on the data with negative inputs. Second, only original feature of the data points is applied to NMF for clustering so that the data to be clustered cannot be analyzed in a more compact and discriminative feature space to further improve the clustering performance.

The CF method is an important variant of NMF in which each cluster is regarded as a linear combination of the data points and at the same time each data point is also expressed as a linear combination of these cluster centers. Given a matrix X, it is decomposed into three matrices, i.e., W, V and X itself, among which the W and V are nonnegative, which satisfies that X ≈ XWV T . The major advantage of CF over NMF is that the clustering task can be performed by CF model in any feature space, including data with negative numbers and any transformed data spaces, e.g., the reproducing kernel Hilbert space, thus rendering the CF method a more general clustering method [Cai et al., 2011] [Xu and Gong, 2004] [Pei et al., 2016].

However, the aforementioned CF, like NMF, does not inherently explore the geometric structure of the data, which is important for clustering. Therefore, some geometry-based extensions have been proposed. Cai [Cai et al., 2011] incorporates a manifold regularizer with CF to address the underlying concepts which are consistent with the intrinsic manifold structure to facilitate subsequent process, such as clustering. Pei [Pei et al., 2016] extends the standard CF by utilizing a sophisticated method to learn the affinity matrix by adaptively assigning the neighbors for each data point for document clustering. However, most of these works share at least one of the following drawbacks. First, the model of the affinity matrix used in the graph regularizer is predefined (e.g., the Graph Laplacian), which means the clustering results may be sensitive to the selected model. Second, the affinity matrix is constructed on the raw data to a large extent, which is unable to well reveal the global manifold structure of data.

Alternatively, inspired by the successful way to exploit the self-representation of data in which the original data is regarded as a dictionary [Guo, 2015] [Du et al., 2016], we consider CF as an improved self-representation matrix factorization method with a learning-based dictionary to efficiently reveal the global structure of original data. More importantly, since the linear coefficients of CF carry clear semantic meanings, which indicate they contain plentiful information of the cluster label for each data point [Xu and Gong, 2004]. Thus, the coefficients of CF model can be extracted to construct the affinity matrix to relieve the disadvantage brought by using the raw data. In our proposed model, we construct the affinity matrix with adaptive neighbors based on the renewable coefficient matrix and learn a sparse data representation simultaneously. In detail, several aspects of our model which worth to be highlighted are as follows.

1. The proposed algorithm is a general framework that can combine the power of CF model with two kinds of graph regularizers which contain comprehensive and complementary structure information.
2. The proposed affinity matrix of the manifold structure is constructed by adaptively assigning its nearest neighbors, so that the clustering results are not sensitive to the input data matrix. At the same time, a self-representation of original data is learned to better construct the affinity matrix.
3. A graph regularizer based on the original data is added to better reveal the local structure information in the original data and learn a sparse clustering indicator matrix simultane-

ously. As the weight matrices of the graphs are highly sparse, an efficient multiplicative update rule is proposed to solve the proposed optimization.

The remainder of this paper is organized as follows: The derivation of our algorithm is described in section 2. After that, the optimization algorithm is proposed in section 3. The experimental results are represented in section 4, followed by the conclusion section.

2 The ProposedMethod

In this section, we describe our proposed algorithm which extends the standard CF model with the consideration of two different manifold structures. In detail, the affinity matrix of first manifold structure is constructed by adaptively assigning its nearest neighbors in each iteration based on the renewable self-representation of the raw data. The other graph regularizer is based on original data to complementally reveal the local structure information of original data and learn the cluster indicator matrix simultaneously. We will describe each part of the objective function in the following subsections.

2.1 Graph Regularizer

In the CF model X ≈ XWV T , the j-th row of matrix V , i.e., vT j = [vj1, vj2, · · · , vjn], can be regarded as a new representation of each data point with the new basis. Therefore, some constraints can be added on matrix V to exploit the geometric structure of the data, which is beneficial for the subsequent clustering task. A natural assumption needs to be mentioned that if two data points xi, xj are close in the intrinsic geometry of the data distribution, then their representations in the new basis should be also close to each other [Cai et al., 2011] [Pei et al., 2016]. This assumption plays an important role in developing various kinds of algorithms, such as spectral clustering and spectral-based dimensionality reduction algorithms.

Before defining the introduced graph regularizer, let us construct the edge weight matrix S first. Previous studies have showed that the nearest-neighbor graph on data points can effectively model the local geometric structure. Therefore, we consider a graph with n vertices where each vertex belongs to a concept. The weight matrix S is then defined as follows:

where Np(xi) denotes the set of p-nearest neighbors of xi. Then the graph regularizer can be defined to measure the smoothness of the low-dimensional representations on the pnearest neighbor graph by [Belkin and Niyogi, 2002] [Belkin and Niyogi, 2003]:

where tr(·) denotes the trace of a matrix. L = D - S is a graph Laplacian[Chung, 1997], where S is the graph weight matrix and D is a diagonal matrix whose entries are column sums of S.

The graph regularization R can well reveal the local intrinsic structure contained in the original data and learn a sparse cluster indicator matrix at the same time. Although there are a few drawbacks in this manifold structure and we will solve them in the next subsection, we still incorporate it into our final objective function for the purpose of obtaining better cluster indicator matrix and the local structure information hidden in the original data.

2.2 Adaptive Neighbor Structure based on Self Representation

In the above subsection, the graph weight matrix (or affinity matrix) S is predefined, which means that it may be sensitive to the input raw data. In the literature, there are many approaches to construct the affinity matrix to solve this problem [Guo, 2015]. Recently, a new idea has been proposed to learn the affinity matrix by adaptively assigning neighbors for each data point based on the local connectivity [Nie et al., 2014]. To be complete, we first introduce how to assign probabilistic neighbors in this method. For simplicity, the Euclidean distance is used as the distance measurement.

For the i-th data point xi, the Aij can be used to denote the probability of any of the data point xj ∈ [x1, x2, · · · , xn] (excluding itself) being connected to xi as a neighbor. In general, a smaller distance between two points xi and xj indicates a larger probability Aij. So the probability Aij|nj=1 can be determined by solving the following problem:

where Ai ∈ Rn×1 is a vector with the j-th element as Aij. The constraints ATi 1 = 1 and 0 ≤ Ai ≤ 1 are introduced to guarantee the probability property of Ai.

However, there is a problem in eq. (3) that it has a trivial solution, which means only the nearest data point can be defined as the neighbor of xi with the probability 1, while all the other data points can not be the neighbors of xi. Alternatively, if we solve the following problem without taking into consideration any distance information in the data:

The ideal solution is that all the data points can be neighbors of xi with the same probability 1n .

By integrating eq. (3) and eq. (4), we have the following optimization problem:

where γ is a positive trade-off parameter to control the second term.

However, there is still a drawback in this method that the affinity matrix is constructed on the raw data, which is unable to well reveal the global subspace structure of data[Guo, 2015]. To solve this problem, we can naturally recall the assumption mentioned before that if two data points xi, xj are close in the intrinsic geometry of the data distribution, then the representations of these two data points in the new basis should also be close to each other[Cai et al., 2011] [Pei et al., 2016]. Therefore, we decide to employ a new representation, rather than the raw data, to construct the affinity matrix.

Meanwhile, inspired by the successful way to exploit the self-representation of data in which the original data itself is regarded as a dictionary [Guo, 2015] [Du et al., 2016], we observe that CF model can be considered as an improved selfrepresentation matrix factorization method with a learningbased dictionary to efficiently reveal the global structure of original data. More importantly, the linear coefficients of CF carry clear semantic meanings, which indicates they contain plentiful information of the cluster label for each data point[Xu and Gong, 2004]. Therefore, the CF model can be rewritten in the following form:

where R = WV T denotes the coefficient matrix based on the dictionary of the original data matrix, which is a meaningful representation of the original data points.

Hence, by incorporating the self-representation with the adaptive neighbor structure, we have the following problem for each data point:

For each data point xi, we can use eq. (7) to assign its neighbors. Therefore, we can solve the following problem to assign the neighbors for all the data points:

With slight algebraic transformation, it gives the following formulation:min

where LA is the Laplacian matrix of A, which is constructed in the way of DA - A. The degree matrix DA is defined as a diagonal matrix in which its i-th diagonal element is ∑nj=1 Aij .

2.3 The Objective Function

Finally, by integrating the adaptive neighbor structure and manifold regularizers into the original CF model, we have the overall objective function of our proposed algorithm as follows:

where X ∈ Rm×n denotes the original data matrix, m is the feature dimension, and n is the number of data points. W ∈ Rn×r and V ∈ Rn×r are the decomposed matrix factors. A ∈ Rn×n is the affinity matrix which we have learned in an adaptive approach with the new data representation. λ1, λ2, and λ3 are three nonnegative regularization parameters.

3 Optimization Algorithm

The objective function in eq. (10) is not convex with both W and V . Therefore, it is difficult to reach the global optimization. However, the objective function is convex if we update the variables alternatively. Thus, we introduce an iterative algorithm which can achieve a local minimum as follows.

3.1 UpdateWand Vwith fixed A

Define K = XT X, then the objective function can be reformed as follows:

Let ψjk, φjk be the Lagrangian multiplier for constraints wjk ≥ 0 and vjk ≥ 0, respectively, and Ψ = [ψik], Φ = [φik]. Since variable A is fixed here, we don't consider the Lagrangian multipliers here for the constraints ∀i ATi 1 = 1, Ai ≥ 0. Then the Lagrangian function L of O is:

The partial derivatives of L with respect to W and V are:

Using the KKT conditions ψjkwjk = 0 and φjkvjk = 0, we get the following equations for wjk and vjk:

Let LA = DA -A and L = D-S, then the equations can lead to the following updating rules:

Regarding these updating rules, we have following theorem:

Theorem1. The objective functionO in eq. (10) is nonincreasing under the update rules in eq. (17) and eq. (18). The objective function is invariant under these updates if and only if W and V are at a stationary point.

Theorem 1 guarantees the convergence of W and V in eq. (17) and eq. (18). Meanwhile, A has a closed-form solution. So the final solution will be a local optimum. The proof of Theorem 1 is omitted because of the size limitation.

3.2 Update Awith fixedWand V

The update of A can be done via solving the following optimization problem:

Note that:

Then the problem becomes:

To simplify the procedure, denote γ = 2λ3 λ1 . Note that the problem (21) is independent between different i, which means we can solve the following problem individually for each i. So the problem reduces to:

Denote dij = ‖(WV T )i - (WV T )j‖22 and denote di ∈ Rn×1 as a vector with the j-th element as dij, then the problem can be written in the vector form as:

For each i, the Lagrangian function is:

where η and βi ≥ 0 are the Lagrangian Multipliers.

According to the KKT conditions, it can be verified that the optimal solution Ai should be:

To have a sparse similarity A, we have:

where k is the number of the nearest neighbors.

We could set γi to be:

The overall γ could be set to the mean of γ1, γ2, . . . , γn, which is:

3.3 Extension to Negative DataMatrices

The updating rules we introduced in the above section only take effect when the K is nonnegative. However, it is possible that the K contains negative entries. So in this section, we will present a more general algorithm to handle any case. Following [Xu and Gong, 2004], the algorithm is based on the theorem proposed by Sha [Sha et al., 2007], which is stated as follows.

Theorem 2. Define the nonnegative general quadratic form as:

where v is an m-dimensional nonnegative vector, A is a symmetric positive definite matrix and b is an arbitrary mdimensional vector. Let A+ and A- denote the nonnegative matrices with elements:

It is easy to see that A = A+-A-. Then, we can obtain the solution v that minimizes f(v) through the following iterative updating:

The Theorem 2 can naturally be applied because the objective function O is a quadratic form of W (or V ). We need to identify the corresponding A and b in the objective function.

Fixing V , the part b can be attained by taking the first order derivative with respect to W at W = 0:

The part A for the quadratic form O(W) can be obtained by taking the second order derivative with respect to W:

where

Let K+ and K- denote the nonnegative matrices with elements:

where we have K = K+ - K-. Substituting A and bi using eq. (30) and eq. (31), we get the multiplicative updating equation for each element wjk of W:

where P + = K+WV T V + λ1WV T DAV and P - = K-WV T V + λ1WV T AV .

Similarly, we can get the updating equation for each element vjk in V as following:

where Q+ = VW T K+W + λ1DAVW T W + λ2DV and Q- = V W T K-W + λ1AV W T W + λ2SV .

4 Experimental Results

In this section, we evaluate the performance of our proposed method on some datasets to show the effectiveness of our algorithm. We compare our method with some exist algorithms including the K-means, CF [Xu and Gong, 2004], NMF [Lee and Seung, 2001], SMCE [Elhamifar and Vidal, 2011], SSC [Elhamifar and Vidal, 2013], and Normalized Cuts (Ncut) [Shi and Malik, 2000]. For all the clustering methods, the number of clusters is known as input.

Datasets. There are in total six datasets used in our experiments, all from the UCI Machine Learning Repository. Table 2 summarizes the characteristics of the datasets used in our experiments. All the datasets are nonnegative.

Evaluation Metrics. Following [Xu et al., 2003] [Huang et al., 2014], we adopt three widely used evaluation metrics to quantitatively measure the clustering performance of our algorithm, i.e. Clustering Accuracy, Normalized Mutual Information and Purity.

Parameters Setting. To compare these methods fairly, we run them with some selected parameter combinations and report the best result for comparison.

For K-means, NMF, CF and Ncut, we run them for 10 times and calculate both of the mean and standard deviation. The experimental results of SMCE, SSC and our method are relatively stable. So there is no need to average them. Thus, they are only run for 1 time. During the experiments, we set the cluster number and dimension of reduced data representation equal to the number of ground truth classes for all datasets and methods. For Ncut and our method, we construct the predefined Laplacian matrices by 0-1 weight based on the Euclidean distances between each data point. Also, the neighbor size of these fixed Laplacian matrices is set to be 5 for simplicity. For the Laplacian matrix in the adaptive neighbor structure in our model, the neighbor size is set by searching in the range of {c - 1, c, c + 1, c + 2, c + 3, c + 4}, where c is the cluster number. For our method, the regularization parameters λ1 and λ2 are set by searching from {10-5 , 10-4 , · · · , 104 , 105 }. Since the regularization parameter λ3 can update automatically in each iteration based on the value of λ1 and γ, we just initialize it empirically. We have also initialized the W and V by PCAN [Nie et al., 2014]. For SSC and SMCE, we use the codes provided by their authors with the recommended parameters to achieve a good performance. Note that there is no parameter selection required for the K-means, NMF and CF, since the number of clusters is given.

Clustering Results. Table 1 shows the clustering results on six datasets in terms of accuracy, NMI and purity, respectively. In the table, we can see that regardless of the dataset, our proposed model always achieve the best clustering performance in terms of all the measurements. In addition, we can find some other detailed points:

1. For three matrix-factorization-based methods (NMF, CF, our model), our model achieves a significant improvement over both CF and NMF, which confirms that our model has a better ability to capture the intrinsic geometrical structure of the original data by considering a self-representative manifold regularizer with an adaptive neighbor structure.

2. Although some methods like SMCE have built a similarity graph to explore the data manifold, our model construct a better similarity matrix based on self-representation and employ an adaptive way to assign neighbors so that achieves better performance.

3. The clustering performance of our method on datasets which are of high dimensionality, such as Chess, Vote, is extremely better than other algorithms, especially in the measurement of NMI, which indicates our model can effectively handle the clustering problem of high dimensional data comparing with other methods. In these tables, we can observe that most methods produce low NMI, less than 1%, on the data set Chess. One possible reason is that the data in Chess is both high dimensional and diverse, which renders it difficult for clustering. Nevertheless, our method still has a relative higher NMI, 2.03% comparing with other methods.

For datasets containing categorical attributes, such as Zoo and Vote, our method also presents a great advantage over other methods in all the three measurements. One possible reason may be that the two kinds of manifold structures in our algorithm can better extract comprehensive information of the original data, no matter it is numerical, categorical or mixed.

5 Conclusion

In this paper, we propose a novel graph regularized concept factorization model with adaptive neighbor structure for data clustering. Different from other graph regularized clustering methods, our model constructs the affinity matrix by adaptively assigning closest neighbors for each data point. The manifold regularization term based on a learned affinity matrix can better consider the intrinsic geometric structure of data. Besides, the distances between each point used to build the affinity matrix are calculated based on a sparse selfrepresentation of the original data. Therefore, the clustering result is not sensitive to the input data. An efficient multiplicative update rule is proposed to optimize the problem. Experimental results on several benchmark datasets show that our algorithm outperforms many state-of-art clustering methods. In the further research, we may extend our current algorithm to be implemented more effectively to address the task of big data clustering.

Acknowledgments

This paper is supported in part by the National Natural Science Foundation of China under grants U1536204, 61771349, 61711530239, and in part by the MQNS Grant No. 9201701203 and the MQ Enterprise Partnership Scheme Pilot Res Grant No. 9201701455.