Multiple Partitions Aligned Clustering

1 Introduction

As an important problem in machine learning and data mining, clustering has been extensively studied for many years [Jain, 2010]. Technology advances have produced large volumes of data with multiple views. Multi-view features depict the same object from different perspectives, thereby providing complementary information. To leverage the multi-view information, multi-view clustering methods have drawn increasing interest in recent years [Chao et al., 2017]. Due to its unsupervised learning nature, multi-view clustering is still a challenging task. The key question is how to reach a consensus of clustering among all views.

In the clustering field, two dominating methods are kmeans [Jain, 2010] and spectral clustering [Ng et al., 2002]. Numerous variants of them have been developed over the past decades [Chen et al., 2013; Liu et al., 2018; Yang et al.,

∗Corresponding author

2018; Kang et al., 2018a]. Among them, some can tackle multi-view data, e.g., multi-view kernel k-means (MKKM) [Tzortzis and Likas, 2012], robust multi-view kernel k-means (RMKKM) [Cai et al., 2013], Co-trained multi-view spectral clustering (Co-train) [Kumar and Daum´e, 2011], Coregularized multi-view spectral clustering (Co-reg) [Kumar et al., 2011]. Along with the development of nonnegative matrix factorization (NMF) technique, multi-view NMF also gained a lot of attention. For example, a multi-manifold regularized NMF (MNMF) is designed to preserve the local geometrical structure of the manifolds for multi-view clustering [Zong et al., 2017].

Recently, subspace clustering method has shown impressive performance. Subspace clustering method first obtains a graph, which reveals the relationship between data points, then applies spectral clustering to achieve the embedding of original data, finally utilizes k-means to obtain the final clustering result [Elhamifar and Vidal, 2013; Kang et al., 2019a]. Inspired by it, subspace clustering based multi-view clustering methods [Gao et al., 2015; Zhang et al., 2017; Huang et al., 2019] have become popular in recent years. For instance, Gao et al. proposed multi-view subspace clustering (MVSC) method [Gao et al., 2015]. In this approach, multiple graphs are constructed and they are forced to share the same cluster pattern. Therefore, the final clustering is a negotiated result and it might not be optimal. [Wang et al., 2016] supposes that each graph should be close to each other. After obtaining graphs, their average is utilized to perform spectral clustering. The averaging strategy might be too simple to fully take advantage of heterogeneous information. Furthermore, it is a two-stage algorithm. The constructed graph might not be optimal for the subsequent clustering [Kang et al., 2017].

By contrast, another class of graph-based multi-view clustering method learns a common graph based on adaptive neighbors idea [Nie et al., 2016a; Zhan et al., 2017]. In specific, xi is connected to xj with probability sij. sij should have a large value if the distance between xi and xj is small. Otherwise, sij should be small. Therefore, obtained sij is treated as the similarity between xi and xj. In [Nie et al., 2016a], each view shares the same similarity graph. Moreover, a weight for each view is automatically assigned based on loss value. Though this approach has shown its competitiveness, one shortcoming of it is that it fails to consider the flexible local manifold structures of different views.

Although proved to be effective in many cases, existing graph-based multi-view clustering methods are limited in several aspects. First, they integrate the multi-view information in the feature space via some simple strategies. Due to the generally unavoidable noise in the data representation, the graphs might be severely damaged and cannot represent the true similarities among data points [Kang et al., 2019b]. It would make more sense if we directly reach consensus clustering in partition space where a common cluster structure is shared by all views, while the graphs might be quite different for different views. Hence, partitions from various views might be less affected by noise and easier to reach an agreement. Second, most existing algorithms follow a multi-stage strategy, which might degrade the final performance. For example, the learned graph might not be suitable for the subsequent clustering task. A joint learning method is desired for this kind of problem.

Regarding the problems mentioned above, we propose a novel multiple Partitions Aligned Clustering (mPAC) method. Fig. 1 shows the idea of our approach. mPCA performs graph construction, spectral embedding, and partitions integration via joint learning. In particular, an iterative optimization strategy allows the consensus clustering to guide the graph construction, which later contributes to a new unified clustering. To sum up, we have our two-fold contributions as follows:

• Orthogonal to existing multi-view clustering methods, we integrate multi-view information in partition space. This change in paradigm accompanies several benefits.
• An end-to-end single stage model is developed to achieve from graph construction to final clustering. Especially, we assume that the unified clustering is reachable for each view through a distinct transformation. Moreover, the output of our algorithm is the discrete cluster indicator matrix, thus no more subsequent step is needed.

Notations In this paper, matrices and vectors are represented by capital and lower-case letters, respectively. For A = [aij] ∈ Rm×n , Ai,: and A:,j represents the i-th row and j-th column of A, respectively. The ℓ2-norm of vector x is defined as ‖x‖ = √xT · x, where T means transpose. Tr(A) denotes the trace of A. ‖A‖F = √∑mi=1 ∑nj=1 A2ij denotes the Frobenius norm of A. Vector 1 indicates its elements are all ones. I refers to the identity matrix with a proper size. Ind def = {Y ∈ {0, 1}n×c |Y 1 = 1} represents the set of indicator matrices. We use the superscript Ai or subscript Ai to denote the i-th view of A interchangeably when convenient.

