# Fair-Capacitated Clustering

Tai Le Quy

Arjun Roy

Gunnar Friege

Leibniz University Hannover  Hannover, Germany<EMAIL_ADDRESS>Leibniz University
Hannover  Hannover, Germany<EMAIL_ADDRESS>Leibniz University Hannover  Hannover,
Germany<EMAIL_ADDRESS>Eirini Ntoutsi

Free University of Berlin  Berlin, Germany<EMAIL_ADDRESS>
###### Abstract

Traditionally, clustering algorithms focus on partitioning the data into
groups of similar instances. The similarity objective, however, is not
sufficient in applications where a _fair-representation_ of the groups in
terms of protected attributes like gender or race, is required for each
cluster. Moreover, in many applications, to make the clusters useful for the
end-user, a _balanced cardinality_ among the clusters is required. Our
motivation comes from the education domain where studies indicate that
students might learn better in diverse student groups and of course groups of
similar cardinality are more practical e.g., for group assignments. To this
end, we introduce the _fair-capacitated clustering problem_ that partitions
the data into clusters of similar instances while ensuring cluster fairness
and balancing cluster cardinalities. We propose a two-step solution to the
problem: i) we rely on fairlets to generate minimal sets that satisfy the fair
constraint and ii) we propose two approaches, namely hierarchical clustering
and partitioning-based clustering, to obtain the fair-capacitated clustering.
The hierarchical approach embeds the additional cardinality requirements
during the merging step while the partitioning-based one alters the assignment
step using a knapsack problem formulation to satisfy the additional
requirements. Our experiments on four educational datasets show that our
approaches deliver well-balanced clusters in terms of both fairness and
cardinality while maintaining a good clustering quality.

###### keywords:

fair-capacitated clustering, fair clustering, capacitated clustering,
fairness, learning analytics, fairlets, knapsack.

##  1 Introduction

Machine learning (ML) plays a crucial role in decision-making in almost all
areas of our lives, including areas of high societal impact, like healthcare
and education. Our work’s motivation comes from the education domain where ML-
based decision-making has been used in a wide variety of tasks from student
dropout prediction [10], forecasting on-time graduation of students [16] to
education admission decisions [22]. Recently, the issue of bias and
discrimination in ML-based decision-making systems is receiving a lot of
attention [29] as there are many recorded incidents of discrimination (e.g.,
recidivism prediction [21], grades prediction [4, 15]) caused by such systems
against individuals or groups or people on the basis of _protected attributes_
like gender, race etc. Bias in education is not a new problem, rather there is
already a long literature on different sources of bias in education [25] or
students’ data analysis [3] as well as studies on racial bias [32] and gender
bias [23]. However, ML-based decision-making systems have the potential to
amplify prevalent biases or create new ones and therefore, fairness-aware ML
approaches are required also for the educational domain.

In this work, we focus on fairness in clustering, i.e., the balance of members
in cluster w.r.t protected attributes, as in educational activities, group
assignments [9] and student team achievement divisions [31] are important
tools in teaching and learning tasks to help students working together towards
shared learning goals. Better communication, higher-order thinking, conflict
management are several examples of the advantages of group assignments [9].
Clustering algorithms are effective solutions for partitioning students into
groups of _similar instances_ [3, 27]. Traditional algorithms, however, focus
solely on the similarity objective and do not consider the fairness of the
resulting clusters w.r.t. protected attributes like gender or race. However,
studies indicate that students might learn better in diverse student groups,
e.g., mixed-gender groups [12, 33]. Lately, fair-clustering solutions have
been proposed, e.g., [6], which aim to discover clusters with a fair
representation regarding some protected attributes.

In a teaching situation, one is often interested in certain group sizes which
are usually between 2–4 students per group in primary, secondary and
university education but might be much larger in adult education and Massive
Open Online Courses (MOOCs). It is obvious that the size of the groups should
be comparable to allow for a fair allocation of work among the students.
Again, traditional clustering algorithms do not consider this requirement, and
as a result, clusters of varying sizes might be extracted, reducing the
usefulness and applicability of the partitioning for the end-user/teacher.
This leads to the demand for clustering solutions that also take into account
the size of the clusters. The problem is known as _the capacitated clustering
problem (CCP)_ [26], which aims to extract clusters with a limited
capacity111We use the terms cluster capacity, cluster size and cluster
cardinality interchangeably to refer to the number of instances in a cluster.
while minimizing the total dissimilarity in the clusters. Capacitated
clustering is useful in many applications, e.g., transferring goods/services
from the service providers (post office, stores, etc.), garbage collection and
salesforce territorial design [28] to various customer locations [11]. To the
best of our knowledge, no solution exists that considers both fairness and
capacity of clusters on top of the similarity objective.

To this end, we propose a new problem, the so-called _fair-capacitated
clustering_ that ensures fairness and balanced cardinalities of the resulting
clusters. We decompose the problem into two subproblems: i) the fairness-
requirement compliance step that preserves fairness at a minimum threshold of
balance score and ii) the capacity-requirement compliance step that ensures
clusters of comparable sizes. For the first step, we generate fairlets [6],
which are minimal sets that satisfy fair representation w.r.t. a protected
attribute while approximately preserving the clustering objective. For the
second step, we propose two solutions for two different clustering types,
namely hierarchical and partitioning-based clustering, that consider the
capacity constraint during the merge step (for the hierarchical approach) and
during the assignment step (for the partitioning approach). Experimental
results, on four real datasets from the education domain, show that our
methods result in fair and capacitated clusters while preserving the
clustering quality.

