Multi-Task Multi-View Clustering for Non-Negative Data

1 Introduction

Multi-task clustering improves individual clustering performance by learning the relationship among related tasks. Multi-view clustering makes use of the consistency among different views to achieve better performance. Both multitask clustering and multi-view clustering have severally found wide applications and received much attention in recent years. Nevertheless, there are many practical problems that involve both multi-task clustering and multi-view clustering, i.e., the tasks are closely related and each task can be analyzed from multiple views. For example, the tasks for clustering the web pages from four universities are four related tasks. The four tasks all have word features in the main texts, they also have many other features, such as the words in the hyperlinks pointing to the web pages, and the words in the titles of the web pages. For another example, the tasks for clustering the web images collected from Chinese web sites and English web sites are two related tasks. The two tasks both have visual features in the images, they also have word features in the surrounding texts in Chinese and English respectively. To tackle the clustering problem of such data sets, existing algorithms can only utilize limited information, i.e., multi-view clustering algorithms only use the information of the views in a single task, multi-task clustering algorithms only exploit the mutual information shared by all the related tasks from a single view. However, we can get better performance if both the multi-task and multi-view information could be utilized.

Recently, multi-task multi-view learning algorithms, which learn multiple related tasks with multi-view data, have been proposed. The graph-based framework in [He and Lawrence, 2011] takes full advantages of both the feature heterogeneity and task heterogeneity. Within each task, the consistency among different views is obtained by requiring them to produce the same classification function, and across different tasks, the relationship is established by utilizing the similarity constraint on the common views. The inductive learning framework in [Zhang and Huan, 2012] uses co-regularization and task relationship learning, which increases the practicality of multi-task multi-view learning. These methods have demonstrated their superiorities over either multi-task or multi-view learning algorithms. However, they all tackle classification. To the best of our knowledge, there is no existing approach to the multi-task multi-view clustering problem.

In this paper, we aim to deal with the multi-task multi-view clustering of non-negative data, which arises in many applications, such as various types of documents. Based on the observation that the related tasks have both common views and task specific views, we propose a bipartite graph based multitask multi-view clustering (MTMVC) framework, which consists of three parts. (1) Within-view-task clustering: this part clusters the data of each view in each task. It is the base of the framework and mutually boosts with the other two parts. (2) Multi-view relationship learning: this part uses the consistency among different views to improve the clustering performance. (3) Multi-task relationship learning: this part learns the relationship among related tasks to improve the clustering performance. We integrate the three parts into one objective function and optimize it with a gradient ascent method. Because of the unitary constraints, we further solve the optimization problem by mapping the variables to the Stiefel manifold [Manton, 2002]. Experimental results on several real data sets show the superiority of the proposed algorithm over either multi-task clustering algorithms or multiview clustering algorithms for multi-task clustering of multiview data.

2 RelatedWork

Multi-task Clustering: Multi-task clustering improves the clustering performance by learning the information shared among multiple related tasks. The approach in [Gu and Zhou, 2009] learns a subspace shared by the related tasks. The method in [Gu et al., 2011] handles the multi-task clustering problem by learning a kernel. Unlike the above methods which focus on cross-domain multi-task clustering, some multi-task clustering methods are proposed to deal with the case of the related tasks from a same distribution or similar distributions [Zhang and Zhang, 2010; 2013].

Multi-view Clustering: Multi-view clustering achieves better performance by using the consistency among different views. The method in [de Sa, 2005] is based on the minimizingdisagreement idea. The method in [Kumar et al., 2011] co-regularizes the clustering hypotheses across views. The method in [Kumar and Daum´e, 2011] applies the idea of cotraining, which uses the spectral embedding from one view to constrain the similarity graph used for the other view.

Multi-task Multi-view Learning: Multi-task multi-view learning deals with the learning problem of multiple related tasks with multiple views. There are mainly two algorithms proposed recently [He and Lawrence, 2011; Zhang and Huan, 2012]. As far as we know, there is no existing approach to the multi-task multi-view clustering problem.

