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

Алгоритмы бикластеризации одновременно кластеризуют строки и столбцы матрицы данных. Эти кластеры строк и столбцов называются бикластерами. Каждый из них определяет подматрицу исходной матрицы данных с некоторыми требуемыми свойствами.

Например, для матрицы формы (10, 10) один из возможных бикластеров, состоящий из трёх строк и двух столбцов, задаёт подматрицу формы (3, 2):

>>> import numpy as np
>>> data = np.arange(100).reshape(10, 10)
>>> rows = np.array([0, 2, 3])[:, np.newaxis]
>>> columns = np.array([1, 2])
>>> data[rows, columns]
array([[ 1,  2],
       [21, 22],
       [31, 32]])

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

Алгоритмы различаются тем, как они определяют бикластеры. К распространённым типам относятся:

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

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

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

../_images/sphx_glr_plot_spectral_coclustering_003.png — Пример бикластеров, образованных разбиением строк и столбцов.

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

../_images/sphx_glr_plot_spectral_biclustering_003.png — Пример бикластеров в виде шахматной доски.

После обучения модели принадлежность строк и столбцов кластерам можно узнать из атрибутов rows_ и columns_. rows_[i] — это бинарный вектор, ненулевые элементы которого соответствуют строкам, принадлежащим бикластеру i. Аналогично, columns_[i] указывает, какие столбцы принадлежат бикластеру i.

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

Примечание

В разных областях бикластеризацию также называют ко-кластеризацией, двухмодовой кластеризацией, двумерной кластеризацией, блочной кластеризацией, связанной двумерной кластеризацией и т. д. Названия некоторых алгоритмов, например Spectral Co-Clustering, отражают эти альтернативные термины.

2.4.1. Спектральная ко-кластеризация

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

Примечание

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

2.4.1.1. Математическая формулировка

Приближённое решение задачи оптимального нормализованного разреза можно найти с помощью обобщённого разложения Лапласиана графа по собственным значениям. Обычно для этого необходимо работать непосредственно с матрицей Лапласиана. Если исходная матрица данных \(A\) имеет форму \(m \times n\), то матрица Лапласиана соответствующего двудольного графа имеет форму \((m + n) \times (m + n)\). Однако в данном случае можно работать непосредственно с матрицей \(A\), которая меньше и эффективнее.

Входная матрица \(A\) предварительно обрабатывается следующим образом:

\[A_n = R^{-1/2} A C^{-1/2}\]

Где \(R\) — диагональная матрица, элемент \(i\) которой равен \(\sum_{j} A_{ij}\), а \(C\) — диагональная матрица, элемент \(j\) которой равен \(\sum_{i} A_{ij}\).

Сингулярное разложение \(A_n = U \Sigma V^\top\) задаёт разбиение строк и столбцов матрицы \(A\). Подмножество левых сингулярных векторов задаёт разбиение строк, а подмножество правых сингулярных векторов — разбиение столбцов.

\(\ell = \lceil \log_2 k \rceil\) сингулярных векторов, начиная со второго, содержат необходимую информацию о разбиении. Они используются для построения матрицы \(Z\):

\[\begin{split}Z = \begin{bmatrix} R^{-1/2} U \\\\ C^{-1/2} V \end{bmatrix}\end{split}\]

где столбцы матрицы \(U\) — это \(u_2, \dots, u_{\ell + 1}\), и аналогично для \(V\).

Затем строки матрицы \(Z\) кластеризуются с помощью алгоритма k-средних. Первые n_rows меток задают разбиение строк, а оставшиеся n_columns меток — разбиение столбцов.

Примеры

Демонстрация алгоритма Spectral Co-Clustering: простой пример создания матрицы данных с бикластерами и применения к ней этого метода.
Бикластеризация документов с помощью алгоритма Spectral Co-clustering: пример поиска бикластеров в наборе данных двадцати групп новостей.

Литература

