Βικιπαίδεια

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

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

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

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

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

Ορισμός Επεξεργασία

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

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

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

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

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

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

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

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

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

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

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

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

Τεχνικές Ομαδοποίησης - Αλγόριθμοι Επεξεργασία

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

Ιεραρχική Ομαδοποίηση (Hierarchical Clustering) Επεξεργασία

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

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

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

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


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

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

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

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

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

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

Διαχωριστική Ομαδοποίηση (Partitional clustering) Επεξεργασία

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

Για τον προσδιορισμό του κέντρου χρησιμοποιούνται είτε αλγόριθμοι απλού περάσματος είτε τετραγωνικού σφάλματος. Με τον αλγόριθμο απλού περάσματος ομαδοποιείται το σύνολο των δεδομένων με ένα μόνο πέρασμα. Ο αριθμός των ομάδων, όπως προαναφέρθηκε, έχει οριστεί από τον χρήστη. Το πρώτο στοιχείο γίνεται κέντρο μάζας της πρώτης ομάδας. Για τα επόμενα στοιχεία υπολογίζονται οι αποστάσεις από τα κέντρα μάζας όσων ομάδων υπάρχουν και αποθηκεύονται μόνο οι μικρότερες, μία για κάθε στοιχείο. Έστω λοιπόν di η ελάχιστη απόσταση του στοιχείου i από το κοντινότερη ομάδα. Έχοντας θέσει μια τιμή κατωφλίου, αν di < dκατωφλίου τότε το στοιχείο i ανατίθεται στην ομάδα αυτή, αν όμως είναι μεγαλύτερη τότε το στοιχείο αυτό γίνεται κέντρο μάζας μιας νέας ομάδας. Ο αλγόριθμος τερματίζει όταν ομαδοποιηθούν όλα τα στοιχεία. Στη δεύτερη περίπτωση χρησιμοποιείται ως κριτήριο η τιμή της εξίσωσης του τετραγωνικού σφάλματος. Αρχικά επιλέγονται τα στοιχεία που θα εκπροσωπούν τις ομάδες που έχουν οριστεί. Τα υπόλοιπα στοιχεία εναποτίθενται στις πλησιέστερες ομάδες. Επαναπροσδιορίζονται τα κέντρα των ομάδων και αυτή η διαδικασία επαναλαμβάνεται έως ότου η τιμή του τετραγωνικού σφάλματος για κάθε στοιχείο να είναι σταθερή και να μην παρατηρείται καμία αλλαγή στα κέντρα των ομάδων ή στις αναθέσεις[6].


Ομαδοποίηση k-μέσων (k-means clustering) Επεξεργασία

Ο Αλγόριθμος k-μέσων αποτελεί το πιο χαρακτηριστικό παράδειγμα αλγορίθμων τετραγωνικού σφάλματος[7]. Η διαδικασία που ακολουθεί αποτελείται από τα παρακάτω στάδια :

1. Σε ένα σύνολο δεδομένων πλήθους Ν επιλέγουμε έναν αριθμό ομάδων (k) για να χρησιμοποιήσουμε και γίνεται τυχαία αρχικοποίηση των κεντρικών σημείων τους. Για τον προσδιορισμό του αριθμού των συστάδων προτείνεται μια γρήγορη μελέτη των δεδομένων για την εύρεση τυχόν διακριτών ομάδων. Τα κεντρικά σημεία των ομάδων αναπαρίστανται με διανύσματα όπως και κάθε άλλο σημείο από τα δεδομένα.

2. Γίνεται ανάθεση των λοιπών στοιχείων υπολογίζοντας τις αποστάσεις τους από τα κέντρα των ομάδων. Το κάθε στοιχείο κατηγοριοποιείται στη συστάδα με την οποία εμφανίζει την ελάχιστη δυνατή απόσταση.

3. Έχοντας ταξινομήσει πλέον το σύνολο των στοιχείων, υπολογίζουμε ξανά το κέντρο κάθε ομάδας κάνοντας χρήση του μέσου όλων των διανυσμάτων της ομάδας.

