A Notion of Individual Fairness for Clustering

• URL: http://arxiv.org/abs/2006.04960v1
• Date: Mon, 8 Jun 2020 21:41:39 GMT
• Title: A Notion of Individual Fairness for Clustering
• Authors: Matth\"aus Kleindessner, Pranjal Awasthi, Jamie Morgenstern
• Abstract summary: 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.
• Score: 22.288902523866867
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A common distinction in fair machine learning, in particular in fair classification, is between group fairness and individual fairness. In the context of clustering, group fairness has been studied extensively in recent years; however, individual fairness for clustering has hardly been explored. 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. We study several questions related to our proposed notion of individual fairness. On the negative side, we show that deciding whether a given data set allows for such an individually fair clustering in general is NP-hard. On the positive side, for the special case of a data set lying on the real line, we propose an efficient dynamic programming approach to find an individually fair clustering. For general data sets, we investigate heuristics aimed at minimizing the number of individual fairness violations and compare them to standard clustering approaches on real data sets.

Related papers

• ABCDE: Application-Based Cluster Diff Evals [49.1574468325115]
  It aims to be practical: it allows items to have associated importance values that are application-specific, it is frugal in its use of human judgements when determining which clustering is better, and it can report metrics for arbitrary slices of items. The approach to measuring the delta in the clustering quality is novel: instead of trying to construct an expensive ground truth up front and evaluating the each clustering with respect to that, ABCDE samples questions for judgement on the basis of the actual diffs between the clusterings.
  arXiv  Detail & Related papers  (2024-07-31T08:29:35Z)
• 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)
• Fair Group-Shared Representations with Normalizing Flows [68.29997072804537]
  We develop a fair representation learning algorithm which is able to map individuals belonging to different groups in a single group. We show experimentally that our methodology is competitive with other fair representation learning algorithms.
  arXiv  Detail & Related papers  (2022-01-17T10:49:49Z)
• 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)
• 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)
• 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)
• You Never Cluster Alone [150.94921340034688]
  We extend the mainstream contrastive learning paradigm to a cluster-level scheme, where all the data subjected to the same cluster contribute to a unified representation. We define a set of categorical variables as clustering assignment confidence, which links the instance-level learning track with the cluster-level one. By reparametrizing the assignment variables, TCC is trained end-to-end, requiring no alternating steps.
  arXiv  Detail & Related papers  (2021-06-03T14:59:59Z)
• MultiFair: Multi-Group Fairness in Machine Learning [52.24956510371455]
  We study multi-group fairness in machine learning (MultiFair) We propose a generic end-to-end algorithmic framework to solve it. Our proposed framework is generalizable to many different settings.
  arXiv  Detail & Related papers  (2021-05-24T02:30:22Z)
• Protecting Individual Interests across Clusters: Spectral Clustering with Guarantees [20.350342151402963]
  We propose an individual fairness criterion for clustering a graph $mathcalG$ that requires each cluster to contain an adequate number of members connected to the individual. We devise a spectral clustering algorithm to find fair clusters under a given representation graph.
  arXiv  Detail & Related papers  (2021-05-08T15:03:25Z)
• Distributional Individual Fairness in Clustering [7.303841123034983]
  We introduce a framework for assigning individuals, embedded in a metric space, to probability distributions over a bounded number of cluster centers. We provide an algorithm for clustering with $p$-norm objective and individual fairness constraints with provable approximation guarantee.
  arXiv  Detail & Related papers  (2020-06-22T20:02:09Z)
• 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)

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.