Clustering

Affinity Propagation clustering algorithm.

Follows the message-passing scheme of Frey and Dueck (2007) as implemented in scikit-learn: similarities are negative squared Euclidean distances, the diagonal of the similarity matrix holds the preference (default: the median of all similarities, diagonal included), and tiny random noise breaks exact ties. Samples with a positive a(k,k) + r(k,k) become exemplars.

The algorithm needs three n-by-n matrices, so memory grows quadratically with the number of samples. If no exemplar emerges, all labels are -1 and a ConvergenceWarning is issued.

Agglomerative (hierarchical) clustering.

Bottom-up clustering that starts with each sample as its own cluster and iteratively merges the closest pair of clusters until nClusters clusters remain (or, with distanceThreshold, until the closest pair is at least that far apart).

Supported linkage criteria: - single: minimum distance between clusters - complete: maximum distance between clusters - average: average distance between clusters - ward: minimizes the total within-cluster variance (Euclidean only)

Distances are Euclidean. The dendrogram is built in O(n^2) time and O(n^2) memory, so very large inputs (tens of thousands of samples) are not practical.

BIRCH clustering algorithm.

Phase 1: Build a CF tree by scanning the data. Each sample joins the closest leaf entry if the merged entry keeps a radius (root mean squared distance of its members to their centroid) of at most threshold; otherwise it starts a new entry. A node with more than branchingFactor entries is split. Phase 2: Apply Ward agglomerative clustering on the leaf entries to produce final nClusters clusters. With nClusters: null this step is skipped and every leaf entry is its own cluster.

The tree is built on mean-centered data, so large constant offsets in X do not degrade the radius test. Samples are labeled by their closest leaf entry.

DBSCAN (Density-Based Spatial Clustering of Applications with Noise).

Clusters points based on density. Points in high-density regions are grouped together, while points in low-density regions are marked as noise.

Algorithm: 1. For each point, find all neighbors within eps distance (the point itself counts) 2. If a point has at least minSamples neighbors, it's a core point 3. Core points and their neighbors form clusters 4. Points not reachable from any core point are noise (label = -1)

A border point that lies within eps of core points from several clusters joins the cluster that reaches it first, so labels of border points depend on the order of the rows in X.

Advantages: - No need to specify number of clusters - Can find arbitrarily shaped clusters - Points in sparse regions are labeled as noise instead of distorting a cluster

Gaussian Mixture Model (GMM).

Fits a mixture of Gaussian distributions using the Expectation-Maximization (EM) algorithm. The covariance structure is chosen with covarianceType: "diag" (the default, one variance per feature and component), "spherical" (one variance per component), "full" (a full matrix per component) or "tied" (one full matrix shared by all components).

Unlike scikit-learn, whose default is "full", the default here stays "diag" so that results of earlier Deepbox versions are unchanged.

Iteration stops when the change of the mean log-likelihood per sample falls below tol. The run with the best log-likelihood out of nInit starts is kept.

K-Means clustering algorithm.

Partitions n samples into k clusters by minimizing the within-cluster sum of squared distances to cluster centroids.

Algorithm: Lloyd's algorithm (iterative refinement), optionally with Elkan's triangle-inequality bounds 1. Initialize k centroids (random or greedy k-means++) 2. Assign each point to nearest centroid 3. Update centroids as mean of assigned points (empty clusters are moved to the points that are farthest from their centroid) 4. Stop when the assignment no longer changes, when the squared centroid shift is at most tol * mean(var(X)), or after maxIter iterations

tol is relative to the average per-feature variance of X, like scikit-learn, so the stopping rule does not depend on the scale of the data.

Time Complexity: O(n * k * i * d) where: - n = number of samples - k = number of clusters - i = number of iterations - d = number of features

Mean Shift clustering with a flat kernel.

Automatically determines the number of clusters from the density landscape of the data. The bandwidth parameter is the radius of the kernel. With bandwidth: "auto" it is estimated from the data the same way as sklearn.cluster.estimate_bandwidth with quantile=0.3.

Clusters are ordered by the number of samples they attract (strongest mode first), so label 0 is always the densest mode.

Mini-Batch K-Means clustering.

A faster variant of KMeans that updates the centroids from small random batches of data (Sculley, 2010): each batch sample is assigned to its nearest centroid, then every centroid moves towards its samples with a per-centroid learning rate of 1 / (number of samples it has seen), so a centroid is the running mean of all samples assigned to it. This trades a small amount of quality for much lower cost on large datasets.

maxIter counts mini-batch steps (one batch per step), not passes over the data as in scikit-learn. Training also stops early when the smoothed batch inertia has not improved for maxNoImprovement consecutive steps, or when the squared centroid movement of a step is at most tol * mean(var(X)) (disabled for the default tol: 0). With nInit > 1 the whole procedure is repeated and the run with the lowest inertia on the full data is kept.

OPTICS clustering algorithm.

Computes the core distances, the reachability distances and the visiting order of every sample (Euclidean metric), then extracts flat clusters from the reachability plot with one of two methods:

- "dbscan" (default): cut the plot at eps, like DBSCAN with that radius. When eps is not given it defaults to maxEps; if maxEps is infinite, the 75th percentile of the finite reachability distances is used instead (a Deepbox heuristic; scikit-learn would put everything in one cluster). - "xi": the Xi-steep method of the paper, with predecessor correction, as in sklearn.cluster.OPTICS(cluster_method="xi"). Cluster boundaries are the steep regions of the plot whose reachability ratio is at least xi.

Noise samples get label -1. As in scikit-learn, minSamples counts the sample itself, and samples are visited in index order, with ties in reachability broken by the lower index.

Distances are computed on the fly, so memory use is linear in the number of samples; run time is quadratic.

Spectral Clustering using graph Laplacian eigenvectors.

Particularly effective for non-convex clusters and clusters with complex shapes that KMeans cannot handle well.

Affinities: - "rbf": exp(-gamma * ||x_i - x_j||^2) between all pairs (default). - "nearest_neighbors": each sample is linked to its nNeighbors nearest samples, counting itself as the first (so it has nNeighbors - 1 neighbors, as in scikit-learn); the graph is symmetrized as (C + C^T) / 2. - "precomputed": X is itself a square, non-negative affinity matrix; it is symmetrized as (A + A^T) / 2 and the diagonal is ignored.

The method builds and decomposes a dense n x n matrix, so memory is O(n^2) and time O(n^3).