Skinny-dip: Clustering in a Sea of Noise
published: Sept. 25, 2016, recorded: August 2016, views: 1167
Report a problem or upload filesIf you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Can we ﬁnd heterogeneous clusters hidden in data sets with 80% noise? Although such settings occur in the real-world, we struggle to ﬁnd methods from the abundance of clustering techniques that perform well with noise at this level. Indeed, perhaps this is enough of a departure from classical cluster-ing to warrant its study as a separate problem. In this paper we present SkinnyDip which, based on Hartigan’s elegant dip test of unimodality, represents an intriguing approach to clustering with an attractive set of properties. Speciﬁcally, SkinnyDip is highly noise-robust, practically parameter-free and completely deterministic. SkinnyDip never performs multivariate distance calculations, but rather employs in-sightful recursion based on “dips” into univariate projections of the data. It is able to detect a range of cluster shapes and densities, assuming only that each cluster admits a unimodal shape. Practically, its run-time grows linearly with the data. Finally, for high-dimensional data, continuity properties of the dip enable SkinnyDip to exploit multimodal projection pursuit in order to ﬁnd an appropriate basis for clustering. Although not without its limitations, SkinnyDip compares favorably to a variety of clustering approaches on synthetic and real data, particularly in high-noise settings.
Link this pageWould you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !