CDIMC-net: Cognitive Deep Incomplete Multi-view Clustering Network

1 Introduction

Multi-view clustering is a well-known research topic in fields of machine learning [Chao et al., 2017; Zhang et al., 2018]. Generally speaking, almost all of the previous researches on multi-view clustering are based on the assumption that all views of samples are available and strictly aligned. However, in practical applications, more and more collected multiview data are incomplete where some views are unavailable. For example, many volunteers only have one or two kinds of examination results of magnetic resonance imaging, positron emission tomography, and cerebrospinal fluid for Alzheimer's disease diagnosing [Xiang et al., 2013]. Multi-view data with missing views are called incomplete multi-view data and clustering on such data is the so-called incomplete multi-view clustering (IMC) [Wen et al., 2019; Hu and Chen, 2018]. Obviously, conventional methods fail to handle these incomplete multi-view data. In addition, owing to the missing views, it is difficult to explore the complementary and consistent information from the incomplete multi-view data, which makes IMC a very challenging task.

∗ corresponding author, '†' indicates co-first authors.

For IMC, Trivedi et al. [Trivedi et al., 2010] proposed a kernel canonical correlation analysis (KCCA) based method, which recovers the kernel matrix of the incomplete view according to that of the complete view. However, it can only handle the two-view data and requires that one view is complete. To address this issue, Li et al. proposed the partial multi-view clustering (PMVC) based on matrix factorization, where the paired views are decomposed into the same representation [Li et al., 2014]. Then various extensions of PMVC, such as graph regularized PMVC (GPMVC) [Rai et al., 2016] and incomplete multi-modal grouping (IMG) [Zhao et al., 2016] have been proposed, which mainly incorporate the graph embedding technique to enhance the separability of the common representation. In [Zhao et al., 2018], the graph embedding and deep feature extraction techniques are simultaneously integrated into PMVC to preserve the local structure and capture the high-level features. Partial multi-view clustering via consistent GAN (PMVC GAN) unifies the Autoencoder and cycle generative adversarial network (GAN) into a novel IMC framework, which can infer the missing views via GAN and in turn promotes the common representation learning [Wang et al., 2018]. However, the above methods are not applicable to arbitrary incomplete cases where some incomplete samples have more than one views or no samples have complete views [Wen et al., 2020]. To address the issue, weighted matrix factorization technique is introduced for IMC, where the representative works are multiple incomplete views clustering (MIC) [Shao et al., 2015], doubly aligned IMC (DAIMC) [Hu and Chen, 2018], one-pass IMC (OPIMC) [Hu and Chen, 2019], and online multi-view clustering (OMVC) [Shao et al., 2016]. Besides these methods, many graph learning based methods [Wang et al., 2019; Wen et al., 2020] and multiple kernels based methods (such as incomplete multiple kernel k-means with mutual kernel completion (MKKM-IK-MKC) [Liu et al., 2019]) have also been proposed to handle the arbitrary IMC cases.

Although the aforementioned methods provide some schemes to address the IMC problem, these methods still suffer from the following issues: 1) most of the previous methods exploit the shallow models to obtain the common representation, which cannot capture the high-level features from the complex multi-view data. Although some deep network based methods like PMVC GAN can capture the high-level features, it is inflexible to handle all kinds of incomplete cases. 2) None of them considers the negative effect of marginal samples since these methods treat all samples equally. This is unreasonable because those marginal samples are generally far away from the cluster centers and can be viewed as outliers, which are harmful to model training [Guo et al., 2019]. In this paper, we propose a novel cognitive based deep incomplete multi-view clustering network, referred to as CDIMCnet, to address the above issues. CDIMC-net integrates several view-specific deep encoders, a self-paced kmeans clustering layer, and multiple graph constraints into a unified network for arbitrary IMC. Representatively, the main contributions of our work are illustrated as follows:

