: Εμβύθιση Γράφων με Χρήση Υποκλάσεων στην Κατηγοριοποίηση Δεδομένων:
Creators: name: Μαρωνίδης, Αναστάσιος Γεωργίου
Publisher: name: Aristotle University of Thessaloniki
Year: 2010
Subjects: Μάθηση υποχώρων
Εμβύθιση γράφων
Υποκλασεις
Subspace learning
Graph embedding
Subclass structure

description: Τα τελευταία χρόνια, οι τεχνικές μάθησης υποχώρων (subspace learning techniques), έχουν ευρέως χρησιμοποιηθεί για την αντιμετώπιση του προβλήματος της μείωσης της διάστασης των δεδομένων σε πολλά πραγματικά προβλήματα κατηγοριοποίησης. Η Ανάλυση Πρωτευουσών Συνιστωσών ή Principal Component Analysis (PCA) και η Ανάλυση Γραμμικής Διακριτικής Ικανότητας ή Linear Discriminant Analysis (LDA), είναι δύο από τις πιο γνωστές τεχνικές αυτής της κατηγορίας. Σε αυτήν την κατηγορία τεχνικών, επίσης μεγάλη προσοχή έχουν προσελκύσει μέθοδοι οι οποίες χρησιμοποιούν πληροφορία υποκλάσεων για τον αποδοτικότερο διαχωρισμό των κλάσεων. Η μέθοδος Ανάλυση Διακριτικής Ικανότητας με Χρήση Υποκλάσεων ή Subclass Discriminant Analysis (SDA) και η μέθοδος Ανάλυση Διακριτικής Ικανότητας με Ομαδοποίηση ή Clustering Discriminant Analysis (CDA) είναι δύο από αυτές. Παράλληλα, σπουδαίο έργο έχει γίνει και στον τομέα της Εμβύθισης Γράφων (Graph Embedding). Η Εμβύθιση Γράφων είναι μια γενική προσέγγιση του προβλήματος της μείωσης της διάστασης των δεδομένων με τη βοήθεια της θεωρίας γράφων. Η προσέγγιση αυτή ενοποιεί τους διάφορους αλγορίθμους σε ένα κοινό πλαίσιο. Ένα από τα πλεονεκτήματα αυτής της προσέγγισης είναι ότι μπορεί να χρησιμοποιηθεί ως ένα γενικό εργαλείο στην ανάπτυξη νέων μεθόδων μείωσης της διάστασης. Ένα επιπλέον πλεονέκτημα είναι ότι επιτρέπει την εύκολη ενσωμάτωση των πυρήνων στην αντιμετώπιση προβλημάτων με δεδομένα μη γραμμικά διαχωρίσιμα. Η ενοποίηση ανάμεσα στην Εμβύθιση Γράφων και σε πολλούς αλγορίθμους, με επίβλεψη και χωρίς, έχει ήδη γίνει. Στην παρούσα εργασία, επιδιώκεται μια επέκταση του πλαισίου της Εμβύθισης Γράφων με τρόπο ώστε να ενσωματώσει τη διακριτική πληροφορία που προέρχεται από τις υποκλάσεις. Το αποτέλεσμα αυτής της επιδίωξης είναι το καινοτόμο πλαίσιο που ονομάζεται Εμβύθιση Γράφων με Χρήση Υποκλάσεων ή Subclass Graph Embedding (SGE). Αποδεικνύεται ότι το πλαίσιο αυτό αποτελεί μια γενίκευση της κλασικής Εμβύθισης Γράφων, στην οποία ενσωματώνονται οι τεχνικές SDA και CDA. Η εύρεση των υποκλάσεων εντός ενός συνόλου δεδομένων μπορεί να επιτευχθεί με πολλούς διαφορετικούς τρόπους που συνολικά αναφέρονται με τον όρο τεχνικές ομαδοποίησης. Στην παρούσα εργασία γίνεται χρήση της σχετικά καινούργιας μεθόδου της Φασματικής Ομαδοποίησης (Spectral Clustering). Ο λόγος είναι ότι είναι εύκολα υλοποιήσιμη και παράλληλα ξεπερνά σε αποτελεσματικότητα πολλές κοινές μεθόδους. Πειράματα τα οποία διεξήχθησαν σε διάφορες βάσεις δεδομένων αποδεικνύουν την υπεροχή των τεχνικών που χρησιμοποιούν πληροφορία υποκλάσεων έναντι των κοινών τεχνικών.
description: In recent years, subspace learning techniques have been extensively used as a dimensionality reduction approach in many real-world classification problems. Principal Component Analysis (PCA) and Linear Discriminant Analysis (LDA) are two of the most popular such algorithms. One reason for using subspace learning methods is to achieve efficient results in a computationally easy and fast way. In this category of algorithms, much attention have also attracted methods which use subclass information for the discrimination between the classes. Subclass Discriminant Analysis (SDA) and Clustering Discriminant Analysis (CDA) are two of them. In parallel, great work has been done on Graph Embedding. Graph Embedding is a general graph theoretic approach, which unifies the several subspace learning techniques into a common framework. One of the main advantages of this approach is that it can be used as a general platform for developing new dimensionality reduction methods. Another advantage is that it allows for an easy utilization of kernels for confronting non-linearly separable data. The connection between the graph embedding framework and many algorithms, both unsupervised (PCA, LPP, ISOMAP, LLE etc.) and supervised (LDA) has already been done. In this thesis, an extension of the Graph Embedding approach in order to integrate subclass discriminant information in supervised configuration is attempted. The result is the novel Subclass Graph Embedding (SGE) framework. It is shown that this framework comprises a generalization of the classical Graph Embedding, which also unifies the SDA and CDA methods. The extraction of the clustering structure within a dataset could be achieved by several methods. In this work, a relatively new technique called Spectral Clustering has been employed for this reason. This technique has been proven simple to implement and it usually outperforms other methods for clustering. Experiments that have been conducted in different datasets demonstrate the superiority of the subclass techniques (SDA and CDA) against the standard methods.