CAREER: A Theoretical Exploration of Efficient and Accurate Clustering Algorithms

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

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.