Введение

Техника интеллектуального анализа данных для одновременной кластеризации строк и столбцов матрицы. Бикластеризация, блочная кластеризация, совместная кластеризация или двухмодовая кластеризация – это техника интеллектуального анализа данных, позволяющая одновременно кластеризовать строки и столбцы матрицы. Термин был впервые предложен Борисом Миркиным для обозначения метода, разработанного за много лет до этого.

Для заданного набора образцов, представленных n-мерным векторным признаком, весь набор данных можно представить в виде m строк и n столбцов (то есть, матрицы m x n). Алгоритм бикластеризации генерирует бикластеры. Бикластер – это подмножество строк, демонстрирующее схожее поведение по отношению к подмножеству столбцов, или наоборот.

Разработка

Бикластеризация была первоначально введена Джоном А. Хартиганом в 1972 году. Термин "бикластеризация" позднее был использован и усовершенствован Борисом Г. Миркиным. Этот алгоритм не был обобщён до 2000 года, когда Y. Cheng и George M. Church предложили алгоритм бикластеризации, основанный на оценке среднеквадратичного остатка (MSR), и применили его к данным биологической экспрессии генов. В 2001 и 2003 годах И. С. Дхиллон опубликовал два алгоритма, применяющих бикластеризацию к файлам и словам. Одна версия была основана на разделении двухдольного спектрального графа. Другая – на теории информации. Дхиллон предположил, что потеря взаимной информации при бикластеризации равна расстоянию Калбака-Лейблера (KL distance) между P и Q. P представляет распределение файлов и признаков слов до бикластеризации, а Q – распределение после бикластеризации. KL-расстояние используется для измерения различия между двумя случайными распределениями. KL = 0, когда два распределения идентичны, и KL увеличивается с ростом различия. Таким образом, целью алгоритма было найти минимальное KL-расстояние между P и Q. В 2004 году Ариндам Банерджи использовал взвешенное расстояние Брегмана вместо KL-расстояния для разработки алгоритма бикластеризации, который подходил для любого типа матрицы, в отличие от алгоритма, основанного на KL-расстоянии. Чтобы кластеризовать более двух типов объектов, в 2005 году Беккерман расширил взаимную информацию в теореме Дхиллона с одной пары на несколько пар.

Сложность

Сложность задачи бикластеризации зависит от точной постановки задачи и, в особенности, от функции оценки, используемой для определения качества заданного бикластера. Однако наиболее интересные варианты этой задачи являются NP-полными. NP-полнота определяется двумя условиями. В простом случае, когда в бинарной матрице A элемент a(i,j) может быть равен только 0 или 1, бикластер эквивалентен биклику в соответствующем двудольном графе. Бикластер максимального размера эквивалентен биклику максимального размера ребер в двудольном графе. В сложном случае элемент в матрице A используется для вычисления качества заданного бикластера и решения более узкой версии задачи. Это требует либо значительных вычислительных затрат, либо использования приближенных эвристик для сокращения времени вычислений.