1) We propose a novel and flexible deep clustering network for arbitrary IMC cases, which incorporates the graph embedding to promote the network training.

2) This is the first work that introduces the human cognitive based learning into IMC. Compared with the existing works, CDIMC-net can adaptively reduce the negative influence of the marginal samples, and thus is more robust to outliers.

2 Kmeans Clustering

Kmeans is one of the most famous clustering algorithms. For any data X = [x1, . . . , xn] ∈ Rm×n with n samples and m features, kmeans seeks to find k optimal cluster centers U = [u1, . . . , uk] ∈ Rm×k and cluster indicator S ∈ {0, 1}k×n by solving the following problem [Nie et al., 2019]:

where Sj,i = 1 denotes that the corresponding i-th sample xi is partitioned into the j-th cluster. 1 is a vector with all elements as 1.

3 The ProposedMethod

3.1 Problem Statement

For the given incomplete multi-view data with l views, we use X(v) = [x(v) 1 , . . . , x(v) n ] ∈ Rmv×n to represent the instance set of the v-th view, where mv is the feature dimension, n denotes the number of samples, and elements of the missing instances are denoted as 'NaN' (i.e., not a number). The view available and missing information is recorded in a diagonal matrix W (v) for the v-th view, where W (v) i,i = 1 if the i-th instane is available in the v-th view, otherwise W (v) i,j = 0. The goal of IMC is to group these n samples into k clusters.

3.2 CDIMC-net

As shown in Fig.1, CDIMC-net groups the incomplete multiview data via two phases: pre-training and fine-tuning, where an Autoencoder based pre-training phase is used to initialize the network parameters and the fine-tuning phase aims at obtaining the cluster-friendly representations while producing the cluster indicators for all input samples.

Pre-training Network

In our work, based on the conventional under-complete Autoencoder [Guo et al., 2017; Xie et al., 2016], we develop a graph regularized incomplete multi-view Autoencoder for incomplete multi-view cases, where the graph embedding technique is introduced to preserve the local structure of data and a weighted fusion layer is introduced to eliminate the negative influence of missing views. Specifically, the proposed incomplete multi-view Autoencoder is composed of the following three components.

View-specific encoders and decoders: As the basic Autoencoder, encoder network captures the most salient features from the high-dimensional data and the decoder network aims at recovering the data from the encoded features [Guo et al., 2017]. Considering that different views may have different dimensions, information, structures, and appearances, we design several view-specific encoders {f (v) EC }l v=1 and corresponding decoders {f (v) DC }l v=1 for different views.

Fusion layer: As mentioned in many references, all views share the common semantic information for the same sample, such as the common representation or cluster label [Zhao et al., 2018; Hu and Chen, 2019]. Inspired by this, CDIMCnet seeks to obtain the common representation shared by all views for clustering. Specifically, a simple weighted fusion layer is introduced for such goal as follows:

where h(v) i is the output of instance x(v) i at the v-th encoder f (v) EC . h∗i is the common representation for the i-th sample.

As shown in Fig.1, the fusion layer is placed between the encoding network and the decoding network. Introducing the weighted fusion layer can solve the issue of incomplete learning by reducing the negative influence of missing views.

Graph embedding: In fields of subspace learning, a recognized manifold assumption is that if two data points xi and xj are close to each other, then their corresponding low dimensional representations should also be close in the latent subspace [Cai et al., 2008; Kang et al., 2017; Wen et al., 2018a]. To preserve such neighbor relationships, the following graph embedding constraint is considered:

where N (v) ∈ Rn×n denotes the nearest neighbor graph constructed from instance set X(v) as follows:

where ψ(x(v) i ) denotes the nearest instance set to x(v) i .

Loss function of pre-training: Combining the graph embedding loss and Autoencoder loss, the overall loss function of the pre-training network is designed as:

where ¯X(v) = f (v) DC (f (v) EC (X(v))) denotes the reconstructed data of the v-th view, Ω1 and Ω2 denote the parameters of encoder network and decoder network, respectively. α is a positive hyper-parameter.