Co-clustering: Co-clustering has received a lot of attention in several practical applications such as text mining [Dhillon, 2001], genes [Cho et al., 2004] and recommender systems [George and Merugu, 2005]. Co-clustering clusters the samples and features simultaneously so that the clustering performance of samples can be improved by the clustering of features, and vice versa [Banerjee et al., 2007].

3 MTMVC Framework

3.1 ProblemFormulation

We are given T clustering tasks, each with Vt views, i.e., X(v) t = {x(v) 1 , x(v) 2 , ...., x(v) nt } ∈ Rd(v) t ×nt , t = 1, . . . , T, v = 1, . . . , Vt, where nt is the number of samples in the tth task, d(v) t is the feature number of the v-th view in task t. Each task t is to be partitioned into ct clusters. In multitask multi-view applications, the related tasks can be analyzed from multiple views. It can be observed that from some views, the related tasks share a lot of features [He and Lawrence, 2011], we call such views common views, and call the other views task specific views. S is the index collection of common views. Tv is the index collection of tasks under the common view v. The common view v consists of the features in the tasks belonging to Tv under view v. We assume the related tasks share at least one common view, and the number of clusters in each task is the same, i.e., c1 = c2 = . . . = cT = c. The first c eigenvectors represent the eigenvectors corresponding to the c largest eigenvalues.

3.2 Framework Overview

Based on the characteristics of the multi-task multi-view applications, we integrate the features in the common view of

each task to link the related tasks together, and propose a bipartite graph based MTMVC framework (Figure 1), which consists of three components: within-view-task clustering, multi-view relationship learning and multi-task relationship learning. For within-view-task clustering, we construct a bipartite graph for each view of each task, and apply the bipartite graph co-clustering (BiCo) algorithm [Dhillon, 2001]. For multi-view relationship learning, we minimize the disagreement between the clustering of samples under each pair of views in each task. For multi-task relationship learning, we construct a bipartite graph between the samples and the shared features in the common view for each task, and perform the BiCo method to learn a shared subspace among the related tasks under each common view.

3.3 Objective Function

Within-view-task Clustering

This component clusters the data in each view of each task. It accomplishes the essential task of the whole algorithm and mutually boosts with the other two components. It also ensures the preservation of the knowledge available locally at each view of each task to avoid negative transfer [Pan and Yang, 2010]. We use BiCo, which clusters the samples and features through a bipartite graph, and the two phases boost each other. Given a data set X ∈ Rd×n , we have W = [ 0 X XT 0 ] and D = [ D1 0 0 D2 ] , where W is the matrix of bipartite graph, D is the degree matrix, D1(i, i) = ∑j Xij , D2(j, j) = ∑i Xij . The objective function of BiCo can be expressed as

where L = D-1/2 (D-W)D-1/2 , Z = [U;M], U ∈ Rd×c is composed of the first c eigenvectors of features, which indicates a partitioning of features, M ∈ Rn×c is composed of the first c eigenvectors of samples, which indicates a partitioning of samples. Eq.(1) can also be expressed as

Multi-view Relationship Learning

To meet the requirement of consistency among different views within each task, we need a way to compare the eigenvectors of samples under view v and view q in each task t, say M (v) t and M (q) t . Since M (v) t and M (q) t do not represent the true clustering result, we cannot compute the disagreement between them directly by squared Euclidean distance. But we can compute the similarity matrices for the partitioning of samples under view v and view q, say SimM(v) t and SimM(q) t , then compute the disagreement between them by squared Euclidean distance as follows.

Considering the feasibility of optimization, we use the common measure inner product to compute the similarity matrix, and get SimM(v) t = M (v) t M (v)T t . Under the constraint in Eq.(3), minimizing Eq.(3) can be simplified as

Multi-task Relationship Learning

