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
- Self-Supervised Graph Embedding Clustering [70.36328717683297]
K-means one-step dimensionality reduction clustering method has made some progress in addressing the curse of dimensionality in clustering tasks.
We propose a unified framework that integrates manifold learning with K-means, resulting in the self-supervised graph embedding framework.
arXiv Detail & Related papers (2024-09-24T08:59:51Z) - 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 noise model that requires a small number of parameters to be given by the decision maker.
We present an algorithm for fair clustering with provable emphrobustness guarantees.
arXiv Detail & Related papers (2024-06-02T03:11:31Z) - Proportionally Representative Clustering [17.5359577544947]
We propose a new axiom proportionally representative fairness'' (PRF) that is designed for clustering problems.
Our fairness concept is not satisfied by existing fair clustering algorithms.
Our algorithm for the unconstrained setting is also the first known-time approximation algorithm for the well-studied Proportional Fairness (PF) axiom.
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.