Fair Clustering Problems Open Access
Deng, Zirui (Spring 2021)
Abstract
Clustering is a fundamental tool in machine learning and data mining which takes many forms according to different objectives being considered. It entails partitioning points into groups (clusters) and may be used to make decisions for each point based on its group. We study various fair clustering problems under the disparate impact doctrine, where each minority class must be represented approximately equally in every cluster. We offer a survey of recent clustering algorithms that account for different notions of fairness.
Table of Contents
1 Introduction 1
2 Fair Clustering Through Fairlets 6
2.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Main results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3 Algorithms for ”Relaxed” Fair Clustering 15
4 Fair Correlation Clustering 19
4.1 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.2 Overview of results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.3 Fair decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.3.1 α = 1/2: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.3.2 α = 1/col: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.3.3 α = 1/t: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
5 Essentially Fair Clustering 29
5.1 LP formulations for fair clustering problems . . . . . . . . . . . . . . 30
5.2 Combining two solutions . . . . . . . . . . . . . . . . . . . . . . . . . 32
5.3 Rounding the x-variables . . . . . . . . . . . . . . . . . . . . . . . . . 34
5.4 True approximation for k-center . . . . . . . . . . . . . . . . . . . . . 37
6 Conclusion 41
Bibliography 42
About this Honors Thesis
School | |
---|---|
Department | |
Degree | |
Submission | |
Language |
|
Research Field | |
Keyword | |
Committee Chair / Thesis Advisor | |
Committee Members |
Primary PDF
Thumbnail | Title | Date Uploaded | Actions |
---|---|---|---|
Fair Clustering Problems () | 2021-04-12 22:38:07 -0400 |
|
Supplemental Files
Thumbnail | Title | Date Uploaded | Actions |
---|