Распознавание образов.

 

Практические задачи

•        Распознавание рукописных букв (FineReader)

•        Отпечатки пальцев, распознавание речи,

•        Аэрофотосъемка, определение свой/чужой (военные)

•        Автоматический анализ ЭКГ, ЯМР, постановка диагноза,

…

 

Ключевые слова: методы распознавания образов, pattern recognition, machine learning,

 

Вход: новый объект

Выход: предсказание класса объекта

 

Пример №1: автоматическое предсказание сорта зерен пшеницы по одномерному электрофорезу. 40 сортов. ~ 80 дорожек каждого сорта

 

 

 

Пример №2: автоматическая постановка диагноза “рак яичника” по данным ИФА и масс-спектрометрии. Выборка образцов плазмы: 38 здоровых, 67 больных

 

 

 

Выделение признаков

Цель: выделить признаки объектов, удобные для классификации

 

в идеале:

•        объекты из одного класса должны иметь схожие значения

•        объекты из разных классов должны иметь разные значения

 

 

Примеры признаков:

 

Определение сортов пшеницы

•        профиль оптической плотности вдоль дорожки

 

Классификация рака яичника

•        интенсивность и положение пиков масс-спектра

•        пол, возраст пациента

•        результаты ИФА

 

 

Два типа задач:

 

1)Есть набор объектов. Нужно сгруппировать похожие объекты между собой (если группировка осмысленна!).

Это обучение без учителя (кластерный анализ)

 

 

 

2) Дополнительно есть информация о классах объектов. Нужно “обучиться” на этой информации

Это обучение с учителем: нейронные сети, теорема Байеса,

 

 

 

Обучение без учителя

 

Кластеризация – объединение схожих объектов в группы (кластеры).

 

Обычно нужно заранее задавать число кластеров

 

Нужно некоторым образом определить, как считать расстояние между объектами.

 

•        Иерархическая кластеризация: последовательность объединения объектов на различных уровнях сходства (дендрограмма)

метод средней связи, метод полной связи, метод Уорда, …

•        Разделяющая кластеризация: напрямую возвращает состав кластеров

Метод k-средних, PAM,…

 

 

 

 

 

Пример кластерного анализа в виде heatmap. Каждый столбец – объект, каждая строка – переменная (признак). Цветом кодируется значение. Полоса под дендрограммой объектов – истинные значения классов. Видно, что в данном случае кластерный анализ дает безошибочное разделение на 2 группы. Кластеризация признаков позволяет определить, какие группы переменных похожи друг на друга.

 

 

Обучение с учителем

 

Задача – построить решающее правило, которое позволит относить вновь обработанный образец в тот или иной класс.

 

нейронные сети, SVM, decision trees

 

•        Требуется большая выборка с заранее отклассифицированными объектами.

•        Обычно работает лучше чем обучение без учителя.

•        Кросс-валидация – при отсутствии тестовой выборки.

•        Проблема переобучения (overfitting)

 

 

Задача: построить решающее правило ¦, которое хорошо описывает данные, т.е. найти отображение

 

 

Обучающая и тестовая выборки

 

 

Проблема: обобщение и переобучение

Компромисс в выборе решающего правила:

q      не должно быть слишком простым (чтобы дать достаточную точность)

q      не должно быть слишком сложным (чтобы хорошо работало на новых объектах, не входящих в обучающую выборку)

 

 

 

 

Кросс-валидация: проверка классификации

 

•        Главное - не тестироваться на том, на чем обучались! Иначе оценка ошибки будет чересчур оптимистичной

•        Кросс-валидация применяется при малом объеме выборки

•        Разделить всю выборку на K частей

 

•        Для каждого k=1..K: сформировать тестовую выборку как k-я часть. Для обучающей выборки – все остальное. Обучить классификатор на обучающей выборке, протестировать на тестовой выборке. Общая ошибка классификатора оценивается как среднее всех ошибок.

 

 

Уменьшение числа переменных (отбор признаков)

dimensionality reduction , feature selection

 

Большое число признаков (обычно стандарт в крупномасштабных биологических экспериментах):

 

•        Усложняет анализ данных

•        Обычно не все признаки имеют биологическую интерпретацию

•        Часто целью является отбор значимых признаков

•        Ухудшает работу классификации. Переобучение.

•        применение dimensionality reduction перед классификацией

 

Этапы решения практических задач

-        формализация предметной области
(формализация признаков, определение набора классов)

 

-        формирование обучающей выборки

 

-        снижение размерности пространства признаков

 

-        обучение («с учителем», «без учителя»)

 

-        распознавание

 

-        адаптация (если качество обучения признано неудовлетворительным)

 

- обратная задача распознавания (определение набора признаков наиболее характерных для объектов заданного класса)

 

Распознавание образов в биоинформатике

Экспериментальные технологии:

-        экспресс-методы ДНК сиквенирования

-        транскриптомные ДНК микрочипы

-        системы детекции белков (белковые чипы, масс-спектрометрия, …)

-        системы детекции метаболитов (ЯМР, МС)

-        флуоресцентная микроскопия клеток

-        автоматизированный анализ тканевых срезов

-        …

 

Вычислительные технологии:

-        информационные ресурсы

-        методы анализа последовательностей

-        методы смыслового анализа публикаций

-        молекулярное моделирование и докинг

-        методы анализа количественного соотношения структура-активность (QSAR)