2 Subspace Clustering Revisited

In general, for data X ∈ Rm×n with m features and n samples, the popular subspace clustering method can be formulated as:

where α > 0 is a balance parameter and R(Z) is some regularization function, which varies in different algorithms [Peng et al., 2018]. For simplicity, we just apply the Frobenius norm in this paper. diag(S) is the vector consists of diagonal elements of S. S is treated as the affinity graph. Therefore, once S is obtained, we can implement spectral clustering algorithm to obtain the clustering results, i.e.,

where L ∈ Rn×n is the Laplacian of graph S and F ∈ Rn×c is the spectral embedding and c is number of clusters. Graph Laplacian L is defined by L = D - S, where D is a diagonal matrix with dii = ∑j sij . Since F is not discrete, kmeans is often used to recover the indicator matrix Y ∈ Ind.

When data of multiple views are available, Eq. (2) can be extended to this scenario accordingly. X = [X1 ;X2 ; · · · ;Xv ] ∈ Rm×n denotes the data with v views, where Xi ∈ Rmi×n represents the i-th view data with mi features. Basically, most methods in the literature solve the following problem

where G represents some strategy to obtain a consensus graph S. For example, [Gao et al., 2015] enforces each graph to share the same F; [Wang et al., 2016] penalizes the discrepancy between graphs, then their average is used as input to spectral clustering.

We observe that there are several drawbacks shared by these approaches. First and foremost, they still lack an effective way to integrate multi-view knowledge while simultaneously considering the heterogeneity among views. Simply taking the average of graphs or assigning a unique spectral embedding is not enough to take full advantage of rich information. The graph representation itself might not be optimal to characterize the multi-view information. Secondly, they adopt a multi-stage approach. Since there is no mechanism to ensure the quality of learned graphs, this approach might lead to sub-optimal clustering results, which often occurs when noise exists. To address the above-mentioned challenging issues, we propose a multiple Partitions Aligned Clustering (mPAC) method.

3 Proposed Approach

Unlike Eq.(3), which learns a unique graph based on multiple graphs Si s, we propose to learn a partition for each graph. In specific, we adopt a joint learning strategy and formulate our objective function as

Next, we propose a way to fuse the multi-view information in the partition space. For multi-view clustering, a shared cluster structure is assumed. It is reasonable to assume a cluster indicator matrix Y ∈ Ind for all views. Unfortunately, Fi's elements are continuous. The discrepancy also exists among Fi's. Thus, it is challenging to integrate multiple Fis. To recover the underlying cluster Y , we assume that each partition is a perturbation of Y and it can be aligned with Y through a rotation [Kang et al., 2018b; Nie et al., 2018]. Mathematically, it can be formulated as v∑

where Ri represents an orthogonal matrix. Eq. (5) treats each view equally. As shown by many researchers, it is necessary to distinguish their contributions. Therefore, we introduce a weight parameter wi for view i. Deploying a unified framework, we eventually reach our objective for mPAC as

We can observe that the proposed approach is distinct from other methods in several aspects:

• Orthogonal to existing multi-view clustering techniques, Eq. (6) integrates heterogeneous information in partition space. Considering that a common cluster structure is shared by all views, it would be natural to perform information fusion based on partitions.
• Generally, learning with multi-stage strategy often leads to sub-optimal performance. We adopt a joint learning framework. The learning of similarity graphs, spectral embeddings, view weights, and unified cluster indicator matrix is seamlessly integrated together.
• Y is the final discrete cluster indicator matrix. Hence, discretization procedure is no longer needed. This eliminates the k-means post-processing step, which is sensitive to initialization. With input X, (6) will output the final discrete Y . Thus, it is an end-to-end single-stage learning problem.
• Multiple graphs are learned in our approach. Hence, the local manifold structures of each view are well taken care of.
• As a matter of fact, Eq. (6) is not a simple unification of the pipeline of steps and it attempts to learn graphs with optimal structure for clustering. According to the graph spectral theory, the ideal graph is c-connected if there are c clusters [Kang et al., 2018b]. In other words, the

Laplacian matrix L has c zero eigenvalues σis. Approximately, we can minimize ∑ci=1 σi, which is equivalent to min F T F =I Tr(F T LF). Hence, the third term in Eq. (6) ensures that each graph Si is optimal for clustering.

4 OptimizationMethods

To handle the objective function in Eq. (6), we apply an alternating minimization scheme to solve it.

4.1 Update Si for Each View

By fixing other variables, we solve Si according to

It can be seen that each Si is independent from other views. Therefore, we can solve each view separately. To simplify the notations, we ignore the view index tentatively. Note that L is a function of S and T r(F T LF ) = ∑ij 1 2 ‖Fi,: -Fj,:‖2Sij . Equivalently, we solve

