WikiSort.ru - Не сортированное

ПОИСК ПО САЙТУ | о проекте

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

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

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

Бикластеризация была впервые представлена 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]

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

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

См. также

Примечания

↑ 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.
↑ G. Govaert, M. Nadif. Co-clustering: models, algorithms and applications. — ISTE, Wiley, 2013. — ISBN 978-1-84821-473-6.
↑ 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.
1 2 Mirkin, Boris. Mathematical Classification and Clustering. — Kluwer Academic Publishers, 1996. — ISBN 0-7923-4159-7.
↑ 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. JSTOR 2284710.
↑ Hartigan J A. Direct clustering of a data matrix[J]. Journal of the american statistical association, 1972, 67(337): 123—129.
↑ 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.
↑ 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.
↑ 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.
↑ 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.
↑ Peeters R. The maximum edge biclique problem is NP-complete[J]. Discrete Applied Mathematics, 2003, 131(3): 651—654.
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.

Литература

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.
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. PMC 430175. PMID 12671006.

Ссылки

FABIA: Factor Analysis for Bicluster Acquisition, an R package —software

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .

Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2025
WikiSort.ru - проект по пересортировке и дополнению контента Википедии

[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. 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.

[mirkin-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. JSTOR 2284710.

[6] Hartigan J A. Direct clustering of a data matrix[J]. Journal of the american statistical association, 1972, 67(337): 123—129.

[7] ttps://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. ACM, 2001: 269—274.

[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. ACM, 2003: 89-98.

[10] 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] Peeters R. The maximum edge biclique problem is NP-complete[J]. Discrete Applied Mathematics, 2003, 131(3): 651—654.

[madeira-oliveira-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.