Title

Hilbert Space Filling Curve (Hsfc) Nearest Neighbor Classifier

Abstract

The Nearest Neighbor algorithm is one of the simplest and oldest classification techniques. A given collection of historic data (Training Data) of known classification is stored in memory. Then based on the stored knowledge the classification of unknown data (Test Data) is predicted by finding the classification of the nearest neighbor. The drawback of this classifier is found when a test instance is presetted to be classified. The distance from the test patten to every point in the training set must be found. The required computations to find these distances are proportional to the number of training points (A), which is computationally complex, especially with N large. The purpose of this paper is to reduce the computational complexity of the testing phase of the nearest neighbor by using the Hilbert Space Filling Curve (HSFC). The HSFC allows you to find the nearest points to a test datum in 0(log(N)) computations. The HSFC computational advantage is achieved at the expense of classification accuracy, since die HSFC approach cannot always find the nearest of the neighbors. In this paper, we quantify the comparative performance of the HSFC-NN and the NN approaches for a number of classification problems. Thus, we draw important conclusions about the advantages and disadvantages of the HSFC method in finding the nearest neighbors of a test datum in nearest neighbor classification approaches.

Publication Date

1-1-2005

Publication Title

2nd International Conference on Cybernetics and Information Technologies, Systems and Applications, CITSA 2005, 11th International Conference on Information Systems Analysis and Synthesis, ISAS 2005

Volume

2

Number of Pages

273-278

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

Socpus ID

37349096858 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/37349096858

This document is currently not available here.

Share

COinS