Fine-tuning and Clustering

By optimizing problem (5), we can obtain a more compact common representation H∗ for the incomplete multiview data and the initialized network parameters. However, it cannot guarantee the obtained common representation to be cluster-friendly. In many previous deep clustering works, kmeans is widely considered [Yang et al., 2017; Guo et al., 2018]. However, as can be seen from objective function (1), the conventional kmeans treats all samples including the cluster-oriented samples and marginal samples (outliers) equally, which makes the trained clustering network be sensitive to outliers. A good approach to address this issue is to select the most cluster-oriented samples for model fine-tuning [Guo et al., 2019]. To this end, we introduce a self-paced kmeans as the clustering layer for fine-tuning.

Self-paced kmeans: The loss function of the self-paced kmeans is denoted as follows [Guo et al., 2019]:

where U and S are the cluster center matrix and cluster indicator matrix as in (1). A difference between the self-paced kmeans and the conventional kmeans is that the cluster centers U is fixed in self-paced approach. This operation can avoid the trivial solution: all samples are trained into a same point in the latent space. r = [r1, . . . , rn] ∈ Rn is a weight vector, λ is an age parameter.

Generally, parameter λ needs to increase gradually such that more samples can be selected for network training. However, it is difficult to control its growth rate for different tasks. In our work, we adopt a statistic based adaptive approach following [Guo et al., 2019] to update parameter λ:

where Klosst is a loss vector at the t-th training step and is calculated as: Klossti = ∥∥h∗t i -U tSt :,i∥∥22 for the i-th sample. µ (Klosst ) and σ (Klosst ) denote the average and standard deviation of vector Klosst , respectively. T is the maximum training iterations.

By introducing the weight vector v and parameter λ, the proposed CDIMC-net can select the most confident samples whose clustering losses are no more than λ for training. Then with the iteration increases, more confident samples will be selected. This process is similar to the human cognitive learning, i.e., learns from easy to hard or less to more.

Loss function of fine-tuning: Combining the losses of kmeans and graph embedding, the overall loss function of the fine-tuning network is:

At the end of fine-tuning, CDIMC-net will produce the clustering result S for the incomplete multi-view data.

3.3 Optimization

Similar to conventional Autoencoer, all parameters of the pretraining network can be directly optimized by the Stochastic Gradient Descent (SGD) algorithm and back-propagation. Thus, in this section, we focus on the optimization of the finetuning network, where an alternating optimization algorithm is adopted to optimize loss function (8).

Step 1: Update the encoder parameters Ω1: The optimization problem for encoder parameters Ω1 is:

Problem (9) can be adaptively optimized via SGD and back-propagation.

Step 2: Update cluster indicator S: S is updated by solving the following problem:

The optimal solution to problem (10) is:

Step 3: Update r: The optimization problem to variable r is degraded as follows by fixing the other variables:

Supposing Klossi = ‖h∗i -US:,i‖22 , the optimal solution to problem (12) can be expressed as follows:

Step 4: Update λ: λ is updated via (7).

By alternatively updating the above variables, the proposed CDIMC-net can converge to the local optimal solution.

3.4 Implementation for IMC

It should be noted that deep learning commonly groups the given data into several subsets and then feeds these subsets Algorithm 1: Fine-tuning and clustering of CDIMC-net Input: Arranged incomplete multi-view data

