Simultaneous Representation Learning and Clustering for Incomplete Multi-view Data

1 Introduction

Conventional multi-view learning assumes that each example of data appears in all views [Jing et al., 2017; Tao et al., 2017; Nie et al., 2016a; Karasuyama and Mamitsuka, 2013; Sun, 2013; Hou et al., 2010]. However, in real-world applications, it is often the case that every view suffers from some data missing, which results in incomplete multi-view data. For example, in cross-language document clustering, documents have been translated into different languages representing multiple views. However, not all documents are translated into each language. Another example is web image retrieval. Not all web images are associated with text descriptions and the image itself may be inaccessible due to deletion or invalid url. Such incompleteness makes it impossible to apply conventional methods on these data directly. Therefore, how to efficiently manipulate this kind of incomplete multi-view data becomes a practical and important problem.

∗Contact Author

Since clustering is a basic and common task, a few clustering methods have recently been proposed for incomplete multi-view data. As a pioneering work, [Li et al., 2014] learns the representations of view-specific examples and complete examples simultaneously, thus in the learned latent subspace, all examples are homogeneously represented. Such strategy has also been adopted by [Yin et al., 2015; Zhao et al., 2016; Yin et al., 2017; Cai et al., 2018; Zhao et al., 2018]. The limitation of this strategy is that it requires each data sample appears in all views or only one view. A more general case for a multi-view data with more than two views is that each data sample is present on any number of views. To deal with this case, another strategy has been used by [Xu et al., 2015; Hu and Chen, 2018; Tao et al., 2018]. By introducing weight matrices which distinguish present and missing instances on each view, these methods factorize data matrices of different views into a common latent subspace, and then perform postprocessing on the common representation matrix to obtain the clustering results. Their performance can be further improved due to the following reasons: (1) Since these methods are based on Matrix Factorization (MF), they are essentially linear, and thus cannot well disclose non-linear structure hidden in data, which limits their learning ability. (2) The manner of separately performing representation learning and clustering may not be able to jointly obtain the optimal solution.

In this paper, we propose Simultaneous Representation Learning and Clustering (SRLC) to address the aforementioned issues. Specifically, to utilize the non-linear information, on each view, SRLC constructs a similarity matrix to measure the relationships of present instances. And based on these matrices, SRLC incorporates representation learning and clustering by learning low-dimensional representations of present instances and a common probability label matrix simultaneously. To enhance the reasonability of the model, rotation matrices are introduced to deliver clustering information, and class coding vectors are employed to establish a weight mechanism. The mechanism characterizes the contribution of each sample according to its clustering uncertainty, which improve the robustness of SRLC. An iterative optimization algorithm for SRLC with proved convergence is proposed. The effectiveness of SRLC is demonstrated by comparing with state-of-the-art methods on six datasets.

2 Notations and Problem Setting

Throughout the paper, matrices and vectors are written as boldface uppercase letters and boldface lowercase letters, respectively. For a matrix M, its i-th row and ij-th element are denoted by mi and mij, respectively. The transpose, the trace and Frobenius norm of matrix M are denoted by MT , tr(M) and ||M||F , respectively. For a vector mi, the 2-norm of mi is denoted by ||mi||.

Given a dataset {xi|i = 1, ..., n} with n samples sampled from V views, where xi is the i-th sample. Each sample has V representations, i.e., xi = [x(1) i , ..., x(V ) i ] ∈ R1×d , where x(v) i ∈ R1×d(v) is the i-th example on the v-th view and d = ∑Vv=1 d(v) . The dataset can be denoted in a matrix form X = [X1 , ...,XV ] ∈ Rn×d , where X(v) = [x(v) 1 ; ...; xVn ] ∈ Rn×d(v) collects the instances of the V -th view.

In the incomplete multi-view setting, each x(v) i can be missing. For each view, a diagonal indicator matrix O(v) ∈ {0, 1}n×n is defined as:

Incomplete multi-view clustering aims to cluster the n samples into C clusters by integrating all incomplete views.

