Μείωση δεδομένων με διαμερισμό του χώρου χρησιμοποιώντας αλγόριθμους Convex Hull για την εύρεση των πιο απομακρυσμένων αντικειμένων (Bachelor thesis)
Γκιοργκίνης, Θωμάς
In the ever evolving scientific field of data categorization, the nearest
neighbors algorithm is a stable, efficient method. However, it has sev eral weaknesses that deem it inappropriate in some cases of data sets.
Its main drawbacks are: high cost of categorizing each object due to
multiple calculations, high storage requirements, and dependence of
the accuracy of the results on the quality of the training data. In or der to address its weaknesses, several data reduction algorithms have
been implemented, aiming at minimizing the processing burden of the
categorizer without affecting its accuracy. The Reduction by Space
Partitioning algorithm is one of the most well-known prototype gen eration algorithms for accelerating instance based categorists. RSP3
is based on a repetitive separation process of the original training
set. As the criterion for the most subset will be divided first, RSP3
adopts the larger diameter criterion. That is, the subset with the
largest diameter defined by the two most distant objects is divided
first. The process continues until the resulting subsets are homoge neous, that is, they include objects of the same class. The search for
the two most remote objects of each subset is a costly process, since
it requires the calculation of all the distances between the objects of
each sub-set. Thus, RSP3 has a high computational pre-processing
cost. In the framework of the thesis, computational geometry algo rithms will be studied to find the Convex Hull of each subset. Convex
Hull is composed by the objects of the data set that define its con tour. The motivation for studying these algorithms stems from the
following observation: If these objects that define Convex Hull are
found, searching for the most remote objects in each subset will be
done quickly since it will not be necessary to calculate all possible
distances to the subset but only all possible distances between the
objects of Convex Hull. In the experimental part of the thesis, two
Convex Hull algorithms will be implemented and incorporated into
RSP3. It will also be investigated whether it is possible to use Con vex Hull algorithms in multi-dimensional datasets. The new variants
of RSP3 will be tested in 15 sets of real data categorization data and
their speed will be compared to that of the “conventional” RSP3.
| Institution and School/Department of submitter: | Σχολή Τεχνολογικών Εφαρμογών - Τμήμα Μηχανικών Πληροφορικής |
| Subject classification: | Αλγόριθμοι Algorithms Μείωση δεδομένων Data reduction |
| Keywords: | Convex Hull;απομακρυσμένα αντικείμενα;remotely objects;RSP3;αλγόριθμος των εγγύτερων γειτόνων;nearest neighbor algorithm;δεδομένα;data;Τεχνικές μείωσης δεδομένων;Data reduction techniques |
| Description: | Πτυχιακή εργασία - Σχολή Τεχνολογικών Εφαρμογών - Τμήμα Μηχανικών Πληροφορικής, 2019 (α/α 11044) |
| URI: | http://195.251.240.227/jspui/handle/123456789/15059 |
| Item type: | bachelorThesis |
| General Description / Additional Comments: | Πτυχιακή εργασία |
| Subject classification: | Αλγόριθμοι Algorithms Μείωση δεδομένων Data reduction |
| Submission Date: | 2022-07-24T15:04:35Z |
| Item language: | el |
| Item access scheme: | free |
| Institution and School/Department of submitter: | Σχολή Τεχνολογικών Εφαρμογών - Τμήμα Μηχανικών Πληροφορικής |
| Publication date: | 2019-02-22 |
| Bibliographic citation: | Γκιοργκίνης, Θ. (2019). Μείωση δεδομένων με διαμερισμό του χώρου χρησιμοποιώντας αλγόριθμους Convex Hull για την εύρεση των πιο απομακρυσμένων αντικειμένων. (Πτυχιακή εργασία). Διεθνές Πανεπιστήμιο της Ελλάδος |
| Abstract: | Στο συνεχές εξελισσόμενο επιστημονικό πεδίο της κατηγοριοποίησης
δεδομένων, ο αλγόριθμος των εγγύτερων γειτόνων αποτελεί μια στα θερή, αποτελεσματική μέθοδο. Διαθέτει όμως αδυναμίες που τον καθι στούν ακατάλληλο σε ορισμένες περιπτώσεις συνόλων δεδομένων. Τα
βασικά μειονεκτήματά του είναι: υψηλό κόστος κατηγοριοποίησης του
κάθε αντικειμένου λόγω πολλαπλών υπολογισμών που μεσολαβούν, υ ψηλές απαιτήσεις σε αποθηκευτικό χώρο και η σχέση εξάρτησης της
ακρίβειας των αποτελεσμάτων με την ποιότητα των δεδομένων εκπα ίδευσης. Στην προσπάθεια αντιμετώπισης των αδυναμιών του έχουν
υλοποιηθεί διάφοροι αλγόριθμοι μείωσης του πλήθους των δεδομένων,
που στοχεύουν στην όσο πιο δυνατή ελάττωση του φόρτου επεξεργασίας
του κατηγοριοποιητή χωρίς να επηρεάζεται η ακρίβειά του. Ο αλγόριθ μος Reduction by Space Partitioning είναι ένας από τους πιο γνωστούς
αλγόριθμους prototype generation για την επιτάχυνση instance based
κατηγοριοποιητών. Ο RSP3 βασίζεται σε μια επαναληπτική διαδικασία
διαχωρισμού του αρχικού συνόλου εκπαίδευσης. Ως κριτήριο για το πιο
υποσύνολο θα διαιρεθεί πρώτο, ο RSP3 υιοθετεί το κριτήριο της με γαλύτερης διαμέτρου. Δηλαδή, το υποσύνολο με τη μεγαλύτερη διάμε τρο που ορίζεται από τα δύο πιο απομακρυσμένα αντικείμενα διαιρείται
πρώτο. Η διαδικασία συνεχίζεται μέχρις ότου τα υποσύνολα που προ κύπτουν είναι ομοιογενή, δηλαδή να περιλαμβάνουν αντικείμενα της ίδια
κλάσης. Η αναζήτηση των δυο πιο απομακρυσμένων αντικειμένων κάθε
υποσυνόλου αποτελεί μια διαδικασία μεγάλου κόστους, αφού προϋπο θέτει τον υπολογισμό όλων των αποστάσεων μεταξύ των αντικειμένων
του κάθε υποσυνόλου. ΄Ετσι, ο RSP3 έχει υψηλό υπολογιστικό κόστος
προ-επεξεργασίας. Στα πλαίσια της εργασίας θα μελετηθούν οι αλγόριθ μοι υπολογιστικής γεωμετρίας για την εύρεση του Convex Hull του κάθε
υποσυνόλου. Το Convex Hull είναι τα αντικείμενα του συνόλου δεδο μένων που ορίζουν το περίγραμμα του. Το κίνητρο για την μελέτη αυτών
των αλγορίθμων πηγάζει από την εξής παρατήρηση: Αν βρεθούν αυτά
τα αντικείμενα που ορίζουν το Convex Hull, η αναζήτηση των πιο α πομακρυσμένων αντικειμένων σε κάθε υποσύνολο θα γίνεται γρήγορα
αφού δεν θα απαιτείται η εύρεση όλων των πιθανών αποστάσεων στο
υποσύνολο αλλά μόνο όλων των πιθανών αποστάσεων μεταξύ των α ντικείμενων του Convex Hull. Στο πειραματικό κομμάτι της εργασίας
δύο αλγόριθμοι Convex Hull θα υλοποιηθούν και ενσωματωθούν στον
RSP3. Επίσης, θα μελετηθεί το κατά πόσο είναι δυνατό, οι αλγόριθ μοι εύρεσης του Convex Hull να εκτελεστούν σε σύνολα δεδομένων με
πολλές διαστάσεις. Οι νέες παραλλαγές του RSP3 θα δοκιμαστούν σε
15 σύνολα δεδομένων κατηγοριοποίησης πραγματικών δεδομένων και η
ταχύτητα τους θα συγκριθεί με τον “συμβατικό” RSP3. In the ever evolving scientific field of data categorization, the nearest neighbors algorithm is a stable, efficient method. However, it has sev eral weaknesses that deem it inappropriate in some cases of data sets. Its main drawbacks are: high cost of categorizing each object due to multiple calculations, high storage requirements, and dependence of the accuracy of the results on the quality of the training data. In or der to address its weaknesses, several data reduction algorithms have been implemented, aiming at minimizing the processing burden of the categorizer without affecting its accuracy. The Reduction by Space Partitioning algorithm is one of the most well-known prototype gen eration algorithms for accelerating instance based categorists. RSP3 is based on a repetitive separation process of the original training set. As the criterion for the most subset will be divided first, RSP3 adopts the larger diameter criterion. That is, the subset with the largest diameter defined by the two most distant objects is divided first. The process continues until the resulting subsets are homoge neous, that is, they include objects of the same class. The search for the two most remote objects of each subset is a costly process, since it requires the calculation of all the distances between the objects of each sub-set. Thus, RSP3 has a high computational pre-processing cost. In the framework of the thesis, computational geometry algo rithms will be studied to find the Convex Hull of each subset. Convex Hull is composed by the objects of the data set that define its con tour. The motivation for studying these algorithms stems from the following observation: If these objects that define Convex Hull are found, searching for the most remote objects in each subset will be done quickly since it will not be necessary to calculate all possible distances to the subset but only all possible distances between the objects of Convex Hull. In the experimental part of the thesis, two Convex Hull algorithms will be implemented and incorporated into RSP3. It will also be investigated whether it is possible to use Con vex Hull algorithms in multi-dimensional datasets. The new variants of RSP3 will be tested in 15 sets of real data categorization data and their speed will be compared to that of the “conventional” RSP3. |
| Advisor name: | Ουγιάρογλου, Στέφανος |
| Examining committee: | Δέρβος, Δημήτριος |
| Publishing department/division: | Σχολή Τεχνολογικών Εφαρμογών /Τμήμα Μηχανικών Πληροφορικής |
| Publishing institution: | ihu |
| Number of pages: | 87 |
| Appears in Collections: | Πτυχιακές Εργασίες |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| GKIORKINIS.pdf | 1.32 MB | Adobe PDF | View/Open |
Please use this identifier to cite or link to this item:
This item is a favorite for 0 people.
http://195.251.240.227/jspui/handle/123456789/15059
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
