Knowledge discovery in high dimensional data

Abstract

While data clustering has a long history and a large amount of research has been devoted to the development of numerous clustering techniques, significant challenges still remain. One of the most important of them is associated with high data dimensionality. A particular class of clustering algorithms has been very successful in dealing with such datasets, utilizing information driven by dimensionality reduction techniques. Projection methods for dimension reduction have enabled the discovery of otherwise unattainable structure in ultra high dimensional data. In this thesis, we try to deepen our understanding on what can be achieved by this kind of approaches in an attempt to theoretically discover the relationship between true clusters in the data and the distribution of their projection. Based on such findings, we propose a series of new hierarchical divisive clustering algorithms. The proposed algorithms require minimal user-defined parameters and have the desirable feature of being able to provide approximations for the number of clusters present in the data. The experimental results indicate that the proposed techniques are effective in simulated data scenarios and as well in real world problems that are affected by high dimensionality.

Ενώ η ομαδοποίηση δεδομένων έχει μια μακρά ιστορία και ένα μεγάλο κομμάτι της έρευνας έχει αφιερωθεί στην ανάπτυξη πολυάριθμων μεθόδων ομαδοποίησης, σημαντικές προκλήσεις παραμένουν ακόμα. Μία από τις πιο σημαντικές σχετίζεται με τη μεγάλη διάσταση των δεδομένων. Μία συγκεκριμένη κατηγορία αλγορίθμων ομαδοποίησης αντιμετωπίζει τέτοιου τύπου δεδομένα με μεγάλη επιτυχία χρησιμοποιώντας τεχνικές μείωσης της διάστασης. Οι μέθοδοι προβολών για την μείωση διάστασης μας έδωσαν τη δυνατότητα να ανακαλύψουμε τη δομή των δεδομένων εξαιρετικά μεγάλης διάστασης. Σε αυτή τη διατριβή, γίνεται μία προσπάθεια να εμβαθύνουμε την κατανόηση μας σχετικά με το τι μπορεί να επιτευχθεί από αυτού του είδους τις τεχνικές σε μία προσπάθεια να ανακαλύψουμε θεωρητικά τη σχέση των ομάδων στα δεδομένα και την κατανομή των προβολών τους. Βασισμένοι στα ευρήματα μας προτείνουμε μία σειρά από διαχωριστικούς ιεραρχικούς αλγορίθμους ομαδοποίησης. Οι προτεινόμενοι αλγόριθμοι απαιτούν ελάχιστες παραμέτρους εισόδου και επίσης έχουν την δυνατότητα να εκτιμούν το πλήθος των ομάδων στα δεδομένα. Τα πειραματικά αποτελέσματα δείχνουν ότι οι προτεινόμενες τεχνικές είναι αποτελεσματικές σε τεχνητά δεδομένα αλλά και σε πραγματικές εφαρμογές που χαρακτηρίζονται από πολύ μεγάλη διάσταση.