Scalable Fair Clustering

Introduction

The success of machine learning led to its widespread adoption in many aspects of our daily lives. Automatic prediction and forecasting methods are now used to approve mortgage applications or estimate the likelihood of recidivism (Chouldechova, 2017). It is thus crucial to design machine learning algorithms that are fair, i.e., do not suffer from bias against or towards particular population groups. An extensive amount of research over the last few years has focused on two key questions: how to formalize the notion of fairness in the context of common machine learning tasks, and how to design efficient algorithms that conform to those formalizations. See e.g., the survey by Chouldechova and Roth (2018) for an overview.

In this paper we focus on the second aspect. Specifically, we consider the problem of fair clustering and propose efficient algorithms for solving this problem. Fair clustering, introduced in (Chierichetti et al., 2017), generalizes the standard notion of clustering by imposing a constraint that all clusters must be balanced with respect to specific sensitive attributes, such as gender or religion. In the simplest formulation, each input point is augmented with one of two colors (say, red and blue), and the goal is to cluster the data while ensuring that, in each cluster, the fraction of points with the less frequent color is bounded from below by some parameter strictly greater than . Chierichetti et al. proposed polynomial time approximation algorithms for fair variants of classic clustering methods, such as $k$-center (minimize the maximum distance between points and their cluster centers) and $k$-median (minimize the average distance between points and their cluster centers). To this end, they introduced the notion of fairlet decomposition: a partitioning of the input pointset into small subsets, called fairlets, such that a good balanced clustering can be obtained by merging fairlets into clusters. Unfortunately, their algorithm for computing a fairlet decomposition has running time that is at least quadratic in the number of the input points. As a result, the algorithm is applicable only to relatively small data sets.

In this paper we address this drawback and propose an algorithm for computing fairlet decompositions with running time that is near-linear in the data size. We focus on the $k$-median formulation, as $k$-center clustering is known to be sensitive to outliers. Our algorithms apply to the typical case where the set of input points lie in a $d$-dimensional space, and the distance is induced by the Euclidean norm.E.g., all data sets used to evaluate the algorithms in (Chierichetti et al., 2017) fall into this category.

The running time can be reduced further by applying dimensionality reduction techniques, see, e.g., (Cohen et al., 2015; Makarychev et al., 2018) and the references therein.

We complement our theoretical analysis with empirical evaluation. Our experiments show that the quality of the clustering obtained by our algorithm is comparable to that of Chierichetti et al. (2017). At the same time, the empirical runtime of our algorithm scales almost linearly in the number of points, making it applicable to massive data sets (see Figure 2).

Since the original paper of Chierichetti et al. (2017), there has been several followup works studying fair clustering. In particular, Rösner and Schmidt (2018) and Bercea et al. (2018) studied the fair variant of $k$-center clustering (as opposed to $k$-median in our case). Furthermore, the latter paper presented a “bi-criteria” approximation algorithm for $k$-median and $k$-means under a somewhat different notion of fairness. However, their solution relies on a linear program that is a relaxation of an integer linear program with at least $n^{2}$ variables, one for every pair of points. Thus, their algorithm does not scale well with the input size. Another algorithm proposed in Bera et al. (2019), requires solving a linear program with $nk$ variables. Due to the special structure of the LP it is plausible that it can be solved efficiently, but we are not aware of any empirical evaluation of this approach.

The work most relevant to our paper is a recent manuscript by Schmidt et al. (2018), which proposed efficient streaming algorithms for fair $k$-means (which is similar to $k$-median studied here). Specifically, they give a near-linear time streaming algorithm for computing a core-set: a small subset $S\subseteq P$ such that solving fair clustering over $S$ yields an approximate solution for the original point-set $P$. In order to compute the final clustering, however, they still need to apply a fair clustering algorithm to the core-set. Thus, our approach is complementary to the core-set approach, and the two can be combined to yield algorithms which are both fast and space-efficientWe note, however, that since core-sets typically require assigning weights to data points, such combination requires extending the clustering algorithm to weighted pointsets. In this paper we do not consider the weighted case..