4. Τα βήματα 2 και 3 εκτελούνται για ορισμένο αριθμό επαναλήψεων ή μέχρι να μην παρατηρείται κάποια αλλαγή μεταξύ των επαναλήψεων.

Αλγόριθμος Ομαδοποίησης του Μαρκόφ (Markov Cluster Algorithm – MCL Algorithm) Επεξεργασία

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

Ο MCL αλγόριθμος προσομοιώνει τη ροή σε ένα δίκτυο (flow simulation) υπολογίζοντας διαδοχικές δυνάμεις του πίνακα γειτνίασης του δικτύου (adjacency matrix). Σε κάθε επανάληψη εκτελείται ένα βήμα εκτόνωσης (expansion) που συνοδεύεται από ένα βήμα εμφύσησης (inflation) ώστε να αυξηθεί η αντίθεση μεταξύ των περιοχών ισχυρής ροής και αδύναμης. Το αποτέλεσμα αυτής της διαδικασίας είναι ο διαχωρισμός των περιοχών έντονης ροής, δηλαδή των συστάδων, από τις περιοχές μηδενικής ροής. Η απόδοση του αλγορίθμου και ο αριθμός των ομάδων που προκύπτουν εξαρτώνται σημαντικά από την παράμετρο της εμφύσησης (inflation parameter).

Ασαφής Ομαδοποίηση (Fuzzy Clustering) Επεξεργασία

Η διαφορά αυτής της τεχνικής ομαδοποίησης με την κλασική αυστηρή ομαδοποίηση δεδομένων έγκειται στο ότι κάθε σημείο μπορεί να ανήκει σε όλες τις ομάδες μέχρι κάποιο βαθμό. Στις προηγούμενες περιπτώσεις τα διάφορα στοιχεία κατανέμονταν σε ομάδες βάσει ορισμένων κριτηρίων. Στην ασαφή ομαδοποίηση ένα στοιχείο μπορεί να ανήκει ταυτόχρονα σε δύο ή και παραπάνω ομάδες. Συγκεκριμένα, ορίζεται για το καθένα μια συνάρτηση συμμετοχής η οποία και αποτυπώνει το βαθμό συμμετοχής του στοιχείου σε κάθε ομάδα. Οι τιμές κυμαίνονται από το μηδέν έως το ένα. Όταν ο βαθμός τείνει στο μηδέν υπάρχουν αμφιβολίες για τη συμμετοχή του στοιχείου στη συγκεκριμένη συστάδα ενώ όταν τείνει στη μονάδα η συμμετοχή είναι σίγουρη. Στην περίπτωση που όλα τα στοιχεία μιας ομάδας παρουσιάζουν βαθμό συμμετοχής ένα, η ομάδα δεν έχει ασαφή χαρακτήρα αλλά αυστηρό. Επομένως, η διαφορά της κλασικής ομαδοποίησης από την ασαφή είναι ότι η πρώτη δέχεται διακριτές τιμές συμμετοχής ενώ η δεύτερη συνεχής[9].

Biclustering Επεξεργασία

Το Biclustering, επίσης γνωστό ως συν-ομαδοποίηση, είναι μια τεχνική εξόρυξης δεδομένων που επιτρέπει την ταυτόχρονη ομαδοποίηση στηλών και σειρών ενός πίνακα. Ο J.A. Hartigan εισήγαγε το biclustering το 1972[10], αλλά ο αλγόριθμος γενικεύτηκε από τους Y. Cheng και G.M. Church το 2000, όταν πρότειναν έναν αλγόριθμο biclustering για δεδομένα βιολογικής γονιδιακής έκφρασης που βασιζόταν σε διακύμανση δεδομένων[11]. Το Biclustering έχει γίνει μια πολύ σημαντική τεχνική για τη μελέτη δεδομένων γονιδιακής έκφρασης και έχει βοηθήσει στην κατανόηση λειτουργικά συσχετισμένων ομάδων γονιδίων υπό διαφορετικές συνθήκες.

Οι μέθοδοι biclustering μπορούν να χωριστούν σε τρεις κατηγορίες, συν-έκφραση (co-expression), από συν-ρύθμιση (co-regulation) και συντηρημένη συν-ρύθμιση (conserved co-regulation). Πρόσφατα, οι αλγόριθμοι όπως ο cMonkey[12][13], COALESCE[14] και η πιο πρόσφατη έκδοση του SAMBA[15] έχουν προσαρμοστεί για τύπους δεδομένων όπως κοινά μοτίβα θέσεων πρόσδεσης, αλληλεπιδράσεις πρωτεΐνης-DNA και δίκτυα αλληλεπιδράσεων πρωτεΐνης-πρωτεΐνης. Αυτές οι τεχνικές καταλήγουν σε υποσύνολα που συν-ρυθμίζονται και όχι απλά συν-εκφράζονται. Τέλος, διάφορες τεχνικές[16], επεκτείνουν την ενοποιητική προσέγγιση αναζητώντας διατηρημένα biclusters ανάμεσα σε διαφορετικά είδη.

Η μέθοδος cMonkey σχεδιάστηκε για να παράγει υποτιθέμενα συν-ρυθμιζόμενα biclusters που είναι βέλτιστα για ένα δίκτυο αλληλεπιδράσεων. Εκτός από τα δεδομένα έκφρασης μικροσυστοιχιών, το cMonkey ενσωματώνει επίσης ανάντη αλληλουχίες και δίκτυα αλληλεπιδράσεων στη διαδικασία biclustering. Οι ανάντη αλληλουχίες χρησιμοποιούνται για την εύρεση υποθετικών κοινών μοτίβων δέσμευσης μεταξύ των γονιδίων σε ένα bicluster, παρέχοντας επιπλέον στοιχεία για πιθανή από συν-ρύθμιση. Τα συν-ρυθμιζόμενα γονίδια είναι επίσης πιο πιθανό να μοιράζονται άλλες λειτουργικές συζεύξεις, οι οποίες αντικατοπτρίζονται ως ένας αριθμός συνδέσεων μεταξύ γονιδίων ανάμεσα σ’ ένα bicluster σύμφωνα με βάσεις δεδομένων γνωστών αλληλεπιδράσεων όπως το BIND[17] και DIP[18]. Με άλλα λόγια, αυτά τα γονίδια σχηματίζουν μικρά, άκρως συνδεδεμένα υπο-δίκτυα μέσα σε αυτά τα μεγαλύτερα δίκτυα. Σε σύγκριση με άλλες μεθόδους, το cMonkey παράγει biclusters τα οποία είναι πιο ‘σφιχτά’ (έχουν μικρότερη διακύμανση μεταξύ των τιμών έκφρασης γονιδίων) και έτσι περιλαμβάνουν πιο πειραματικές συνθήκες. Το cMonkey πολλαπλών ειδών (Multi-species cMonkey) είναι μια επέκταση της μεθόδου cMonkey για να επιτρέψει την ανακάλυψη ομάδων που διατηρούνται σε πολλαπλά είδη δεδομένων.

ΤΥΠΟΙ ΤΟΥ BICLUSTER

α) Bicluster με σταθερές τιμές

b) Bicluster με σταθερές τιμές σε σειρές ή στήλες.

γ) Bicluster με συνδεδεμένες τιμές.

Triclustering Επεξεργασία

Το Triclustering είναι ένα δύο συνθετικά σύνολα δεδομένων που μοιράζονται τις ετικέτες κατά μήκος μιας από τις διαστάσεις. Πρόκειται για ένα τρισδιάστατο σύνολο δεδομένων και για μία προσπάθεια ανακάλυψης συναφών υποσυνόλων μέσα στα τρισδιάστατα δεδομένα.

