Interpretable clustering: an optimization approach

• DOI: 10.1007/s10994-020-05896-2
• Publication Date: 2020-08-16T19:02:25Z
• Authors: Dimitris Bertsimas; Agni Orfanoudaki; Holly Wiberg
• Keywords: 0202 electrical engineering, electronic engineering, information engineering; 006; 02 engineering and technology

State-of-the-art clustering algorithms provide little insight into the rationale for cluster membership, limiting their interpretability. In complex real-world applications, the latter poses a barrier to machine learning adoption when experts are asked to provide detailed explanations of their algorithms’ recommendations. We present a new unsupervised learning method that leverages Mixed Integer Optimization techniques to generate interpretable tree-based clustering models. Utilizing a flexible optimization-driven framework, our algorithm approximates the globally optimal solution leading to high quality partitions of the feature space. We propose a novel method which can optimize for various clustering internal validation metrics and naturally determines the optimal number of clusters. It successfully addresses the challenge of mixed numerical and categorical data and achieves comparable or superior performance to other clustering methods on both synthetic and real-world datasets while offering significantly higher interpretability.