- •Анализ и интерпретация его результатов
- •Типология задач кластеризации Типы входных данных
- •Цели кластеризации
- •Методы кластеризации
- •Формальная постановка задачи кластеризации
- •Применение в биологии
- •В информатике
- •Кластеризация документов
- •Алгоритмы семейства forelТекущая версия (не проверялась)
- •Нейронная сеть Кохонена
- •Слой Кохонена [править] Базовая версия
- •[Править] Геометрическая интерпретация
- •[Править] Сети векторного квантования
- •[Править] Самоорганизующиеся карты Кохонена
- •[Править] Идея и алгоритм обучения
- •[Править] Самоорганизующиеся карты и главные многообразия
- •[Править] Упругие карты
[Править] Самоорганизующиеся карты и главные многообразия
Идея самоорганизующихся карт очень привлекательна и породила массу обобщений, однако, строго говоря, мы не знаем, что мы строим: карта — это результат работы алгоритма и не имеет отдельного («объектного») определения. Есть, однако, близкая теоретическая идея — главные многообразия (principal manifolds).[8] Эти многообразия обобщают линейные главные компоненты. Они были введены как линии или поверхности, проходящие через «середину» распределения данных, с помощью условия самосогласованности: каждая точка x на главном многообразии M является условным математическим ожиданием тех векторов z, которые проектируются на x (при условии x = P(z), где P — оператор проектирования окрестности M на M),
Самоорганизующиеся карты могут рассматриваться как аппроксимации главных многообразий и популярны в этом качестве[9].
[Править] Упругие карты
Основная статья: Упругая карта
Визуализация набора данных по экспрессии генов в раке молочной железы с использованием упругих карт (b) и метода главных компонент (c). Классы точек показаны с использованием размера (ER - статус эстроген-рецептора), формы (GROUP - риск развития метастаз) и цвета (TYPE - молекулярный тип опухоли). На панели (a) показана конфигурация узлов двумерной упругой карты в проекции на первые три главные компоненты. Сравнивая (b) и (c), можно заметить, что базальный тип опухоли как кластер лучше отделен на нелинейной проекции (b).
Метод аппроксимации многомерных данных, основанный на минимизации «энергии упругой деформации» карты, погружённой в пространство данных, был предложен А. Н. Горбанём в 1996 году, и впоследствии развит им совместно с А. Ю. Зиновьевым, А. А. Россиевым и А. А. Питенко.[7] Метод основан на аналогии между главным многообразием и эластичной мембраной и упругой пластиной. В этом смысле он является развитием классической идеи сплайна (хотя упругие карты и не являются многомерными сплайнами).
Пусть задана совокупность входных векторов S. Так же, как и сети векторного квантования и самоорганизующиеся карты, упругая карта представлена как совокупность кодовых векторов (узлов) Wj в пространстве сигналов. Множество данных S разделено на классы Kj, состоящие из тех точек , которые ближе к Wj, чем к другим Wl (). Искажение кодирования D
может трактоваться как суммарная энергия пружин единичной жёсткости, связывающих векторы данных с соответствующими кодовыми векторами.
На множестве узлов задана дополнительная структура: некоторые пары связаны «упругими связями», а некоторые тройки объединены в «рёбра жёсткости». Обозначим множество пар, связанных упругими связями, через E, а множество троек, составляющих рёбра жёсткости, через G. Например, в квадратной решётке ближайшие узлы (как по вертикали, так и погоризонтали) связываются упругими связями, а ребра жёсткости образуются вертикальными и горизонтальными тройками ближайших узлов. Энергия деформации карты состоит из двух слагаемых:
энергия растяжения
энергия изгиба
где λ,μ — соответствующие модули упругости.
Задача построения упругой карты состоит в минимизации функционала
U = D + UE + UG;
Если разбиение совокупности входных векторов S на классы Kj фиксировано, то минимизация U — линейная задача с разреженной матрицей коэффициентов. Поэтому, как и для сетей векторного квантования, применяется метод расщепления: фиксируем {Wj} — ищем {Kj} — для данных {Kj} ищем {Wj} — для данных {Wj} ищем {Kj} — … Алгоритм сходится к (локальному) минимуму U.
Метод упругих карт позволяет решать все задачи, которые решают самоорганизующиеся карты Кохонена, однако обладает большей регулярностью и предсказуемостью. При увеличении модуля изгиба μ упругие карты приближаются к линейным главным компонентам. При уменьшении обоих модулей упругости они превращаются в Кохоненовские сети векторного квантования. В настоящее время упругие карты интенсивно используются для анализа многомерных данных в биоинформатике.[10] Соответствующее программное обеспечение опубликовано и свободно доступно на сайте Института Кюри (Париж).[11][12]
На рисунке представлены результаты визуализации данных по раку молочной железы. Эти данные содержат 286 примеров с указанием уровня экспрессии 17816 генов[13]. Они доступны онлайн как ставший классическим тестовый пример для визуализации и картографии данных[14].