Hilbert Space Filling Curve (HSFC) Nearest Neighbor Classifier
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.
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 downloading and filling out the Internet Distribution Consent Agreement. You may also contact the project coordinator Kerri Bottorff for more information.
Bachelor of Science (B.S.)
College of Engineering and Computer Science
Dissertations, Academic -- Engineering; Engineering -- Dissertations, Academic
Length of Campus-only Access
Honors in the Major Thesis
Reeder, John, "Hilbert Space Filling Curve (HSFC) Nearest Neighbor Classifier" (2005). HIM 1990-2015. 475.