1 Introduction↩︎

As artificial intelligence and machine learning serve as the ‘new electricity’ of systems, it is becoming increasingly important to ensure that AI systems embody societal values such as privacy, transparency, and fairness. Fairness is a growing concern, as AI systems are used to make decisions that can critically affect our daily lives, finances, and careers [2]. The impulse to tackle the issue of fairness in AI is prominently reflected in several governmental policy documents [3]–[5], the emergence of dedicated conferences on Ethical AI, and the formation of AI ethics boards by various big tech companies. Over the past years, several developments have taken place in the theory and application of fairness in supervised learning. One prominent approach is to use information derived from labelled data in supervised learning to formalize some notions of equity within and across (pre-specified and) protected attributes [6]. In contrast, in several models of unsupervised learning, protected attributes or their labelling are unknown. Fairness in unsupervised machine learning is becoming important with the growth of data collection both in public (e.g., via IoT devices) and private sectors (e.g., map services and social media). Unfettered and irresponsible use of such data has the danger of increasing inequity [7].

We focus on fairness in clustering, which is one of the most widely applied tasks in unsupervised machine learning. A (centroid selection) clustering problem has a metric space \(\mathcal{X}\) with a distance measure \(d:\mathcal{X}\times \mathcal{X}\rightarrow \mathbb{R}^+\cup \{0\}\), a multiset \({\mathcal{N}}\subseteq \mathcal{X}\) of \(n\) data points (agents), a set \({\mathcal{M}}\) of candidate centers, and positive integer \(k\leq n\). In many clustering problems, each data point corresponds to an individual’s attribute profile; thus, we refer to the data points as agents. The goal is to find a size-\(k\) subset of centers, \(Y\subseteq {\mathcal{M}}\;: \;|Y|=k\). Such centroid selection problems can be widely applied to various applications including recommender systems and data-compression. The problem also captures social planning scenarios where \(k\) facility locations need to be chosen to serve a set of agents.

In such a (centroid selection) clustering problem, there are two versions of the problem. In the discrete version, the set of candidate centers \({\mathcal{M}}\) is a finite subset of \(\mathcal{X}\). In the unconstrained or continuous setting, \({\mathcal{M}}=\mathcal{X}\). We first focus on the unconstrained setting as done by [8]. Later we discuss how our concepts and ideas extend to the discrete setting. For a location \(i\) and set of locations \(S {\subseteq {\mathcal{M}}}\), we will denote \(\min_{c\in S}d(i,c)\) as \(d(i,S)\). Standard clustering solutions include \(k\)-center, \(k\)-medians, and \(k\)-means.¹ These standard objectives can be viewed as achieving some form of global welfare but are not well-suited for proportional representational and fairness concerns. The problems of computing outcomes optimising these objectives are also NP-hard [9], [10].

We seek a suitable concept for clustering that captures general fairness principles such as non-discrimination, equality of opportunity, and equality of outcome. In many applications, the data points correspond to real individuals or their positions or opinions. Such individuals may expect the clustering outcome to capture natural fairness requirements.

Previous axiomatic studies of clustering have measured fair representation by the distance from each data point to the nearest centroid. We initiate a proportional representation perspective on fairness in clustering. In capturing this desiderata axiomatically, we require a property in which representation guarantees depend on the number (or proportion) of data points and how “tightly” they are clustered together.

Our perspective is motivated by applications in which groups of individuals (to which the data points correspond) may expect to receive centroid representation proportional to their size. For instance, the centroids may be citizens selected to make representative decisions on behalf of the public, as is done in a jury or a sortition panel. Similarly, computing a proportionally fair clustering is also meaningful in facility location, where the location of the facility should depend on the density and the number of people it is serving. More generally, our axioms and algorithms are well-motivated in any setting in which one may want to take a representative sample from datapoints between which a distance metric is well-defined.

In this paper, we consider the following fundamental research question. What is a meaningful concept of proportional fairness in centroid clustering? Is such a concept guaranteed to be achievable?

