Parameter Free Clustering with Cluster Catch Digraphs (Technical Report)
  We propose clustering algorithms based on a recently developed geometric
digraph family called cluster catch digraphs (CCDs). These digraphs are used to
devise clustering methods that are hybrids of density-based and graph-based
clustering methods. CCDs are appealing digraphs for clustering, since they
estimate the number of clusters; however, CCDs (and density-based methods in
general) require some information on a parameter representing the
\emph{intensity} of assumed clusters in the data set. We propose algorithms
that are parameter free versions of the CCD algorithm and does not require a
specification of the intensity parameter whose choice is often critical in
finding an optimal partitioning of the data set. We estimate the number of
convex clusters by borrowing a tool from spatial data analysis, namely Ripley's
$K$ function. We call our new digraphs utilizing the $K$ function as RK-CCDs.
We show that the minimum dominating sets of RK-CCDs estimate and distinguish
the clusters from noise clusters in a data set, and hence allow the estimation
of the correct number of clusters. Our robust clustering algorithms are
comprised of methods that estimate both the number of clusters and the
intensity parameter, making them completely parameter free. We conduct Monte
Carlo simulations and use real life data sets to compare RK-CCDs with some
commonly used density-based and prototype-based clustering methods.
