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

Материал из MachineLearning.

Статья существенно переработана с использованием LLM GPT-5.6 Thinking и проверена участником Kseniia Karpeeva.

Промпт приводится полностью в обсуждении статьи.

Бикластеризация (англ. biclustering) — семейство методов кластеризации, одновременно выделяющих связанные подмножества строк и столбцов матрицы данных. Результатом работы алгоритма является набор бикластеров (англ. biclusters) — подматриц, внутри которых наблюдается определённая локальная закономерность.

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

Например, несколько генов могут согласованно изменять активность только при определённых экспериментальных условиях. Пользователи рекомендательной системы могут иметь сходные предпочтения только для конкретного жанра фильмов. Документы могут быть объединены общей темой, описываемой небольшим набором слов.

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

Бикластер задаётся двумя множествами:

$B=(I,J).$

Здесь $I$ — выбранные строки, а $J$ — выбранные столбцы.

Таким образом, бикластеризация отвечает одновременно на два вопроса:

какие объекты похожи;
по каким именно признакам проявляется это сходство.

Содержание

1 Зачем нужна бикластеризация
2 Постановка задачи
3 Определение бикластера
4 Простой пример
5 Отличие от близких методов
- 5.1 Классическая кластеризация
- 5.2 Отбор признаков
- 5.3 Кластеризация в подпространствах
- 5.4 Сокластеризация
6 Типы бикластеров
- 6.1 Постоянные значения
- 6.2 Постоянство по строкам
- 6.3 Постоянство по столбцам
- 6.4 Аддитивно согласованные бикластеры
- 6.5 Мультипликативно согласованные бикластеры
- 6.6 Сдвинутые и масштабированные профили
- 6.7 Сохранение порядка
- 6.8 Плотные бинарные бикластеры
7 Структура набора бикластеров
8 Функции качества
- 8.1 Среднеквадратичный остаток
- 8.2 Интерпретация остатка
- 8.3 Дисперсия
- 8.4 Корреляция
- 8.5 Плотность
- 8.6 Ошибка восстановления
- 8.7 Комбинированные критерии
9 Основные методы
- 9.1 Прямое разбиение матрицы
- 9.2 Алгоритм Чэна — Чёрча
- 9.3 Жадный локальный поиск
- 9.4 Спектральная бикластеризация
- 9.5 Вероятностные модели
- 9.6 Клетчатая модель
- 9.7 Факторные методы
- 9.8 Анализ формальных понятий
- 9.9 Эволюционные методы
10 Вычислительная сложность
11 Как оценивать результат
- 11.1 Внутренняя оценка
- 11.2 Внешняя оценка
- 11.3 Статистическая значимость
- 11.4 Устойчивость
- 11.5 Предметная проверка
12 Предварительная обработка данных
- 12.1 Центрирование
- 12.2 Стандартизация
- 12.3 Логарифмирование
- 12.4 Дискретизация
- 12.5 Пропущенные значения
13 Выбор алгоритма
14 Настройка параметров
15 Практический алгоритм анализа
16 Визуализация
17 Прикладные задачи
- 17.1 Биоинформатика
- 17.2 Анализ текстов
- 17.3 Рекомендательные системы
- 17.4 Анализ веб-данных
- 17.5 Анализ сетей
- 17.6 Медицинские данные
18 История
19 Преимущества метода
20 Ограничения метода
- 20.1 Отсутствие единого определения
- 20.2 Вычислительная сложность
- 20.3 Чувствительность к параметрам
- 20.4 Избыточные результаты
- 20.5 Случайные закономерности
- 20.6 Зависимость от предварительной обработки
- 20.7 Сложность оценки
21 Когда обычная кластеризация лучше
22 Программная реализация
23 Связь с современным машинным обучением
- 23.1 Разреженные модели
- 23.2 Матричная факторизация
- 23.3 Интерпретируемое обучение
- 23.4 Ограниченная бикластеризация
- 23.5 Глубокие модели
24 Алгоритм применения
25 См. также
26 Примечания
27 Литература
28 Ссылки

Зачем нужна бикластеризация

Пусть имеется таблица, строки которой соответствуют объектам, а столбцы — их признакам.

В классической кластеризации строк предполагается, что объекты одного кластера должны быть похожи по всем или почти всем признакам. Это предположение часто оказывается слишком сильным.

Рассмотрим несколько примеров.

Пациенты могут иметь сходные значения только части медицинских показателей.
Гены могут совместно реагировать только на отдельные воздействия.
Пользователи могут одинаково оценивать фильмы одного жанра, но расходиться в оценках остальных фильмов.
Документы могут быть похожи по словам, относящимся к одной теме, и отличаться по остальной лексике.
Посетители сайта могут иметь общий маршрут только на определённой группе страниц.

В подобных задачах использование всех признаков может скрывать локальную закономерность. Нерелевантные столбцы добавляют шум и увеличивают расстояние между объектами, которые в содержательном смысле должны рассматриваться совместно.

Бикластеризация использует другой принцип:

выбирается подмножество строк;
одновременно выбирается подмножество столбцов;
проверяется согласованность соответствующей подматрицы;
процедура повторяется для поиска других локальных структур.

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

Постановка задачи

Пусть дана матрица объектов и признаков

$A=(a_{ij})\in\mathbb R^{m\times n},$

где $m$ — число объектов, а $n$ — число признаков.

Множество строк обозначим через

$X=\{x_1,\ldots,x_m\},$

а множество столбцов — через

$Y=\{y_1,\ldots,y_n\}.$

Элемент $a_{ij}$ содержит значение признака $y_j$ для объекта $x_i$ .

В зависимости от прикладной задачи матрица может иметь различный смысл.

Строки	Столбцы	Значение элемента
Гены	Экспериментальные условия	Уровень экспрессии гена
Пользователи	Товары или фильмы	Оценка, покупка или просмотр
Документы	Слова	Частота слова или вес TF–IDF
Пациенты	Клинические признаки	Результат измерения
Посетители сайта	Веб-страницы	Число или факт посещения

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

Определение бикластера

Бикластером называется пара множеств

$B=(I,J),$

где

$I\subseteq\{1,\ldots,m\},\qquad J\subseteq\{1,\ldots,n\}.$

Эта пара задаёт подматрицу

$A_{IJ}=(a_{ij})_{i\in I,\;j\in J}.$

Множество $I$ содержит строки бикластера, а множество $J$ — столбцы, на которых проявляется их сходство.

