title: Choosing ℓpnorms in high-dimensional spaces based on hub analysis.
abstract: The hubness phenomenon is a recently discovered aspect of the curse of dimensionality. Hub objects have a small distance to an exceptionally large number of data points while anti-hubs lie far from all other data points. A closely related problem is the concentration of distances in high-dimensional spaces. Previous work has already advocated the use of fractional ℓpnorms instead of the ubiquitous Euclidean norm to avoid the negative effects of distance concentration. However, which exact fractional norm to use is a largely unsolved problem. The contribution of this work is an empirical analysis of the relation of different ℓpnorms and hubness. We propose an unsupervised approach for choosing an ℓpnorm which minimizes hubs while simultaneously maximizing nearest neighbor classification. Our approach is evaluated on seven high-dimensional data sets and compared to three approaches that re-scale distances to avoid hubness.
authors.affiliation: Austrian Research Institute for Artificial Intelligence, Freyung 6/6, Vienna, Austria.
authors.forename: Arthur
authors.initials: A
authors.lastname: Flexer
authors.affiliation: Austrian Research Institute for Artificial Intelligence, Freyung 6/6, Vienna, Austria.
authors.forename: Dominik
authors.initials: D
authors.lastname: Schnitzer
keywords: Concentration of distances; Fractional norms; High-dimensional data analysis; Hubness