Algorithms and techniques for efficient and effective nearest neighbours classification

Αρχική

Πλοήγηση

Επιστημονικό πεδίο

Ημερομηνία

Συγγραφέας

Χώρα

Γλώσσα

Ίδρυμα

Σχετικά με το ΕΑΔΔ

Κατάθεση Διατριβής

Συχνές Ερωτήσεις

Κέντρο Υποστήριξης Χρηστών

Επικοινωνία

Ανοικτά Δεδομένα

Περίληψη

Ο κατηγοριοποιητής κ εγγύτερων γειτόνων είναι ένας αποτελεσματικός αλγόριθμος κατηγοριοποίησης. Ωστόσο, περιλαμβάνει μειονεκτήματα και αδυναμίες που τον καθιστούν ακατάλληλο σε συγκεκριμένα πεδία εφαρμογής ή/και σύνολα δεδομένων. Το πρώτο μειονέκτημα είναι το υψηλό κόστος κατηγοριοποίησης ως αποτέλεσμα του υπολογισμού των αποστάσεων μεταξύ κάθε αντικείμενου προς κατηγοριοποίηση και όλων των αντικειμένων που ανήκουν στο σύνολο εκπαίδευσης. Αν και τα σημερινά υπολογιστικά συστήματα είναι εφοδιασμένα με ισχυρούς επεξεργαστές, σε περιπτώσεις μεγάλων συνόλων δεδομένων, το συγκεκριμένο μειονέκτημα καθιστά την κατηγοριοποίηση μια ιδιαίτερα χρονοβόρα διαδικασία, η εκτέλεση της οποίας μπορεί να είναι απαγορευτική. Το δεύτερο μειονέκτημα αφορά τις μεγάλες απαιτήσεις σε αποθηκευτικό χώρο. Κατηγοριοποιητές που βασίζονται σε μοντέλα κατηγοριοποίησης (π.χ., δένδρα απόφασης, νευρωνικά δίκτυα) μπορούν μετά την κατασκευή του μοντέλου να διαγράψουν τα δεδομένα εκπαίδευσης ώστε να εξοικονομήσουν χώρο. Αντίθετα, ο κατηγοριοποιητής κ εγγύτερων γειτόνων πρέπει να έχει πάντα όλα τα δεδομένα εκπαίδευσης διαθέσιμα. Έτσι δεν είναι δυνατή η εξοικονόμηση αποθηκευτικού χώρου. Τέλος, η ακρίβεια που επιτυγχάνει ο κατηγοριοποιητής κ εγγύτερων γειτόνων εξαρτάται από την ποιότητα των δεδομένων εκπαίδευσης. Δεδομένα με θόρυβο, αντικείμενα χωρίς ετικέτα κλάσης, ακραία σημεία και επικαλύψεις στις περιοχές διαφορετικών κλάσεων αποπροσανατολίζουν τον κατηγοριοποιητή με αποτέλεσμα τη μείωση της ακρίβειας.Τα μειονεκτήματα αυτά αποτελούν μια ενεργή περιοχή έρευνας. Η διδακτορική διατριβή έχει ως κίνητρο την αντιμετώπιση των συγκεκριμένων μειονεκτημάτων. Ως εκ τούτου, η διατριβή συνεισφέρει καινοτόμους αλγόριθμους που αντιμετωπίζουν με αποτελεσματικό τρόπο τα μειονεκτήματα αυτά. Με άλλα λόγια, η διατριβή προτείνει αλγόριθμους και τεχνικές αποτελεσματικής κατηγοριοποίησης εγγύτερων γειτόνων. Η συνεισφορά έχει χωριστεί σε τρεις κατηγορίες: (i) νέες τεχνικές μείωσης όγκου των δεδομένων εκπαίδευσης που αντιμετωπίζουν όλα τα μειονεκτήματα και δεν παρουσιάζουν τις αδυναμίες υπαρχουσών τεχνικών, (ii) υβριδικούς αλγορίθμους που συνδυάζουν διαφορετικού τύπου μεθόδους επιτάχυνσης με στόχο την μείωση του υπολογιστικού κόστους της κατηγοριοποίησης (iii) βελτιώσεις σε υπάρχουσες τεχνικές και πειραματικές μελέτες.Η απόδοση των προτεινόμενων αλγόριθμων, τεχνικών και βελτιώσεων ελέγχθηκε πειραματικά και συγκρίθηκε με γνωστές στη βιβλιογραφία μεθόδους χρησιμοποιώντας διάφορα σύνολα δεδομένων. Οι πειραματικές μετρήσεις επικυρώθηκαν με το μη παραμετρικό στατιστικό τεστ του Wilcoxon. Τα αποτελέσματα υποδεικνύουν ότι οι αλγόριθμοι, οι τεχνικές και οι βελτιώσεις επιτυγχάνουν τον σκοπό για τον οποίο αναπτύχθηκαν και ότι οδηγούν σε αποτελεσματική κατηγοριοποίηση σε ότι αφορά την ακρίβεια, το κόστος κατηγοριοποίησης και το κόστος προ-επεξεργασίας.

περισσότερα

Περίληψη σε άλλη γλώσσα

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.

περισσότερα

Διαβάστε τη διατριβή (Online)