The rest of our paper is structured as follows: Section 2 overviews the
related work. The fair-capacitated clustering problem is introduced in Section
3. Section 4 describes our proposed approaches and section 5 presents the
detail of experimental evaluation on educational datasets. Finally, the
conclusion and outlook are summarized in Section 6.

##  2 Related work

Chierichetti et al. [6] introduced the fair clustering problem with the aim to
ensure equal representation for each protected attribute, such as gender, in
every cluster. In their formulation, each instance is assigned with one of two
colors (red, blue). They proposed a two-phase approach: clustering all
instances into fairlets - small clusters preserving the fairness measure, and
then applying vanilla clustering methods ($k$-Center, $k$-Median) on those
fairlets. Subsequent studies focus on generalization and scalability. Backurs
et al. [1] presented an approximate fairlet decomposition algorithm which can
formulate the fairlets in nearly linear time thus tackling the efficiency
bottleneck of [6]. Rösner and Schmidt [30] generalize the fair clustering
problem to more than two protected attributes. A more generalized and tunable
notion of fairness for clustering was introduced in Bera et al. [2]. Anshuman
and Prasant [5] introduced a fair hierarchical agglomerative clustering method
for multiple protected attributes.

The capacitated clustering problem (CCP), a combinatorial optimization
problem, was first introduced by Mulvey and Beck [26] who proposed solutions
using heuristic and subgradient algorithms. Several approaches exist to
improve the efficiency of solutions or CCP approaches for different cluster
types. Khuller and Sussmann [18], for example, introduced an approximation
algorithm for the capacitated $k$-Center problem. Geetha et al. [11] improved
$k$-Means algorithm for CCP by using a priority measure to assign points to
their centroid. Lam and Mittenthal [20] proposed a heuristic hierarchical
clustering method for CCP to solve the multi-depot location-routing problem.

In this work, we introduce the problem of fair-capacitated clustering which
builds upon notions from fair clustering and capacitated clustering. In
particular, we build upon the notion of fairlets [6] to extract the minimal
sets that preserve fairness. Regarding the CCP we follow the formulation of
[26] to ensure balanced cluster cardinalities. To the best of our knowledge,
the combined problem has not been studied before and as already discussed,
comprises a useful tool in many domains like education.

##  3 Problem definition

Let $X\in\mathbb{R}^{n}$ be a set of instances to be clustered and let
$d():X\times X\rightarrow\mathbb{R}$ be the distance function. For an integer
$k$ we use $[k]$ to denote the set $\\{1,2,...,k\\}$. A k-clustering
$\mathcal{C}$ is a partition of $X$ into $k$ disjoint subsets,
$\mathcal{C}=\\{C_{1},C_{2},...,C_{k}\\}$, called clusters with
$S=\\{s_{1},s_{2},...,s_{k}\\}$ be the corresponding cluster centers. The goal
of clustering is to find an assignment222We focus on hard clustering where
each instance is only assigned to one cluster. $\phi:X\rightarrow[k]$ that
minimizes the objective function:

$\mathcal{L}(X,\mathcal{C})=\sum_{s_{i}\in S}\sum_{x\in C_{i}}d(x,s_{i})$ (1)

As shown in Eq. 1, the goal is to find an assignment that minimizes the sum of
distances between each point $x\in X$and its corresponding cluster center
$s_{i}\in S$. It is clear that such an assignment optimizes for similarity but
does not consider fairness or capacity of the resulting clusters.

Capacitated clustering: The goal of capacitated clustering [26] is to discover
clusters of given capacities while still minimizing the distance objective
$\mathcal{L}(X,\mathcal{C})$. The capacity constraint is defined as an upper
bound $Q_{i}$ on the cardinality of each cluster $C_{i}$:

$|C_{i}|\leq Q_{i}$ (2)

Clustering fairness:  We assume the existence of a binary protected attribute
$P=\\{0,1\\}$, e.g., gender={“male", “female"}. Let $\psi:X\rightarrow P$
denotes the demographic group to which the point belongs, i.e., male or
female.

Fairness of a cluster is evaluated in terms of the balance score [6] as the
minimum ratio between two groups.

$balance(C_{i})=\min\left(\frac{|\\{x\in C_{i}\mid\psi(x)=0\\}|}{|\\{x\in
C_{i}\mid\psi(x)=1\\}|},\frac{|\\{x\in C_{i}\mid\psi(x)=1\\}|}{|\\{x\in
C_{i}\mid\psi(x)=0\\}|}\right)$

(3)

Fairness of a clustering $\mathcal{C}$ equals to the balance of the least
balanced cluster $C_{i}\in\mathcal{C}$.

$balance(\mathcal{C})=\min_{C_{i}\in C}balance(C_{i})$ (4)

We now introduce the problem of fair-capacitated clustering that combines all
aforementioned objectives regarding distance, fairness and capacity.

######  Definition 1.

(Fair-capacitated clustering problem)
We define the problem of $(t,k,q)$-fair-capacitated clustering as finding a
clustering $\mathcal{C}=\\{C_{1},\cdots C_{k}\\}$ that partitions the data $X$
into $|\mathcal{C}|=k$ clusters such that the cardinality of each cluster
$C_{i}\in\mathcal{C}$ does not exceed a threshold $q$, i.e., $|C_{i}|\leq q$
(_the capacity constraint_), the balance of each cluster is at least $t$,
i.e., $balance(\mathcal{C})\geq t$ (_the fairness constraint_), and minimizes
_the objective function_ $\mathcal{L}(X,\mathcal{C})$. Parameters $k,t,q$ are
user defined referring to the number of clusters, minimum balance threshold
and maximum cluster capacity, respectively.

