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. Spectral Co-Clustering

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

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

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

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

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

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

  1. Независимая нормализация строк и столбцов, как в Spectral Co-Clustering. В этом методе сумма строк равна константе, а сумма столбцов - другой константе.

  2. Бистохастизация: повторная нормализация строк и столбцов до сходимости. При этом методе сумма строк и столбцов равна одной и той же константе.

  3. Лог нормализация: вычисляется логарифм матрицы данных: \(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):

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

  2. Назначить бикластеры из одного набора в другой по принципу “один к одному”, чтобы максимизировать сумму их сходств. Этот шаг выполняется с помощью Венгерского алгоритма.

  3. Итоговая сумма сходств делится на размер большего набора.

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