Using Pivots to Speed-Up k-Medoids Clustering


  • Adriano Arantes Paterlini ICMC - USP
  • Mario A. Nascimento University of Alberta
  • Caetano Traina Jr. ICMC - USP


Clustering, k-medoids, Metric space, Pivot-based technique


Clustering is a key technique within the KDD process, with k-means, and the more general k-medoids, being well-known incremental partition-based clustering algorithms. A fundamental issue within this class of algorithms is to find an initial set of medians (or medoids) that improves the efficiency of the algorithms (e.g., accelerating its convergence to a solution), at the same time that it improves its effectiveness (e.g., finding more meaningful clusters). Thus, in this article we aim at providing a technique that, given a set of elements, quickly finds a very small number of elements as medoid candidates for this set, allowing to improve both the efficiency and effectiveness of existing clustering algorithms. We target the class of k-medoids algorithms in general, and propose a technique that selects a well-positioned subset of central elements to serve as the initial set of medoids for the clustering process. Our technique leads to a substantially smaller amount of distance calculations, thus improving the algorithm's efficiency when compared to existing methods, without sacrificing effectiveness.  A salient feature of our proposed technique is that it is not a new k-medoid clustering algorithm per se, rather, it can be used in conjunction with any existing clustering algorithm that is based on the k-medoid paradigm. Experimental results, using both synthetic and real datasets, confirm the efficiency, effectiveness and scalability of the proposed technique. 


Download data is not yet available.

Author Biographies

Adriano Arantes Paterlini, ICMC - USP

Systems Analyst at Department of Computer Science - ICMC - USP

Mario A. Nascimento, University of Alberta

Ph.D. Associate Professor at Department of Computing Science- University of Alberta

Caetano Traina Jr., ICMC - USP

Ph.D. Titular Professor at Department of Computer Science - ICMC - USP