Clustering without Over-Representation

Abstract

In this paper we consider clustering problems in which each point is endowed with a color. The goal is to cluster the points to minimize the classical clustering cost but with the additional constraint that no color is over-represented in any cluster. This problem is motivated by practical clustering settings, e.g., in clustering news articles where the color of an article is its source, it is preferable that no single news source dominates any cluster. For the most general version of this problem, we obtain an algorithm that has provable guarantees of performance; our algorithm is based on finding a fractional solution using a linear program and rounding the solution subsequently. For the special case of the problem where no color has an absolute majority in any cluster, we obtain a simpler combinatorial algorithm also with provable guarantees. Experiments on real-world data shows that our algorithms are effective in finding good clustering without over-representation.

10 pages, 6 figures, in KDD 2019

References in corpus (2)

• DeepWalk: Online Learning of Social Representations
• Fairness in Learning: Classic and Contextual Bandits

Cited by in corpus (26)

• Fair clustering via equitable group representations
• Individual Fairness for $k$-Clustering
• A review of clustering models in educational data science towards fairness-aware learning
• Fair Hierarchical Clustering
• Fairness in Clustering with Multiple Sensitive Attributes
• A Notion of Individual Fairness for Clustering
• Representativity Fairness in Clustering
• Efficient Algorithms For Fair Clustering with a New Fairness Notion
• Distributional Individual Fairness in Clustering
• Approximation Algorithms for Socially Fair Clustering
• Fair Correlation Clustering
• Hypergraph Clustering for Finding Diverse and Experienced Groups
• A Stochastic Alternating Balance $k$-Means Algorithm for Fair Clustering
• Deep Fair Discriminative Clustering
• Fair Correlation Clustering
• Improved Approximation Algorithms for Individually Fair Clustering
• KFC: A Scalable Approximation Algorithm for $k$-center Fair Clustering
• Probabilistic Fair Clustering
• A New Notion of Individually Fair Clustering: $\alpha$-Equitable $k$-Center
• How to Solve Fair $k$-Center in Massive Data Models
• Fair densest subgraph across multiple graphs
• FPT Approximation for Fair Minimum-Load Clustering
• FACROC: a fairness measure for FAir Clustering through ROC curves
• A Sociotechnical View of Algorithmic Fairness
• Coping with Mistreatment in Fair Algorithms
• Attraction-Repulsion clustering with applications to fairness