Συλλογές
Τίτλος Linear and non linear dimensionality reduction for distributed knowledge discovery
Δημιουργός Magdalinos, Panagis
Συντελεστής Athens University of Economics and Business, Department of Informatics
Vazirgiannis, Michalis
Τύπος Text
Φυσική περιγραφή 142p.
Γλώσσα en
Περίληψη An increasing number of contemporary applications produce massive volumes of very high dimensional data. In scientific databases, for example, it is common to encounter large sets of observations, represented by hundreds or even thousands of coordinates. Unfortunately the rate of data generation and accumulation significantly outperforms our ability to explore and analyze it. Nevertheless, in order to extract knowledge from these datasets, we need to access the underlying, hidden information. However, the size and complexity of these collections makes their processing and analysis impractical or even ineffective [13, 47]. Therefore, scaling up knowledge discovery algorithms for data of both high dimensionality and cardinality has been recently recognized as one of the top-10 problems in data mining research [95].In parallel, the evolution of the internet as well as the emergence of novel applications, such as peer-to-peer systems, has led to an unprecedented distribution of available information. Data is dispersed among network nodes, making the cost of centralizing and subsequent processing prohibitive. Consequently, distributed data mining and distributed knowledge discovery have also emerged as highly challenging tasks[95]. Nevertheless, the vast amount of generated data dictates methods that are fast, exhibit low requirements in terms of computational resources and can be applied to various network setups. Motivated by the previous analysis, this thesis attempts to provide a solution through the definition of efficient and effective dimensionality reduction algorithms. The proposed methods exhibit minor requirements in terms of computational resources without compromising the quality of the produced results; therefore can be exploited in the context of centralized and distributed preprocessing for knowledge discovery. Towards this end,• We introduce FEDRA (Chapter 3, [62, 63]), a dimensionality reduction algorithm which poses minimum time and space requirements and is ideal for large FEDRA is an acronym for A Fast and Efficient Dimensionality Reduction Algorithm datasets of particularly high cardinality and dimensionality.• Inspired by the nature of landmark based dimensionality reduction algorithms(Chapter 2) we introduce the distributed adaptation of FEDRA ([62, 61]) and extend its underlying methodology in order to derive a framework for the decentralization of any landmark based dimensionality reduction algorithm (Chapter 3, Section 3.4)• We propose a distributed non linear dimensionality reduction algorithm, the Distributed Isomap (Chapter 4, [66, 65]) which to the best of our knowledge comprises the first of this kind. Additionally, motivated by recent research results on text-mining ([41, 17, 101, 78, 71]) we propose its application for hard dimensionality reduction problems related with text-mining.• Finally, we introduce X-SDR (Chapter 5, [64]), a prototype that enables the integration and evaluation of any dimensionality reduction algorithm. X-SDRis an open source tool that supports the evaluation of methods through experimentation on artificial and real world datasets thus promoting itself as an ideal candidate platform for research and teaching in academia.
Η πρόοδος της επιστήμης σε διάφορα γνωσιακά πεδία έχει οδηγήσει σε μια πρωτοφανή πληροφοριακή υπερφόρτωση. Οι επιστήμονες καθημερινά έρχονται αντιμέτωποι με αυξανόμενου μεγέθους πειραματικά αποτελέσματα τα οποία καλούνται να ερμηνεύσουν και να αξιολογήσουν. Τα συγκεκριμένα σύνολα παρουσιάζουν μια σειρά από προκλήσεις καθώς κλασσικές μέθοδοι ανάλυσης και αξιολόγησης αποτυγχάνουν στον χειρισμό τους εξαιτίας τόσο των αυξημένων απαιτήσεων σε υπολογιστικούς πόρους όσο και της ύπαρξης μεγάλου αριθμού μεταβλητών που ορίζουν τα δεδομένα (οι διαστάσεις του πειράματος). Ως εκ τούτου, η ποιότητα των αποτελεσμάτων πολλών διαδικασιών εξόρυξης γνώσης επιδεινώνεται σημαντικά [12,45]. Συνεπώς, η δημιουργία αλγορίθμων προεπεξεργασίας δεδομένων που επιτρέπουν την μετέπειτα επιτυχή εκτέλεση διαδικασιών μάθησης και εξόρυξης γνώσης αναγνωρίζεται ως ένα από τα 10 σημαντικότερα προβλήματα του συγκεκριμένου ερευνητικού χώρου [93]. Παράλληλα η εξέλιξη του διαδικτύου αλλά και η εμφάνιση καινοτόμων κατανεμημένων εφαρμογών όπως τα δίκτυα ομότιμων κόμβων είχαν σαν αποτέλεσμα την κατανομή της διαθέσιμης πληροφορίας. Τα δεδομένα είναι πλέον διεσπαρμένα σε ένα σύνολο κόμβων και το κόστος της συνάθροισης τους καθώς και της κεντρικής επεξεργασίας τους είναι απαγορευτικό. Αυτό έχει σαν αποτέλεσμα ο ερευνητικός χώρος της κατανεμημένη εξόρυξη γνώσης να αποκτήσει μεγάλη σημασία [93]. Προφανώς, ο μεγάλος όγκος πληροφορίας καθώς και η διασπορά της επιβάλλουν τον ορισμό μεθόδων με μικρές υπολογιστικές απαιτήσεις ενώ παράλληλα οι αλγόριθμοι αυτοί θα πρέπει να είναι εφαρμόσιμοι σε μια πληθώρα περιστάσεων,ακόμα και σε δίκτυα ομότιμων κόμβων. Με αφορμή την παραπάνω ανάλυση, στα πλαίσια της συγκεκριμένης διδακτορικής διατριβής γίνεται προσπάθεια επίλυσης των παραπάνω προβλημάτων μέσω του ορισμού μεθόδων μείωσης διάστασης που χαρακτηρίζονται από μικρές απαιτήσεις χώρου και χρόνου ενώπαράλληλα μπορούν να εφαρμοστούν ακόμα και σε κατανεμημένα περιβάλλοντα όπως αυτά των δικτύων ομότιμων κόμβων. Οι αλγόριθμοι αυτοί έχουν σαν στόχο την προ-επεξεργασία των δεδομένων που χρησιμοποιούνται για την εξόρυξη γνώσης. Οι καινοτομίες της συγκεκριμένης διδακτορικής διατριβής συνοψίζονται στην παρακάτω λίστα: • Προτείνεται ένας νέος αλγόριθμος μείωσης διάστασης, ο FEDRA (Κεφάλαιο 3, [60, 61]), με κύριο χαρακτηριστικό τις μειωμένες απαιτήσεις σε μνήμη και υπολογιστική ισχύ, δύο χαρακτηριστικά που τον προκρίνουν σαν ιδανική λύση για πολυπληθή και πολυδιάστατα σύνολα δεδομένων. • Χρησιμοποιώντας ως βάση τα εγγενή χαρακτηριστικά των μεθόδων μείωσης διάστασης με χρήση σημείων αναφοράς (Κεφάλαιο 2) ορίζεται η κατανεμημένη εκδοχή του αλγορίθμου FEDRA ([60, 59]) ενώ επεκτείνεται η μεθοδολογία ώστε να ορίσει ένα συνολικό πλαίσιο για την κατανεμημένη εφαρμογή αλγορίθμων μείωσης διάστασης που κάνουν χρήση σημείων αναφοράς (Κεφάλαιο 3, παράγραφος 3.4). • Προτείνεται ένα νέος αλγόριθμος κατανεμημένης, μη γραμμικής μείωσης διάστασης, ο D-Isomap (Κεφάλαιο 4, [63, 64]) ο οποίος αποτελεί τον πρώτο αλγόριθμο της συγκεκριμένης κατηγορίας. Επιπροσθέτως, ακολουθώντας τα τελευταία ερευνητικά αποτελέσματα της εξόρυξης γνώσης από συλλογές κειμένων [39, 16, 99, 76, 69], προτείνεται η εφαρμογή του D-Isomap στην κατανεμημένη εξόρυξη γνώσης από συλλογές κειμένων • Τέλος παρουσιάζεται το εργαλείο X-SDR (Κεφάλαιο 5, [62]). Το X-SDR αποτελεί ένα πρωτότυπο εργαλείο για πειραματική αποτίμηση κεντρικών και κατανεμημένων μεθόδων μείωσης διάστασης μέσω της εφαρμογής τους σε πραγματικά και τεχνητά σύνολα δεδομένων. Η ευχρηστία του καθώς και η επεκτασιμότητα του το καθιστούν ιδανικά για ερευνητική και διδακτική χρήση.
Λέξη κλειδί Fast and Efficient Dimensionality Reduction Algorithm (FEDRA)
eXtensible Suite for Dimensionality Reduction (X-SDR)
Non Linear Dimensionality Reduction
Ημερομηνία 31-05-2010
Άδεια χρήσης https://creativecommons.org/licenses/by/4.0/