KERNEL DENSITY ESTIMATION, AFFINITY-BASED CLUSTERING, AND TYPICAL CUTS

The typical cut is a clustering method that is based on the probability pnm that points xn and xm are in the same cluster over all possible partitions (under the Boltzmann distribution for the mincut cost function). We present two contributions regarding this algorithm. (1) We show that, given a kernel density estimate of the data, minimising the overlap between cluster densities is equivalent to the mincut criterion. This gives a principled way to determine what affinities and scales to use in the typical-cut algorithm, and more generally in clustering and dimensionality reduction algorithms based on pairwise affinities. (2) We introduce an iterated version of the typical-cut algorithm, where the estimated pnm are used to refine the affinities. We show this procedure is equivalent to finding stationary points of a certain objective function over clusterings; and that at the stationary points the value of pnm is 1 if n and m are in the same cluster and a small value otherwise. Thus, the iterated typical-cut algorithm sharpens the pnm matrix and makes the cluster structure more obvious. 1.