Show simple item record

dc.contributor.author
Bianchi, Enrico
dc.contributor.author
Penna, Paolo
dc.date.accessioned
2021-03-03T16:56:00Z
dc.date.available
2021-03-03T08:34:08Z
dc.date.available
2021-03-03T16:56:00Z
dc.date.issued
2021-02
dc.identifier.other
10.3390/a14020055
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/472645
dc.identifier.doi
10.3929/ethz-b-000472645
dc.description.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.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
MDPI
en_US
dc.rights.uri
http://creativecommons.org/licenses/by/4.0/
dc.subject
clustering
en_US
dc.subject
stable instances
en_US
dc.subject
ordinal queries
en_US
dc.subject
minimum spanning tree
en_US
dc.subject
medoids
en_US
dc.subject
active learning
en_US
dc.subject
noisy queries
en_US
dc.title
Optimal clustering in stable instances using combinations of exact and noisy ordinal queries
en_US
dc.type
Journal Article
dc.rights.license
Creative Commons Attribution 4.0 International
dc.date.published
2021-02-08
ethz.journal.title
Algorithms
ethz.journal.volume
14
en_US
ethz.journal.issue
2
en_US
ethz.pages.start
55
en_US
ethz.size
28 p.
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.identifier.wos
ethz.identifier.scopus
ethz.publication.place
Basel
en_US
ethz.publication.status
published
en_US
ethz.date.deposited
2021-03-03T08:34:14Z
ethz.source
SCOPUS
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2021-03-03T16:56:09Z
ethz.rosetta.lastUpdated
2021-03-03T16:56:09Z
ethz.rosetta.exportRequired
true
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Optimal%20clustering%20in%20stable%20instances%20using%20combinations%20of%20exact%20and%20noisy%20ordinal%20queries&rft.jtitle=Algorithms&rft.date=2021-02&rft.volume=14&rft.issue=2&rft.spage=55&rft.au=Bianchi,%20Enrico&Penna,%20Paolo&rft.genre=article&rft_id=info:doi/10.3390/a14020055&
 Search print copy at ETH Library

Files in this item

Thumbnail

Publication type

Show simple item record