To establish the relationship among related tasks, we hope to learn a subspace shared by the related tasks under the common view, in which the clustering result of each task is considered as the same as that in the original feature space. The shared subspace can be seen as a new feature space, in which the distributions of related tasks are close to each other. More specifically, if there are some tasks related to each other, there may exist some common latent features that cause the distributions of the related tasks to be close to each other [Gu and Zhou, 2009]. Therefore the task information can be transferred through the shared subspace. Based on the analysis above, we construct a bipartite graph between the samples and the shared features in the common view for each task, and perform the BiCo method to learn a shared subspace from the shared features in the common view. In BiCo, the eigenvectors of features in the v-th view of the t-th task U (v) t can be thought of as dimensionality reduction with a linear combination of associated features, which can also be referred to as subspace basis [Vidal, 2011]. Considering there is a subspace U (v) shared by the related tasks under the common view v, as the BiCo method contains a component U (v) t which can be seen as a subspace, and the eigenvectors of features U (v) t can be boosted by the eigenvectors of samples M (v) t , thus we use the BiCo method to learn the shared subspace U (v) which can be boosted by M (v) t in all the related tasks.

where ˜ A(v) t = D-1/2 1 ˜X(v) t D-1/2 2 , ˜X(v) t is a data matrix between the samples in task t and the features shared by the tasks in the common view v.

The Overall Objective Function

We integrate within-view-task clustering, multi-view relationship learning and multi-task relationship learning into the overall objective function as follows.

where J1 = tr(U (v)T t A(v) t M (v) t ), J2 = tr(M (v) t M (v)T t M (q) t M (q)T t ) and J3 = tr(U (v)T ˜ A(v) t M (v) t ).

all the views in each task t, Vt∑ v=1 Vt∑ q̸=v J2 is to maximize the

agreement between the cluster assignments of any two different views in each task t, ∑ v∈S ∑ J3 is to learn the shared

t∈Tv subspace under each common view. λ ≥ 0, µ ≥ 0 are parameters.

Discussion

Note that the objective of multi-task multi-view clustering is very complicated since different missions are involved. We divide the problem into three parts to make it easier to solve. There are other ways to combine the components. However, our way of using components in similar forms and linear combination leads to a simple solution of the problem.

We use the BiCo method for the first component, since it can boost M (v) t by U (v) t and vice versa, which can further promote multi-view and multi-task relationship learning. Specifically, during multi-view relationship learning, M (v) t can take advantage of M (q) t (q ̸= v) because the boosted M (q) t by BiCo in the first component can indicate the partition of samples more accurately. During multi-task relationship learning, the shared subspace U (v) can be boosted by the M (v) t which has been improved by BiCo in the first component. However, despite these advantages, the use of BiCo limits our framework to work only for non-negative data.

The BiCo methods used in the first component and the third component play different roles. The BiCo method in the first component is to establish associations between the samples and any view within each task, and is essential to the multiview relationship learning. The BiCo method in the third component is to learn the shared subspace among the related tasks, as BiCo can cluster features besides clustering samples, and the clusters of features (the eigenvectors of features) can be seen as subspace basis [Vidal, 2011].

Algorithm 1 MTMVC

Input: T tasks, each with Vt views {X(v) t }Tt=1 , v = 1, . . . , Vt. The index collection of common views S. The index collection of tasks under the common view v Tv. Cluster number c. λ ≥ 0, µ ≥ 0, the step length γ.

Output: Partitions {P (t) }Tt=1 .

Initialization: Compute A(v) t in Eq.(2). U (v) t is formed by the first c left singular vectors of A(v) t , and M(v) t is formed by the first c right singular vectors of A(v) t . Select the shared features under the common view v, then compute ˜X(v) t and ˜ A(v) t (t ∈ Tv) in Eq.(5). U (v) is formed by the first c left singular vectors of ˜ A, where ˜ A = D-1/2 1 ˜XD-1/2 2 , and ˜X is the combination of ˜X(v) t (t ∈ Tv). repeat

