<i>K</i>-CDFs: a Nonparametric Clustering Algorithm via Cumulative Distribution Function

We propose a novel partitioning clustering procedure based on the cumulative distribution function (CDF), called <i>K</i>-CDFs. For univariate data, the <i>K</i>-CDFs represent the cluster centers by empirical CDFs and assign each observation to the closest center measured by the Crame´r-von Mises distance. The procedure is nonparametric and does not require assumptions on cluster distributions imposed by mixture models. A projection technique is used to generalize the <i>K</i>-CDFs for univariate data to an arbitrary dimension. The proposed procedure has several appealing properties. It is robust to heavy-tailed data, is not sensitive to the data dimensions, does not require moment conditions on data and can effectively detect linearly nonseparable clusters. To implement the <i>K</i>-CDFs, we propose two kinds of algorithms: a greedy algorithm as the classical Lloyd’s algorithm and a spectral relaxation algorithm. We illustrate the finite sample performance of the proposed algorithms through simulation experiments and empirical analyses of several real datasets.