Are you dense? Incorporating Density-based Structures in Explainable Clustering

Explainable clustering methods have focused almost entirely on centroid-based reference clusterings with mostly convex cluster shapes. However, many real-world datasets contain clusters of non-convex, arbitrary shapes that are typically found with density-based clustering methods. We address this gap with our novel explainability framework **LUCID** (exp**L**aining cl**U**ster stru**C**tures v**I**a **D**ensity-aware trees). LUCID explains a given density-based clustering by fitting an interpretable tree over its density-connectivity structure, combining sparse feature rules with a case-based explanation for structure no such simple rule can separate. We demonstrate LUCID's applicability in extensive experiments, highlighting its necessity for density-based reference clusterings and datasets containing density-connected structures.