A new efficient medoid based divisive hierarchical clustering method for large-scale data

Abstract Clustering in data mining groups a set of data objects into a collection of different classes which are called clusters. Being one category of the most popular clustering methods, hierarchical clustering has found applications in various disciplines as an effective tool for data analysis. However, a run of hierarchical clustering requires multiple iterations to compute and update the pairwise distances between all intermediate clusters, making the conventional linkage methods of hierarchical clustering algorithms inevitably suffer from the quadratic time and space complexity. Given the fact that the choice of linkage profoundly affects not only the quality but also the efficiency of hierarchical clustering, we propose in this paper a new linkage method, named the medoid linkage, for hierarchical clustering and design an efficient divisive algorithm, referred to as MEDIA, for it to address the scalability issue of hierarchical clustering large-scale data. Experiments performed on both synthetic and real datasets demonstrate that our scheme can not only provide better clustering results but also scale well for large-sized high-dimensional data.