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

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

TL;DR

Researchers have developed a novel top-down clustering algorithm called Mutual Information Scoring (MIS) designed specifically for high-dimensional categorical data. By applying this method to messy, real-world foster care administrative records, they demonstrated how unsupervised learning can uncover systemic biases and hidden patterns in how social services are delivered and documented.

What Problem Does This Paper Address?

Administrative data—like the records kept on the 420,000+ children in the U.S. foster care system—is a goldmine for social scientists, but it is notoriously difficult to mine. Unlike the clean, continuous datasets often used in machine learning benchmarks, this data is high-dimensional, purely categorical (e.g., placement types, reasons for removal), and riddled with missing values.

Existing clustering methods for categorical data often struggle with two things:

  1. Interpretability: They might group data points together, but they don't explain why those groups exist in a way that a social worker or policy analyst can use.
  2. Parameter Sensitivity: Many algorithms require the user to specify the number of clusters ($k$) upfront, which is often unknown in exploratory social science.

The authors aim to move away from "predictive risk modeling" (which can reinforce existing biases) toward a "prescriptive" approach that helps researchers understand the underlying structure and biases of the system itself.

Methods

The authors propose a two-part framework: MIS Clustering and Cluster Summarization.

1. MIS Clustering

This is a top-down, divisive clustering approach. Instead of starting with random points and iterating (like $k$-means), it starts with the whole dataset and recursively splits it.

  • Significant Attribute Selection: The algorithm identifies which attribute provides the most information about the rest of the data. It uses a modified Mutual Information Score (MIS) that normalizes standard mutual information by the number of categories in an attribute. This prevents the algorithm from being "tricked" into picking attributes just because they have many possible values (a common bias in information theory).
  • Entropy-Based Splitting: Once an attribute is chosen, the data is partitioned based on that attribute's categories. The partition with the lowest entropy (meaning the most internal similarity) is selected to form a new cluster.

2. Cluster Summarization

To make the results interpretable, the authors use Kullback–Leibler (KL) divergence. They compare the distribution of attributes within a specific cluster to the global distribution of the entire dataset. This highlights exactly which features make a particular group of foster youth unique compared to the "average" profile.

Datasets

The study evaluates the MIS algorithm on two fronts:

  • Benchmarks: Seven widely used categorical datasets from the UCI Machine Learning Repository, including the "Mushroom," "Zoo," and "Congressional Voting" datasets. These provide a ground truth to measure clustering "purity."
  • Real-World Application: The Adoption and Foster Care Analysis and Reporting System (AFCARS) 2018 dataset. The researchers specifically looked at data from New York (N=23,676) and Texas (N=52,363) to compare decentralized vs. centralized administrative models.

Key Insights and Ideas

  • Missing Data is a Signal, Not Just Noise: One of the most striking findings was that clusters were often defined by the absence of missing values. For example, youth in pre-adoptive homes had significantly more complete medical records than those in other settings. This suggests that the "quality" of data collection is tied to the stability of the child's placement.
  • Policy Leaves a Digital Trace: The algorithm identified clusters in New York that appeared to be driven by state-level funding eligibility. Youth in relative foster homes vs. non-relative homes showed distinct profiles that likely reflect how different placements are licensed and funded, rather than just the needs of the child.
  • Holistic Youth Profiles: By looking at clusters rather than individual variables, the researchers found an "inextricable relationship" between placement types and "bouncing around" (placement disruptions). This holistic view helps identify specific pathways through the system that qualitative researchers can then investigate more deeply.

Key Results

The MIS algorithm proved to be highly effective, particularly when allowed to automatically determine the number of clusters (MIS-auto).

As shown in Table 1, MIS-auto achieved an average purity score of 0.80 across the UCI benchmarks, outperforming state-of-the-art methods like MGR (0.744) and G-ANMI (0.719).

Table 1: Purity of categorical clustering algorithms on UCI data sets.

In the real-world case study, the algorithm successfully reduced tens of thousands of complex records into 10 distinct clusters for New York and 6 for Texas, providing a manageable "map" for social work scholars to analyze.

Limitations and Future Work

The authors are careful to note that while these tools are powerful for understanding systems, they should not replace human judgment in high-stakes decisions. "Data always tells an incomplete story," they warn.

A primary limitation is that the current entropy measure assumes attribute independence for simplicity, which isn't always true in social data. Future work could involve refining these information-theoretic measures to account for correlations between variables. Additionally, the authors suggest that these quantitative insights should serve as a jumping-off point for future qualitative research—interviews and ethnographic work—to understand the "why" behind the patterns the algorithm uncovered.

Summary updated

Abstract

Youth in the American foster care system are significantly more likely than their peers to face a number of negative life outcomes, from homelessness to incarceration. Administrative data on these youth have the potential to provide insights that can help identify ways to improve their path towards a better life. However, such data also suffer from a variety of biases, from missing data to reflections of systemic inequality. The present work proposes a novel, prescriptive approach to using these data to provide insights about both data biases and the systems and youth they track. Specifically, we develop a novel categorical clustering and cluster summarization methodology that allows us to gain insights into subtle biases in existing data on foster youth, and to provide insight into where further (often qualitative) research is needed to identify potential ways of assisting youth.
BibTeX
@inproceedings{sankhe2022mutual,
  author = {Pranav Sankhe and Seventy F. Hall and Melanie Sage and Maria Y. Rodriquez 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