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

Бикластеризация , блоковая кластеризация , сокластеризация , также двух модальная кластеризация — методика data mining , которая позволяет одновременную кластеризацию строк и столбцов матрицы . Термин был впервые предложен Б.Г. Миркиным, хотя сам метод был придуман гораздо раньше (J.A. Hartigan ).

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

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

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

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

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

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

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

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

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

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

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

На основе обзора С. Мадейры и А. Оливейры и некоторых других была так же предложена таксономия методов бикластеризации на основе типов бикластеров, их структуры, характера порождения, стратегии поиска и типов значений данных.

См. также

Примечания

G. Govaert, M. Nadif. Block clustering with bernoulli mixture models: Comparison of different approaches, (англ.) // (англ.) ( : journal. — Elsevier, 2008. — Vol. 52 . — P. 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 H. H., De Boeck P. Two-mode clustering methods:a structured overview (неопр.) // (англ.) ( . — 2004. — Т. 13 , № 5 . — С. 363—394 . — doi : . — .
↑ Mirkin, Boris. (англ.) . — Kluwer Academic Publishers , 1996. — ISBN 0-7923-4159-7 .
Hartigan J. A. Direct clustering of a data matrix (англ.) // Journal of the American Statistical Association : journal. — American Statistical Association, 1972. — Vol. 67 , no. 337 . — P. 123—129 . — doi : . — JSTOR .
Дата обращения: 30 апреля 2016. 15 марта 2022 года.
от 4 марта 2016 на Wayback Machine Cheng Y, Church G M. Biclustering of expression data[C]//Ismb. 2000, 8: 93-103.
Дата обращения: 30 апреля 2016. 24 сентября 2015 года.
↑ Madeira S. C., Oliveira A. L. Biclustering Algorithms for Biological Data Analysis: A Survey (англ.) // IEEE Transactions on Computational Biology and Bioinformatics : journal. — 2004. — Vol. 1 , no. 1 . — P. 24—45 . — doi : . — .
Игнатов Д.И. // CITForum.ru. — 2008. 1 мая 2023 года.
Ignatov D.I., Watson B.W. (англ.) // Proceedings of Russian and South African Workshop on Knowledge Discovery Techniques Based on Formal Concept Analysis (RuZA 2015). CEUR Workshop Proceedings, 2015. — 2015. — Vol. 1552 . — P. 23—39 . 19 апреля 2022 года.

Литература

Abdullah, Ahsan; Hussain, Amir. (англ.) // Neurocomputing, vol. 69 issue 16-18 : journal. — 2006. — Vol. 69 , no. 16—18 . — P. 1882—1896 . — doi : .
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 J. T., Gerstein M. B. Spectral Biclustering of Microarray Data: Coclustering Genes and Conditions (англ.) // (англ.) ( : journal. — 2003. — Vol. 13 , no. 4 . — P. 703—716 . — doi : . — . — PMC .