A Fast kNN Algorithm Using Multiple Space-Filling Curves

Entropy

Anton Shtanyuk¹  Konstantin Barkalov¹  Alexander Sysoyev¹ 

[1] Department of Mathematical Software and Supercomputing Technologies, Lobachevsky University, 603950 Nizhny Novgorod, Russia;

关键词: machine learning;    kNN;    dimensionality reduction;    multiple space-filling curves;   

DOI  :  10.3390/e24060767

来源: DOAJ

【 摘 要 】

The paper considers a time-efficient implementation of the k nearest neighbours (kNN) algorithm. A well-known approach for accelerating the kNN algorithm is to utilise dimensionality reduction methods based on the use of space-filling curves. In this paper, we take this approach further and propose an algorithm that employs multiple space-filling curves and is faster (with comparable quality) compared with the kNN algorithm, which uses kd-trees to determine the nearest neighbours. A specific method for constructing multiple Peano curves is outlined, and statements are given about the preservation of object proximity information in the course of dimensionality reduction. An experimental comparison with known kNN implementations using kd-trees was performed using test and real-life data.

【 授权许可】

Unknown