Robust Auto-Weighted Multi-View Clustering

1 Introduction

With the advent of the Internet and big data era, it is very common for many real-world applications to deal with multiview data. The existence of such multi-view data raised the interest of multi-view learning [Xu et al., 2013; Sun, 2013; Tao et al., 2018]. To make full use of the information of multi-view data to improve clustering accuracy, multi-view clustering (MVC) has become an important research topic in the past two decades [Chao et al., 2017]. MVC is a machine learning paradigm to classify the similar subjects into the same group and dissimilar subjects into different groups by combining the available multi-view information, which indicates that MVC searches for the consistent clusterings across different view [Chao et al., 2017].

In the traditional multi-view data research [Hagen and Kahng, 1992; Blum and Mitchell, 1998], clustering is performed by building a weighted graph in which nodes correspond to data points and weights are related to the similarity between the points. The higher the similarity is, the greater the weight is, and vice versa. Each graph represents a view of the research object. Using the weighted graph, MVC can be solved with spectral clustering method [von Luxburg, 2007].

∗ Corresponding author.

There is a straightforward way to convert multi-view into a single view so that the spectral clustering method can be used for multi-view clustering. However, this simple method ignores the connection between each view and lacks corresponding theoretical support.

Some researchers also seek breakthroughs in other directions of clustering [Chang et al., 2016; Kang et al., 2017a; 2017b]. [Cai et al., 2011] proposed a multi-view spectral clustering model and [Kumar et al., 2011] introduced the coregularization technique into the spectral clustering model to perform clustering tasks. However, these methods are easily affected by the poor quality view. [Kumar et al., 2011; Li et al., 2015] approximated the weight of data nodes by combining prior knowledge. But this approach, due to the introduction of human intervention, is difficult to ensure that it still works when faced with big data tasks. In addition, in the face of specific clustering tasks, most researchers focus on spectral clustering to deal with it [Kumar et al., 2011; Xia et al., 2014; Li et al., 2015; Chang et al., 2015; Xue et al., 2017]. They tried to optimize and improved on the basis of spectral clustering in order to obtain better clustering performance. However, there is an obvious uncertainty in these improved methods based on spectral clustering, which requires post-processing (e.g., K-means) to eventually generate a labeling matrix.

Recently, [Nie et al., 2016] proposed a Constrained Laplacian Rank (CLR) method based on Laplacian matrix rank constraints. Combining two measurements, Frobenius norm and ℓ1-norm, this method solves MVC problem by minimizing the distance between the eventually learned similarity matrix and the similarity matrix of the various view. The adjacency matrix with just connected components is obtained by the minimum distance, and the number of connected components is exactly equal to the number of clustering in the original multi-view data. The adjacency matrix can be used directly to complete the clustering task. It can avoid the uncertainty caused by the post-processing of the traditional spectral clustering algorithm. However, the CLR method is only applicable to a single view clustering. How to obtain the explicit cluster structure with multiple noisy views has not been solved yet.

In this paper, we propose a novel Robust Auto-weighted Multi-view Clustering (RAMC) that aims to learn a consensus graph with exactly k connected components, where k is the number of clusters. In this way, the obtained graph can be directly used for clustering without the need of further postprocessing. To make sure the graph has exactly k connected components, we explicitly impose a low-rank constraint on the objective function. ℓl-norm has been employed in this paper for robustness. In addition, by solving each subproblem with an optimal solution through the alternating optimization steps, the proposed RAMC gives the concrete steps to solve the multi-view clustering. Furthermore, experiments are conducted on two synthetic datasets containing noise and three actual datasets, and the experimental results confirm the superiority of the proposed algorithm. The robustness performance of the proposed RAMC shows that as the ratio of random noise increases, although the performance of all the compared algorithms decreases, the performance gain of the proposed algorithm becomes more significant.

The contribution of this paper briefly summarized as follows:

• The proposed algorithm is able to learn a consensus graph with exactly k connected components (k is the number of clusters) by exploring the mutual information among multiple views. The obtained graph can be directly used for clustering without any further postprocessing.
• The proposed algorithm is robust to the outliers since we employ the ℓ1-norm. We have validated this in the later experiment.
• Since the algorithm is non-smooth and difficult to solve, we propose an efficient iterative method with guaranteed convergence to optimize it.
• We conduct extensive experiments to verify the performance of the proposed algorithm. The experimental results confirm its superiority compared to state-of-the-art alternatives.

Notation. In the whole article, every matrix is written in capital letters. In a matrix A, ai represents the i-th row, and aij represents the element corresponding to the i-th row and the j-th column. The trajectory is expressed as Tr(A). The matrix representation corresponding to the v-th view is written as A(v) . The ℓ1-norm of the matrix is expressed as ‖A‖1 . Especially, 1n is used to represent a n dimensional column vector, each of which is 1.