Update U (v) t by Eq.(9).

Update U (v) by Eq.(12).

Update M(v) t by Eq.(17).

until Eq.(6) is convergent.

Run the k-means algorithm on M(v) t (t = 1, . . . , T), where v is the most informative view a priori. If there is no prior knowledge on the view informativeness, run the k-means algorithm on the column-wise concatenation of M(v) t (v = 1, . . . , Vt).

λ ≥ 0 and µ ≥ 0 control the relative importance of the three components. Specifically, Eq.(6) can be seen as the objective function of a multi-view clustering method with µ = 0, and a multi-task clustering method with λ = 0.

3.4 Optimization

In this subsection, we present an algorithm to optimize Eq.(6) by gradient ascent method. Optimizing Eq.(6) is with respect to variables U (v) t , U (v) andM (v) t . Because of the constraint in Eq.(6), we map the variables to the Stiefel manifold.

Proposition 1 [Manton, 2002] The complex Stiefel manifold St(n, p) is St(n, p) = {X ∈ C n×p : XH X = I}. Let X ∈ C n×p be a rank p matrix. The projection operator π : C n×p → St(n, p) is defined to be π(X) = arg min Q∈St(n,p) ||X - Q||2F . Moreover, if the SVD of X is

X = UΣV H , then π(X) = UIn,pV H , where In,p denotes the n - by - p matrix with ones along the diagonal.

Computation of U (v) t : Given M (v) t , optimizing Eq.(6) with respect to U (v) t turns to be

Then we get

According to proposition 1, we can get

Computation of U (v) : For the common view v, we get the optimal U (v) by the following computations. Given M (v) t , optimizing Eq.(6) with respect to U (v) turns to be

Then we get

According to proposition 1, we can get

Computation of M (v) t :

1) If v ∈ S and t ∈ Tv, given U (v) t , U (v) , M (q) t (q ̸= v), optimizing Eq.(6) with respect to M (v) t turns to be

Then we get

2) If v /∈ S or t /∈ Tv(v ∈ S), given U (v) t , M (q) t (q ̸= v), optimizing Eq.(6) with respect to M (v) t turns to be

Then we get

According to proposition 1, we can get

We present the process of optimizing Eq.(6) in Algorithm 1. Our proposed algorithm is typically a gradient ascent algorithm, which is proved to be convergent [Griffin, 2012].

3.5 Time Complexity

Denote d as the feature number, n as the sample number, iter as the iterations of MTMVC and I as the iterations of k-means. The time complexity of the initialization process is O(d2n + dn2 ). The time complexity during iterations is O(iter(dnc + d2 c + dc2 + n2 c + c2n)). The time complexity of the final clustering part in MTMVC k-means is O(Icnd). The overall time complexity of MTMVC is O((d2 + iter(cd + c2 ) + Icd)n + (d + iterc)n2 + iterd2 c + iterdc2 ) = O(d2n + dn2 ) .

4 Experiments

4.1 Data Sets

WebKB 1 : The WebKB data set contains web pages collected from computer science department websites at 4 universities. They are divided into 7 categories, we choose 4 most populous categories such as course, faculty, project and student for clustering. The data set has 4 tasks, each is to cluster the web pages of an university. There are three views for each task: the words in the main texts of all the 4 universities constitute the common view, since the tasks share lots of words from the main text view; the words in the hyperlinks pointing to the web pages of this university and the words in the titles of the web pages of this university constitute two task specific views respectively, since the tasks share few words from the hyperlink view and title view.

20NewsGroups 2 : The 20NewsGroups data set is composed of 6 root categories, under which are 20 sub categories. We generate the NG data set from the samples of 4 root categories (comp, rec, sci and talk), each with 4 sub categories. NG has 4 tasks, each containing samples from 4 root categories.

Email 3 : The Email data set contains the emails of 3 inboxes from different users. The data set has 3 tasks, with each task formed by an inbox from a specific user. We aim to divide each task into 2 clusters, one is spam, the other is non-spam.

