Gauss Shift: Density Attractor Clustering Faster Than Mean Shift

Richard Leibrandt, Stephan Günnemann

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations

Abstract

Mean shift is a popular and powerful clustering method. While techniques exist that improve its absolute runtime, no method has been able to effectively improve its quadratic time complexity with regard to dataset size. To enable development of an alternative, faster method that leads to the same results, we first contribute the formal cluster definition, which mean shift implicitly follows. Based on this definition we derive and contribute Gauss shift – a method that has linear time complexity. We quantify the characteristics of Gauss shift using synthetic datasets with known topologies. We further qualify Gauss shift using real-life data from active neuroscience research, which is the most comprehensive description of any subcellular organelle to date. Supplementary material: www.daml.in.tum.de/gauss-shift.

Original languageEnglish
Title of host publicationMachine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2020, Proceedings
EditorsFrank Hutter, Kristian Kersting, Jefrey Lijffijt, Isabel Valera
PublisherSpringer Science and Business Media Deutschland GmbH
Pages125-142
Number of pages18
ISBN (Print)9783030676575
DOIs
StatePublished - 2021
EventEuropean Conference on Machine Learning and Knowledge Discovery in Databases, ECML PKDD 2020 - Virtual, Online
Duration: 14 Sep 202018 Sep 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12457 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceEuropean Conference on Machine Learning and Knowledge Discovery in Databases, ECML PKDD 2020
CityVirtual, Online
Period14/09/2018/09/20

Keywords

  • Clustering
  • Density attractor clustering
  • Efficiency
  • Gauss shift
  • Local search
  • Neuroscience
  • Optimization
  • mean shift

Fingerprint

Dive into the research topics of 'Gauss Shift: Density Attractor Clustering Faster Than Mean Shift'. Together they form a unique fingerprint.

Cite this