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.
Author(s): Dan A. Simovici
Publisher: World Scientific Publishing
Year: 2021
Language: English
Pages: 881
City: Singapore
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