1 http://www.cs.cmu.edu/afs/cs.cmu.edu/project/theo-

20/www/data/

2 http://qwone.com/ jason/20Newsgroups/

3 http://www.ecmlpkdd2006.org/challenge.html

For NG and Email, we adopt the way of constructing multitask multi-view data in [He and Lawrence, 2011; Zhang and Huan, 2012], which has been effectively used to validate the multi-task multi-view learning methods. Based on the way in [He and Lawrence, 2011; Zhang and Huan, 2012], for each task, the common view consists of the words appearing in the main texts of all the tasks, the task specific view consists of the words that only appear in this task. We use Rainbow 4 for data preprocessing: removing the header lines and stop words, selecting words by mutual information.

4.2 Baseline Methods

To the best of our knowledge, there is no existing work for multi-task multi-view clustering. We compare the MTMVC algorithm with (1) typical single-task single-view clustering methods: k-means, normalized spectral clustering algorithm (NSC) [Ng et al., 2001], kernel k-means (kk-means), bipartite graph co-clustering algorithm (BiCo) [Dhillon, 2001]; (2) multi-view clusteringmethods: co-regularizedmulti-view spectral clustering algorithm (CoRe) [Kumar et al., 2011], cotrained multi-view spectral clustering algorithm (CoTr) [Kumar and Daum´e, 2011]; (3) multi-task clustering methods: the shared subspace learning multi-task clustering algorithm (LSSMTC) [Gu and Zhou, 2009] and the kernel learning multi-task clustering algorithm (LNKMTC) [Gu et al., 2011].

4 http://www.cs.cmu.edu/∼mccallum/bow/

In addition, we evaluate MTMVC without the second component (MTMVC-MT), regressing to a multi-task algorithm, and without the third component (MTMVC-MV), regressing to a multi-view algorithm. In general, we use the clustering result of MTMVC from the most informative view (as all multi-view clustering methods do). But sometimes we may not know the most informative view, so we also evaluate MTMVC by running k-means on column-wise concatenation of M (v) t (v = 1, . . . , Vt), we denote this version as MTMVCCV.

As existing multi-task clustering methods can only work in a view which contains the features shared by all the tasks, we perform LSSMTC, LNKMTC and MTMVC-MT on the common view. To make the three methods exploit the information of task specific views, we also perform them on a concatenation of the features of all the views, and call them LSSMTC(CF), LNKMTC(CF) and MTMVC-MT(CF).

4.3 Settings

For NSC, kk-means, CoRe and CoTr, the Gaussian kernel width δ is set with the median Euclidean distance between samples of each task, which can self-adapt to the data and has been commonly used in the literatures [Gretton et al., 2006; Kumar et al., 2011]. For the other parameters, we apply grid searching [Zhang and Huan, 2012] to identify the optimal values. For the baseline methods, we extend the grid searching range largely upon the original authors's settings. For CoRe, the parameter λ is set by searching the grid {0.01, 0.02, . . . 0.99, 1}. For CoTr, the number of selected eigenvectors is set by searching the grid {1, 1.1, . . . , 1.5} × c, where c is the cluster number. For LSSMTC and LSSMTC(CF), the parameter λ is set by searching the grid {0.1, 0.2, . . . 0.9}, the dimensionality of the shared subspace l is set by searching the grid {2, 4, 6, 8, 10}. For LNKMTC and LNKMTC(CF), the neighborhood size is set by searching the grid {10, 20, . . . 100}, the regularization parameter C is set by searching the grid {0.1, 1, 10, 100, 500, 1000}, the trace parameter b is set by searching the grid {10, 20, 30, 40, 50}. For MTMVC and MTMVC-CV, we set the parameter of step length γ = 1, and set λ, µ by searching the grid {0.1, 0.2, . . . , 1}. Specifically, we set λ = 0 for MTMVCMT and MTMVC-MT(CF), µ = 0 for MTMVC-MV.

