Interpretable Clustering via Optimal Trees
  State-of-the-art clustering algorithms use heuristics to partition the
feature space and provide little insight into the rationale for cluster
membership, limiting their interpretability. In healthcare applications, the
latter poses a barrier to the adoption of these methods since medical
researchers are required to provide detailed explanations of their decisions in
order to gain patient trust and limit liability. We present a new unsupervised
learning algorithm that leverages Mixed Integer Optimization techniques to
generate interpretable tree-based clustering models. Utilizing the flexible
framework of Optimal Trees, our method approximates the globally optimal
solution leading to high quality partitions of the feature space. Our
algorithm, can incorporate various internal validation metrics, naturally
determines the optimal number of clusters, and is able to account for mixed
numeric and categorical data. It achieves comparable or superior performance on
both synthetic and real world datasets when compared to K-Means while offering
significantly higher interpretability.
