Ομαδοποίηση βιολογικών δεδομένων

Ένας απλός ορισμός για την ομαδοποίηση ή συσταδοποίηση (clustering): "Ομαδοποίηση ονομάζεται η διαδικασία που οργανώνει πρότυπα (παρατηρήσεις, δεδομένα ή διανύσματα) σε ομάδες (συστάδες-clusters), όπου τα μέλη μιας ομάδας είναι παρόμοια μεταξύ τους σύμφωνα με κάποιο κριτήριο".

Βασίζεται σε δύο αρχές: (1) ομοιογένεια (δηλ. στοιχεία εντός της ίδιας ομάδας είναι παρόμοια μεταξύ τους) και (2) διαχωρισμό (δηλ. στοιχεία σε διαφορετικές συστάδες είναι διαφορετικά μεταξύ τους).

Λόγω της ευελιξίας της, η ομαδοποίηση εφαρμόζεται σε όλους σχεδόν τους επιστημονικούς τομείς, όπως στη Βιολογία, την Ιατρική, τη Μηχανική Μάθηση, την Οικονομία, το Μάρκετινγκ, την Αστρονομία, την Αρχαιολογία και πολλά άλλα.

Η ομαδοποίηση είναι μάθηση χωρίς επίβλεψη, η οποία ξεκινά από μια βάση δεδομένων που αποτελείται από δεδομένα εκπαίδευσης και στόχος είναι να χωριστούν τα στοιχεία εκπαίδευσης σε ομάδες. Έχουν αναπτυχθεί διάφοροι αλγόριθμοι ομαδοποίησης για τη συγκέντρωση διαφορετικών τύπων δεδομένων που παράγονται από διαφορετικές πηγές. Για το ίδιο σύνολο δεδομένων, διαφορετικοί αλγόριθμοι ομαδοποίησης θα δώσουν διαφορετικά αποτελέσματα. Δεν υπάρχει ένα μόνο εργαλείο το οποίο να μπορεί να δώσει την καλύτερη ομαδοποίηση για ένα συγκεκριμένο σύνολο δεδομένων.

## Ορισμός
Ο ορισμός διαφέρει από πρόβλημα σε πρόβλημα και εξαρτάται από τον επιθυμητό στόχο και τις ιδιότητες των δεδομένων. Παρά τη δυσκολία αυτή, εξακολουθούν να υπάρχουν ορισμένοι ορισμοί λειτουργίας ή εργασίας. Για παράδειγμα, έχουμε τα εξής.

1) Μία ομάδα είναι ένα σύνολο δεδομένων που είναι παρόμοια μεταξύ τους, ενώ τα δεδομένα σε διαφορετικές ομάδες είναι διαφορετικά μεταξύ τους.

2) Μία ομάδα είναι ένα σύνολο δεδομένων έτσι ώστε η απόσταση μεταξύ ενός δεδομένου σε ένα σύμπλεγμα και του κεντροειδούς του συμπλέγματος να είναι μικρότερη από την απόσταση μεταξύ αυτών των δεδομένων και των κεντροειδών οποιωνδήποτε άλλων συστάδων.

3) Μία ομάδα είναι ένα σύνολο δεδομένων, έτσι ώστε η απόσταση μεταξύ οποιωνδήποτε δύο δεδομένων στο σύμπλεγμα να είναι μικρότερη από την απόσταση μεταξύ οποιουδήποτε δεδομένου στο σύμπλεγμα και οποιουδήποτε δεδομένου που δεν βρίσκεται μέσα σε αυτό.

4) Μία ομάδα είναι μία συνεχής περιοχή δεδομένων με μια σχετικώς υψηλή πυκνότητα, η οποία διαχωρίζεται από άλλες τέτοιες πυκνές περιοχές.

Η διαδικασία ομαδοποίησης μπορεί να οδηγήσει σε διαφορετική κατανομή ενός συνόλου δεδομένων, ανάλογα με το συγκεκριμένο κριτήριο που χρησιμοποιείται για την ομαδοποίηση. Επομένως, υπάρχει ανάγκη για προ-επεξεργασία, πριν από την εκτέλεση και τη συσσώρευση εργασιών σε ένα σύνολο δεδομένων. Τα βασικά βήματα για την ανάπτυξη της διαδικασίας ομαδοποίησης μπορούν να συνοψιστούν ως εξής:

• Επιλογή χαρακτηριστικών. Ο στόχος είναι να επιλεγούν σωστά οι λειτουργίες στις οποίες πραγματοποιείται η ομαδοποίηση, ώστε να κωδικοποιεί όσο το δυνατόν περισσότερες πληροφορίες σχετικά με το αποτέλεσμα του ενδιαφέροντος. Επομένως, η προ-επεξεργασία των δεδομένων μπορεί να είναι απαραίτητη πριν από τη χρήση τους.

• Αλγόριθμος ομαδοποίησης. Αυτό το βήμα αναφέρεται στην επιλογή ενός αλγορίθμου που έχει ως αποτέλεσμα τον ορισμό ενός καλού συστήματος ομαδοποίησης για ένα σύνολο δεδομένων. Ένα μέτρο εγγύτητας και ένα κριτήριο ομαδοποίησης χαρακτηρίζουν κυρίως έναν αλγόριθμο ομαδοποίησης καθώς και την αποτελεσματικότητά του.

i.Το μέτρο εγγύτητας είναι ένα μέτρο που προσδιορίζει πόσο "όμοια" είναι δύο σημεία δεδομένων (δηλ. στις περισσότερες περιπτώσεις πρέπει να βεβαιωθούμε ότι όλα τα επιλεγμένα κριτήρια συμβάλλουν εξίσου στον υπολογισμό του μέτρου εγγύτητα).

ii. Κριτήριο ομαδοποίησης. Σε αυτό το στάδιο, πρέπει να οριστεί το κριτήριο της ομαδοποίησης, το οποίο μπορεί να εκφραστεί μέσω μιας συνάρτησης κόστους ή κάποιου άλλου είδους κανόνων. Πρέπει να υπογραμμιστεί ότι σε αυτό το στάδιο λαμβάνεται υπόψιν ο τύπος των δεδομένων που αναμένεται να αναλυθούν. Έτσι, μπορούμε να ορίσουμε ένα "καλό" κριτήριο ομαδοποίησης, οδηγώντας σε ένα διαχωρισμό που ικανοποιεί το σύνολο δεδομένων.

• Επικύρωση των αποτελεσμάτων. Η ορθότητα των αποτελεσμάτων των αλγορίθμων ομαδοποίησης ελέγχεται χρησιμοποιώντας κατάλληλα κριτήρια και τεχνικές. Ανεξάρτητα από τις μεθόδους ομαδοποίησης, η τελική κατάτμηση των δεδομένων απαιτεί κάποιο είδος αξιολόγησης στις περισσότερες εφαρμογές.

• Ερμηνεία των αποτελεσμάτων. Σε πολλές περιπτώσεις, οι εμπειρογνώμονες στον τομέα της εφαρμογής πρέπει να ενσωματώσουν τα αποτελέσματα ομαδοποίησης με άλλα πειραματικά στοιχεία και αναλύσεις, προκειμένου να βγάλουν το σωστό συμπέρασμα.

## Τεχνικές Ομαδοποίησης - Αλγόριθμοι
Το σημαντικότερο στάδιο σε όλη τη διαδικασία ομαδοποίησης αποτελεί η επιλογή του κατάλληλου μοντέλου. Κάθε μοντέλο ομαδοποίησης δεδομένων στηρίζεται σ΄ έναν αλγόριθμο. Υπάρχει πληθώρα αλγορίθμων που δίνουν αποτελέσματα είτε αυστηρά είτε ασαφή και στη συνέχεια θα γίνει αναφορά σε ορισμένες βασικές κατηγορίες αλγορίθμων, με τους ιεραρχικούς και διαχωριστικούς να είναι οι πιο συχνά χρησιμοποιούμενοι. Η επιλογή της τεχνικής εξαρτάται από τη μορφή των δεδομένων που προορίζονται για επεξεργασία αλλά και από τον ίδιο τον χρήστη.

### Ιεραρχική Ομαδοποίηση (Hierarchical Clustering)
Σε αυτή την τεχνική ομαδοποίησης τα δεδομένα ιεραρχούνται και τα αποτελέσματα δίνονται με τη μορφή δενδρογράμματος, μέσω του οποίου φαίνεται το μέγεθος και ο αριθμός των ομάδων που δημιουργούνται. Οι αλγόριθμοι συνδέουν αντικείμενα και σχηματίζουν συστάδες, βασιζόμενοι στην απόσταση τους. Η Ιεραρχική Ομαδοποίηση μπορεί να είναι απλού, μέσου ή ολοκληρωμένου συνδέσμου.

Στην Ομαδοποίηση απλού συνδέσμου (single-linkage) για τη δημιουργία μιας νέας ομάδας αναζητείται η μικρότερη απόσταση που μπορεί να έχει ένα ζεύγος στοιχείων από δύο ομάδες σε σχέση με όλα τα υπόλοιπα δυνατά ζεύγη στοιχείων από το σύνολο των ομάδων. Στην Ιεραρχική Ομαδοποίηση μέσου συνδέσμου (average-linkage) για την συγχώνευση συστάδων λαμβάνεται υπόψη η μέση απόσταση μεταξύ όλων των ζευγών στοιχείων ανάμεσα σε δύο ομάδες και επιλέγεται η μικρότερη μέση απόσταση.

