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

Вступление

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

Мы рассмотрим задачу классификации для случая заранее известного множества классов. Для простоты изложения рассмотрим случай, когда количество классов равняется двум. Такая постановка часто встречается в прикладных задачах распознавания, когда цель состоит в автоматическом обнаружении некоторого события. Пример такой задачи - обнаружение присутствия лица человека на изображении.

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

Классификатором назовем функцию, которая по вектору признаков объекта выносит решение, какому именно классу он принадлежит:

Функция F отображает пространство векторов признаков в пространство меток классов Y. В случае двух классов Y = {-1, 1}, '1' соответствует случаю обнаружения искомого события, '-1' - событие не обнаружено. Мы рассматриваем вариант обучения с учителем (supervised learning), когда для обучения классификатора нам доступен некоторый набора векторов {x} , для которых известна их истинная принадлежность к одному из классов. Для обучения классификатора используется только часть данных, которая называется тренировочным набором. После того как обучение классификатора на тренировочном наборе завершено, необходимо оценить качество получившегося классификатора.

Целью тренировки классификатора является увеличение вероятности верной классификации данных, в момент тренировки недоступных (unseen data). Раз так - оценка качества классификации тренировочных данных не является адекватной мерой для оценки работы классификатора на новых, в процессе тренировки не использованных, данных.

При тренировке классификаторов существует опасность того, что классификатор будет слишком хорошо подогнан под тренировочные данные, что может привести к плохим результатам на новых (unseen) данных. Эта проблема называется <перетренировкой> или <переобучением> классификатора.

Принятие решения о качестве получившегося классификатора на основании проверки на тренировочных данных может привести к тому, что переобучение (если оно присутствует) может не быть обнаружено. Более адекватной оценкой является оценка производительности на тестовом наборе - наборе данных, размеченных по классам, но не использовавшимся в процессе тренировки. Способ разделения доступных при обучении данных на тренировочный и тестовый наборы будет рассмотрен ниже (в разделе <Способы разделения данных на тренировочный и тестовый наборы>).

Оценка

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

Базовые характеристики

Базовыми характеристиками качества классификации являются уровни ошибок первого и второго рода (error rates). Ошибка первого рода - это "ложный пропуск" (false negative), когда интересующее нас событие ошибочно не обнаруживается. Ошибка второго рода - "ложное обнаружение" (false positive), когда при отсутствии события ошибочно выносится решение о его присутствии.

Пусть количество объектов в тестовом наборе равно N, из них Np - кол-во "положительных" (c меткой '1') объектов, а  Nn - кол-во объектов "отрицательных" (с меткой '-1'). Естественно, N=Np+Nn. Пусть количество ложных пропусков FN, а ложных обнаружений FP, тогда несложно подсчитать количество верных пропусков и верных обнаружений (true negatives, true positives):

TP = Np - FN;
TN = Nn - FP;

Используя эти величины можно рассчитать нормированные уровни ошибок первого и второго рода, а также долю верно распознаваемых пропусков и обнаружений:

nFN=FN / Np * 100%; nFP = FP / Nn * 100%;
nTN=TN / Nn * 100%; nTP = TP / Np * 100%;

Такие величины более наглядно отражают качество распознавания, поскольку не зависят (в явном виде) от количества объектов в тестовом наборе. Мера точности (precision) и отзыва (recall), часто использующиеся в задачах поиска информации (data mining), рассчитываются также на основе характеристик TP и FP:

Отзыв измеряет долю верного распознавания относительно всех объектов интересующего нас класса, совпадает с nTP. Точность измеряет долю верных обнаружений среди всех обнаруженных объектов.

ROC-кривая

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

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

В такой постановке задачи вектор признаков состоит только из одного компонента h (роста). Рассмотрим классификатор, производящий решение на основе близости этого признака к среднему значению на тренировочной выборке спортсменов. Накопив некоторую статистику по росту тех и других, в процессе тренировки вычисляется среднее значение роста для обоих классов H_b, H_f. Предположим, что в основной предпосылке мы не ошиблись, и H_b > H_f. Тогда требуется выбрать величину порога H_b >= T >= H_f, по которому мы будем принимать решение.

Интуитивно понятно, что чем ближе будет эта величина к H_b, тем меньше вероятность ложного обнаружения баскетболиста (ошибки второго рода). В то же время, чем она ближе к H_f тем меньше вероятность ошибочного пропуска баскетболиста (ошибки первого рода). Говоря математически, выбор величины T влияет на соотношение nFP и nTP.

