necom eval partition

This document describes the design philosophy, metrics, and selection guidance for necom eval partition. For command-line options and usage examples, see docs/help/eval/partition.md.

Design Philosophy

necom adopts a componentized design philosophy, separating cluster generation from evaluation. This differs from the integrated design of the Python package clusteval:

• Python clusteval: The fit() method internally performs Grid Search (trying different $k$ or $\epsilon$), computes internal metrics (e.g., Silhouette), and returns the optimal result.
• necom workflow:
  1. Generate: Use necom cut scan-simple to generate a series of candidate partitions (necom clust dbscan’s --scan is not yet implemented).
  2. Evaluate: Use necom eval partition to compute evaluation metrics for these candidates in batch.
  3. Decide: The user selects the optimal parameters based on metrics (e.g., Silhouette peak, Elbow point).
• Complementary:
  • necom eval tree [planned]: Focuses on consistency between tree structure and grouping (geometry/evolution).
  • necom eval partition: Focuses on the statistical validity of partitions, supporting external (two-group comparison) and internal (single group + matrix/coordinates/tree) evaluation.
• Scenarios:
  • Algorithm comparison: Compare result differences between MCL and K-Medoids on the same dataset.
  • Benchmarking: Compare clustering results against known standard classifications (Ground Truth) to compute accuracy.
  • Parameter tuning: Compare stability of clustering results under different parameters (e.g., eps or inflation).

This design allows evaluation tools to exist independently of clustering algorithms, supporting clustering results from any source.

Input Validation

necom eval partition validates inputs before computing metrics to avoid silent failures:

• Empty partitions: A single partition or any batch group with no samples is rejected.
• External evaluation (--other / --truth): The two partitions must contain exactly the same sample set. The command errors out rather than intersecting keys silently.
• Internal evaluation (--matrix, --tree, --coords): Every sample in the partition must be present in the distance source. Missing samples produce a clear error instead of NaN metrics.
• --no-singletons: Singleton clusters are removed from the reference partition first; samples that become unreferenced are excluded from evaluation, and the remaining sample sets are still required to match.

Output Format

necom eval partition writes a TSV with a header row followed by one result row.

• External evaluation: one row of pair-based metrics (ari, ami, homogeneity, completeness, v_measure, fmi, nmi, mi, ri, jaccard, precision, recall).
• Distance-based internal evaluation: silhouette, dunn, c_index, gamma, tau, davies_bouldin.
• Coordinate-based internal evaluation: davies_bouldin, calinski_harabasz, pbm, ball_hall, xie_beni, wemmert_gancarski.
• Batch mode (--input-format long): one row per Group, with the Group column preserved as the first column.
• Non-finite metric values (NaN, +Infinity, or -Infinity) are emitted as NA to keep the TSV parseable. This occurs in degenerate cases such as Calinski-Harabasz when clusters are perfectly compact and well-separated, or Xie-Beni when two centroids coincide.

Core Metrics

Clustering evaluation metrics usually fall into two categories: external validity (requires Ground Truth or a reference partition) and internal validity(depends only on the geometry/statistics of the data).

1. External Validity

Used to compare consistency between two clustering results, or to evaluate how well a result matches the true classification.

1.1 Pair-Based

Focuses on whether sample pairs remain in the same/different groups across two partitions.

• ARI (Adjusted Rand Index)
  • Definition: Rand Index corrected for chance.
  • Principle: Counts sample pairs that are in the same or different groups in both partitions, and subtracts the expected value under random assignment.
  • Range: [-1, 1]. 1 means perfect agreement, 0 means random level, negative values mean worse than random.
  • Advantages:
    • Interpretable: 0 is the random baseline, intuitive.
    • Symmetric: ARI(A, B) == ARI(B, A).
  • Disadvantages: Insensitive to internal cluster structure (e.g., shape).
  • Applicable: General scenarios with imbalanced cluster sizes and many clusters.
• RI (Rand Index)
  • Definition: Proportion of correctly classified sample pairs.
  • Range: [0, 1].
  • Disadvantages: Not corrected for chance. As the number of clusters increases, the RI of random partitions also approaches 1, reducing discriminative power. Generally not recommended for standalone use.
• Jaccard Index (Pair-wise)
  • Definition: Among all sample pairs considered in the same group by either partition (TP + FP + FN), the proportion considered in the same group by both partitions (TP).
  • Formula: $J = \frac{TP}{TP + FP + FN}$.
  • Meaning: The Jaccard similarity between set $S_1$ (same-group pairs in P1) and set $S_2$ (same-group pairs in P2).
• Precision (Pair-wise)
  • Definition: Among all sample pairs considered in the same group by the predicted partition (P1), the proportion also considered in the same group by the true partition (P2).
  • Formula: $P = \frac{TP}{TP + FP}$.
