CIF: Small: New Directions in Clustering: Interactive Algorithms and Statistical Models

聚类，或基于成对相似度划分数据点，是无监督学习和数据挖掘的最重要问题之一。由于处理大量有噪声的数据，以及缺乏验证聚类输出的基准，聚类算法通常存在精度低和时间复杂度高的问题。本项目通过整合信息论中的几个新技术工具，研究聚类算法的新方向及其基本限制。具有理论保证和实际验证的可扩展聚类算法应该在数据科学的所有领域都有很高的影响。该项目旨在利用自适应收集标记数据的交互式算法来提高聚类和相关机器学习问题的准确性。近年来，众包的广泛使用促进了这种算法的发展。将开发的算法，以及下限方法，扩展到一大类机器学习问题，并有助于理解信息理论最优性和计算效率之间的权衡。考虑到错误的相互作用，使用相似度量，重叠集群和算法设计中的并行相互作用的广义设置正在进行中。该项目还将探讨这种设置与知名的随机图社区模型（如随机块模型）的联系。新的统计模型，如几何块模型，将作为流行的随机块模型的替代研究。将开发几何块模型和信息论下界的群落恢复算法。该项目还将开发统计模型，忠实地捕捉真实网络的属性，为测试聚类算法提供基准。其中包括用于社区检测和交互式聚类的统计模型。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Clustering, or partitioning data-points based on pairwise similarities, is one of the most important problems of unsupervised learning and data mining. Algorithms for clustering often suffer from low accuracy and high time complexity due to processing massive amounts of data that are noisy, and for lack of a benchmark to validate the clustering output. This project studies new directions for clustering algorithms and their fundamental limits by incorporating several new technical tools from information theory. Scalable algorithms for clustering with theoretical guarantees and practical validation should have high impact in all areas of data science.This project aims to make use of interactive algorithms that adaptively gather labeled data to improve accuracy of clustering and related machine learning problems. In recent years, wide-spread use of crowdsourcing has facilitated the development of such algorithms. The algorithms that will be developed, as well as the lower bounding methods, extend to a large class of machine learning problems, and help understand trade-off between information theoretic optimality and computational efficiency. A generalized setup taking into account erroneous interactions, use of similarity measures, overlapping clusters and parallel interactions in design of algorithms is being pursued. Connections of this setup with well-known random graph community models such as the stochastic block model will also be explored in this project. New statistical models, such as the geometric block model, will be studied as an alternative to the popular stochastic block model. Algorithms for community recovery for the geometric block model andinformation theoretic lower bounds will be developed. This project will also develop statistical models that faithfully capture the properties of real networks to provide a benchmark for testing clustering algorithms. These include statistical models for community detection and interactive clustering.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.