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

Note

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

2.4.1. Spectral Co-Clustering#

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

Note

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

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-means. Первые метки n_rows задают разбиение на строки, а остальные метки n_columns задают разбиение на столбцы.

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\) дает метки столбцов.

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, который используе модифицированный алгоритм Джонкера-Волгенанта (Jonker-Volgenant, JV).
Итоговая сумма сходств делится на размер большего набора.

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