We note that the above algorithms guarantee constant approximation factors, as opposed to the logarithmic factor in our paper. As we show in the experimental section, this does not seem to affect the empirical quality of solutions produced by our algorithm. Still, designing a constant factor algorithm with a near-linear running time is an interesting open problem.

Possible settings of (r,b)𝑟𝑏(r,b).

Chierichetti et al. (2017) gave $(r,b)$-fairlet decomposition algorithms only for $b=1$. This does not allow for computing a full decomposition of the pointset into well-balanced fairlets if the numbers of red and blue points are close but not equal (for instance, if their ratio is 9:10). One way to address this could be to downsample the larger set in order to make them have the same cardinality and then compute a $(1,1)$-fairlet decomposition. The advantage of our approach is that we do not disregard any, even random, part of the input. This may potentially lead to much better solutions, partially by allowing that the clusters are not ideally balanced. The general settings of $r$ and $b$ are also considered by Bercea et al. (2018); Bera et al. (2019).

Our techniques.

Our main contribution is to design a nearly-linear time algorithm for $(r,b)$-fairlet decomposition for any integer values of $r,b$. Our algorithm has two steps. First, it embeds the input points into a tree metric called HST (intuitively, this is done by computing a quadtree decomposition of the point set, and then using the distances in the quadtree). In the second step it solves the fairlet decomposition problem with respect to the new distance function induced by HST. The distortion of the embedding into the HST accounts for the $\log n$ factor in the approximation guarantee.

Once we have the HST representation of the pointset, the high-level goal is to construct “local” $(r,b)$-fairlets with respect to the tree. To this end, the algorithm scans the tree in a top-down order. In each node $v$ of the tree, it greedily partitions the points into fairlets so that the number of fairlets whose points belong to subtrees rooted at different children of $v$ is minimized. In particular, we prove that minimizing the number of such fairlets (which we refer to as the Minimum Heavy Point problem) leads to an $O(1)$-approximate $(r,b)$-fairlet decomposition with respect to the distance over the tree.

Preliminaries

for all $p,q\in Y$ and $i\leq k$, $d_{i}(f(p),f(q))\geq d(p,q)$,

$\overline{d}(f(p),f(q))\leq c_{f}\cdot d(p,q)$.

A tree $T$ rooted at vertex $r$ is a hierarchically well-separated tree ($\gamma$-HST) if all edges of $T$ have non-negative weights and the following two conditions hold:

The (weighted) distances from any node to all its children are the same.

For each node $v\in V\setminus\{r\}$, the distance of $v$ to its children is at most ${1/\gamma}$ times the distance of $v$ to its parent.

High-level Description of Our Algorithm

Our algorithm for $(r,b)$-fair $k$-median problem in Euclidean space follows the high-level approach of Chierichetti et al. (2017): it first computes an approximately optimal $(r,b)$-fairlet decomposition for the input point set $P$ (see Algorithm 1). Then, in the second phase, it clusters the ($r,b$)-fairlets produced in the first phase into $k$ clusters (see Algorithm 2). Our main contribution is designing a scalable algorithm for the first phase of this approach, namely ($r,b$)-fairlet decomposition.

An important step in our algorithm is to embed the input pointset $P$ into a $\gamma$-HST (see Section 2 for more details on HST metrics). To this end, we exploit the following standard construction of $\gamma$-HST using randomly shifted grids.

Note that the final tree generated by the above construction is a $\gamma$-HST: on each path from the root to a leaf, the length of consecutive edges decrease exponentially (by a factor of $\gamma$) and the distance from any node to all of its children are the same. Moreover, we assume that $\Delta/\varepsilon=n^{O(1)}$.

Phase 1: computing (r,b𝑟𝑏r,b)-fairlet decomposition.

Step 1.

