chapter  23
26 Pages

Two-Mode Partitioning and Multipartitioning

ByMaurizio Vichi

Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 519 23.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 520 23.2 The Two-Mode Cluster . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 521

23.2.1 Models for Two-Mode Clusters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 521 23.3 Two-Mode Partition: Single and Multipartition . . . . . . . . . . . . . . . . . . . . . . . . . 523

23.3.1 Models for Two-Mode Single-Partition: The Double K-Means . . . . . . . . 525 23.4 Isolation of Two-Mode Clusters and Their Measures . . . . . . . . . . . . . . . . . . . . . 527

23.4.1 Heterogeneity within Two-Mode Clusters . . . . . . . . . . . . . . . . . . . . . . . 527 23.4.2 Measures of Heterogeneity within Two-Mode Clusters . . . . . . . . . . . . . 528 23.4.3 Within Clusters Criteria for Two-Mode Single-Partitioning . . . . . . . . . . 530 23.4.4 Isolation between Two-Mode Clusters . . . . . . . . . . . . . . . . . . . . . . . . . 530 23.4.5 Measures of Isolation between Two-Mode Clusters . . . . . . . . . . . . . . . . 531 23.4.6 Between Clusters Criteria for Two-Mode Single-Partitioning . . . . . . . . . 532 23.4.7 Links between Partitioning Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . 533

23.4.7.1 Decomposition of the Total Deviance of X for a Given Two-Mode Partition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 533

23.4.7.2 Decomposition of the Total Cut (Degree or Weight) of X . . . . . 533 23.4.7.3 Decomposition of the Total Normalized Cut

(Degree or Weight) of X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 533 23.5 Estimation and Algorithm for Double K -Means Model . . . . . . . . . . . . . . . . . . . 534

23.5.1 Least-Squares Estimation of DKM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 534 23.5.2 Maximum Likelihood and Other Methods of Estimation of DKM . . . . . 537

23.6 Two-Mode Multipartitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 540 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 540

Two-mode clustering, coclustering, biclustering, and subspace clustering are similar terms used to describe the activity of clustering simultaneously the two-modes, that is, rows and columns, of a rectangular data matrix or a rectangular (dis)similarity matrix. Methodologies in this field of research differ from classical cluster analysis methods, where the assignments of objects to clusters are based on the entire set of variables and, vice versa, the assignments of variables to clusters are based on the total set of objects. The motivation for the increasing use of two-mode clustering methodologies resides in the fact that, frequently groups of objects may be homogeneous only within subsets of variables, while

of

variables may be strongly associated only on subsets of objects. In microarray cluster analysis, for example, the clustering on tissue samples is coregulated within subsets of samples and groups of samples share a common gene expression pattern only for some subsets of genes; in market basket analysis customers have similar preference patterns only on subsets of products and, vice versa, classes of products may more frequently be consumed and preferred by subgroups of customers; on movie recommender systems generally reviewers are homogeneous on subset of movies and vice versa movies are generally chosen by homogeneous typologies of people with similar profiles of preferences. To obtain a two-mode partitioning researchers may think to apply on the data matrix X simply an algorithm for partitioning rows and independently an algorithm for partitioning columns, thus splitting X into rectangular blocks. However, with this simple approach the partitioning of objects would be optimal for the entire profile of variables and the partitioning of variables would be ideal for the entire set of objects, but, this is what we wish to avoid, having hypothesized homogeneous groups of objects only within subset of variables, while variables strongly associated only on subsets of objects. Thus, in general the independent application of a clustering methodology on the rows and columns of a data matrix is not fully appropriate for two-mode clustering and suitable methodologies are needed. In this paper, we wish to overview a large amount of new literature proposed in the last years in two-mode clustering due to the need of data reduction, bioinformatics applications and text-mining analyses.