1.0.0.1 Contributions.

In contrast to traditional optimization objectives in clustering and centroid selection, we take an axiomatic fairness perspective. We first identify a potential shortcoming of some recently introduced concepts that aim to capture proportional fairness for clustering; in particular, we show how the concepts do not capture an intuitive and minimal requirement of proportional representation called unanimous proportionality. We then propose a new axiom called proportional representative fairness (PRF), which is our central conceptual contribution.

We propose PRF for both the unconstrained and discrete clustering setting. We discuss how PRF overcomes some of the drawbacks of the previously introduced concepts. In particular, it implies the minimal requirement of unanimous proportionality. PRF has several other desirable features: a PRF outcome is guaranteed to exist, the axiom does not require a preset specification of protected groups and it is robust to outliers and multiplicative scaling. We show that none of the traditional clustering algorithms or previously introduced algorithms for fair clustering satisfy PRF.

We design polynomial-time algorithms to achieve PRF both in the unconstrained and discrete settings.² We call our algorithms SEAR (Spatial Expanding Approval Rule) as they are inspired by using core ideas from the ordinal multi-winner voting Expanding Approvals Rule (EAR) of [11] but carefully use spatial information to make synchronized decisions. We prove that our algorithm for the unconstrained setting also gives \(3\)-approximate Proportional Fairness (PF) [1], and hence is the first known polynomial-time approximation algorithm for PF on general metric spaces. We also prove that our algorithm for the discrete setting matches the best known approximation of Proportional Fairness (PF), thereby providing no compromise on PF approximation but additionally satisfying PRF. We summarize our theoretical contributions in Table 1 via a comparison of our algorithms with the best guarantees previously known. All missing proofs can be found in 7.

2 Related Work↩︎

2.1 Fair clustering↩︎

Fairness in machine learning and computer systems is a vast topic [12]—for an overview, see [2] or the survey by [13]. We focus on the fundamental learning problem of clustering, which is a well-studied problem in computer science, statistics, and operations research [14]. Our approach is axiomatic, focused on the concept of proportional fairness (or representation), and does not rely on the use of a pre-specified or protected set of attributes. Thus, the most closely related papers are those of [1], [8], [15], and [16], which we review below.

[1] proposed the concept of proportional fairness (PF) for the discrete setting, which is based on the entitlement of groups of agents of large enough size. They reasoned that PF is a desirable fairness concept but it is not guaranteed to be achievable for every instance. On the other hand, they showed that outcomes satisfying reasonable approximations of PF are guaranteed to exist and can be computed in polynomial time via the ‘Greedy Capture’ algorithm.

[8] analyzed the proportional fairness axiom in the unconstrained setting and presented similar results to those obtained by [1]. They showed that the natural adaptation of the Greedy Capture algorithm finds an approximately PF outcome in Euclidean space. On the other hand, they showed that checking whether a PF outcome exists is NP-hard and that the clustering returned by the ‘greedy capture’ algorithm cannot be computed in polynomial time unless P = NP. [15] consider the same discrete clustering setting as [1] and propose a stronger version of proportional fairness called core fairness. They present results on lower and upper approximation bounds for various restrictions of the discrete setting.

[16] consider the discrete clustering problem in which the set of agents and candidate centers coincide. For this setting, they propose a fairness concept that has a similar goal as that of [1]. In subsequent work, it has been referred to as individual fairness [17], [18]. Individual fairness requires that, for each agent \(i\), there is a selected center that is at most \(r(i)\) from \(i\), where \(r(i)\) is the smallest radius around \(i\) that includes \(n/k\) agents.