3 Proposed Approach

In this section, we first present the motivation of this paper. Next, we introduce our model in two aspects and then give an unified objective function. Finally, an efficient iterative algorithm is presented for optimization.

3.1 Motivation

Most existing incomplete multi-view clustering methods are based on matrix factorization. There are mainly two separate steps of these methods:

Step 1. Factorizing each X(v) into a common latent feature matrix V ∈ Rn×C and a basis matrix U(v) ∈ RC×d(v) simultaneously by solving the following problem:

where Ψ(V, U(v) ) is the regularization term on V and U(v) , and C1 and C (v) 2 are constraint sets. These methods distinguish each other by employing different constraints or regularization terms on V and U(v) .

Step 2. Applying a post-processing algorithm such as Kmeans on V to obtain the clustering indicators.

Although the incomplete multi-view data can be clustered by applying these two steps, the performance of these methods can be further improved due to the following reasons: (1) the learned unified representation matrix V may be of low quality if the relations between V and {X(v) }Vv=1 are nonlinear; (2) successively and independently performing two steps are not guaranteed to yield globally optimal solution.

3.2 Partial Spectral Embedding

To disclose the non-linear structure and utilize the complementary information of different views, we construct an undirected weighted graph S(v) ∈ Rn×n on each view according to pairwise similarity of {x(v) i }ni=1 . Since some instances can be missing, s(v) ij is calculated by

where f(x(v) i , x(v) j ) is a similarity calculation method such as [Zelnik-Manor and Perona, 2004; Nie et al., 2016b], and Θ denotes the information of s(v) ij is missing. According to Eq. (3), s(v) ij can be estimated only if both x(v) i and x(v) j are present. To eliminate the influence of Θ in subsequent calculating, for convenience, we define Θ · 0 = 0 · Θ = 0.

Based on S(v) , we aim to learn a low-dimensional representation matrix F(v) = [f (v) 1 ; ...; f (v) n ] ∈ Rn×C which contains the clustering information of X(v) . Since the information of S(v) can be partial, the i-th row f (v) i of F(v) can be computed only if x(v) i is present, i.e., o(v) ii = 1. As a result, the optimization problem can be written as

where IC ∈ RC×C is the identity matrix. According to Eq. (4), if o(v) ii = 0, the elements of f (v) i can be assigned with arbitrary values.

3.3 Probability Spectral Rotation

To incorporate clustering into representation learning and facilitate consensus, we learn a common probability label matrix Y = [y1; ...; yn] ∈ Rn×C together with {F(v) }Vv=1 .

To establish reasonable interactions between Y and {F(v) }Vv=1 , for each F(v) , a rotation matrix R(v) ∈ RC×C is employed to extract the clustering information, and C coding vectors {t(c)}Cc=1 are introduced to identify the C classes. For the c-th coding vector t(c) ∈ R1×C , only its c-th element is equal to 1 and the other ones are 0 (c = 1, ...,C). The probability spectral rotation term is formulated as:

where γ ≥ 1 is an adaptive parameter. From Eq. (5), it can be observed that f (v) i affects Y and R(v) only if o(v) ii = 1. Different from the classical procrustes average technique [Hastie et al., 2010] which rotates fixed {F(v) }Vv=1 to form a unified binary indicator matrix, Eq. (5) generates a probability matrix Y according to the rotation loss of {f (v) i }i,v to

{t(c)}Cc=1 . Thus, each sample can be weighted by Eq. (5) automatically according to the degree of clustering uncertainty ∑Cc=1 (yic)γ , which enables clearly clustered samples to play more important roles in the learning stage.

3.4 Unified Objective Function

By combining Eq. (4) and Eq. (5), we propose our SRLC model as follows:

where λ > 0 is a balanced-parameter that controls the tradeoff between the aforementioned two objectives. With the increase of λ, SRLC learns {F(v) }Vv=1 more based on Y to utilize more consensus information. With the decrease λ, SRLC learns {F(v) }Vv=1 more based on {S(v) }Vv=1 to utilize more complementarity information.

