On the performance of bisecting K-means and PDDP

1 Introduction and problem statement The problem this paper focuses on is the unsupervised clustering of a data-set. The dataset is given by the matrix M = x1,x2,…,xN ∊ ℜp×N, where each column of M, xi ∊ ℜp, is a single data-point. This is one of the more basic and common problems in fields like pattern analysis, data mining, document retrieval, image segmentation, decision making, etc. (12, 13). The specific problem we want to solve herein is the partition of M into two sub-matrices (or sub-clusters) ML ∊ ℜp×NL and MR ∊ ℜp×NR, NL + NR = N. This problem is known as bisecting divisive clustering.