Please use this identifier to cite or link to this item: http://hdl.handle.net/10889/2001
Title: Ομαδοποίηση δεδομένων υψηλής διάστασης
Authors: Τασουλής, Σωτήρης
Issue Date: 2009-10-09T10:33:21Z
Keywords: Ομαδοποίηση
Διάσπαση ιδιάζουσων τιμών
Αναγνώριση προτύπων
Ανάλυση πρωτευουσών συνιστωσών
Keywords (translated): Clustering
Singular value decomposition
Pattern recognition
Principal component analysis
Abstract: Η ομαδοποίηση ομαδοποιεί τα δεδομένα βασισμένη μόνο σε πληροφορία που βρίσκεται σε αυτά η οποία περιγράφει τα αντικείμενα και τις σχέσεις τους. Ο στόχος είναι τα αντικείμενα που βρίσκονται σε μια ομάδα να είναι όμοια(ή σχετικά) μεταξύ τους και διαφορετικά απο τα αντικείμενα των άλλων ομάδων. Όσο μεγαλύτερη είναι η ομοιότητα(ή η ομοιογένεια) σε μια ομάδα και όσο μεγαλύτερη είναι η διαφορετικότητα ανάμεσα στις ομάδες τόσο καλύτερη είναι η ομαδοποίηση. Οι μεθόδοι ομαδοποίησης μπορούν να διακριθούν σε τρείς κατηγορίες, ιεραρχικές, διαχωριστικές, και στις βασισμένες στη πυκνότητα. Οι ιεραρχικοί αλγόριθμοι μας δίνουν ιεραρχίες ομάδων σε μία top-down(συγχωνευτική) ή bottom-up(διαχωριστική) μορφή. Η εργασία αυτή επικεντρώνεται στην ιεραρχική διαχωριστική ομαδοποίηση. Ανάμεσα στους ιεραρχικούς διαχωριστικούς αλγορίθμους ξεχωρίζουμε τον αλγόριθμο Principal Direction Divisive Partitioning (PDDP). Ο PDDP χρησιμοποιεί την προβολή των δεδομένων στα κύρια συστατικά της αντίστοιχης μήτρας συνδιασποράς. Αυτό επιτρέπει την εφαρμογή σε δεδομένα υψηλής διάστασης. Στην εργασία αυτή προτείνεται μια βελτίωση του αλγορίθμου \Principal Direction Divisive Partitioning. Ο προτεινόμενος αλγόριθμος συνδυάζει στοιχεία από την εκτίμηση πυκνότητας και τις μεθόδους βασισμένες στην προβολή με έναν γρήγορο και αποδοτικό αλγόριθμο, ικανό να αντιμετωπίσει δεδομένα υψηλής διάστασης. Τα πειραματικά αποτελέσματα δείχνουν βελτιωμένη απόδοση ομαδοποίησης σε σύγκριση με άλλες δημοφιλείς μεθόδους. Επίσης ερευνάται το πρόβλημα του αυτόματου καθορισμού του πλήθους των ομάδων που είναι πολύ σημαντικό την ανάλυση ομάδων.
Abstract (translated): Cluster analysis groups data objects based only on information found in the data that describes the objects and their relationships. The goal is that the objects within a group be similar (or related) to one another and different from (or unrelated to) the objects in other groups. The greater the similarity (or homogeneity) within a group and the greater the difference between groups, the better or more distinct the clustering. Clustering methods can be broadly divided into three categories, hierarchical, partitioning and density-based (while there are other categorisations). Hierarchical algorithms provide nested hierarchies of clusters in a top-down (agglomerative), or bottom-up (divisive) fashion. This work is focused on the class of hierarchical divisive clustering algorithms. Amongst the class of divisive hierarchical algorithms, the Principal Direction Divisive Partitioning (PDDP) algorithm is of particular value. PDDP uses the projection of the data onto the principal components of the associated data covariance matrix. This allows the application to high dimensional data. In this work an improvement of the algorithm PDDP is proposed. The proposed algorithm merges concepts from density estimation and projection-based methods towards a fast and efficient clustering algorithm, capable of dealing with high dimensional data. Experimental results show improved partitioning performance compared to other popular methods. Moreover, we explore the problem of automatically determining the number of clusters that is central in cluster analysis.
Appears in Collections:Τμήμα Μαθηματικών (ΜΔΕ)

Files in This Item:
File Description SizeFormat 
S_Tasoulis_2009.pdf544.06 kBAdobe PDFView/Open


This item is licensed under a Creative Commons License Creative Commons