Clustering with Noisy Queries
Clustering with Noisy Queries
复制标题
带有噪音查询的集群
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
B. Saha
中科院分区：
文献类型：
--
作者：
A. Mazumdar;B. Saha
在本文中，我们启动了一项严格的理论研究，该研究具有嘈杂的查询（或错误的甲骨文）的聚类。给定一组$ n $元素，我们的目标是通过向Oracle提出最少数量的成对查询来恢复真正的聚类。 Oracle可以回答表格的查询：“元素$ u $和$ v $属于同一集群吗？” - 查询可以交互询问（自适应查询）或非适应性的，但概率$ p $可能是错误的。在本文中，我们在两种情况下都在嘈杂的甲骨文聚类的查询数量上提供了第一个信息理论下限。我们设计的新型算法与此查询复杂性下降非常匹配，即使群集的数量未知。此外，我们为自适应和非自适应设置设计了计算有效算法。该问题捕获/概括了多种应用程序方案。它是由不断增长的工作体系直接激发的，该工作将众包用于{EM实体分辨率}，这是一项基本且具有挑战性的数据挖掘任务，旨在识别与同一实体相同的数据库中的所有记录。在这里，人群代表嘈杂的甲骨文，查询数量直接与众包的成本有关。另一个应用程序来自社交网络中{Em Sign Edge预测}的问题，在社交网络中，社交互动可以是正面和负面的，并且必须通过查询几对来确定所有配对互动的迹象。此外，嘈杂的甲骨文聚类与相关聚类密切相关，从而在其中改进。最后，它在流行的{EM随机块模型}中引入了一个新的研究方向，其中一个人具有不完全的随机块模型矩阵来恢复簇。
In this paper, we initiate a rigorous theoretical study of clustering with noisy queries (or a faulty oracle). Given a set of $n$ elements, our goal is to recover the true clustering by asking minimum number of pairwise queries to an oracle. Oracle can answer queries of the form : "do elements $u$ and $v$ belong to the same cluster?" -- the queries can be asked interactively (adaptive queries), or non-adaptively up-front, but its answer can be erroneous with probability $p$. In this paper, we provide the first information theoretic lower bound on the number of queries for clustering with noisy oracle in both situations. We design novel algorithms that closely match this query complexity lower bound, even when the number of clusters is unknown. Moreover, we design computationally efficient algorithms both for the adaptive and non-adaptive settings. The problem captures/generalizes multiple application scenarios. It is directly motivated by the growing body of work that use crowdsourcing for {em entity resolution}, a fundamental and challenging data mining task aimed to identify all records in a database referring to the same entity. Here crowd represents the noisy oracle, and the number of queries directly relates to the cost of crowdsourcing. Another application comes from the problem of {em sign edge prediction} in social network, where social interactions can be both positive and negative, and one must identify the sign of all pair-wise interactions by querying a few pairs. Furthermore, clustering with noisy oracle is intimately connected to correlation clustering, leading to improvement therein. Finally, it introduces a new direction of study in the popular {em stochastic block model} where one has an incomplete stochastic block model matrix to recover the clusters.