Методы бикластеризации для анализа интернет-данных

       

Описание модели


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

, где ячейка

равна

, если ген

проявился для условия

, иначе 0. Бикластер

соответствует подмножеству генов

, которые проявились для всего подмножества условий
. Другими словами, пара

определяет подматрицу E для которой все элементы равны 1. Отметим, что согласно такому определению каждая ячейка

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

Определение 2.19  

Пара

называется максимальным по вложению бикластером тогда и только тогда, когда (1)

и (2)

такой, что (a)

и (b)

.

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



Предложение 2.1  

Определение максимального по вложению бикластера  2.19 и определение формального понятия  2.12 эквивалентны.

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


возрастет. Знак

не зависит от действий на предыдущих шагах, что влечет естественное условие прекращения добавления элементов — изменение

становится положительным для любой внешней строки

(или столбца
).
Рассмотрим критерий аддитивной кластеризации (2.4) более подробно. Очевидно, что (2.5) можно переписать следующим образом.
В последнем выражении первое слагаемое — постоянная величена; раскрывая скобки под знаком суммирования во втором слагаемом приходим к новой записи критерия (2.5). Критерий (2.5) представляет собой разность постоянного члена

и
, где



(2.7)

Теперь для минимизации критерия (2.5) необходимо максимизировать (2.7). Критерий (2.7) позволяет лучше интерпретировать условие оптимальности, основанное на изменении знака (2.6) с отрицательного на положительный, когда

оптимально. В самом деле, приращение (2.7), когда

добавляется к

(

остается без изменений), равно:



(2.8)

Для простоты положим, что

положительно. В этом случае

будет отрицательным, когда среднее значение



(2.9)

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

в качестве
, как, например, в модели [31]. Бокс-кластер

должен включать только те объекты

и
, для которых среднее сходство (average proximity)

(см. (2.9)) и

не меньше половины максимального значения. Такой выбор

приводит к обнаружению бокс-кластеров с большими внутренними значениями сходства. Оптимальное значение
, минимизирующее критерий (2.4) для данного бокс-кластера
, равно среднему внутреннему сходству



(2.10)

Для оптимального значения

из (2.10) при его подстановке в критерий

из (2.7) получим



(2.11)

Как видим, эта форма критерия (2.7) не содержит

(определенного по формуле (2.10) ) и может быть легко преобразована для случая, когда оптимальное значение

отрицательно.
Назад Содержание Вперёд

Содержание раздела