• Recall (Pair-wise)
  • Definition: Among all sample pairs considered in the same group by the true partition (P2), the proportion also considered in the same group by the predicted partition (P1).
  • Formula: $R = \frac{TP}{TP + FN}$.
• FMI (Fowlkes-Mallows Index)
  • Definition: Geometric mean of Precision and Recall.
  • Principle: $FMI = \sqrt{\frac{TP}{TP+FP} \times \frac{TP}{TP+FN}}$.
  • Range: [0, 1].
  • Applicable: When both Precision and Recall are important.

1.2 Information-Theoretic

Focuses on the amount of information (entropy) shared between two partitions.

• AMI (Adjusted Mutual Information)
  • Definition: Mutual Information corrected for chance.
  • Principle: Computes shared information between two partitions based on entropy, and subtracts the random expectation.
  • Range: [-1, 1] (typically [0, 1]). 1 means perfect agreement, 0 means random, negative values mean worse than random (e.g., anti-correlated partitions).
  • Advantages:
    • More robust when the number of clusters is very large (even close to the sample size).
    • Captures complex non-linear relationships.
  • Applicable: Small samples, many clusters (Large K) scenarios.
• NMI (Normalized Mutual Information)
  • Definition: Normalized Mutual Information.
  • Principle: $NMI = \frac{MI(U, V)}{\sqrt{H(U) \cdot H(V)}}$ (geometric mean) or $\frac{2 \cdot MI}{H(U) + H(V)}$ (arithmetic mean). necom uses the geometric mean.
  • Range: [0, 1].
  • Disadvantages: Not corrected for chance.
  • Applicable: Scenarios with balanced cluster size distributions.
  • Implementation note: Because NMI is a ratio of MI to the geometric mean of the two entropies, the choice of logarithm base cancels out. The value is therefore independent of whether natural logs or base-2 logs are used.
• MI (Mutual Information)
  • Definition: Mutual information between two partitions.
  • Principle: $MI(U, V) = \sum \sum P(u,v) \log \frac{P(u,v)}{P(u) P(v)}$.
  • Range: [0, +∞).
  • Disadvantages: Difficult to interpret directly; strongly affected by partition entropy. Usually used as an intermediate step for AMI/NMI.
  • Implementation note: The implementation uses natural logarithms (matching scikit-learn), so the raw MI value (in nats) equals the base-2 value (in bits) multiplied by ln(2) (≈ 0.693). Normalized metrics (NMI, AMI, V-Measure) are unaffected because they are ratios.
• Homogeneity
  • Definition: Does each cluster contain only members of a single class? (Similar to Precision, requiring clusters to be “pure.”)
  • Principle: Based on conditional entropy $H(C|K)$. If $H(C|K)=0$, Homogeneity is 1.
  • Range: [0, 1].
• Completeness
  • Definition: Are all members of a class assigned to the same cluster? (Similar to Recall, requiring clusters to be “complete.”)
  • Principle: Based on conditional entropy $H(K|C)$. If $H(K|C)=0$, Completeness is 1.
  • Range: [0, 1].
• V-Measure
  • Definition: Harmonic mean of Homogeneity and Completeness.
  • Range: [0, 1].
  • Disadvantages: Not corrected for chance. With small samples or many clusters, scores tend to be high.
  • Applicable: When you need to analyze the source of clustering error (over-fragmentation vs. over-mixing).

2. Internal Validity

Used to evaluate the quality of a clustering result itself (compactness and separation) without Ground Truth.

2.1 Distance-Based

Requires a distance matrix (--matrix) or a phylogenetic tree (--tree).

• Silhouette Coefficient
  • Principle: For each sample $i$, compute its average distance to samples in the same cluster $a(i)$ and its average distance to the nearest other cluster $b(i)$. $s(i) = (b - a) / \max(a, b)$.
  • Range: [-1, 1].
    • Near 1: sample is well clustered (close to same cluster, far from others).
    • 0: sample lies on a cluster boundary.
    • Negative: sample may be mis-clustered.
  • Implementation note: Following scikit-learn’s convention, samples in singleton clusters contribute $s(i) = 0$ to the average (but are still counted in the divisor $N$). The score is 0.0 when there are fewer than 2 clusters or when every sample is its own cluster.
  • Advantages: Intuitive; balances cohesion and separation.
  • Disadvantages: High computational complexity ($O(N^2)$); requires optimization for large-scale data.
• Dunn Index
  • Principle: Ratio of the minimum between-cluster distance to the maximum within-cluster diameter.
  • Range: [0, +∞). Larger is better.
  • Boundary cases: If the maximum intra-cluster diameter is zero (perfectly compact clusters) and the minimum inter-cluster distance is positive, the score is infinite and is reported as NA. If both are zero, the score is 0.0.
  • Advantages: Simple and intuitive.
  • Disadvantages: Extremely sensitive to noise (because it relies on min/max).