In a paper inspired by our work, [19] analyze the key algorithms and axioms in our paper in further detail and show that the axioms that we propose also imply approximations of various fairness concepts introduced in the literature. Drawing an analogy to multiwinner voting axioms, they refer to our proposed axiom PRF for the discrete setting as mPJR and also define a weaker axiom which they call mJR. They take a deep dive into the logical relations between the axioms and approximate notions of proportional fairness, individual fairness, core fairness, and another core-inspired generalization of proportional fairness [20]. They prove that any approximation to PF is also an approximation to individual fairness and vice versa. In addition to the algorithms we formalize in this paper, they also consider Greedy Capture [1] and a randomized version of this algorithm known as Fair Greedy Capture [20]. A key takeaway from our paper is reaffirmed by their work, namely that our algorithms are the best-known algorithms for satisfying proportional representation axioms while also giving non-trivial approximation guarantees with respect to other fairness notions.

There are also several concepts and algorithms in clustering where the protected groups are pre-specified based on protected attributes [21]–[28]. In contrast, we are seeking fairness properties that apply to arbitrarily defined groups of all possible sizes. In our proposed axiom, these groups are endogenously determined from data points; in some real-world settings, this is a legal requirement since it can be forbidden by law to have decision-making processes use certain attributes as inputs. Clustering can also be viewed as a facility location problem [29], where multiple facilities (centers) are to be located in a metric space; for a recent overview, see the survey by [30].

2.2 Comparison with multi-winner voting↩︎

The clustering problem especially has natural connections with multi-winner voting in which agents and centers in the clustering context correspond to agents and candidates in multi-winner voting.

The literature on proportionally representative multi-winner voting includes axioms such as JR, PJR, EJR, and FJR for dichotomous preferences [31], [32], axioms such as PSC for rankings [33], and axioms such as Generalised PSC [11], [31] or Rank-PJR+[34] for weak orders. Naively applying these axioms to our spatial problem results in a reduction from our unconstrained problem to a multiwinner voting problem with an infinite number of candidates. Conversely, our fairness (or proportional representation) axioms take into account the additional distance-based cardinal information available when the candidates belong to a general metric space. Hence, our axioms formalize a notion of proportional representation for \(m\)-dimensional Euclidean space for \(m>2\). In contrast to ordinal algorithms for multi-winner voting (such as the Expanding Approvals Rule (EAR) [11] or Single Transferable Vote), the algorithms in this paper carefully account for additional spatial information to make synchronized decisions.

[35] consider a similar setting to ours but explore to what extent algorithms that are agnostic to cardinal spatial information and only use ordinal ranking of pairwise distances can achieve approximate fairness. They define \((\alpha,\gamma)\)-proportional representation, a powerful strengthening of approximate core fairness [15]. Their notion captures (and strengthens) the ideal of core stability in this setting: no coalition of agents \(S\) large enough to “deserve” \(t\) centroids should be able to propose an alternative set of \(t\) centroids which they all prefer to their individually best size-\(t\) subset of the selected centroids. They then parameterize this idea by \(\alpha\), the required size of a coalition which deserves \(t\) centroids, and \(\gamma\), the degree to which the alternative centroid selection better represents the coalition. Similar to ours, their property effectively addresses the shortfalls of existing concepts with respect to proportional representation (see Definition 2). In contrast to theirs, the properties we study do not require parameterization and are guaranteed to exist. [35] show that the (ordinal multi-winner) Expanding Approvals Rule (EAR) of [11] is \((\alpha,\gamma)\)-representative with \(\gamma \leq 1 + 6.71 \alpha/(\alpha-1)\) and also satisfies \(5.71\)-approximation to proportional fairness. They are able to improve on these bounds with a modified version of Greedy Capture when cardinal information is known.

Proportionally representation in multi-winner voting (and more generally participatory budgeting) has also been studied when agents have cardinal utilities. Based on prior work for approvals [31], [36] study desirable axioms such as FJR and EJR for positive, additive utilities, and rules such as the Method of Equal Shares (MES). We make no assumption of additive utilities, nor do we ever consider total or average distances. Under additive cardinal utilities, a group of agents of proportion large enough to “deserve” multiple candidates can (in some instances) be satisfied with respect to EJR by a single candidate which gives some agent very high utility. Because our model and axioms take an agnostic approach to cardinal utility values, we instead place requirements on the selection of a proportional number of candidates. One possible approach to our problem is to take distances as proxy for utilities and to apply a rule like MES. However, translating to cardinal utilities necessitates the loss of important spatial information as different cardinal utilities consistent with the distances give different MES outcomes. One possibility is to set utility to be negation of the distance. But the setting and axioms of Peters et al. assume positive, additive utilities.