Compute an approximately minimum number of points that are required to be removed from the children of $v$ so that (1) the set of points contained by each child becomes $(r,b)$-balanced, and (2) the union of the set of removed points is also $(r,b)$-balanced. More formally, we solve Question 3.2 approximately (recall that for each child $v_{i}$, $N^{i}_{r}$ and $N^{i}_{b}$ respectively denotes the number of red and blue points in $T(v_{i})$).

A point $p\in T(v)$ is heavy with respect to $v$ if it belongs to a fairlet $D$ such that $\textsf{lca}(D)=v$. For each fairlet $D\in\mathcal{X}$, $\textsf{lca}(D)$ denotes the least common ancestor (lca) of the points contained in $D$ in $T$.

Suppose that $v$ is a node in $T$. For each $i\in[\gamma^{d}]$ corresponding to non-empty children of $v$, let $x^{i}_{r},x^{i}_{b}$ be respectively the number of red and blue points that are removed from $T(v_{i})$. The goal is to minimize $\sum_{i=1}^{\gamma^{d}}x^{i}_{r}+x^{i}_{b}$ such that the following conditions hold:

for each $i\in[\gamma^{d}]$, $(N^{i}_{r}-x^{i}_{r},N^{i}_{b}-x^{i}_{b})$ is ($r,b$)-balanced.

$(\sum_{i\in[\gamma^{d}]}x^{i}_{r},\sum_{i\in[\gamma^{d}]}x^{i}_{b})$ is ($r,b$)-balanced.

Step 2.

After computing $\{x^{i}_{r},x^{i}_{b}\}_{i\in[\gamma^{d}]}$, for each $i\in[\gamma^{d}]$, remove an arbitrary set of $x^{i}_{r}$ red and $x^{i}_{b}$ blue points from $T(v_{i})$ and add them to $P_{v}$. Then, output an arbitrary $(r,b)$-fairlet decomposition of points $P_{v}$ which is guaranteed to be $(r,b)$-balanced by Step 1.

Step 3.

For each non-empty child of $v$, $v_{i}$ (for $i\in[\gamma^{d}]$), run $\textsc{FairletDecomposition}(v_{i},r,b)$ which is guaranteed to be $(r,b)$-balanced by Step 1.

Here is the main guarantee of our approach in the first step (i.e., ($r,b$)-fairlet decomposition).

Phase 2: merging (r,b𝑟𝑏r,b)-fairlets into k𝑘k clusters.

In this phase, we essentially follow the same approach as Chierichetti et al. (2017).

Suppose that $Q$ is an $\alpha$-approximate $(r,b)$-fairlet decomposition of $P$. Then, ClusterFairlet($Q$) returns an $(\alpha+(r+b)\cdot\beta)$-approximate $(r,b)$-fair $k$-median clustering of $P$ where $\beta$ denotes the approximation guarantee of the $k$-median algorithm invoked in ClusterFairlet.

Finally, Theorem 3.3 and 3.4 together imply Theorem 1.1.

Fairlet Decomposition: a Top-down Approach on γ𝛾\gamma-HST

In this section, we provide a complete description of the first phase in our $(r,b)$-fair $k$-median algorithm (described in Section 3), namely our scalable ($r,b$)-fairlet decomposition algorithm.

Thus, by Theorem 4.1 and the bound on the expected distortion of embeddings into HST metrics (Theorem 2.3), we can prove Theorem 3.3.

Theorem 3.3. We first embed the points into an $O(r^{5}+b^{5})$-HST $T$ and then perform the algorithm guaranteed in Theorem 4.1. By Theorem 2.3, the expected distortion of our embedding to $T$ is $O(d\cdot\gamma\cdot\log_{\gamma}n)$ and by Theorem 4.1, there exists an algorithm that computes an $O(r^{3}+b^{3})$-approximate fairlet-decomposition of $P$ with respect to distances in $T$. Hence, the overall algorithm achieves $O(d\cdot(r^{8}+b^{8})\cdot\log n)$-approximation.

Since the embedding $T$ can be constructed in time $O(d\cdot n\cdot\log n)$ and the fairlet-decomposition algorithm of Theorem 4.1 runs in near-linear time, the overall algorithm also runs in $\widetilde{O}(n)$. $\square$

