
Computer Science 2015
Active DistanceBased Clustering using KmedoidsAbstract: kmedoids algorithm is a partitional, centroidbased clustering algorithm which uses pairwise distances of data points and tries to directly decompose the dataset with $n$ points into a set of $k$ disjoint clusters. However, kmedoids itself requires all distances between data points that are not so easy to get in many applications. In this paper, we introduce a new method which requires only a small proportion of the whole set of distances and makes an effort to estimate an upperbound for unknown distances using the inquired ones. This algorithm makes use of the triangle inequality to calculate an upperbound estimation of the unknown distances. Our method is built upon a recursive approach to cluster objects and to choose some points actively from each bunch of data and acquire the distances between these prominent points from oracle. Experimental results show that the proposed method using only a small subset of the distances can find proper clustering on many realworld and synthetic datasets.