3 Towards an Axiom Capturing Proportional Representation↩︎

Proportional fairness for clustering has been considered in a series of recent papers. [1] first proposed a proportional fairness axiom that requires that there is no set of agents of size at least \(n/k\) that can find an unselected center that is “better” (i.e., located closer than the closest selected center) for each of them.

The idea of proportional fairness was further strengthened to core fairness that requires that there is no set of agents of size at least \(n/k\) that can demand a more preferred location for a center [15]. One rationale for proportional fairness is explained in the following example, which was first presented by [8] and then reused by [15]. We reuse the same example. Consider a set of data points/agents. The agents are divided into 11 subsets of clusters each of which is densely clustered. One cluster of agents has size 10,000. The other 10 clusters have sizes 100 each. The big cluster is very far from the smaller clusters. The small clusters are relatively near to each other. [8] and [15] are of the view that any set of centers that satisfies a reasonable notion of proportional fairness would place 10 centers for the big cluster and 1 center serving the small clusters. Next, we point out that proportional fairness and core fairness do not necessarily satisfy this minimal requirement, which we formalize via the unanimous proportionality axiom below.

UP captures a principle which [1] highlighted as desirable — in their words, one which requires that “any subset of at least \(r\lceil n/k \rceil\) individuals is entitled to choose \(r\) centers.”³ The following example shows that proportional fairness [1] does not imply Unanimous Proportionality. Similarly, it can be shown that the fairness concept proposed by [16] does not imply unanimous fairness.

The example above shows that there is a need to formalize new concepts in order to capture proportional representative fairness. The property should imply unanimous proportionality but should also be meaningful if no two agents/data points completely coincide in their location. One reason why the existing fairness concepts do not capture UP is that they make an implicit assumption that an agent only cares about the distance from the nearest center and not on how many centers are nearby. As discussed in the introduction, this assumption is not necessarily accurate in contexts such as data abstraction, sortition, and political representation.

In addition to capturing proportional representation in a robust sense, we would also like our axiom (and algorithms) to guarantee the existing proportional fairness concepts, at least in an approximate fashion. Since a PF outcome may not exist, [1] and [8] studied an approximate notion of proportional fairness in the discrete and unconstrained settings, respectively.

We seek to devise an axiom which is compatible with approximate PF, and subsequently to design algorithms which satisfy our axiom while also providing good approximate guarantees with respect to PF. We close the section with an example presented by [8] that shows that a PF outcome may not exist. We will use the same example to illustrate our new fairness concept in the next section.

4 Fairness for the Unconstrained Setting↩︎

We propose a new concept Proportionally Representative Fairness (PRF) that captures proportional representation fairness concerns. The intuition behind the concept is based on two natural principles: (1) a set of agents that is large enough deserves to have a proportional number of centers ‘near’ it, and (2) the requirement of proximity of the nearby centers to a subset of agents should also depend on how densely together the particular subset of agents are. We use these two principles to propose a new fairness concept.

PRF has the following features: it implies unanimous proportionality; it is oblivious to and does not depend on the specification of protected groups or sensitive attributes; it is robust to outliers in the data, since the fairness requirements are for groups of points that are sizable enough; and it is scale invariant to multiplication of distances (i.e., PRF outcomes are preserved if all the distances are multiplied by a constant).

Next, let us illustrate an example where proportional fairness is not achievable but one of the most natural clustering outcomes satisfies PRF.

In addition to capturing natural outcomes when PF outcomes may not exist, PRF actually guarantees a \(\rho\)-PF outcome for \(\rho\approx 3.6\) in the unconstrained setting on general metric spaces.

Next, we highlight that the well-known \(k\)-means or \(k\)-median solutions do not necessarily satisfy PRF. Example 4 is adapted from an example by [1].

