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]])
Для визуализации бикластера строки и столбцы матрицы данных могут быть переставлены так, чтобы бикластер стал смежным.
Алгоритмы различаются тем, как они определяют бикластеры. Некоторые из распространенных типов включают:
постоянные значения, постоянные строки или постоянные столбцы
необычно высокие или низкие значения
подматрицы с низкой дисперсией
коррелированные строки или столбцы
Алгоритмы также различаются тем, как строки и столбцы могут быть назначены бикластерам, что приводит к различным бикластерным структурам. Блочно-диагональные или шахматные структуры возникают, когда строки и столбцы делятся на разделы.
Если каждая строка и каждый столбец принадлежат ровно одному бикластеру, то перестановка строк и столбцов матрицы данных выявляет бикластеры на диагонали. Вот пример такой структуры, где бикластеры имеют более высокие средние значения, чем остальные строки и столбцы:
В шашечном случае каждая строка принадлежит всем кластерам столбцов, а каждый столбец - всем кластерам строк. Вот пример такой структуры, когда дисперсия значений внутри каждого бикластера мала:
После обучении модели принадлежность строк и столбцов к кластерам можно определить по атрибутам 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\) препроцессится следующим образом:
где \(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\):
где столбцами \(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\). Итоговая матрица вычисляется по формуле
После нормализации вычисляются первые несколько сингулярных векторов, как и в алгоритме 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 нет внутренних бикластерных мер. Внешние меры ссылаются на внешний источник информации, например на истинное решение. При работе с реальными данными истинное решение обычно неизвестно, но бикластеризация искусственных данных может быть полезна для оценки алгоритмов именно потому, что истинное решение известно.
Чтобы сравнить набор найденных бикластеров с набором истинных бикластеров, необходимы две меры сходства: мера сходства для отдельных бикластеров и способ объединения этих индивидуальных сходств в общую оценку.
Для сравнения отдельных бикластеров использовалось несколько мер. На данный момент реализован только индекс Жаккара:
где \(A\) и \(B\) - бикластеры, \(|A \cap B|\) - количество элементов в их пересечении. Индекс Жаккара достигает своего минимума 0, когда бикластеры не пересекаются вообще, и максимума 1, когда они идентичны.
Для сравнения двух наборов бикластеров было разработано несколько методов.
На данный момент доступен только consensus_score
(Hochreiter et. al., 2010):
Вычислить сходство бикластеров для пар бикластеров, по одному в каждом наборе, используя индекс Жаккара или аналогичную меру.
Назначить бикластеры из одного набора в другой по принципу “один к одному”, чтобы максимизировать сумму их сходств. Этот шаг выполняется с помощью Венгерского алгоритма.
Итоговая сумма сходств делится на размер большего набора.
Минимальная оценка консенсуса, 0, происходит, когда все пары бикластеров полностью несхожи. Максимальный балл, 1, наступает, когда оба набора идентичны.