Clustering: Theoretical and Practical Aspects

Description

This unique compendium gives an updated presentation of clustering, one of the most challenging tasks in machine learning. The book provides a unitary presentation of classical and contemporary algorithms ranging from partitional and hierarchical clustering up to density-based clustering, clustering of categorical data, and spectral clustering.Most of the mathematical background is provided in appendices, highlighting algebraic and complexity theory, in order to make this volume as self-contained as possible. A substantial number of exercises and supplements makes this a useful reference textbook for researchers and students. Contents Preface 1. Introduction 2. Set-Theoretical Preliminaries 2.1 Introduction 2.2 Sets and Set Operations 2.3 Sequences 2.4 Multisets 2.5 Closure Systems 2.6 Permutations 2.7 Relations 2.8 Partially Ordered Sets 2.9 The Poset of Partitions of a Set 2.10 Boolean Matrices 2.11 Galois Connections and Formal Concepts 2.12 Exercises and Supplements 2.13 Bibliographical Comments 3. Dissimilarities, Metrics, and Ultrametrics 3.1 Introduction 3.2 Dissimilarity Spaces 3.3 Similarities and Dissimilarities between Sets 3.4 Norms and Metrics on Rn 3.5 The Geometry of Ultrametric Spaces 3.6 Matrices on Semirings 3.7 Entropy 3.7.1 Partition Entropy 3.7.2 Generalized Entropy 3.7.3 Conditional Entropy and Entropy Gain 3.7.4 The Entropic Metric Space of Partitions of Finite Sets 3.8 Exercises and Supplements 3.9 Bibliographical Comments 4. Convexity 4.1 Introduction 4.2 Convex Sets 4.3 Operations on Convex Sets 4.4 Extreme Points 4.5 Convex Functions 4.6 Exercises and Supplements 4.7 Bibliographical Comments 5. Graphs and Hypergraphs 5.1 Introduction 5.2 Vertices, Edges and Weights 5.3 Trees 5.3.1 Heaps 5.3.2 kd-Trees 5.4 Bipartite Graphs 5.5 Co-cycles 5.6 GF(2)-Linear Spaces and Graphs 5.7 Graphs and Matrices 5.8 Directed Graphs 5.9 From Matrices to Graphs 5.10 Minimum Spanning Trees 5.11 Matrices and Dissimilarities 5.12 Planar Graphs 5.13 Voronoi Diagrams 5.14 Graph Searching 5.15 Flows in Graphs 5.16 Hypergraphs 5.17 Exercises and Supplements 5.18 Bibliographical Comments 6. Partitional Clustering 6.1 Introduction 6.2 Inertia of a Set of Vectors 6.3 The k-Means Algorithm 6.4 Clustering and Matrices 6.5 The PAM Algorithm 6.6 Kernel k-Means Clustering 6.7 A Geometric Approach to k-Clustering 6.8 Clustering and Singular Value Decomposition of Matrices 6.9 Vector Quantization and Matching Pursuit 6.10 Partitional Clustering in R 6.11 Clustering in Python 6.12 Exercises and Supplements 6.13 Bibliographical Comments 7. Statistical Approaches to Clustering 7.1 Introduction 7.2 Sampling 7.3 Likelihood Function 7.4 Data Density Estimations 7.5 Density Kernels for Unidimensional Data 7.6 Density Kernels for Multidimensional Data 7.7 Mean Shift Clustering 7.8 Expectation Maximization and Clustering 7.9 The EM Algorithm for Unidimensional Data 7.10 Exercises and Supplements 7.11 Bibliographical Comments 8. Hierarchical Clustering 8.1 Introduction 8.2 Ultrametrics, Hierarchies, and Partition Chains 8.3 Ultrametrics and Minimum Spanning Trees 8.4 The Single-Link Algorithm 8.5 Other Hierarchical Clustering Algorithms 8.6 Hierarchical Clustering in R 8.7 Hierarchical Clustering in Python 8.8 Divisive Hierarchical Clustering 8.9 The CURE Algorithm 8.10 Complexity of Hierarchical Clustering 8.11 Exercises and Supplements 8.12 Bibliographical Comments 9. Density-based Clustering 9.1 Introduction 9.2 Core, Border and Noise Objects in DBSCAN 9.3 The OPTICS Algorithm 9.4 Density-based Clustering in R 9.5 Density-based Clustering in Python 9.6 Subspace Clustering 9.7 Exercises and Supplements 9.8 Bibliographical Comments 10. Categorical Data Clustering 10.1 Introduction 10.2 Market Basket Data and Clustering Sets 10.3 The ROCK Algorithm 10.4 The CACTUS Approach 10.5 An Entropy-based Framework 10.6 Exercises and Supplements 10.7 Bibliographical Comments 11. Spectral Clustering 11.1 Introduction 11.2 Data and Graphs 11.3 The Ordinary Spectrum of a Graph 11.4 The Laplacian Spectrum of a Graph 11.5 Cuts, Separators, and Clusterings 11.6 Spectral Clustering Algorithms 11.7 Spectral Clustering in R Exercises and Supplements Bibliographical Comments 12. Correlation and Consensus Clustering 12.1 Introduction 12.2 Graphs and Correlation Clustering 12.3 The NP-Completeness of Correlation Clustering 12.4 Disagreements Minimization 12.5 Consensus Clustering 12.6 Exercises and Supplements 12.7 Bibliographical Comments 13. Clustering Quality 13.1 Introduction 13.2 Internal Criteria 13.2.1 The Davies-Bouldin Criterion 13.2.2 The Dunn Quality Indices 13.2.3 The Silhouette Coefficient 13.3 External Criteria 13.4 Pairwise Measures 13.5 Graph Clustering and Modularity 13.6 Exercises and Supplements 13.7 Bibliographical Comments 14. Clustering Axiomatization 14.1 Introduction 14.2 Clustering Functions 14.3 An Impossibility Result 14.4 Antichains of Partitions 14.5 Centroid-based Clustering and Consistency 14.6 Partitioning Functions 14.7 An Axiomatization of Clustering Quality Measures 14.8 Exercises and Supplements 15. Biclustering 15.1 Introduction 15.2 Reorderable Matrices 15.3 A Boolean Approach to Binary Data Sets Biclustering 15.4 The Cheng and Church Algorithm 15.5 Numerical Aspects of Biclustering of Binary Data Sets 15.6 Exercises and Supplements 16. Semi-supervised Clustering 16.1 Introduction 16.2 A Semi-Supervised Variant of k-Means 16.3 Constraint Propagation 16.4 Semi-Supervised Hierarchical Clustering 16.5 Learning Mahalanobis Metrics 16.6 Exercises and Supplements 16.7 Bibliographical Comments Appendix A Special Functions and Applications A.1 Introduction A.2 Euler’s Functions A.3 Spheres and Cubes in Rn Appendix B Linear Algebra B.1 Introduction B.2 Matrices B.3 Matrix Rank B.4 Matrix Differentiation B.5 Eigenvalues of Matrices B.6 Optimization and Eigenvalues B.7 Matrix Norms B.8 Unitary Matrices and Orthogonal Projections B.9 Positive Definite Matrices B.10 Singular Values of Matrices B.11 CS Decomposition B.12 Geometry of Subspaces B.13 Matrix Approximation via SVD Appendix C Linear Programming C.1 Introduction C.2 The Fourier-Motzkin Elimination C.3 Primal and Dual LP Problems C.4 The Bin Packing Problem C.5 Bibliographical Comments Appendix D NP Completeness D.1 Introduction D.2 Words and Problems D.3 Problems and Algorithms D.4 Variables and Propositional Formulas D.5 Turing Machines D.6 NP Complete Problems D.7 Parameterized Problems D.8 Approximation Algorithms D.9 Bibliographical Comments Bibliography Index