Τέλος, στην περίπτωση του ολοκληρωμένου συνδέσμου (complete-linkage), υπολογίζεται η μεγαλύτερη απόσταση που μπορεί να έχει ένα ζεύγος στοιχείων μεταξύ δύο ομάδων συγκριτικά με τα υπόλοιπα πιθανά ζεύγη στοιχείων και έτσι σχηματίζονται οι ομάδες .

Οι Ιεραρχικοί Αλγόριθμοι χωρίζονται σε δύο υποκατηγορίες, τους Συσσωρευτικούς και τους Διαιρετικούς. Στους Συσσωρευτικούς κάθε σημείο θεωρείται μια ξεχωριστή ομάδα από μόνο του, η οποία περιέχει μόνο το σημείο αυτό. Στη συνέχεια γίνονται συγχωνεύσεις των ομάδων μέχρις ότου καταλήξουν όλες να ανήκουν σε μία κοινή συστάδα που περιέχει το σύνολο των σημείων (bottom-up).  Στους Διαιρετικούς αντίθετα, υπάρχει αρχικά μια ομάδα που περιέχει όλα τα στοιχεία, η οποία και διαιρείται σε μικρότερες μέχρι να προκύψουν ομάδες με ένα μόνο στοιχείο η καθεμία (top-down).

## Ιεραρχική Συσσωρευτική Ομαδοποίηση (Hierarchical Agglomerative Clustering - HAC)

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

1.     Αρχικά κάθε σημείο θεωρείται μία ομάδα, δηλαδή σε ένα σύνολο Χ σημείων υπάρχουν Χ ομάδες.

2.     Έπειτα υπολογίζονται οι αποστάσεις μεταξύ των ομάδων. Όταν βρεθεί το ζευγάρι στοιχείων με τη μικρότερη απόσταση σε σχέση με τις υπόλοιπες ομάδες συγχωνεύεται σε μία. Οι ομάδες πλέον είναι κατά 1 λιγότερες.

3.     Υπολογίζονται εκ νέου οι αποστάσεις και το 2ο βήμα επαναλαμβάνεται έως ότου και τα Χ σημεία να τοποθετηθούν σε μία και μοναδική ομάδα. Με αυτόν τον τρόπο σχεδιάζεται και το αντίστοιχο δένδρο.

Σε ένα δενδρόγραμμα ο άξονας Υ υποδεικνύει την απόσταση με την οποία συγχωνεύονται οι συστάδες και στον άξονα Χ αποτυπώνεται το πλήθος των συστάδων.

### Διαχωριστική Ομαδοποίηση (Partitional clustering)
Στη Διαχωριστική τεχνική Ομαδοποίησης ορίζεται εξαρχής συγκεκριμένος αριθμός ομάδων και τα δεδομένα χωρίζονται με βάση τις υπάρχουσες αυτές ομάδες. Σε δεύτερο στάδιο επαναπροσδιορίζονται αυτές οι αναθέσεις των στοιχείων και το αποτέλεσμα βελτιστοποιείται καθώς τρέχει ο αλγόριθμος μέχρι να εκπληρωθεί κάποιο κριτήριο τερματισμού. Βασική κατηγορία αλγορίθμων που απαντώνται σε αυτή την τεχνική είναι αλγόριθμοι που χρησιμοποιούν σαν κριτήριο το κέντρο μάζας της εκάστοτε ομάδας για την αναπαράστασή της. Η κάθε συστάδα επομένως αποδίδεται με ένα κεντρικό διάνυσμα.

Για τον προσδιορισμό του κέντρου χρησιμοποιούνται είτε αλγόριθμοι απλού περάσματος είτε τετραγωνικού σφάλματος.  Με τον αλγόριθμο απλού περάσματος ομαδοποιείται το σύνολο των δεδομένων με ένα μόνο πέρασμα. Ο αριθμός των ομάδων, όπως προαναφέρθηκε, έχει οριστεί από τον χρήστη. Το πρώτο στοιχείο γίνεται κέντρο μάζας της πρώτης ομάδας. Για τα επόμενα στοιχεία υπολογίζονται οι αποστάσεις από τα κέντρα μάζας όσων ομάδων υπάρχουν και αποθηκεύονται μόνο οι μικρότερες, μία για κάθε στοιχείο. Έστω λοιπόν di η ελάχιστη απόσταση του στοιχείου i από το κοντινότερη ομάδα. Έχοντας θέσει μια τιμή κατωφλίου, αν di 

Κατηγορία:Βιοπληροφορική