Biclustering

Το Biclustering, block clustering , co-clustering, ή two-mode clustering   είναι μία τεχνική εξόρυξης δεδομένων που επιτρέπει την ταυτόχρονη ομαδοποίηση των γραμμών και των στηλών ενός πίνακα. Ο όρος δόθηκε αρχικά από τον Mirkin, αν και η τεχνική αυτή είχε προταθεί αρκετά νωρίτερα (από τον J.A. Hartigan).
Δοθέντος ενός συνόλου  γραμμών σε  στήλες (δηλ., ενός πίνακα ), ο αλγόριθμος biclustering παράγει biclusters - ένα υποσύνολο γραμμών που εμφανίζουν παρόμοια συμπεριφορά σε ένα υποσύνολο στηλών, ή το αντίστροφο.

Ανάπτυξη

Η τεχνική biclustering προτάθηκε αρχικά από τον J. A. Hartigan το 1972. Ο όρος biclustering εισήχθη αργότερα από τον Mirkin. Όμως ο αλγόριθμος που περιγράφει τη γενική μέθοδο δόθηκε το 2000 από τους Y. Cheng και G. M. Church, οι οποίοι και πρότειναν έναν biclustering αλγόριθμο που βασίζεται στη διακύμανση (variance) και τον εφάρμοσαν σε δεδομένα γονιδιακής έκφρασης. Η δημοσίευσή τους αυτή παραμένει ακόμα το πιο σημαντικό κομμάτι στη βιβλιογραφία που αφορά το biclustering γονιδιακής έκφρασης.
Τα έτη 2001 και 2003, ο I.S.Dhillon εξέδωσε δύο αλγορίθμους για την εφαρμογή biclustering σε αρχεία και δεδομένα. Η μία εκδοχή βασιζόταν στη διαμέριση διμερών φασματικών γράφων, ενώ άλλη στη θεωρία πληροφορίας. Ο Dhillon θεώρησε ότι η απώλεια αμοιβαίας πληροφορίας κατά το biclustering ήταν ίση με την απόσταση Kullback-Leibler (KL) ανάμεσα στα P και Q, όπου P η κατανομή των αρχείων και των βασικών λέξεων (feature words) πριν το biclustering, και Q η κατανομή μετά. Η απόσταση KL εκτιμά τη διαφορά ανάμεσα σε δύο τυχαίες κατανομές και παίρνει την τιμή μηδέν (KL = 0) όταν οι κατανομές είναι ίδιες, ενώ αυξάνεται καθώς αυξάνεται και η διαφορά μεταξύ των κατανομών. Έτσι, ο στόχος του αλγορίθμου είναι η εξεύρεση της ελάχιστης απόστασης KL ανέμεσα στα P και Q. Το 2004 ο A.Banerjee χρησιμοποίησε μια απόσταση Bregman με βάρη αντί της KL ώστε να σχεδιάσει έναν αλγόριθμο biclustering κατάλληλο για το χειρισμό κάθε είδους πίνακα.
Το 2005, ο Bekkerman επέκτεινε την αμοιβαία πληροφορία στο θεώρημα του Dhillon από ένα ζεύγος σε πολλά, ώστε να πετύχει την ομαδοποίηση περισσότερων από δύο ειδών αντικείμενα.

Πολυπλοκότητα

Η πολυπλοκότητα του προβλήματος biclustering εξαρτάται από τη διατύπωση του συγκεκριμένου προβλήματος, και κυρίως από την εκτιμήτρια συνάρτηση που χρησιμοποιείται για την αξιολόγηση ενός δοσμένου bicluster. Παρ' όλα αυτά, οι πιο ενδιαφέρουσες παραλλαγές του προβλήματος είναι NP-πλήρεις. Τα NP-πλήρη προβλήματα έχουν δύο συνθήκες. Στην απλή περίπτωση όπου υπάρχει μόνο ένα στοιχείο a₍ᵢ,ⱼ₎ με τιμή είτε 0 ή 1 στον δυαδικό πίνακα A, τότε το bicluster ισοδυναμεί με ένα biclique στο αντίστοιχο διμερές γράφημα. Το μέγιστο bicluster ιδοσυναμεί με το biclique μέγιστου πλήθους ακμών (maximum edge biclique) στο αντίστοιχο διμερές γράφημα. Στην πιο περίπλοκη περίπτωση, το στοιχείο του Α χρησιμοποιείται για τον υπολογισμό της ποιότητας ενός δοσμένου bicluster και την επίλυση μια πιο περιορισμένης εκδοχής του προβλήματος. Για να απλοποιηθεί ο υπολογισμός, απαιτείται μεγάλη υπολογιστική προσπάθεια ή χρήση ευριστικών.

Αλγόριθμοι

