Disjunctive and Conjunctive Normal Form Explanations
of Clusters Using Auxiliary Information · 2025
Read Disjunctive and Conjunctive Normal Form Explanations by of Clusters Using Auxiliary Information (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-20846.txt.
Introduction
Robert Downey and S S Ravi explain computer-found clusters in plain logic rules in a 2025 paper. Clustering tools group data well, but people often cannot say what a group means. Extra facts about each item, which the tool never saw, can supply the words. The authors call these extra facts tags and build short rule sets from them.
Two rule shapes are studied: a simple set of tags, or two tag sets joined by an AND. Exact math methods and faster rough methods both build the rules. Tests on varied data sets show the rules stay short enough to read. Runtime results show where the exact method slows down. Readable rules help people trust and audit what a clustering tool found.
Catalog record
| CREATOR | of Clusters Using Auxiliary Information |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 86 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-20846
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Disjunctive and Conjunctive Normal Form Explanations of Clusters Using Auxiliary Information Abstract Robert F. Downey 1 S. S. Ravi 2 1 1 footnotetext: Department of Electrical and Computer Engineering, University of Virginia, Charlottesville, VA 22904. Email: [email protected] . 2 2 footnotetext: Biocomplexity Institute, University of Virginia, Charlottesville, VA 22904 and Department of Computer Science, University at Albany – SUNY, Albany, NY 12222. Email: [email protected] . Abstract 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. Keywords: Clustering, Explainability, Auxiliary information, Cluster descriptors, Hitting set, Integer linear program, Heuristics 1 Introduction 1.1 Background, Motivation and Contributions Tools based on Artificial Intelligence (AI) are currently being used in many business and societal applications such as obtaining loans from financial institutions, security checkpoints at airports and sentencing decisions in courts (see e.g., [ 1 , 30 , 9 ] ). When such applications use black box models, the danger is that the results may be unfair to some sectors of the population or cause harm. As a consequence, the area of explainable AI (XAI) has become increasingly important [ 1 ] . A considerable amount of effort has been devoted to XAI for supervised learning models (see e.g., [ 22 , 23 , 13 ] ). The area of explainable AI for unsupervised learning tasks such as clustering and classification has not received as much attention [ 6 , 17 ] . The focus of this paper is on explainability in the context of clustering algorithms. Specifically, we consider post hoc explanations of outputs generated by clustering algorithms. Our explanation method is based on the use of auxiliary information (or tags ) associated with clustered data items. The approach of using tags to explain clusters was proposed in [ 6 ] and was developed further in other papers (see e.g., [ 25 , 17 , 7 , 2 ] ). This approach constructs a short descriptor , which is a subset of tags, for each cluster. A simple form of such a descriptor introduced in [ 6 ] is a disjunctive descriptor, where for each data item x in a cluster, the corresponding descriptor contains at least one tag that describes x . Our work considers this form of descriptors as well as a more general version called the conjunctive normal form (CNF) descriptor that provides for two disjunctive descriptors. While the CNF version requires more computation time, it has the potential to provide better explanations due to its expressive power. Formal definitions concerning the descriptors are presented in Section 2 . Our work constructs clusters of some public domain datasets using the k -means algorithm (see e.g., [ 15 , 26 ] for details regarding this algorithm), generates disjunctive and CNF descriptors for the clusters and examines the effectiveness of the descriptors. Specifically, our contributions are as follows. 1. Since constructing optimal disjunctive descriptors is, in general, computationally intractable [ 6 ] , we use an integer linear programming approach to develop descriptors of minimum size. As a baseline for comparison, we also use a greedy heuristic based on the hitting set problem [ 12 ] for constructing disjunctive descriptors. In addition, we present a method for constructing CNF descriptors. To our knowledge, the CNF form of descriptors has not been considered in the literature. 2. We construct descriptors for clusters from four public domain datasets and discuss the effectiveness of the tag-based explanations. The sizes of these datasets vary roughly from 170 to 30,000. 3. Examining the explanations for the datasets considered provides interesting insights regarding the relative informativeness of disjunctive and CNF explanations. The CNF form can aid in providing additional tags when the disjunctive form provides little or nondescript information. As an example, this added insight is illustrated in Table 9 (Section 5.3 ) for the Movies dataset. Here, the CNF descriptor is formed by combining the original disjunctive descriptor (generated by the heuristic for hitting set) with another hitting set which is obtained after excluding tags in the previous hitting set. This second hitting set provides further information about the cluster beyond the one or two tags in the disjunctive heuristic needed to cover every data item in a cluster. More details are provided in Section 5.3 . 4. Using synthetic datasets, we examine the computation time used to generate the descriptors to understand the scalability of our methods. Our exact algorithm for generating a disjunctive descriptor (based on an integer linear program) is slower on smaller datasets, highlighting an even greater advantage of heuristic solvers for these cases. For larger datasets, the CNF algorithm takes roughly twice as long as the disjunctive solvers, as the disjunctive approach is applied twice to generate the two clauses required for the CNF. Additional details regarding this timing study appear in Section 3.7 . More details regarding the contributions are provided in subsequent sections. 1.2 Related Work As AI is beginning to be used extensively in many applications, explainability of AI models has assumed a lot of importance [ 1 , 22 , 23 , 19 , 20 , 31 , 30 , 9 ] . These references discuss methods used for both supervised and unsupervised learning tasks. Since our focus is on explaining outputs of clustering algorithms, we will restrict our discussion to known methods for that task. In the machine learning literature, explaining clusters has been studied from two perspectives. The one-view approach of conceptual clustering [ 5 , 18 , 24 ] considers finding a clustering and its description simultaneously. Unlike our work, the explanation is based on the features used for clustering. So, these methods require that the features used to perform clustering be human interpretable. Another approach, called exemplar-based clustering [ 8 ] , has also been studied to generate a clustering and an explanation simultaneously. In this approach, the explanation for a cluster consists of a small subset, called an exemplar , of instances in that cluster such that every instance in the cluster is close to at least one exemplar. This form of explanation is similar to the use of exemplars in cognitive psychology [ 28 ] . As mentioned earlier, the tag-based approach for explaining outputs of clustering algorithms was proposed in [ 6 ] . That work established the complexity of obtaining descriptors of minimum length and provided an integer linear programming approach for the problem. Given the difficulty of constructing optimal descriptors efficiently, Sambaturu et al. [ 25 ] present approximation algorithms for constructing descriptors of near-optimal length and established rigorous performance guarantees provided by the algorithms. To