Example 4 (\(k\)-means does not satisfy PRF). Consider Figure 3 in which there are \(n/3\) agents uniformly distributed on the perimeter of each of the three circles. If \(k=3\), a \(k\)-means or \(k\)-median solution will place one center by the small circles and two centers in the big circle. In contrast, PRF requires that each of the circles gets its own centroid. It can also be shown that \(k\)-center does not satisfy PRF.

On face value, it is not clear whether an outcome satisfying PRF exists as similar concepts such as PF cannot always be guaranteed [8]. Secondly, even if a PRF outcome is guaranteed to exist, the complex constraints seem computationally challenging. PRF is a property that requires conditions on an exponential number of subsets of agents. For each subset of agents, it enforces representational constraints pertaining to an infinite number of neighborhood distances. Perhaps surprisingly, we show that not only is a PRF outcome guaranteed to exist, it can be computed in polynomial time.

The algorithm intuitively works as follows. Firstly, instead of considering infinite possible centers, we restrict our attention to the \(n\) candidates centers that coincide with each agent’s location. Each agent is given an initial weight of 1. This weight dynamically decreases over the course of the algorithm. The algorithm can be viewed as gradually expanding the neighborhoods of each of the agents.⁴ Instead of continuously expanding the neighborhood, we only consider at most \(n^2\) possible values of neighborhood radii. If there exists some location in the candidate set such that it is in the intersection of the neighborhoods of a group of agents with total weight of at least \(n/k\), we select one such candidate, and reduce the agents’ collective weight by \(n/k\).⁵ The process is continued until \(k\) centers are chosen. The algorithm is formally specified as Algorithm 4. The following is the main result of the present section and summarizes the theoretical guarantees of Algorithm 4.

We will now formally prove two key lemmas used to prove Theorem 1.

Lemma 1 implies guaranteed existence of an outcome satisfying our axiom, which was one of our goals in devising PRF. In conjunction with Proposition 1, the lemma also gives us that the outcome returned by Algorithm 4 is \(\frac{1}{2}(3+\sqrt{17})\)-PF. This is noteworthy as it establishes Algorithm 4 as the first known polynomial-time approximation algorithm for PF on general metric spaces in the unconstrained setting. As we will show next, Algorithm 4 actually provides the stronger guarantee of \(3\)-PF.

5 Fairness for the Discrete Setting↩︎

We presented PRF as a desirable concept for the unconstrained setting. It is not immediate how to adapt the concept to the discrete setting. Applying the unconstrained PRF definition to the discrete setting leads to the issues of non-existence. On the other hand, some natural attempts to account for the coarseness of the candidate space, \({\mathcal{M}}\), can lead to a concept that is too weak. For example, one alternative is to require that an outcome \(X\) be such that if, for any set of agents \(S\subseteq {\mathcal{N}}\) of size at least \(|S|\ge \ell n/k\) such that the maximum distance between pairs of agents in \(S\) is \(y\), the following holds: \(|c\in X\mathbin{:}\exists i\in S \text{ s.t } d(i,c)\leq y|\geq \min\{\ell, |\cup_{j\in S} B_y(j)\cap {\mathcal{M}}|\}\), where \(B_r(i)\) denote a ball of radius \(r\) around agent \(i\). Alternatively, we could replace the right-hand side of the final inequality with \(\min\{\ell, |\cap_{i\in S} B_y(i)\cap {\mathcal{M}}|\}\). Both of these versions are too weak. To see this, suppose \(k=1\), all agents are located at \(0\), and \({\mathcal{M}}=(\ldots, -2, -1, 1, 2, 3, \ldots)\), then neither version places any restriction on the facility location and do not even imply UP.

To resolve these issues, we need to take into account that the nearest candidate locations may be very far from a subset of agents. We adapt our PRF concept for the discrete setting via a careful adaptation of the PRF concept for the unconstrained setting.