Τα triclusters κατασκευάζονται ή ανακαλύπτονται από δύο σύνολα δεδομένων επιλέγοντας ένα υποσύνολο χαρακτηριστικών από κάθε σύνολο δεδομένων και ένα κοινό υποσύνολο γραμμών από μία ολόκληρη σειρά[19].

Ο αλγόριθμος ξεκινά με τυχαία δημιουργημένους σπόρους. Για κάθε επανάληψη, υπολογίζει το σκορ κάθε πιθανής δισδιάστατης (2D) περιοχής σε μία ολόκληρη υπό-περιοχή και σταματά σε μια τοπική βελτιστοποίηση εάν επιτευχθεί ο μέγιστος αριθμός επαναλήψεων. Το TRICLUSTER (gTRI-CLUSTER)[20] είναι μια βελτιωμένη έκδοση του αλγορίθμου TRICLUSTER. Η διαδικασία αλγορίθμου gTRI-CLUSTER περιλαμβάνει τα εξής: (i) προσδιορίζει το μέγιστο υποσύνολο συναφών δειγμάτων για κάθε γονίδιο, (ii) κατασκευάζονται τα καλούπια ομοιότητας, (iii) παρατίθενται οι πιθανές μέγιστες ομάδες από το δείγματος χρησιμοποιώντας αναζήτηση βάθους (iv) τα biclusters δημιουργούνται από τα δείγματα × μήτρες χρόνου και συγχωνεύονται για να δημιουργήσουν τις μέγιστες ομάδες με ανεστραμμένη λίστα.

Η ανάλυση τρισδιάστατων δεδομένων επικρατεί όλο και περισσότερο σε όλους τους τομείς της βιοϊατρικής και μπορεί να χρησιμοποιηθεί για το προφίλ εξέλιξης μιας νόσου.

Επικύρωση αποτελεσμάτων Επεξεργασία

Στην ομαδοποίηση, η ορθότητα των αποτελεσμάτων αποτελεί μια αναγκαία διαδικασία, ανεξαρτήτως της μεθόδου που χρησιμοποιήθηκε. Αυτό συμβαίνει διότι καθορίζονται ομάδες που δεν είναι γνωστές εξ’ αρχής, οπότε κρίνεται απαραίτητη μια αξιολόγηση στις περισσότερες περιπτώσεις ομαδοποίησης και πραγματοποιείται εφαρμόζοντας τις κατάλληλες μεθόδους και κριτήρια[21]. Δύο βασικά χαρακτηριστικά των ομάδων που σχηματίζονται είναι η περιεκτικότητα και η διακριτότητα.

Περιεκτικότητα Επεξεργασία

Η περιεκτικότητα αναφέρεται στο πόσο στενά συσχετίζονται τα στοιχεία εντός μιας ομάδας μέσω ανάλυσης της διαφοράς τους. Έτσι, οι συμπαγείς ομάδες προκύπτουν από στοιχεία τα οποία εμφανίζουν μικρή διαφορά σε χαρακτηριστικά όπως μέγιστη και μέση απόσταση μεταξύ τους ή μέγιστη και μέση απόσταση από το κέντρο της ομάδας. Για τον υπολογισμό των παραπάνω μεγεθών αξιοποιούνται δείκτες όπως η μέση τυπική απόκλιση της τετραγωνικής ρίζας(RMSSTD) και το R2(RS)[22].

RMSSTD Επεξεργασία

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

RS Επεξεργασία

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

RS=SSB/SST

όπου το SSB ισούται με το άθροισμα των τετραγώνων μεταξύ των ομάδων ενώ το SST με το συνολικό άθροισμα των τετραγώνων του συνόλου του σετ δεδομένων[23].

Διακριτότητα Επεξεργασία

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

SD Επεξεργασία

Ο δείκτης SD αναφέρεται τόσο στο θέμα του μέσου διασκορπισμού των ομάδων όσο και στο αντίστοιχο του συνολικού διαχωρισμού μεταξύ τους καθώς αποτελεί μια συνάρτηση των 2 παραπάνω μεγεθών.