Υπάρχουν ποικίλοι αλγόριθμοι biclustering που έχουν αναπτυχθεί ειδικά για τον τομέα της βιοπληροφορικής, και περιλαμβάνουν τους: block clustering, CTWC (Coupled Two-Way Clustering), ITWC (Interrelated Two-Way Clustering), δ-bicluster, δ-pCluster, δ-pattern, FLOC, OPC, Plaid Model, OPSMs (Order-preserving submatrixes), Gibbs, SAMBA (Statistical-Algorithmic Method for Bicluster Analysis), Robust Biclustering Algorithm (RoBA), Crossing Minimization, cMonkey, PRMs, DCC, LEB (Localize and Extract Biclusters), QUBIC (QUalitative BIClustering), BCCA (Bi-Correlation Clustering Algorithm) BIMAX, ISA, SAMBA και FABIA (Factor Analysis for Bicluster Acquisition). Αλγόριθμοι biclustering  έχουν επίσης προταθεί και χρησιμοποιηθεί και σε άλλους τομείς, με τις ονομασίες coclustering, bidimensional clustering, και subspace clustering (ομαδοποίηση υποχώρου).
Με δεδομένη τη σημασία ανεύρεσης τοπικών μοτίβων σε δεδομένα χρονοσειρών (time-series), πρόσφατα έχουν προταθεί διάφορες μέθοδοι για το χειρισμό του προβλήματος biclustering στη συγκεκριμένη περίπτωση των δεδομένων χρονοσειρών γονιδιακής έκφρασης. Σε αυτή την περίπτωση, τα ενδιαφέροντα biclusters μπορούν να απομονωθούν σε εκείνα που περιέχουν διαδοχικές στήλες. Ο περιορισμός αυτός οδηγεί σε ένα υπολογίσιμο πρόβλημα και διευκολύνει την ανάπτυξη αποδοτικών αλγορίθμων εξαντλητικής αναζήτησης, όπως οι CCC-Biclustering  και e-CCC-Biclustering. Τα προσεγγιστικά μοτίβα στους CCC-Biclustering αλγορίθμους επιτρέπουν ένα δοσμένο πλήθος σφαλμάτων ανά γονίδιο, συγκριτικά με το προφίλ έκφρασης που αντιπροσωπεύει το συνολικό μοτίβο έκφρασης του bicluster. Ο αλγόριθμος e-CCC-Biclustering χρησιμοποιεί εκφράσεις προσέγγισης για να βρει και να επιστρέψει όλα τα μέγιστα CCC-Biclusters από έναν διακριτοποιημένο πίνακα Α, καθώς και αποδοτικές τεχνικές επεξεργασίας συμβολοσειρών.
Αυτοί οι αλγόριθμοι εντοπίζουν κι επιστρέφουν όλα τα μέγιστα biclusters με συναφείς και διαδοχικές στήλες με τέλεια/προσεγγιστικά μοτίβα έκφρασης, σε γραμμικό/πολυωνυμικό χρόνο. Το γεγονός αυτό επιτυγχάνεται με το χειρισμό μιας διακριτοποιημένης παραλλαγής του αρχικού πίνακα, με το ίδιο μέγεθος, και χρησιμοποιώντας σε αυτόν αποδοτικές τεχνικές επεξεργασίας συμβολοσειρών βασισμένες σε δέντρα επιθέματος (suffix trees).
Κάποιοι πρόσφατοι αλγόριθμοι έχουν προσπαθήσει να συμπεριλάβουν επιπρόσθετη υποστήριξη για το biclustering ορθογώνιων πινάκων με τη μορφή άλλων τύπων δεδομένων, όπως ο cMonkey.
Υπάρχει μια συνεχής διαμάχη σχετικά με την αξιολόγηση των αποτελεσμάτων όλων αυτών των μεθόδων, καθώς το biclustering επιτρέπει την αλληλοεπικάλυψη ανάμεσα στα clusters κι ακόμα κάποιοι αλγόριθμοι επιτρέπουν την εξαίρεση των μη συμβιβαστών στηλών/συνθηκών. Δεν είναι όλοι οι διαθέσιμοι αλγόριθμοι ντετερμινιστικοί, και γι' αυτό ο εκάστοτε αναλυτής θα πρέπει να δίνει ιδιαίτερη προσοχή στο βαθμό κατά τον οποίο τα αποτελέσματα αντιπροσωπεύουν σταθερά ελάχιστα (minima). Μιας και πρόκειται για πρόβλημα μη-επιβλεπόμενης ομαδοποίησης, η απουσία κάποιας πρότυπης μεθόδου αξιολόγησης καθιστά ιδιαίτερα δύσκολο τον εντοπισμό λαθών στα αποτελέσματα. Μια προσέγγιση θα ήταν η χρήση πολλών διαφορετικών αλγορίθμων biclustering, κι έπειτα η ψηφοφορία μεταξύ τους για να αποφανθεί το βέλτιστο αποτέλεσμα (με πλειοψηφία ή ενισχυμένη πλειοψηφία). Ένας άλλος τρόπος είναι η ανάλυση της ποιότητας των μοτίβων μετατόπισης και κλιμάκωσης (shifting και scaling patterns) στα biclusters. Το biclustering έχει χρησιμοποιηθεί στον τομέα της εξόρυξης κειμένου (text mining) όπου είναι ευρύτερα γνωστό με την ονομασία co-clustering . Τα σώματα κειμένων αναπαριστώνται με διανυσματική μορφή ως ένας πίνακας D του οποίου οι γραμμές δηλώνουν τα έγγραφα και οι στήλες τις λέξεις στο λεξικό. Τα στοιχεία Dᵢⱼ του πίνακα υποδηλώνουν την εμφάνιση της λέξης j στο έγγραφο i. Οι αλγόριθμοι co-clustering εφαρμόζονται πάνω σε τέτοιους πίνακες για να ανακαλύψουν μπλοκ στο D που αντιστοιχούν σε ένα σύνολο εγγράφων (γραμμές) που χαρακτηρίζονται από ένα σύνολο λέξεων (στήλες).