Алгоритм бикластеризации обычно возвращает семейство

$\mathcal B=\{B_1,\ldots,B_K\}.$

В отличие от обычного разбиения на кластеры:

один объект может входить в несколько бикластеров;
один признак может входить в несколько бикластеров;
часть объектов и признаков может не войти ни в один бикластер;
разные бикластеры могут описывать разные типы закономерностей;
бикластеры могут пересекаться;
число бикластеров не всегда задаётся заранее;
найденные бикластеры не обязаны покрывать всю матрицу.

Простой пример

Рассмотрим искусственную матрицу.

	$y_1$	$y_2$	$y_3$	$y_4$	$y_5$	$y_6$
$x_1$	8	9	1	2	0	1
$x_2$	7	8	0	1	1	0
$x_3$	1	0	9	8	7	1
$x_4$	0	1	8	9	8	0
$x_5$	2	1	0	1	0	9

В матрице можно выделить два бикластера:

$B_1=(\{x_1,x_2\},\{y_1,y_2\}),$

$B_2=(\{x_3,x_4\},\{y_3,y_4,y_5\}).$

Объекты $x_1$ и $x_2$ похожи только по признакам $y_1$ и $y_2$ . Объекты $x_3$ и $x_4$ похожи по другому набору признаков.

Если сравнивать строки сразу по всем шести столбцам, обе локальные структуры будут выражены слабее.

Отличие от близких методов

Классическая кластеризация

При кластеризации строк расстояние между двумя объектами обычно вычисляется с использованием всех признаков.

Например, евклидово расстояние между строками $x_p$ и $x_q$ имеет вид

$d(x_p,x_q)=\sqrt{\sum_{j=1}^{n}(a_{pj}-a_{qj})^2}.$

В эту сумму входят все столбцы. Даже если два объекта очень похожи по небольшой группе признаков, большое число нерелевантных столбцов может сделать расстояние между ними значительным.

Бикластеризация не требует, чтобы один набор признаков использовался для описания всех групп объектов. Для каждого бикластера формируется собственное множество столбцов.

Отбор признаков

Отбор признаков (англ. feature selection) выбирает один общий набор признаков для всей выборки.

Бикластеризация выполняет локальный отбор признаков: один набор столбцов может быть важен для первой группы объектов, а другой — для второй.

Например, одна группа пациентов может выделяться по показателям крови, а другая — по результатам функциональных исследований. Глобальный отбор признаков может оставить только один из этих наборов.

Кластеризация в подпространствах

Кластеризация в подпространствах (англ. subspace clustering) также ищет группы объектов, существующие только в некоторых измерениях.

Граница между кластеризацией в подпространствах и бикластеризацией не всегда однозначна. Обычно термин «бикластеризация» подчёркивает симметричное рассмотрение строк и столбцов и явное представление результата в виде пары

$(I,J).$

В кластеризации в подпространствах основным результатом чаще считается группа объектов, для которой дополнительно указывается набор релевантных признаков.

Сокластеризация

Термины бикластеризация и сокластеризация (англ. co-clustering) часто используются как синонимы.

В более узком смысле сокластеризацией называют задачу, в которой все строки и столбцы разбиваются на непересекающиеся группы. Пересечения этих групп образуют полное шахматное разбиение матрицы.

Бикластеризация в широком смысле допускает:

пересекающиеся бикластеры;
неполное покрытие матрицы;
разное число строк и столбцов в бикластерах;
независимый поиск отдельных локальных структур.

Поэтому значение термина следует уточнять по постановке задачи и используемому алгоритму.

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

Единого определения «хорошего бикластера» не существует. Разные методы ищут разные виды локальных закономерностей.^[1]

Постоянные значения

В простейшем случае все значения внутри бикластера близки к одной константе:

$a_{ij}=\mu+\varepsilon_{ij},\qquad i\in I,\quad j\in J,$

где $\mu$ — средний уровень, а $\varepsilon_{ij}$ — шум.

Такой бикластер называют бикластером с постоянными значениями (англ. constant-value bicluster).

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

Постоянство по строкам

В бикластере, постоянном по строкам (англ. constant-row bicluster), каждая строка имеет собственный уровень:

$a_{ij}=\mu_i+\varepsilon_{ij}.$

Внутри одной строки значения близки друг к другу, но уровни разных строк могут существенно отличаться.

Например, один ген может иметь высокий уровень экспрессии, а другой — низкий, однако оба сохраняют этот уровень во всех выбранных условиях.

Постоянство по столбцам

Постоянство по столбцам (англ. constant-column bicluster) описывается моделью

$a_{ij}=\nu_j+\varepsilon_{ij}.$

В этом случае значение определяется главным образом выбранным столбцом и приблизительно повторяется для всех строк бикластера.

Аддитивно согласованные бикластеры

Аддитивная модель (англ. additive model) имеет вид

$a_{ij}=\mu+\alpha_i+\beta_j+\varepsilon_{ij},$

где:

$\mu$ — общий уровень;
$\alpha_i$ — эффект строки;
$\beta_j$ — эффект столбца;
$\varepsilon_{ij}$ — остаточное отклонение.

Строки могут иметь разные базовые уровни, но одинаково реагируют на изменение столбцов.

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

Мультипликативно согласованные бикластеры

Мультипликативная модель (англ. multiplicative model) может быть записана как

$a_{ij}=\mu\alpha_i\beta_j+\varepsilon_{ij}.$

Строки такого бикластера имеют сходную форму профиля, но различаются масштабом.

Если все значения положительны, логарифмирование преобразует мультипликативную зависимость в аддитивную:

$\log a_{ij}\approx\log\mu+\log\alpha_i+\log\beta_j.$

Подобные структуры связаны с сингулярным разложением, факторным анализом и другими методами понижения размерности.

Сдвинутые и масштабированные профили

В ряде задач ищутся строки, которые отличаются друг от друга только сдвигом или масштабированием.

Сдвинутая модель (англ. shift model) имеет вид

$a_{ij}=p_j+\alpha_i+\varepsilon_{ij},$

а масштабированная модель (англ. scale model) —

$a_{ij}=\alpha_i p_j+\varepsilon_{ij},$

где $p_j$ описывает общий профиль.

При совместном использовании сдвига и масштаба получается модель

$a_{ij}=\alpha_i p_j+\beta_i+\varepsilon_{ij}.$

Такие модели позволяют находить объекты с одинаковой формой поведения, даже если их абсолютные значения различаются.

Сохранение порядка

