Mutual Information Scoring: Increasing Interpretability in Categorical Clustering Tasks with Applications to Child Welfare Data

Pranav Sankhe, Seventy F. Hall, Melanie D. Sage, Maria Y. Rodriguez, Varun Chandola, Kenneth Joseph

Introduction

Administrative datasets in fields like social work and child welfare are often high-dimensional, categorical, and fraught with missing values. While machine learning offers tools to navigate this complexity, traditional clustering methods frequently fall short. Most algorithms require a pre-defined number of clusters ($k$) and operate as "black boxes," providing little insight into the logic behind their groupings. In sensitive domains like foster care, where data reflects systemic inequalities, there is a critical need for models that move beyond simple prediction toward "prescriptive understanding."

Researchers at the University at Buffalo have addressed this gap by introducing Mutual Information Scoring (MIS), a novel top-down clustering framework designed specifically for categorical data. By combining information theory with statistical summarization, the MIS approach identifies meaningful patterns in data while automatically explaining the characteristics that define each group.

The MIS Framework

The researchers developed a two-part framework that prioritizes both statistical rigor and human interpretability.

1. Top-Down Clustering via MIS

Unlike bottom-up (agglomerative) methods, the MIS algorithm uses a divisive approach. It begins with the entire dataset as a single group and recursively splits it into smaller, more homogeneous clusters.

  • Attribute Selection: To determine the best way to split a group, the algorithm identifies a "significant attribute" using a modified Mutual Information Score. Standard Mutual Information (MI) tends to be biased toward attributes with a high number of categories. The authors normalize this by dividing the MI by the number of categories, ensuring a fairer selection process.
  • Entropy-Based Splitting: Once an attribute is selected, the algorithm creates partitions and selects the one with the lowest entropy (highest internal similarity) to form a new cluster. A key advantage of this method is its ability to stop automatically when no further meaningful clusters can be identified, removing the need for users to guess the value of $k$.

2. Cluster Summarization via KL-Divergence

To make the resulting clusters actionable for human experts, the framework employs Kullback-Leibler (KL) divergence. This measure compares the distribution of attributes within a specific cluster to the global distribution of the entire dataset. This allows the system to generate intuitive summaries, such as identifying that a specific cluster is unique because it contains a disproportionately high percentage of a certain demographic or placement type compared to the general population.

Empirical Evaluation and Results

The authors evaluated the MIS framework against seven standard categorical datasets from the UCI Machine Learning Repository (including Mushroom, Vote, and Breast Cancer) and a real-world application using U.S. foster care data.

Benchmark Performance

On the UCI benchmark datasets, the "MIS (auto)" version—which determines the number of clusters independently—achieved an average purity score of 0.80. This outperformed several state-of-the-art methods, including G-ANMI (0.719) and MGR (0.744). Notably, the automated version often performed better than versions where the number of clusters was manually specified, suggesting that the algorithm's stopping criteria are highly effective at capturing the natural structure of categorical data.

Case Study: AFCARS Foster Care Data

The researchers applied the model to 2018 data from the Adoption and Foster Care Analysis and Reporting System (AFCARS) for New York and Texas. The analysis focused on 27 variables, including demographics, clinical diagnoses, and welfare history.

Two major insights emerged from this application:

  • Missing Data as a Signal: The algorithm revealed that "missingness" in administrative data is rarely random. For instance, children in pre-adoptive homes often had significantly more complete medical records than those in other settings. This suggests that the system prioritizes data collection differently based on a child's trajectory.
  • Policy-Driven Data: In New York, clusters were heavily influenced by state-level funding eligibility. This highlights that administrative data often reflects bureaucratic processes and policy requirements more than the actual needs or characteristics of the children served.

Conclusion

The MIS framework represents a shift in how machine learning can be applied to social science. By prioritizing interpretability and handling the inherent "messiness" of categorical data, the tool acts as a microscope for systemic issues. Rather than acting as a "crystal ball" to predict individual outcomes, MIS allows researchers and policy-makers to identify sub-populations that may be underserved or affected by systemic biases, providing a foundation for more equitable policy interventions.

Summary updated

BibTeX
@inproceedings{sankhe2022mutual,
  author = {Pranav Sankhe and Seventy F. Hall and Melanie D. Sage and Maria Y. Rodriguez and Varun Chandola and Kenneth Joseph},
  title = {{Mutual Information Scoring: Increasing Interpretability in Categorical Clustering Tasks with Applications to Child Welfare Data}},
  booktitle = {SBP-BRiMS},
  year = {2022},
  doi = {10.1007/978-3-031-17114-7\_16},
}
Figure