{Y (v)}lv=1 , indicator matrix { ¯W (v)}lv=1 , and graphs {N (v)}lv=1 ; parameter α; Maximum iterations: T; Maximum iterations for inner loop: Maxiter; Batch size: bs; Stopping threshold: ξ. Output: Clustering indicator S. 1 Initialization: Feed {Y (v)}lv=1 , { ¯W (v)}lv=1 , and {N (v)}lv=1 into the pre-trained network to obtain the consensus representation H∗ , and then implement kmeans on it to obtain the initialized cluster center matrix U and cluster indicator matrix S. Set all elements of r as 1. 2 for t ∈ {1, 2, . . . , T} do 3 for j ∈ {1, 2, . . . ,Maxiter} do 4 Update the network parameters by optimizing (9) batch to batch; 5 Update cluster indicator S using (11); 6 Update weight vector r using (13); 7 Update step-parameter λ using (7); 8 if 1 - 1n ∑i,j St i,j St-1 i,j < ξ then 9 Stop training; 10 return S.

batch by batch for model training. However, for our method, it is difficult to sufficiently utilize the local geometric information of graphs N (v) via the conventional batch-to-batch training approach. To solve this issue, we propose a simple approach to explore such local information as much as possible. Based on the assumption that samples from the same cluster are more likely to have connections marked by edge value '1', we propose to reorder the given samples {X(v)}l v=1 first according to the initialized clustering result obtained by performing kmeans on the features stacked by all views and then construct the nearest neighbor graphs {N (v)}l v=1 from the reordered data, followed by feeding the batch of samples one by one for network training. In this way, every sub-block {N (v) batch}l v=1 corresponding to the selected batch of samples {X(v) batch}l v=1 will carry dense nearest neighbor information as much as possible such that more local information can be utilized. Specifically, the detail implementation steps of our

CDIMC-net for IMC are presented as follows:

Step 1: Data rearrangement and nearest neighbor graph construction: 1) Concatenating all views into one single view, where the missing instances denoted by 'NaN' are filled in the average instance of the corresponding view; 2) Performing kmeans on the stacked view; 3) Reorder data according to the clustering result, where samples grouped into the same cluster are placed together; 4) Construct the nearest neighbor graph according to (4) from the reordered data. The rearranged data is denoted by {Y (v)}l v=1 , the corresponding nearest neighbor graph and view indicator matrix are denoted by {N (v)}l v=1 and { ¯W (v)}l v=1 , respectively.

Step 2: Network pre-training: Exploit the rearranged data, graphs, and indicator matrices to train the IMC Autoencoder network, where all features of the missing views are set as 0. For each batch, we exploit SGD to optimize the

selected batch of data, ¯ Y (v) batch and H(v) batch are the corresponding reconstructed data and feature representation, ¯W (v) batch and LN (v) batch are the sub-indicator matrix and Laplacian matrix of the v-th graph corresponding to the batch of data, bs denotes the batch size.

Step 3: Network fine-tuning: The detailed fine-tuning steps are summarized in Algorithm 1.

4 Experiment

4.1 Experimental Settings

Databases: Three databases listed in Table 1 are adopted. 1) Handwritten [Asuncion and Newman, 2007]: It contains five views and 2000 samples from ten numerals (i.e., 09), where the five views are obtained by Fourier coefficients, profile correlations, Karhunen-Love coefficient, Zernike moments, and pixel average extractors. 2) Berkeley Drosophila Genome Project gene expression pattern database (BDGP): BDGP is composed of 5 categories and 2500 samples, where each class has 500 samples [Cai et al., 2012]. Each sample is represented by four views, i.e., texture feature and three kinds of visual features extracted from the lateral, dorsal, and ventral images. 3) MNIST [LeCun, 1998]. Following [Wang et al., 2018], we evaluate CDIMC-net on the same subset of the MNIST database, which is composed of 4000 samples and ten digits. Pixel feature and edge feature are extracted as two views.