В некоторых задачах важны не точные значения, а их относительный порядок.

Бикластер с сохранением порядка (англ. order-preserving bicluster) содержит строки, в которых выбранные столбцы могут быть упорядочены одной и той же перестановкой:

$a_{i\pi(1)}\leq a_{i\pi(2)}\leq\ldots\leq a_{i\pi(|J|)}$

для всех $i\in I$ .

Например, для двух строк могут выполняться отношения

$a_{i2}<a_{i1}<a_{i3}$

$a_{k2}<a_{k1}<a_{k3},$

хотя сами численные значения этих строк сильно различаются.

Порядковые модели устойчивы к монотонным преобразованиям и применяются, когда важен общий порядок возрастания и убывания показателей.^[1]

Плотные бинарные бикластеры

Если матрица содержит только нули и единицы, бикластер может определяться как подматрица с высокой долей единиц.

В матрице «пользователь — товар» единица может означать покупку товара. Плотный бикластер тогда содержит группу пользователей, купивших один и тот же набор товаров.

Полностью заполненная единицами подматрица соответствует полному двудольному подграфу (англ. complete bipartite subgraph).

Структура набора бикластеров

Бикластеры могут по-разному располагаться внутри матрицы.

Структура	Описание
Непересекающаяся	Бикластеры не имеют общих строк и столбцов
Пересекающаяся	Один объект или признак может входить в несколько бикластеров
Шахматная	Все строки и столбцы разбиваются на группы, образующие прямоугольные блоки
Блочно-диагональная	После перестановки строк и столбцов основные блоки располагаются вдоль диагонали
Иерархическая	Одни бикластеры могут содержаться внутри других
Неполное покрытие	Часть матрицы не относится ни к одному бикластеру

Пересечение бикластеров во многих задачах имеет содержательный смысл.

Один ген может участвовать в нескольких биологических процессах. Один пользователь может интересоваться несколькими независимыми категориями товаров. Одно слово может использоваться в разных темах.

Однако большое число сильно пересекающихся бикластеров затрудняет интерпретацию. Поэтому алгоритмы могут ограничивать:

число бикластеров;
минимальный размер;
максимальную долю пересечения;
число бикластеров, содержащих один объект;
сходство нового бикластера с уже найденными.

Функции качества

Алгоритм бикластеризации должен определить, насколько согласованной является выбранная подматрица.

Для этого используется функция качества (англ. quality function) или целевая функция (англ. objective function).

Различные функции качества соответствуют разным определениям бикластера. Поэтому значение критерия одного алгоритма обычно нельзя напрямую сравнивать со значением критерия другого.

Среднеквадратичный остаток

Один из наиболее известных критериев был предложен Яйзуном Чэном и Джорджем Чёрчем для анализа экспрессии генов.^[1]

Для бикластера $(I,J)$ определим среднее значение строки

$a_{iJ}=\frac{1}{|J|}\sum_{j\in J}a_{ij},$

среднее значение столбца

$a_{Ij}=\frac{1}{|I|}\sum_{i\in I}a_{ij}$

и среднее значение всей подматрицы

$a_{IJ}=\frac{1}{|I||J|}\sum_{i\in I}\sum_{j\in J}a_{ij}.$

Остаток элемента определяется как

$r_{ij}=a_{ij}-a_{iJ}-a_{Ij}+a_{IJ}.$

Он показывает, насколько значение $a_{ij}$ отклоняется от аддитивной модели, учитывающей эффект строки и столбца.

Среднеквадратичный остаток (англ. mean squared residue, MSR) имеет вид

$H(I,J)=\frac{1}{|I||J|}\sum_{i\in I}\sum_{j\in J}\left(a_{ij}-a_{iJ}-a_{Ij}+a_{IJ}\right)^2.$

Если

$H(I,J)=0,$

подматрица идеально согласована в рамках аддитивной модели.

При заданном пороге $\delta$ подматрицу называют $\delta$ -бикластером, если

$H(I,J)\leq\delta.$

Интерпретация остатка

Рассмотрим аддитивную модель

$a_{ij}=\mu+\alpha_i+\beta_j.$

Для неё средние значения имеют вид

$a_{iJ}=\mu+\alpha_i+\overline{\beta},$

$a_{Ij}=\mu+\overline{\alpha}+\beta_j,$

$a_{IJ}=\mu+\overline{\alpha}+\overline{\beta}.$

После подстановки в остаток получаем

$r_{ij}=0.$

Поэтому MSR измеряет отклонение от аддитивной согласованности.

Низкое значение MSR само по себе не гарантирует содержательности результата. Маленькие или почти постоянные подматрицы также могут иметь малый остаток.

Поэтому критерий часто дополняют:

минимальным числом строк;
минимальным числом столбцов;
ограничением на дисперсию;
штрафом за малый размер;
штрафом за пересечение с другими бикластерами.

Дисперсия

Для поиска почти постоянных блоков может использоваться внутрибикластерная дисперсия

$V(I,J)=\frac{1}{|I||J|}\sum_{i\in I}\sum_{j\in J}(a_{ij}-a_{IJ})^2.$

Малое значение $V(I,J)$ означает, что все элементы близки к общему среднему.

Однако этот критерий не обнаруживает строки с одинаковой формой, но разными базовыми уровнями.

Корреляция

Согласованность строк можно оценивать с помощью коэффициента корреляции.

Например, средняя попарная корреляция строк имеет вид

$C(I,J)=\frac{2}{|I|(|I|-1)}\sum_{\substack{p,q\in I\\p<q}}\operatorname{corr}\left(A_{pJ},A_{qJ}\right).$

Высокая корреляция позволяет находить сходные профили, даже если строки различаются сдвигом или масштабом.

При малом числе столбцов оценка корреляции может быть неустойчивой.

Плотность

Для бинарных данных плотность бикластера определяется как

$D(I,J)=\frac{1}{|I||J|}\sum_{i\in I}\sum_{j\in J}a_{ij}.$

Если элементы принимают значения ноль и один, $D(I,J)$ равно доле единиц внутри подматрицы.

При $D(I,J)=1$ подматрица полностью заполнена единицами.

Ошибка восстановления

В факторных и вероятностных моделях качество может измеряться ошибкой восстановления матрицы:

$L=\left\|A-\widehat A\right\|_F^2,$

где $\|\cdot\|_F$ — норма Фробениуса, а $\widehat A$ — приближение исходной матрицы.

