📊 statistics

A Computational Approach to Improving Fairness in K-means Clustering

This paper proposes a two-stage computational approach to improve fairness in K-means clustering by identifying and adjusting the membership of specific data points to reduce subpopulation imbalances while maintaining clustering quality.

Original authors: Guancheng Zhou, Haiping Xu, Hongkang Xu, Chenyu Li, Donghui Yan

Published 2026-02-10

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Guancheng Zhou, Haiping Xu, Hongkang Xu, Chenyu Li, Donghui Yan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Problem: The "Unfair Party" Effect

Imagine you are organizing a massive school dance. To make sure everyone has a good time, you decide to split the students into two groups (clusters) based on their interests: the "Music Lovers" and the "Art Enthusiasts."

You use a standard method to group them, but when the groups are finalized, you notice something awkward. The "Music Lovers" room is almost entirely filled with boys, while the "Art Enthusiasts" room is almost entirely filled with girls.

Even though you didn't try to do this, your grouping method accidentally created a "gender divide." In the world of data science, this is a fairness issue. If a computer uses these biased groups to make decisions—like who gets a scholarship or a job—it could accidentally discriminate against certain groups of people just because they were lumped together in a way that doesn't reflect the real world.

The Goal: Fixing the Groups Without Ruining the Vibe

The researchers wanted to fix this "unfairness" without breaking the clusters.

If you suddenly start moving people from one room to another randomly, you might ruin the whole point of the party. If you move a huge group of "Art Enthusiasts" into the "Music" room, the music lovers will be annoyed because the "vibe" (the cluster quality) is ruined.

The goal is to find a way to balance the groups (make sure both rooms have a fair mix of boys and girls) while making sure the groups still actually represent the interests of the students.

The Solution: The "Boundary Swap" Strategy

Instead of rebuilding the whole party from scratch, the researchers proposed a two-stage approach.

Stage 1: Run the standard grouping method (K-means) to get the best possible groups based on interests.
Stage 2: Look for "promising" people to swap.

But who are these "promising" people? You wouldn't move someone who is deeply obsessed with art into the music room. You only want to move the people who are "on the fence." The researchers came up with two clever ways to find these people:

1. The "Near-Foreign" Method (The Social Butterflies)

Think of this like looking for the people standing near the doorway between the two rooms. These are the "Social Butterflies"—people who are technically in the Music room, but they are standing so close to the Art room that they could easily walk over without feeling like they've entered a totally different world. By swapping these "boundary" people, you balance the gender ratio without changing the "vibe" of either room.

2. The "Gini Index" Method (The Mixed-Up Crowd)

Imagine looking at a small circle of people. If everyone in that circle is wearing a band T-shirt, that area is "pure." But if you see a circle where some people are wearing band shirts and others are wearing berets, that area is "mixed."

The researchers use a math tool called the Gini Index to find these "mixed" spots. They look for the people living in these "mixed" zones. Because these people are already surrounded by a mix of interests, moving them to the other group is a very "low-risk" move. It fixes the fairness issue but keeps the overall quality of the groups almost exactly the same.

The Result: A Fairer Party

The researchers tested this on several real-world datasets (like medical data and student performance).

The verdict? Their methods successfully made the groups much fairer (more balanced) while barely touching the "quality" of the groups. It’s like successfully balancing the gender ratio at the dance without anyone even noticing that the groups had been adjusted.

In short: They found a way to make AI more "just" by focusing on the people who are already standing on the edge, making sure the math doesn't accidentally leave anyone behind.

Technical Summary: A Computational Approach to Improving Fairness in K-means Clustering

1. Problem Statement

Standard clustering algorithms, most notably K-means, aim to minimize intra-cluster variance (the within-cluster sum of squares). However, they are "fairness-blind." This lack of consideration for sensitive attributes (e.g., race, gender) can lead to clusters that disproportionately represent or exclude specific subpopulations. Such biases can result in unfair downstream analysis or harmful social consequences.

While fair clustering can be formulated as a constrained optimization problem, solving it directly is computationally prohibitive because it is a mixed-integer programming problem that is NP-hard. Existing fair clustering methods are often mathematically complex, computationally expensive, or too tightly coupled to specific algorithms.

2. Methodology

The authors propose a novel two-stage optimization approach that treats fairness as a post-processing adjustment rather than a primary constraint during the initial clustering phase.

Stage 1: Standard Clustering: Perform traditional K-means clustering to obtain an initial partition of the data that maximizes cluster quality.
Stage 2: Membership Adjustment: Identify a small subset of "promising" data points located near cluster boundaries and switch their cluster assignments to balance the subpopulation proportions. By focusing only on boundary points, the algorithm minimizes the impact on the overall clustering quality (the objective function).

To identify these "promising" points, the paper introduces two distinct heuristics:

Near-Foreign Heuristic (fcNearForeign):
- Logic: Targets points that are far from their own cluster centroid but are among the nearest neighbors to a different cluster's centroid.
- Mechanism: It identifies "foreign points" of a destination cluster. Reassigning these points is unlikely to significantly degrade the cluster quality because they are already geographically peripheral to their current group.
Gini Index Heuristic (fcGini):
- Logic: Uses the Gini index (traditionally used in decision trees to measure node impurity) to detect "mixed" data points.
- Mechanism: For each point, the algorithm calculates the Gini index of its $k$ -nearest neighbors. A high Gini index indicates a point is in a highly "mixed" neighborhood (a cluster boundary), while a low index indicates an "interior" point. The algorithm prioritizes switching points with the highest Gini indices to improve fairness.

3. Key Contributions

Two-Stage Framework: A computationally efficient alternative to solving complex constrained optimization problems.
Dual Heuristics: The introduction of both a distance-based (Near-Foreign) and an impurity-based (Gini) method for identifying boundary points.
Algorithmic Versatility: The approach is "algorithm-agnostic," meaning it can be applied to any clustering method (e.g., spectral clustering) or any definition of fairness.
Efficiency: Both proposed algorithms maintain linear computational complexity relative to the number of data points and the number of necessary exchanges.

4. Experimental Results

The authors tested their algorithms on seven benchmark datasets from the UCI Machine Learning Repository (e.g., Heart, StudentPerf, CMC). They evaluated performance using two metrics:

Fairness Index ( $F$ ): A measure of the discrepancy between subpopulation proportions in clusters versus the general population (lower is better).
Cluster Quality ( $\kappa$ ): The ratio of between-cluster sum of squares to total sum of squares (higher is better).

Findings:

Significant Fairness Improvement: Both fcNearForeign and fcGini substantially reduced the fairness index compared to standard K-means across all datasets.
Minimal Quality Loss: The impact on cluster quality ( $\kappa$ ) was negligible, proving that the "boundary-switching" strategy effectively preserves the structural integrity of the clusters.
Robustness: The Gini index approach proved insensitive to the choice of neighborhood size ( $k$ ).

5. Significance

This work provides a practical, scalable solution for practitioners who need to ensure fairness in automated data grouping. By decoupling the fairness adjustment from the initial clustering, the authors offer a method that is easy to implement and can be integrated into existing machine learning pipelines without the need for heavy mathematical re-formulation. This is particularly significant for sensitive applications in social science, healthcare, and market segmentation where biased clustering can lead to systemic inequality.