Biclustering

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια

Το Biclustering, block clustering ,[1] co-clustering, ή two-mode clustering [2] [3] είναι μία τεχνική εξόρυξης δεδομένων που επιτρέπει την ταυτόχρονη ομαδοποίηση των γραμμών και των στηλών ενός πίνακα. Ο όρος δόθηκε αρχικά από τον Mirkin,[4] αν και η τεχνική αυτή είχε προταθεί αρκετά νωρίτερα[4] (από τον J.A. Hartigan[5]).

Δοθέντος ενός συνόλου γραμμών σε στήλες (δηλ., ενός πίνακα ), ο αλγόριθμος biclustering παράγει biclusters - ένα υποσύνολο γραμμών που εμφανίζουν παρόμοια συμπεριφορά σε ένα υποσύνολο στηλών, ή το αντίστροφο.

Ανάπτυξη[Επεξεργασία | επεξεργασία κώδικα]

Η τεχνική biclustering προτάθηκε αρχικά από τον J. A. Hartigan το 1972.[6] Ο όρος biclustering εισήχθη αργότερα από τον Mirkin. Όμως ο αλγόριθμος που περιγράφει τη γενική μέθοδο δόθηκε το 2000 από τους Y. Cheng και G. M. Church, οι οποίοι και πρότειναν έναν biclustering αλγόριθμο που βασίζεται στη διακύμανση (variance) και τον εφάρμοσαν σε δεδομένα γονιδιακής έκφρασης.[7] Η δημοσίευσή τους αυτή παραμένει ακόμα το πιο σημαντικό κομμάτι στη βιβλιογραφία που αφορά το biclustering γονιδιακής έκφρασης.

Τα έτη 2001 και 2003, ο I.S.Dhillon εξέδωσε δύο αλγορίθμους για την εφαρμογή biclustering σε αρχεία και δεδομένα. Η μία εκδοχή βασιζόταν στη διαμέριση διμερών φασματικών γράφων,[8] ενώ άλλη στη θεωρία πληροφορίας. Ο Dhillon θεώρησε ότι η απώλεια αμοιβαίας πληροφορίας κατά το biclustering ήταν ίση με την απόσταση Kullback-Leibler (KL) ανάμεσα στα P και Q, όπου P η κατανομή των αρχείων και των βασικών λέξεων (feature words) πριν το biclustering, και Q η κατανομή μετά. Η απόσταση KL εκτιμά τη διαφορά ανάμεσα σε δύο τυχαίες κατανομές και παίρνει την τιμή μηδέν (KL = 0) όταν οι κατανομές είναι ίδιες, ενώ αυξάνεται καθώς αυξάνεται και η διαφορά μεταξύ των κατανομών.[9] Έτσι, ο στόχος του αλγορίθμου είναι η εξεύρεση της ελάχιστης απόστασης KL ανέμεσα στα P και Q. Το 2004 ο A.Banerjee χρησιμοποίησε μια απόσταση Bregman με βάρη αντί της KL ώστε να σχεδιάσει έναν αλγόριθμο biclustering κατάλληλο για το χειρισμό κάθε είδους πίνακα.[10]

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

Πολυπλοκότητα[Επεξεργασία | επεξεργασία κώδικα]

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

Είδη bicluster[Επεξεργασία | επεξεργασία κώδικα]

Κάθε αλγόριθμος biclustering ορίζει διαφορετικά το bicluster.[12]

Υπάρχουν:

  1. Bicluster με σταθερές τιμές (a),
  2. Bicluster με σταθερές τιμές στις γραμμές (b) ή στις στήλες (c),
  3. Bicluster με συναφείς τιμές (d, e).

1.Bicluster με σταθερές (constant) τιμές

Όταν ένας αλγόριθμος biclustering επιχειρεί να βρει σταθερά biclusters, ο πιο συνήθης τρόπος είναι να αναδιατάσσει τις γραμμές και τις στήλες του πίνακα ώστε να ομαδοποιήσει παρόμοιες γραμμές/στήλες και να βρει biclusters με παρόμοιες τιμές. Η μέθοδος αυτή είναι επαρκής όταν τα δεδομένα μας είναι καθαρά. Αλλά όταν τα δεδομένα περιέχουν θόρυβο (όπως συμβαίνει τις περισσότερες φορές), τότε θα πρέπει να χρησιμοποιηθούν πιο εκλεπτυσμένες μέθοδοι. Ένα τέλειο σταθερό bicluster (perfect constant bicluster) είναι ένας πίνακας (I, J) όπου όλες οι τιμές του a(i, j) είναι ίσες με μ. Σε πραγματικά δεδομένα, το a(i, j) μπορεί να θεωρηθεί ως n(i, j) + μ, όπου το n(i, j) είναι ο θόρυβος. Σύμφωνα με τον αλγόριθμο του Hartigan, για να διαχωριστεί ο αρχικός πίνακας σε ένα σύνολο από biclusters, χρησιμοποιείται η διακύμανση (variance). Επομένως, ένα τέλειο σταθερό bicluster είναι εκείνο που εμφανίζει διακύμανση μηδέν. Επίσης, προκειμένου να αποφευχθεί ο διαχωρισμός του πίνακα σε biclusters με μόνο μία γραμμή και μία στήλη, ο Hartigan υποθέτει ότι υπάρχουν συνολικά K biclusters στον αρχικό πίνακα, κι έτσι όταν ο πίνακας διαχωριστεί σε K biclusters, ο αλγόριθμος σταματά.