3.5 Optimization

The problem (6) is not convex over all three groups of variables {R(v) }Vv=1 , {F(v) }Vv=1 ,Y, simultaneously. To solve this problem, we adopt alternating minimization strategy.

Update R(v) . With Y and {F(v) }Vv=1 fixed, for each R(v) , we need to solve the following problem

To update R(v) , we introduce the following propositions.

Proposition 1. The minimum problem (7) is equivalent to

The detailed proofs of all propositions of this paper can be found in the supplementary material.

Proposition 2. Denote (F(v) )T O(v)GasM(v) . Suppose the SVD of M(v) is M(v) = U(v)Σ(v) (V(v) )T , then the optimal solution R(v) to the problem (7) is

Update F(v) . With {R(v) }Vv=1 and Y fixed, for each R(v) , we need to solve the following problem

By analyzing Eq. (10), it can be observed that f (v) i needs to be optimized only if o(v) ii = 1. Suppose ∑ni=1 o(v) ii = n(v) data points appears on the v-th view, the corresponding rows of F(v) and G are collected by F(v) Ω ∈ Rn(v)×C and G(v) Ω ∈ Rn(v)×C , respectively. S(v) Ω ∈ Rn(v)×n(v) collects the elements f(x(v) i , x(v) j ) of S(v) . To optimize F(v) Ω , according to Proposition 1, the problem (10) can be transformed into the following matrix form

where L(v) Ω is the Laplacianmatrix of S(v) Ω . Since the problem (11) is difficult to solve directly, we consider the following relaxed problem:

where A(v) = α(v) I - L(v) Ω and B(v) = G(v) Ω (R(v) )T /λ. α(v) is an arbitrary constant which ensures that A(v) is a positive definite matrix. Motivated by [Nie et al., 2017], the problem (12) can be solved by the following iteration strategy:

2. Update F(v) Ω with fixed C(v) . According to Proposition 2, suppose the SVD of C(v) is C(v) = U(v)Σ(v) (V(v) )T , then F(v) Ω is updated by

After obtaining the F(v) Ω , F(v) can be updated accordingly. The solution procedure of (12) is listed in Algorithm 1.

Algorithm 1 Algorithm to solve the problem (12)

Input: The matrices F(v) Ω , L(v) Ω , G(v) Ω and R(v) , the parameters λ and α(v) , the maximum number of iteration T1.

Output: F(v) Ω . Initialization:

1. Calculate A(v) = α(v) I - L(v) Ω .
2. Compute B(v) = G(v) Ω (R(v) )T /λ.

while not converged and number of iteration< T1 do 1: Update C(v) = A(v)F(v) Ω +B(v)

• 2: Calculate the SVD of C(v) = U(v)Σ(v) (V(v) )T
• 3: Update F(v) Ω =U(v) (V(v) )T . end while

Update Y. With {F(v) }Vv=1 and {R(v) }Vv=1 fixed, each row yi can be updated by solving the following problem:

Denote qic = ∑Vv=1 o(v) ii ||t(c) - f (v) i R(v) ||2 , which is the (i, c)-th element of matrix Q ∈ Rn×C . When γ = 1, the optimal solution of (14) is

where < · > is 1 if the argument is true or 0 otherwise.

When γ > 1, the Lagrangian function of the problem (14) is Lµ = ∑Cc=1 (yic)γ qic - µ(∑Cc=1 yic - 1), where µ is the Lagrange multiplier. Setting the derivative of Lµ with respect to yic to zero and combining the constraint ∑Cc=1 yic = 1, we arrive at the closed-form solution of the problem (14):

Since the proposed (6) is solved in an alternative way, we initialize F(v) and Y such that (F(v) )T O(v)F(v) = IC and Y ∈ Ind, where Ind is a set of binary clustering indicator matrices. Additionally, α(v) can be calculated by power method [Nie et al., 2017]. At last, we resort to a decision function to assign the single class label for each yi,

