Back to search

Πανεπιστήμιο Μακεδονίας

Algorithms and techniques for efficient and effective nearest neighbours classification

Abstract

dc:description

Although the k-NN classifier is considered to be an effective classification algorithm, it has some major weaknesses that may render its use inappropriate for some application domains and / or datasets. The first one is the high computational cost involved (all distances between each unclassified item and all training data must be computed). Although nowadays systems are equipped with powerful processors, in cases of large datasets, this drawback renders the classification a time-consuming and in some cases a prohibitive procedure. Another weakness is the high storage requirements for maintaining the training data. Eager classifiers (e.g., decision tress, neural networks) can discard the training data after the construction of the classification model in order to save space. In contrast, the k-NN classifier must have all the training data always available. Moreover, the classification accuracy achieved by the classifier depends on the quality of the available training data. Noisy and mislabelled data, as well as outliers and overlaps between data regions of different classes may mislead the algorithm and affect the classification accuracy. The aforementioned weaknesses constitute an active research problem. The dissertation is motivated by these weaknesses and tries to remedy the problem. Therefore, it contributes novel algorithms and techniques that can effectively deal with the aforementioned weaknesses. In other words, it proposes algorithms and techniques for efficient and effective k-NN classification. The contributions are distinguished into three main categories: (i) new data reduction techniques that deal with all the weak points of the classifier and avoid the limitations and disadvantages of existing data reduction techniques, (ii) novel hybrid algorithms that combine different types of speed-up techniques and that can effectively reduce the computational cost of the classifier, and, (iii) improvements and experimentations for existing algorithms.The proposed algorithms, techniques and improvements are evaluated on several datasets and experimentally compared to state-of-the-art methods. The experimental measurements are validated by statistical tests of significance. The results illustrate that the proposed methods satisfy the goals for which they were developed and lead to improved classification, in terms of accuracy, preprocessing and computational cost.

Degree

thesis:*
Grantor dc:publisher
Πανεπιστήμιο Μακεδονίας
Year dc:date
2014

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Ougiaroglou, Stefanos
  • Ουγιαρόγλου, Στέφανος

Subjects

dc:subject × 20

Rights

dc:rights
Statement dc:rights
  • BY
Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/34608

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Ougiaroglou, Stefanos; Ουγιαρόγλου, Στέφανος. Algorithms and techniques for efficient and effective nearest neighbours classification. Πανεπιστήμιο Μακεδονίας, 2014. http://hdl.handle.net/10442/hedi/34608