Fair Model-based Clustering

Jinwon Park; Kunwoong Kim; Jihu Lee; Yongdai Kim

stat.MLFeb 25, 2026

Fair Model-based Clustering

Authors: Jinwon Park, Kunwoong Kim, Jihu Lee, Yongdai Kim

Organizations: Graduate School of Data Science, Seoul National University · Department of Statistics, Seoul National University

Abstract

The goal of fair clustering is to find clusters such that the proportion of sensitive attributes (e.g., gender, race, etc.) in each cluster is similar to that of the entire dataset. Various fair clustering algorithms have been proposed that modify standard K-means clustering to satisfy a given fairness constraint. A critical limitation of several existing fair clustering algorithms is that the number of parameters to be learned is proportional to the sample size because the cluster assignment of each datum should be optimized simultaneously with the cluster center, and thus scaling up the algorithms is difficult. In this paper, we propose a new fair clustering algorithm based on a finite mixture model, called Fair Model-based Clustering (FMC). A main advantage of FMC is that the number of learnable parameters is independent of the sample size and thus can be scaled up easily. In particular, mini-batch learning is possible to obtain clusters that are approximately fair. Moreover, FMC can be applied to non-metric data (e.g., categorical data) as long as the likelihood is well-defined. Theoretical and empirical justifications for the superiority of the proposed algorithm are provided.

Figures & tables

Panel of Figure 1 — Figure 1: Pareto front lines between $\Delta$ and Cost on Adult, Bank, and Credit datasets. See Fig. 5 for the lines between Balance and Cost. See Fig. 6 for the similar results without $L_{2}$ normalization.

Panel of Figure 2 — Figure 2: Pareto front lines between $\Delta$ and Cost (with standard deviation bands obtained by five random initializations) of FMC-EM (left) and FMC-GD (right) on Adult dataset. See Fig. 4 in Appendix for similar results with respect to Balance and on other datasets.

Panel of Figure 3 — Figure 3: Pareto front lines between $\{\Delta,\textup{ Balance}\}$ and Cost on Census dataset. See Fig. 7 in Appendix for the similar results without $L_{2}$ normalization.

Algorithm	Time (std)
VFC	5053.0 (915.5)
SFC	2218.2 (535.1)
FMC (mini-batch, $n=0.1N$ )	253.0 (12.1)

Table 1: Comparison of the average computation time (seconds) with standard deviations (std) over five random initials on Census dataset (

N=

2,458,285).

Method $\left(\frac{n}{N}\right)$	Cost ( $\times 10^{5}$ )	$\Delta$	Balance	Time
SS (1%)	11.167	0.005	0.851	53.7%
SS (3%)	10.988	0.004	0.894	65.8%
SS (5%)	10.973	0.003	0.883	71.4%
SS (10%)	10.916	0.003	0.881	77.2%
MB (10%)	10.857	0.002	0.896	100.0%

Table 2: Performances of mini-batch learning (MB) and sub-sample learning (SS) on Census dataset. The computation times of SS are measured by the relative ratio compared to the mini-batch learning with

10\%,

and the Lagrangian

\lambda

for each case is tuned to achieve the lowest Gap value i.e.,

\Delta\approx 0.

See Table 4 in Appendix for the similar results without

L_{2}

normalization.

Appendix figures & tables15 assets

Supplementary material from the paper’s appendix.

Appendix

A_{i}^{t}(\Theta)=\begin{cases}Q_{fair,i}(\Theta\mid\Theta^{[t]};\lambda)&\textup{ if }i\in I_{t}\\ A_{i}^{t-1}(\Theta)&\textup{ otherwise }\end{cases}

Appendix

Algorithm 3 FMC-EM (Expectation-Maximization) for mini-batch learning with sub-sampled

\Delta

In practice, we set

(T,R,\gamma)=(200,10,10^{-2})

Panel of Figure 4 — Figure 4: First row: Pareto front lines between Balance and Cost with standard deviation bands of FMC-EM and FMC-GD on Adult dataset. Second row: Pareto front lines between $\{\Delta$ , Balance $\}$ and Cost with standard deviation bands of FMC-EM and FMC-GD on Bank dataset. Third row: Pareto front lines between $\{\Delta$ , Balance $\}$ and Cost with standard deviation bands of FMC-EM and FMC-GD on Credit dataset.

Panel of Figure 5 — Figure 5: Pareto front lines between Balance and Cost on Adult, Bank, and Credit datasets.

