Attraction-Repulsion clustering with applications to fairness

Eustasio del Barrio, Hristo Inouzhe, Jean-Michel LoubesarXiv 2019 · arXiv

Introduction

In unsupervised machine learning, clustering algorithms are frequently deployed to group individuals for high-stakes applications, ranging from credit scoring to resource allocation. However, when the underlying data reflects historical or systemic biases, standard algorithms like k-means or hierarchical clustering tend to produce homogeneous groups. This often results in the over-representation or under-representation of protected groups (e.g., based on race or gender) within specific clusters, violating the principle of demographic parity.

Demographic parity suggests that the composition of each cluster should approximately mirror the diversity of the overall population. Achieving this is challenging because fairness and the natural geometric structure of data are often in tension. Forcing perfect parity can obscure meaningful patterns, while ignoring fairness risks automating discrimination. This paper introduces a novel pre-processing heuristic that treats protected attributes as physical charges to "nudge" clustering outcomes toward greater diversity without requiring a complete redesign of existing algorithms.

The Attraction-Repulsion Framework

The authors propose a physics-inspired approach using four new dissimilarity measures ($\delta_1$ through $\delta_4$). The core intuition relies on an analogy to electromagnetism:

  • The "Charge" Analogy: Protected attributes (e.g., $S=1$ for one group, $S=-1$ for another) are treated as electric charges.
  • Repulsion: The algorithm increases the mathematical distance between points sharing the same protected attribute, making it less likely they will be assigned to the same cluster.
  • Attraction: Conversely, the distance between points with different attributes is decreased to encourage mixing.

Implementation Strategies

To ensure these measures are compatible with standard tools, the authors provide three implementation pathways:

  1. Iterative Hierarchical Clustering: By deriving a recursive formula similar to the Lance-Williams class, the authors allow these new distances to be used efficiently with Ward’s minimum variance method.
  2. Multidimensional Scaling (MDS): For algorithms requiring Euclidean coordinates (like k-means), the authors use MDS to embed the perturbed distances back into a coordinate space.
  3. Kernel Extension: A "kernel trick" version is provided to handle non-linear data structures, such as concentric rings, where linear boundaries are insufficient.

Experimental Evaluation

The researchers evaluated the framework across synthetic and real-world datasets:

  • The Ricci Dataset: A classic case study in legal ethics involving firefighter exam scores. The attraction-repulsion method significantly improved the "balance" (a proxy for demographic parity) from 0.34 to 0.61 compared to standard k-means.
  • Schools Civil Rights Data Collection (CRDC): Using data from New Jersey schools, the authors simulated the creation of diverse school districts, balancing geographic proximity with ethnic composition.
  • Synthetic "Ring" Data: The kernel-based approach successfully clustered non-convex structures into diverse groups, a task where traditional fair clustering methods often fail.

Key Insights: The Geometry-Fairness Trade-off

A central contribution of the paper is the conceptualization of the "ethical debt"—the hidden social cost of technological infrastructure that must be addressed through algorithmic design. The authors highlight that practitioners should not seek perfect parity at any cost, as high-intensity fairness corrections can eventually "destroy" the original cluster structure.

Notably, the dissimilarity measure $\delta_4$ is identified as particularly effective because it is "local." It primarily perturbs distances for points that are already close together, preserving the global geometry of the data while still promoting diversity. When compared to the popular "Fairlet" decomposition method, the attraction-repulsion approach produced clusters that were more compact and identifiable (as measured by the Silhouette Index), even if the Fairlet method occasionally achieved higher raw balance scores.

Conclusion and Future Directions

The attraction-repulsion framework offers an algorithm-agnostic pre-processing step that is compatible with k-means, hierarchical clustering, and DBSCAN. While it provides a flexible way to promote diversity, it is a heuristic rather than a constraint-based optimization; it does not provide hard guarantees for specific fairness thresholds.

Future work aims to move toward a multi-objective optimization framework to automatically balance diversity and cluster quality. Additionally, the authors suggest exploring model-based clustering, such as Gaussian Mixture Models, within this framework to further refine the trade-off between data integrity and social equity.

Summary updated

Abstract

We consider the problem of diversity enhancing clustering, i.e, developing clustering methods which produce clusters that favour diversity with respect to a set of protected attributes such as race, sex, age, etc. In the context of fair clustering, diversity plays a major role when fairness is understood as demographic parity. To promote diversity, we introduce perturbations to the distance in the unprotected attributes that account for protected attributes in a way that resembles attraction-repulsion of charged particles in Physics. These perturbations are defined through dissimilarities with a tractable interpretation. Cluster analysis based on attraction-repulsion dissimilarities penalizes homogeneity of the clusters with respect to the protected attributes and leads to an improvement in diversity. An advantage of our approach, which falls into a pre-processing set-up, is its compatibility with a wide variety of clustering methods and whit non-Euclidean data. We illustrate the use of our procedures with both synthetic and real data and provide discussion about the relation between diversity, fairness, and cluster structure. Our procedures are implemented in an R package freely available at https://github.com/HristoInouzhe/AttractionRepulsionClustering.
BibTeX
@misc{barrio2019attraction,
  author = {Eustasio del Barrio and Hristo Inouzhe and Jean-Michel Loubes},
  title = {{Attraction-Repulsion clustering with applications to fairness}},
  year = {2019},
  eprint = {1904.05254},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1904.05254},
}
Figure