Бикластеризация

Поделись знанием:
Перейти к: навигация, поиск

Бикластеризация, блоковая кластеризация ,[1] сокластеризация, также двухмодальная кластеризация [2] [3] — методика data mining, которая позволяет одновременную кластеризацию строк и столбцов матрицы. Термин был впервые предложен Mirkin,[4] хотя сам метод был придуман гораздо раньше[4] (J.A. Hartigan[5]).

Принимая на вход набор <math>m</math> строк в <math>n</math> столбцах (матрица размера <math>m \times n</math>), алгоритм бикластеризации генерирует бикластеры — подмножество строк, которые проявляют похожее поведение через подмножество столбцов.





История развития

Бикластеризация была впервые представлена J. A. Hartigan в 1972 году[6]. Термин бикластеризация был позднее введен Mirkin. Этот алгоритм не был обобщён до 2000 года, когда Y. Cheng и G. M. Church предложили алгоритм бикластеризации, основанный на дисперсии, и применили его к биологическим данным по экспрессии генов[7]. Их статья до сих пор остаётся одним из наиболее важных литературных материалов в области бикластеризации экспрессии генов.

В 2001 и 2003 годах I. S. Dhillon предложил два алгоритма, в которых бикластеризация применяется для файлов и слов. Одна из версий была основана на разделении двудольных спектральных графов[8]. Вторая была основана на теории информации. Dhillon допустил, что потеря взаимной информации при бикластеризации равна KL (расстояние Кульбака-Лейблера) между P и Q. P означает распределение файлов и характеристических слов перед бикластеризацией. Q, в свою очередь, — распределение после кластеризации. KL-расстояние необходимо в качестве меры отличий между двумя случайными распределениями. KL = 0, когда два распределения одинаковы, и возрастает, если возрастает отличие[9]. Таким образом, целью алгоритма являлась минимизация KL-расстояния между P и Q. В 2004 A. Banerjee использовал взвешенное расстояние Брегмана вместо KL-расстояния, чтобы разработать алгоритм бикластеризации, подходящий для любого типа матрицы, в отличие от KL алгоритма[10].

С целью кластеризовать более чем два типа объектов Bekkerman в 2005 году расширил взаимную информацию в теореме Dhillon от одной пары до множества пар.

Сложность задачи

Сложность задачи бикластеризации зависит от конкретной формулировки, в особенности от функции, используемой для оценки качества полученного бикластера. Наиболее интересные варианты этих задач являются NP-полными и требуют больших вычислительных мощностей или использования эвристических подходов[11] [12].

Типы бикластеров

Различные алгоритмы бикластеризации имеют различные определения бикластера[12]

Основные типы:

  1. Бикластер с постоянными значениями (a),
  2. Бикластер с постоянными значениями по строкам (b) или столбцам (c),
  3. Бикластер со сцепленными значениями (d, e).

См. также

Напишите отзыв о статье "Бикластеризация"