where hi ∈ Rn×1 with the j-th component defined by hij = ‖Fi,: -Fj,:‖2 . By setting its first-order derivative to zero, we obtain

4.2 Update Fi for Each View

Similarly, we drop all unrelated terms with respect to Fi and ignore the view indexes. It yields,

This sub-problem can be efficiently solved based on the method developed in [Wen and Yin, 2013].

4.3 Update Ri for Each View

With respect to Ri, the objective function is additive. We can solve each Ri individually. Specifically,

Lemma 1. For problem

its closed-form solution is R∗ = UV T , where U, V are the left and right unitary matrix of the SVD decomposition of F T Y , respectively [Sch¨onemann, 1966].

4.4 Update Y

For Y , we get

Let's unfold above objective function, we have

Thus, we can equivalently solve

It admits a closed-form solution, that is, ∀i = 1, · · · , n,

4.5 Update wi for Each View

Let's denote ‖Y -FiRi‖F as qi, then this subproblem can be expressed as

Based on Cauchy-Schwarz inequality, we have

The minimum, which is a constant, is achieved when √wi ∝ qi √wi . Thus, the optimal w is given by, ∀i = 1, · · · , v,

.

For clarity, we summarize the algorithm 1 to solve Eq. (6) in Algorithm 1.

5 Experiments

5.1 Experimental Setup

We conduct experiments on four benchmark data sets: BBCSport, Caltech7, Caltech20, Handwritten Numerals. Their

1 Our code is available: https://github.com/sckangz/mPAC

Algorithm 1 Optimization for mPAC

Input: Multiview matrix X1 , · · · ,Xv , cluster number c, parameters α, β, γ. Output: Y . Initialize: Random Y and Fi, Ri = I, wi = 1/v, ∀i = 1, · · · , v. REPEAT

1:

for view 1 to v do

2:

Update each column of S according to (9);

3:

4:

Solve the subproblem (10);

Solve the subproblem (11);

5: end for

6: Update Y according to (15);

7: Update wi via (18) for each view.

UNTIL stopping criterion is met

statistics information is summarized in Table 1. We compare the proposed mPAC with several state-of-the-art methods from different categories, including Co-train [Kumar and Daum´e, 2011], Co-reg [Kumar et al., 2011], MKKM [Tzortzis and Likas, 2012], RMKM [Cai et al., 2013], MVSC [Gao et al., 2015], MNMF [Zong et al., 2017], parameter-free auto-weighted multiple graph learning (AMGL) [Nie et al., 2016a]. Furthermore, the classical kmeans (KM) method with concatenated features (i.e., all features, AllFea in short) is included as a baseline. That is to say, all views are of the same importance. Following [Huang et al., 2018], all values of each view are normalized into range [-1, 1]. To achieve a comprehensive evaluation, we apply five widely-used metrics to examine the effectiveness of our method: F-score, precision, Recall, Normalized Mutual Information (NMI), and Adjusted Rand Index (ARI). We initialize our algorithm by using the results from [Nie et al., 2016b].

5.2 Experimental Results

We repeat each method 10 times and report their mean and standard deviation (std) values. For our proposed method, we only need to implement once since no k-means is involved. The clustering performance on those four data sets is summarized in Tables 2-5, respectively. We can observe that our mPAC method achieves the best performance in most cases, which validates the effectiveness of our approach. In general, our method works better than k-means and NMF based techniques. Furthermore, it can be seen that the improvement is remarkable. With respect to graph-based clustering methods, our approach also demonstrates its superiority. In particular, both MVSC and AMGL assume that all graphs produce the same partition, while our method learns one partition for each view and finds the underlying cluster by aligning mechanism.

To visualize the effect of partitions alignment, we implement t-SNE on the clustering results of Handwritten Numerals data. As shown in Fig. 2, some partitions have a good cluster structure, thus it might be easy to find a good Y . On the other hand, although the partition of view 5 is bad, we can still achieve a good solution Y . This indicates that our method is reliable to obtain a good clustering since it operates in the partition space. By contrast, previous methods may not consistently provide a good solution.

5.3 Sensitivity Analysis

Taking Caltech7 as an example, we demonstrate the influence of parameters to clustering performance. From Fig. 3, we can observe that our performance is quite stable under a wide range of parameter settings. In particular, it becomes more robust to α and β when γ increases, which indicates the importance of partition alignment.

6 Conclusion

In this paper, a novel multi-view clustering method is developed. Different from existing approaches, it seeks to integrate multi-view information in partition space. We assume that each partition can be aligned to the consensus clustering through a rotation matrix. Furthermore, graph learning and clustering are performed in a unified framework, so that they can be jointly optimized. The proposed method is validated on four benchmark data sets.

Acknowledgments

This paper was in part supported by Grants from the Natural Science Foundation of China (Nos. 61806045 and 61572111), two Fundamental Research Fund for the Central Universities of China (Nos. ZYGX2017KYQD177 and A03017023701012) and a 985 Project of UESTC (No. A1098531023601041) .