##  4 Fair-capacitated clustering

In this section, we propose two $(t,k,q)$ fair-capacitated clustering
approaches, one for hierarchical clustering and the second for partitioning-
based clustering. For both cases, we decompose the complex problem into two
simpler subproblems: i) the fairlet decomposition step that divides the
original points into set of points, the so-called fairlets, each preserving a
balance score subject to the balance threshold $t$ (Section 4.1) and ii) the
final clustering step that clusters these fairlets into $k$ final clusters so
that the cardinality constraint subject to the cardinality threshold $q$ is
met. Step (ii) depends on the clustering type: for hierarchical clustering,
the merge step needs to be changed (Section 4.2), whereas for the
partitioning-based clustering the assignment step needs to change (Section
4.3).

###  4.1 Fairlet decomposition

Traditionally, the vanilla versions of clustering algorithms are not capable
of ensuring fairness because they assign the data points to the closest center
without the fairness consideration. Hence, if we could divide the original
data set into subsets such that each of them satisfies the balance threshold
$t$ then grouping these subsets to generate the final clustering would still
preserve the fairness constraint. Each fair subset is defined as a fairlet. We
follow the definition of fairlet decomposition by [6].

######  Definition 2.

(Fairlet decomposition)
Suppose that $balance(X)\geq t$ with $t=f/m$ for some integers $1\leq f\leq
m$, such that the greatest common divisor $gcd(f,m)=1$. A decomposition
$\mathcal{F}=\\{F_{1},F_{2},...,F_{l}$} of $X$ is a fairlet decomposition if:
i) each point $x\in X$ belongs to exactly one fairlet $F_{j}\in\mathcal{F}$,
ii) $|F_{j}|\leq f+m$ for each $F_{j}\in\mathcal{F}$, i.e., the size of each
fairlet is small, and iii) for each $F_{j}\in\mathcal{F}$, $balance(F_{j})\geq
t$, i.e., the balance of each fairlet satisfies the threshold $t$. Each
$F_{j}$ is called a fairlet.

By applying fairlet decomposition on the original dataset $X$, we obtain a set
of fairlets $\mathcal{F}=\\{F_{1},F_{2},\ldots,F_{l}\\}$. For each fairlet
$F_{j}$ we select randomly a point $r_{j}\in F_{j}$ as the center. For a point
$x\in X$, we denote $\gamma:X\rightarrow[1,l]$ as the index of the mapped
fairlet.

The second step, is to cluster the set of fairlets
$\mathcal{F}=\\{F_{1},F_{2},$ $\ldots,F_{l}\\}$ into $k$ final clusters,
subject to the cardinality constraint. The clustering process is described
below for the hierarchical clustering type (Section 4.2) and for the
partitioning-based clustering type (Section 4.3). Clustering results in an
assignment from fairless to final clusters:
$\delta:\mathcal{F}\rightarrow[k]$. The final fair-capacitated clustering
$\mathcal{C}$ can be determined by the overall assignment function
$\phi(x)=\delta(F_{\gamma(x)})$, where $\gamma(x)$ returns the index of the
fairlet to which $x$ is mapped.

###  4.2 Fair-capacitated hierarchical clustering

Given the set of fairlets: $\mathcal{F}=\\{F_{1},F_{2},\ldots,F_{l}\\}$, let
$W=\\{w_{1},w_{2},\ldots,w_{l}\\}$ be their corresponding weights, where the
weight $w_{j}$ of a fairlet $F_{j}$ is defined as its cardinality, i.e.,
number of points in $F_{j}$.

Traditional agglomerative clustering approaches merge the two closest
clusters, so rely solely on similarity. We extend the merge step by also
ensuring that merging does not violate the cardinality constraint w.r.t. the
cardinality threshold $q$.

###### Theorem 1

The balance score of a cluster formed by the union of two or more fairlets, is
at least $t$.

$balance(\mathcal{Y})\geq t,~{}\text{where}~{}\mathcal{Y}=\cup_{j\leq
l}F_{j}~{}\text{and}~{}balance(F_{j})\geq t$

###### Proof.

We use the method of induction to derive the proof. Assume we have a set of
fairlets $\mathcal{F}=\\{F_{1},F_{2},\ldots,F_{l}\\}$, in which,
$balance(F_{j})\geq t$, $~{}j={1,\ldots,l}$. We first consider the case for
any two fairlets $\\{F_{1},F_{2}\\}\in\mathcal{F}$. We have $\displaystyle
balance(F_{1})=\frac{f_{1}}{m_{1}}\geq t$ and $\displaystyle
balance(F_{2})=\frac{f_{2}}{m_{2}}\geq t$. We denote by $\mathcal{Y}$ is the
union of two fairlets $F_{1}$ and $F_{2}$, then

$balance(\mathcal{Y})=balance(F_{1}\cup
F_{2})=\frac{f_{1}+f_{2}}{m_{1}+m_{2}}$ (5)

It holds:

$\displaystyle\frac{f_{1}}{m_{1}}\geq t$ (6)
$\displaystyle\text{or,}~{}\frac{f_{1}}{m_{1}+m_{2}}\geq\frac{tm_{1}}{m_{1}+m_{2}}$
$\displaystyle\text{Similarly,}~{}\frac{f_{2}}{m_{1}+m_{2}}\geq\frac{tm_{2}}{m_{1}+m_{2}}$
$\displaystyle\implies\frac{f_{1}}{m_{1}+m_{2}}+\frac{f_{2}}{m_{1}+m_{2}}\geq\frac{tm_{1}}{m_{1}+m_{2}}+\frac{tm_{2}}{m_{1}+m_{2}}$
$\displaystyle\implies\frac{f_{1}+f_{2}}{m_{1}+m_{2}}\geq\frac{t(m_{1}+m_{2})}{m_{1}+m_{2}}=t$

