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

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

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

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

Бикластеризация была впервые представлена J. A. Hartigan в 1972 году. Термин бикластеризация был позднее введен Mirkin. Этот алгоритм не был обобщён до 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-полными и требуют больших вычислительных мощностей или использования эвристических подходов.

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

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

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

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

См. также

• Анализ формальных понятий
• Полный двудольный граф
• Соответствие Галуа

Литература

• Abdullah, Ahsan; Hussain, Amir. A new biclustering technique based on crossing minimization (англ.) // Neurocomputing, vol. 69 issue 16-18 : journal. — 2006. — Vol. 69, no. 16—18. — P. 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 J. T., Gerstein M. B. Spectral Biclustering of Microarray Data: Coclustering Genes and Conditions (англ.) // Genome Research : journal. — 2003. — Vol. 13, no. 4. — P. 703—716. — doi:10.1101/gr.648603. — PMID 12671006. — PMC 430175.

Ссылки

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