AF: Small: New Challenges and Approaches in Clustering Algorithms

点击翻译按钮获取中文摘要

Clustering is the task of dividing a dataset into similar groups, a fundamental data analysis technique frequently applied in computer science and other disciplines. Typically, the task is modeled as a computational problem and algorithms are designed in order to perform the task. This project investigates fair clustering models, essential for computing and society, that can train machine learning systems in an unbiased or fair manner for each protected group (defined based on a sensitive feature, say gender). However, designing algorithms with provable guarantees for fair clustering has been frustrating, as the fair versions pose novel challenges. In particular, the classic techniques that have been used to solve regular (or vanilla) clustering problems have fallen short in handling the fair versions. Accordingly, the project aims to bridge this gap of understanding and design tools and techniques to achieve guarantees matching those of vanilla clustering. Additionally, the project supports research by graduate students and outreach activities to create awareness among local school/college students about ongoing research in Theoretical Computer Science. This project highlights a collection of fundamental fair clustering problems with the fairness notion of balance. This notion requires that each protected group is well-represented in every cluster. Balanced clustering has emerged as one of the most popular, but difficult clustering models in recent times. For example, it is widely known that k-median (or k-means) clustering admits polynomial-time constant-factor approximation algorithms, but a similar approximation is not known for the balanced versions. This project investigates the limitations and applicability of generic techniques from the area of approximation, such as relax-and-round and metric partitioning. As a part of the project, new tools and techniques will be designed that would help solve a broader class of problems. The study will also examine the trade-offs between quantities such as time complexity, approximation guarantee, and the extent of fairness satisfaction.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.