| Περίληψη : | Η ομαδοποίηση δεδομένων (clustering) είναι μία καλά θεμελιωμένη μέθοδος ανάλυσης δεδομένων με εφαρμογές σε πολλούς τομείς, όπως η αναγνώριση μοτίβων και η ανάλυση εικόνας. Η πλειοψηφία των αλγορίθμων ομαδοποίησης που έχουν αναπτυχθεί πραγματοποιούν επεξεργασία κατά δέσμες (batch processing), όπου πριν την ενημέρωση των παραμέτρων κάθε φορά λαμβάνεται υπόψιν ολόκληρο το σύνολο δεδομένων. Ωστόσο, στη σημερινή εποχή, η ύπαρξη μεγάλου όγκου δεδομένων απαιτεί την ανάπτυξη αλγορίθμων ομαδοποίησης που θα μπορούν να επεξεργάζονται αποδοτικά τέτοια σύνολα δεδομένων σε αποδεκτό χρόνο. Μία κατηγορία τέτοιων αποδοτικών αλγορίθμων είναι αυτοί που πραγματοποιούν online επεξεργασία, όπου η ενημέρωση των παραμέτρων κάθε φορά βασίζεται σε ένα μόνο τυχαία επιλεγμένο δεδομένο. Ενώ έχουν προταθεί διάφοροι online αλγόριθμοι στις περισσότερες οικογένειες αλγορίθμων ομαδοποίησης, δεν έχει γίνει ακόμα εκτενής έρευνα πάνω σε online αλγορίθμους ομαδοποίησης κατά ενδεχόμενα (possibilistic clustering algorithms). Η παρούσα εργασία συμβάλλει ερευνητικά στην περιοχή αυτή, προτείνοντας δύο αλγορίθμους που ανήκουν στην τελευταία κατηγορία. Ο πρώτος (O-PCM2) είναι ένας στοχαστικός αλγόριθμος απότομης κατάδυσης (stochastic gradient descent), ενώ ο δεύτερος (Ο-PCM2 v2) προκύπτει από τον αντίστοιχο αλγόριθμο ομαδοποίησης που πραγματοποιεί επεξεργασία κατά δέσμες, γράφοντας την εξίσωση των παραμέτρων του τελευταίου σε αναδρομική μορφή. Οι αλγόριθμοι αυτοί παρουσιάζονται λεπτομερώς και για τον O-PCM2 αποδεικνύεται ένα θεώρημα σύγκλισης, με βάση τα γενικά αποτελέσματα σύγκλισης που ισχύουν για τους στοχαστικούς αλγορίθμους απότομης κατάδυσης. Τέλος, η αποτελεσματικότητά τους εξετάζεται μέσω πειραμάτων πάνω σε προσομοιωμένα και πραγματικά δεδομένα. Μεταξύ άλλων, αναδεικνύεται η ικανότητα του O-PCM2 να αντιμετωπίσει επιτυχώς περιπτώσεις δεδομένων υψηλής διάστασης και περιπτώσεις δυναμικά μεταβαλλόμενου περιβάλλοντος. Στα πειράματα αυτά, οι προτεινόμενοι αλγόριθμοι συγκρίνονται με τον αντίστοιχο αλγόριθμο ομαδοποίησης κατά ενδεχόμενα που πραγματοποιεί επεξεργασία κατά δέσμες, καθώς και με τον αλγόριθμο online k-means. Γενικά, τα πειραματικά αποτελέσματα που παρουσιάζονται για τους προτεινόμενους αλγορίθμους είναι πολύ ενθαρρυντικά, ειδικά στην περίπτωση που δεν υπάρχει σημαντική επικάλυψη ανάμεσα στις ομάδες που σχηματίζουν τα δεδομένα.
Clustering is a well-established data analysis method that has been widely used in various fields, such as pattern recognition and image analysis. Nowadays, the accumulation of huge amounts of data in a wide range of applications makes most of the existing batch clustering algorithms inadequate for efficient processing. Thus, the need for new efficient algorithms inevitably arises. One such category of algorithms is that of the online clustering algorithms, which can process big data without demanding prohibitively high computational cost, since the update of the parameters each time is only based on one randomly chosen datapoint. While various online algorithms have been introduced in many categories of clustering algorithms, this is not the case with the possibilistic clustering algorithms. This Thesis contributes to this field of research by introducing two novel online possibilistic clustering algorithms. The first one, called O-PCM2 is a stochastic gradient descent algorithm, while the other, called O-PCM2 v2, results from its associated batch possibilistic algorithm, by writing the parameter updating equation of the latter in recursive form. The algorithms are presented in detail and a convergence proof of O-PCM2 is provided, based on the general convergence results established for the family of the stochastic gradient descent algorithms. Finally, the effectiveness of the proposed algorithms is assessed through extensive experimentation on both simulated and real data sets. In addition, the ability of O-PCM2 to deal with high-dimensionality data sets as well as its ability to work (in principle) in a dynamically changing environment have also been shown through relative experiments. Their performance is also compared to other relative algorithms, namely, their batch possibilistic counterpart and the online k-means algorithm. In general, the experimental results for the proposed algorithms are very encouraging especially for cases where the clusters do not exhibit significant degree of overlap.
|
|---|
Copyright © 2013 Βιβλιοθήκη Ο.Π.Α. Με την επιφύλαξη παντός δικαιώματος.