In summary, the procedure of SRLC is listed in Algorithm 2.

Algorithm 2 Optimization of SRLC

Input: The data matrices {X(v) }Vv=1 , the indicator matrices {O(v) }Vv=1 , hyper-parameters λ and γ, the maximum number of iteration T2.

Output: The discrete indicator matrix Y with Eq. (17). Initialization:

1. Construct similarity matrices {S(v) }Vv=1 with Eq. (3).
2. Initialize F(v) such that (F(v) )T O(v)F(v) = IC.
3. Initialize Y ∈ Ind.
4. Compute α(v) such that α(v) I-L(v) Ω is positive definite. while not converged and number of iteration< T2 do 1: Update R(v) with Eq. (9), ∀v ∈ [1, V ].
5. 2: Update F(v) Ω of F(v) according to Alg. 1, ∀v ∈ [1, V ].
6. 3: Update Y with Eq. (15) or (16).
7. end while

4 Theoretical Analysis

In this section, we provide the convergence guarantee and computational complexity analysis of Algorithm 2.

4.1 Convergence Guarantee

In this subsection, we first present the convergence proof of Algorithm 1 based on [Nie et al., 2017]. Next, we prove that Algorithm 2 converges to a stationary point of Eq. (6).

Proposition 3. The objective function (12) is monotonically increased with Algorithm 1.

Proposition 4. Algorithm 2 decreases the objective value of (6) in each iteration monotonically until it converges to a stationary point.

4.2 Computational Complexity

In the following, we analyze the computational complexity of SRLC. In the initialization, the construction of {S(v) Ω }Vv=1 costs O(∑v (n(v) )2d(v) ). In each iteration, SRLC has three alternating steps. To update {R(v) }Vv=1 , since (F(v) )T O(v)G = (F(v) Ω )T G(v) Ω , we need O(∑v n(v)C 2 ) for matrix multiplication and O(C 3V ) for SVD. To update Y, we pay O(∑v n(v)C 2 ) to compute Q and O(nC) to calculate Y. To update {F(v) Ω }Vv=1 of {F(v) }Vv=1 , the computational complexity of the proposed Algorithm 1 is O(∑v n(v)C 2 t1+ ∑v (n(v) )2Ct1), where t1 is the number of iteration of Algorithm 1. Overall, since V ≪ n(v) and C ≪ n(v) , the computational complexity of SRLC is O(∑v (n(v) )2 (d(v) +t1t2C)), where t2 is the number of iteration of Algorithm 2.

5 Experiment

In this section, we conduct experiments to verify the proposed SRLC. Firstly, we compare SRLC with five state-of-the-art methods on partial multi-view clustering task. Then we study the impact of hyper-parameters and finally present the results about convergence behavior.

5.1 Experiments Setup

The experiments are conducted on six real-world datasets: Microsoft Research Cambridge Volume 1 (MSRC) 1 , Caltech7 2 , Handwritten digits (Dights) 3 , ORL 4 , Yale 5 , WebKB 6 . A detailed summarization of these datasets is in Table 1.

Since all these datasets are originally complete, to mimic the incomplete multi-view setting, we randomly remove some examples from each sample. Concretely, for each x(v) i , there is a probability to remove it. In the experiments, the probability is tuned form 10% to 50% with a step 10%. And for each sample xi, we ensure that it has at least one x(v) i remaining. The probability can also be regarded as the partial example ratio (PER) of the dataset.

In the experiments, we compare the proposed SRLC with several state-of-the-art methods: Partial multi-View Clustering (PVC) [Li et al., 2014], Incomplete Multi-modality Grouping (IMG) [Zhao et al., 2016], Multiple Incomplete views Clustering (MIC) [Shao et al., 2015], Multiview Learning with Incomplete Views (MLIV) [Xu et al., 2015], and Doubly Aligned Incomplete Multi-view Clustering (DAIMC) [Hu and Chen, 2018]. Since the original PVC and IMG can only deal with two incomplete views, we extend them according to Eq. (2), so that the extended versions can be applied on multi-view data with any number of incomplete views. All hyper-parameters of the compared methods are determined by grid-search.

