权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

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

基本信息

批准号：
2133484
负责人：
Arya Mazumdar
金额：
$ 50万
依托单位：
University of California-San Diego
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2021
资助国家：
美国
起止时间：
2021-06-01 至 2024-10-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2133484&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的法定使命，并被认为值得通过使用基金会的知识价值和更广泛的影响审查标准进行评估来支持。

项目成果

期刊论文数量（10）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

The Complexity of Average-Case Dynamic Subgraph Counting

平均情况动态子图计数的复杂性

DOI：
10.1137/1.9781611977073.23
发表时间：
2022
期刊：
Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA
影响因子：
0
作者：
Henzinger, Monika;Lincoln, Andrea;and Saha, Barna
通讯作者：
and Saha, Barna

BEER: Blocking for Effective Entity Resolution

BEER：阻止有效的实体解析

DOI：
10.1145/3448016.3452747
发表时间：
2021
期刊：
SIGMOD/PODS '21: Proceedings of the 2021 International Conference on Management of Data
影响因子：
0
作者：
Galhotra, Sainyam;Firmani, Donatella;Saha, Barna;Srivastava, Divesh
通讯作者：
Srivastava, Divesh

Byzantine Resilient Distributed Clustering with Redundant Data Assignment

具有冗余数据分配的拜占庭弹性分布式集群

DOI：
发表时间：
2021
期刊：
IEEE International Symposium on Information Theory
影响因子：
0
作者：
Bulusu, Saikiran;Gandikota, Venkata;Mazumdar, Arya;Rawat, Ankit Singh;Varshney, Pramod
通讯作者：
Varshney, Pramod

On Learning Mixture of Linear Regressions in the Non-Realizable Setting