Минимальная глобальная ошибка восстановления не всегда означает, что отдельные бикластеры будут легко интерпретироваться.

Комбинированные критерии

На практике часто оптимизируется несколько характеристик одновременно:

согласованность значений;
число строк;
число столбцов;
статистическая значимость;
устойчивость;
непохожесть на уже найденные структуры.

Пример комбинированного критерия:

$Q(I,J)=-H(I,J)+\lambda_1|I||J|-\lambda_2O(I,J),$

где $O(I,J)$ измеряет пересечение с ранее найденными бикластерами, а $\lambda_1$ и $\lambda_2$ являются весовыми коэффициентами.

Основные методы

Прямое разбиение матрицы

Одну из первых формальных постановок одновременной кластеризации строк и столбцов предложил Джон Хартиган в 1972 году.^[1]

Метод Хартигана рассматривал разбиение матрицы на прямоугольные блоки с малой внутриблочной изменчивостью.

Современные методы этого класса поочерёдно изменяют разбиения строк и столбцов:

фиксируют группы столбцов и обновляют группы строк;
фиксируют группы строк и обновляют группы столбцов;
повторяют процедуру до стабилизации результата.

Этот подход называют чередующейся оптимизацией (англ. alternating optimization).

Алгоритм Чэна — Чёрча

Алгоритм Чэна — Чёрча начинает с большой подматрицы и последовательно удаляет строки и столбцы, сильнее всего увеличивающие MSR.

Упрощённая схема метода:

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

Маскирование (англ. masking) означает замену элементов найденного бикластера случайными или фоновыми значениями, чтобы следующий запуск алгоритма не возвращал тот же результат.

Метод относительно прост, но зависит от:

значения порога;
порядка удаления строк и столбцов;
способа маскирования;
размера исходной подматрицы;
случайных величин, используемых при маскировании.

Жадный локальный поиск

Жадный локальный поиск (англ. greedy local search) строит решение последовательными локальными изменениями.

На каждом шаге алгоритм может:

добавить строку;
удалить строку;
добавить столбец;
удалить столбец;
заменить строку или столбец;
объединить два бикластера.

Выбирается изменение, сильнее всего улучшающее целевую функцию.

Жадные методы обычно работают быстрее полного перебора, но могут останавливаться в локальном оптимуме.

Спектральная бикластеризация

В спектральной бикластеризации (англ. spectral biclustering) матрица интерпретируется как взвешенный двудольный граф.

Одна доля вершин соответствует строкам, а другая — столбцам. Элемент $a_{ij}$ задаёт вес ребра между строкой $i$ и столбцом $j$ .

После нормализации матрицы вычисляется её сингулярное разложение

$A=U\Sigma V^{\mathsf T}.$

Столбцы матриц $U$ и $V$ задают низкоразмерные представления строк и столбцов.

Затем к этим представлениям применяется обычная кластеризация.

Индерджит Дхиллон использовал спектральное разбиение двудольного графа для одновременной кластеризации документов и слов.^[1]

Юваль Клугер и соавторы применили спектральный подход к поиску шахматных структур в матрицах экспрессии генов.^[1]

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

Вероятностные модели

В вероятностной бикластеризации принадлежность строк и столбцов бикластерам рассматривается как скрытая переменная (англ. latent variable).

Например, для каждой строки может вводиться скрытая метка

$z_i\in\{1,\ldots,K_r\},$

а для каждого столбца —

$w_j\in\{1,\ldots,K_c\}.$

Распределение элемента зависит от пары меток:

$a_{ij}\sim p(a\mid z_i,w_j,\theta).$

Параметры $\theta$ и скрытые метки могут оцениваться с помощью EM-алгоритма, вариационного вывода (англ. variational inference) или методов Монте-Карло.

Преимущества вероятностных моделей:

явное описание шума;
возможность оценивать неопределённость;
использование априорной информации;
работа с различными типами распределений.

К недостаткам относятся вычислительная сложность и зависимость от правильности выбранной вероятностной модели.

Клетчатая модель

Клетчатая модель (англ. plaid model) представляет матрицу как сумму нескольких перекрывающихся слоёв:

$a_{ij}=\theta_{ij}^{(0)}+\sum_{k=1}^{K}\rho_{ik}\kappa_{jk}\theta_{ij}^{(k)}+\varepsilon_{ij}.$

Здесь:

$\theta_{ij}^{(0)}$ — фоновый слой;
$\rho_{ik}$ показывает, входит ли строка $i$ в слой $k$ ;
$\kappa_{jk}$ показывает, входит ли столбец $j$ в слой $k$ ;
$\theta_{ij}^{(k)}$ описывает вклад бикластера;
$\varepsilon_{ij}$ — шум.

Модель допускает одновременное участие одного элемента матрицы в нескольких бикластерах.^[1]

Название связано с тем, что наложенные прямоугольные слои визуально напоминают клетчатую ткань.

Факторные методы

Факторные методы представляют матрицу как произведение матриц меньшего размера:

$A\approx WH^{\mathsf T}.$

Столбцы $W$ описывают участие строк в скрытых факторах, а столбцы $H$ — участие признаков.

Если коэффициенты факторов являются разреженными, каждый фактор может соответствовать отдельному бикластеру.

Разреженность (англ. sparsity) означает, что большая часть коэффициентов равна нулю или близка к нулю.

Метод FABIA рассматривает бикластеризацию как разреженный факторный анализ и предназначен для поиска перекрывающихся мультипликативных структур.^[1]

Разреженность обычно обеспечивается с помощью регуляризации.

Анализ формальных понятий

Для бинарных матриц бикластеризация связана с анализом формальных понятий (англ. formal concept analysis).

Пусть $a_{ij}=1$ означает, что объект $i$ обладает признаком $j$ .

Формальное понятие задаётся парой:

множество объектов, обладающих общим набором признаков;
множество всех признаков, общих для этих объектов.

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

В отличие от многих эвристических алгоритмов, анализ формальных понятий может перечислять все максимальные точные бикластеры. Однако их число в худшем случае растёт экспоненциально.

Эволюционные методы

Бикластер можно представить двумя бинарными векторами:

$u\in\{0,1\}^m,\qquad v\in\{0,1\}^n,$

где единица означает включение строки или столбца в бикластер.

Такое представление позволяет применять генетические алгоритмы, эволюционные стратегии и другие метаэвристики (англ. metaheuristics).

Эволюционные методы могут одновременно оптимизировать несколько критериев:

размер бикластера;
среднеквадратичный остаток;
дисперсию;
степень пересечения;
статистическую значимость.

Они не гарантируют нахождение глобального оптимума и могут требовать большого числа вычислений.

Вычислительная сложность

Полный перебор всех бикластеров практически невозможен.

Для матрицы размера $m\times n$ существует

$(2^m-1)(2^n-1)$

непустых пар подмножеств строк и столбцов.

Даже для матрицы $30\times30$ число возможных подматриц имеет порядок

$2^{60}.$

Для многих определений бикластера поиск оптимального решения является NP-трудной задачей (англ. NP-hard problem).

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

Чэн и Чёрч показали NP-трудность поиска наибольшего квадратного бикластера, удовлетворяющего ограничению на среднеквадратичный остаток.^[1]

Поэтому практические методы используют:

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

Результат большинства алгоритмов не гарантированно является глобально оптимальным.

Как оценивать результат

Оценка бикластеризации сложнее оценки обычной кластеризации.

Различные алгоритмы:

находят разные типы структур;
возвращают разное число бикластеров;
по-разному допускают пересечения;
используют разные функции качества;
могут не покрывать всю матрицу.

Поэтому универсального критерия оценки не существует.^[1]

Внутренняя оценка

Внутренняя оценка (англ. internal validation) использует только исходную матрицу и найденные бикластеры.

Можно анализировать:

согласованность значений;
размер бикластера;
покрытие матрицы;
степень пересечения;
устойчивость к шуму;
устойчивость к изменению параметров;
отличие от случайных подматриц.

Внутренний критерий должен соответствовать модели бикластера.

MSR подходит для аддитивных структур, но может плохо оценивать бикластеры с сохранением порядка.

Корреляция подходит для сходных профилей, но может не обнаруживать блоки с постоянными значениями.

Не следует оценивать несколько методов только по функции, которую непосредственно оптимизирует один из них.

Внешняя оценка

Если известен эталонный набор бикластеров, найденные структуры можно сравнить с эталоном.

Поставим бикластеру

$B=(I,J)$

в соответствие множество ячеек

$C(B)=I\times J.$

Сходство двух бикластеров можно определить с помощью коэффициента Жаккара (англ. Jaccard index):

$s(B_1,B_2)=\frac{|C(B_1)\cap C(B_2)|}{|C(B_1)\cup C(B_2)|}.$

Значение равно единице для совпадающих бикластеров и нулю для бикластеров без общих ячеек.

Пусть $\mathcal M$ — найденные бикластеры, а $\mathcal G$ — эталонные.

Релевантность (англ. relevance) можно определить как

$\operatorname{Rel}(\mathcal M,\mathcal G)=\frac{1}{|\mathcal M|}\sum_{B\in\mathcal M}\max_{G\in\mathcal G}s(B,G).$

Эта величина показывает, насколько найденные бикластеры похожи на какие-либо эталонные.

Полнота восстановления (англ. recovery) имеет вид

$\operatorname{Rec}(\mathcal M,\mathcal G)=\frac{1}{|\mathcal G|}\sum_{G\in\mathcal G}\max_{B\in\mathcal M}s(B,G).$

Она показывает, насколько хорошо были восстановлены все эталонные структуры.

Высокая релевантность при низкой полноте означает, что алгоритм нашёл несколько точных бикластеров, но пропустил остальные.

Высокая полнота при низкой релевантности может означать, что алгоритм возвращает слишком много лишних или фрагментированных структур.

Статистическая значимость

При переборе большого числа подматриц некоторые из них могут оказаться согласованными случайно.

Для проверки статистической значимости (англ. statistical significance) можно сравнивать качество найденного бикластера с распределением качества случайных подматриц того же размера.

Один из вариантов:

случайно переставить элементы матрицы;
повторно выполнить бикластеризацию;
сравнить качество случайных бикластеров с исходным результатом;
повторить процедуру много раз.

При этом необходимо учитывать множественную проверку гипотез (англ. multiple testing), поскольку алгоритм фактически рассматривает большое число потенциальных подматриц.

Устойчивость

Устойчивость (англ. stability) показывает, насколько результат меняется при небольших изменениях данных.

Для проверки устойчивости можно:

повторить алгоритм с разными случайными начальными состояниями;
добавить слабый шум;
удалить часть строк;
удалить часть столбцов;
использовать бутстрэп-выборки (англ. bootstrap samples);
изменить значения гиперпараметров;
сравнить результаты на независимых данных.

Содержательный бикластер должен сохраняться при небольших возмущениях, если они не изменяют саму локальную структуру.

Предметная проверка

В реальных данных эталонные бикластеры обычно неизвестны.

Поэтому результат проверяется с использованием предметных знаний.

В биоинформатике анализируется, связаны ли найденные гены с общими биологическими функциями или сигнальными путями.

В рекомендательных системах оценивается качество рекомендаций.

В анализе текстов проверяется тематическая однородность документов и интерпретируемость слов.

Численно хороший бикластер может оказаться бесполезным, если он не имеет содержательной интерпретации.

Предварительная обработка данных

Результат бикластеризации часто сильно зависит от предварительной обработки данных.

Центрирование

При центрировании строк из каждого элемента вычитается среднее значение строки:

$\widetilde a_{ij}=a_{ij}-\frac{1}{n}\sum_{k=1}^{n}a_{ik}.$

После этого строки сравниваются по форме, а не по абсолютному уровню.

Центрирование столбцов выполняется аналогично.

Стандартизация

При стандартизации строки её значения преобразуются по формуле

$\widetilde a_{ij}=\frac{a_{ij}-\overline a_i}{s_i},$

где $\overline a_i$ — среднее строки, а $s_i$ — её стандартное отклонение.

После стандартизации строки с разными масштабами становятся сопоставимыми.

При этом информация об абсолютном уровне и разбросе теряется.

Логарифмирование

Для положительных данных часто используется преобразование

$\widetilde a_{ij}=\log(a_{ij}+c),$

где $c\geq0$ предотвращает вычисление логарифма нуля.

Логарифмирование:

уменьшает влияние больших значений;
стабилизирует дисперсию;
преобразует мультипликативные зависимости в аддитивные.

Дискретизация

Дискретизация (англ. discretization) преобразует числовые значения в конечный набор категорий.

Например,

$\widetilde a_{ij}=\begin{cases}1,&a_{ij}>\tau,\\0,&a_{ij}\leq\tau.\end{cases}$

