ExKMC: Expanding Explainable $k$-Means Clustering

Explainability-accuracy trade-off is quantifiable: ExKMC demonstrates that users can deliberately choose how much explanation complexity they're willing to accept, with the algorithm guaranteeing that increasing tree complexity (more leaves) will not worsen clustering quality—enabling organizations to make intentional trade-offs rather than accepting them as inevitable.

Simple explanations are achievable for clustering: The method explains cluster assignments through "short sequences of single-feature thresholds" (e.g., "if age > 30 AND income < $50k, then cluster A"), making unsupervised learning decisions interpretable to non-technical stakeholders—addressing a significant gap since most explainable AI work focuses on supervised learning.

Decision trees provide a practical explainability mechanism: By using small decision trees as the core explainability tool, ExKMC leverages a method that is already familiar to business users and regulators, rather than introducing novel but harder-to-understand explanation techniques.

Performance doesn't require sacrificing interpretability: The algorithm outperforms both standard decision tree methods and other explainable clustering approaches, suggesting that explainability and accuracy are not inherently at odds—a finding that could encourage broader adoption of interpretable AI systems.

Flexibility enables real-world deployment: The adjustable parameter k' allows different use cases (high-stakes decisions requiring more explanation vs. applications where accuracy is paramount) to use the same algorithm, making it more practical for organizations with varying transparency requirements.