CAREER: A Theoretical Exploration of Efficient and Accurate Clustering Algorithms

职业生涯：高效准确聚类算法的理论探索

• 批准号: 2337832
• 负责人: Debarati Das
• 金额: $ 64.77万
• 依托单位: Pennsylvania State Univ University Park
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-05-01 至 2029-04-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2337832&HistoricalAwards=false
• 关键词: CAREER; Theoretical; Exploration; Efficient; Accurate

Clustering, a fundamental technique in data analysis and machine learning, involves grouping data points to ensure higher similarities within a group (cluster) than across clusters. Since its inception in the early 20th century, clustering has proven highly valuable in diverse fields such as biology, economics, marketing, statistics, computer science, and social network analysis. This CAREER project aims to create a unified framework along with various tools and techniques to design optimal approximation algorithms for a broad range of NP-hard clustering problems. Despite significant progress in developing efficient approximations for computationally hard clustering problems, the analysis of the large-scale and complex datasets remains challenging resulting in suboptimal accuracy and limiting practical applications in science and engineering. The algorithmic development and analysis are expected to have a direct impact on the fields of data science and bioinformatics. The educational components of the project include a 3-day summer workshop for high school students, training and mentoring of graduate students, development of new courses, and the fostering of student participation from underrepresented groups in theoretical computer science.The project comprises two primary thrusts. The first thrust focuses on addressing clustering challenges in strings with special emphasis on centroid-based clustering problems such as k-median and k-center. This study will encompass various metric spaces including edit distance, Ulam, and Kendall tau. The objective is to formulate methodologies that transcend the limitations set by the triangle inequality, yielding polynomial-time algorithms with approximations arbitrarily close to one. The second thrust focuses on issues related to hierarchical clustering. Here the objective is to evaluate how well the techniques and frameworks originally devised for addressing string clustering problems can be adapted for aggregating hierarchical clusters. Additionally, the project will develop new methods for constructing hierarchical clusters specifically tailored to address challenges related to large datasets. The new tools and combinatorial methods developed in this project are expected to enhance algorithms for clustering problems and should find applicability in various other domains including communication complexity, streaming algorithms, and distributed systems.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.

聚类是数据分析和机器学习中的一项基本技术，涉及对数据点进行分组，以确保组（簇）内的相似性高于簇间的相似性。自 20 世纪初诞生以来，集群已被证明在生物学、经济学、市场营销、统计学、计算机科学和社交网络分析等不同领域具有极高的价值。该 CAREER 项目旨在创建一个统一的框架以及各种工具和技术，为广泛的 NP 难聚类问题设计最佳逼近算法。尽管在开发计算困难聚类问题的有效近似方法方面取得了重大进展，但对大规模和复杂数据集的分析仍然具有挑战性，导致精度不理想并限制了科学和工程中的实际应用。算法的开发和分析预计将对数据科学和生物信息学领域产生直接影响。该项目的教育组成部分包括为高中生举办为期 3 天的夏季研讨会、研究生培训和指导、新课程开发以及促进理论计算机科学领域代表性不足群体的学生参与。该项目包括两个主要目标。第一个重点是解决字符串中的聚类挑战，特别强调基于质心的聚类问题，例如 k 中值和 k 中心。这项研究将涵盖各种度量空间，包括编辑距离、Ulam 和 Kendall tau。目标是制定超越三角不等式限制的方法，产生近似值任意接近于 1 的多项式时间算法。第二个重点关注与层次聚类相关的问题。这里的目标是评估最初为解决字符串聚类问题而设计的技术和框架如何适用于聚合层次聚类。此外，该项目将开发新的方法来构建专门定制的分层集群，以解决与大型数据集相关的挑战。该项目中开发的新工具和组合方法预计将增强聚类问题的算法，并应在其他各个领域找到适用性，包括通信复杂性、流算法和分布式系统。该奖项反映了 NSF 的法定使命，并被认为值得支持通过使用基金会的智力优点和更广泛的影响审查标准进行评估。