Choosing the Cluster to Split in Bisecting Divisive Clustering Algorithms

Abstract

This paper deals with the problem of clustering a data-set. In particular, the bisecting divisive approach is here considered. This approach can be naturally divided into two sub-problems: the problem of choosing which cluster must be divided, and the problem of splitting the selected cluster. The focus here is on the first problem. The contribution of this work is to propose a new simple technique for the selection of the cluster to split. This technique is based upon the shape of the cluster. This result is presented with reference to two specific splitting algorithms: the celebrated bisecting K-means algorithm, and the recently proposed Principal Direction Divisive Partitioning (PDDP) algorithm. The problem of evaluating the quality of a partition is also discussed.