2 The ProposedMethodology

2.1 Graph-based Clustering Description

Suppose there are n samples which belong to c clusters, a Similarity Matrix (SM) is firstly constructed to represent the affinities of all the samples in the graph-based clustering methods. Many previous works have studied to design an SM with high quality, such as [Cai et al., 2005]. Later, [Nie et al., 2014; Chen and Dy, 2016; Nie et al., 2016] proposed an ideal SM S ∈ Rn×n , and introduced the CLR method [Nie et al.,

2016; 2017]. which is supposed to exactly have c connected components. So S can be directly used for the clustering task.

Based on the ℓ2-norm and the ℓ1-norm, between the given affinity matrix A and the learned similarity matrix S , Nie et al. defined the CLR for graph-based clustering [Nie et al., 2016]. Then they applied Frobenius norm and proposed the Parameter-weighted Multi-view Clustering (PwMC) [Nie et al., 2017]. However, Frobenius norm is sensitive to outliers and noise which exist in many real situations [Pang et al., 2010]. In order to reduce the negative effect of outliers and noise in graph-based clustering, Frobenius norm is replaced by ℓ1-norm. Then the target function can be written as

where S is a nonnegative matrix, and each row in S sums up to 1. C stands for the set of n by n square matrices with c connected components. Then based on ℓ1-norm and graph theory in [Fan, 1997], the connectivity constraint can be replaced with a rank constraint, problem (1) becomes

where LS is a Laplacian matrix, and LS = DS - (ST +S) 2 . rank(LS) is the rank of LS. The degree matrix DS ∈ Rn×n is defined as a diagonal matrix with i-th diagonal element ∑j (sij+sji) 2 . Now the target SM can be solved and be directly used for clustering.

2.2 Robust Auto-WeightedMulti-viewClustering (RAMC)

In this paper, a Robust Auto-weighted Multi-view Clustering (RAMC) is proposed to deal with the multi-view clustering problem. For multi-view data, m denotes the number of view and A(1) , A(2) , ..., A(m) denotes the corresponding input SMs, where A(v) ∈ Rn×n (1 ≤ v ≤ m). Assigning the same weight to each graph and calculating an average SM is a simple way to deal this problem. However, this method has an obvious disadvantage that it ignores the differences between different view and is easily disturbed by poor quality views, which ultimately leads to the insufficient precision of clustering. Co-training methods also have the similar disadvantage [Blum and Mitchell, 1998]. So an effective strategy to solve this problem is to use a group of meaningful weight to measure the importance of each view. Thus, the formulated objective becomes

To facilitate parameter adjustment, a regularization item is added to the problem (3). Thus, solving the problem (3) is equivalent to finding out the target SM S, which is constrained as in Eq. (3) but can approximate each original input SMA(v) . Then, the formulated objective becomes

where α = [α(1) , α(2) , ..., α(m) ]T and γ > 0. γ ‖α‖22 is used to smoothen the weight distribution. Obviously, If γ → 0, then the weight of best view will be 1 and other weights will be 0, so the trivial solution will be obtained. Conversely, if γ → ∞, then the equal weights will be obtained. Since solving the problem is based on the parameter γ and robust ℓ1-norm, so this method is named as Robust Auto-Weighted Multi-view Clustering (RAMC).

2.3 Optimization of RAMC

When the parameter γ is set to a proper value, the alternating iterative strategy is used to optimize the problem (4).

When α is fixed, the following subproblem needs to be solved

σi (LS) means the i-th smallest eigenvalue of LS. Because LS is a positive semidefinite matrix, so σi (LS) ≥ 0 . Given a λ which is large enough, so the rank constraint in Eq. (5) can be removed. Thus the problem (5) can be changed into the following form

Because λ is large enough, and σi (LS) > 0 for each i, so for the problem (6), the optimal solution S will let the second term c∑ i=1 σi(LS) equal to 0 and the constraint rank(LS) = n - c will be satisfied. Furthermore, according to Ky Fan's Theory [Fan, 1949], the following equation can be written

Then, utilizing Eq. (7), the problem (6) is changed into the following problem

This problem can be solved iteratively by optimizing variables F and S.

i. Solving F When S is fixed, the problem (8) can be written

Algorithm 1 The algorithm of Robust Auto-Weighted multiview Clustering (RAMC) in Eq. (4)

Input:

SMs for m views A(1) ,A(2) , ...,A(m) and A(v) ∈ Rn×n , number of clusters c, parameter γ. Initialize the weight for each view (e.g.,α(v) = 1m ). Let A = m∑ v=1 α(v)A(v) , and compute F ∈ Rn×c , which is formed by the c eigenvectors of LA = DA - AT +A 2 corresponding to the c smallest eigenvalues.

repeat

repeat

i. For each i , update the i-th row of S by solving the problem (15). where U (v) is a diagonal matrix with the j-th diagonal element as 1 2|˜ sij-aij| and pi =

ii. Update F, which is formed by the c eigenvectors 2 corresponding to the c smallest

‖fi - fj‖22 . of LS = DS - ST +S eigenvalues.

until converge

Update the weight α(v) by solving the problem (23). until converge Output: S ∈ Rn×n with exactly c connected components

and the view weight α.

By the c eigenvectors of LS corresponding to the c smallest eigenvalues, the optimal solution of F is well composed in this method.

1. Solving S When F is fixed. For fixed F, the problem (8) is as follows

Since for different i, the problem (10) is independent, then the following problem can be solved separately

The problem (11) can be changed into vector form as

where vi is a vector with the j-th element vij = ‖fi - fj‖22 . With the iterative reweighted way, the problem (12) can be solved by iteratively solving the following problem

where U (v) is a diagonal matrix with the j-th diagonal element u(v) jj = 1 2∣∣∣˜ sij-a(v) ij ∣∣∣ , and ˜ sij is the current solution. Nie et al have been proved that the iterative method decreases the objective of the problem (12) in each iteration and will converge to the optimal solution to the problem (12) .

The problem (13) becomes

For each i, let pi = m∑ v=1 α(v)U (v)a(v) i - λ2 vi, the following problem can be written

The Lagrangian function of problem (15) is

where η and βi are the Lagrangian multipliers, η ̸= 0 and βi ≥ 0. Let the derivative of Eq. (16) w.r.t. be zero, that is

For the j-th element of si, it then becomes

According to the KKT condition, then sijβij = 0. So from Eq. (18) there is

where (v)+ = max(0, v). The following function w.r.t. η is defined as

Based on Eqs. (19)-(20), and the constraint, si1n = 1, there is

Obviously, the root of a function gi(x) is the value of η. Because gi(x) is a piecewise linear and monotonically increasing function, so η can be easily calculated by Newton's method. After calculating η, the optimal solution to the problem (15) can be obtained by Eq. (19).

When S is fixed, the problem (4) is equivalent to minimization to the following problem:

where e(v) = ∥∥S - A(v)∥∥1 . Then the problem (22) becomes

The problem can be solved by a valid iterative algorithm which is put forward by [Duchi et al., 2008]. By solving the problem (23), α can be updated. Therefore, the solving process of the problem (4) can be summarized in Algorithm 1. According to [Nie et al., 2017], Algorithm 1 will converge, because each subproblem is obtained a optimal solution with the alternating optimization steps.

3 Experiments

In this section, some experiments are designed to verify the effectiveness of the proposed algorithm. Following the CLR

method, a graph is constructed for each view of the multiview datasets as the initial input matrix A(v) with k-nearest neighbor method. Only one parameter κ needs to be set in this method, here the κ represents the number of neighbor nodes. Too large and too small values of κ can lead to poor clustering results. Take the MSRCv1 data set as an example, when κ is set between 5 and 25, it is found that the purity and NMI increase as κ increases. When κ = 12, the Purity and NMI start to oscillate and don't obviously be improved with increasing the κ value and the Purity and NMI reach the optimal values when κ = 16. The κ values setting are similar on other data sets. In this paper, κ is fixed to 16. Two metrics are used to evaluate the clustering results, one is the standard clustering Purity, and the other is Normalized Mutual Information (NMI).

3.1 Toy Example

In this part, two toy experiments on the Toy-1 dataset and Toy-2 dataset are conducted to verify the effectiveness of RAMC algorithm. Toy-1 and Toy-2 datasets include two views respectively. Each view is made up of 90 × 90 matrix. There are three diagonally arranged block matrices in each view of the Toy-1 dataset and the Toy-2 dataset. The elements in the three-block matrices of each view are randomly set from 0 to 1. For the Toy-1 dataset, other data in each matrix are noise data, which is randomly set from 0 to e with e = 0.6 in the first view and e = 1 in the second view. For the Toy2 dataset, it has the same scale with the Toy-1 dataset while with different noise settings. With the initial noise e = 0.6 and e = 0.7 in view 1 and view 2, the input matrix for view 1 is obtained with e = 0.8 for the first and second block data, while the input matrix for view 2 is obtained with e = 1.0 for the second block and third data. Figure 1 and Figure 2 show the normalized original input graphs and the gray-scales of clustering results processed by the RAMC algorithm. Experimental results show that the RAMC algorithm can remove the noise successfully and get the pure block matrices. That is, the proposed algorithm shows the optimal clustering performance on multi-view data with noise.

