Multi-View Multiple Clustering

1 Introduction

The goal of clustering is to partition samples into disjoint groups to facilitate the discovery of hidden patterns in the data. Traditional clustering algorithms are designed for singleview data. With the diffusion of the internet of things and of big data, samples can be easily collected from different sources, or observed from different views. For example, a video can be characterized using image signals and audio signals, and a given news can be reported in different languages. Objects with diverse feature views are typically called multiview data. It's recognized that the integration of information contained in multiple views can achieve consolidated data clustering [Chao et al., 2017]. Many multi-view clustering methods have been developed to extract comprehensive information from multiple feature views; examples are co-training based [Kumar and Daum´e, 2011], multiple kernel learning [G¨onen and Alpaydın, 2011], and subspace learning based [Cao et al., 2015; Luo et al., 2018]. However, the aforementioned clustering methods typically provide a single clustering, which may fail to reveal the high-quality and diverse alternative clusterings of the same data.

Figure 1 shows a collection of objects represented by a texture view and a color view. We can group the objects based on their shared shapes. By leveraging the commonality and the individuality of these multi-view objects, we can obtain two alternative clusterings (texture+shape and color+shape), as shown at the bottom of the figure. From this example, we can see that multi-view data include not only the commonality information for generating high-quality clustering (as multi-view clustering does), but also the individual (or specific) information for generating diverse clusterings (as multiple clustering aims to achieve).

To explore different clusterings of the given data, multiple clustering has emerged as a new branch of clustering in recent years. Some approaches seek diverse clusterings in alternative to those already explored, by enforcing the new ones to be different [Bae and Bailey, 2006; Davidson and Qi, 2008; Yang and Zhang, 2017]; other solutions simultaneously seek multiple clusterings by reducing their correlation [Caruana et al., 2006; Jain et al., 2008; Dang and Bailey, 2010; Wang et al., 2018], or by seeking orthogonal (or independent) subspaces and clusterings therein [Niu et al., 2010; Ye et al., 2016; Mautz et al., 2018; Wang et al., 2019]. However, these multiple clustering methods are designed for single-view data.

Based on the discussed example in Figure 1, we leverage the individuality and the commonality of multi-view data to generate high-quality and diverse clusterings, and we propose an approach called multi-view multiple clustering (MVMC) to achieve this goal. To the best of our knowledge, MVMC is the first attempt to encompass both multiple clusterings and multi-view clustering, where the former focuses on generating diverse clusterings from a single data view, and the latter focuses on a single consensus clustering by summarizing the information from different views. MVMC first extends multiview self-representation learning [Luo et al., 2018] to explore the individuality information encoding matrices and the commonality information matrix shared across views. To obtain more credible commonality information from multiple views, we force the commonality information matrix to be smooth across all views. In addition, we use the Hilbert-Schmidt Independence Criterion (HISC) [Gretton et al., 2005] to enhance the individuality between matrices, and consequently increase the diversity between clusterings. We then use matrix factorization to jointly factorize each individuality matrix (for diversity) and the commonality matrix (for quality) into a clustering indicator matrix and a basis matrix. To simultaneously seek the individual and common data matrices, and diverse clusterings therein, we use an alternating optimization technique to solve the unified objective. In addition, we extend multiple co-clustering [Tokuda et al., 2017; Wang et al., 2018] to the multi-view scenario, and term the extended approach as multi-view multiple co-clustering (MVMCC).

The main contributions of our work are as follows:

• We study how to generate multiple clusterings from multi-view data, which is an interesting and challenging problem, but largely overlooked. The problem we address is different from existing multi-view clustering, which generates a single clustering from multiple views, and also different from multiple clustering, which produces alternative clusterings from single-view data.
• We introduce a unified objective function to simultaneously seek multiple individuality information encoding matrices, and the commonality information encoding matrix. This unified function can leverage the individuality to generate diverse clusterings, and the commonality to boost the quality of the generated clusterings. We further adopt an alternative procedure to optimize the unified objective.
• Extensive experimental results show that MVMC (MVMCC) performs considerably better than existing multiple clustering (co-clustering) algorithms [Cui et al., 2007; Niu et al., 2010; Ye et al., 2016; Yang and Zhang, 2017; Tokuda et al., 2017; Wang et al., 2018] in exploring multiple clusterings and co-clusterings.

2 The ProposedMethods

2.1 Multi-ViewMultiple Clustering

