Doktorandenseminarvortrag: Clustering in High-Dimensional Spaces

Abstract

Cluster analysis in high dimensional spaces faces some unintuitive problems. Especially for prototype based clustering algorithms produce unintuitive results. The problems are related to an effect called distance concentration, which describes that distances from a query point to all data objects become similar. Distance concentration was first defined by Bayer in [referenz] and further analysed in [referenz] All these analysis consider the k nearest neighbour problem. The theoretical framework is used to specify the distance concentration problem for clustering algorithms, especially hard k-means clustering, fuzzy c-means clustering, fuzzy c-means clustering with polynomial fuzzifier function and an alternative fuzzy c-means algorithm. In my talk, I discuss several strategies to counter the effect of distance concentration. The theoretical results are used on a 457-dimensional data set of aircraft movements on the airport of Frankfurt which contains roughly 720000 data objects.