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_. Эти модели разделяют строки и столбцы, как в блочно-диагональных и шахматных структурах биклостеров.

Примечание

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

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 метки обеспечивают разбиение столбцов.

Примеры

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

Ссылки

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

2.4.2. Спектральное биклостеринг

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

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

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

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

Нормализация строк и столбцов независимо, как и в случае со спектральным совместным кластерированием. Этот метод делает сумму значений по строкам постоянной, а сумму значений по столбцам — другой постоянной.
**Бистохастизация**: повторяемая нормализация строк и столбцов до схождения. Этот метод делает суммы значений по строкам и столбцам одинаковыми.
**Логарифмическая нормализация**: вычисляется логарифм матрицы данных: \(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}}\]

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

Если использовалась логарифмическая нормализация, все сингулярные векторы имеют смысл. Однако, если использовалась независимая нормализация или бистохастизация, первые сингулярные векторы \(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\), получаются метки столбцов.

Примеры

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

Ссылки

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–2025 The scikit-learn developers
Licensed under the 3-clause BSD License.
https://scikit-learn.org/1.6/modules/biclustering.html