Suppose Xv ∈ Rdv×n denotes the feature data matrix of the v-th view, for n objects in the dv dimensional space. v ∈ {1, 2, · · · ,m}, where m is the number of views.

We aim to generate h (provided by the user) different clusterings from {Xv }mv=1 using the shared and individual information embedded in the data matrices. As an application example, one can group the same 'customers' (represented by different feature views) from the perspective of purchase capability, loyalty (leave or stay), and fraud (yes or no). Most multi-view clustering approaches in essence focus on the shared and complementary information of multiple data views to generate a consolidated clustering [Chao et al., 2017]. By viewing each subspace as a feature view, an intuitive solution to explore multiple clusterings on multiview data is to first concatenate different feature views, and then apply subspace-based multiple clustering methods on the concatenated feature vectors [Niu et al., 2010; Ye et al., 2016; Wang et al., 2019].

To find high-quality and diverse multiple clusterings, we should make concrete use of the individuality and commonality of multi-view data. The individuality helps to explore diverse clusterings, while the commonality coordinates the diverse clusterings to capture the common knowledge of multiview data. To explore the individuality and commonality of multi-view data, we extend the multi-view self-representation learning [Cao et al., 2015; Luo et al., 2018] as follows:

where U ∈ Rn×n is specified to encode the commonality of the data matrices {Xv }mv=1 , and Dk ∈ Rn×n is used to encode the individuality of the k-th (k ∈ {1, 2, , · · · , h}) group of views. Φ1({Dk }hk=1 ) and Φ2(U) (defined later) are two constraints used to enhance the individuality and commonality. The multi-view self-representation learning in [Cao et al., 2015; Luo et al., 2018] requires h = m. In contrast, Eq. (1) does not have this requirement. As a result, the group-wise individuality and diversity are jointly considered, and the number of alternative clusterings can be adjusted by the user. The assumption for the linear representation in Eq. (1) is that a data sample can be expressed as a linear combination of other samples in the subspace. This assumption is widely-used in sparse representation [Wright et al., 2010] and low-rank representation learning [Liu et al., 2013].

[Luo et al., 2018] recently combined U and {Dk }mk=1 into an integrated co-association matrix of samples, and then applied spectral clustering to seek a consistent clustering. Their empirical study shows that the individual information encoded by Dk helps producing a robust clustering. However, since Xv and Xv′ (v′ ̸= v) describe the same objects using different types of features, the matrix Dk resulting from Eq. (1) may still have a large information overlap with Dk′ . As a result, the expected individuality of Dk and Dk′ cannot be guaranteed. This information overlapping is not necessarily an issue for multi-view clustering, which aims at finding a single clustering, but it is for our problem, where multiple clusterings of both high-quality and diversity are expected.

To enhance the diversity between the individuality encoding (representation) matrices {Dk }hk=1 , we approximately quantify the diversity based on the dependency between these matrices. The smaller the dependency between data matrices is, the larger their diversity is, since the matrices are less correlated. Various measurements can be used to evaluate the dependence between variables. Here, we adopt the Hilbert-Schmidt Independence Criterion (HSIC) [Gretton et al., 2005], for its simplicity, solid theoretical foundation, and capability in measuring both linear and nonlinear dependence between variables. HSIC computes the squared norm of the cross-covariance operator over Dk and Dk′ in Hilbert Space to estimate the dependency. The empirical HISC does not have to explicitly compute the joint distribution of Dk and Dk′ . It is given by:

where Kk ,Kk′ ,H ∈ Rn×n , Kk , and Kk′ are used to measure the kernel induced similarity between the matrices Dk and Dk′ respectively. H = δij - 1/n, δij = 1 if i = j, δij = 0 otherwise. In this paper, we adopt the inner product kernel to specify Kk = (Dk )T Dk , ∀k ∈ {1, 2, · · · , h}. Then, we minimize the overall HISC on h individuality matrices to reduce their redundancy, and specify Φ1(Dk ) as follows:

Inspired by subspace-based multi-view learning [Gao et al., 2015; Chao et al., 2017] and manifold regularization [Belkin et al., 2006], we specify Φ2(U) in Eq. (1) to collect more shared information from multiple data views as follows:

where Wv ij is the feature similarity between xvi and xvj . To compute Wv , we simply adopt an ϵ = 5 nearest neighborhood graph, and use the Gaussian heat kernel (with kernel width set to the standard deviation of the distance between samples) to quantify the similarity between neighborhood samples. ˜L = ∑mv=1 (Λv -Wv ), and Λv is a diagonal matrix with Λvii = ∑nj=1 Wv ij . Minimizing Φ2(U) can guide U to encode consistent and complementary information shared across views. In this way, the quality of diverse clusterings can be boosted using enhanced shared information.

