On March 5, 2024, Sampath Deegalla will present his PhD thesis at the Department of Computer and Systems Sciences (DSV), Stockholm University. The title of the thesis is “Nearest Neighbor Classification in High Dimensions”.

The defence takes place at DSV in Kista, starting at 13:00 pm.
Find your way to DSV

Download the PhD thesis from Diva

PhD student: Sampath Deegalla, DSV
Opponent: Professor Slawomir Nowaczyk, Halmstad University
Main supervisor: Professor Henrik Boström, KTH
Supervisor: Professor Keerthi Walgama, University of Peradeniya, Sri Lanka

Contact Sampath Deegalla

Abstract

The simple k nearest neighbor (kNN) method can be used to learn from high dimensional data such as images and microarrays without any modification to the original version of the algorithm. However, studies show that kNN’s accuracy is often poor in high dimensions due to the curse of dimensionality; a large number of instances are required to maintain a given level of accuracy in high dimensions. Furthermore, distance measurements such as the Euclidean distance may be meaningless in high dimensions. As a result, dimensionality reduction could be used to assist nearest neighbor classifiers in overcoming the curse of dimensionality. Although there are success stories of employing dimensionality reduction methods, the choice of which methods to use remains an open problem. This includes understanding how they should be used to improve the effectiveness of the nearest neighbor algorithm.

The thesis examines the research question of how to learn effectively with the nearest neighbor method in high dimensions. The research question was broken into three smaller questions. These were addressed by developing effective and efficient nearest neighbor algorithms that leveraged dimensionality reduction. The algorithm design was based on feature reduction and classification algorithms constructed using the reduced features to improve the accuracy of the nearest neighbor algorithm. Finally, forming nearest neighbor ensembles was investigated using dimensionality reduction.

A series of empirical studies were conducted to determine which dimensionality reduction techniques could be used to enhance the performance of the nearest neighbor algorithm in high dimensions. Based on the results of the initial studies, further empirical studies were conducted and they demonstrated that feature fusion and classifier fusion could be used to improve the accuracy further. Two feature and classifier fusion techniques were proposed, and the circumstances in which these techniques should be applied were examined. Furthermore, the choice of the dimensionality reduction method for feature and classifier fusion was investigated. The results indicate that feature fusion is sensitive to the selection of the dimensionality reduction method. Finally, the use of dimensionality reduction in nearest neighbor ensembles was investigated. The results demonstrate that data complexity measures such as the attribute-to-instance ratio and Fisher’s discriminant ratio can be used to select the nearest neighbor ensemble depending on the data type.

Keywords: Nearest Neighbor, High-Dimensional Data, Curse of Dimensionality, Dimensionality Reduction