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

CIF：小型：聚类的新方向：交互式算法和统计模型

• 批准号: 1909046
• 负责人: Arya Mazumdar
• 金额: $ 50万
• 依托单位: University of Massachusetts Amherst
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-10-01 至 2021-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1909046&HistoricalAwards=false
• 关键词: CIF; Small; New; Directions; Clustering

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.

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