SD(nc) = a⋅ Scat(nc) + Dis(nc)

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

Συνδυαστικές μέθοδοι Επεξεργασία

Για την ανάλυση της ποιότητας της ομαδοποίησης υφίστανται και ορισμένες μέθοδοι που συνδυάζουν στοιχεία από τις παραπάνω τεχνικές όπως για παράδειγμα οι δείκτες Dunn, C και Davies-Bouldin.

Davies-Bouldin(DB) Επεξεργασία

Ο DB είναι ένας δείκτης σχετικά χαμηλής πολυπλοκότητας που για μικρές τιμές του χαρακτηρίζονται οι καλής ποιότητας ομαδοποιήσεις. Ένα μέτρο της ομοιότητας μεταξύ 2 ομάδων Rij ορίζεται με βάση ένα μέτρο της διασποράς της μιας ομάδας si και ένα μέτρο της ανομοιότητας dij μεταξύ των 2 ομάδων. Για να πληρούνται τα κριτήρια ορισμού του Rij, αυτό ορίζεται ως εξής:

Rij = (si + sj)/dij

Έπειτα ο δείκτης DB ορίζεται ως:

Γενικώς ο δείκτης αποτελεί ένα μέτρο ομοιότητας μεταξύ των ομάδων και είναι επιθυμητό για αυτό το λόγο να έχει χαμηλή τιμή, όπως προαναφέρθηκε, ενώ επιπλέον, δεν επηρεάζεται από τον αριθμό των ομάδων(3),(4).

Dunn Επεξεργασία

Ένας δείκτης που αξιοποιείται για την ταυτοποίηση καλά διαχωρισμένων και συμπαγών ομάδων είναι ο Dunn. Σε αυτήν την περίπτωση ο δείκτης παίρνει υψηλές τιμές με τις διαμέτρους των ομάδων να είναι μικρές. Όπως και ο DB, έτσι και ο Dunn δεν επηρεάζεται από τον αριθμό των ομάδων, αλλά εμφανίζει κάποια προβλήματα όπως η ευαισθησία στο θόρυβο και η πολυπλοκότητα, η οποία ευθύνεται για τον μεγάλο χρόνο επεξεργασίας. Ως dmin ορίζεται η μικρότερη απόσταση μεταξύ 2 ομάδων ενώ ως dmax η μέγιστη απόσταση 2 στοιχείων εντός μιας ομάδας. Έτσι, ο Dunn ορίζεται ως εξής:

D= dmin/ dmax

C Επεξεργασία

Ο δείκτης C εφαρμόζεται καλύτερα σε ομάδες παρόμοιου μεγέθους. Ορίζεται ως: C=(S-Smin)/(S-Smax)

με S το άθροισμα των αποστάσεων όλων των ζευγών στοιχείων της ίδιας ομάδας. Η τιμή με την οποία ταυτοποιείται η βέλτιστη ομαδοποίηση είναι η μέγιστη, με τον δείκτη να λαμβάνει τιμές, έπειτα από κανονικοποίηση σε εύρος 0 έως 1. Επίσης, ο αριθμός των ομάδων σχετίζεται με την τιμή του δείκτη, διότι στην ιδανική περίπτωση που έχουν σχηματιστεί όσες ομάδες απαιτούνται, ο δείκτης παίρνει τιμή 1[24].

Σταθερότητα ομαδοποίησης Επεξεργασία

