Adaptive Hierarchical Clustering Using Ordinal Queries
Adaptive Hierarchical Clustering Using Ordinal Queries
复制标题
使用序数查询的自适应层次聚类
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
D. Kempe
中科院分区：
文献类型：
--
作者：
E. Emamjomeh;D. Kempe
在许多聚类应用中（例如，动物或植物物种的本体或聚类），分层聚类比扁平聚类更具描述性。n个元素上的分层聚类用有根二叉树表示，树有n个叶子，每个叶子对应一个元素。以内部节点为根的子树捕获集群。本文研究了仅使用有序查询的分层聚类的主动学习。顺序查询由一组三个元素组成，对查询的响应揭示了两个元素（在查询中的三个元素中）彼此“更接近”，而不是第三个元素。如果存在一个包含x和x‘但不包含x的簇，我们说元素x和x’比x'更接近。当所有查询响应都正确时，有一种确定性算法，该算法使用最多n log2 n个自适应有序查询来学习底层分层聚类。我们将该算法推广到一个模型中，其中每个查询响应以概率独立正确，并且以概率1−p对抗不正确。我们表明，在存在噪声的情况下，我们的算法使用O（n log n + n log（1/Δ））自适应有序查询，以概率至少为1−Δ的概率输出正确的分层聚类。对于我们的结果，适应性是至关重要的：我们证明，即使在没有噪声的情况下，在最坏的情况下，每个非自适应算法都需要Ω（n3）有序查询。
In many applications of clustering (for example, ontologies or clusterings of animal or plant species), hierarchical clusterings are more descriptive than a flat clustering. A hierarchical clustering over n elements is represented by a rooted binary tree with n leaves, each corresponding to one element. The subtrees rooted at interior nodes capture the clusters. In this paper, we study active learning of a hierarchical clustering using only ordinal queries. An ordinal query consists of a set of three elements, and the response to a query reveals the two elements (among the three elements in the query) which are "closer" to each other than to the third one. We say that elements x and x' are closer to each other than x" if there exists a cluster containing x and x', but not x". When all the query responses are correct, there is a deterministic algorithm that learns the underlying hierarchical clustering using at most n log2 n adaptive ordinal queries. We generalize this algorithm to be robust in a model in which each query response is correct independently with probability [Equation], and adversarially incorrect with probability 1 − p. We show that in the presence of noise, our algorithm outputs the correct hierarchical clustering with probability at least 1 − Δ, using O(n log n + n log(1/Δ)) adaptive ordinal queries. For our results, adaptivity is crucial: we prove that even in the absence of noise, every non-adaptive algorithm requires Ω(n3) ordinal queries in the worst case.