Panel of Figure 6 — Figure 6: (Top three) Pareto front lines between $\Delta$ and Cost on Adult, Bank, and Credit datasets, without $L_{2}$ normalization. (Bottom three) Pareto front lines between Balance and Cost on Adult, Bank, and Credit datasets, without $L_{2}$ normalization.

Dataset		Adult		Bank
Algorithm		Balance $\uparrow$	Cost $\downarrow$	Balance $\uparrow$	Cost $\downarrow$
Standard clustering	$K$ -means	0.169	9509	0.246	8513
	MM-GD	0.174	9629	0.243	8603
	MM-EM	0.173	9636	0.242	8600
Fair clustering	FCA	0.494	10680	0.645	10853
	FMC-GD	0.467	14921	0.635	15725

Appendix

Table 3: Comparison of FMC and FCA in terms of Balance and Cost on Adult and Bank datasets.

Panel of Figure 7 — Figure 7: (Left) Pareto front lines between $\Delta$ and Cost on Census dataset, without $L_{2}$ normalization. (Right) Pareto front lines between Balance and Cost on Census dataset, without $L_{2}$ normalization.

Method $\left(\frac{n}{N}\right)$	Cost ( $\times 10^{7}$ )	$\Delta$	Balance	Time
SS (1%)	3.073	0.011	0.832	52.4%
SS (3%)	2.907	0.006	0.895	54.5%
SS (5%)	3.096	0.003	0.898	58.5%
SS (10%)	3.049	0.003	0.902	79.2%
MB (10%)	3.043	0.003	0.896	100.0%

Appendix

Table 4: Performances of mini-batch learning (MB) and sub-sample learning (SS) on Census dataset, without

L_{2}

normalization. The computation times of SS are measured by the relative ratio compared to the mini-batch learning with

10\%

, and the Lagrangian

\lambda

for each case is tuned to achieve the lowest Gap value i.e.,

\Delta\approx 0.

Dataset		Adult			Bank			Credit
Algorithm		Balance $\uparrow$	NLL $\downarrow$	$\Delta$ $\downarrow$	Balance $\uparrow$	NLL $\downarrow$	$\Delta$ $\downarrow$	Balance $\uparrow$	NLL $\downarrow$	$\Delta$ $\downarrow$
Standard clustering	MM-GD	0.004	8.609	0.089	0.322	9.706	0.037	0.534	5.749	0.030
Standard clustering	MM-EM	0.004	8.618	0.099	0.312	9.771	0.030	0.534	5.751	0.029
Fair clustering	FMC-GD	0.467	9.524	0.008	0.631	9.919	0.002	0.732	8.232	0.005
Fair clustering	FMC-EM	0.480	11.600	0.001	0.633	9.940	0.002	0.739	7.706	0.001

Appendix

Table 5: Clustering results (i.e., Balance, NLL, and

\Delta

) on three datasets with categorical data.

Dataset		Bank			Credit
Algorithm		Balance $\uparrow$	NLL $\downarrow$	$\Delta$ $\downarrow$	Balance $\uparrow$	NLL $\downarrow$	$\Delta$ $\downarrow$
Standard clustering	MM-GD	0.119	9.700	0.027	0.286	5.762	0.029
Standard clustering	MM-EM	0.114	9.717	0.027	0.298	5.791	0.028
Fair clustering	FMC-GD	0.180	10.026	0.002	0.371	8.474	0.003
Fair clustering	FMC-EM	0.179	10.281	0.002	0.373	7.617	0.006

Appendix

Table 6: Clustering results (i.e., Balance, NLL, and

\Delta

) on two datasets with categorical data for

M=3

Dataset		Bank			Credit
Algorithm		Balance $\uparrow$	Cost $\downarrow$	$\Delta\downarrow$	Balance $\uparrow$	NLL $\downarrow$	$\Delta\downarrow$
Standard clustering	$K$ -means	0.087	8513	0.055	0.159	4901	0.056
Standard clustering	MM-EM	0.085	8538	0.108	0.151	4954	0.110
Fair clustering	VFC	0.171	9373	0.016	0.294	6058	0.019
	FMC-EM ( $\lambda=4$ )	0.168	19059	0.013	0.295	22047	0.017
	FMC-EM ( $\lambda=10$ )	0.180	20040	0.000	0.375	23067	0.000

Appendix

Table 7: Clustering results (i.e., Balance, Cost, and

\Delta

) on Bank and Credit datasets with continuous data for

M=3

. We set

\lambda=4

to compare with VFC (e.g.,

\Delta\approx 0.016

for Bank) and

\lambda=10.0