2.Biclusters με σταθερές (constant) τιμές σε γραμμές ή στήλες

Αυτό το είδος bicluster δεν μπορεί να υπολογιστεί μόνο με χρήση της διακύμανσης των τιμών του. Για να ολοκληρωθεί η ταυτοποίηση του bicluster θα πρέπει πρώτα να κανονικοποιηθούν οι στήλες και οι γραμμές. Υπάρχουν όμως και άλλοι αλγόριθμοι που μπορούν να βρουν τέτοιου τύπου biclusters μέσω διαφορετικών προσεγγίσεων, χωρίς κανονικοποίηση.

3.Biclusters με συναφείς (coherent) τιμές

Για την ανεύρεση τέτοιων biclusters θα πρέπει να γίνει μια ριζική βελτίωση των αλγορίθμων biclustering των προηγούμενων δύο περιπτώσεων. Αυτό σημαίνει ότι απαιτείται ένας εκλεπτυσμένος αλγόριθμος, ο οποίος μπορεί για παράδειγμα να χρησιμοποιεί τη συνδιακύμανση (covariance) ανάμεσα σε γραμμές και στήλες ή να κάνει χρήση κάποιας μετρικής ομοιότητας όπως αυτή του θεωρήματος των Cheng και Church, κατά το οποίο ένα bicluster ορίζεται ως το υποσύνολο γραμμών και στηλών που έχουν περίπου την ίδια τιμή MSR (Mean Squared Residue - Μέσο Τετραγωνικό Υπόλοιπο).  

a) Bicluster with constant values
2.0 2.0 2.0 2.0 2.0
2.0 2.0 2.0 2.0 2.0
2.0 2.0 2.0 2.0 2.0
2.0 2.0 2.0 2.0 2.0
2.0 2.0 2.0 2.0 2.0
b) Bicluster with constant values on rows
1.0 1.0 1.0 1.0 1.0
2.0 2.0 2.0 2.0 2.0
3.0 3.0 3.0 3.0 3.0
4.0 4.0 4.0 4.0 4.0
4.0 4.0 4.0 4.0 4.0
c) Bicluster with constant values on columns
1.0 2.0 3.0 4.0 5.0
1.0 2.0 3.0 4.0 5.0
1.0 2.0 3.0 4.0 5.0
1.0 2.0 3.0 4.0 5.0
1.0 2.0 3.0 4.0 5.0
d) Bicluster with coherent values (additive)
1.0 4.0 5.0 0.0 1.5
4.0 7.0 8.0 3.0 4.5
3.0 6.0 7.0 2.0 3.5
5.0 8.0 9.0 4.0 5.5
2.0 5.0 6.0 1.0 2.5
e) Bicluster with coherent values (multiplicative)
1.0 0.5 2.0 0.2 0.8
2.0 1.0 4.0 0.4 1.6
3.0 1.5 6.0 0.6 2.4
4.0 2.0 8.0 0.8 3.2
5.0 2.5 10.0 1.0 4.0

Η σχέση ανάμεσα σε αυτά τα μοντέλα ομάδων και άλλα είδη ομαδοποίησης, όπως η ομαδοποίηση συσχέτισης (correlation clustering), συζητώνται στο.[13]

Αλγόριθμοι[Επεξεργασία | επεξεργασία κώδικα]

Υπάρχουν ποικίλοι αλγόριθμοι 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),[14] Robust Biclustering Algorithm (RoBA), Crossing Minimization,[15] cMonkey,[16] PRMs, DCC, LEB (Localize and Extract Biclusters), QUBIC (QUalitative BIClustering), BCCA (Bi-Correlation Clustering Algorithm) BIMAX, ISA, SAMBA και FABIA (Factor Analysis for Bicluster Acquisition).[17] Αλγόριθμοι biclustering  έχουν επίσης προταθεί και χρησιμοποιηθεί και σε άλλους τομείς, με τις ονομασίες coclustering, bidimensional clustering, και subspace clustering (ομαδοποίηση υποχώρου).[12]

