Efficient Clustering with Limited Distance Information
Given a point set S and an unknown metric d on S, we study the problem of efficiently partitioning S into k clusters while querying few distances between the points. In our model we assume that we have access to one versus all queries that given a point s 2 S return the distances between s and all other points. We show that given a natural assumption about the structure of the instance, we can efficiently find an accurate clustering using only O(k) distance queries. We use our algorithm to cluster proteins by sequence similarity. This setting nicely fits our model because we can use a fast sequence database search program to query a sequence against an entire dataset. We conduct an empirical study that shows that even though we query a small fraction of the distances between the points, we produce clusterings that are close to a desired clustering given by manual classification.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringSimilar Papers 제목 키워드 기반
Learning Bregman Distance Functions and Its Application for Semi-Supervised Clustering
Learning distance functions with side information plays a key role in many machine learning and data mining applications. Conventional approaches often assume a Mahalanobis distance function. These approaches are limited…
ClusteringLearning a Distance for the Clustering of Patients with Amyotrophic Lateral Sclerosis
Amyotrophic lateral sclerosis (ALS) is a severe disease with a typical survival of 3-5 years after symptom onset. Current treatments offer only limited life extension, and the variability in patient responses highlights …
Semi- supervised Affinity Propagation Clustering Algorithm Based on Mahalanobis Distance
A semi-supervised affinity propagation clustering algorithm based on Mahalanobis distance （SAPBM） is proposed to try to solve some problems， including that the limitations of the distance measurement of the affinity prop…
ClusteringUnsupervised lexicon learning from speech is limited by representations rather than clustering
Zero-resource word segmentation and clustering systems aim to tokenise speech into word-like units without access to text labels. Despite progress, the induced lexicons are still far from perfect. In an idealised setting…
Graph ClusteringExploring dual information in distance metric learning for clustering
Distance metric learning algorithms aim to appropriately measure similarities and distances between data points. In the context of clustering, metric learning is typically applied with the assist of side-information prov…
ClusteringMetric Learning