Ссылки

  1. ↑ G. Govaert, M. Nadif (2008). «Block clustering with bernoulli mixture models: Comparison of different approaches,». Computational Statistics and Data Analysis (Elsevier) 52: 3233–3245.
  2. ↑ G. Govaert, M. Nadif. Co-clustering: models, algorithms and applications. — ISTE, Wiley, 2013. — ISBN 978-1-84821-473-6.
  3. ↑ Van Mechelen I, Bock HH, De Boeck P (2004). «Two-mode clustering methods:a structured overview». Statistical Methods in Medical Research 13 (5): 363–94. DOI:10.1191/0962280204sm373ra. PMID 15516031.
  4. ↑ 1 2 Mirkin Boris. Mathematical Classification and Clustering. — Kluwer Academic Publishers, 1996. — 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.
  6. ↑ [amstat.tandfonline.com/doi/abs/10.1080/01621459.1972.10481214#.VBLA6vmSwjA Hartigan J A. Direct clustering of a data matrix[J]. Journal of the american statistical association, 1972, 67(337): 123–129.]
  7. ↑ 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. ↑ [dl.acm.org/citation.cfm?id=502550 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. ACM, 2001: 269–274.]
  9. ↑ [dl.acm.org/citation.cfm?id=956764 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. ACM, 2003: 89–98.]
  10. ↑ [dl.acm.org/citation.cfm?id=1014111 Banerjee A, Dhillon I, Ghosh J, et al. A generalized maximum entropy approach to bregman co-clustering and matrix approximation[C]//Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2004: 509–514.]
  11. ↑ [www.sciencedirect.com/science/article/pii/S0166218X03003330 Peeters R. The maximum edge biclique problem is NP-complete[J]. Discrete Applied Mathematics, 2003, 131(3): 651–654.]
  12. ↑ 1 2 . Madeira SC, Oliveira AL (2004). «Biclustering Algorithms for Biological Data Analysis: A Survey». IEEE Transactions on Computational Biology and Bioinformatics 1 (1): 24–45. DOI:10.1109/TCBB.2004.2. PMID 17048406.

Ошибка в сносках?: Тег <ref> с именем «ahsan», определённый в <references>, не используется в предшествующем тексте.

  • A. Tanay. R. Sharan, and R. Shamir, "Biclustering Algorithms: A Survey", In Handbook of Computational Molecular Biology, Edited by Srinivas Aluru, Chapman (2004)
  • Kluger Y, Basri R, Chang JT, Gerstein MB (2003). «Spectral Biclustering of Microarray Data: Coclustering Genes and Conditions». Genome Research 13 (4): 703–716. DOI:10.1101/gr.648603. PMID 12671006.

Внешние ссылки

  • [www.bioinf.jku.at/software/fabia/fabia.html FABIA: Factor Analysis for Bicluster Acquisition, an R package] —software

Отрывок, характеризующий Бикластеризация

– Нет, послушайте, – сказал Пьер, успокоиваясь. – Вы удивительный человек. То, что вы сейчас сказали, очень хорошо, очень хорошо. Разумеется, вы меня не знаете. Мы так давно не видались…детьми еще… Вы можете предполагать во мне… Я вас понимаю, очень понимаю. Я бы этого не сделал, у меня недостало бы духу, но это прекрасно. Я очень рад, что познакомился с вами. Странно, – прибавил он, помолчав и улыбаясь, – что вы во мне предполагали! – Он засмеялся. – Ну, да что ж? Мы познакомимся с вами лучше. Пожалуйста. – Он пожал руку Борису. – Вы знаете ли, я ни разу не был у графа. Он меня не звал… Мне его жалко, как человека… Но что же делать?
– И вы думаете, что Наполеон успеет переправить армию? – спросил Борис, улыбаясь.
Пьер понял, что Борис хотел переменить разговор, и, соглашаясь с ним, начал излагать выгоды и невыгоды булонского предприятия.
Лакей пришел вызвать Бориса к княгине. Княгиня уезжала. Пьер обещался приехать обедать затем, чтобы ближе сойтись с Борисом, крепко жал его руку, ласково глядя ему в глаза через очки… По уходе его Пьер долго еще ходил по комнате, уже не пронзая невидимого врага шпагой, а улыбаясь при воспоминании об этом милом, умном и твердом молодом человеке.
Как это бывает в первой молодости и особенно в одиноком положении, он почувствовал беспричинную нежность к этому молодому человеку и обещал себе непременно подружиться с ним.
Князь Василий провожал княгиню. Княгиня держала платок у глаз, и лицо ее было в слезах.
– Это ужасно! ужасно! – говорила она, – но чего бы мне ни стоило, я исполню свой долг. Я приеду ночевать. Его нельзя так оставить. Каждая минута дорога. Я не понимаю, чего мешкают княжны. Может, Бог поможет мне найти средство его приготовить!… Adieu, mon prince, que le bon Dieu vous soutienne… [Прощайте, князь, да поддержит вас Бог.]
– Adieu, ma bonne, [Прощайте, моя милая,] – отвечал князь Василий, повертываясь от нее.
– Ах, он в ужасном положении, – сказала мать сыну, когда они опять садились в карету. – Он почти никого не узнает.
– Я не понимаю, маменька, какие его отношения к Пьеру? – спросил сын.
– Всё скажет завещание, мой друг; от него и наша судьба зависит…
– Но почему вы думаете, что он оставит что нибудь нам?
– Ах, мой друг! Он так богат, а мы так бедны!
– Ну, это еще недостаточная причина, маменька.
– Ах, Боже мой! Боже мой! Как он плох! – восклицала мать.


Когда Анна Михайловна уехала с сыном к графу Кириллу Владимировичу Безухому, графиня Ростова долго сидела одна, прикладывая платок к глазам. Наконец, она позвонила.
– Что вы, милая, – сказала она сердито девушке, которая заставила себя ждать несколько минут. – Не хотите служить, что ли? Так я вам найду место.
Графиня была расстроена горем и унизительною бедностью своей подруги и поэтому была не в духе, что выражалось у нее всегда наименованием горничной «милая» и «вы».
– Виновата с, – сказала горничная.
– Попросите ко мне графа.
Граф, переваливаясь, подошел к жене с несколько виноватым видом, как и всегда.
– Ну, графинюшка! Какое saute au madere [сотэ на мадере] из рябчиков будет, ma chere! Я попробовал; не даром я за Тараску тысячу рублей дал. Стоит!
Он сел подле жены, облокотив молодецки руки на колена и взъерошивая седые волосы.
– Что прикажете, графинюшка?
– Вот что, мой друг, – что это у тебя запачкано здесь? – сказала она, указывая на жилет. – Это сотэ, верно, – прибавила она улыбаясь. – Вот что, граф: мне денег нужно.
Лицо ее стало печально.
– Ах, графинюшка!…
И граф засуетился, доставая бумажник.
– Мне много надо, граф, мне пятьсот рублей надо.
И она, достав батистовый платок, терла им жилет мужа.
– Сейчас, сейчас. Эй, кто там? – крикнул он таким голосом, каким кричат только люди, уверенные, что те, кого они кличут, стремглав бросятся на их зов. – Послать ко мне Митеньку!
Митенька, тот дворянский сын, воспитанный у графа, который теперь заведывал всеми его делами, тихими шагами вошел в комнату.
– Вот что, мой милый, – сказал граф вошедшему почтительному молодому человеку. – Принеси ты мне… – он задумался. – Да, 700 рублей, да. Да смотри, таких рваных и грязных, как тот раз, не приноси, а хороших, для графини.
– Да, Митенька, пожалуйста, чтоб чистенькие, – сказала графиня, грустно вздыхая.
– Ваше сиятельство, когда прикажете доставить? – сказал Митенька. – Изволите знать, что… Впрочем, не извольте беспокоиться, – прибавил он, заметив, как граф уже начал тяжело и часто дышать, что всегда было признаком начинавшегося гнева. – Я было и запамятовал… Сию минуту прикажете доставить?
– Да, да, то то, принеси. Вот графине отдай.
– Экое золото у меня этот Митенька, – прибавил граф улыбаясь, когда молодой человек вышел. – Нет того, чтобы нельзя. Я же этого терпеть не могу. Всё можно.
– Ах, деньги, граф, деньги, сколько от них горя на свете! – сказала графиня. – А эти деньги мне очень нужны.


Источник — «http://wiki-org.ru/wiki/index.php?title=Бикластеризация&oldid=81622184»