Sparse Kmeans Eval

sparse-kmeans-eval

Simple and Scalable Sparse k-means Clustering via Feature Ranking — Zhang et al. (2020) (arXiv:2002.08541, 2020)

What this evaluates

Evaluates the clustering quality and feature selection capability of sparse k-means algorithms on biological and standard machine learning benchmark datasets. It probes how well the method separates known classes and selects discriminative features compared to baseline k-means variants.

Datasets

• Mice protein expression dataset — total 1080; splits: full (1080)
• UCI/Keel/ASU Benchmark Datasets — total ?; splits: full (-1)

Metrics

• Normalized Mutual Information (NMI) (primary) — range: [0, 1]
  • NMI = I(C;Y) / sqrt(H(C)H(Y)), where I is mutual information and H is entropy between cluster assignments C and true labels Y.
• Mixed Nodes — range: count
  • Count of clusters containing samples from more than one true class.

Input / output format

Input: Feature matrix (n samples × d features) with known class labels for post-hoc evaluation.

Output: Cluster assignments for each sample (integer labels 1..k) and a binary feature selection mask indicating selected features.

Scoring recipe

def evaluate_clustering(cluster_labels, true_labels, k):
    nmi = normalized_mutual_info_score(cluster_labels, true_labels)
    mixed_nodes = 0
    total_mixed = 0
    for c in range(k):
        mask = (cluster_labels == c)
        if len(np.unique(true_labels[mask])) > 1:
            mixed_nodes += 1
            total_mixed += np.sum(mask)
    return {'NMI': nmi, 'Mixed Nodes': mixed_nodes, 'Total Mixed': total_mixed}

Common pitfalls

• Non-deterministic initialization requires averaging over multiple runs (paper specifies 20 trials with k-means++ seeding).
• Sparsity parameter s is dataset-dependent and tuned via gap statistic; using a fixed sparsity level across datasets biases results.
• NMI assumes the number of clusters k matches the true number of classes; mismatched k invalidates the metric.

Evidence (verbatim from paper)

We evaluate the performance of the algorithms on each dataset with normalized mutual information (NMI) [[43]] and report the results in Table 4. The performance evaluated by ARI is given in the Supplement.

Citation

@misc{zhang2020sparsekmeans,
  title={Simple and Scalable Sparse k-means Clustering via Feature Ranking},
  author={Zhang et al. (2020)},
  year={2020},
  note={arXiv:2002.08541}
}

• arXiv: 2002.08541