Κατεβάστε τη διατριβή σε μορφή PDF (4.53 MB) (Η υπηρεσία είναι διαθέσιμη μετά από δωρεάν εγγραφή)

Όλα τα τεκμήρια στο ΕΑΔΔ προστατεύονται από πνευματικά δικαιώματα.

DOI	10.12681/eadd/34608
Διεύθυνση Handle	http://hdl.handle.net/10442/hedi/34608
ND	34608
Εναλλακτικός τίτλος	Algorithms and techniques for efficient and effective nearest neighbours classification
Συγγραφέας	Ουγιαρόγλου, Στέφανος (Πατρώνυμο: Ανέστης)
Ημερομηνία	2014
Ίδρυμα	Πανεπιστήμιο Μακεδονίας. Σχολή Επιστημών Πληροφορίας. Τμήμα Εφαρμοσμένης Πληροφορικής
Εξεταστική επιτροπή	Ευαγγελίδης Γεώργιος Δέρβος Δημήτριος Aldama Montes Jose Francisco Μαργαρίτης Κωνσταντίνος Σαμαράς Νικόλαος Κολωνιάρη Γεωργία Παπαδόπουλος Απόστολος
Επιστημονικό πεδίο	Φυσικές Επιστήμες ➨ Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
Λέξεις-κλειδιά	Εγγύτεροι γείτονες; Κατηγοριοποίηση; Συσταδοποίηση; Μείωση όγκου δεδομένων, Συμπύκνωση δεδομένων; Επιλογή / Δημιουργία αντιπροσώπων; Ροές δεδομένων / Δυναμικά περιβάλλοντα; Επεξεργασία με σκοπό τη μείωση θορύβου; Χρονοσειρές
Χώρα	Ελλάδα
Γλώσσα	Αγγλικά
Άλλα στοιχεία	247 σ., πιν., σχημ., γραφ.
Ειδικοί όροι χρήσης/διάθεσης	Το έργο παρέχεται υπό τους όρους της δημόσιας άδειας του νομικού προσώπου Creative Commons Corporation: Αναφορά Δημιουργού 3.0 (CC-BY)

Στατιστικά χρήσης

ΠΡΟΒΟΛΕΣ

Αφορά στις μοναδικές επισκέψεις της διδακτορικής διατριβής για την χρονική περίοδο 07/2018 - 07/2023.
Πηγή: Google Analytics.

ΞΕΦΥΛΛΙΣΜΑΤΑ

Αφορά στο άνοιγμα του online αναγνώστη για την χρονική περίοδο 07/2018 - 07/2023.
Πηγή: Google Analytics.

ΜΕΤΑΦΟΡΤΩΣΕΙΣ

Αφορά στο σύνολο των μεταφορτώσων του αρχείου της διδακτορικής διατριβής.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.

ΧΡΗΣΤΕΣ

Αφορά στους συνδεδεμένους στο σύστημα χρήστες οι οποίοι έχουν αλληλεπιδράσει με τη διδακτορική διατριβή. Ως επί το πλείστον, αφορά τις μεταφορτώσεις.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.

Σχετικές εγγραφές (με βάση τις επισκέψεις των χρηστών)

Εκπαιδευτική τεχνολογία: ένας διδακτικός μικρόκοσμος για την εισαγωγή στον αντικειμενοστραφή προγραμματισμό

Energy management and consumer modeling in smart grid systems

Ανάπτυξη συστήματος υποστήριξης αποφάσεων σε περιβάλλον γεωγραφικών συστημάτων πληροφοριών με χρήση ασαφών πολυκριτήριων μεθόδων

Εκπαιδευτική τεχνολογία. Προσαρμοστικό διαδικτυακό περιβάλλον συμβατό με το πρότυπο SCORM με χρήση μαθητύπων για εξ' αποστάσεως εκπαίδευση: εφαρμογή στη διδασκαλία του αντικειμενοστραφούς προγραμματισμού

Βελτιστοποίηση της απόδοσης ενός χειμερινού κι ενός εαρινού ενεργειακού φυτού

Scalable indexing and exploration of big time series data

Κατασκευή και εφαρμογές μικροαισθητήρων για χημική ανάλυση

Αλγόριθμοι διαχείρισης δεδομένων και εξαγωγή γνώσης σε εφαρμογές γράφων

Εξόρυξη γνώσης από βάσεις χρονοσειρών: επιλογή χαρακτηριστικών και κατηγοριοποίηση

Εφαρμογή αλγορίθμων μηχανικής εκμάθησης για εξόρυξη και κατηγοριοποίηση πληροφοριών περιεχομένου στα οπτικοακουστικά μέσα

"Αλγόριθμοι και τεχνικές για αποδοτική και αποτελεσματική κατηγοριοποίηση εγγυτέρων γειτόνων"
	Πληκτρολογήστε το κείμενο της εικόνας!
Δηλώνω ότι έλαβα γνώση και ανεπιφύλακτα συμφωνώ και αποδέχομαι τους Όρους Χρήσης του Εθνικού Αρχείου Διδακτορικών Διατριβών, καθώς και της . Έλαβα γνώση οτι το έργο παρέχεται υπό τους όρους της δημόσιας άδειαςCreative Commons Αναφορά Δημιουργού 3.0 Ελλάδα