Такие соотношения выражаются ROC-кривой метода (receiver operator characteristic - ROC curve). Английское название пришло из области обработки сигналов. Кривая выражает соотношение уровня верных (nTP) и ложных обнаружений (nFP). Рисунок 1 демонстрирует кривую ROC для метода распознавания цвета кожи, основанного на нормированной таблице частот [1]. Построение кривой ROC обычно производится путем варьирования параметров классификатора и фиксации получающихся nTP и nFP.

Рисунок 1 Характеристическая кривая (ROC) метода, выражающая соотношение верных и ложный обнаружений

В многие классификаторы, помимо приведенного модельного примера, основанные на моделировании плотности распределения (как параметрические, так и непараметрические), а также методы, основанные на методе главных компонент [2], факторном анализе [4], дискриминантном анализе [3] и т.д. допускают дополнительные настройки после тренировки, так что для их сравнения имеет смысл оценивать именно ROC кривые.

Способы разделения данных на тренировочный и тестовый наборы

Метод удерживания (Holdout)

В случае, когда объем данных доступных для тренировки и проверки классификатора достаточно велик, часть данных можно попридержать до тестирования, и не использовать для тренировки. Таким образом весь набор данных разделяется на две непересекающиеся части случайным образом - тренировочный набор и тестовый набор (такой метод называется метод удерживания - holdout). Обучение производится на тренировочном, проверка на тестовом наборах. Обычно, для тестирования отводится от 1/10 до 1/3 всего доступного набора данных. Для увеличения надежности подобная процедура удержания части данных производится несколько раз, и результат усредняется (repeated holdout).

Для некоторых классификаторов предусмотрена (или возможна) двухступенчатая тренировка (вспомните примеры из прошлого раздела). Тогда разделение можно произвести на три части - тренировочный, тестовый и верификационный наборы (validation set). Верификационный набор используется для настройки параметров классификатора, например - для выбора оптимального соотношения nTP и nFP.

Стратификация (Stratification)

Если в доступных данных объекты одного класса встречаются значительно чаще объектов другого класса (один класс доминирует над другим), то при случайном разделении данных на тренировочный/тестовый наборы может возникнуть неприятная ситуация. В тренировочный (или тестовый) набор может попасть слишком мало экземпляров второго класса (теоретически - вообще ни одного). Понятно, что в таком случае успешное обучение вряд ли возможно. Чтобы избежать подобной ситуации прибегают к процедуре стратификации - при разделении на тестовый и тренировочной наборы данные каждого класса разделяют в нужной пропорции и затем из полученных четырех наборов составляют тестовый и тренировочный. Это позволяет добиться достаточной представительности каждого класса, как на этапе тренировки, так и при проверке.

Перекрестная проверка (Cross-validation)

Для того чтобы избежать пересечения тестовых наборов, которое возможно при использовании метода Repeated holdout, используется метод перекрестной проверки (cross-validation). Он заключается в разделении всего набора данных на k подмножеств (иногда с учетом стратификации). Затем k раз производится тренировка по k-1 наборам и проверка по одному оставшемуся - см.  Рисунок 2.

Рисунок Рисунок 2 Перекрестная проверка

Результаты, полученные на каждой из k итераций, усредняются для получения финального результата. Как показывают многочисленные тестирования, 10 итераций обычно оказывается достаточно, поэтому k обычно принимается равным 10 (tenfold cross-validation). Для еще более точной оценки уровня ошибок иногда производится десятикратная перекрестная проверка (ten tenfold cross validation).

Вариантом перекрестной проверки является проверка <без одного> - leave-one-out. Фактически он является перекрестной проверкой для случае k равному N (количество данных). Этот вариант часто используется для проверки гипотез. К плюсам метода стоит отнести тренировку по максимуму данных, отсутствие случайности, которая присутствует при использовании holdout и перекрестной проверки. Минусами являются невозможность стратификации, а также очень высокая вычислительная сложность.

Самонастройка (Bootstrap)

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

Для набора из N объектов повторить N раз следующую процедуру:

1.      Cоставить тренировочный набор из случайно выбранных N элементов (элементы могут входить в тренировочный набор несколько раз!)

2.      Провести тренировку на этом наборе

3.      Проверить на остальных данных, в набор не попавших.

Самонастройка считается наилучшим способом оценки классификации при очень маленьких наборов данных. Самонастройку также иногда называют '0.632 bootstrap'. 0.632 - это ожидаемая доля всех доступных данных, использованных для тренировки хотя бы на одном из шагов:

Как видно из формул, при росте N вероятность использования каждого из векторов данных (хотя бы в одной из итераций) стремится к 63.2%.

Сравнение классификаторов

Прямое сравнение

Простейшим способом сравнения двух классификаторов является сравнение их уровней ошибок (error rates) и выбора наиболее подходящего. В случае, если классификатор содержит свободный параметр, позволяющий регулировать соотношение nTP и nFP - целесообразно сравнивать ROC кривые.

