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

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

Например, для данной матрицы формы (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]])

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

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

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

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

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

Пример бикластеров, образованных разделением строк и столбцов.

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

Пример бикластеров шахматной доски.

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

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

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

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

2.4.1.1. Математическая постановка

Приближенное решение оптимального нормализованного разреза может быть найдено с помощью обобщенного разложения по собственным значениям лапласиана графа. Обычно это означало бы работать напрямую с матрицей Лапласа. Если исходная матрица данных $A$ имеет форму m×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 метки — разделение столбцов.

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}}$

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

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