1 https://www.microsoft.com/en-us/research/project/.

2 http://www.vision.caltech.edu/Image Datasets/Caltech101/.

3 http://archive.ics.uci.edu/ml/datasets/Multiple+Features.

4 http://www.cad.zju.edu.cn/home/dengcai/Data/FaceData.html.

5 http://vision.ucsd.edu/content/yale-face-database.

6 http://www.cs.cmu.edu/afs/cs/project/theo-11/www/wwkb/.

Since all the compared methods except SRLC need postprocessing to extract the clustering indicators, we apply Kmeans [Ding et al., 2005] on the unified representation matrices of these methods to obtain the clustering the results. To make fair comparison, K-means and our proposed SRLC share the same stable initialization clustering indicator matrix which is calculated according to [Xu et al., 2016].

The clustering results are evaluated by two metrics, the adjusted rand index (AdjRI) and the normalized mutual information (NMI). On each dataset, we repeat 10 independent times to create incomplete multi-view data for each PER, and the average performance is reported.

5.2 Clustering Results

Figure 1 and Table 2 report the AdjRI and NMI results on six data sets with different partial example ratios, respectively. From these figures and table, we have the following observations. (1) With the increase of PER, in terms of both AdjRI and NMI, the performance of all the compared methods becomes worse in most cases, which is consistent with intuition. (2) On datasets MSRC, Caltech7 and Dights, as the PER increases, the performance of MIC is degenerated fast than the performance of other methods. The possible reason is that MIC simply fills the missing instances with the global feature average, which may lead to a deviation when PER is large. (3) Each of the MF-based methods achieves good performance on certain datasets, but performs worse on other datasets. The possible reason is that they adopt different regularization terms or constraints, which makes them good at grouping certain kind of data and poor at clustering the others. (4) The proposed SRLC consistently outperforms the other compared methods over all datasets as the PER varies from 10% to 50%. This may be because SRLC incorporates representation learning and clustering, and is capable to explore the non-linear information hidden in the data.

5.3 Hyper-parameter Study

The proposed SRLC has two hyper-parameters {λ, γ}. λ is tuned in the range of {101 , 101.5 , 102 , 102.5 , 103 } while γ is tuned in the range of {1.1, 1.3, 1.5, 1.7, 1.9}. The experiments are conducted on datasets MSRC-v1 and Caltech7 with PER=30%. As shown in Figure 2(a) and Figure 2(b), SRLC achieves acceptable with different combinations of {λ, γ}. However, how to identify the optimal parameters is data dependent. Two datasets have different optimal parameters because their data characteristics are different.

5.4 Convergence Study

To verify the convergence property of the proposed SRLC, we conduct experiments on datasets MSRC and Caltech7 with PER=30% and set the hyper-parameters {λ, γ} as {102 , 1.1} respectively. In Figure 2(c) and Figure 2(d), the blue curves show the objective function value of (6) and the red dashed lines presents the NMI of SRLC in each iteration. It can be NMI

Figure 2: Parameter and convergence studies of SRLC.

observed that as the iteration round increases, the objective function value decreases fast and the performance increases rapidly, indicating SRLC has fast convergence propety.

6 Conclusion

In this paper, we propose a spectral-based method to deal with incomplete multi-view problem by incorporating representation learning and clustering. Based on the similarity matrices independently constructed on each view, the proposed SRLC algorithm learns a common probability label matrix together with low-dimensional representations of present instances, which enables SRLC to utilize non-linear information and facilitates the optimization procedure to meet the demand of clustering. Experimental results on six datasets validate the effectiveness of SRLC. In the future, we will study how to extend SRLC to the semi-supervised classification task.

Acknowledgements

This work was supported by the National Natural Science Foundation of China (No. 61473302, 61503396), and the NSF for Distinguished Young Scholars of Hunan Province under Grant 2019JJ20020.