На Рисунок 3 показано сравнение двух классификаторов. Можно увидеть что второй (график зеленого цвета) показывает больший уровень верных обнаружений при уровне ложных обнаружений менее 8%. В зависимости от того, какой уровень ложного обнаружения является допустимым можно выбрать из этих двух классификаторов оптимальный.

Рисунок 3 Сравнение двух классификаторов

Более компактная мера (не несущая, впрочем, всей информации о соотношении верных и ложных обнаружений) - это площадь под ROC кривой (area under curve - AUC). Для случая заметного превосходства одного классификатора над другим (см. Рисунок 4) AUC позволяет уверенно сравнить две кривые ROC и выбрать лучший.

Рисунок SEQ Рисунок * ARABIC 4 Соотношение ROC-кривой и меры AUC кривых различных классификаторов.
Красный график - AUC = 0.96463, синий - AUC = 0.98841.

Однако не во всех случаях AUC дает верное представление о том, какой из классификаторов лучше. Например, на Рисунок 3 AUC для первого классификатора (красный график) больше, чем для второго, в то время как первый классификатор уступает второму при уровне ложных обнаружений менее 8%. В таких случаях без анализа самих кривых не обойтись.

Статистические тесты

Уровни ошибок, рассчитываемые по некоторому количеству испытаний, по сути, сами являются случайными величинами. Для повышения надежности оценки они усредняются (repeated holdout, cross-validation, leave one out). Фактически это означает, что производится оценка математического ожидания этих случайных величин.

Прямое сравнение полученных оценок матожидания уровня ошибок может дать неверные результаты, поскольку не учитывает <надежность> полученных оценок. Для проверки различия средних значений в статистике приняты различные тесты, в частности t-тест (тест Стьюдента) сравнения средних [5]. Данный тест дает ответ на вопрос - действительно ли имеет место значимое различие между средними, или оно объясняется статистическими колебаниями.

Для двух классификаторов, тренированных и проверяемых на одних и тех же данных (например, на одном и том же разделении при перекрестной проверке) применяется более точный парный двухвыборочный t-тест [6]. Проверка наличия статистического различия матожиданий уровней ошибок производится следующим образом. Пусть для оценки качества распознавания применяется перекрестная проверка с k подмножествами. На каждой итерации i=1..k; вычисляется уровень ошибок для первого и второго классификаторов X_i, Y_i (для одного и того же набора). Для вынесения решения о статистически значимом отличии этих величин вычисляются следующие величины:

Данное распределение t имеет k-1 степень свободы. Для того чтобы принять (или отвергнуть) гипотезу о статистически значимом различии средних нужно сравнить полученное значение t с таблицей распределения Cтьюдента для k-1 степеней свободы. В случае если вычисленное значение не превышает табличное, вероятность существенного различия не выше указанного в таблице (таблица составляется для определенного уровня значимости), в противном случае - выше.

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

Заключение

Резюмируя все вышесказанное, алгоритм сравнения классификаторов можно приблизительно сформулировать так:

1. Выбрать способ разделения на тренировочный и тестовый наборы
2. Провести испытания для всех классификаторов на общих наборах, вычислить характеристики производительности методов;
3. Проверить на наличие статистического различия между полученными величинами;
4. Выбрать классификатора c наилучшими характеристиками;

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

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

Литература 

[1]   Vezhnevets V., Sazonov V., Andreeva A., "A Survey on Pixel-Based Skin Color Detection Techniques". Proc. Graphicon-2003, pp. 85-92, Moscow, Russia, September 2003.

[2]   "Метод главных компонент," Цифровая библиотека лаборатории компьютерной графики и мультимедиа ВМиК МГУ, http://library.graphicon.ru/catalog/19.

[3]   "Линейный дискриминантный анализ," Цифровая библиотека лаборатории компьютерной графики и мультимедиа ВМиК МГУ, http://library.graphicon.ru/catalog/184.

[4]   "Факторный анализ," Цифровая библиотека лаборатории компьютерной графики и мультимедиа ВМиК МГУ, http://library.graphicon.ru/catalog/217.

[5]   "Основные статистики и таблицы," Электронный учебник StatSoft, http://www.statsoft.ru/home/textbook/modules/stbasic.html

[6]   "Статистические методы исследования в медицине и здравоохранении," / Под ред. Л.Е. Полякова - Л.: Медицина, 1971.

[7]   Mitchell, Tom. M. 1997. "Machine Learning," New York: McGraw-Hill.

[8]   Witten, Ian H., and Eibe Frank. 2000. "Data Mining: Practical Machine Learing Tools and Techniques with Java Implementations," San Diego, CA: Morgan Kaufmann.