A Stochastic Alternating Balance $k$-Means Algorithm for Fair Clustering
In the application of data clustering to human-centric decision-making systems, such as loan applications and advertisement recommendations, the clustering outcome might discriminate against people across different demographic groups, leading to unfairness. A natural conflict occurs between the cost of clustering (in terms of distance to cluster centers) and the balance representation of all demographic groups across the clusters, leading to a bi-objective optimization problem that is nonconvex and nonsmooth. To determine the complete trade-off between these two competing goals, we design a novel stochastic alternating balance fair $k$-means (SAfairKM) algorithm, which consists of alternating classical mini-batch $k$-means updates and group swap updates. The number of $k$-means updates and the number of swap updates essentially parameterize the weight put on optimizing each objective function. Our numerical experiments show that the proposed SAfairKM algorithm is robust and computationally efficient in constructing well-spread and high-quality Pareto fronts both on synthetic and real datasets.
Code (1)
Tasks
ClusteringDecision MakingSimilar Papers 제목 키워드 기반
BalLOT: Balanced $k$-means clustering with optimal transport
We consider the fundamental problem of balanced $k$-means clustering. In particular, we introduce an optimal transport approach to alternating minimization called BalLOT, and we show that it delivers a fast and effective…
A Deep Latent Factor Graph Clustering with Fairness-Utility Trade-off Perspective
Fair graph clustering seeks partitions that respect network structure while maintaining proportional representation across sensitive groups, with applications spanning community detection, team formation, resource alloca…
Community DetectionGraph ClusteringMatrix Editing Meets Fair Clustering: Parameterized Algorithms and Complexity
We study the computational problem of computing a fair means clustering of discrete vectors, which admits an equivalent formulation as editing a colored matrix into one with few distinct color-balanced rows by changing a…
Imbalanced Data Clustering using Equilibrium K-Means
Centroid-based clustering algorithms, such as hard K-means (HKM) and fuzzy K-means (FKM), have suffered from learning bias towards large clusters. Their centroids tend to be crowded in large clusters, compromising perfor…
ClusteringDeep ClusteringFairer Chess: A Reversal of Two Opening Moves in Chess Creates Balance Between White and Black
Unlike tic-tac-toe or checkers, in which optimal play leads to a draw, it is not known whether optimal play in chess ends in a win for White, a win for Black, or a draw. But after White moves first in chess, if Black has…