Co-Clustering

Gérard Govaert is Professor at the University of Technology of Compiègne, France. He is also a member of the CNRS Laboratory Heudiasyc (Heuristic and diagnostic of complex systems). His research interests include latent structure modeling, model selection, model-based cluster analysis, block clustering and statistical pattern recognition. He is one of the authors of the MIXMOD (MIXtureMODelling) software.Mohamed Nadif is Professor at the University of Paris-Descartes, France, where he is a member of LIPADE (Paris Descartes computer science laboratory) in the Mathematics and Computer Science department. His research interests include machine learning, data mining, model-based cluster analysis, co-clustering, factorization and data analysis.

• Acknowledgment xiIntroduction xiiiI.1. Types and representation of data xiiiI.1.1. Binary data xivI.1.2. Categorical data xivI.1.3. Continuous data xvI.1.4. Contingency table xviiI.1.5. Data representations xixI.2. Simultaneous analysis xxI.2.1. Data analysis xxI.2.2. Co-clustering xxiiI.2.3. Applications xxiiiI.3. Notation xxviiI.4. Different approaches xxviiiI.4.1. Two-mode partitioning xxviiiI.4.2. Two-mode hierarchical clustering xxxviiI.4.3. Direct or block clustering xxxixI.4.4. Biclustering xxxixI.4.5. Other structures and other aims xlivI.5. Model-based co-clustering xlviI.6. Outline xlixChapter 1. Cluster Analysis 11.1. Introduction 11.2. Miscellaneous clustering methods 41.2.1. Hierarchical approach 41.2.2. The k-means algorithm 51.2.3. Other approaches 71.3. Model-based clustering and the mixture model 111.4. EM algorithm 151.4.1. Complete data and complete-data likelihood 161.4.2. Principle 171.4.3. Application to mixture models 181.4.4. Properties 191.4.5. EM: an alternating optimization algorithm 191.5. Clustering and the mixture model 201.5.1. The two approaches 201.5.2. Classification likelihood 211.5.3. The CEM algorithm 221.5.4. Comparison of the two approaches 221.5.5. Fuzzy clustering 241.6. Gaussian mixture model 261.6.1. The model 261.6.2. CEM algorithm 281.6.3. Spherical form, identical proportions and volumes 291.6.4. Spherical form, identical proportions but differing volumes 301.6.5. Identical covariance matrices and proportions 311.7. Binary data 321.7.1. Binary mixture model 321.7.2. Parsimonious model 331.7.3. Examples of application 351.8. Categorical variables 361.8.1. Multinomial mixture model 361.8.2. Parsimonious model 381.9. Contingency tables 411.9.1. MNDKI2 algorithm 411.9.2. Model-based approach 431.9.3. Illustration 471.10. Implementation 491.10.1. Choice of model and of the number of classes 511.10.2. Strategies for use 511.10.3. Extension to particular situations 521.11. Conclusion 53Chapter 2. Model-Based Co-Clustering 552.1. Metric approach 552.2. Probabilistic models 572.3. Latent block model 592.3.1. Definition 592.3.2. Link with the mixture model 612.3.3. Log-likelihoods 622.3.4. A complex model 632.4. Maximum likelihood estimation and algorithms 672.4.1. Variational EM approach 692.4.2. Classification EM approach 722.4.3. Stochastic EM-Gibbs approach 732.5. Bayesian approach 752.6. Conclusion and miscellaneous developments 76Chapter 3. Co-Clustering of Binary and Categorical Data 793.1. Example and notation 803.2. Metric approach 823.3. Bernoulli latent block model and algorithms 843.3.1. The model 843.3.2. Model identifiability 853.3.3. Binary LBVEM and LBCEM algorithms 863.4. Parsimonious Bernoulli LBMs 903.5. Categorical data 913.6. Bayesian inference 933.7. Model selection 963.7.1. The integrated completed log-likelihood (ICL) 963.7.2. Penalized information criteria 973.8. Illustrative experiments 983.8.1. Townships 983.8.2. Mero 1013.9. Conclusion 105Chapter 4. Co-Clustering of Contingency Tables 1074.1. Measures of association 1084.1.1. Phi-squared coefficient 1094.1.2. Mutual information 1114.2. Contingency table associated with a couple of partitions 1134.2.1. Associated distributions 1134.2.2. Associated measures of association 1164.3. Co-clustering of contingency table 1194.3.1. Two equivalent approaches 1194.3.2. Parameter modification of criteria 1214.3.3. Co-clustering with the phi-squared coefficient 1244.3.4. Co-clustering with the mutual information 1294.4. Model-based co-clustering 1314.4.1. Block model for contingency tables 1334.4.2. Poisson latent block model 1374.4.3. Poisson LBVEM and LBCEM algorithms 1384.5. Comparison of all algorithms 1404.5.1. CROKI2 versus CROINFO 1424.5.2. CROINFO versus Poisson LBCEM 1424.5.3. Poisson LBVEM versus Poisson LBCEM 1444.5.4. Behavior of CROKI2, CROINFO, LBCEM and LBVEM 1474.6. Conclusion 149Chapter 5. Co-Clustering of Continuous Data 1515.1. Metric approach 1525.1.1. Measure of information 1535.1.2. Summarized data associated with partitions 1535.1.3. Objective function 1565.1.4. CROEUC algorithm 1575.2. Gaussian latent block model 1595.2.1. The model 1595.2.2. Gaussian LBVEM and LBCEM algorithms 1605.2.3. Parsimonious Gaussian latent block models 1615.3. Illustrative example 1635.4. Gaussian block mixture model 1685.4.1. The model 1695.4.2. GBEM algorithm 1705.5. Numerical experiments 1735.5.1. GBEM versus CROEUC and EM 1745.5.2. Effect of the size of data 1755.6. Conclusion 175Bibliography 177Index 199