Μελέτη Μεθόδων Μείωσης Διαστατικότητας:
Creators: name: Στεργίου, Ελευθερία Αντωνίου
Publisher: name: Aristotle University of Thessaloniki
Year: 2010
Subjects: Μείωση Διαστατικότητας
Αλγόριθμος ΦΕΔΡΑ
Πολυδιάστατα δεδομένα
Dimensionality Reduction
FEDRA Algorithm
Multidimensional data

description: Οι εξελίξεις στη συλλογή δεδομένων και οι δυνατότητες αποθήκευσης κατά την διάρκεια των περασμένων δεκαετιών οδήγησαν σε μια υπερφόρτωση πληροφοριών στις περισσότερες επιστήμες. Οι ερευνητές δουλεύοντας σε διάφορους τομείς όπως αστρονομία, βιολογία, οικονομικά, πληροφορική και μηχανική αντιμετωπίζουν όλο και περισσότερες παρατηρήσεις και προσομοιώσεις σε καθημερινή βάση. Τα προβλήματα ανάλυσης δεδομένων όπου τα αντικείμενα δεδομένων έχουν μεγάλο αριθμό χαρακτηριστικών γίνονται περισσότερο διαδεδομένα σε περιοχές όπως η ανάλυση πολυμεσικών δεδομένων αλλά και η βιοπληροφορική. Σε τέτοιες περιπτώσεις είναι συχνά ωφέλιμη η μείωση της διάστασης των δεδομένων (μείωση διαστατικότητας) έτσι ώστε να βελτιωθεί η αποδοτικότητα και η ακρίβεια της ανάλυσης των δεδομένων. Για αυτόν τον λόγο αναπτύχθηκαν οι μέθοδοι μείωσης διαστατικότητας (Dimensionality Reduction Techniques). Η μείωση διαστάσεων (Dimensionality Reduction –DR) είναι μια μεθοδολογία που προσπαθεί να προβάλει ένα σύνολο από διανύσματα υψηλής διάστασης σε ένα χώρο χαμηλότερης διάστασης. Στόχος της μεθοδολογίας μείωσης διαστάσεων είναι η μείωση των διαστάσεων των δεδομένων με ταυτόχρονη διατήρηση των ιδιοτήτων τους. Πιο αναλυτικά οι Τεχνικές Μείωσης Διάστασης προβάλουν δεδομένα από τον αρχικό υψηλής διάστασης χώρο Rn σε έναν νέο χαμηλότερης διάστασης χώρο Rk (συνήθως k &lt;&lt; n). Η μεθοδολογία αυτή είναι απαραίτητη για διάφορους λόγους. Αρχικά, γιατί με αυτόν τον τρόπο οι αποστάσεις μεταξύ των δεδομένων στον ελαττωμένο χώρο υπολογίζονται πιο γρήγορα. Παράλληλα, το μέγεθος του συνόλου δεδομένων μειώνεται και αποκαλύπτεται η δομή των δεδομένων, η οποία παραμένει κρυμμένη στον αρχικό πολυδιάστατο χώρο. Είναι γεγονός ακόμα πως βελτιώνεται η αποδοτικότητα των τεχνικών εξόρυξης δεδομένων και οι ερωτήσεις ομοιότητας είναι πιο γρήγορες. Στόχος της παρούσα εργασίας είναι η Μελέτη Τεχνικών Μείωσης Διαστατικότητας. Πιο συγκεκριμένα, υλοποιείται ο αλγόριθμος FEDRA στην γλώσσα προγραμματισμού Matlab και αναλύονται εκτενώς οι παρακάτω αλγόριθμοι: PCA (Principal Component Analysis), MDS (Multidimensional Scaling), LLE (Locally Linear Embedding). Τα πειραματικά αποτελέσματα του αλγορίθμου FEDRA συγκρίνονται με αυτά των υπόλοιπων αλγορίθμων και τελικά διαπιστώνεται ότι ο FEDRA είναι ένας γρήγορος και αποδοτικός αλγόριθμος μείωσης διαστατικότητας. Παράλληλα, ο FEDRA έχει λίγες απαιτήσεις μνήμης και καλή υπολογιστική πολυπλοκότητα συγκριτικά με τους υπόλοιπους αλγορίθμους. Επιπλέον, είναι κατάλληλος για hard προβλήματα μείωσης διαστατικότητας, όπου κάποιοι άλλοι αλγόριθμοι δεν μπορούν να εφαρμοστούν σε τέτοιου είδους προβλήματα. Ο FEDRA επιτυγχάνει να δίνει καλή ποιότητα αποτελεσμάτων συγκρινόμενα με άλλους αλγορίθμους μείωσης διαστατικότητας, καταναλώνοντας λιγότερο χώρο μνήμης και όντας γρηγορότερος. Συμπληρωματικά, ο FEDRA κατορθώνει να χρησιμοποιεί οποιαδήποτε Minkowski απόσταση (p &gt; 1) και όχι μόνο την Ευκλείδεια απόσταση. Επιπρόσθετα, στον αλγόριθμο FEDRA μπορούν να γίνουν επεκτάσεις που θα βελτιώσουν ακόμη περισσότερο την υπολογιστική του πολυπλοκότητα αλλά και τις απαιτήσεις μνήμης συγκριτικά με την υπάρχουσα έκδοσή του αλλά και με άλλους αλγορίθμους μείωσης διαστατικότητας. Αυτές οι επεκτάσεις έχουν την δυνατότητα να βελτιώσουν την ποιότητα προβολής και είναι κατάλληλες για εφαρμογές όπου μπορούν να δείξουν ανοχή σε υψηλότερα κόστη επεξεργασίας.
description: Advances in data collection and storage capabilities during the past decades have led to an information overload in most sciences. Researchers working in domains as diverse as astronomy, biology, economics, and computer science, face larger and larger observations and simulations on a daily basis. Problems of data analysis where the data objects have big number of characteristics become widespread in areas such as analysis of multimedia data and bioinformatics. In such cases is often beneficial the dimensionality reduction of data, so as to improved the efficiency and the precision of data analysis. For this reason were developed Dimensionality Reduction Methods. The reduction of dimensions (Dimensionality Reduction - DR) is a methodology that tries to project a set of vectors in high dimensional space to a lower dimensional space. The objective of the dimensionality reduction methodology is the reduction of dimensions of data with simultaneous maintenance of their attributes. More analytically, the Dimensionality Reduction Techniques project data from the original high dimensional space Rn in a new, lower dimensional space Rk (usually k &lt; 1) and not only the Euclidean distance. Additionally, FEDRA algorithm can have complementary extensions that will improve more the computational complexity and also the memory requirements with these of the existing publication and also with the other algorithms of dimensionality reduction. These extensions of the basic algorithm can increase FEDRA’s quality of results, for applications that can tolerate higher processing costs.