Explaining Clusters Using Minimal Weighted Edge Coverage

Abstract

Current clustering techniques in unsupervised learning lack interpretability. This is primarily because clustering represents a combinatorial optimization problem that becomes exponentially complex in large-dimensional spaces. Consequently, most clustering algorithms employ intricate mathematical computations, statistical assumptions, distance approximations, and data transformations in ways that diminish their interpretability. This study introduces a Linear Integer Programming model to optimize the balance between interpretability and quality, drawing inspiration from the graph theory's Minimal Edge Covering problem. An edge cover is a set of graph edges ensuring each vertex of the graph is incident to at least one edge of the set; the challenge lies in determining the smallest set possible. By adopting this approach, data can be grouped into clusters in the form of tree-like structures, enhancing our comprehension of the clustering process. If the edges are weighted to represent dissimilarities or distances, the problem becomes the Minimum Weighted Edge Covering (MWEC) problem.