We begin by highlighting the fact that, in the discrete setting, PRF implies \((1+\sqrt{2})\)-approximate PF, the closest PF approximation known to exist in the discrete setting [1]. Our proof follows similarly to Theorem 1 from [1].

For the discrete setting, we propose a new algorithm (Algorithm 5). Algorithm 5 is similar to Algorithm 4, which was designed for the unconstrained setting. In fact, Algorithm 4 can be viewed as first setting \({\mathcal{M}}\) to the multiset of candidate locations corresponding to agents in \({\mathcal{N}}\) and then running Algorithm 5.

Similar to Algorithm 4, Algorithm 5 terminates in polynomial time and returns \(k\) centers and its output satisfies PRF.

Notably, by satisfying PRF, Algorithm 5 matches the best known PF approximation factor in the discrete setting. As the following remark highlights, however, the existing algorithms do not capture PRF.

In 12, we experimentally compare Algorithm 5 to ALG\(_g\) and a variant of k-means. We show that it performs especially well when the mean squared distance of the agents is calculated based on their distance from not only the closest center but also the next \(j\)-closest centers (for large \(j\)). This provides another perspective indicating that, in situations where a “fair” clustering should account for an agent’s distance from more than just her closest center, our algorithm is better suited than the existing alternatives. In 9, we consider two natural and stronger notions of PRF in the discrete setting (that also apply to the continuous setting). We show that the versions that we consider do not guarantee the existence of a fair outcome.

6 Discussion↩︎

We revisited a classical AI problem with a novel solution concept that builds on ideas from social choice and fair division. We proposed a natural fairness concept called PRF for clustering. PRF is guaranteed to exist and has desirable features: it implies unanimous proportionality, does not require the specification of protected groups, and is robust to outliers and multiplicative scaling. Even if our only focus is on the PF axiom, we make significant progress on efficient algorithms for approximate PF for general metric spaces. We did not focus on strategic aspects. Unfortunately, PRF and PF are incompatible in general with the incentive of an agent to report their location truthfully (see 11). A natural next step is to identify stronger versions of PRF that still guarantee existence. It will be interesting to consider refinements of our algorithms which make more clever choices when selecting candidates with sufficient weighted support. Another direction for future research is to understand how much impact the constraint of PRF imposes on standard optimization objectives such as for \(k\)-means, \(k\)-median, or \(k\)-center.

Acknowledgments↩︎

Haris Aziz is supported by the NSF-CSIRO project on “Fair Sequential Collective Decision-Making”. We thank John Dickerson and Bo Li for helpful comments.

7 Omitted proofs↩︎

8 Tight Analysis of PF Approximations↩︎

The following example shows the analysis in Proposition 1 is tight. That is, there is an instance for which an outcome satisfying PRF for Unconstrained Clustering obtains no better than \(\frac{3+\sqrt{17}}{2}\)-PF.

It can be verified that all distances in Table 2 satisfy the triangle inequality. Note that, since \(6+2\sqrt{17}\) is the maximum distance between any pair of agents in \({\mathcal{N}}\) (call this \(y\)), and \(d(l,x)=y\), it holds that \(\{x\}\) satisfies PRF for Unconstrained Clustering. Through straightforward arithmetic, it can then be shown that \(\frac{d(i,x)}{d(i,c)}=\frac{d(j,x)}{d(j,c)}=\frac{d(l,x)}{d(l,c)}= \frac{3+\sqrt{17}}{2}\).

9 Strengthening of PRF↩︎

We consider two natural and stronger notions of PRF in the discrete setting (that also apply to the continuous setting). We will show that the versions that we consider do not guarantee the existence of a fair outcome in all settings.

The PRF concept can be increasingly strengthened in the following ways by making the requirements on the outcome stronger.

The following example shows that an outcome satisfying PRFII and hence PRFIII may not exist.

10 \(k\)-means++↩︎

Step 1.

The first centroid is selected randomly.

Step 2.

Calculate the Euclidean distance between the centroid and every other data point in the dataset. The point farthest away will become our next centroid.

Step 3.