Οι ομαδοποιήσεις συχνά, ως αποτέλεσμα εύρεσης μοτίβου, θεωρούνται βαρυσήμαντες αλλά για να ισχύει αυτό πρέπει να είναι παράλληλα και σταθερές. Για τον υπολογισμό της σταθερότητας πρέπει ο αλγόριθμος να επαναληφθεί με σετ δεδομένων όπου έχει γίνει επαναδειγματοληψία και εν τέλει να συγκριθούν τα αποτελέσματα των ομαδοποιήσεων μεταξύ τους. Η επαναδειγματοληψία μπορεί να προκύψει έπειτα από διαχωρισμό του αρχικού σετ δειγμάτων. Η διαδικασία που πρέπει να ακολουθηθεί έχει ως αφετηρία την επιλογή ενός τυχαίου υποδείγματος, χωρίς αντικατάσταση και στη συνέχεια την προσθήκη τυχαίου θορύβου. Έπειτα λαμβάνεται ένα δείγμα με αρχικά δεδομένα αλλά με αντικατάσταση. Κατά τη σύγκριση των αποτελεσμάτων, μπορούν να επιλεχθούν ζεύγη υποδειγμάτων μεταξύ τους ή να δημιουργηθούν ζεύγη του αρχικού δείγματος με υποδείγματα[25][26].

Εφαρμογές Επεξεργασία

Η ανάλυση clustering αποτελεί σημαντικό εργαλείο σε πολλές εφαρμογές σε πολλούς τομείς των επιχειρήσεων και της επιστήμης. Έτσι, συνοψίζουμε τις βασικές κατευθύνσεις στις οποίες χρησιμοποιείται η ομαδοποίηση[27]:

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

• Δημιουργία υποθέσεων. Η ανάλυση clustering χρησιμοποιείται εδώ για να συναχθούν ορισμένες υποθέσεις σχετικά με τα δεδομένα, ώστε να γίνει περεταίρω έρευνα μέσω πειραματικών διαδικασιών.

• Δοκιμή υποθέσεων. Στην περίπτωση αυτή, η ανάλυση clustering χρησιμοποιείται για την επαλήθευση της εγκυρότητας μιας συγκεκριμένης υπόθεσης.

• Πρόβλεψη βάσει των ομάδων. Η ανάλυση clustering εφαρμόζεται στο σύνολο δεδομένων και τα προκύψαντες ομάδες χαρακτηρίζονται από τα ιδιαίτερα μοτίβα που ανήκουν σε αυτά τα clusters. Στη συνέχεια, τα άγνωστα μοτίβα μπορούν να ταξινομηθούν σε καθορισμένες ομάδες με βάση την ομοιότητά τους με τα χαρακτηριστικά των clusters. Ετσι, μπορούν να εξαχθούν χρήσιμες γνώσεις σχετικά με τα δεδομένα. Για παράδειγμα, η ανάλυση clustering μπορεί να εφαρμοστεί σε σύνολο δεδομένων που αφορούν ασθενείς που έχουν μολυνθεί από την ίδια ασθένεια. Το αποτέλεσμα είναι ένας αριθμός ομάδων ασθενών, ανάλογα με την αντίδρασή τους σε συγκεκριμένα φάρμακα. Στη συνέχεια, για έναν νέο ασθενή, είναι να δυνατόν να προσδιοριστεί το cluster στο οποίο ανήκει και να γίνει αγωγή με συγκεκριμένο φάρμακο.

Η ομαδοποίηση έχει ένα ευρύ φάσμα εφαρμογών στις βιολογικές επιστήμες και με τα χρόνια έχει χρησιμοποιηθεί σε πολλούς τομείς, από την ανάλυση των κλινικών πληροφοριών, τη φυλογενετική, τη γονιδιωματική και πρωτεωμική. Για παράδειγμα, αλγόριθμοι ομαδοποίησης που εφαρμόζονται στα δεδομένα έκφρασης γονιδίων μπορούν να χρησιμοποιηθούν για τον εντοπισμό συν-ρυθμιζόμενων γονιδίων και την παροχή ενός γενετικού «αποτυπώματος» για διάφορες ασθένειες. Αλγόριθμοι ομαδοποίησης που εφαρμόζονται σε ολόκληρη τη βάση δεδομένων των γνωστών πρωτεϊνών μπορούν να χρησιμοποιηθούν για την αυτόματη οργάνωση διαφόρων πρωτεϊνών σε οικογένειες που σχετίζονται στενά αλλά και για την αναγνώριση συντηρημένων αλληλουχιών των πρωτεϊνών[28][29]. Ομοίως, οι αλγόριθμοι clustering που εφαρμόζονται δεδομένα τριτοταγών δομών μπορούν να χρησιμοποιηθούν για την οργάνωση και την παροχή πληροφοριών σχετικά με το ρυθμό μεταβολής μεταξύ αλληλουχίας και δομής[30].