Compared methods: Compared methods include: PMVC, IMG, MIC, OMVC, DAIMC, OPIMC, IMC with graph regularized matrix factorization (IMC GRMF) [Wen et al., 2018b], MKKM-IK-MKC, and PMVC CGAN. Besides, two baseline methods, i.e., best single view (BSV) [Zhao et al., 2016] and Concat [Zhao et al., 2016] are also evaluated, where BSV reports the results of the best view, and Concat implements the kmeans on the stacked features of all views. For CDIMC-net, the encoder and decoder networks are stacked by four full connected layers with size of [0.8mv, 0.8mv, 1500, k] and [k, 1500, 0.8mv, 0.8mv], respectively. The activation function is 'ReLU' and the optimizer is 'SGD' for the pre-training network and 'ADAM' for the fine-tuning network. CDIMC-net is implemented on PyTorch and Ubuntu Linux 16.04.

Incomplete data construction: For the data with more than two views, we randomly remove p% (p ∈ {10, 30, 50, 70}) instances from every view under the condition that all samples at least have one view. For MNIST database, p% (p ∈ {10, 30, 50, 70}) instances are randomly selected as paired samples whose views are complete, and the remaining samples are treated as single view samples, where half of them only have the first view and the other half of the samples only have the second view.

Evaluation metric: Clustering accuracy (ACC) and normalized mutual information (NMI) [Hu and Chen, 2018].

4.2 Experimental Results and Analysis

Experimental results on the above three databases are listed in Tables 2. We can observe the following points from the results: 1) CDIMC-net significantly outperforms the other methods on the three databases. For instance, on the Handwritten database with a missing-view rate of 50%, CDIMCnet obtains about 91% ACC and 84% NMI, which are about 10% and 16% higher than those of the second best method, respectively. 2) BSV and Concat obtain worse IMC performance than the other methods in most cases. Thus, we can conclude that exploring the complementary information and consistent information of multiple views is beneficial to improve the performance. 3) CDIMC-net performs better than the advanced deep network based method PMVC CGAN on the MNIST database. This demonstrates that CDIMC-net is superior to PMVC CGAN for IMC.

4.3 Parameter Analysis

Fig.2 shows the relationships of ACC, graph embedding hyper-parameter α, and the learning rate of the CDIMC-net on the Handwritten and BDGP databases with a missing-view rate of 10%. We can observe that CDIMC-net obtains relatively better performance when the two parameters are small. Specifically, a large learning rate is harmful to obtain the local optimal clustering results and a large α makes the graph embedding term dominate the training phase. In the applications, we suggest selecting the learning rate and α from [1e-5,1e-3].

4.4 Component Analysis

In this subsection, we conduct experiments on the Handwritten and BDGP databases to validate the importance of graph embedding, self-paced learning, and pre-training, where the degenerate models of CDIMC-net without a graph embedding term, self-pace constraint, and pre-training phase, are compared. From Fig.3, we can find that CDIMC-net outperforms the three degenerate models, which demonstrates the effectiveness of the introduced three approaches.

4.5 Convergence Analysis

Fig.4 shows the loss value of fine-tuning network versus the iterations on the Handwritten and BDGP databases with a missing-view rate of 10%. From the figures, we can observe that the loss value shows a downward trend overall and decreases quickly in the first few steps. This validates the convergence property of the proposed method.

5 Conclusion

In this paper, we proposed a novel and flexible CDIMC-net, which can handle all kinds of incomplete data. Based on human cognitive learning, CDIMC-net introduces the selfpaced kmeans to improve the robustness to outliers. Besides this, it incorporates the graph embedding technique to preserve the local structure of data. The superior performance of CDIMC-net are validated on several incomplete cases with the comparison of many state-of-the-art IMC methods.

Acknowledgements

This work is partially supported by Shenzhen Fundamental Research Fund under Grant no. JCYJ20190806142416685, Guangdong Basic and Applied Basic Research Foundation under Grant nos. 2019A1515110582 & 2019A1515110475, Establishment of Key Laboratory of Shenzhen Science and Technology Innovation Committee under Grant no. ZDSYS20190902093015527, University of Macau (File no. MYRG2019-00006-FST), National Natural Science Foundation of China under Grant nos. 61702110 & 61702163, and National Postdoctoral Program for Innovative Talent under Grant no. BX20190100.