To evaluate the clustering results, we adopt two performance measures in [Xu et al., 2003]: clustering accuracy (Acc) and normalized mutual information (NMI).

4.4 Clustering Results

We repeat each algorithm 10 times under each parameter setting. For the algorithms LSSMTC(CF), LNKMTC(CF), MTMVC-MT(CF) and MTMVC-CV, we show the mean result and the standard deviation corresponding to the best parameter setting. For the other algorithms, we show those of the most informative view corresponding to the best parameter setting. For multi-view clustering methods, we cluster each task at a time. From the clustering results in Table 1, 2 and 3, the following observations could be made.

1. BiCo performs better than the single-task single-view baseline methods (consistent with experiments in previous works [Dhillon, 2001]), and even performs better than the multi-view and multi-task baseline methods (without using co-clustering as building block) sometimes. This is because that for non-negative data such as documents, BiCo can boost the performance of sample clustering by the clustering of features and vice versa. Whereas the baseline methods only cluster the samples without the sample-feature mutual boosting.
2. The methods with simple feature concatenation such as LSSMTC(CF), LNKMTC(CF) and MTMVC-MT(CF) do not help much on improving the clustering performance, and they may perform worse than LSSMTC, LNKMTC and MTMVCMT on a single view sometimes. From the comparison between MTMVC and MTMVC-MT(CF), it can be seen that applying multi-view relationship learning is more effective than simply concatenating features. This is consistent with the conclusions in the multi-view clustering literatures.

(3) MTMVC-MV outperforms the multi-view clustering algorithms CoRe and CoTr in most cases, because whether multi-view relationship learning can help improve the clustering performance highly depends on the performance of the basic clustering. CoRe and CoTr use NSC as the ba-

• sic clustering method, while MTMVC-MV uses BiCo. BiCo is shown to perform much better than NSC for non-negative data in most cases in the three tables.
• MTMVC-MT outperforms the multi-task clustering algorithms LSSMTC and LNKMTC in most cases, because: 1) the basic clustering method BiCo used by MTMVC-MT performs better than k-means used by LSSMTC and kkmeans used by LNKMTC; 2) during the multi-task relationship learning, MTMVC-MT uses BiCo to explicitly learn the shared subspace by combining the associated features, whereas LSSMTC does not; 3) there are also some specific characteristics within each task, MTMVC-MT uses the within-view-task clustering part to preserve the knowledge available locally in each task, while LNKMTC only gets the clustering result through a common kernel space.
• MTMVC and MTMVC-CV further improve upon BiCo, MTMVC-MV and MTMVC-MT, thus they perform much better than all the other baseline algorithms. This is because that MTMVC and MTMVC-CV contain a multi-view relationship learning component and a multi-task relationship learning component, thus it can take advantages of both the consistency among different views and the relationship among related tasks, whereas the baselines take advantage of only one (or none) of the two functions. In most cases MTMVC performs better than MTMVC-CV, since it considers the most informative view. In some cases when the most informative view is not so dominant, MTMVC-CV, which takes into account the clustering of all the views and gets a result of trade off, performs a little better than MTMVC. Overall, MTMVC performs better than or comparable to MTMVC-CV.

5 Conclusion

In this paper, we propose a multi-task multi-view clustering (MTMVC) framework which integrates within-view-task clustering, multi-view relationship learning and multi-task relationship learning, and solve the optimization problem by using a gradient ascent method which exploits unitary constraints. As far as we know, this is the first work addressing multi-task multi-view clustering. Experimental results show the superiority of the proposed algorithm over either multitask clustering or multi-view clustering algorithms for multitask clustering of multi-view data. Our algorithm uses bipartite graph co-clustering as the basic clustering method, thus it works for non-negative data. For future work, we will solve the general multi-task multi-view clustering problem.

Acknowledgments

This work was supported by National Science Foundation of China (No. 61272374,61300190).