Glossary

Adjusted Rand Index (ARI). A measure of agreement between two partitions of the same data (e.g. a clustering and a set of true labels) that corrects the ordinary Rand Index for the agreement expected by chance; see Definition 6.3.

Autoencoder. A neural network trained to reconstruct its own input through a lower-dimensional bottleneck layer, used as a nonlinear alternative to PCA for dimension reduction; see 5.9.

Bandwidth. A tuning parameter (often denoted \(\sigma\) or \(\sigma^2\)) controlling the scale of an RBF kernel or similar weighting function; larger bandwidths treat more distant points as similar.

Bayesian Information Criterion (BIC). A model selection criterion that balances a model’s goodness of fit against its number of parameters, used to choose the number of clusters in a Gaussian mixture model.

Centering matrix. The matrix \({\bf H} = {\bf I} - \frac{1}{N}\vec{1}\vec{1}^T\), which subtracts the column means from a data matrix when applied on the left.

Chart. A local, continuous, invertible map from a neighborhood on a manifold to Euclidean space, used to assign local coordinates to nearby points; see 5.3.

Cluster. A subset of the data whose members are more similar to one another than to members of other subsets.

Clustering. The unsupervised learning task of partitioning data into groups of similar observations; see Chapter 6.

Cophenetic correlation. The correlation between the original pairwise distances in a dataset and the heights at which pairs of points are merged in a hierarchical clustering dendrogram, used to assess how faithfully a dendrogram represents the original distances; see Definition 6.1.

Dendrogram. A tree diagram showing the sequence of merges (or splits) produced by hierarchical clustering.

Dimension reduction. The unsupervised learning task of finding a lower-dimensional representation of data that preserves important relationships.

Elbow plot. A plot of a clustering loss (e.g. total within-cluster variation) against the number of clusters \(k\), used informally to select \(k\) by looking for a bend, or “elbow,” in the curve.

Expectation-Maximization (EM) algorithm. An iterative algorithm for maximum likelihood estimation in models with latent variables, such as Gaussian mixture models, alternating between computing posterior cluster probabilities (E-step) and updating parameters (M-step).

Feature map. The (possibly implicit, possibly infinite-dimensional) function \(\varphi\) associated with a kernel \(k\), such that \(k(\vec{x},\vec{y}) = \varphi(\vec{x})^T\varphi(\vec{y})\).

Gap statistic. A method for choosing the number of clusters \(k\) by comparing the within-cluster variation of the observed data to the within-cluster variation expected under a reference distribution with no clustering structure.

Gaussian Mixture Model (GMM). A probabilistic model for clustering in which the data are assumed to arise from a mixture of several Gaussian distributions, one per cluster; see 6.4.

Geodesic distance. The length of the shortest path between two points that stays on a manifold, as opposed to the (generally shorter) straight-line Euclidean distance between the same two points in the ambient space.

Graph Laplacian. The matrix \({\bf L} = {\bf D} - {\bf W}\), where \({\bf W}\) is a graph’s weighted adjacency matrix and \({\bf D}\) is its diagonal degree matrix; central to Laplacian eigenmaps and spectral clustering.

Hessian eigenmaps (HLLE). A manifold learning method that recovers low-dimensional coordinates from the null space of an estimated Hessian operator on the manifold; see 5.7.

Intrinsic dimension. The true (typically much smaller) dimension of the manifold on which high-dimensional data are assumed to lie.

Isometry. A mapping between two spaces that exactly preserves distances; central to the assumptions behind ISOMAP; see Definition 5.6.

ISOMAP. A manifold learning method that applies classical multidimensional scaling to estimated geodesic distances rather than Euclidean distances; see 5.4.

\(k\)-center. A center-based clustering method that chooses cluster centers (from among the data points) to minimize the maximum distance from any point to its assigned center; see 6.1.

\(k\)-means. A center-based clustering method that partitions data into \(k\) clusters by minimizing the total squared Euclidean distance from each point to its cluster’s mean; see 6.1.

\(k\)-medoids. A center-based clustering method, similar to \(k\)-means, that requires cluster centers to be data points and typically uses (non-squared) distance; see 6.1.

Kernel. A function \(k(\vec{x},\vec{y})\) that computes an inner product in some (possibly implicit) feature space, allowing linear methods to be applied to nonlinear structure without explicitly computing the feature map; see 5.1.

Kernel PCA. A nonlinear extension of PCA obtained by applying PCA to the (implicit) feature-space representation of the data via the kernel trick; see 5.2.

Kernel trick. The technique of replacing inner products \(\vec{x}^T\vec{y}\) with kernel evaluations \(k(\vec{x},\vec{y})\) to obtain a nonlinear version of a linear method; see 5.1.

Laplacian eigenmap. A manifold learning method that recovers low-dimensional coordinates from the eigenvectors of the graph Laplacian, prioritizing the preservation of local neighborhoods; see 5.6.

Linkage. In hierarchical clustering, the rule (e.g. single, complete, average, or Ward) used to compute the dissimilarity between two clusters, each possibly containing more than one point; see 6.3.

Loadings. The eigenvectors of the sample covariance matrix in PCA, giving the directions along which the data vary the most.

Locally Linear Embedding (LLE). A manifold learning method that recovers low-dimensional coordinates by preserving the local, linear reconstruction weights of each point from its nearest neighbors; see 5.5.

Manifold. A space that locally resembles Euclidean space near every point, though it may be globally curved; see Definition 5.1.

Manifold hypothesis. The assumption that observed high-dimensional data lie on or near a manifold of much smaller intrinsic dimension; see 3.1.

Manifold learning. The branch of nonlinear dimension reduction concerned with recovering a low-dimensional manifold structure from high-dimensional data.

Mercer’s condition. The condition a function \(k\) must satisfy to be a valid kernel, namely that every kernel matrix it produces is positive semidefinite; see Theorem 5.1.

Multidimensional Scaling (MDS). A family of dimension reduction methods that find a low-dimensional configuration of points whose pairwise distances best match a given set of original distances or dissimilarities; see 4.4.

Neighborhood graph. A graph connecting each data point to some set of nearby points (e.g. its \(k\) nearest neighbors, or all points within distance \(\epsilon\)), used as the starting point for most manifold learning and spectral methods.

Nonnegative Matrix Factorization (NMF). A dimension reduction method that factors a nonnegative data matrix into the product of two nonnegative matrices, often yielding an interpretable, parts-based representation; see 4.3.

Normalized Mutual Information (NMI). An information-theoretic measure of agreement between two partitions of the same data, normalized to lie between 0 (no shared information) and 1 (perfect agreement); see Definition 6.4.

Principal Component Analysis (PCA). A linear dimension reduction method that finds the directions of maximum variance in the data; see 4.1.

Rand Index. The fraction of all pairs of samples on which two partitions of the data agree (both place the pair together, or both place it apart); see Definition 6.2.

Reconstruction error. The discrepancy between the original data and its approximation after dimension reduction and (if applicable) mapping back to the original space.

Scree plot. A plot of PCA variances (eigenvalues) against component number, used informally to choose the number of components to retain by looking for a bend, or “elbow,” in the curve.

Silhouette score. A measure of how well each point fits its assigned cluster relative to the next-closest cluster, averaged over all points to assess the quality of a clustering; see 6.1.5.3.

Singular Value Decomposition (SVD). A matrix factorization \({\bf X} = {\bf USV}^T\) expressing any matrix as an orthogonal transformation, a scaling, and a second orthogonal transformation; closely related to PCA; see 4.2.

Spectral clustering. A clustering method that partitions data using the eigenvectors of a graph Laplacian built from the data; see 6.5.

Tangent space. The linear subspace that best approximates a manifold at a given point, spanned by the columns of the Jacobian of the manifold map at that point.

UMAP (Uniform Manifold Approximation and Projection). A manifold learning method that constructs a fuzzy neighborhood graph and directly optimizes a low-dimensional embedding to match it, rather than solving an eigenvalue problem; see 5.8.

Unsupervised learning. The branch of machine learning concerned with finding structure in unlabeled data, as opposed to supervised learning’s focus on predicting a labeled outcome; see Chapter 1.