Therefore, from Eq. 5 and Eq. 6 we get,

$balance(\mathcal{Y})\geq t$ (7)

Thus, the statement given in Theorem 1 is true for any cluster formed by the
union of any two fairlets. Now we assume that the statement holds true for a
cluster formed from $i$ fairlets, i.e, $\mathcal{Y}=\cup_{j\leq i}F_{j}$,
where $1<i<l$. Then,

$\displaystyle balance(\mathcal{Y})=\frac{\sum_{j\leq i}f_{j}}{\sum_{j\leq
i}m_{j}}\geq t$ (8)

Consider another fairlet $F_{i+1}\in\mathcal{F}$ which is not in the formed
cluster $\mathcal{Y}$, $\displaystyle
balance(F_{i+1})=\frac{f_{i+1}}{m_{i+1}}\geq t$. Then, by joining $F_{i+1}$
with the cluster $\mathcal{Y}$ we get the new cluster
$\mathcal{Y}^{{}^{\prime}}$ such that,

$\displaystyle balance(\mathcal{Y}^{{}^{\prime}})=\frac{f_{i+1}+\sum_{j\leq
i}f_{j}}{m_{i+1}+\sum_{j\leq i}m_{j}}$ (9)

Following the steps in Eq. 6, we can similarly show that,

$\displaystyle\frac{f_{i+1}+\sum_{j\leq i}f_{j}}{m_{i+1}+\sum_{j\leq
i}m_{j}}\geq t$ (10) $\displaystyle\implies
balance(\mathcal{Y}^{{}^{\prime}})\geq t$

Hence, the theorem holds true for cluster formed with $i+1$ fairlets if it is
true for $i$ fairlets. Since $i$ is any arbitrary number of fairlets, thus the
theorem holds true for all cases. ∎

Theorem 1 shows that for any cluster formed by union of fairlets, the fairness
constraint is always preserved. Henceforth, we don’t need further
interventions w.r.t. fairness.

The pseudocode is shown in Algorithm 1. In each step, the closest pair of
clusters is identified (line 4) and a new cluster is created (line 6) only if
its capacity does not exceed the capacity threshold $q$. Otherwise, the next
closest pair is investigated. The procedure continues until $k$ clusters
remain. The remaining clusters are fair and capacitated according to the
correponding thresholds $t$ and $q$.

To compute the proximity matrix (line 1 and line 1), we use the distance
between centroids of the corresponding clusters. The function
$capacity(cluster)$ in line 1 returns the size of a cluster.

Input: $\mathcal{F}=\\{F_{1},F_{2},\ldots,F_{l}\\}$: a set of fairlets
$q$: a given maximum capacity of final clusters
$W=\\{w_{1},w_{2},\ldots,w_{l}\\}$: weights of fairlets
$k$: number of clusters

Output: A fair-capacitated clustering

1 compute the proximity matrix ;

2 $clusters\leftarrow\mathcal{F}$ //each fairlet $F_{j}$ is considered as
cluster ;

3 repeat

4 $cluster_{1},cluster_{2}\leftarrow$ the closest pair of clusters ;

5 if  _$capacity(cluster_{1})+capacity(cluster_{2})\leq q$_ then

6 $newcluster\leftarrow$ merge($cluster_{1},cluster_{2}$);

7 update $clusters$ with $newcluster$;

8 update the proximity matrix ;

9

10 else

11 continue;

12

13 end if

14

15until  _$k$ clusters remain_;

16return _$clusters$_ ;

Algorithm 1 Hierarchical fair-capacitated algorithm

###  4.3 Fair-capacitated partitioning-based clustering

Partitioning-based clustering algorithms, such as $k$-Medoids, can be viewed
as a distance minimization problem, in which, we try to minimize the objective
function in Eq. 1, i.e., minimize the sum of the distance from every $x_{j}\in
X$ to its medoid $s_{i}$. The vanilla $k$-Medoids does not satisfy a
cardinality constraint since the allocating points to clusters step is only
based on the distance among them. Now, if we change the goal of this
assignment step to find the “best" data points with a defined capacity for
each medoid instead of searching for the most suitable medoid for each point,
we can control the cardinality of clusters. We formulate the problem of
_assigning points to clusters_ subject to a capacity threshold $q$ as a
knapsack problem [24].

At a given $k$-Medoids assignment step, let $S=\\{s_{1},s_{2},...,s_{k}\\}$ be
the cluster centers, i.e., medoids, $\mathcal{C}=\\{C_{1},C_{2},...,C_{k}\\}$
be the resulting clusters. We change the assignments of points to clusters,
using knapsack, in order to meet the capacity constraint $q$. In particular,
we define a flag variable $y_{j}=1$ if $x_{j}$ is assigned to cluster $C_{i}$,
otherwise $y_{j}=0$. Now, if we assign a value $v_{j}$ to data point $x_{j}$,
which depends on the distance of $x_{j}$ to $C_{i}$, with $v_{j}$ being
maximum if $C_{i}$ is the best cluster for $x_{j}$, i.e, the distance between
$x_{j}$ and $s_{i}$ is minimum. We define the value $v_{j}$ of instance
$x_{j}$ based on an exponential decay distance function:

$v_{j}=e^{-\frac{1}{\lambda}*d(x_{j},s_{i})}$ (11)