Create clusters around these centroids by associating every point with its nearest centroid.

Step 4.

The point which has the farthest distance from its centroid will be our next centroid.

Step 5.

Repeat Steps 3 and 4 until \(k\) number of centroids are located.

11 Strategyproofness and Fairness↩︎

Most of the work on clustering assumes that the data points are truthfully reported. If data points correspond to individual agents who prefer to have a nearby center, then the issue of incentives also arises (see, e.g., [37]). It is easy to see that Algorithm 4 for the unconstrained setting coincides with the mid-point mechanism if there are two agents on a line. Since the mid-point (egalitarian mechanism) is known to be manipulable (see, e.g., [38]), Algorithm 4 is not strategyproof even for \(k=1\) (under which an agent cares about the sole facility to be as close as possible). A discretized version of the same example shows that Algorithm 5 is also not strategyproof.

Instead of understanding the strategic aspects of a particular algorithm, we next examine the tradeoff between fairness and strategyproofness. We focus on the case of \(k=1\) for which the preference relation of an agent is clear: an agent wants the location to be as close as possible.

12 Experimental results↩︎

We now apply Algorithm 4 to four real-world datasets. We consider the discrete domain in which \({\mathcal{M}}={\mathcal{N}}\) as most clustering data sets only have the data points. Algorithm 4 is guaranteed to satisfy PRF; therefore, we are interested in analyzing the performance of the algorithm with respect to other objectives. A prominent objective for clustering algorithms is to minimize the Mean Squared Distance (MSD) to the closest center: the average distance between each datapoint and its closest center. We consider this performance measure as the number of centers ranges from \(k=1\) to \(100\).

In addition to MSD to the closest center, we analyze two other related measures. MSD to the closest \(k/2\) centers and MSD to the closest \(k\) centers. Intuitively, MSD to the closest \(k/2\) centers is the average distance between each datapoint and its \(k/2\)-closest centers (MSD to the closest \(k\) centers is similar). These measures capture—to varying extents—the idea that it may be desirable to have datapoints located close to more than just one center; this idea is at the core of the proportional representation concept. To benchmark Algorithm 4’s performance, we also implement two other algorithms: the well-known \(k\)-means++ algorithm⁷ of [40] and ALG\(_g\) of [15]. For all of our MSD measures, a smaller value is more desirable.

Datasets. The four datasets that we analyze are from the UCI Machine Learning Repository [41]. We summarize these below.⁸ HCV dataset (contains information about patients with Hepatitis C and blood donors.); Seeds dataset (describes measurements of geometrical properties of kernels belonging to three different varieties of wheat.); Buddy-move dataset (consists of user information from user reviews published in www.holidayiq.com about point of interests in South India); and Wholesale dataset (consists of client information for a wholesale distributor. It includes annual spending on various product categories.)

Results. Table ¿tbl:table1? summarizes our results. We illustrate our analysis in Figures 6-8. Across all the datasets, Algorithm 4’s performance relative to \(k\)-means improves when moving from MSD to closest center to MSD to closest \(k/2\) centers and MSD to closest \(k\) centers. A similar pattern is observed for \(ALG_g\), which may be expected and is reassuring since—like Algorithm 4—\(ALG_g\) is motivated by the idea of proportional fairness. For two of the datasets (Wholesale and HCV), Algorithm 4 offers substantially better performance compared to \(k\)-means with respect to MSD to closest \(k\) centers. In these cases, Algorithm 4 also outperforms \(ALG_g\). For MSD to the closest \(k/2\) centers, \(ALG_g\) and Algorithm 4 either outperform or perform similar to \(k\)-means. In contrast, and as expected, the \(k\)-means outperforms both algorithms with respect to the MSD to closest center. With this measure, \(ALG_g\) typically outperforms Algorithm 4. The experiments illustrate that other well-known algorithms produce different outcomes compared to our Algorithm 4, and this difference can be quantified via an intuitive PRF-related metric, i.e., minimizing the MSD to multiple centers.

References↩︎