Given the equivalence between matrix factorization based clustering and spectral clustering (or k-means clustering), we adopt the widely used semi-nonnegative matrix factorization [Ding et al., 2010] to explore the k-th clustering on U+Dk as follows:

where Rk ∈ Rn×rk and Bk ∈ Rn×rk (rk is the number of sample clusters) are the clustering indicator matrix and the basis matrix, respectively. Here, the k-th clustering is generated not only with respect to Dk , but also to U, which encodes the shared information of multi-view data. As such, the explored k-th clustering (encoded by Rk ) not only reflects the individuality of views in the k-th group, but also captures the commonality of all data views. As a consequence, a highquality, and yet diverse clustering can be generated.

The above process first explores the individual information matrices and the shared information matrix, and then generates diverse clusterings on the data matrices. A sub-optimal solution may be obtained as a result because the two steps are performed separately. To avoid this, we advocate to simultaneously optimize {Dk }hk=1 and the diverse clusterings {Rk }hk=1 therein, and formulate a unified objective function for MVMC as follows:

By solving Eq. (6), we can simultaneously obtain multiple diverse clusterings of quality by leveraging the commonality and individuality information of multiple views.

Binary matrices {Rk }hk=1 are hard to directly optimize. As such, we relax the entries of {Rk }hk=1 to nonnegative numeric values. Since Eq. (6) is not jointly convex for {Dk }hk=1 , U and {Rk }hk=1 , it is unrealistic to find the global optimal values for all the variables. Here, we solve Eq. (6) via the alternating optimization method, which alternatively optimizes one variable, while fixing the other variables. The detailed optimization process can be viewed in the supplementary file due to the limitation of space.

2.2 Multiple Views Multiple Co-Clusterings

Recently, multiple co-clustering algorithms have also been suggested to explore alternative co-clusterings from the same data [Tokuda et al., 2017; Wang et al., 2018]. Multiple co-clustering methods aim at exploring multiple twoway clusterings, where both samples and features are clustered. In contrast, multiple clustering techniques only explore diverse one-way clusterings, where only samples (or only features) are clustered. Based on the merits of matrix tri-factorization in exploring co-clusters [Wang et al., 2011; 2018], we can seek multiple co-clusterings on multiple views by optimizing an objective function as follows:

where Cv ∈ Rdv×cv and Rv ∈ Rn×rk correspond to the row-cluster (grouping features) and column-cluster (grouping samples) indicator matrices of the h-th co-clustering. Sv ∈ Rcv×rv plays the role of absorbing the different scaling factors of Rv and Cv to minimize the squared error. Here we fix h = m for MVMCC, since different feature views have different numbers of features. Eq. (7) can be optimized following the similar procedure for optimizing Eq. (6), which is provided in the supplementary file due to page limit.

3 Experimental Results and Analysis

3.1 Experimental Setup

In this section, we evaluate our proposed MVMC and MVMCC on five widely-used multi-view datasets [Li et al., 2015; Tao et al., 2018], which are described in Table 1. The datasets have different number of views and are from different domains. Caltech-7 1 and Caltech-20 [Li et al., 2015] are two subsets of Caltech-101, which contains only 7 and 20 classes, respectively. The creation of these subsets is due to the unbalance of the number of data in each class of Caltech101. Each sample is made of 6 views of the same image. Mul-fea digits 2 is comprised of 2,000 data points from 0 to 9 digit classes, with 200 data points for each class. There are six public features available: 76 Fourier coefficients of the character shapes, 216 profile correlations, 64 Karhunenlove coefficients, 240 pixel averages in 2×3 windows, 47 Zernike moments, and 6 morphological features. Wiki article 3 contains selected sections from the Wikipedia's featured articles collection. We considered only the 10 most populated categories. It contains two views: text and image. Corel 4 [Tao et al., 2018] consists of 5000 images from 50 different categories. Each category has 100 images. The features are color histogram (9), edge direction histogram (18), and WT (9). Mirflickr 5 contains 25,000 instances collected from Flicker. Each instance consists of an image and its associated textual tags. To avoid noise, here we remove textual tags that appear less than 20 times in the dataset, and then delete instances without textual tags or semantic labels. This process gives us 16,738 instances.