Более сложная схема может использовать значения $-1$ , $0$ и $1$ для обозначения уменьшения, отсутствия изменения и увеличения показателя.

Дискретизация упрощает поиск закономерностей, но приводит к потере информации и делает результат зависимым от выбранных порогов.

Пропущенные значения

Способ обработки пропущенных значений должен учитывать причины их появления.

Возможные подходы:

удаление строк или столбцов;
заполнение средним или медианой;
восстановление с помощью матричной факторизации;
использование алгоритма, непосредственно поддерживающего пропуски;
вычисление функции качества только по наблюдаемым элементам.

В рекомендательных системах отсутствие оценки обычно не означает нулевую оценку. Поэтому заменять все пропуски нулями нельзя без дополнительного обоснования.

Выбор алгоритма

Выбор метода зависит от типа данных и искомой закономерности.

Свойства задачи	Возможный подход	Причина
Нужны аддитивно согласованные блоки	Алгоритм Чэна — Чёрча	Использует среднеквадратичный остаток
Матрица большая и разреженная	Спектральная сокластеризация	Эффективно использует спектральные свойства разреженной матрицы
Требуется полное разбиение строк и столбцов	Блочная или вероятностная сокластеризация	Явно моделирует группы строк и столбцов
Бикластеры могут пересекаться	Клетчатая или факторная модель	Допускает сложение нескольких локальных эффектов
Данные бинарные	Анализ формальных понятий или поиск плотных подграфов	Использует дискретную структуру матрицы
Важен порядок, а не точные значения	Порядковая бикластеризация	Устойчива к монотонным преобразованиям
Требуется оптимизация нескольких критериев	Эволюционный алгоритм	Позволяет использовать многоцелевую функцию качества
Необходимо учитывать вероятностный шум	Вероятностная модель	Явно задаёт распределение наблюдений

Универсально лучшего алгоритма не существует.

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

близость абсолютных значений;
одинаковая форма профиля;
пропорциональное изменение;
сохранение порядка;
высокая плотность единиц;
совместное появление категорий;
общий скрытый фактор.

Настройка параметров

К типичным параметрам алгоритмов относятся:

число бикластеров;
минимальное число строк;
минимальное число столбцов;
максимальный размер бикластера;
порог функции качества;
допустимая доля пересечения;
число случайных инициализаций;
коэффициент регуляризации;
порог дискретизации;
число факторов;
уровень шума.

Параметры не следует выбирать только по значению функции, которую непосредственно оптимизирует алгоритм.

Дополнительно необходимо учитывать:

интерпретируемость;
устойчивость;
качество во внешней задаче;
время работы;
повторяемость результата;
чувствительность к предварительной обработке.

В задачах без эталонной разметки полезно исследовать несколько близких наборов параметров и проверять, сохраняются ли основные бикластеры.

Практический алгоритм анализа

Применение бикластеризации можно представить следующей последовательностью действий:

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

Для честного сравнения нескольких методов необходимо использовать одинаковые исходные данные и одинаковую предварительную обработку.

Визуализация

Наиболее распространённый способ визуализации бикластеров — тепловая карта (англ. heat map).

Строки и столбцы переставляются так, чтобы элементы одного бикластера находились рядом.

Для непересекающихся бикластеров после перестановки часто возникает блочно-диагональная или шахматная структура.

Пересекающиеся бикластеры визуализировать сложнее. Возможные подходы:

отдельная тепловая карта для каждого бикластера;
цветовое выделение строк и столбцов;
графовое представление;
матрица принадлежности объектов бикластерам;
интерактивная визуализация;
отображение средних профилей.

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

Прикладные задачи

Биоинформатика

Бикластеризация получила широкое распространение при анализе матриц экспрессии генов (англ. gene expression matrices).

В таких матрицах:

строки соответствуют генам;
столбцы — образцам, моментам времени или экспериментальным условиям;
значения — уровням экспрессии.

Обычная кластеризация объединяет гены на основании поведения во всех условиях. Однако биологический процесс может быть активен только:

в определённом типе клеток;
на конкретной стадии развития;
при воздействии препарата;
в определённой группе пациентов;
при заболевании.

Бикластеризация позволяет выделять группы генов, согласованно активных только в соответствующем подмножестве условий.^[1]^[1]

Методы также применяются для анализа:

данных ДНК-микрочипов;
чувствительности клеточных линий к лекарствам;
взаимодействий «ген — заболевание»;
взаимодействий «ген — препарат»;
протеомных данных;
метаболомных данных;
эпигенетических измерений;
многомодальных биологических данных.

После выделения бикластера выполняется функциональная проверка: анализируется, связаны ли найденные гены с общими биологическими процессами или сигнальными путями.

Анализ текстов

Корпус документов можно представить матрицей «документ — термин».

Значением элемента может быть:

число вхождений слова;
бинарный признак присутствия;
нормированная частота;
вес TF–IDF.

Бикластер содержит группу документов и набор слов, объясняющих их сходство.

Одновременная кластеризация документов и слов позволяет получить не только группу текстов, но и её интерпретацию.

Например, группа документов может характеризоваться словами «нейронная сеть», «обучение», «градиент» и «оптимизация».

Один документ может входить в несколько бикластеров, если он относится к нескольким темам.

Анализ веб-данных

Матрица «пользователь — веб-страница» может содержать:

факт посещения;
число посещений;
длительность просмотра;
число действий;
вероятность перехода.

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

Они могут использоваться для:

анализа навигационных маршрутов;
персонализации;
сегментации аудитории;
поиска совместно посещаемых страниц;
анализа поведения пользователей;
выявления автоматического или аномального трафика.

Анализ сетей

Многие данные естественным образом представляются в виде двудольного графа:

авторы и публикации;
пользователи и товары;
пациенты и симптомы;
белки и биологические функции;
студенты и учебные дисциплины;
компании и технологии.

Матрица смежности такого графа содержит единицу или вес связи между сущностями двух типов.

Бикластер соответствует локально плотному двудольному подграфу.^[1]

Медицинские данные

В медицинских исследованиях строки могут соответствовать пациентам, а столбцы — симптомам, лабораторным показателям, генетическим вариантам или результатам обследований.

Бикластеризация позволяет выделять подгруппы пациентов, сходство которых объясняется определённым набором признаков.

Такие группы могут использоваться для:

поиска подтипов заболеваний;
стратификации пациентов;
анализа ответа на лечение;
поиска сочетаний симптомов;
формулирования исследовательских гипотез.

