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 an unknown data (Test Data) is predicted by finding the classification of the nearest neighbor. For example, if an instance from the test set is presented to the nearest neighbor classifier, its nearest neighbor, in terms of some distance metric, in the training set is found. Then its classification is predicted to be the classification of the nearest neighbor. This classifier is known as the 1-NN (one-nearest-neighbor). An extension to this classifier is the k-NN classifier. It follows the same principle as the 1-NN classifier with the addition of finding k (k > l) neighbors and taking the classification represented by the highest number of its neighbors. It is easy to see that the implementation of the nearest neighbor classifier is effortless, simply store the training data and their classifications. The drawback of this classifier is found when a test instance is presented to be classified. The distance from the test pattern. 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 (N), which is computationally complex, especially with N large. The purpose of this thesis is to reduce the computational complexity of the testing phase of the nearest neighbor by using the Hilbert Space Filling Curve (HSFC). The HSFC NN classifier was implemented and its accuracy and computational complexity is compared to the original NN classifier to test the validity of using the HSFC in classification.

Notes

This item is only available in print in the UCF Libraries. If this is your thesis or dissertation, you can help us make it available online for use by researchers around the world by STARS for more information.

Thesis Completion

2005

Semester

Spring

Advisor

Georgiopoulos, Michael

Degree

Bachelor of Science (B.S.)

College

College of Engineering and Computer Science

Degree Program

Computer Engineering

Subjects

Dissertations, Academic -- Engineering; Engineering -- Dissertations, Academic

Format

Print

Identifier

DP0022043

Language

English

Access Status

Open Access

Length of Campus-only Access

None

Document Type

Honors in the Major Thesis

This document is currently not available here.

Share

COinS