Disjunctive and Conjunctive Normal Form Explanations of Clusters Using Auxiliary Information
This work addresses the need for interpretable cluster explanations in data analysis, but it is incremental as it builds on existing terminology and methods for explanation generation.
The paper tackles the problem of generating post-hoc explanations for clusters using auxiliary information not used in clustering, focusing on disjunctive and conjunctive normal form explanations, and employs integer linear programming and heuristic methods to produce these explanations across various datasets while discussing scalability.
We consider generating post-hoc explanations of clusters generated from various datasets using auxiliary information which was not used by clustering algorithms. Following terminology used in previous work, we refer to the auxiliary information as tags. Our focus is on two forms of explanations, namely disjunctive form (where the explanation for a cluster consists of a set of tags) and a two-clause conjunctive normal form (CNF) explanation (where the explanation consists of two sets of tags, combined through the AND operator). We use integer linear programming (ILP) as well as heuristic methods to generate these explanations. We experiment with a variety of datasets and discuss the insights obtained from our explanations. We also present experimental results regarding the scalability of our explanation methods.