Найденные бикластеры не следует автоматически интерпретировать как клинически подтверждённые подтипы. Необходима независимая медицинская и статистическая проверка.

История

Одну из первых формальных постановок одновременного группирования строк и столбцов предложил Джон Хартиган в статье 1972 года «Direct Clustering of a Data Matrix».^[1]

Хартиган рассматривал прямую кластеризацию матрицы (англ. direct clustering) и её разбиение на прямоугольные блоки с малой внутриблочной изменчивостью.

Термин biclustering систематически использовался Борисом Миркиным в монографии «Mathematical Classification and Clustering», опубликованной в 1996 году.^[1]

В 2000 году Чэн и Чёрч предложили критерий среднеквадратичного остатка и применили бикластеризацию к данным экспрессии генов.^[1]

Эта работа способствовала распространению бикластеризации в биоинформатике.

В начале 2000-х годов появились:

спектральная сокластеризация документов и слов;
клетчатая модель;
порядковые бикластеры;
спектральная бикластеризация экспрессии генов;
вероятностные блочные модели.

В дальнейшем были разработаны разреженные факторные, байесовские, выпуклые и эволюционные методы.

Область применения бикластеризации расширилась от анализа генов к рекомендательным системам, обработке текстов, медицинским данным и анализу сетей.

Преимущества метода

К преимуществам бикластеризации относятся:

обнаружение локальных закономерностей;
использование разных наборов признаков для разных групп объектов;
возможность пересечения кластеров;
одновременная интерпретация строк и столбцов;
применимость к высокоразмерным данным;
применимость к разреженным матрицам;
возможность работы с числовыми, бинарными и категориальными данными;
возможность поиска аддитивных, мультипликативных и порядковых структур.

Бикластер часто легче интерпретировать, чем обычный кластер, поскольку вместе с группой объектов возвращается набор признаков, объясняющих её образование.

Ограничения метода

Отсутствие единого определения

Разные методы называют бикластером разные структуры:

постоянный блок;
аддитивный профиль;
коррелирующие строки;
плотную бинарную подматрицу;
порядково согласованный блок;
скрытый фактор.

Поэтому результаты разных алгоритмов могут существенно различаться и при этом оставаться корректными относительно их моделей.

Вычислительная сложность

Для многих постановок точный поиск оптимального бикластера вычислительно невозможен на больших данных.

Большинство методов используют приближённую оптимизацию и не гарантируют глобального решения.

Чувствительность к параметрам

Результат может зависеть от:

порога качества;
числа бикластеров;
минимального размера;
предварительной нормализации;
случайной инициализации;
способа обработки пропусков;
коэффициентов регуляризации.

Поэтому необходимо анализировать устойчивость решения.

Избыточные результаты

Алгоритм может возвращать:

большое число почти одинаковых бикластеров;
вложенные бикластеры;
сильно пересекающиеся структуры;
множество маленьких подматриц;
бикластеры, возникающие случайно.

Требуется дополнительная фильтрация и объединение результатов.

Случайные закономерности

Чем больше потенциальных подматриц рассматривается, тем выше вероятность обнаружить согласованный блок случайно.

Особенно осторожно следует интерпретировать:

очень маленькие бикластеры;
бикластеры, найденные после большого числа запусков;
структуры с небольшим преимуществом над случайным фоном;
результаты без проверки на независимых данных.

Зависимость от предварительной обработки

Центрирование, стандартизация и дискретизация могут полностью изменить тип обнаруживаемых структур.

Например, стандартизация строк удаляет информацию об их абсолютных уровнях. Это полезно для поиска сходной формы, но делает невозможным поиск бикластеров с одинаковыми абсолютными значениями.

Сложность оценки

В реальных задачах эталонные бикластеры обычно неизвестны.

Низкое значение внутренней функции качества не гарантирует прикладной полезности или предметной значимости.

Когда обычная кластеризация лучше

Бикластеризация не является универсальной заменой классической кластеризации.

Обычная кластеризация может быть предпочтительнее, если:

все признаки имеют одинаковый смысл для всех групп;
ожидается глобальная структура данных;
требуется непересекающееся разбиение;
необходим простой и устойчивый результат;
число объектов невелико;
важна лёгкость визуализации;
локальные наборы признаков не имеют содержательной интерпретации.

Если один и тот же набор признаков определяет сходство всех объектов, использование бикластеризации может неоправданно усложнить анализ.

Программная реализация

В библиотеке scikit-learn реализованы два спектральных метода:

SpectralBiclustering;
SpectralCoclustering.

Пример спектральной бикластеризации:

import numpy as np
from sklearn.cluster import SpectralBiclustering
 
X = np.array([
    [8, 9, 1, 2, 0, 1],
    [7, 8, 0, 1, 1, 0],
    [1, 0, 9, 8, 7, 1],
    [0, 1, 8, 9, 8, 0],
    [2, 1, 0, 1, 0, 9],
], dtype=float)
 
model = SpectralBiclustering(
    n_clusters=(2, 2),
    random_state=42,
)
 
model.fit(X)
 
row_labels = model.row_labels_
column_labels = model.column_labels_
 
print("Группы строк:", row_labels)
print("Группы столбцов:", column_labels)

Параметр n_clusters=(2, 2) задаёт число групп строк и число групп столбцов.

Этот алгоритм ищет шахматную структуру и не предназначен для произвольного набора пересекающихся бикластеров.

Для спектральной сокластеризации используется класс SpectralCoclustering.

В экосистеме Bioconductor доступен пакет fabia, реализующий метод FABIA.^[1]

При выборе программной реализации необходимо проверить:

поддерживаемый тип матрицы;
допустимость отрицательных значений;
поддержку пропусков;
возможность пересечения бикластеров;
необходимость заранее задавать число бикластеров;
используемую функцию качества;
наличие случайной инициализации;
вычислительную сложность;
способ получения принадлежности строк и столбцов.

Связь с современным машинным обучением

Бикластеризация относится к методам обучения без учителя, но связана с несколькими другими направлениями машинного обучения.

Разреженные модели

Многие современные модели используют регуляризацию, заставляющую коэффициенты принимать нулевые значения.

Разреженный фактор может соответствовать небольшой группе строк и столбцов, то есть бикластеру.

Поэтому граница между бикластеризацией, разреженной факторизацией и поиском интерпретируемых скрытых факторов не всегда является строгой.

Матричная факторизация

В рекомендательных системах матрица взаимодействий приближается произведением

$A\approx UV^{\mathsf T}.$