to achieve the perfect fairness (i.e.,

\Delta\approx 0

Figure 8: The effects of $K$ on NLL, $\Delta,$ and Balance (from left to right) for FMC-EM (solid orange line) and MM-EM (dotted gray line) on Adult dataset. The number of clusters $K$ ranges from 2 to 10.

Panel of Figure 9 — Figure 9: Comparison of different covariance structures (isotropic vs. diagonal) in FMC-EM and FMC-GD on Adult, Bank, and Credit datasets, in terms of the negative log-likelihood (NLL) and Balance. $\sigma^{2}I$ denotes the results from isotropic covariance and diag denotes the results from diagonal covariance.

Panel of Figure 10 — Figure 10: Convergence of FMC-EM (with $\lambda=5.0$ ) in terms of NLL, Cost, $\Delta,$ and Balance on Adult dataset.

Figure 11: $\Delta$ vs. Balance on Adult dataset. The points are obtained from FMC-EM with various values of $\lambda.$

Method	Accuracy $\uparrow$	$\Delta$ $\downarrow$	Balance $\uparrow$
SFC	0.573	0.006	0.490
FMC (continuous only, $\lambda=10$ )	0.579	0.000	0.491
FMC (continuous + categorical, $\lambda=10$ )	0.706	0.000	0.488
VFC	0.621	0.070	0.429
FMC (continuous only, $\lambda=1$ )	0.627	0.071	0.411
FMC (continuous + categorical, $\lambda=1$ )	0.703	0.054	0.430

Appendix

Table 8: Comparison of classification accuracy between continuous-only methods and FMC applied jointly to

(x^{\textup{cont}},x^{\textup{cate}})

for

K=2,

on Adult dataset. We set

\lambda=10

when comparing with SFC (

\Delta\approx 0

) and

\lambda=1

when comparing with VFC (

\Delta\approx 0.07

Clustering

Clustering groups data points by shared structure, developing methods to discover, validate, and interpret groups across diverse data and constraints.

See all 347 papers

Fast and effective algorithms for fair clustering at scale
May 13, 2026Claudio Mantuano, Manuel Kammermann, Philipp BaumannClustering Algorithmic Fairness
Department of Business Administration, University of Bern, Engehaldenstrasse 4, 3012 Bern, Switzerland
Proportionally Representative Clustering
Apr 27, 2023Haris Aziz, Barton E. Lee, Sean Morota Chu +1Clustering Algorithmic Fairness
UNSW Sydney · ETH Zürich · Northwestern University
COVAriance-Induced Fairness Gap Penalty for Subgroup-Fair Clustering
Jul 20, 2026Kyungseon Lee, Hankyo Jeong, Kunwoong Kim +2Clustering Algorithmic Fairness
Department of Statistics, Seoul National University · KAIST AI

May 13, 2026J/K move · Enter open · S save

Fast and effective algorithms for fair clustering at scale

Claudio Mantuano, Manuel Kammermann, Philipp Baumann

Department of Business Administration, University of Bern, Engehaldenstrasse 4, 3012 Bern, Switzerland

Clustering Algorithmic Fairness Group Fairness

Open paper AskPDF arXiv

Clustering is an unsupervised machine learning task that consists of identifying groups of similar objects. It has numerous applications and is increasingly used in fairness-sensitive domains where objects represent individuals, such as customers, employees, or students. We address a fair clustering problem in which objects belong to protected groups. The problem consists of partitioning the objects into a predefined number of clusters while attaining a user-defined target level of fairness, meaning that each protected group is sufficiently represented in each cluster. The objective is to minimize the clustering cost, defined as the sum of squared Euclidean distances between the objects and the centers of their clusters. Since clustering cost and fairness are generally in conflict, managing the trade-off between them is essential in practical applications. Existing methods provide limited control over this trade-off and either fail to scale to large datasets or, when they scale, produce low-quality solutions. We propose a general framework for fair clustering that provides precise control over the cost-fairness trade-off and introduce three heuristics based on it. The first heuristic focuses on solution quality and the flexibility to incorporate additional constraints, the second improves scalability while retaining high solution quality, and the third is designed for maximum scalability, producing solutions for instances with millions of objects in seconds. The proposed heuristics outperform existing approaches in comprehensive numerical experiments on benchmark datasets. The source code of our heuristics and instructions for reproducing the experiments are publicly available on GitHub.

Abstract

Clustering

Explore similar work

Fast and effective algorithms for fair clustering at scale

Proportionally Representative Clustering

COVAriance-Induced Fairness Gap Penalty for Subgroup-Fair Clustering