In the rest of this section we prove the following result which together with Claim 4.2 imply Theorem 4.1.

For any tree $T$ with the root vertex $v$, the number of heavy points with respect to $v$ in the ($r,b$)-fairlet decomposition constructed by $\textsc{MinHeavyPoints}(v,r,b)$ is at most $O(r^{2}+b^{2})$ times the minimum number of heavy points in any valid ($r,b$)-fairlet decomposition of $T$.

In this section, we show that MinHeavyPoints algorithm invoked by FairletDecomposition finds an $O(r^{2}+b^{2})$-approximate solution of Minimum Heavy Points problem.

The high-level overview of MinHeavyPoints is as follows. For any subset of points $D\subseteq P$, we can compute in $O(1)$ what the maximal size $(r,b)$-balanced subset of $D$ is: w.l.o.g. suppose that $N_{r}\geq N_{b}$ and $r\geq b$. If $N_{r}\leq{r\over b}\cdot N_{b}$, the collection is $(r,b)$-balanced. Otherwise, it suffices to greedily pick maximal size $(r,b)$-fairlets (see procedure UnbalancedPoints for the formal algorithm). This simple observation implies a lower bound on the size of any optimal solution of Heavy Points Minimization with respect to $v$ and we use this value to bound the approximation guarantee of MinHeavyPoints algorithm.

UnbalancedPoints($N_{r},N_{b},r,b$) correctly computes the minimum number of points that is required to be removed from $N_{r}\cup N_{b}$ so that the remaining points become $(r,b)$-balanced. Moreover, the solution returned by the procedure only removes points form a single color class.

Another structure we will refer to in the rest of this section is saturated ($r,b$)-fairlets. A fairlet $D$ is a saturated $(r,b)$-fairlet if it has exactly $r+b$ points; $r$ points from color $c$ and $b$ points from color $\overline{c}$.

Stage 2: Adding free points.

If the “must-have” heavy points are not $(r,b)$-balanced, then one color is dominant. For a color class $c\in\{r,b\}$, a collection of points $S$ is $c$-dominant if $|S_{c}|\geq{r\over b}\cdot|S_{\overline{c}}|$. Moreover, the collection is minimally-balanced $c$-dominant if $S$ is $(r,b)$-balanced but it will be no longer $(r,b)$-balanced even if we remove a single point of color $\overline{c}$.

Let $c$ be the dominant color in the heavy points. Then, we inspect all children of $v$ and if there exits a child in which $\overline{c}$ is dominant, we borrow as many points of color $\overline{c}$ as we can (we need to keep the subtree $(r,b)$-balanced, see ExtraPoint procedure) till either the set of heavy points becomes $(r,b)$-balanced or all subtrees rooted at children of $v$ become minimally-balanced $c$-dominant. It is straightforward to show that at most ${b\over r}\cdot|S_{c}|$ points of color $\overline{c}$ will be borrowed from the children of $v$ in this phase.

Suppose that the set of heavy points is $c$-dominant. If the set of heavy points is not $(r,b)$-balanced at the end of stage 2, then for each $i\in[\gamma^{d}]$, the set of points in the subtree rooted at $v_{i}$ is minimally-balanced $c$-dominant.

Suppose that the set of heavy points is $c$-dominant. If the set of heavy points is not $(r,b)$-balanced at the end of stage 2, then for each $i\in[\gamma^{d}]$, the set of points in the subtree rooted at $v_{i}$ have an $(r,b)$-fairlet decomposition with at most one non-saturated $(r,b)$-fairlet.

Stage 3: Non-saturated fairlets.

Moreover, in any non-saturated $(r,b)$-fairlet, ${r_{i}\over b_{i}}<{r\over b}$, which implies that $r_{i}b\leq rb_{i}-1$. Let $Q$ denote the set of children of $v$ whose non-saturated fairlets are picked. After adding all points in these non-saturated fairlets,