3.2 Clustering Effects on Different Real Datasets

Following [Li et al., 2015], three widely used real-world multi-view datasets, MSRCv1 [Winn and Jojic, 2005], Caltech101 [Li et al., 2007] (following [Nie et al., 2017], two regular subsets Caltech101-7 and Caltech101-20 are used in our experiments) and Digits [Asuncion and Newman, 2007] are considered in the experiments. The summarization of these datasets is shown in Table 1. The proposed RAMC is compared with the methods: Co-regularized spectral clustering [Kumar et al., 2011] (Co-reg), Multi-View Spectral Clustering [Cai et al., 2011] (MVSC), Robust Multi-view Spectral Clustering [Xia et al., 2014] (RMSC), Parameterweighted Multi-view Clustering (PwMC) [Nie et al., 2017], Self-weighted Multi-view Clustering (SwMC) [Nie et al., 2017]. The result of CLR is also compared as a baseline in the experiment. The parameter in each compared method is set as optimum. In order to increase the generality of the proposed algorithm, α(v) for each view, is initialized to a random weight between 0 and 1, and all weights are normalized. For each compared method, we repeat the experiment 20 times on each dataset and report the average performance with the standard deviation (std).

Following [Nie et al., 2017], the clustering results of all the methods are shown in Table 2, and the best results are marked in boldface. According to the Table 2, the proposed RAMC achieves the best clustering purity and NMI on the three realworld datasets compared with other six methods.

It can also be seen that the standard deviation of clustering performance obtained by the RAMC method is quite small, which means that the proposed RAMC method has stable clustering performance. It's worth mentioning that the average clustering NMI of the proposed RAMC on the dataset Caltech101-20 is even 10 percentage points higher than the best performance on other approaches. And the clustering NMI is also improved on the Caltech 101-7 dataset.

For space limitation, only one random running result is shown in Figure 3. It can be seen that the solid lines show the clustering results with parameter γ searched in logarithmic form (logγ 10 ) from 0 to 5 with step size 0.5. In theory, the best clustering results would be obtained if all possible γ is searched. With an acceptable way, the step size is reduced from 0.5 to 0.1, thus the more accurate clustering results can be obtained. For clarity, the dotted line exhibits some clustering results near the optimal value with step size 0.1.

3.3 Robustness Performance Evaluation

To prove the robustness of the proposed algorithm, the following experiments are designed. First, a set of noisy dataset needs to be constructed based on an original dataset. Suppose r is the ratio of random noise, and n is the number of the original datasets, we randomly pick out n × r data points from the original dataset.The selected data is added to a normal distribution with an average of 300 and a standard deviation of 30, thus a set of the noisy dataset are formed with different r from 0 to 0.5 with a step size 0.05. For space limitation, we only take the MSRCv1 dataset as an example. To make the comparison more clear, we only compare with the second best and the third best algorithms. We use the clustering purity and NMI as evaluation metrics in this section. The experimental results are reported in Figure 4. From the experimental results, we have the following observation. Although as the ratio of random noise increases, the performance of all the compared algorithms decreases, the performance gain of the proposed algorithm becomes more significant. For example, compared with PwMC, the performance gain of RAMC on Purity increases from 0.59% to 67.00% when the ratio of random noise increases from 0 to 0.5. Meanwhile, compared with PwMC, the performance gain of RAMC on NMI increases from 1.22% to 498.55% when the ratio of random

(b) NMI

Figure 4: We conduct experiments to test the robustness of the proposed algorithm. From the experimental results, we can see that as the noisy percentage increases, the performance gain of the proposed algorithm becomes more significant.

noise increases from 0 to 0.5. This phenomenon confirms the robustness of the proposed algorithm.

4 Conclusion and FutureWork

In this paper, we have proposed a novel Robust AutoWeighted multi-view Clustering (RAMC) that aims to learn a consensus graph with exactly k connected components, where k is the number of clusters. The structure of the obtained graph makes it suitable to be directly used for clustering without any further post-processing. To make sure the graph has exactly k connected components, we explicitly impose a low-rank constraint on the objective function and ℓlnorm has been employed in this paper for robustness. With the extensive experiments, the proposed method shows the superiority and robustness on two synthetic datasets and three real-world datasets. In future work, this framework will be extended to semi-supervised context.

Acknowledgments

This research was supported by the National Natural Science Foundation of China (No. 61602379) and International cooperation and exchange program of Shaanxi Province (No. 2016KW-034).