Fair Clustering Problems Público

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

Rights statement

• Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.

School	Emory College
Department	Mathematics
Degree	B.S.
Submission	Honors Thesis
Language	English
Research Field	Applied Mathematics Computer Science Mathematics
Palabra Clave	Fairness Machine learning Clustering
Committee Chair / Thesis Advisor	Michelangelo Grigni, Emory University
Committee Members	Manuela Manetta, Emory University Jinho Choi, Emory University

Última modificación

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	Fair Clustering Problems ()	2021-04-12 22:38:07 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions