Обновлено 19.03.2010 Автор: Administrator
Относительно связный текст про распознавание образов и возможные применения в биоинформатике. Уровень начальный, формул нет. Текст будет дорабатываться, критика и замечания приветствуются.Распознавание образов и биоинформатика
М.А.Пятницкий, ИБМХ РАМН
Варианты
задачи о распознавании образов
Обучение без
учителя (кластерный анализ)
Уменьшение
количества признаков.
Обобщение на
несколько классов
Этапы
решения практических задач
Распознавание образов (pattern recognition) – это набор статистических методов, позволяющих изучать различия между двумя и более группами объектов по нескольким переменным одновременно. В качестве примера можно привести следующую ситуацию (Ким et al, 1989). Группа экспертов исследует возможность переговоров с террористами, захватившими заложников. Их интересуют те особенности ситуации, при которых возможно безопасное освобождение заложников, даже если требования террористов не выполнены. Существует несколько переменных, предсказывающих благополучное освобождение заложников – число террористов, поддержка их местным населением, характер их устных заявлений, тип и количество оружия, отношение числа террористов к числу заложников и т. д. Изучая предыдущие инциденты, эксперты должны найти ответ на следующие вопросы: 1) какие из этих переменных могут быть полезными для предсказания судьбы заложников; 2) как эти переменные могут быть связаны в математическую функцию для предсказания наиболее вероятного исхода; 3) какова точность предсказания. Методы распознавания образов могут обеспечить получение необходимых данных.
Проблематика распознавания образов охватывает чрезвычайно обширный круг задач. Сюда можно отнести распознавание речи и рукописного текста, фильтрацию спама из электронной почты, проблемы идентификации свой/чужой для противовоздушной обороны, поиск лиц на фотографиях и т.д. Несмотря на кажущуюся легкость разрешения ряда подобных задач человеком, для компьютера это является несравненно более сложной задачей. Так, 3-летний ребенок безошибочно отличает, например, мужчин и женщин. Однако написание программы для автоматического определения пола по фотографии весьма сложно и нетривиально.
Особое развитие методы распознавания образов получили с развитием вычислительной техники в последние десятилетия. Дело в том, что многие алгоритмы из этой области требуют больших объемов вычислений, что было доступно ранее лишь специалистам. Совершенствование программных пакетов, повышение их дружественности к пользователю также стимулировало рост числа использования этих методов на практике.
Существует множество применений методов распознавания образов в биомедицине: автоматическая постановка диагноза по результатам анализа ЭКГ, ЭЭГ или результатов других лабораторных исследований, обработка изображений магнитно-резонасной и компьютерной томографии, идентификация личности по биометрическим показателям (отпечатки пальцев и сканирование радужной оболочки глаза). Одним из направлений биоинформатики является использование подобных методов для обработки результатов высокопроизводительных экспериментов по геномике, протеомике, метаболомике. Практически каждый исследователь сталкивается в той или иной степени с задачами по распознаванию образов.
Список практических приложений методов по распознаванию образов может быть продолжен до бесконечности, однако у всех перечисленных задач есть общее – автоматическая классификация класса изучаемых объектов, основываясь на различных признаках, характеризующих эти объекты.
Каждый объект задачи распознавания образов должен быть описан с помощью некоторого набора признаков. Например, при постановке диагноза больному (который рассматривается как объект) врача будут интересовать такие признаки как возраст, вес, артериальное давление, уровень гемоглобина в крови и другие данные лабораторных исследований.
Вообще
говоря, для описания сложных объектов (коими, без сомнения, являются пациенты) могут
быть использованы самые разнообразные признаки. Однако, в зависимости от
задачи, одни признаки могут оказаться полезными, в то время как другие не будут
иметь отношения к делу. Например, если ставится задача предсказать риск
развития гипертонической болезни, то врача скорее будут интересовать такие
признаки как систолическое давление и вес больного, а вовсе не цвет его глаз.
Выбирая, использовать в дальнейшем конкретный признак или нет, следует стремиться
к тому, чтобы объекты из одного класса имели схожие значения этого признака, а объекты из разных классов иметь разные
значения. Если объект характеризуется d признаками, то его можно
рассматривать как точку в d-мерном пространстве (пространстве признаков).
Наряду с понятием пространства признаков, важным параметром задачи распознавания образов является используемое число классов. Класс должен быть определен таким образом, чтобы каждое наблюдение принадлежало только к одному классу. Например, при автоматической постановке диагноза каждый пациент может быть отнесен либо к группе “имеющих заболевание”, либо к группе “здоровые”. В таких случаях говорят, что имеется задача бинарной классификации. Число классов может быть и больше двух. Например, при распознавании рукописных заметок (чем занимается, например, известная программа FineReader), каждая буква должна быть классифицирована как один из 33 возможных вариантов.
Иногда, в зависимости от задачи, исследователь может варьировать число возможных классов. Например, возможно, что вместо простой классификации больной/здоровый более осмысленно с клинической точки зрения решать более сложную задачу и рассматривать три класса: “здоровый”, “легкая форма заболевания” и “тяжелая форма заболевания”.
Предположим, что исследователю доступна большая выборка с историями болезни большого числа пациентов, включая результаты лабораторных анализов и т.д. Можно представить две различных постановки задачи.
Во-первых, исследователя может интересовать построение диагностического правила, которое позволит определять у вновь поступившего больного наличие указанного заболевания. В этом случае необходимо подготовить аналогичные данные по здоровым людям, а затем с помощью соответствующих математических методов и алгоритмов “обучить” классификатор распознавать, принадлежит ли каждый вновь исследуемый пациент к классу “больные” или к классу “здоровые”. Процесс построения такого диагностического правила называется “обучением с учителем”, поскольку для этого необходимо иметь выборку объектов с заранее известными классами (т.н. обучающая выборка). Классификатор “обучается” на этой информации и строит решающее правило, позволяющее определять класс каждого нового объекта, не входившего в обучающую выборку. Решающее правило можно наглядно представить в виде поверхности в пространстве признаков. Отнесение объекта в один из двух классов зависит от того, с какой стороны этот объект окажется от разделяющей поверхности в пространстве признаков. Также исследователя может интересовать вопрос о том, какие показатели имеют наибольший вес в диагностическом правиле, а какие показатели никак не связаны с наличием заболевания.
Другая ситуация возникает, если целью исследования является изучение структуры имеющихся данных и определение числа классов, на которые могут быть сгруппированы объекты. Например, необходимо решить, является ли имеющаяся выборка больных однородной или же существует несколько подтипов заболевания (а следовательно нужно применять различные методики лечения и т.д.). Такая постановка задачи называется “обучением без учителя”, поскольку классы изучаемых объектов заранее неизвестны. При обучении без учителя ставится цель понять структуру имеющихся данных, разбив их на несколько групп, которые объединяют похожие между собой в некотором смысле объекты. Такие группы называются кластерами, поэтому обучение без учителя также называют кластерный анализ. При этом объекты внутри одного кластера более схожи между собой, чем объекты из разных кластеров.
Рисунок 1. А). Обучение без учителя (кластерный анализ).
Имеющиеся объекты разбиваются на группы (кластеры). Объекты внутри кластера
более схожи между собой, чем объекты из разных кластеров. Классы объектов из
исходной выборки неизвестны. Число кластеров обычно задается как параметр. Новый
объект классифицируется как принадлежащий наиболее близкому кластеру. Б).
Обучение с учителем. Имеется выборка, в которой классы объектов известны
заранее. В процессе “обучения” классификатора в пространстве признаков строится
решающее правило, дискриминирующее объекты по классам. Класс нового объекта определяется
в результате применения к нему решающего правила.
Таким образом, задачи обучения без учителя и
обучения с учителем принципиально различаются между собой, что
проиллюстрировано на рисунке 1, где приведены объекты, характеризующиеся двумя
признаками – x1 и x2. Соответственно при решении обоих типов задач применяются разные
алгоритмы и возникают различные аспекты, что будет рассмотрено чуть более
подробно.
Обучение без учителя или кластерный анализ – это группирование (кластеризация) множества объектов таким образом, чтобы все объекты, принадлежащие одной группе (кластеру), были более похожи друг на друга, чем на объекты других кластеров.
Например, при анализе результатов транскриптомных экспериментов (биочипы, microarray) кластерный анализ используется для обнаружения групп генов, которые обладают схожими профилями экспрессии. В этом случае гены являются объектами, а признаками служит уровень экспрессии при разнообразных воздействиях, например лекарственных. Такие группы генов часто кодируют функционально взаимосвязанные белки, такие как ферменты определенного метаболического пути.
Можно перечислить несколько дополнительных целей, которые преследуются при кластерном анализе, помимо выявления структуры данных и классификации. Во-первых, при работе с неоднородной выборкой все последующие статистические расчеты должны вестись с каждым кластером в отдельности (реализация принципа “разделяй и властвуй”). В противном случае рассчитанные значения статистик (среднее, дисперсия и т.д.) будут показывать “среднюю температуру по больнице”. Во-вторых, может быть необходимым выявить наиболее типичного представителя каждого кластера и использовать его в качестве некоторого эталона. Наконец, с помощью кластерного анализа можно выявлять нетипичные объекты, т.н. “выбросы”.
Различные
алгоритмы кластерного анализа можно разделить на два основных класса: иерархические и итеративные
методы (неиерархические). Результатом работы иерархических методов является
последовательность объединения объектов в кластеры на различных уровнях
сходства (дендрограмма). Примерами могут служить методы ближней, средней и
полной связей, метод Уорда, метод DIANA. Неиерархические алгоритмы
кластеризации напрямую возвращают состав кластеров. Наиболее популярны метод k-средних
(k-means), карты Кохонена, различные
подходы с применением теории графов.
За последние десятилетия предложены десятки методов кластерного анализа и их различные модификации. Такое разнообразие объясняется тем, что не существует однозначно наилучшего критерия качества кластеризации. Соответственно, разные алгоритмы дают различный результат, а выбор определенного варианта кластерного анализа зависит от специфики исследуемой задачи.
Следует отметить, что в большинстве алгоритмов необходимо указывать a priori либо число кластеров, на которое будет произведено разбиение, либо определять различные параметры, также косвенно влияющие на число результирующих кластеров. Поэтому обычно кластерный анализ применяют несколько раз, варьируя число кластеров, а затем выбирают наилучшее разбиение объектов, используя различные критерии.
В качестве примера рассмотрим применение одного из методов иерархического кластерного анализа – метода средней связи. На рисунке 2А приведены 8 объектов, характеризующихся 2 признаками. Поскольку никакой информации о классах объектов нет, то можно применять только обучение без учителя – кластерный анализ.
Предварительное изучение расположения объектов друг относительно друга показывает, что вероятнее всего присутствуют три кластера. При этом в первый кластер входят объекты №1, №2 и №3, второй кластер составляют объекты №4-№7, а объект №8 сильно отличается от остальных объектов, формируя отдельный кластер.
Согласно методу средней связи (average linkage) первоначально считается, что каждый объект представляет собой кластер. Таким образом, исходно имеется 8 кластеров, каждый из которых состоит из одного объекта. Далее рассчитываются все попарные расстояния между объектами. Заметим, что здесь возможны различные определения понятия ”расстояния между объектами” – может использоваться, например, расстояние Махаланобиса, расстояние Хэмминга, различные варианты коэффициента корреляции и т.д. Выбор различной меры расстояния между объектами определяется спецификой задачи. Однако в настоящем примере мы будем использовать “обычное” расстояние – евклидово.
После того, как определены все попарные расстояния, выбираются два объекта с наименьшим расстоянием, в нашем случае это объекты №6 и №7. Считается, что эти два объекта формируют кластер, соответственно общее число кластеров становится равным 7. Далее матрица расстояний пересчитывается, причем ранее объединенные в один кластер объекты считаются одним объектом с усредненными по кластеру параметрами. При этом расстояние между двумя кластерами Ci и Cj определяется как расстояние между их центрами тяжести:
|
|
(1) |
где
– число белков в i-ом
кластере, 
– расстояние между объектами.
Далее находятся и объединяются два других наиболее близких кластера и т.д. На каждом шаге число кластеров уменьшается, пока все объекты не окажутся принадлежащими одному кластеру.
Процесс объединения объектов в кластеры удобно иллюстрировать с помощью специального графика – дендрограммы (см. рисунок 2Б). Дендрограмма показывает, на каком уровне сходства объекты объединялись в кластеры. Так, на рисунке видно, что первоначально были объединены в кластер объекты №6 и №7, поскольку расстояние между ними минимально. На следующем шаге объединяются объекты № 2 и №3,а далее объединяются объекты № 4 и №5. Наконец, при расстоянии между объектами равным 1,0 объединяются в один кластер два кластера, состоявших ранее из №6-7 и №4-5. Объект №8 включается в состав единственного кластера последним, что означает его максимальную удаленность от остальных объектов.
Рисунок 2. А. Исходная выборка из 8 объектов, характеризующихся 2 признаками. Б. Последовательность объединения объектов в кластеры на различных уровнях сходства –дендрограмма. Для получения состава кластеров необходимо задаться порогом отсечения (показано пунктиром). В. Три кластера, полученных при выбранном пороге отсечения.
Однако, построенная дендрограмма еще не является искомым разбиение объектов на группы. Как уже говорилось, для большинства алгоритмов кластерного анализа необходимо заранее задавать количество кластеров в той или иной форме, и метод средней связи не является исключением. Для получения состава кластеров необходимо, задавшись некоторым пороговым значением уровня сходства, провести сечение дендрограммы. Так, на рисунке 2Б показано сечение при уровне сходства 1,4. В результате пересечения ветвей дендрограммы можно проследить состав получаемых кластеров. В настоящем примере получаются три кластера: (№8), (№4-№7), (№1-№3). Разбиение на указанные три кластера показано на рисунке 2В, где объекты из одного кластера отмечены одинаковым символом. При другом уровне отсечения будет получаться другой состав кластеров. Например, при уровне отсечения равном 2,0 результатом будут являться два кластера: (№8) и (№1-№7). Существуют различные подходы, которые позволяют оценить оптимальный уровень отсечения дендрограммы и следовательно, наиболее вероятное количество кластеров.
Обучение с учителем или машинное обучение (machine learning) – это извлечение информации из известных примеров, которая используется для последующей классификации новых данных. Для этого необходим набор объектов с заранее известными классами – так называемая обучающая выборка. Например, для предсказания наличия рака яичника с помощью масс-спектрометрического профилирования сыворотки, необходимо иметь как образцы сыворотки женщин с гистологически подтвержденным диагнозом, так и образцы сыворотки женщин, не страдающих данным заболеванием. В процессе обучения классификатора строится разделяющая поверхность (граница) между объектами указанных классов из обучающей выборки.
Для проверки пригодности использования построенного классификатора в клинической практике необходимо оценить точность предсказания. Для этого необходимо иметь в распоряжении так называемую тестовую выборку – дополнительную коллекцию образцов с заранее известным диагнозом, но не входивших обучающую выборку. Диагностика образцов сыворотки (объектов) из тестовой выборки происходит путем последовательного применения найденного решающего правила. По количеству ошибок на тестовой выборке можно судить о применимости созданной диагностики заболевания.
Необходимо подчеркнуть основное правило для оценки точности классификатора – “никогда не тестироваться на объектах из обучающей выборки”. Как правило, классификатор с высокой точностью разделяет объекты из обучающей выборки. Но это ни в коей мере не является свидетельством в пользу того, что сравнимая точность будет достигнута на тестовой выборке и далее при практическом использовании..
В качестве примеров наиболее популярных алгоритмов обучения с учителем можно назвать нейронные сети, метод опорных векторов, метод k-ближайших соседей, деревья решений. Мы не будем останавливаться на особенностях реализации конкретных методов. Вместо этого будут рассмотрены аспекты обучения с учителем, не зависящие от используемого алгоритма классификации, но весьма важные для корректного практического применения.
Важные понятия из области обучения с учителем это обобщение (generalization) и переобучение (overfitting). Обобщение – это способность классификатора правильно предсказывать классы тех объектов, которых он раньше никогда не “видел”, то есть объектов, не входивших в обучающую выборку. Высокая обобщающая способность классификатора означает его пригодность к применению в реальном мире. Проблема состоит в том, что оценить обобщающую способность классификатора заранее невозможно, поскольку исследователь располагает только имеющимися у него данными. Поэтому кажется разумным настроить алгоритм классификации таким образом, чтобы, по крайней мере, на обучающем множестве ошибки были минимальными.
На рисунке 3 приведены примеры разделяющих поверхностей между объектами двух классов в пространстве двух переменных x1 и x2. Очевидно, что использование слишком простой разделяющей поверхности (прямой) не позволяет достичь приемлемой ошибки как для обучающего множества, так и для тестового примера (рисунок 3А). В тоже время легко построить разделяющую поверхность, описываемую многими параметрами, которая позволит достичь 100%-точности при работе на обучающей выборке, однако будет с большей вероятностью ошибаться на новых объектах (рисунок 3Б). В этом случае говорят, что произошло переобучение, то есть классификатор чрезмерно подстроился под обучающие данные, но его обобщающая способность по-прежнему низка. Таким образом, необходимо искать баланс между сложностью решающего правила и способностью классификатора к обобщению (рисунок 3В).
Рисунок 3. Иллюстрация понятий обобщения и переобучения. А. Слишком простое решающее правило – малая точность на обучающей выборке. Б. Большое количество параметров решающего правила часто ведет к переобучению – классификатор безошибочен на обучающей выборке, но плохо работает на тестовой (слабая обобщающая способность) В. Баланс между сложностью решающего правила и способностью классификатора к обобщению.
Выбор правильной степени “сложности” классификатора представляет собой нелегкую задачу. Почти всегда классификатор с большим числом настраиваемых параметров (например, нейронные сети) покажет меньшую ошибку, однако это может свидетельствовать не о хорошем качестве модели, а о переобучении. В то же время алгоритм с относительно малым числом параметров (например, метод k-ближайших соседей) не всегда может обеспечить наибольшую точность классификации. Таким образом, желательно иметь хотя бы приблизительную оценку количества варьируемых параметров (степеней свободы) у выбранного алгоритма классификации, что может дать представление о возможности переобучения.
Не стоит забывать и о том, что построенное решающее правило можно использовать для получения дополнительных знаний о предметной области. В этом плане преимущество имеют методы распознавания образов, параметры которых могут быть интерпретированы в терминах специфики решаемой задачи.
Стандартная схема применения методов обучения с учителем состоит в разделении всех имеющихся данных на две части – обучающую и тестовую выборки. В процессе обучения классификатора формируется решающее правило, позволяющее правильно предсказывать класс объектов из обучающей выборки. После завершения подстройки классификатора под обучающую выборку, сформированное правило применяется для тестовой выборке. Результат предсказания сравнивается с истинными классами объектов тестовой выборки, что позволяет оценить точность построенного классификатора. Поскольку объекты из тестовой выборки классификатору не предъявлялись в процессе обучения, то такая оценка является объективной.
К сожалению, использовать приведенную схему оценки точности классификации не всегда удается. В случае сложных алгоритмов распознавания образов (например, нейронных сетей) необходимо подстроить значения множества параметров. Это означает, что при обучении с учителем желательно иметь как можно больше объектов в обучающей выборке, иначе алгоритму классификации может не хватить информации для построения решающего правила с приемлемой точностью работы. Также очевидно, что тестовая выборка тоже должна быть достаточно большой для оценки качества классификации с требуемой точностью. На практике же объем имеющейся выборки часто весьма ограничен, например в исследование можно включить десятки пациентов, но редко сотни и тысячи.
Представим, что имеются данные о 100 больных с диагнозом меланома или невус. Необходимо построить классификатор, позволяющий дискриминировать эти два заболевания. Предположим, что мы распределили все имеющиеся данные на обучающую и тестовую выборки в соотношении 9:1, то есть для построения решающего правила будут использованы сведения о 90 больных, а проверка будет проведена на оставшихся 10 больных. Ясно, что в таком случае оценка точности классификации будет крайне грубой. Например, из 10 тестовых случаев были корректно предсказаны 8. Можно ли сказать, что точность классификатора составила 80% или же это случайность и при другом разделении данных на обучающую и тестовую выборки будет правильный диагноз будет предсказан только в половине случаев? Таким образом, необходимо найти компромисс между наибольшим размером обучающей выборки и точностью оценки доли случаев ошибок классификации.
Для решения этой проблемы часто применяют процедуру кросс-валидации. С этой целью все имеющиеся данные разделяют на k частей (блоков), см. рисунок 4. Обычно k задают равным 5 или 10 и говорят о 5-кратной или 10-кратной кросс-валидации. В предельном случае задают k равным количеству объектов, тогда тогворят о кросс-валидации с исключением по одному. На каждом шаге процедуры кросс-валидации k–1 блоков данных объединяют в обучающую подвыборку, а оставшийся блок соответствует тестовой подвыборке. Затем обучают классификатор на обучающей подвыборке и определяют долю ошибок на тестовой подвыборке. Далее вся последовательность повторяется, но в качестве обучающей и тестовой подвыборок используют уже другие блоки данных.
Рисунок 4. Процедура кросс-валидации для оценки точности работы классификатора. Цветом показаны обучающая и тестовая подвыборки. Пояснения в тексте.
Итоговую оценку точности работы классификатора вычисляют как среднее значение точности на каждом шаге. Таким образом, с помощью процедуры кросс-валидации удается максимально полно использовать имеющуюся выборку для оценки точности классификации (способности к обобщению). Таким же образом оцениваются и другие меры качества классификации – чувствительность и специфичность.
Необходимо подчеркнуть, что кросс-валидацию необходимо использовать только в том случае, если количество данных слишком мало для формирования достаточно больших обучающих и тестовых выборок. Если же имеется достаточное количество объектов, то рекомендуется использовать классическую схему для оценки классификации. Другой недостаток процедуры кросс-валидации – высокие вычислительные затраты, поскольку на каждом шагу проводят обучение классификатора.
Безусловно, построение классификаторов, которые работают безошибочно, возможно далеко не всегда. Это может быть связано с несовершенством выбранных признаков и/или с недостатками применяемого математического метода. Также сама задача может не допускать 100%-корректного предсказания в силу формальных ограничений.
Таким образом, в реальных задачах обычно сталкиваются с ошибками классификаторов. При этом “цена” различных видов ошибок может быть различной. Рассмотрим двуклассовую задачу автоматического постановки диагноза “инфаркт” по ЭКГ. При этом возможны два типа ошибок. Если пациент на самом деле здоров, а классификатор предсказывает развитие инфаркта, то такая ошибка называется ложно-положительной или ошибкой первого типа. Если же у пациента развивается инфаркт, а в результате применения классификатора он отнесен к классу “здоровые”, то в этом случае совершается ложно-отрицательная ошибка или так называемая ошибка второго типа. Ясно, что для данной задачи цена ошибки второго типа (неназначение лечения больному) намного выше, чем цена ошибки первого типа (назначение лечения, которое на самом деле не требуется).
На рисунке 5 представлены возможные варианты соотнесения результата классификации и “правильного ответа” (золотого стандарта), представляющего собой обычную таблицу сопряженности 2x2. Продолжая пример, в таблице класс “–” означает отсутствие инфаркта, класс “+” обозначает наличие инфаркта.
Рисунок 5. Возможные варианты соответствия результатов классификации и золотого стандарта.
Для формальной оценки точности классификатора необходимо разделить число правильных ответов (т.е. когда результат классификации совпал со значением золотого стандарта) на общее число предсказаний:
Помимо точности вводят другие меры оценки работы классификатора: чувствительность и специфичность. Чувствительность представляет собой ошибку классификатора на объектах, которые согласно золотому стандарту принадлежат к классу “+”, т.е. на пациентах с диагнозом “инфаркт”:
Специфичность – ошибка классификатора на объектах класса “–”, т.е. на здоровых:
Идеальный классификатор имеет 100%-ную чувствительность и специфичность. В зависимости от задачи многие алгоритмы распознавания образов могут быть специальным образом изменены, чтобы минимизировать частоту одного из типов ошибок, но при этом увеличивается частота совершения ошибок другого типа.
Отличительной особенностью современных высокопроизводительных (high-throughput) экспериментов является большое значение переменных, характеризующих объект исследования. Так в результате протеомных экспериментов могут быть получены сотни электрофоретических пятен или пиков на масс-спектрах. Еще больше данных получается в результате транскриптомных экспериментов – для каждого образца измеряется относительная концентрация десятков тысяч мРНК.
Если количество признаков сопоставимо или превышает количество объектов (так называемое проклятие размерности, curse of dimensionality), то это сильно затрудняет работу алгоритмов классификации, способствуя переобучению. Для многих современных биологических методик число переменных обычно на порядок превосходит число анализируемых образцов. Поэтому стандартной практикой перед применением собственно методов распознавания образов, является уменьшение размерности пространства признаков (dimensionality reduction), то есть отбрасывание части переменных.
Часто основной целью исследования является именно отбор дискриминирующих между классами переменных. Например, при изучении молекулярных механизмов развития рака, особый интерес представляют гены, имеющие различные уровни экспрессии в нормальной ткани и в опухоли. С помощью технологий транскриптомики (методы microarray и SAGE) можно определять уровни экспрессии для десятков тысяч генов, но по-настоящему важными являются только несколько десятков. Таким образом, необходимо произвести отбор потенциально важных признаков среди остальных переменных. При этом трудно отбросить какие-либо переменные исходя из априорных сведений и биологической специфики, поскольку любой ген/белок может оказаться биомаркером с приблизительно равной вероятностью.
Методы отбора переменных (feature selection) можно разделить на два типа, относительно того используется ли при этом сам классификатор или нет. В первом случае “качество” отобранных переменных определяется точностью классификации, которая при этом достигается. Оптимальным решением является полный перебор всех сочетаний переменных, поскольку при сложных взаимосвязях между признаками вполне возможны ситуации, когда две переменные по отдельности не являющиеся дискриминаторными, становятся таковыми при добавлении третьей переменной. Очевидно, что полный перебор вычислительно невозможен при сколько-нибудь значительном числе признаков. Попыткой преодолеть это является применение генетических алгоритмов для поиска оптимального набора переменных. Другой стратегией является пошаговое включение/исключение переменных по одной.
Вторая группа методов никак не опирается на методы классификации. Существующие переменные отбираются либо с помощью классических статистических тестов (критерии Стьюдента, Фишера), либо формируются новые переменные как линейные комбинации исходных признаков (метод главных компонент). Еще одним подходом является исключение сильно зависимых друг от друга переменных с помощью кластерного анализа. Из каждого кластера оставляется только одна переменная.
Большинство алгоритмов классификации разработаны для случая двух классов. При этом для многих задач необходима классификация на несколько групп, например при предсказании различных подтипов опухолей. Существует два основных подхода к обобщению бинарной классификации на несколько классов, представленных на рисунке 6.
Рисунок 6. Два подхода к мультиклассовой классификации, пояснения в тексте.
При подходе “один-против-всех” для каждого класса строится отдельный классификатор, дискриминирующий этот класс от всех остальных классов, а итоговая разделяющая поверхность строится как объединение соответствующих поверхностей. При подходе “один-против-одного” строится n(n-1)/2 классификаторов, разделяющих каждый класс от каждого. Новый объект присваивается тому классу, для которого классификатор в этом наиболее “уверен” – имеет наибольшее значение решающей функции.
Методы распознавания образов применяются практически во всех областях биоинформатики. Это связано с огромным количеством данных, которые накоплены в результате развития современных экспериментальных методик – миллионы белковых последовательностей, паттерны экспрессии десятков тысяч генов, тысячи исследовательских публикаций. Объем получаемых данных намного больше того, который может осмыслить человек, поэтому, пожалуй, основной целью применения методов распознавания образов в постгеномной биологии является извлечение новых знаний (data mining) о молекулярных механизмах функционирования клетки в норме и патологии.
Существует несколько аспектов, характерных для экспериментальных результатов современной биомедицины. Во-первых, каждый объект характеризуется большим количеством признаков, как правило, намного превышающим количество образцов. Как уже отмечалось, это затрудняет работу методов обучения с учителем и способствует переобучению классификаторов. Далее, существуют сложные взаимосвязи между этими переменными. Подразумевается, что эти взаимосвязи отражают важные биологические закономерности, которые далеко не все изучены. Наконец, объект может описываться с помощью различных типов данных. Например, для предсказания функции белков можно использовать сети белок-белковых взаимодействий описываемые в виде графов, последовательности аминокислотных остатков как строки из 20-символьного алфавита, тексты публикаций описывающих эксперименты с указанным белком. Соответствующий алгоритм предсказания функции белка должен интегрировать указанные типы данных.
Приведем несколько примеров, иллюстрирующих типовые задачи распознавания образов, встречающиеся в биоинформатике.
Многие свойства белков также удается предсказывать, используя методы обучения с учителем – трехмерную структуру, принадлежность к определенному семейству, внутриклеточную локализацию, паттерны пострансляционной модификации, гидрофильные и гидрофобные участки. Для этого формируют обучающую выборку, состоящую из двух классов: белков обладающих интересующим свойством (например, локализованных на мембране) и белков этим свойством не обладающих. Иногда в качестве второго класса используют случайным образом сгенерированные последовательности аминокислотных остатков.
В результате секвенирования генома получается длинная последовательность нуклеотидов, для которой необходимо определить границы генов и экзон-интронную структуру. Для этого используют алгоритмы распознавания, обученные на заранее размеченных геномных последовательностях.
В качестве объектов для распознавания могут быть использованы различные изображения. Важной с точки зрения клиники является задача автоматического анализа изображений мазков крови с помощью роботизированной микроскопии. В этом случае классификатор распознает классы клеток крови и подсчитывает лейкоцитарную формулу. Другим примером является предсказание внутриклеточной локализации белков по данным флуоресцентной микроскопии.
Широко применяются методы обучения с учителем для анализа результатов экспериментов по протеомике и транскриптомике. В обоих случаях типовой задачей является построение диагностического правила и поиск биомаркеров для различных заболеваний, в первую очередь онкологических. Для этого классификатор обучают, используя профили экспрессии генов или белков для различных групп, например рак/норма. Подразумевается, что внедрение в клиническую практику методов экспресс-анализа протеома и транскриптома поможет диагностике заболеваний на ранних стадиях.
Последнее время бурно развиваются методы компьютерного конструирования лекарств. Одной их важнейших задач этой области является предсказание возможности использования различных молекул в качестве лекарств (drug-likeness). Применимость конкретного соединения в качестве лекарственного средства зависит от сочетания многих молекулярных свойств, влияющих на фармакодинамику и фармакокинетику – растворимости, количества атомов-доноров и атомов-акцепторов водородной связи, молекулярного веса, распределения электронной плотности и т.д. Указанные свойства представляются как молекулярные дескрипторы (количественные переменные), с тем чтобы максимально сохранить всю информацию о химии соединения. Далее формируется обучающая выборка, состоящая из известных лекарственных соединений и веществ, таковыми не являющимися. Если удается построить классификатор, способный с достаточной точностью различать соединения двух классов, то можно использовать компьютер в качестве средства для виртуального скрининга миллионов соединений-кандидатов, избегая, таким образом, дорогостоящих экспериментов.
Можно сформулировать следующую последовательность действий при решении практических задач по распознаванию образов (при обучении с учителем).
1. Формализация предметной области – определение набора признаков, которые характеризуют объект, а также определение количества классов. Действия на этом шаге обусловлены спецификой решаемой проблемы – в некоторых ситуациях исследователь может варьировать эти значения (например, можно выбрать типы необходимых лабораторных анализов), а иногда признаки фиксированы (например, прибор детектирует флуоресценцию только по 4 каналам).
2. Формирование обучающей и тестовой выборок. Здесь действуют те же правила, что и при статистическом анализе – объем выборки должен быть по возможности максимальным. Также желательно, чтобы обучающая выборка была сбалансированной – объекты различных классов входить примерно в равной пропорции.
3. Уменьшение размерности пространства признаков – отбрасывание “лишних” переменных для предотвращения переобучения и улучшения точности распознавания. Наиболее часто применяется при анализе результатов транскриптомных и протеомных экспериментов.
4. Выбор конкретного алгоритма классификации и обучение на имеющихся данных. Здесь многое определяется спецификой проблемы, а также предпочтениями исследователя.
5. Проверка обобщающей способности классификатора – применение для тестовой выборки, оценка точности, чувствительности и специфичности классификации. Если количество имеющихся данных невелико, то используют процедуру кросс-валидации.
6. Если качество классификации неудовлетворительно, то возвращаются к шагу 3 – изменяют используемый набор признаков, варьируют параметры алгоритма классификации и т.д.
7. После построения классификатора, хорошо работающего на тестовой выборке, часто решают обратную задачу: определяют набор признаков, наиболее характерных для объектов заданного класса. Это позволяет выдвинуть гипотезы о возможном механизме изучаемого явления, что в свою очередь позволяет спланировать дизайн нового эксперимента для их проверки. Применение методов распознавания образов как элемента в цепи получения новых знаний проиллюстрировано на рисунке 7.
Рисунок 7. Использование методов распознавания образов для получения новых знаний.
В биологии и медицине задачи, требующие применения кластерного анализа или обучения с учителем, встречаются практически на каждом шагу. При этом методы распознаванию образов могут быть использованы как в прикладной сфере (разработка нового способа диагностики), так и в фундаментальной (изучение молекулярных механизмов заболеваний). Современному исследователю следует быть подготовленным к этому.
1. Дуда Р., Харт П., Распознавание образов и анализ сцен, Мир, 1976, С.507
2. Ким Дж.-О., Мьюллер Ч.У., Клекка У.Р., Факторный, дискриминантный и кластерный анализ, Финансы и статистика, 1989, С. 216
| < Предыдущая | Следующая > |
|---|
Комментарии