학술논문
Fast Approximate Hubness Reduction for Large High-Dimensional Data
Document Type
Conference
Source
2018 IEEE International Conference on Big Knowledge (ICBK) ICBK Big Knowledge (ICBK), 2018 IEEE International Conference on. :358-367 Nov, 2018
Subject
Language
Abstract
High-dimensional data mining is challenging due to the "curse of dimensionality". Hubness reduction counters one particular aspect of the dimensionality curse, but suffers from quadratic algorithmic complexity. We present approximate hubness reduction methods with linear complexity in time and space, thus enabling hubness reduction for large data for the first time. Furthermore, we introduce a new hubness measure especially suited for large data, which is, in addition, readily interpretable. Experiments on synthetic and real-world data show that the approximations come at virtually no cost in accuracy in comparison with full hubness reduction. Finally, we demonstrate improved transport mode detection in massive mobility data collected with mobile devices as concrete research application. All methods are made publicly available in a free open source software package.