Методы классификации

Ричард Бреретон, хемометрический центр Бристольского университета, Англия
Homepage of Chemometrics, Editorial, May 2004
CLASSIFICATION METHODS
Richard Brereton
Centre for Chemometrics, School of Chemistry
Cantock's Close, Bristol BS8 1TS, United Kingdom.

Для ученых-хемометриков классификация представляет собой одну из наиболее часто решаемых задач. При ее решении данные, получаемые в серии экспериментов, используются для разделения исследуемых образцов на одну или несколько групп. Одной из первых, и наиболее традиционных работ, посвященных этому направлению в многомерной статистике, принято считать работу Р. Фишера (1930 г.), в которой организмы разделялись на подвиды в зависимости от результатов измерений их физических параметров.

Техника многомерной классификации

Изначально технику анализа многомерных данных для решения проблем дискриминации разработали биологи при решении задачи классификации организмов. Обычно, чтобы разделить организм или растение на подвиды одного измерения недостаточно. Предположим, нам нужно определить какое из животных перед нами — мышонок или жук-носорог. Самый простой параметр, который мы можем измерить это длина. Но просто длины явно недостаточно для определения. Что если мы будем измерять другой параметр, например ширину? Однако этого тоже будет недостаточно, так как известно, что ширина жука-носорога может достигать ширины взрослой мыши (см. рисунок 1). То есть ни длина, ни ширина сами по себе не смогут помочь нам отличить жука от мыши. Поэтому здесь необходимо использовать одновременно данные нескольких измерений. Например, ширина жука-носорога больше его длины, следовательно, в нашем случае лучше рассматривать в качестве основного параметра отношение длины к ширине. Поэтому биологи обычно записывают результаты не одного, а серии измерений, используя которые вместе можно различить различные организмы. Некоторые, наиболее ранние работы по данной тематике оставляли сильное впечатление, например, наблюдения за несколькими измерениями тел позволило различить достаточно близко связанные друг с другом виды, что можно с большим успехом использовать при изучении окаменелых животных или растительных организмов. Исторически, биология, а в особенности таксономия, была и остается мощнейшей движущей силой для разработки многомерных методов классификации.

Рис.1. Сравнительные размеры жука-носорога, взрослой мыши и мышонка

Большинство читателей Homepage of Chemometrics наверняка хорошо разбираются в классических многомерных методах, таких как, например, МГК-классификация, PLS-дискриминация или SIMCA которые широко используются известными научными группами. Однако, возможно некоторые из них не в курсе, что существует множество подходов, которые не менее эффективно могут быть использованы в химии. Одной из наиболее вероятных причин такой плохой осведомленности является отсутствие программного обеспечения с достаточно дружественным интерфейсом, которое бы реализовывало эти методы. В хемометрике, зачастую, в таких программах реализованы методы десяти или двадцатилетней давности, в то время как реализация более новых — является уделом энтузиастов. Для того чтобы появилось очень качественное и надежное программное обеспечение, удобное в использовании и по приемлемой цене, потребуется несколько лет, поэтому тем, кто не имеет глубоких познаний в программировании, приходится пользоваться методами, предложенными ранее. Таким образом, менее известные подходы могут быть более эффективными, но для их использования нужно иметь хорошие технические знания, достаточные чтобы самому писать процедуры в среде MatLab, или пользоваться различными статистическими пакетами.

Одноклассовая дискриминация

В нашем обсуждении мы ограничимся одноклассовой дискриминацией и рассмотрим некоторые методы, с которыми, возможно, наши читатели не знакомы. Одноклассовый классификатор позволяет определить принадлежит ли образец к данному классу или нет. Если у нас имеется три класса, то необходимо построить три различных модели для каждого из них. Тогда первая модель позволит отличить образцы первого класса от образцов второго и третьего, вторая — образцы второго класса от образцов, принадлежащих первому или третьему и т.п. Зачастую подобные классификаторы концептуально более просты, нежели те, которые пытаются определить принадлежность образца, рассматривая одновременно два класса и более. Следовательно, любую задачу классификации можно свести к использованию нескольких одноклассовых классификаторов.

Любая такая задача преследует две основные цели:

Идеальный метод минимизирует оба типа ошибок. Обычно существует некоторый порог, который определяет, принадлежит ли образец некоторому классу. Чем выше такой порог, тем метод более требователен к отбору, и тем меньше образцов будут приписаны данному классу и наоборот. Соответственно, при уменьшении порога мы ожидаем уменьшение ошибок первого рода, но, одновременно, увеличение ошибок второго рода.

Кривые мощности критерия

Для того чтобы понять, как работает тот или иной метод, можно воспользоваться кривой мощности критерия. Обычно, эту кривую применяют для тестового набора, но при необходимости ее можно использовать и при кросс-валидации, чем для обучающего набора образцов. При движении слева направо или снизу вверх мы видим, что количество образцов отнесенных к определенному классу увеличивается, отражая снижение порога. Идеальный метод, для которого число ошибочно принятых и ошибочно отклоненных образцов равно нулю будет представлен на графике точкой в левом верхнем углу. Каждый метод характеризуется площадью области под кривой. Чем больше данная площадь, тем лучше метод, так на рисунке второй метод, представленный черной кривой лучше, чем описываемый красной.

Рис. 2. Характеристические кривые операторов классификации

Если мы не можем найти идеальный метод, что же будет лучше для нас — уменьшить число ошибочно принятых или ошибочно отклоненных образцов? Большинство химиков привыкли к однозначным решениям, например, определить, является ли образец эфиром или нет (т.е. ответ должен быть единственным и если анализ проведен грамотно он будет однозначным). Они не привыкли иметь дело со случаями, встречающимися, например, в биологии или медицинской диагностике, или в криминалистике, где часто определенного ответа просто не существует. Очень многое зависит от того, какие именно задачи нас интересуют. Рассмотрим, например, довольно важную область исследований — судебные рассмотрения. В большинстве судебных разбирательств в Англии необходимо представить улику, которая должна доказать вину безо всяких сомнений. На обвинении лежит ответственность за представление такой улики, и если имеются хоть какие-то весомые сомнения, осуждение будет весьма опасным шагом. Следовательно, основным приоритетом при выборе метода здесь будет уменьшение ошибочно принятых образцов. И если можно показать, что метод действительно использует этот критерий, наличие нескольких ошибочно отклоненных данных не будет играть существенной роли. В этом случае, кто-то может быть ошибочно оправдан, но для осуждения мы должны быть твердо уверены в неоспоримости его вины. Если же говорить о медицинской диагностике, то мы должны придерживаться противоположного правила, чтобы минимизировать ошибочно отклоненные образцы, так как это будет означать, что любые признаки болезни будут в дальнейшем диагностированы более тщательно. Небрежность в медицине зачастую приводит к тому, что по недосмотру игнорируются начальные признаки болезни и пациент заболевает еще сильнее или умирает.

После того, как мы определились с критериями, необходимо рассмотреть методы классификации. Существуют три основных группы таких методов: граничные методы (1), методы оценки плотности (2), и модельные методы (3).

Граничные методы

Граничные методы определяют классы, используя границы областей. В некоторых простейших случаях классы можно разделить прямой линией, как на рисунке 3. Каждый объект в данном случае характеризуется двумя измерениями. Набирающий популярность метод опорных векторов (Support Vector Machine — SVM) ищет образцы, расположенные на границах между двумя классами (рисунок 4). Идеальная классификация получается в том случае, когда область между границами пуста. На рисунке это показано для случая пяти опорных векторов. Большинство хемометриков находят этот метод немного некорректным, так как для классификации используется лишь небольшая часть образцов, а именно только те (называемые опорными векторами), которые лежат на границах.

Рис. 3. Разделение классов прямой линией

Рис. 4. К определению опорных векторов

Здравый смысл подсказывает, что для классификации необходимы большие наборы данных, и, на самом деле другие методы требуют достаточно солидных обучающих наборов. Тем не менее, если SVM модель можно построить на скромном наборе данных и если она будет хорошо работать на тестовом наборе, можно ожидать вполне адекватных результатов.

Одной из проблем, связанных с построением SVM-модели является то, что не всегда можно легко найти линейную границу между классами. На практике найти такие многомерные данные, которые можно представить в виде, сходном с рисунком 4, либо в пространстве исходных переменных либо главных компонент, достаточно сложно. К тому же данный случай может быть следствием использования недостаточного числа переменных для иллюстрации границ между классами, которые на самом деле могут зависеть от гораздо большего числа переменных. Более того, даже в пространстве исходных данных поиск линейных границ, разделяющих классы, может быть весьма затруднительным, согласно рисунку 5. Что мы можем здесь сделать? Увеличить размерность. Если два класса полностью разделяются параболой, то почему бы ни добавить размерность x2? Данные переместятся из плоскости в трехмерную систему координат, в которой можно будет построить плоскость, идеально разделяющую разные классы. В качестве опорных векторов будут выступать экстремальные образцы из обоих классов. Другими словами, одной из основных особенностей метода опорных векторов является добавление, с помощью так называемого оператора ядра, дополнительных размерностей для нахождения границ между классами в виде гиперплоскостей. Для химических данных, часто, первым шагом является применение метода главных компонент для упрощения матрицы данных, в которой в результате остаются только несколько наиболее существенных главных компонент, а только после этого применяют SVM вместе с оператором ядра для определения границ между классами. При обратном проецировании на систему исходных координат такие плоскости выглядят несколько необычно, в виде кривых и окружностей, но, тем не менее, они должны разделять объекты на различные области в соответствии с их классовой принадлежностью. Сначала, на обучающем наборе достигают наилучшего разделения, а затем его можно опробовать на тестовом наборе, как было описано выше.

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

Рис. 5. Разделение классов параболой

Методы оценки плотности

Методы оценки плотности базируются на нескольких принципах. Основная их цель не столько построить границы классов, сколько определить плотность образцов в пространстве, образованном исходными или производными (например, главными компонентами) переменными. На рисунке 6 представлены два одномерных распределения, полученные для двух классов, выделенные красным и синим цветом. Часто такие распределения могут быть аппроксимированы аналитической моделью, например кривой Гаусса. Каждое распределение имеет центр и стандартное отклонение. Неизвестный образец относят к тому или иному распределению с некоторой вероятностью. Существуют стандартные методы, для определения вероятности принадлежности определенного образца некоторому классу в зависимости от удаления его от центра с учетом стандартного отклонения. Т.е. мы можем изучить результаты измерений, найти вероятность принадлежности образца к каждому из рассматриваемых классов, и, либо выбрать класс, где вероятность наибольшая, либо, если вероятность низка для всех классов, отклонить образец.

Рис. 6. Одномерные распределения

На рисунке 7 представлены два распределения плотности вероятностей полученных для двух классов, каждый из которых характеризуется двумя переменными. Любой неизвестный образец, таким образом, может быть, в зависимости от оценки вероятности, отнесен к тому или иному классу.

Рис. 7. Двумерные распределения

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

Стоит так же заметить, что предварительная обработка исходных данных, например МГК или логарифмическое преобразование, или отбор переменных могут быть весьма существенным шагом перед определением функций плотности вероятностей.

Модельные методы

И, наконец, последний класс методов, которые очень любят хемометрики, это модельные методы. Большинство из них хорошо знакомо читателям Homepage of Chemometrics и были рассмотрены в предыдущих статьях, так что здесь мы приведем очень сжатый обзор.

Возможно самый первый, и уж точно наиболее часто цитируемый исторический пример обычно берется из работы Р. А. Фишера, который исследовал возможность классификации трех подвидов ириса по четырем измерениям: длине и ширине лепестка и длине и ширине чашелистика. Для каждой пары классов можно вычислить многомерную дискриминационная оценку и, если она оказалось положительной, то объект соотносится с первым классом, а если отрицательной, то со вторым. Такие функции дискриминации можно использовать для всех случаев, где число измеряемых признаков меньше числа объектов в каждом классе.

Рис. 8. Зависимость дискриминационной оценки от номера образца

Хорошо известным обобщением такого метода является расстояние Махаланобиса определяющее дистанцию от каждого объекта до центра класса. При этом, в отличие от известного всем евклидового расстояния учитывается отклонение по каждой переменной и протяженность каждого класса. Дело в том, что некоторые классы могут быть более рассеяны чем другие, и, следовательно, большое расстояние от модели описывающей такой класс вовсе не означает, что образец не принадлежит этому классу. Слабое место такого классического подхода состоит в том, что в химии мы часто измеряем намного больше переменных, чем имеем образцов. Так в обычном спектре может быть сотни или тысячи значений интенсивности, и для использования классической дискриминационной функции Фишера потребуется уменьшить число переменных либо простым отбором (для этого разработано достаточно много пошаговых алгоритмов), либо объединяя переменные (например, с помощью МГК).

С начала первых работ по хемометрике 70-80 годов таких модельных методов было разработано в избытке и, такие известные методы как SIMCA или Discriminant PLS довольно подробно представлены на Homepage of Chemometrics.

Байесовская классификация

В заключении о еще одином важном подходе, связанным с задачами классификации, — это использование байесовской статистики. В наше время он весьма и весьма популярен в статистических кругах. Все описанные выше методы предполагали, что перед использованием классификационных алгоритмов вероятность того, что объект принадлежит тому или иному классу одинакова. Однако это далеко не всегда так. Например, пусть нам известно, что только 1% образцов принадлежит определенной группе, можем ли мы включить эту информацию или априорные знания в вероятностные вычисления? Да, существуют давно установленные выражения, которые позволяют сделать это без особых затрат. Например, в медицинской диагностике, если доктор отправляет подозрительный образец для дальнейшего анализа, значит, он уже считает, что что-то не так, он не то, чтобы уверен, но вероятность того, что с пациентом что-то не так, выше, чем, если бы образец был выбран просто случайным образом. Можем ли мы эту заранее заданную вероятность включить в модель? В химии мы можем проделать серию экспериментов для исследования различных параметров. Например, мы можем проверить некоторый объект на предмет, является ли он выбросом или нет с помощью инфракрасной спектроскопии. Если его спектр не удовлетворяет нашему заранее заданному классу для допустимых объектов, то, очевидно, что что-то не так и мы можем использовать эту информацию в качестве дополнительных входных данных для следующего теста. Каждый тест позволяет нам уточнить вероятность того, что исследуемый объект принадлежит к определенному классу. Особенно важен такой подход в криминалистике. Является ли обвиняемый виновным или нет? В большинстве случаев, не существует отдельной улики, которая бы однозначно дала бы ответ на этот вопрос, но каждая отдельная деталь, складываясь с остальными, позволит построить полную картину до тех пор, пока обвинение не станет окончательным и риск неправильного решения будет наименьшим.

Заключение

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