Runtime analysis of MinHeavyPoints.

Here we analyze the runtime of MinHeavyPoints which corresponds to step $1$ in FairletDecomposition. Note that stage $1$ only requires $O(1)$ operations on the number of red and blue points in $T(v)$. Each of stage $2$ and stage $3$ requires $O(1)$ operations on the number of red and blue points in all non-empty children of $T(v)$. Although the number of children of $T(v)$ can be as large as $\gamma^{d}$, for each node $v$ in $T$, MinHeavyPoints performs $O(1)$ operations on the number of red and blue points in $T(v)$ exactly twice: when it is called on $v$ and the parent of $v$. Hence, in total MinHeavyPoints performs $O(1)$ time on each node in $T$ which in total is $O(n)$.

Experiments

In this section we show the performance of our proposed algorithm for $(r,b)$-fair $k$-median problem on three different standard data sets considered in (Chierichetti et al., 2017) which are from UCI Machine Learning Repository (Dheeru and Karra Taniskidou, 2017)https://archive.ics.uci.edu/ml/datasets/diabetes. Furthermore, to exhibit the performance of our algorithms on large and high-dimensional scale datasets, we consider an additional data set.

Bank. The datasethttps://archive.ics.uci.edu/ml/datasets/Bank+Marketing is extracted from marketing campaigns of a Portuguese banking institution (Moro et al., 2014). Among the information about the clients, we selected (“age”, “balance”, “duration-of-account”) as attributes to represent the dimensions of the points in the space. Moreover, we consider “marital-status” as the sensitive information.

Census. The datasethttps://archive.ics.uci.edu/ml/datasets/adult contains the records extracted from 1994 US Census (Kohavi, 1996). We picked attributes (“age” , “fnlwgt”, “education-num”, “capital-gain”, “hours-per-week”) to represent the points in the space. Moreover, we consider “gender” as the sensitive attribute.

Census II. The datasethttps://archive.ics.uci.edu/ml/datasets/US+Census+Data+(1990) contains the records extracted from 1990 US Census. We picked 25 numeric attributes to represent points in the space. Moreover, we consider “gender” as the sensitive attribute.

Results.

Comparing the cost of the solution returned by our fairlet decomposition algorithm with the result of (Chierichetti et al., 2017) (as in Table 1) shows that we achieve empirical improvements on all instances. The main reason is that our algorithm is particularly efficient when the input pointset lies in a low dimensional space which is the case in all three datasets “Diabetes”, “Bank” and “Census”. Moreover, unlike (Chierichetti et al., 2017), for each dataset, we can afford running our algorithm on the whole dataset (see Table 3). Empirically, the running time of our algorithm scales almost linearly in the number points in the input pointset (see Figure 2).

In Figure 2 and both Table 1 and 3, the reported runtime for each sample size $S$ is the median runtime of our algorithm on $10$ different sample sets from the given pointset each of size $S$.

Acknowledgment

The authors would like to thank Ravi Kumar for many helpful discussions. This project was supported by funds from the MIT-IBM Watson AI Lab, NSF, and Simons Foundation.

References

Appendix A Missing Proofs

Lemma 4.3. The proof is by induction on height of $v$ in $T$. The base case is when $v$ is a leaf node in $T$ and the algorithm trivially finds an optimal solution in this case. Suppose that the induction hypothesis holds for all vertices of $T$ at height $h-1$. Here, we show that the statement holds for the vertices of $T$ at height $h$ as well.

Hence, by the induction hypothesis, for each $i\in[\gamma^{d}]$,

Next, we bound the cost of sol by Lemma 4.4 and (4) as follows:

Next, we bound the cost of the fairlet decomposition which is constructed by augmenting the set of fairlets $\textsc{OPT}_{i}\setminus\overline{\textsc{OPT}}_{i}$ with the set of affected points $\overline{P}_{i}$.

Let $Q_{0}$ denote the set of affected points $\overline{P}_{i}$. We augment the fairlet decomposition in three steps:

In this step, we create as many $(r,b)$-balanced fairlets using the affected points $Q_{0}$ only. Note that the contribution of each point involved in such fairlets is $h_{T}(v_{i})$ where $h_{T}(v_{i})$ denotes the distance of $v_{i}$ from the leaves in $T(v_{i})$. Let $Q_{1}\subseteq Q_{0}$ denote the set of affected points that do not join any fairlets at the end of this step. Note that all points in $Q_{1}$ are of the same color $c$.

Step 2:

Next, we add as many points of $Q_{1}$ as possible to the existing fairlets in $\textsc{OPT}_{i}\setminus\overline{\textsc{OPT}}_{i}$ while preserving the $(r,b)$-balanced property. Now the extra cost incurred by each points of $Q_{1}$ that joins a fairlet in this step is at most $(r+b)\cdot h_{T}(v_{i})$. Let $Q_{2}\subset Q_{1}$ be the set of points that do not belong to an fairlets by the end of the second phase. Note that at the end of this step, if $Q_{2}$ is non-empty, then all fairlets are maximally-balanced $c$-dominant (a fairlet $S$ is maximally-balanced $c$-dominant if (1) in $S$, the number of points of color $c$ are larger than the number of points in color $\overline{c}$, (2) the set $S$ is $(r,b)$-balanced, and (3) adding a point of color $c$ to $S$ makes it unbalanced).

Step 3:

Finally, we show that by mixing the points of at most $b\cdot|Q_{2}|$ existing fairlets with the set $Q_{2}$, we can find an $(r,b)$-balanced fairlet decomposition of the involved points and the contribution of each such point to the total cost is at most $h_{T}(v_{i})$. Note that since the set of all points we are considering is $(r,b)$-balanced, not all of the so far constructed fairlets are saturated (i.e., has size exactly $r+b$). In particular, we show that there exists a set of non-saturated fairlets $\mathcal{X}$ of size at most $b\cdot|Q_{2}|$ whose addition to $Q_{2}$ constitutes a $(r,b)$-balanced set. For each fairlet $D\in\mathcal{X}$,

where $c_{D}$ and $\overline{c}_{D}$ respectively denotes the set of points of color $c$ and $\overline{c}$ in $D$. This implies that after picking at most $|Q_{2}|$ non-saturated fairlets (i.e., the fairlets in $\mathcal{X}$),

where $c_{\mathcal{X}}$ and $\overline{c}_{\mathcal{X}}$ respectively denotes the set of points of color $c$ and $\overline{c}$ in $\bigcup_{D\in\mathcal{X}}D$. Hence, the set of points $Q_{2}\cup\bigcup_{D\in\mathcal{X}}D$ is $(r,b)$-balanced. Moreover, the cost of this step is at most $|Q_{2}|\cdot b\cdot(r+b)\cdot h_{T}(v_{i})$.

Let $N$ denote the set of the centers of fairlets in $Q$. For a set of points $X$, let $\textsc{OPT}_{k\text{-median}}(X)$ denotes an optimal $k$-median clustering of $X$ (note that there is not fairness requirement). Since $C\subseteq P$, the optimal $k$-median cost of $N$ is smaller than the optimal $k$-median cost of $P$. Since $\overline{P}$ contains at most $(r+b)$ copies of each point of $N$, by assigning all copies of each point $p\in N$ in $\overline{P}$ to the center of $p$ in an optimal $k$-median clustering of $N$,

As ClusterFairlet returns a $\beta$-approximate $k$-median clustering of $\overline{P}$, and by (5)-(6), the cost of the clustering $\mathcal{C}$ constructed by ClusterFairlet is

Since the distance of each point $p_{i}\in P$ to the center of its cluster in $\mathcal{C}^{*}$ is less than the sum of its distance to the center of its fairlet $c_{i}$ in $Q$ and the distance of $c_{i}$ to its center in $\mathcal{C}$, we can bound the cost of $\mathcal{C}^{*}$ in terms of the costs of $\mathcal{C}$ and $Q$ as follows: