milia.cluster.indices#
Cluster validity indices beyond scikit-learn’s silhouette, Calinski-Harabasz and Davies-Bouldin.
Density-based and model-based indices for clusters that are not convex blobs:
dbcv(): Density-Based Clustering Validation (Moulavi et al., 2014), all-points core distance.dbcvknn(): DBCV with a k-nearest-neighbour core distance; tolerates noise labels (-1).lccv(): Local Cores-based Cluster Validity.dbcs(): Density-based Cluster Silhouette, on geodesic distances over a kNN graph.mmi(): Mean-Max Index.cvflda(): Cluster Validation based on Fisher’s Linear Discriminant Analysis.
Implemented from the papers, with no dependency on kDBCV (which does not import under numpy 2).
Functions
|
Compute Cluster Validation based on Fisher's LDA (CVFLDA). |
|
Compute Density-based Cluster Silhouette (DCS) score. |
|
Density-Based Clustering Validation (Moulavi, Jaskowiak, Campello, Zimek & Sander, SIAM SDM 2014). |
|
Compute Density-Based Clustering Validation (DBCV) score. |
|
Safely divide two floating-point numbers. |
|
Compute Local Cores-Based Cluster Validity (LCCV) index. |
|
Compute Mean-Max Index (MMI) for high-dimensional data. |
|
Minimum mutual-reachability distance between two clusters' core points (Moulavi et al., 2014, Def. |
|
Density sparseness of one cluster and its points' core distances (Moulavi et al., 2014, Defs. |
- milia.cluster.indices.divide(num, denom, default=0.0)#
Safely divide two floating-point numbers.
- Parameters:
- Return type:
- Returns:
The result of num / denom, or default if denom is near zero.
Examples
>>> divide(1.0, 4.0), divide(1.0, 0.0, default=-1.0) (0.25, -1.0)
- milia.cluster.indices.dbcvknn(X, labels, knn=True, minpts=3)#
Compute Density-Based Clustering Validation (DBCV) score.
Evaluates non-convex, arbitrarily shaped clusters by measuring mutual reachability distances over intra-cluster Minimum Spanning Trees (MST).
- Mathematical Formulation:
The density-sparse distance within cluster \(C_i\) is given by:
\[\text{v-spar}(C_i) = \max_{e \in \text{MST}(C_i)} d_{mrb}(e)\]The density-separation between clusters \(C_i\) and \(C_j\) is given by:
\[\text{v-sep}(C_i, C_j) = \min_{p \in C_i, q \in C_j} d_{mrb}(p, q)\]The validity index of cluster \(C_i\) is computed as:
\[V_C(C_i) = \frac{\min_{j \neq i} \text{v-sep}(C_i, C_j) - \text{v-spar}(C_i)} {\max\left(\min_{j \neq i} \text{v-sep}(C_i, C_j), \text{v-spar}(C_i)\right)}\]The final DBCV score is the size-weighted mean across all clusters:
\[\text{DBCV} = \sum_{i=1}^{k} \frac{|C_i|}{N} V_C(C_i)\]
- Parameters:
X (
NDArray[double]) – Feature matrix of shape (n_samples, n_features).labels (
NDArray[int_]) – Cluster labels of shape (n_samples,). Noise points are -1.knn (
bool) – If True, uses k-NN distance for core distance. If False, uses all-points inverse power kernel.minpts (
int) – Neighborhood size \(k\) for k-NN core distance.
- Return type:
- Returns:
DBCV score in range [-1.0, 1.0]. Returns np.nan if invalid.
Examples
>>> rng = np.random.default_rng(0) >>> X = np.vstack([rng.normal(size=(20, 2)), rng.normal(loc=8.0, size=(20, 2))]) >>> dbcvknn(X, np.repeat([0, 1], 20)) > 0.5 True
- milia.cluster.indices.lccv(X, labels, k=10, weighted=True)#
Compute Local Cores-Based Cluster Validity (LCCV) index.
Identifies local density maxima within clusters as core points to evaluate inter-core separation versus intra-core compactness.
- Mathematical Formulation:
Let \(L_i\) be the set of local core points in cluster \(C_i\). Compactness \(Comp(C_i)\) and Separation \(Sep(C_i, C_j)\) are defined as:
\[Comp(C_i) = \frac{1}{|L_i|(|L_i|-1)} \sum_{p, q \in L_i, p \neq q} d(p, q)\]\[Sep(C_i, C_j) = \min_{p \in L_i, q \in L_j} d(p, q)\]The LCCV score is the ratio of weighted mean separation to weighted mean compactness:
\[\text{LCCV} = \frac{\bar{Sep}}{\bar{Comp}}\]
- Parameters:
- Return type:
- Returns:
LCCV index value. Higher values indicate better partitioning.
Examples
>>> rng = np.random.default_rng(0) >>> X = np.vstack([rng.normal(size=(20, 2)), rng.normal(loc=8.0, size=(20, 2))]) >>> lccv(X, np.repeat([0, 1], 20)) > 1 True
- milia.cluster.indices.dbcs(X, labels, k=15)#
Compute Density-based Cluster Silhouette (DCS) score.
Evaluates cluster validity using shortest-path geodesic distances constructed over a \(k\)-nearest neighbors mutual graph.
- Mathematical Formulation:
Let \(d_G(x, y)\) denote the shortest path distance between \(x\) and \(y\) on graph \(G\). For point \(i \in C_a\):
\[a_i = \frac{1}{|C_a|-1} \sum_{j \in C_a, j \neq i} d_G(i, j)\]\[b_i = \min_{b \neq a} \frac{1}{|C_b|} \sum_{j \in C_b} d_G(i, j)\]The DCS score for point \(i\) is given by:
\[s_i = \frac{b_i - a_i}{\max(a_i, b_i)}\]
- Parameters:
- Return type:
- Returns:
Mean DCS score in range [-1.0, 1.0].
Examples
>>> rng = np.random.default_rng(0) >>> X = np.vstack([rng.normal(size=(20, 2)), rng.normal(loc=8.0, size=(20, 2))]) >>> dbcs(X, np.repeat([0, 1], 20)) > 0.5 True
- milia.cluster.indices.mmi(X, labels, metric='sqeuclidean')#
Compute Mean-Max Index (MMI) for high-dimensional data.
- Mathematical Formulation:
Let \(c_i\) be the centroid of cluster \(C_i\).
\[W_k = \frac{1}{k} \sum_{i=1}^{k} \max_{x \in C_i} d(x, c_i)\]\[B_k = \min_{i \neq j} d(c_i, c_j)\]\[\text{MMI} = \frac{B_k}{W_k}\]
- Parameters:
- Return type:
- Returns:
MMI score ratio. Larger values indicate better separation over maximum variance.
Examples
>>> rng = np.random.default_rng(0) >>> X = np.vstack([rng.normal(size=(20, 2)), rng.normal(loc=8.0, size=(20, 2))]) >>> mmi(X, np.repeat([0, 1], 20)) > 1 True
- milia.cluster.indices.cvflda(X, labels, threshold=2.0)#
Compute Cluster Validation based on Fisher’s LDA (CVFLDA).
- Mathematical Formulation:
Projects cluster pairs \((C_i, C_j)\) along Fisher’s optimal linear discriminant \(w\):
\[w = S_W^{-1} (\mu_i - \mu_j)\]Measures variance ratio between combined projection \(z_{ij}\) and within variances:
\[R_{ij} = \frac{\text{Var}(z_{ij})}{\frac{1}{2}(\text{Var}(z_i) + \text{Var}(z_j))}\]Pairs with \(R_{ij} < \lambda\) are flagged for merging.
\[\text{CVFLDA} = 1.0 - \frac{\text{count}(R_{ij} < \lambda)}{\text{total pairs}}\]
- Parameters:
- Return type:
- Returns:
CVFLDA score in range [0.0, 1.0]. 1.0 indicates no invalid cluster pairs.
Examples
>>> rng = np.random.default_rng(0) >>> X = np.vstack([rng.normal(size=(20, 2)), rng.normal(loc=8.0, size=(20, 2))]) >>> cvflda(X, np.repeat([0, 1], 20)) 1.0
- milia.cluster.indices.spread(cluster_points, d)#
Density sparseness of one cluster and its points’ core distances (Moulavi et al., 2014, Defs. 2-3).
Each point’s core distance is a local density estimate. The cluster’s mutual-reachability minimum spanning tree is built from them, and the sparseness is the heaviest edge between two core points (tree degree above 1), so one peripheral point does not overstate the cluster’s spread.
- Parameters:
- Return type:
- Returns:
(sparseness, core_distances, is_core).
Examples
>>> points = np.array([[0.0, 0.0], [1.0, 0.0], [2.0, 0.0], [3.0, 0.0]]) >>> sparseness, cores, is_core = spread(points, 2) >>> is_core.tolist() [False, True, True, False]
- milia.cluster.indices.separation(points_i, is_core_i, core_dist_i, points_j, is_core_j, core_dist_j)#
Minimum mutual-reachability distance between two clusters’ core points (Moulavi et al., 2014, Def. 4).
- Parameters:
points_i (
ndarray) – Points of the first cluster.is_core_i (
ndarray) – Core-point mask of the first cluster.core_dist_i (
ndarray) – Core distances of the first cluster.points_j (
ndarray) – Points of the second cluster.is_core_j (
ndarray) – Core-point mask of the second cluster.core_dist_j (
ndarray) – Core distances of the second cluster.
- Return type:
- Returns:
The density separation of the two clusters.
Examples
>>> a, b = np.array([[0.0, 0.0], [1.0, 0.0]]), np.array([[5.0, 0.0], [6.0, 0.0]]) >>> core = np.array([True, True]) >>> separation(a, core, np.ones(2), b, core, np.ones(2)) 4.0
- milia.cluster.indices.dbcv(X, labels)#
Density-Based Clustering Validation (Moulavi, Jaskowiak, Campello, Zimek & Sander, SIAM SDM 2014).
Silhouette, Calinski-Harabasz, and Davies-Bouldin all measure separation via raw distance, which implicitly assumes roughly convex, similar-density clusters; documented directly (not assumed) to fail on arbitrarily-shaped ones, exactly what a UMAP/PaCMAP/t-SNE embedding can legitimately produce (elongated or connected structure, not just blobs). DBCV scores each real cluster’s own internal sparseness (a mutual- reachability minimum spanning tree, not raw distance) against its own real separation from its nearest other cluster’s own such structure, so it does not share that convexity assumption; a genuine complement to the other three, not a replacement (a later benchmark still finds silhouette/Davies-Bouldin the more informative pair specifically for convex clusters).
Reimplemented directly from the paper (verified numerically against the reference kDBCV package on several synthetic cases before use), not depending on kDBCV itself: its 1.0.0 release pins numpy<2 and hardcodes the now-removed np.float_/np.int_ aliases, confirmed directly to raise AttributeError on import under this project’s own numpy>=2.0 floor, not merely an overly cautious version pin.
- Parameters:
- Return type:
- Returns:
The real, size-weighted average of every cluster’s own validity score, bounded [-1, 1], higher is better. NaN if fewer than 2 real clusters are present, or if any one of them has fewer than 3 points. A tree on >= 3 nodes always has at least one node with degree > 1 (a “core” point, by this metric’s own definition below); a 2-point cluster’s own minimum spanning tree is a single edge, both endpoints degree 1, leaving no real core point to measure separation from at all, the same real precondition the reference implementation enforces by reassigning 1- and 2-point clusters to noise before scoring, not merely a conservative floor picked here.
Examples
>>> rng = np.random.default_rng(0) >>> X = np.vstack([rng.normal(size=(20, 2)), rng.normal(loc=8.0, size=(20, 2))]) >>> dbcv(X, np.repeat([0, 1], 20)) > 0.5 True