skip to main content


Title: A Pairwise Fair and Community-preserving Approach to k-Center Clustering
Clustering is a foundational problem in machine learning with numerous applications. As machine learning increases in ubiquity as a back-end for automated systems, concerns about fairness arise. Much of the current literature on fairness deals with discrimination against protected classes in supervised learning (group fairness). We define a different notion of fair clustering wherein the probability that two points (or a community of points) become separated is bounded by an increasing function of their pairwise distance (or community diameter). We capture the situation where data points represent people who gain some benefit from being clustered together. Unfairness arises when certain points are deterministically separated, either arbitrarily or by someone who intends to harm them as in the case of gerrymandering election districts. In response, we formally define two new types of fairness in the clustering setting, pairwise fairness and community preservation. To explore the practicality of our fairness goals, we devise an approach for extending existing k-center algorithms to satisfy these fairness constraints. Analysis of this approach proves that reasonable approximations can be achieved while maintaining fairness. In experiments, we compare the effectiveness of our approach to classical k-center algorithms/heuristics and explore the tradeoff between optimal clustering and fairness.  more » « less
Award ID(s):
1918749
NSF-PAR ID:
10212313
Author(s) / Creator(s):
; ; ; ; ;
Date Published:
Journal Name:
International Conference on Machine Learning (ICML)
Page Range / eLocation ID:
1178-1189
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Clustering is a fundamental problem in unsupervised machine learning, and due to its numerous societal implications fair variants of it have recently received significant attention. In this work we introduce a novel definition of individual fairness for clustering problems. Specifically, in our model, each point j has a set of other points S(j) that it perceives as similar to itself, and it feels that it is being fairly treated if the quality of service it receives in the solution is α-close (in a multiplicative sense, for some given α ≥ 1) to that of the points in S(j). We begin our study by answering questions regarding the combinatorial structure of the problem, namely for what values of α the problem is well-defined, and what the behavior of the Price of Fairness (PoF) for it is. For the well-defined region of α, we provide efficient and easily-implementable approximation algorithms for the k-center objective, which in certain cases also enjoy bounded-PoF guarantees. We finally complement our analysis by an extensive suite of experiments that validates the effectiveness of our theoretical results. 
    more » « less
  2. null (Ed.)
    Metric clustering is fundamental in areas ranging from Combinatorial Optimization and Data Mining, to Machine Learning and Operations Research. However, in a variety of situations we may have additional requirements or knowledge,distinct from the underlying metric, regarding which pairs of points should be clustered together. To capture and analyze such scenarios, we introduce a novel family of stochastic pairwise constraints, which we incorporate into several essential clustering objectives (radius/median/means). Moreover, we demonstrate that these constraints can succinctly model an intriguing collection of applications, including among others, Individual Fairness in clustering and Must-link constraints in semi-supervised learning. Our main result consists of a general framework that yields approximation algorithms with provable guarantees for important clustering objectives, while at the same time producing solutions that respect the stochastic pairwise constraints. Furthermore, for certain objectives we devise improved results in the case of Must-link constraints, which are also the best possible from a theoretical perspective. Finally, we present experimental evidence that validates the effectiveness of our algorithms. 
    more » « less
  3. Metric clustering is fundamental in areas ranging from Combinatorial Optimization and Data Mining, to Machine Learning and Operations Research. However, in a variety of situations we may have additional requirements or knowledge, distinct from the underlying metric, regarding which pairs of points should be clustered together. To capture and analyze such scenarios, we introduce a novel family of stochastic pairwise constraints, which we incorporate into several essential clustering objectives (radius/median/means). Moreover, we demonstrate that these constraints can succinctly model an intriguing collection of applications, including among others Individual Fairness in clustering and Must-link constraints in semi-supervised learning. Our main result consists of a general framework that yields approximation algorithms with provable guarantees for important clustering objectives, while at the same time producing solutions that respect the stochastic pairwise constraints. Furthermore, for certain objectives we devise improved results in the case of Must-link constraints, which are also the best possible from a theoretical perspective. Finally, we present experimental evidence that validates the effectiveness of our algorithms. 
    more » « less
  4. Largely due to superior properties compared to traditional materials, the use of polymer matrix composites (PMC) has been expanding in several industries such as aerospace, transportation, defense, and marine. However, the anisotropy and nonhomogeneity of these structures contribute to the difficulty in evaluating structural integrity; damage sites can occur at multiple locations and length scales and are hard to track over time. This can lead to unpredictable and expensive failure of a safety-critical structure, thus creating a need for non-destructive evaluation (NDE) techniques which can detect and quantify small-scale damage sites and track their progression. Our research group has improved upon classical microwave techniques to address these needs; utilizing a custom device to move a sample within a resonant cavity and create a spatial map of relative permittivity. We capitalize on the inevitable presence of moisture within the polymer network to detect damage. The differing migration inclinations of absorbed water molecules in a pristine versus a damaged composite alters the respective concentrations of the two chemical states of moisture. The greater concentration of free water molecules residing in the damage sites exhibit highly different relative permittivity when compared to the higher ratio of polymer-bound water molecules in the undamaged areas. Currently, the technique has shown the ability to detect impact damage across a range of damage levels and gravimetric moisture contents but is not able to specifically quantify damage extent with regards to impact energy level. The applicability of machine learning (ML) to composite materials is substantial, with uses in areas like manufacturing and design, prediction of structural properties, and damage detection. Using traditional NDE techniques in conjunction with supervised or unsupervised ML has been shown to improve the accuracy, reliability, or efficiency of the existing methods. In this work, we explore the use of a combined unsupervised/supervised ML approach to determine a damage boundary and quantification of single-impact specimens. Dry composite specimens were damaged via drop tower to induce one central impact site of 0, 2, or 3 Joules. After moisture exposure, Entrepreneur Dr, Raleigh, North Carolina 27695, U.S.A. 553 each specimen underwent dielectric mapping, and spatial permittivity maps were created at a variety of gravimetric moisture contents. An unsupervised K-means clustering algorithm was applied to the dielectric data to segment the levels of damage and define a damage boundary. Subsequently, supervised learning was used to quantify damage using features including but not limited to thickness, moisture content, permittivity values of each cluster, and average distance between points in each cluster. A regression model was trained on several samples with impact energy as the predicted variable. Evaluation was then performed based on prediction accuracy for samples in which the impact energies are not known to the model.

     
    more » « less
  5. Motivated by concerns surrounding the fairness effects of sharing and transferring fair machine learning tools, we propose two algorithms: Fairness Warnings and Fair-MAML. The first is a model-agnostic algorithm that provides interpretable boundary conditions for when a fairly trained model may not behave fairly on similar but slightly different tasks within a given domain. The second is a fair meta-learning approach to train models that can be quickly fine-tuned to specific tasks from only a few number of sample instances while balancing fairness and accuracy. We demonstrate experimentally the individual utility of each model using relevant baselines and provide the first experiment to our knowledge of K-shot fairness, i.e. training a fair model on a new task with only K data points. Then, we illustrate the usefulness of both algorithms as a combined method for training models from a few data points on new tasks while using Fairness Warnings as interpretable boundary conditions under which the newly trained model may not be fair. 
    more » « less