where $d(x_{j},s_{i})$ is the Euclidean distance between the point $x_{j}$ and
the medoid $s_{i}$. The higher $\lambda$ is the lower the effect of distance
in the value of the points. The point which is closer to the medoid will have
a higher value.

Then, the objective function for the assignment step becomes:

$\displaystyle\textrm{maximize}\sum_{j=1}^{n}v_{j}y_{j}$ (12)

Now, given $\mathcal{F}=\\{F_{1},F_{2},\ldots,F_{l}\\}$ and
$W=\\{w_{1},w_{2},\ldots,w_{l}\\}$ are the set of fairlets and their
corresponding weights respectively; $q$ is the maximum capacity of the final
clusters. Our target is to cluster the set of fairlets $\mathcal{F}$ into $k$
clusters centered by $k$ medoids. We apply the formulas in Eq. 11 and Eq.12 on
the set of fairlets $\mathcal{F}$, i.e, each fairlet $F_{j}$ has the same role
as $x_{j}$. Then, the problem of assigning the fairlets to each $medoid$ in
the cluster assignment step becomes finding a set of fairlets with the total
weights is less than or equal to $q$ and the total value is maximized. In
other words, we can formulate the cluster assignment step in the partitioning-
based clustering as a 0-1 knapsack problem.

$\textrm{maximize}\sum_{j=1}^{l}v_{j}y_{j}$ (13) $\textrm{subject
to}\quad\sum_{j=1}^{l}w_{j}y_{j}\leq q\quad\textrm{and}\quad
y_{j}\in\\{0,1\\}$ (14)

In which, $y_{j}$ is the flag variable for $F_{j}$, $y_{j}=1$ if $F_{j}$ is
assigned to a cluster, otherwise $y_{j}=0$ ; $v_{j}$ is the value of $F_{j}$
which is computed by the Eq. 11; $q$ is the desired maximum capacity.

The pseudocode of our $k$-Medoids fair-capacitated algorithm is described in
Algorithm 2. In which, for each medoid we would search for the adequate points
(line 2) by using function $knapsack(p,values,w,q)$ (line 2) implemented using
dynamic programming, which returns a list of items with a maximum total value
and the total weight not exceeding $q$. In the main function, line 2, we
optimize the clustering cost by replacing $medoids$ with non-medoid instances
when the clustering cost is decreased. This optimization procedure will stop
when there is no improvement in the clustering cost is found (lines 2 to 2).

Input: $\mathcal{F}=\\{F_{1},F_{2},\ldots,F_{l}\\}$: a set of fairlets
$W=\\{w_{1},w_{2},\ldots,w_{l}\\}$: weights of fairlets
$q$: a given maximum capacity of final clusters
$k$: number of clusters

Output: A fair-capacitated clustering

1

2 Function  _ClusterAssignment(_$medoids$_)_:

3 $clusters\leftarrow\emptyset$;

4 for  _each medoid $s$ in medoids_ do

5 candidates $\leftarrow$ all fairlets which are not assigned to any cluster ;

6 $p$ $\leftarrow$ length(candidates) ;

7 $w$ $\leftarrow$ weights(candidates) ;

8 for  _each $fairlet_{i}$ in candidates_ do

9 $values[i]$ $\leftarrow$ $v(fairlet_{i})$ //Eq. 11 ;

10

11 end for

12 $clusters[s]$$\leftarrow$knapsack($p$, $values$, $w$, $q$) ;

13

14 end for

15 return $clusters$;

16

17

18 Function  _main(__)_ :

19

20 $medoids\leftarrow$ select $k$ of the $l$ fairlets arbitrarily ;

21 ClusterAssignment(medoids) ;

22 $cost_{best}\leftarrow$ current clustering cost;

23 $s_{best}\leftarrow null$ ;

24 $o_{best}\leftarrow null$ ;

25

26 repeat

27 for  _each medoid $s$ in medoids_ do

28 for  _each non-medoid $o$ in $\mathcal{F}$_ do

29 consider the swap of $s$ and $o$, compute the current clustering cost;

30 if  _current clustering cost < $cost_{best}$_ then

31 $s_{best}\leftarrow s$;

32 $o_{best}\leftarrow o$;

33 $cost_{best}\leftarrow current~{}clustering~{}cost$;

34

35 end if

36

37 end for

38

39 end for

40 update $medoids$ by the swap of $s_{best}$ and $o_{best}$ ;

41 ClusterAssignment(medoids)

42 until  _no improvements can be achieved by any replacement_ ;

43

44 return _$clusters$_ ;

Algorithm 2 $k$-Medoids fair-capacitated algorithm

##  5 Experiments

In this section, we describe our experiments and the performance of our
proposed algorithms on four real educational datasets.

###  5.1 Experimental setup

####  5.1.1 Datasets

We evaluate our proposed methods on four public datasets. An overview of
datasets is presented in Table 1.

Table 1: An overview of the datasets Dataset | #instances | #attributes | Protected attribute | Balance score
---|---|---|---|---
UCI student performance-Mathematics | 395 | 33 | Sex (F: 208, M: 187 ) | 0.899
UCI student performance-Portuguese | 649 | 33 | Sex (F: 383; M: 266) | 0.695
PISA test scores | 3,404 | 24 | Male (1: 1,697; 0: 1,707 ) | 0.994
OULAD | 4,000 | 12 | Gender (F: 2,000; M: 2,000) | 1
MOOC | 4,000 | 21 | Gender (F: 2,000; M: 2,000) | 1

