Proportionally Representative Clustering
- URL: http://arxiv.org/abs/2304.13917v2
- Date: Tue, 15 Aug 2023 11:07:44 GMT
- Title: Proportionally Representative Clustering
- Authors: Haris Aziz and Barton E. Lee and Sean Morota Chu and Jeremy Vollen
- Abstract summary: 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.
- Score: 19.15677407216981
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In recent years, there has been a surge in effort to formalize notions of
fairness in machine learning. We focus on clustering -- one of the fundamental
tasks in unsupervised machine learning. We propose a new axiom ``proportional
representation fairness'' (PRF) that is designed for clustering problems where
the selection of centroids reflects the distribution of data points and how
tightly they are clustered together. Our fairness concept is not satisfied by
existing fair clustering algorithms. We design efficient algorithms to achieve
PRF both for unconstrained and discrete clustering problems. Our algorithm for
the unconstrained setting is also the first known polynomial-time approximation
algorithm for the well-studied Proportional Fairness (PF) axiom (Chen, Fain,
Lyu, and Munagala, ICML, 2019). Our algorithm for the discrete setting also
matches the best known approximation factor for PF.
Related papers
- Fuzzy K-Means Clustering without Cluster Centroids [79.19713746387337]
Fuzzy K-Means clustering is a critical computation technique in unsupervised data analysis.
This paper proposes a novel Fuzzy K-Means clustering algorithm that entirely eliminates the reliance on cluster centroids.
arXiv Detail & Related papers (2024-04-07T12:25:03Z) - Stochastic Unrolled Federated Learning [85.6993263983062]
We introduce UnRolled Federated learning (SURF), a method that expands algorithm unrolling to federated learning.
Our proposed method tackles two challenges of this expansion, namely the need to feed whole datasets to the unrolleds and the decentralized nature of federated learning.
arXiv Detail & Related papers (2023-05-24T17:26:22Z) - Gradient Based Clustering [72.15857783681658]
We propose a general approach for distance based clustering, using the gradient of the cost function that measures clustering quality.
The approach is an iterative two step procedure (alternating between cluster assignment and cluster center updates) and is applicable to a wide range of functions.
arXiv Detail & Related papers (2022-02-01T19:31:15Z) - Feature-based Individual Fairness in k-Clustering [14.847868952138795]
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.
arXiv Detail & Related papers (2021-09-09T20:42:02Z) - Efficient Algorithms For Fair Clustering with a New Fairness Notion [5.21410307583181]
We revisit the problem of fair clustering, first introduced by Chierichetti et al.
Existing solutions to fair clustering are either not scalable or do not achieve an optimal trade-off between clustering objective and fairness.
We propose a new notion of fairness, which we call $tau$-fair fairness, that strictly generalizes the balance property and enables a fine-grained efficiency vs. fairness trade-off.
arXiv Detail & Related papers (2021-09-02T04:52:49Z) - Fair Clustering Using Antidote Data [35.40427659749882]
We propose an alternate approach to fairness in clustering where we augment the original dataset with a small number of data points, called antidote data.
Our algorithms achieve lower fairness costs and competitive clustering performance compared to other state-of-the-art fair clustering algorithms.
arXiv Detail & Related papers (2021-06-01T16:07:52Z) - Deep Fair Discriminative Clustering [24.237000220172906]
We study a general notion of group-level fairness for binary and multi-state protected status variables (PSVs)
We propose a refinement learning algorithm to combine the clustering goal with the fairness objective to learn fair clusters adaptively.
Our framework shows promising results for novel clustering tasks including flexible fairness constraints, multi-state PSVs and predictive clustering.
arXiv Detail & Related papers (2021-05-28T23:50:48Z) - Determinantal consensus clustering [77.34726150561087]
We propose the use of determinantal point processes or DPP for the random restart of clustering algorithms.
DPPs favor diversity of the center points within subsets.
We show through simulations that, contrary to DPP, this technique fails both to ensure diversity, and to obtain a good coverage of all data facets.
arXiv Detail & Related papers (2021-02-07T23:48:24Z) - 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) - An Efficient Framework for Clustered Federated Learning [26.24231986590374]
We address the problem of federated learning (FL) where users are distributed into clusters.
We propose the Iterative Federated Clustering Algorithm (IFCA)
We show that our algorithm is efficient in non- partitioned problems such as neural networks.
arXiv Detail & Related papers (2020-06-07T08:48:59Z) - 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.