Dhillon, Inderjit S, 2001. Ко-кластеризация документов и слов с помощью спектрального разбиения двудольного графа

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

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

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

2.4.2.1. Математическая формулировка

Сначала входная матрица \(A\) нормализуется, чтобы рисунок в виде шахматной доски стал заметнее. Возможны три метода:

Независимая нормализация строк и столбцов, как в Spectral Co-Clustering. Этот метод приводит суммы строк к одной константе, а суммы столбцов — к другой.
Бистохастическая нормализация: повторная нормализация строк и столбцов до сходимости. Этот метод приводит суммы как строк, так и столбцов к одной и той же константе.
Логарифмическая нормализация: вычисляется логарифм матрицы данных: \(L = \log A\). Затем вычисляются среднее по столбцам \(\overline{L_{i \cdot}}\), среднее по строкам \(\overline{L_{\cdot j}}\) и общее среднее \(\overline{L_{\cdot \cdot}}\) матрицы \(L\). Итоговая матрица вычисляется по формуле

\[K_{ij} = L_{ij} - \overline{L_{i \cdot}} - \overline{L_{\cdot j}} + \overline{L_{\cdot \cdot}}\]

После нормализации вычисляются первые несколько сингулярных векторов, как и в алгоритме Spectral Co-Clustering.

При логарифмической нормализации все сингулярные векторы имеют смысл. Однако при независимой нормализации или бистохастической нормализации первые сингулярные векторы \(u_1\) и \(v_1\) отбрасываются. Далее под «первыми» сингулярными векторами подразумеваются \(u_2 \dots u_{p+1}\) и \(v_2 \dots v_{p+1}\), за исключением случая логарифмической нормализации.

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

Например, если было вычислено \(p\) сингулярных векторов, то описанным способом выбираются \(q\) лучших, где \(q<p\). Пусть \(U\) — матрица, столбцами которой являются \(q\) лучших левых сингулярных векторов, и аналогично \(V\) — матрица для правых векторов. Чтобы разбить строки на группы, строки матрицы \(A\) проецируются в пространство размерности \(q\): \(A * V\). Если рассматривать \(m\) строк этой матрицы размерности \(m \times q\) как объекты выборки и кластеризовать их с помощью алгоритма k-средних, получатся метки строк. Аналогично, проецирование столбцов на \(A^{\top} * U\) и кластеризация этой матрицы размерности \(n \times q\) дают метки столбцов.

Примеры

Демонстрация алгоритма Spectral Biclustering: простой пример создания матрицы в виде шахматной доски и её бикластеризации.

Литература

Kluger, Yuval, et. al., 2003. Спектральная бикластеризация данных микрочипов: совместная кластеризация генов и условий

2.4.3. Оценка бикластеризации

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

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

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

\[J(A, B) = \frac{|A \cap B|}{|A| + |B| - |A \cap B|}\]

где \(A\) и \(B\) — бикластеры, а \(|A \cap B|\) — количество элементов в их пересечении. Индекс Жаккара достигает минимального значения 0, когда бикластеры совсем не пересекаются, и максимального значения 1, когда они идентичны.

Разработано несколько методов сравнения двух наборов бикластеров. Пока доступен только consensus_score (Hochreiter et. al., 2010):

Вычислить сходство пар бикластеров, по одному из каждого набора, используя индекс Жаккара или аналогичную метрику.
Сопоставить бикластеры из одного набора с бикластерами другого набора один к одному так, чтобы максимизировать сумму значений сходства. Этот шаг выполняется с помощью scipy.optimize.linear_sum_assignment, использующего модифицированный алгоритм Йонкера — Фольгена.
Итоговая сумма значений сходства делится на размер большего набора.

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

Литература

Hochreiter, Bodenhofer, et. al., 2010. FABIA: факторный анализ для обнаружения бикластеров.

© 2007–2026 The scikit-learn developers
Licensed under the 3-clause BSD License.
https://scikit-learn.org/1.9/modules/biclustering.html