AF: Small: New Challenges and Approaches in Clustering Algorithms

AF：小：聚类算法的新挑战和方法

• 批准号: 2311397
• 负责人: Sayan Bandyapadhyay
• 金额: $ 16.3万
• 依托单位: Portland State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-05-01 至 2026-04-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2311397&HistoricalAwards=false
• 关键词: AF; Small; New; Challenges; Approaches

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.

聚类是将数据集划分为相似组的任务，是计算机科学和其他学科中经常应用的基本数据分析技术。通常，任务被建模为计算问题，并且设计算法来执行该任务。该项目研究对计算和社会至关重要的公平聚类模型，该模型可以以公正或公平的方式为每个受保护群体（根据敏感特征定义，例如性别）训练机器学习系统。然而，设计具有可证明的公平聚类保证的算法一直令人沮丧，因为公平版本提出了新的挑战。特别是，用于解决常规（或普通）聚类问题的经典技术在处理公平版本方面已达不到要求。因此，该项目旨在弥合理解和设计工具和技术之间的差距，以实现与普通集群相匹配的保证。此外，该项目还支持研究生的研究和外展活动，以提高当地学校/大学生对理论计算机科学正在进行的研究的认识。该项目强调了一系列具有平衡公平概念的基本公平聚类问题。此概念要求每个受保护组在每个集群中都有充分的代表性。平衡聚类已成为近年来最流行但最困难的聚类模型之一。例如，众所周知，k 中值（或 k 均值）聚类允许多项式时间常数因子近似算法，但对于平衡版本，不知道类似的近似。该项目从近似区域研究通用技术的局限性和适用性，例如松弛和舍入和度量划分。作为该项目的一部分，将设计新的工具和技术来帮助解决更广泛的问题。该研究还将考察时间复杂性、近似保证和公平满足程度等数量之间的权衡。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查进行评估，被认为值得支持标准。