Accepted paper at EDBT 2021

Authors

Anna Beer, Ekaterina Allerborn, Valentin Hartmann, Thomas Seidl

The 24th International Conference on Extending Database Technology (EDBT 2021),
23–26 March 2021, Nicosia, Cyprus

Abstract

In high-dimensional datasets some dimensions or attributes can be more important than others. Whereas most algorithms neglect one or more dimensions for all points of a dataset or at least for all points of a certain cluster together, our method KISS (kNN-based Importance Score of Subspaces) detects the most important dimensions for each point individually. It is fully unsupervised and does not depend on distorted multidimensional distance measures. Instead, the kNN in one-dimensional projections of the data points are used to calculate the score for every dimension’s importance. Experiments across a variety of settings show that those scores reflect well the structure of the data. KISS can be used for subspace clustering. What sets it apart from other methods for this task is its runtime, which is linear in the number of dimensions and O(n log(n)) in the number of points, as opposed to quadratic or even exponential runtimes for previous algorithms.