• C-Index
  • Principle: Compares the sum of within-cluster distances with the sum of the smallest $N_W$ distances in the entire dataset ($N_W$ is the number of within-cluster pairs).
  • Range: [0, 1]. Smaller is better.
  • Boundary cases: Returns 0.0 when there are fewer than 2 samples, when there are no within-cluster pairs (all singletons), when all pairs are within-cluster (single cluster), or when all pairwise distances are equal (zero variance in the denominator).
  • Disadvantages: High computational complexity ($O(N^2 \log N)$), requiring sorting of all pairwise distances.
• Hubert’s Gamma
  • Principle: Correlation between the distance matrix and a binary clustering matrix (0 = same cluster, 1 = different clusters).
  • Range: [-1, 1]. Larger is better (Y=1 means different clusters; larger Gamma means between-cluster distances exceed within-cluster distances more strongly).
  • Boundary cases: Returns 0.0 when there are fewer than 2 samples, or when the distance matrix or the clustering matrix has zero variance (degenerate cases such as all-equal distances or a single-cluster partition).
• Kendall’s Tau
  • Principle: Rank correlation coefficient between the distance matrix and the clustering matrix.
  • Range: [-1, 1]. Larger is better.
  • Boundary cases: Returns 0.0 when there are fewer than 2 samples, or when the denominator is zero (degenerate cases with no usable pair comparisons).
• Davies-Bouldin Index (DBI)
  • Principle: Same idea as the coordinate version, but uses medoids (cluster members with the smallest average intra-cluster distance) as cluster representatives because coordinates are not available. scatter_i is the average distance from cluster members to the medoid, and inter-cluster distance is the distance between medoids.
  • Range: [0, +∞). Smaller is better.
  • Boundary cases: If two medoids coincide and at least one cluster has non-zero scatter, the similarity is undefined; a large finite proxy (1e10) is used so the TSV remains parseable.

2.2 Coordinate-Based

Requires a coordinate matrix (--coords). Suitable for Euclidean-space data.

• Davies-Bouldin Index (DBI)
  • Principle: Computes the “similarity” of each cluster pair (within-cluster dispersion sum / centroid distance), then takes the mean of each cluster’s worst (largest) similarity.
  • Range: [0, +∞). Smaller is better.
  • Boundary cases: If two cluster centroids coincide and at least one has non-zero scatter, the similarity is undefined (infinite). The implementation substitutes a large finite proxy (1e10) so the TSV remains parseable.
  • Advantages: Faster than Silhouette.
  • Applicable: Evaluating centroid-based clustering algorithms.
• Calinski-Harabasz Index (CH)
  • Principle: Ratio of between-cluster dispersion (BGSS) to within-cluster dispersion (WGSS).
  • Range: [0, +∞). Larger is better.
  • Advantages: Fast to compute.
  • Boundary cases:
    • If every point is identical (WGSS == 0 and BGSS == 0), the input is degenerate and the score is 0.0.
    • If clusters are perfectly compact and well-separated (WGSS == 0 but BGSS > 0), the score is infinite and is reported as NA to keep the TSV parseable.
• PBM Index
  • Principle: Composite index based on total dispersion, within-cluster dispersion, and maximum centroid distance.
  • Range: [0, +∞). Larger is better.
  • Boundary cases:
    • If within-cluster dispersion is zero while total dispersion is positive (perfectly compact clusters), the score is infinite and is reported as NA to keep the TSV parseable.
    • If both within-cluster and total dispersion are zero (all points coincide with the global centroid — degenerate input), the score is 0.0.
• Ball-Hall Index
  • Principle: Mean of average within-cluster dispersions.
  • Range: [0, +∞). Smaller is better (more compact).
• Xie-Beni Index
  • Principle: Ratio of within-cluster compactness to between-cluster separation (minimum centroid distance).
  • Range: [0, +∞). Smaller is better.
  • Boundary cases: If the closest pair of cluster centroids coincide, separation is zero and the score is infinite; it is reported as NA to keep the TSV parseable.
• Wemmert-Gancarski Index
  • Principle: Compactness index based on relative distances (distance to own centroid / distance to nearest other centroid).
  • Range: [0, 1]. Larger is better.
  • Boundary cases: If a point coincides with another cluster’s centroid (inter-cluster distance is zero), a penalty (10.0) is applied to the ratio so the index remains finite.

Metric Selection Guide

See Also

• necom clust for command overview, supported algorithms, and partition/matrix/coordinate format conventions.
• docs/help/eval/partition.md for the command-line help text, including available options and usage examples.