Learning Linear Representation of Space Partitioning Trees Based on Unsupervised Kernel Dimension Reduction

Space partitioning trees, which sequentially divide and subdivide a space into disjoint subsets using splitting hyperplanes, play a key role in accelerating the query of samples in the cybernetics and computer vision domains. Associated methods, however, suffer from the curse of dimensionality or stringent assumptions on the data distribution. This paper presents a new concept, termed kernel dimension reduction-tree (KDR-tree), that relies on linear projections computed based on an unsupervised kernel dimension reduction approach. The proposed concept does not rely on any assumption on the data distribution and can capture higher-order statistical information encapsulated within the data. This paper then develops two variants of the KDR-tree concept: 1) to handle residual data [i.e., the residual-based KDR-tree (rKDR-tree) algorithm] and 2) to cope with larger datasets, [i.e., the sampling-based KDR-tree (sKDR-tree) algorithm]. By directly comparing the KDR-tree concept to competitive techniques, involving several benchmark datasets, this paper shows that the sKDR-tree yields a better performance for non-Gaussian distributed datasets. Based on the analysis of three datasets, this paper highlights, experimentally, that the rKDR-tree has the potential to discover the intrinsic dimension. This paper also provides a theoretical analysis about the KDR-tree concept to outline why it outperforms existing techniques if the data distribution is non-Gaussian.