Παραπομπές Επεξεργασία

  1. ↑ Jain, A. «Data clustering: A review. ACM Computing Surveys». 
  2. ↑ Sharma, Asuda. «Cluster Analysis of Biological Networks». 
  3. ↑ Amelio, Alessa. «Data Mining: Clustering». 
  4. ↑ Fayyad, Usama. «From Data Mining to Knowledge Discovery in Databases». 
  5. ↑ Murtagh, Fionn. «Algorithms for Hierarchical Clustering: An Overview: Algorithms for Hierarchical Clustering». 
  6. ↑ Dongkuan, Xu. «A Comprehensive Survey of Clustering Algorithms». 
  7. ↑ Wagstaff, Kiri. «Constrained K-Means Clustering with Background Knowledge». 
  8. ↑ van Dongen, Stijn. «A cluster algorithm for graphs». 
  9. ↑ Ameer, Ali. «REVIEW ON FUZZY CLUSTERING ALGORITHMS». 
  10. ↑ Kaiser, Sebastian. «A Toolbox for Bicluster Analysis in R». 
  11. ↑ Yizong, Cheng. «Biclustering of Expression Data». 
  12. ↑ Reiss, David. «Integrated Biclustering of Heterogeneous Genome-Wide Datasets for the Inference of Global Regulatory Networks». 
  13. ↑ Waltman, Peter. «Multi-Species Integrative Biclustering». 
  14. ↑ Huttenhower, C. «Detailing Regulatory Networks through Large Scale Data Integration». 
  15. ↑ Tanay, A. «Revealing Modularity and Organization in the Yeast Molecular Network by Integrated Analysis of Highly Heterogeneous Genomewide Data». 
  16. ↑ Bergmann, Sven. «Iterative Signature Algorithm for the Analysis of Large-Scale Gene Expression Data». 
  17. ↑ Bader, G. «BIND: The Biomolecular Interaction Network Database». 
  18. ↑ Salwinski, L. «The Database of Interacting Proteins: 2004 Update». 
  19. ↑ Zhao, Lizhuang. «BLOSOM: A Framework for Mining Arbitrary Boolean Expressions». 
  20. ↑ Jelili, Oyelade. «Clustering Algorithms: Their Application to Gene Expression Data». 
  21. ↑ HALKIDI, MARIA. «On Clustering Validation Techniques». 
  22. ↑ Liu, Yanchi. «Understanding of Internal Clustering Validation Measures». 
  23. ↑ Halkidi, Maria. «Clustering Validity Checking Methods: Part II». 
  24. ↑ Ακακιάδου, Γεωργία. «Μελέτη του αλγορίθμου ομαδοποίησης k-means σε δεδομένα του παγκόσμιου ιστού». 
  25. ↑ von Luxburg, Ulrike. «Clustering Stability: An Overview, Foundations and TrendsR in Machine Learning». 
  26. ↑ Hennig, Christian. «Cluster validation by measurement of clusteringcharacteristics relevant to the user». 
  27. ↑ Halkidi, Maria. «On Clustering Validation Techniques». 
  28. ↑ Spang, R. «Limits of Homology Detection by Pairwise Sequence Comparison». 
  29. ↑ Kriventseva, Evgenia. «Clustering and Analysis of Protein Families». 
  30. ↑ Holm, L. «DaliLite Workbench for Protein Structure Comparison». 
Ανακτήθηκε από "https://el.wikipedia.org/w/index.php?title=Ομαδοποίηση_βιολογικών_δεδομένων&oldid=9474173"