Title: Improved search strategies and extensions to k-medoids-based clustering algorithms

Authors: Shu-Chuan Chu, John F. Roddick, Jeng-Shyang Pan

Addresses: Department of Information Management, 840, Chengching Rd., Niausung, Kaohsiung, Taiwan. ' School of Computer Science, Engineering and Mathematics, Flinders University, P.O. Box 2100, Adelaide, South Australia 5001, Australia. ' Department of Electronic Engineering, National Kaohsiung University of Applied Sciences, Kaohsiung 807, Taiwan

Abstract: In this paper two categories of improvements are suggested that can be applied to most k-medoids-based algorithms – conceptual/algorithmic improvements, and implementational improvements. These include the revisiting of the accepted cases for swap comparison and the application of partial distance searching and previous medoid indexing to clustering. Various hybrids are then applied to a number of k-medoids-based algorithms and the method is shown to be generally applicable. Experimental results on both artificial and real datasets demonstrate that when applied to CLARANS the number of distance calculations can be reduced by up to 98%.

Keywords: PMI; previous medoid index; TIE; triangular inequality elimination; PDS; partial distance search; CLARA; clustering large applications; CLARANS; randomised search; CLASA; simulated annealing; search strategies.

DOI: 10.1504/IJBIDM.2008.020520

International Journal of Business Intelligence and Data Mining, 2008 Vol.3 No.2, pp.212 - 231

Published online: 28 Sep 2008 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article