Sparse Kmeans Eval

---
name: sparse-kmeans-eval
description: 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. Use when the user wants to benchmark on Mice protein expression dataset, UCI/Keel/ASU Benchmark Datasets, or asks about evaluating this task. Reports Normalized Mutual Information (NMI).
metadata:
  skill_kind: dataset_eval
  source_arxiv: 2002.08541
  bibtex_key: zhang2020sparsekmeans
  confidence: high
---

# 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

```python
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

```bibtex
@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