UCI student performance. This dataset includes the demographics, grades,
social and school-related features of students in secondary education of two
Portuguese schools [7] in 2005 - 2006 with two distinct subjects: Mathematics
and Portuguese. We encode all categorical attributes by using a one-hot
encoding technique. “Sex" is selected as the protected attribute, i.e., we aim
to balance gender in the resulting clusters.

PISA test scores. The dataset contains information about the demographics and
schools of American students [8] taking the exam in 2009 from the Program for
International Student Assessment (PISA) distributed by the United States
National Center for Education Statistics (NCES). “Male" which contains two
values $\\{1,0\\}$ is chosen as the protected attribute.

Open University Learning Analytics (OULAD). This is the dataset from the OU
Analyse project [19] of Open University, England in 2013 - 2014. Information
of students includes their demographics, courses, their interactions with the
virtual learning environment, and their final outcome. We aim to balance the
“Gender" attribute in the resulting clusters.

MOOC. The data covers students who enrolled in the 16 edX courses offered by
the two institutions (Harvard University and the Massachusetts Institute of
Technology) during 2012-2013 [14]. The dataset contains aggregated records
which represent students’ activities and their final grades of the courses.
“Gender" is the protected attribute for fairness in our experiments.

####  5.1.2 Baselines

We compare our approaches against well-known clustering methods, including
fairness-aware algorithms and a traditional one.

$k$-Medoids. $k$-Medoids clustering [17] is a traditional partitioning
technique of clustering that divides the dataset into $k$ clusters and
minimizes the clustering cost. $k$-Medoids uses the actual instances as
centers.

Vanilla fairlet. This is the approach proposed by Chierichetti et al. [6]. The
first phase computes a vanilla fairlet decomposition that ensures fair
clusters, but it might not give the optimal cost value. A vanilla $k$-Center
clustering algorithm [13] is applied to cluster those fairlets into $k$
clusters in the second step.

MCF fairlet. In this version [6], the fairlet decomposition is transformed
into a minimum cost flow (MCF) problem, by which an optimized version of
fairlet decomposition in terms of cost value is computed. Like the vanilla
version, a $k$-Center method is used to cluster fairlets in the second phase.

In our experiments, both resulting fairlets generated by vanilla fairlet and
MCF fairlet methods are used for our proposed fair-capacitated clustering
algorithms. Therefore, we have two versions each proposed methods, namely
Vanilla fairlet hierachical fair-capaciated and MCF fairlet hierachical fair-
capacitated (for the hierarchical approach), Vanilla fairlet k-Medoids fair-
capacitated and MCF fairlet k-Medoids fair-capacitated (for the partitioning
approach). Section 5.2 presents the experimental results of these methods.

####  5.1.3 Measurement

We report our experimental results on clustering cost, balance score, and
capacity. The clustering cost is used for evaluating the quality of
clustering, which is measured by the formula given in Eq. 1. The fairness of
clustering is measured by the balance score in Eq. 4.

####  5.1.4 Parameter selection

Regarding fairness, a minimum threshold of balance $t$ is set to 0.5 for all
datasets in our experiments. It means that the proportion of the minority
group (e.g.,: female) is at least 50% in the resulting clusters. Regarding the
$\lambda$ factor in Eq. 11, a value $\lambda=0.3$ is chosen for our
experiments from a range of [0.1, 1.0] via grid-search. We evaluate the
clustering cost and balance score on a small dataset, i.e., UCI student
performance dataset - Mathematics subject w.r.t $\lambda$.

Theoretically, the ideal capacity of clusters is
$\displaystyle\Big{\lceil}\frac{|X|}{k}\Big{\rceil}$ where $|X|$ is the
population of dataset $X$, $k$ is the number of desired clusters. However, in
many cases, the clustering models cannot satisfy this constraint, especially
the hierarchical clustering model. Hence, we set the formula in Eq. 15 to
compute the maximum capacity $q$ of clusters; $\varepsilon$ is a parameter
chosen in experiments for each fair-capacitated clustering approach.

$q=\Big{\lceil}\frac{|X|*\varepsilon}{k}\Big{\rceil}$ (15)

In our experiments, to find the appropriate value of $\varepsilon$, we set a
range of [1.0, 1.3] to ensure all the generated clusters have members. We
evaluate the cardinality of resulting clusters on the UCI student performance
dataset - Mathematics subject. Based on this, $\varepsilon$ is set to 1.01 and
1.2, for $k$-Medoids fair-capacitated and hierarchical fair-capacitated
methods, respectively.

###  5.2 Experimental results

####  5.2.1 UCI student performance - Mathematics

In Figure 1-a, the clustering cost of all methods is worse compared to that of
the vanilla $k$-Medoids clustering. This is expected as these methods have to
satisfy constraints on fairness or/and cardinality. However, both of our
approaches outperform the vanilla fairlet and MCF fairlet methods. In which,
MCF fairlet hierarchical fair-capacitated shows the best performance due to
the optimization in the merging step. Regarding fairness, as shown in Figure
1-b, the minimum threshold of balance $t$ is visualized as a dashed line while
the actual balance from the dataset is plotted as a dotted line. All of our
methods are comparative to the competitors in almost cases. Interestingly, our
vanilla fairlet $k$-Medoids fair-capacitated method outperforms the
competitive methods when $k$ is less than 10. In terms of cardinality, as
presented in Figure 1-c, the maximum capacity thresholds $q$ are indicated by
the figure’s dashed and dotted lines. Our capacitated variants are superior
(lower dispersion as shown by the interquartile ranges). We have to thicken
the boxplots of our proposed methods since in many cases the dispersion in the
size of the resulting clusters is too small. MCF fairlet shows the worst
performance in terms of cardinality, followed by Vanilla fairlet and vanilla
$k$-Medoids.

