Кривая ошибок

Материал из MachineLearning.

Перейти к: навигация, поиск

Содержание

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

Задача классификации

Рассмотрим задачу классификации в случае двух классов, называемых «положительным» и «отрицательным». Обозначим множество классов через Y=\{-1,+1\}. Большинство известных классификаторов могут быть представлены в виде

a(x) = \textrm{sign} (f(x,w) - w_0),

где x — произвольный объект, f(x,w)дискриминантная функция, w — вектор параметров, определяемый по обучающей выборке, w_0 — порог. Уравнение f(x,w)=w_0 определяет разделяющую поверхность. Примером является линейный классификатор, в котором дискриминантная функция имеет вид скалярного произведения вектора описания объекта на вектор параметров: a(x) = \textrm{sign} (\langle x,w \rangle - w_0).

Пусть \lambda_y – цена ошибки (штраф за ошибку) на объекте класса y \in \{-1, +1\}.

Для байесовского классификатора при достаточно общих предположениях доказано, что оптимальное значение порога w_0 зависит только от соотношения цены ошибок:

w_0 = \ln\frac{\lambda_{-1}}{\lambda_{+1}},

тогда как оптимальное значение вектора параметров w, наоборот, зависит от выборки и не зависит от цены ошибок. Таким образом, варьирование порога w_0 для многих классификаторов эквивалентно варьированию отношения цены ошибок на отрицательных и положительных объектах. На практике цены ошибок зависят от особенностей конкретной задачи (например, от различных экономических соображений или экспертных оценок) и могут многократно пересматриваться.

Заметим, что частным случаем линейного байесовского классификатора является логистическая регрессия.

ROC-кривая наглядно представляет, каким будет качество классификации при различных w_0 и фиксированном w.

TPR и FPR

Пусть задана выборка объектов X^m = (x_1,\ldots,x_m) с соответствующими им верными ответами y_1,\ldots,y_m. Тогда для классификатора a(x) можно определить две характеристики качества:

  1. Доля ложных положительных классификаций (False Positive Rate, FPR):
    \textrm{FPR}(a,X^m) = \frac{\sum_{i=1}^m [a(x_i) = +1][y_i = -1]}{\sum_{i=1}^m [y_i = -1]};
  2. Доля верных положительных классификаций (True Positive Rate, TPR):
    \textrm{TPR}(a,X^m) = \frac{\sum_{i=1}^m [a(x_i) = +1][y_i = +1]}{\sum_{i=1}^m [y_i = +1]}.

ROC-кривая может быть вычислена по любой выборке. Однако ROC-кривая, вычисленная по обучающей выборке, является оптимистично смещённой влево-вверх вследствие переобучения. Величину этого смещения предсказать довольно трудно, поэтому на практике ROC-кривую всегда оценивают по независомой тестовой выборке.

ROC-кривая

Рис.1. «Случайное гадание».
Рис.1. «Случайное гадание».
Рис.2. «Хороший» классификатор.
Рис.2. «Хороший» классификатор.

ROC-кривая показывает зависимость TPR от FPR при варьировании порога w_0. Она проходит из точки (0,0), соответствующей максимальному значению w_0, в точку (1,1), соответствующую минимальному значению w_0.

При w_0 \;>\, \max_{1=1..m} f(x_i,w) все объекты классифицируются как отрицательные, и ошибки возникают на всех положительных объектах, \textrm{FPR}=0, \textrm{TPR}=0.

При w_0 \;<\, \min_{1=1..m} f(x_i,w) все объекты классифицируются как положительные, и ошибки возникают на всех отрицательных объектах, \textrm{FPR}=1, \textrm{TPR}=1.

ROC-кривая монотонно не убывает. Чем выше лежит кривая, тем лучше качество классификации.

На рисунке 1 приведена ROC-кривая, соответствующая худшему случаю — алгоритму «случайного гадания». На рисунке 2 изображён общий случай. Лучший случай — это кривая, проходящая через точки (0,0);\; (0,1);\; (1,1)

Площадь под ROC-кривой AUC

Площадь под ROC-кривой AUC (Area Under Curve) является агрегированной характеристикой качества классификации, не зависящей от соотношения цен ошибок. Чем больше значение AUC, тем «лучше» модель классификации. Данный показатель часто используется для сравнительного анализа нескольких моделей классификации.

Алгоритм построения ROC-кривой

Следующий алгоритм строит ROC-кривую за m обращений к дискриминантной функции.

Входные данные:

  • Выборка X^m
  • Функция f(x,w) при фиксированном векторе параметров w.

Результат:

  • \{(\textrm{FPR}_i, \textrm{TPR}_i)\}_{i=0}^m — последовательность из (m+1) точек ROC-кривой;
  • \textrm{AUC} — площадь под ROC-кривой;
1. вычислить количество представителей классов +1 и -1 в выборке:
   m_{-}\;:=\;\sum_{i=1}^m [y_i= -1], \ \  m_+\;:=\;\sum_{i=1}^m [y_i= +1] ;
2. упорядочить выборку X^m по убыванию значений f(x_i,w);
3. установить начальную точку ROC-кривой: 
   (\textrm{FPR}_0,\textrm{TPR}_0)\;:=\;(0,0);
   \textrm{AUC}\;:=\;0;
4. для всех  i\;:=\;1..m 
     если (y_i = -1), то сместиться на один шаг вправо:
     \textrm{FPR}_i\;:=\;\textrm{FPR}_{i-1} + \frac{1}{m_-}; \ \ \textrm{TPR}_i\;:=\;\textrm{TPR}_{i-1};
     \textrm{AUC}\;:=\;\textrm{AUC} + \frac{1}{m_-}\textrm{TPR}_i;
5.   иначе сместиться на один шаг вверх:
     \textrm{FPR}_i\;:=\;\textrm{FPR}_{i-1}; \ \ \textrm{TPR}_i\;:=\;\textrm{TPR}_{i-1} + \frac{1}{m_+};

Чувствительность и специфичность

Наряду с FPR и TPR используют также показатели чувствительности и специфичности, которые также изменяются в интервале [0,1]:

  • чувствительность алгоритма a совпадает с \textrm{TPR};
  • специфичность алгоритма a определяется как (1-\textrm{FPR}).

Модель с высокой чувствительностью часто дает истинный результат при наличии положительного исхода (обнаруживает положительные примеры). Наоборот, модель с высокой специфичностью чаще дает истинный результат при наличии отрицательного исхода (обнаруживает отрицательные примеры). Если рассуждать в терминах медицинской диагностики, где модель классификации пациентов на больных и здоровых называется диагностическим тестом, то получится следующее:

  • чувствительный диагностический тест проявляется в гипердиагностике – максимальном предотвращении пропуска больных;
  • специфичный диагностический тест диагностирует только доподлинно больных. Это важно в случае, когда, например, лечение больного связано с серьезными побочными эффектами и гипердиагностика пациентов нежелательна.

История

Термин операционная характеристика приёмника (Receiver Operating Characteristic, ROC) пришёл из теории обработки сигналов. Эту характеристику впервые ввели во время II мировой войны, после поражения американского военного флота в Пёрл Харборе в 1941 году, когда была осознана проблема повышения точности распознавания самолётов противника по радиолокационному сигналу. Позже нашлись и другие применения: медицинская диагностика, приёмочный контроль качества, кредитный скоринг, предсказание лояльности клиентов, и т.д.

См. также

Ссылки

Личные инструменты