Алгоритмы кластерного анализа

Введение

в кластерный анализ

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

У кластеризации есть несколько полезных свойств:

• 1) грамотная кластеризация обладает предсказательной силой. Причислив объект исследования к какой-либо группе на основании части свойств, мы можем делать обоснованные предположения о наличии у него и других свойств, типичных для его группы;
• 2) в то же время особый интерес представляют случаи «сбоя» модели кластеризации, когда объект, отнесенный к некоторой группе, существенно отличается от типичных ее представителей по некоторым из своих характеристик. Нередко изучение подобных объектов позволяет открыть что-то новое, существенно экономя время исследователя на проверке всех «типичных» объектов группы;
• 3) кластеризация также позволяет формировать более эффективное описание реальности и обладает иллюстративной силой, так как не требует перечисления всех свойств каждого объекта группы, предоставляя возможность увидеть общую картину, не вдаваясь в несущественные подробности.

Типичная схема процесса кластерного анализа включает:

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

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

По способу организации кластеров алгоритмы кластеризации можно разделить на плоские и иерархические. Плоские алгоритмы формируют кластеры одного ранга, т. е. фактически простой список групп. Иерархические — дают систему вложенных разбиений, т. е. организуют исходные данные в древовидную структуру, корнем которого является кластер, включающий весь массив исходных данных, а листьями — одиночные точки анализируемой выборки. По способу построения вложенных разбиений иерархические алгоритмы можно разделить на: восходящие (агломерирующие) и нисходящие (разделяющие). Первая подгруппа начинает с листьев (отдельных точек) и в серии итераций объединяет близкие точки в более крупные кластеры. Нисходящие алгоритмы, напротив, начинают с корневого кластера, последовательно разделяя на субкластеры вплоть до листьев.

На основе дополнительных характеристик, связанных с механизмами представления и обработки исходных данных, можно выделить:

• • алгоритмы, оперирующие мерами близости/расстояния объектов множества;
• • алгоритмы, работающие с векторами характеристик;
• • вероятностные алгоритмы, основанные на порождающей модели (например, НММ-кластеризация семейств последовательностей);

• • граф-ориентированные — предназначенные для анализа информации, представленной в виде сетей (разного рода карты связей/взаимодействия);
• • бикластеризации — обработка данных серии экспериментов над множеством образцов, заключающаяся в выделении наборов строк и столбцов матрицы результатов, с определенными паттернами распределения значений.

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

Меры расстояния, применяемые в алгоритмах кластеризации. Самой простой является евклидова мера расстояния.

где х, у — элементы множества, между которыми определяется расстояние, а суммирование производится по компонентам векторов х_ь у, описывающих соответствующие объекты.

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

В качестве мер расстояния для биологических данных типично использование коэффициента корреляции Пирсона, ранговой корреляции Спирмена или корреляционной меры, принятой в теории информации, — совместной информации (MI).

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

Задача бикластеризации. При анализе данных экспериментов, проведенных по чип (шстос/ф)-технологиям, например при анализе уровня экспрессии генов в различных условиях, подразумевают наличие корреляции уровня экспрессии для связанных генов. Однако далеко не всегда подобная корреляция наблюдается при всех возможных вариантах опыта: так, при разбиении по типам тканей могут экспрессироваться не все элементы биологического каскада (рис. 2.32).

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

• • бикластеры постоянного значения (а^ = с);
• • бикластеры строк одинаковых значений (а у = т + а,);
• • бикластеры столбцов одинаковых значений (а^ = т + cij);
• • бикластеры аддитивно совместимых значений;
• • бикластеры мультипликативно совместимых значений;
• • бикластеры согласованного изменения.

Рис. 2.32. Пример задачи бикластеризации, когда в данных по проверке уровня экспрессии трех генов в 10 разных условиях (а) при кажущемся отсутствии корреляции использование только части условий {2, 3, 5, 8} решает проблему (б)

Рис. 2.33. Возможные типы кластеров (слева направо): постоянного значения, строк одинаковых значений, столбцов одинаковых значений, аддитивно совместимых значений, мультипликативно совместимых значений и согласованного изменения

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

Рис. 2.34. Возможные комбинации расположения бикластеров на матрице результатов.