Multiple clusterings need to quantify the quality and diversity of alternative clusterings. To measure quality, we use the widely-adopted Silhouette Coefficient (SC) and Dunn Index (DI) as the internal index. Larger values of SC and DI indicate a high quality clustering. To quantify the redundancy between alternative clusterings, we use Normalized Mutual Information (NMI) and Jaccard Coefficient (JC) as external indices. Smaller values of NMI and JC indicate smaller redundancy between alternative clusterings. All these metrics have been used in the multiple clustering literature [Bailey, 2013]. The formal definitions of these metrics, omitted here to save space, can be found in [Bailey, 2013; Yang and Zhang, 2017].

1 https://github.com/yeqinglee/mvdata

2 https://archive.ics.uci.edu/ml/datasets/Multiple+Features

3 http://www.svcl.ucsd.edu/projects/crossmodal/

4 http://www.cais.ntu.edu.sg/œchhoi/SVMBMAL/

5 http://press.liacs.nl/mirflickr/mirdownload.html

3.2 DiscoveringMultiple One-way Clusterings and Multiple Co-Clusterings

We compare the one-way multiple clusterings found by MVMC against Dec-kmeans [Jain et al., 2008], MNMF [Yang and Zhang, 2017], OSC [Cui et al., 2007], mSC [Niu et al., 2010], ISAAC [Ye et al., 2016], and MISC [Wang et al., 2019]. We also compare the multiple co-clusterings found by MVMCC against MultiCC [Wang et al., 2018] and MCC-NBMM [Tokuda et al., 2017]. The input parameters of the comparing methods are set as the authors suggested in their papers or shared code. The parameter values of MVMC and MVMCC are λ1 = 10, λ2 = 100, and h = 2 for multiple one-way clusterings, and h = m for multiple coclusterings. Since none of the existing multiple clustering algorithms can work on multiple view data, we concatenate the feature vectors of multiple view data and then run these comparing methods on the concatenated vectors to seek alternative clusterings. Our MVMC and MCMCC directly run on the multiple view data, without such feature concatenation.

We use k-means to generate the reference clustering for MNMF, and then use their respective solutions to generate two alternative clustering (C1, C2). We downloaded the source code of MNMF, ISAAC, MultiCC, MISC, and MCCNBMM, and implemented the other methods (Dec-kmeans, mSC, and OSC) following the respective original papers. Following the experimental protocol adopted by these methods, we quantify the average clustering quality on C1 and C2, and measure the diversity between C1 and C2. We fix the number of row-clusters rk for each clustering as the respective number of classes of each dataset, as listed in Table 1. For coclustering, we adopt a widely used technique [Monti et al., 2003] to determine the number of column clusters ck. Detailed parameter values are given in the supplementary file.

Table 2 reports the average results (of ten independent runs) and standard deviations of these comparing methods on exploring two alternative one-way clusterings with h = 2. From Table 2, we can see that MVMC often outperforms the comparing methods across different multi-view datasets, which proves the effectiveness of MVMC on exploring alternative clusterings on multi-view data. MVMC always gives the best result on the diversity metrics (NMI and JC). This fact suggests it can find two alternative clusterings with high diversity. MVMC occasionally has a lower quality value (SC and DI) than some of the comparing methods. This is explainable, since obtaining alternative clusterings with high-diversity and high-quality is a well-known dilemma, and MVMC achieves a much larger diversity than the comparing methods. Although the comparing methods employ different techniques to explore alternative clusterings in the subspaces, they almost always lose to MVMC. The cause is that the concatenated long feature vectors override the intrinsic structures of different views. This also explains why the comparing methods have lower values on diversity metrics (NMI and JC). In practice, because of the long concatenated feature vectors, the comparing methods generally suffer from a long runtime and cannot be applied on multi-view datasets with high-dimensional feature views. For example, we tried experiments on a large text dataset with five views, 18,758 samples, and more than 10,000 features per view. Since the concatenated data matrix has more than 100,000 features, almost all the comparing methods cannot complete after a long time, or even cannot run on a moderate server. In contrast, our MVMC is rather efficient, it does not need to concatenate features, and is directly applicable on each view.

