Interpreting clusters via prototype optimization. (February 2022)

• Record Type: Journal Article
• Authors: Carrizosa, Emilio; Kurishchenko, Kseniia; Marín, Alfredo; Romero Morales, Dolores
• Is Part Of: Omega. Volume 107(2022)
• Publication Date: 2022-02
• Subjects: Machine Learning -- Interpretability -- Cluster Analysis -- Prototypes -- Mixed-Integer Programming; Management -- Periodicals; 658.4005
• DOI: 10.1016/j.omega.2021.102543
• Languages: English
• ISSNs: 0305-0483

Abstract

Highlights: We propose a novel post-hoc methodology for Interpretability in Cluster Analysis. Our explanations are distance-based, based on defining prototypes for each cluster. The quality of our explanations is measured through true and false positive cases. We propose two Mixed Integer Linear Optimization models for finding explanations. Abstract: In this paper, we tackle the problem of enhancing the interpretability of the results of Cluster Analysis. Our goal is to find an explanation for each cluster, such that clusters are characterized as precisely and distinctively as possible, i.e., the explanation is fulfilled by as many as possible individuals of the corresponding cluster, true positive cases, and by as few as possible individuals in the remaining clusters, false positive cases. We assume that a dissimilarity between the individuals is given, and propose distance-based explanations, namely those defined by individuals that are close to its so-called prototype. To find the set of prototypes, we address the biobjective optimization problem that maximizes the total number of true positive cases across all clusters and minimizes the total number of false positive cases, while controlling the true positive rate as well as the false positive rate in each cluster. We develop two mathematical optimization models, inspired by classic Location Analysis problems, that differ in the way individuals are allocated to prototypes. We illustrate the explanations provided by these models and their accuracy in both real-life data as well as simulated data.