Feature-based Individual Fairness in k-Clustering
- URL: http://arxiv.org/abs/2109.04554v1
- Date: Thu, 9 Sep 2021 20:42:02 GMT
- Title: Feature-based Individual Fairness in k-Clustering
- Authors: Debajyoti Kar, Sourav Medya, Debmalya Mandal, Arlei Silva, Palash Dey,
Swagato Sanyal
- Abstract summary: We consider the problem of clustering a set of points while ensuring fairness constraints.
We introduce a new notion of individual fairness in k-clustering based on features that are not necessarily used for clustering.
- Score: 14.847868952138795
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Ensuring fairness in machine learning algorithms is a challenging and
important task. We consider the problem of clustering a set of points while
ensuring fairness constraints. While there have been several attempts to
capture group fairness in the k-clustering problem, fairness at an individual
level is not well-studied. We introduce a new notion of individual fairness in
k-clustering based on features that are not necessarily used for clustering. We
show that this problem is NP-hard and does not admit a constant factor
approximation. We then design a randomized algorithm that guarantees
approximation both in terms of minimizing the clustering distance objective as
well as individual fairness under natural restrictions on the distance metric
and fairness constraints. Finally, our experimental results validate that our
algorithm produces lower clustering costs compared to existing algorithms while
being competitive in individual fairness.
Related papers
- Robust Fair Clustering with Group Membership Uncertainty Sets [31.29773979737976]
We study the canonical fair clustering problem where each cluster is constrained to have close to population-level representation of each group.
We introduce a simple and interpretable family of error models that require a small number of parameters to be given by the decision maker.
We then present an algorithm for fair clustering with provable robustness guarantees.
arXiv Detail & Related papers (2024-06-02T03:11:31Z) - Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
We devise an efficient algorithm that recovers clusters using the observed labels.
We present Instance-Adaptive Clustering (IAC), the first algorithm whose performance matches these lower bounds both in expectation and with high probability.
arXiv Detail & Related papers (2023-06-18T08:46:06Z) - Proportionally Representative Clustering [19.15677407216981]
Clustering is one of the fundamental tasks in unsupervised machine learning.
We propose a new axiom proportional representation fairness'' (PRF)
Our fairness concept is not satisfied by existing fair clustering algorithms.
arXiv Detail & Related papers (2023-04-27T02:01:24Z) - Rethinking Clustering-Based Pseudo-Labeling for Unsupervised
Meta-Learning [146.11600461034746]
Method for unsupervised meta-learning, CACTUs, is a clustering-based approach with pseudo-labeling.
This approach is model-agnostic and can be combined with supervised algorithms to learn from unlabeled data.
We prove that the core reason for this is lack of a clustering-friendly property in the embedding space.
arXiv Detail & Related papers (2022-09-27T19:04:36Z) - Fair Labeled Clustering [28.297893914525517]
We consider the downstream application of clustering and how group fairness should be ensured for such a setting.
We provide algorithms for such problems and show that in contrast to their NP-hard counterparts in group fair clustering, they permit efficient solutions.
We also consider a well-motivated alternative setting where the decision-maker is free to assign labels to the clusters regardless of the centers' positions in the metric space.
arXiv Detail & Related papers (2022-05-28T07:07:12Z) - Differentially-Private Clustering of Easy Instances [67.04951703461657]
In differentially private clustering, the goal is to identify $k$ cluster centers without disclosing information on individual data points.
We provide implementable differentially private clustering algorithms that provide utility when the data is "easy"
We propose a framework that allows us to apply non-private clustering algorithms to the easy instances and privately combine the results.
arXiv Detail & Related papers (2021-12-29T08:13:56Z) - Fair Clustering Under a Bounded Cost [33.50262066253557]
Clustering is a fundamental unsupervised learning problem where a dataset is partitioned into clusters that consist of nearby points in a metric space.
A recent variant, fair clustering, associates a color with each point representing its group membership and requires that each color has (approximately) equal representation in each cluster to satisfy group fairness.
We consider two fairness objectives: the group utilitarian objective and the group egalitarian objective, as well as the group leximin objective which generalizes the group egalitarian objective.
arXiv Detail & Related papers (2021-06-14T08:47:36Z) - Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
We give efficient differentially private algorithms for basic clustering problems.
Our results imply an improved algorithm for the Sample and Aggregate privacy framework.
One of the tools used in our 1-Cluster algorithm can be employed to get a faster quantum algorithm for ClosestPair in a moderate number of dimensions.
arXiv Detail & Related papers (2020-08-18T16:22:06Z) - Fair Hierarchical Clustering [92.03780518164108]
We define a notion of fairness that mitigates over-representation in traditional clustering.
We show that our algorithms can find a fair hierarchical clustering, with only a negligible loss in the objective.
arXiv Detail & Related papers (2020-06-18T01:05:11Z) - A Notion of Individual Fairness for Clustering [22.288902523866867]
A common distinction in fair machine learning, in particular in fair classification, is between group fairness and individual fairness.
In this paper, we propose a natural notion of individual fairness for clustering. Our notion asks that every data point, on average, is closer to the points in its own cluster than to the points in any other cluster.
arXiv Detail & Related papers (2020-06-08T21:41:39Z) - Fair Correlation Clustering [92.15492066925977]
We obtain approximation algorithms for correlation clustering under several important types of fairness constraints.
We show that fair solutions to correlation clustering can be obtained with limited increase in cost compared to the state-of-the-art (unfair) algorithms.
arXiv Detail & Related papers (2020-02-06T14:28:21Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.