Με δεδομένη τη σημασία ανεύρεσης τοπικών μοτίβων σε δεδομένα χρονοσειρών (time-series), πρόσφατα έχουν προταθεί διάφορες μέθοδοι για το χειρισμό του προβλήματος biclustering στη συγκεκριμένη περίπτωση των δεδομένων χρονοσειρών γονιδιακής έκφρασης. Σε αυτή την περίπτωση, τα ενδιαφέροντα biclusters μπορούν να απομονωθούν σε εκείνα που περιέχουν διαδοχικές στήλες. Ο περιορισμός αυτός οδηγεί σε ένα υπολογίσιμο πρόβλημα και διευκολύνει την ανάπτυξη αποδοτικών αλγορίθμων εξαντλητικής αναζήτησης, όπως οι CCC-Biclustering [18] και e-CCC-Biclustering.[19] Τα προσεγγιστικά μοτίβα στους CCC-Biclustering αλγορίθμους επιτρέπουν ένα δοσμένο πλήθος σφαλμάτων ανά γονίδιο, συγκριτικά με το προφίλ έκφρασης που αντιπροσωπεύει το συνολικό μοτίβο έκφρασης του bicluster. Ο αλγόριθμος e-CCC-Biclustering χρησιμοποιεί εκφράσεις προσέγγισης για να βρει και να επιστρέψει όλα τα μέγιστα CCC-Biclusters από έναν διακριτοποιημένο πίνακα Α, καθώς και αποδοτικές τεχνικές επεξεργασίας συμβολοσειρών.

Αυτοί οι αλγόριθμοι εντοπίζουν κι επιστρέφουν όλα τα μέγιστα biclusters με συναφείς και διαδοχικές στήλες με τέλεια/προσεγγιστικά μοτίβα έκφρασης, σε γραμμικό/πολυωνυμικό χρόνο. Το γεγονός αυτό επιτυγχάνεται με το χειρισμό μιας διακριτοποιημένης παραλλαγής του αρχικού πίνακα, με το ίδιο μέγεθος, και χρησιμοποιώντας σε αυτόν αποδοτικές τεχνικές επεξεργασίας συμβολοσειρών βασισμένες σε δέντρα επιθέματος (suffix trees).

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