Figure 1: Performance of different methods on UCI student performance dataset
- Mathematics subject

####  5.2.2 UCI student performance - Portuguese

When $k$ is less than 4, as shown in Figure 2-a, the clustering quality of our
models can be close to that of the vanilla $k$-Medoids method. However, the
clustering cost is fluctuated thereafter due to the effort to maintain the
fairness and cardinality of methods. Our vanilla fairlet hierarchical fair-
capacitated outperforms other competitors in most cases. Vanilla fairlet and
MCF fairlet show the worst clustering cost as an effect of the $k$-Center
method. Figure 2-b depicts the clustering fairness. As we can observe, in
terms of fairness, vanilla fairlet hierarchical fair-capacitated has the best
performance when $k$ is less than 10. Contrary to that, by selecting each
point for each cluster in the cluster assignment step, the $k$-Medoids fair-
capacitated method can maintain well the fairness in many cases. Regarding the
cardinality, as illustrated in Figure 2-c, our approaches outperform the
competitors when they can keep the number of instances for each cluster under
the specified thresholds.

Figure 2: Performance of different methods UCI student performance dataset -
Potuguese subject

####  5.2.3 PISA test scores

Although the clustering cost increases in most methods, as presented in Figure
3-a, our approaches outperform the competitors vanilla fairlet and MCF
fairlet. The hierarchical approach shows the best performance compare to other
methods which are concerned with equity and capacity. Interestingly, our
proposed methods outperform the competitors when they can preserve very well
the balance score for all number of clusters in terms of fairness (Figure
3-b). This is explained by fairness in the fairlets that are used as the input
for our clustering method. It is easy to observe in Figure 3-c that our
proposed methods strictly follow the maximum capacities of clusters regarding
the cardinality. MCF fairlet is the worst model, followed by $k$-Medoids and
vanilla fairlet and MCF fairlet.

Figure 3: Performance of different methods on PISA Test Score dataset

####  5.2.4 OULAD

Our MCF fairlet $k$-Medoids fair-capacitated approach outperforms other
methods in terms of clustering cost, although there is an increase compared to
the vanilla $k$-Medoids algorithm, as we can see in Figure 4-a. Concerning
fairness, in Figure 4-b, $k$-Medoids is the weakest method while others can
achieve the highest balance. The balance of Gender feature in the dataset is
the main reason for this result. All fairlets are fully fair; this is a
prerequisite for our methods of being able to maintain the perfect balance.
Regarding cardinality, our approaches demonstrate their strength in ensuring
the capacity of clusters (Figure 4-c). The difference in the size of the
clusters generated by our methods is tiny. This is in stark contrast to the
trend of competitors.

Figure 4: Performance of different methods on OULAD dataset

####  5.2.5 MOOC

The results of clustering quality are described in Figure 5-a. Although an
increase in the clustering cost is the main trend, our methods outperform the
vanilla fairlet and MCF fairlets methods. Regarding clustering fairness, as
depicted in Figure 5-b, our approaches can maintain the perfect balance for
all experiments. This is the result of the actual balance in the dataset and
the fairlets. The emphasis is our methods can divide all the experimented
instances into capacitated clusters, as presented in Figure 5-c, which proves
their superiority in presenting the results over the competitors regarding the
cardinality of clusters.

Figure 5: Performance of different methods on MOOC dataset

####  5.2.6 Summary of the results

In general, fairness is well maintained in all of our experiments. When the
data is fair, in case of OULAD and MOOC datasets, our methods achieve perfect
fairness. In terms of cardinality, our methods are able to maintain the
cardinality of resulting clusters within the maximum capacity threshold, which
is significantly superior to competitive methods. The fair-capacitated
partitioning based method is better than the hierarchical approach since it
can determine the capacity threshold closest to the ideal cardinality
mentioned in Section 5.1.4. Regarding the clustering cost, the hierarchical
approach has an advantage over other methods by outperforming its competitors
in most experiments.

##  6 Conclusion and Outlook

In this work, we introduced the fair-capacitated clustering problem that
extends traditional clustering, solely focusing on similarity, by also aiming
at a balanced cardinality among the clusters and a fair-representation of
instances in each cluster according to some protected attribute like gender or
race. Our solutions work on the fairlets derived from the original instances:
the hierarchical-based approach takes into account the cardinality requirement
during the merging step, whereas the partitioning-based approach takes into
account the cardinality of the final clusters during the assignment step which
is formulated as a knapsack problem. Our experiments show that our methods are
effective in terms of fairness and cardinality while maintaining clustering
quality. Apart from the educational field, the fair-capacitated clustering
problem can contribute to other applications such as clustering of customers
in marketing studies, vehicle routing and communication network design. An
immediate future direction is to improve the clustering quality by optimizing
the cluster assignment phase of the partitioning-based approaches. Moreover,
we plan to extend our work for multiple protected attributes.