Строки матрицы $U$ описывают скрытые свойства пользователей, а строки матрицы $V$ — скрытые свойства объектов.

Обычная матричная факторизация создаёт непрерывные скрытые представления. Бикластеризация обычно возвращает дискретные или разреженные группы строк и столбцов.

Факторные модели бикластеризации занимают промежуточное положение между этими подходами.

Интерпретируемое обучение

Каждый бикластер содержит:

группу объектов;
набор признаков;
локальную закономерность.

Это делает результат потенциально интерпретируемым.

Например, модель может выделить группу пациентов и конкретные клинические показатели, по которым они похожи.

Однако интерпретируемость не возникает автоматически. Слишком большие, маленькие или сильно пересекающиеся бикластеры могут быть трудны для содержательного анализа.

Ограниченная бикластеризация

Если известна часть информации о желаемых группах, её можно использовать в ограниченной бикластеризации (англ. constrained biclustering).

Ограничения могут задавать:

строки, которые должны находиться вместе;
строки, которые не должны находиться вместе;
обязательные признаки;
запрещённые признаки;
известные биологические или предметные группы.

Такой подход связан с полууправляемым обучением (англ. semi-supervised learning).

Глубокие модели

Для бикластеризации могут использоваться автокодировщики, нейронные матричные факторизации и глубокие вероятностные модели.

Сначала нейронная сеть строит скрытое представление данных, после чего в нём выделяются связанные группы строк и столбцов.

Преимуществом является возможность моделировать нелинейные зависимости. Недостатками являются:

сложность обучения;
большое число параметров;
слабая интерпретируемость;
необходимость большого объёма данных;
трудность сравнения с классическими методами.

Глубокая модель не устраняет необходимость определить, что именно считается бикластером и как оценивать его качество.

Алгоритм применения

Практический процесс бикластеризации можно представить следующим образом:

представить данные в виде матрицы «объекты — признаки»;
определить смысл элементов матрицы;
сформулировать тип искомой локальной закономерности;
исследовать распределение значений;
обработать пропуски и выбросы;
выбрать способ нормализации;
выбрать один или несколько алгоритмов;
задать диапазон параметров;
выполнить несколько запусков;
оценить качество и устойчивость;
удалить избыточные бикластеры;
визуализировать подматрицы;
выполнить предметную проверку;
проверить результат на независимых данных.

Перед применением метода необходимо ответить на три основных вопроса:

какие строки должны образовывать совместную группу;
какие столбцы объясняют их сходство;
какая математическая закономерность должна выполняться внутри подматрицы.

См. также

Примечания

Литература

Hartigan J. A. Journal of the American Statistical Association. — 1972. — Т. 67, № 337. — С. 123–129.

Mirkin B. Mathematical Classification and Clustering. — Dordrecht: Kluwer Academic Publishers, 1996. — ISBN 978-0-7923-4159-8

Cheng Y., Church G. M. Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology. — 2000. — С. 93–103.

Dhillon I. S. Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. — 2001. — С. 269–274.

Lazzeroni L., Owen A. Statistica Sinica. — 2002. — Т. 12, № 1. — С. 61–86.

Ben-Dor A., Chor B., Karp R., Yakhini Z. Journal of Computational Biology. — 2003. — Т. 10, № 3–4. — С. 373–384.

Kluger Y., Basri R., Chang J. T., Gerstein M. Genome Research. — 2003. — Т. 13, № 4. — С. 703–716.

Madeira S. C., Oliveira A. L. IEEE/ACM Transactions on Computational Biology and Bioinformatics. — 2004. — Т. 1, № 1. — С. 24–45.

Prelić A., Bleuler S., Zimmermann P. et al. Bioinformatics. — 2006. — Т. 22, № 9. — С. 1122–1129.

Hochreiter S. et al. Bioinformatics. — 2010. — Т. 26, № 12. — С. 1520–1527.

Pontes B., Giráldez R., Aguilar-Ruiz J. S. Journal of Biomedical Informatics. — 2015. — Т. 57. — С. 163–180.

Castanho E. N., Aidos H., Madeira S. C. Briefings in Bioinformatics. — 2024. — Т. 25, № 4.

Ссылки

Biclustering в scikit-learn — описание спектральной бикластеризации и сокластеризации.
SpectralBiclustering — реализация поиска шахматной структуры.
SpectralCoclustering — реализация спектральной сокластеризации.
Пакет FABIA в Bioconductor — факторный анализ для поиска перекрывающихся бикластеров.

Источник — «http://poligon.machinelearning.ru/wiki/index.php?title=%D0%91%D0%B8%D0%BA%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F»

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

Материал из MachineLearning.

Содержание

Зачем нужна бикластеризация

Постановка задачи

Определение бикластера

Простой пример

Отличие от близких методов

Классическая кластеризация

Отбор признаков

Кластеризация в подпространствах

Сокластеризация

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

Постоянные значения

Постоянство по строкам

Постоянство по столбцам

Аддитивно согласованные бикластеры

Мультипликативно согласованные бикластеры

Сдвинутые и масштабированные профили

Сохранение порядка

Плотные бинарные бикластеры

Структура набора бикластеров

Функции качества

Среднеквадратичный остаток

Интерпретация остатка

Дисперсия

Корреляция

Плотность

Ошибка восстановления

Комбинированные критерии

Основные методы

Прямое разбиение матрицы

Алгоритм Чэна — Чёрча

Жадный локальный поиск

Спектральная бикластеризация

Вероятностные модели

Клетчатая модель

Факторные методы

Анализ формальных понятий

Эволюционные методы

Вычислительная сложность

Как оценивать результат

Внутренняя оценка

Внешняя оценка

Статистическая значимость

Устойчивость

Предметная проверка

Предварительная обработка данных

Центрирование

Стандартизация

Логарифмирование

Дискретизация

Пропущенные значения

Выбор алгоритма

Настройка параметров

Практический алгоритм анализа

Визуализация

Прикладные задачи

Биоинформатика

Анализ текстов

Рекомендательные системы

Анализ веб-данных

Анализ сетей

Медицинские данные

История

Преимущества метода

Ограничения метода

Отсутствие единого определения

Вычислительная сложность

Чувствительность к параметрам

Избыточные результаты

Случайные закономерности

Зависимость от предварительной обработки

Сложность оценки

Когда обычная кластеризация лучше

Программная реализация

Связь с современным машинным обучением

Разреженные модели

Матричная факторизация

Интерпретируемое обучение