Optimal clustering in stable instances using combinations of exact and noisy ordinal queries
Open access
Date
2021-02Type
- Journal Article
Abstract
This work studies clustering algorithms which operates with ordinal or comparison-based queries (operations), a situation that arises in many active-learning applications where “dissimilarities” between data points are evaluated by humans. Typically, exact answers are costly (or difficult to obtain in large amounts) while possibly erroneous answers have low cost. Motivated by these considerations, we study algorithms with non-trivial trade-offs between the number of exact (high-cost) operations and noisy (low-cost) operations with provable performance guarantees. Specifically, we study a class of polynomial-time graph-based clustering algorithms (termed Single-Linkage) which are widely used in practice and that guarantee exact solutions for stable instances in several clustering problems (these problems are NP-hard in the worst case). We provide several variants of these algorithms using ordinal operations and, in particular, non-trivial trade-offs between the number of high-cost and low-cost operations that are used. Our algorithms still guarantee exact solutions for stable instances of k-medoids clustering, and they use a rather small number of high-cost operations, without increasing the low-cost operations too much. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000472645Publication status
publishedExternal links
Journal / series
AlgorithmsVolume
Pages / Article No.
Publisher
MDPISubject
clustering; stable instances; ordinal queries; minimum spanning tree; medoids; active learning; noisy queriesOrganisational unit
03659 - Buhmann, Joachim M. (emeritus) / Buhmann, Joachim M. (emeritus)
More
Show all metadata