## References

  * [1] A. Backurs, P. Indyk, K. Onak, B. Schieber, A. Vakilian, and T. Wagner.  Scalable fair clustering.  In International Conference on Machine Learning, pages 405–413. PMLR, 2019.
  * [2] S. Bera, D. Chakrabarty, N. Flores, and M. Negahbani.  Fair algorithms for clustering.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
  * [3] S. Bharara, S. Sabitha, and A. Bansal.  Application of learning analytics using clustering data mining for students’ disposition analysis.  Education and Information Technologies, 23(2):957–984, 2018.
  * [4] K. Bhopal and M. Myers.  The impact of covid-19 on a level students in england.  SocArXiv, 2020.
  * [5] A. Chhabra and P. Mohapatra.  Fair algorithms for hierarchical agglomerative clustering.  arXiv preprint arXiv:2005.03197, 2020.
  * [6] F. Chierichetti, R. Kumar, S. Lattanzi, and S. Vassilvitskii.  Fair clustering through fairlets.  In NIPS 2017, pages 5036–5044, 2017.
  * [7] P. Cortez and A. M. G. Silva.  Using data mining to predict secondary school student performance.  EUROSIS-ETI, 2008.
  * [8] H. L. Fleischman, P. J. Hopstock, M. P. Pelczar, and B. E. Shelley.  Highlights from pisa 2009: Performance of us 15-year-old students in reading, mathematics, and science literacy in an international context. nces 2011-004.  National Center for Education Statistics, 2010.
  * [9] M. Ford and J. Morice.  How fair are group assignments? a survey of students and faculty and a modest proposal.  Journal of Information Technology Education: Research, 2(1):367–378, 2003.
  * [10] J. Gardner, C. Brooks, and R. Baker.  Evaluating the fairness of predictive student models through slicing analysis.  In LAK’19, pages 225–234, 2019.
  * [11] S. Geetha, G. Poonthalir, and P. Vanathi.  Improved k-means algorithm for capacitated clustering problem.  INFOCOMP, 8(4):52–59, 2009.
  * [12] D. Gnesdilow, A. Evenstone, J. Rutledge, S. Sullivan, and S. Puntambekar.  Group work in the science classroom: How gender composition may affect individual performance.  2013\.
  * [13] T. F. Gonzalez.  Clustering to minimize the maximum intercluster distance.  Theoretical computer science, 38:293–306, 1985.
  * [14] HarvardX.  HarvardX Person-Course Academic Year 2013 De-Identified dataset, version 3.0, 2014.
  * [15] S. Hubble and P. Bolton.  A level results in england and the impact on university admissions in 2020-21.  House of Commons Library, 2020.
  * [16] S. Hutt, M. Gardner, A. L. Duckworth, and S. K. D’Mello.  Evaluating fairness and generalizability in models predicting on-time graduation from college applications.  International Educational Data Mining Society, 2019.
  * [17] L. Kaufman and P. J. Rousseeuw.  Partitioning around medoids (program pam).  Finding groups in data: an introduction to cluster analysis, 344:68–125, 1990.
  * [18] S. Khuller and Y. J. Sussmann.  The capacitated k-center problem.  SIAM Journal on Discrete Mathematics, 13(3):403–418, 2000.
  * [19] J. Kuzilek, M. Hlosta, and Z. Zdrahal.  Open university learning analytics dataset.  Scientific data, 4:170171, 2017.
  * [20] M. Lam and J. Mittenthal.  Capacitated hierarchical clustering heuristic for multi depot location-routing problems.  Int. J. Logist. Res. Appl., 16(5):433–444, 2013.
  * [21] J. Larson, S. Mattu, L. Kirchner, and J. Angwin.  How we analyzed the compas recidivism algorithm.  ProPublica (5 2016), 9(1), 2016.
  * [22] F. Marcinkowski, K. Kieslich, C. Starke, and M. Lünich.  Implications of ai (un-) fairness in higher education admissions: the effects of perceived ai (un-) fairness on exit, voice and organizational reputation.  In FAT*2020, pages 122–130, 2020.
  * [23] T. Masterson.  An empirical analysis of gender bias in education spending in paraguay.  World Development, 40(3):583–593, 2012.
  * [24] G. B. Mathews.  On the partition of numbers.  Proceedings of the London Mathematical Society, 1(1):486–490, 1896\.
  * [25] M. Meaney and T. Fikes.  Early-adopter iteration bias and research-praxis bias in the learning analytics ecosystem.  In LAK’19, Fairness and Equity in Learning Analytics Systems Workshop, pages 14–20, 2019.
  * [26] J. M. Mulvey and M. P. Beck.  Solving capacitated clustering problems.  European Journal of Operational Research, 18(3):339–348, 1984.
  * [27] Á. A. M. Navarro and P. M. Ger.  Comparison of clustering algorithms for learning analytics with educational datasets.  IJIMAI, 5(2):9–16, 2018.
  * [28] M. Negreiros and A. Palhano.  The capacitated centred clustering problem.  Computers & operations research, 33(6):1639–1663, 2006.
  * [29] E. Ntoutsi, P. Fafalios, U. Gadiraju, V. Iosifidis, W. Nejdl, M.-E. Vidal, S. Ruggieri, F. Turini, S. Papadopoulos, E. Krasanakis, et al.  Bias in data-driven artificial intelligence systems-an introductory survey.  Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 10(3):e1356, 2020.
  * [30] C. Rösner and M. Schmidt.  Privacy preserving clustering with constraints.  arXiv preprint arXiv:1802.02497, 2018.
  * [31] M. Tiantong and S. Teemuangsai.  Student team achievement divisions (stad) technique through the moodle to enhance learning achievement.  International Education Studies, 6(4):85–92, 2013.
  * [32] N. Warikoo, S. Sinclair, J. Fei, and D. Jacoby-Senghor.  Examining racial bias in education: A new approach.  Educational Researcher, 45(9):508–514, 2016.
  * [33] Z. Zhan, P. S. Fong, H. Mei, and T. Liang.  Effects of gender grouping on students’ group performance, individual achievements and attitudes in computer-supported collaborative learning.  Computers in Human Behavior, 48:587–596, 2015.