Foundations of Comparison-Based Hierarchical Clustering
We address the classical problem of hierarchical clustering, but in a framework where one does not have access to a representation of the objects or their pairwise similarities. Instead, we assume that only a set of comparisons between objects is available, that is, statements of the form "objects $i$ and $j$ are more similar than objects $k$ and $l$." Such a scenario is commonly encountered in crowdsourcing applications. The focus of this work is to develop comparison-based hierarchical clustering algorithms that do not rely on the principles of ordinal embedding. We show that single and complete linkage are inherently comparison-based and we develop variants of average linkage. We provide statistical guarantees for the different methods under a planted hierarchical partition model. We also empirically demonstrate the performance of the proposed approaches on several datasets.
Code (1)
Tasks
ClusteringSimilar Papers 제목 키워드 기반
A Revenue Function for Comparison-Based Hierarchical Clustering
Comparison-based learning addresses the problem of learning when, instead of explicit features or pairwise similarities, one only has access to comparisons of the form: \emph{Object $A$ is more similar to $B$ than to $C$…
ClusteringOpen-Ended Question AnsweringTripletElement-centric clustering comparison unifies overlaps and hierarchy
Clustering is one of the most universal approaches for understanding complex data. A pivotal aspect of clustering analysis is quantitatively comparing clusterings; clustering comparison is the basis for many tasks such a…
ClusteringDisentanglementPhilosophyData clustering: an essential technique in data science
This paper explores the critical role of data clustering in data science, emphasizing its methodologies, tools, and diverse applications. Traditional techniques, such as partitional and hierarchical clustering, are analy…
ClusteringDecision MakingHierarchical clustering of DNA k-mer counts in RNA-seq fastq files reveals batch effects
Batch effects, artificial sources of variation due to experimental design, are a widespread phenomenon in high throughput data. Therefore, mechanisms for detection of batch effects are needed requiring comparison of mult…
ClusteringDiagnosticExperimental DesignComparison three methods of clustering: k-means, spectral clustering and hierarchical clustering
Comparison of three kind of the clustering and find cost function and loss function and calculate them. Error rate of the clustering methods and how to calculate the error percentage always be one on the important factor…
AttributeClustering