Table 3 reports the results of MVMCC, MultiCC, and MCC-NBMM on exploring multiple co-clusterings, whose number is equal to the number of views h = m (unlike h = 2 for Table 2), because of the feature view heterogeneity. For this evaluation, we report the average quality and diversity values of all pairwise alternative co-clusterings of h clusterings. We can see that MVMCC significantly outperforms the two state-of-the-art multiple co-clustering methods across different evaluation metrics and datasets. MultiCC sometimes obtains a better diversity than MVMCC. This is because it directly optimizes the diversity on the samplecluster and feature-cluster matrices, while our MVMCC indirectly optimizes the diversity, mainly using the sample-cluster matrices. These results prove the effectiveness of our solution on exploring multiple co-clusterings on multi-view data.

Following the experimental setup in Table 2, we conduct additional experiments to investigate the contribution of the shared matrix U on improving the quality of multiple clusterings. For this investigation, we introduce a variant of MVMC(nU), which only uses {Dk }hk=1 to generate multiple clusterings and disregards the shared information matrix U. From the reported results on Digits and Wikipeda datasets in Table 4, we can see that the diversity (NMI and JC) of the two alternative clusterings remains almost the same when the shared information matrix U is excluded. However, the quality (SC and DI) is clearly reduced when U is excluded. This contrast proves that U indeed improves the quality of multiple clusterings, and justifies our motivation to seek U across views and leverage it with the individuality information matrix Dv for multiple clusterings.

In summary, we can conclude that the diversity information matrix helps generating diverse clusterings, and the commonality information matrix of multi-view data can improve the quality of the clusterings. These experimental results also confirm our assumption that the diversity and commonality of multi-view data can be leveraged to generate diverse clusterings with high-quality.

3.3 Parameter Analysis

λ1 and λ2 are two important input parameters of MVMC (MCMCC) for seeking the individuality and commonality information of multi-view data, which consequently affect the quality and diversity of multiple clusterings. We investigate the sensitivity of MVMC to these parameters by varying λ1 (it controls diversity) and λ2 (it controls quality) in the range [10-3 , 10-2 , · · · , 103 ]. Figure 2 reports the Quality (DI) and Diversity (1-NMI, the larger the better) of MVMC on the Caltech-7 dataset. We have several interesting observations: (i) diversity (1-NMI) increases as λ1 increases, but not as much as with the increase of λ2 (see Figure 2(b)); quality (DI) increases as λ2 increases, but not as much as with the increase of λ1. (ii) The synchronous increase of λ1 and λ2 does not necessarily give the highest results in quality and diversity. (iii) When both λ1 and λ2 are fixed to a small value, both quality and diversity are reduced. This fact suggests that both diversity and commonality information of multi-view data should be used for the exploration of alternative clusterings. These observations again confirm the known dilemma between diversity and quality of multiple clusterings. The values λ1 = [10, 100] and λ2 = [10, 100] often provide the best balance between quality and diversity.

We vary h from 2 to 2 ∗ m on the Caltech-7 dataset to explore the variation of average quality and diversity of multiple clusterings generated by MVMC. In Figure 3, as h increases, the average quality of multiple clusterings decreases gradually with small fluctuations, and the average diversity fluctuates in a small range. These patterns are due to the quality-diversity dilemma of multiple clusterings. Increasing the number of alternative and diverse clusterings results in a sacrifice of quality. Overall, we can find that our MVMC can explore h ≥ 2 alternative clusterings with quality and diversity.

The time complexity of our MVMC is O(tn2d(h2 v + 2hv + 2h)), where t is the number of iterations for optimization. The experiments are conducted on a server with Ubuntu 16.04, Intel Xeon8163 with 1TB RAM; all methods are implemented in Matlab2014a. The detailed runtime analysis can be viewed in the supplementary file due to the limitation of space.

4 Conclusion

In this paper, we proposed an approach to generate multiple clusterings (co-clusterings) from multi-view data, which is an interesting but largely overlooked clustering topic encompassing both multi-view clustering and multiple clusterings. Our approach leverages the diversity and commonality of multi-view data to generate multiple clusterings, and outperforms state-of-the-art multiple clustering solutions. Our study confirms the existence of individuality and commonality of multi-view data, and their contribution for generating diverse clusterings with good quality. In the future, we plan to find a principled way to automatically determine the number of alternative clusterings, and explore weighting schemes of data views. The code of MVMC (MVMCC) is available at http://mlda.swu.edu.cn/codes.php?name=MVMC.

Acknowledgments

This work is supported by NSFC (61872300 and 61873214), Fundamental Research Funds for the Central Universities (XDJK2019B024), NSF of CQ CSTC (cstc2018jcyjAX0228 and cstc2016jcyjA0351), King Abdullah University of Science and Technology (KAUST), Saudi Arabia.