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.