Υπάρχει μια συνεχής διαμάχη σχετικά με την αξιολόγηση των αποτελεσμάτων όλων αυτών των μεθόδων, καθώς το biclustering επιτρέπει την αλληλοεπικάλυψη ανάμεσα στα clusters κι ακόμα κάποιοι αλγόριθμοι επιτρέπουν την εξαίρεση των μη συμβιβαστών στηλών/συνθηκών. Δεν είναι όλοι οι διαθέσιμοι αλγόριθμοι ντετερμινιστικοί, και γι' αυτό ο εκάστοτε αναλυτής θα πρέπει να δίνει ιδιαίτερη προσοχή στο βαθμό κατά τον οποίο τα αποτελέσματα αντιπροσωπεύουν σταθερά ελάχιστα (minima). Μιας και πρόκειται για πρόβλημα μη-επιβλεπόμενης ομαδοποίησης, η απουσία κάποιας πρότυπης μεθόδου αξιολόγησης καθιστά ιδιαίτερα δύσκολο τον εντοπισμό λαθών στα αποτελέσματα. Μια προσέγγιση θα ήταν η χρήση πολλών διαφορετικών αλγορίθμων biclustering, κι έπειτα η ψηφοφορία μεταξύ τους για να αποφανθεί το βέλτιστο αποτέλεσμα (με πλειοψηφία ή ενισχυμένη πλειοψηφία). Ένας άλλος τρόπος είναι η ανάλυση της ποιότητας των μοτίβων μετατόπισης και κλιμάκωσης (shifting και scaling patterns) στα biclusters.[20] Το biclustering έχει χρησιμοποιηθεί στον τομέα της εξόρυξης κειμένου (text mining) όπου είναι ευρύτερα γνωστό με την ονομασία co-clustering .[21] Τα σώματα κειμένων αναπαριστώνται με διανυσματική μορφή ως ένας πίνακας D του οποίου οι γραμμές δηλώνουν τα έγγραφα και οι στήλες τις λέξεις στο λεξικό. Τα στοιχεία Dij του πίνακα υποδηλώνουν την εμφάνιση της λέξης j στο έγγραφο i. Οι αλγόριθμοι co-clustering εφαρμόζονται πάνω σε τέτοιους πίνακες για να ανακαλύψουν μπλοκ στο D που αντιστοιχούν σε ένα σύνολο εγγράφων (γραμμές) που χαρακτηρίζονται από ένα σύνολο λέξεων (στήλες).

Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

  1. ↑ G. Govaert; M. Nadif (2008). «Block clustering with bernoulli mixture models: Comparison of different approaches,». Computational Statistics and Data Analysis (Elsevier) 52 (6): 3233–3245. 
  2. ↑ G. Govaert· M. Nadif (2013). Co-clustering: models, algorithms and applications. ISTE, Wiley. ISBN 978-1-84821-473-6. 
  3. ↑ «Two-mode clustering methods:a structured overview». Statistical Methods in Medical Research 13 (5): 363–94. 2004. doi:10.1191/0962280204sm373ra. PMID 15516031. 
  4. ↑ 4,0 4,1 Mirkin, Boris (1996). Mathematical Classification and Clustering. Kluwer Academic Publishers. ISBN 0-7923-4159-7. 
  5. ↑ Hartigan JA (1972). «Direct clustering of a data matrix». Journal of the American Statistical Association (American Statistical Association) 67 (337): 123–9. doi:10.2307/2284710. https://archive.org/details/sim_journal-of-the-american-statistical-association_1972-03_67_337/page/123. 
  6. ↑ Hartigan J A. Direct clustering of a data matrix[J].
  7. ↑ https://www.cs.princeton.edu/courses/archive/fall03/cs597F/Articles/biclustering_of_expression_data.pdf Cheng Y, Church G M. Biclustering of expression data[C]//Ismb. 2000, 8: 93–103.
  8. ↑ Dhillon I S. Co-clustering documents and words using bipartite spectral graph partitioning[C]//Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining.
  9. ↑ Dhillon I S, Mallela S, Modha D S. Information-theoretic co-clustering[C]//Proceedings of the ninth ACM SIGKDD international conference on KKluwer Academic Publishersnowledge discovery and data mining.
  10. ↑ Banerjee A, Dhillon I, Ghosh J, et al.
  11. ↑ Peeters R. The maximum edge biclique problem is NP-complete[J].
  12. ↑ 12,0 12,1 12,2 «Biclustering Algorithms for Biological Data Analysis: A Survey». IEEE Transactions on Computational Biology and Bioinformatics 1 (1): 24–45. 2004. doi:10.1109/TCBB.2004.2. PMID 17048406. 
  13. ↑ Kriegel, H.-P.; Kröger, P.; Zimek, A. (March 2009). «Clustering High Dimensional Data: A Survey on Subspace Clustering, Pattern-based Clustering, and Correlation Clustering». ACM Transactions on Knowledge Discovery from Data 3 (1): 1–58. doi:10.1145/1497577.1497578. http://doi.acm.org/10.1145/1497577.1497578. 
  14. ↑ «Revealing modularity and organization in the yeast molecular network by integrated analysis of highly heterogeneous genomewide data». Proc Natl Acad Sci USA 101 (9): 2981–2986. 2004. doi:10.1073/pnas.0308661100. PMID 14973197. 
  15. ↑ Abdullah, Ahsan; Hussain, Amir (2006). «A new biclustering technique based on crossing minimization». Neurocomputing, vol. 69 issue 16-18 69 (16–18): 1882–1896. doi:10.1016/j.neucom.2006.02.018. http://linkinghub.elsevier.com/retrieve/pii/S0925231206001615. 
  16. ↑ «Integrated biclustering of heterogeneous genome-wide datasets for the inference of global regulatory networks». BMC Bioinformatics 2: 280–302. 2006. doi:10.1186/1471-2105-7-280. PMID 16749936. 
  17. ↑ Hochreiter S, Bodenhofer U, Heusel M, Mayr A, Mitterecker A, Kasim A, Khamiakova T, Van Sanden S, Lin D, Talloen W, Bijnens L, Gohlmann HWH, Shkedy Z, Clevert DA (2010). «FABIA: factor analysis for bicluster acquisition». Bioinformatics 26 (12): 1520–1527. doi:10.1093/bioinformatics/btq227. PMID 20418340. 
  18. ↑ «Identification of Regulatory Modules in Time Series Gene Expression Data using a Linear Time Biclustering Algorithm». IEEE Transactions on Computational Biology and Bioinformatics 1 (7): 153–165. 2010. doi:10.1109/TCBB.2008.34. 
  19. ↑ «A polynomial time biclustering algorithm for finding approximate expression patterns in gene expression time series». Algorithms for Molecular Biology 4 (8). 2009. 
  20. ↑ Aguilar-Ruiz JS (2005). «Shifting and scaling patterns from gene expression data». Bioinformatics 21 (10): 3840–3845. doi:10.1093/bioinformatics/bti641. PMID 16144809. 
  21. ↑ Bisson G.; Hussain F. (2008). «Chi-Sim: A new similarity measure for the co-clustering task». ICMLA: 211–217. doi:10.1109/ICMLA.2008.103. 

Επιπρόσθετη βιβλιογραφία[Επεξεργασία | επεξεργασία κώδικα]

Εξωτερικοί σύνδεσμοι[Επεξεργασία | επεξεργασία κώδικα]

Ανακτήθηκε από "https://el.wikipedia.org/w/index.php?title=Biclustering&oldid=10308161"