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

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

(Различия между версиями)
Перейти к: навигация, поиск
м (TPR и FPR)
(Перенос абзаца в соседний раздел.)
 
(15 промежуточных версий не показаны.)
Строка 1: Строка 1:
-
'''Кривая ошибок''' или '''ROC-кривая''' – часто применяемый способ представления характеристик качества бинарного классификатора.
+
{{TOCright}}
 +
'''Кривая ошибок''' или '''ROC-кривая''' – графичекая характеристика качества бинарного классификатора, зависимость доли верных положительных классификаций от доли ложных положительных классификаций при варьировании порога решающего правила. Преимуществом ROC-кривой является её инвариантность относительно отношения [[цена ошибки|цены ошибки]] I и II рода.
-
== Кривая ошибок в задаче классификации ==
+
== Задача классификации ==
 +
Рассмотрим задачу [[классификация|классификации]] в случае двух классов, называемых «положительным» и «отрицательным». Обозначим множество классов через <tex>Y=\{-1,+1\}</tex>. Большинство известных [[классификатор|классификаторов]] могут быть представлены в виде
 +
::<tex>a(x) = \textrm{sign} (f(x,w) - w_0),</tex>
 +
где
 +
<tex>x</tex> — произвольный [[объект]],
 +
<tex>f(x,w)</tex> — [[дискриминантная функция]],
 +
<tex>w</tex> — вектор параметров, определяемый по [[обучающая выборка|обучающей выборке]],
 +
<tex>w_0</tex> — порог.
 +
Уравнение <tex>f(x,w)=w_0</tex> определяет [[разделяющая поверхность|разделяющую поверхность]].
 +
Примером является [[линейный классификатор]], в котором дискриминантная функция имеет вид скалярного произведения вектора описания объекта на вектор параметров:
 +
<tex>a(x) = \textrm{sign} (\langle x,w \rangle - w_0)</tex>.
-
Рассмотрим задачу [[Логистическая регрессия|логистической регрессии]] в случае двух классов. Традиционно, один из этих классов будем называть классом «с положительными исходами», другой - «с отрицательными исходами» и обозначим множество классов через <tex>Y=\{-1,+1\}</tex>. Рассмотрим [[линейный классификатор]] для указанной задачи: <tex>a(x) = sign (f(x,w) - w_0) </tex>.
+
Пусть <tex>\lambda_y</tex> – цена ошибки (штраф за ошибку) на объекте класса <tex>y \in \{-1, +1\}</tex>.
-
Параметр <tex>w_0</tex> полагается равным <tex>\frac{\lambda_{-1}}{\lambda_{+1}}</tex>, где <tex>\lambda_y</tex> – штраф за ошибку на объекте класса <tex>y</tex>, <tex>y \in \{-1, +1\}</tex>. Эти параметры выбираются из эмперических соображений и зависят от задачи.
+
Для [[байесовский классификатор|байесовского классификатора]] при достаточно общих предположениях доказано, что оптимальное значение порога <tex>w_0</tex> зависит только от соотношения цены ошибок:
 +
:: <tex>w_0 = \ln\frac{\lambda_{-1}}{\lambda_{+1}},</tex>
 +
тогда как оптимальное значение вектора параметров <tex>w</tex>, наоборот, зависит от выборки и не зависит от цены ошибок.
 +
Таким образом, варьирование порога <tex>w_0</tex> для многих классификаторов эквивалентно варьированию отношения цены ошибок на отрицательных и положительных объектах.
 +
На практике цены ошибок зависят от особенностей конкретной задачи (например, от различных экономических соображений или экспертных оценок) и могут многократно пересматриваться.
-
Нетрудно заметить, что в задаче существенны не сами параметры <tex>\lambda_y</tex>, а их отношение: <tex>\frac{\lambda_{-1}}{\lambda_{+1}}</tex>.
+
Заметим, что частным случаем линейного байесовского классификатора является [[логистическая регрессия]].
-
'''RoC-кривая''' является распространённым способом оценки качества алгоритма, вне зависимости от выбора цен ошибок.
+
''ROC-кривая'' наглядно представляет, каким будет качество классификации при различных <tex>w_0</tex> и фиксированном <tex>w</tex>.
== TPR и FPR ==
== TPR и FPR ==
 +
Пусть задана выборка объектов <tex>X^m = (x_1,\ldots,x_m)</tex> с соответствующими им верными ответами <tex>y_1,\ldots,y_m</tex>.
 +
Тогда для классификатора <tex>a(x)</tex> можно определить две характеристики качества:
 +
#Доля ложных положительных классификаций (False Positive Rate, FPR):
 +
#:<tex>\textrm{FPR}(a,X^m) = \frac{\sum_{i=1}^m [a(x_i) = +1][y_i = -1]}{\sum_{i=1}^m [y_i = -1]};</tex>
 +
#Доля верных положительных классификаций (True Positive Rate, TPR):
 +
#:<tex>\textrm{TPR}(a,X^m) = \frac{\sum_{i=1}^m [a(x_i) = +1][y_i = +1]}{\sum_{i=1}^m [y_i = +1]}.</tex>
-
Рассмотрим два следующих функционала:
+
== ROC-кривая ==
 +
[[Изображение:RoC-1.jpg|thumb|Рис.1. «Случайное гадание».]]
 +
[[Изображение:RoC-2.jpg|thumb|Рис.2. «Хороший» классификатор.]]
-
1. False Positive Rate доля объектов [[выборка|выборки]] <tex>X^l</tex> '''ошибочно''' отнесённых алгоритмом <tex>a</tex> к классу {+1}:
+
ROC-кривая показывает зависимость TPR от FPR при варьировании порога <tex>w_0</tex>.
 +
Она проходит из точки <tex>(0,0)</tex>, соответствующей максимальному значению <tex>w_0</tex>, в точку <tex>(1,1)</tex>, соответствующую минимальному значению <tex>w_0</tex>.
-
<tex>FPR(a,X^l)=\frac{\sum_{i=1}^l [a(x_i) = +1][y_i = -1]}{\sum_{i=1}^l [y_i = -1]}</tex>
+
При <tex>w_0 \;>\, \max_{1=1..m} f(x_i,w)</tex> все объекты классифицируются как отрицательные, и ошибки возникают на всех положительных объектах, <tex>\textrm{FPR}=0</tex>, <tex>\textrm{TPR}=0</tex>.
-
2. True Positive Rate доля объектов [[выборка|выборки]] <tex>X^l</tex> '''правильно''' отнесённых алгоритмом <tex>a</tex> к классу {+1}:
+
При <tex>w_0 \;<\, \min_{1=1..m} f(x_i,w)</tex> все объекты классифицируются как положительные, и ошибки возникают на всех отрицательных объектах, <tex>\textrm{FPR}=1</tex>, <tex>\textrm{TPR}=1</tex>.
-
<tex>TPR(a,X^l)=\frac{\sum_{i=1}^l [a(x_i) = +1][y_i = +1]}{\sum_{i=1}^l [y_i = +1]}</tex>
+
ROC-кривая монотонно не убывает.
 +
Чем выше лежит кривая, тем лучше качество классификации.
-
Подробнее об этих функционалах можно прочесть [http://en.wikipedia.org/wiki/ROC_curve#Basic_concept здесь].
+
На рисунке 1 приведена ROC-кривая, соответствующая худшему случаю — алгоритму «случайного гадания».
 +
На рисунке 2 изображён общий случай.
 +
Лучший случай — это кривая, проходящая через точки <tex>(0,0);\; (0,1);\; (1,1)</tex>
-
ROC-кривая показывает зависимость количества верно классифицированных положительных объектов из <tex>X^l</tex> (по оси Y) от количества неверно классифицированных отрицательных объектов из <tex>X^l</tex> (по оси X).
+
''ROC-кривая'' может быть вычислена по любой выборке. Однако ''ROC-кривая'', вычисленная по обучающей выборке, является оптимистично смещённой влево-вверх вследствие [[переобучение|переобучения]]. Величину этого смещения предсказать довольно трудно, поэтому на практике ''ROC-кривую'' всегда оценивают по независомой тестовой выборке.
-
[[Изображение:RoC-1.jpg|thumb|Рис.1. «Случайное гадание»]] На рисунке 1 приведена RoC-кривая, соответствующая алгоритму «случайного гадания», когда классификация объекта происходит методом «подбрасывания монетки» с вероятностью исходов <tex>\frac12</tex>.
+
== Площадь под ROC-кривой AUC ==
-
[[Изображение:RoC-2.jpg|thumb|Рис.2. Хороший случай]] На рисунке 2 изображён общий случай. Визуально, чем выше лежит кривая, тем лучше характеристики качества алгоритма.
+
Площадь под ROC-кривой AUC (Area Under Curve) является агрегированной характеристикой качества классификации, не зависящей от соотношения цен ошибок.
 +
Чем больше значение AUC, тем «лучше» модель классификации.
 +
Данный показатель часто используется для сравнительного анализа нескольких моделей классификации.
-
== Алгоритм построения RoC-кривой ==
+
== Алгоритм построения ROC-кривой ==
-
На основе обучающей выборки <tex>X^l</tex> можно очень эффективно аппроксимировать RoC-кривую для заданного классификатора. Ниже приведён алгоритм, строящий эту зависимость.
+
Следующий алгоритм строит ROC-кривую за <tex>m</tex> обращений к дискриминантной функции.
-
===Входные данные===
+
'''Входные данные:'''
-
* Обучающая выборка <tex>X^l</tex>
+
* Выборка <tex>X^m</tex>
-
* <tex>f(x_i,w), \ i=\overline{1,l}</tex> — вероятность того, что <tex>x_i</tex> принадлежит классу {+1}.
+
* Функция <tex>f(x,w)</tex> при фиксированном векторе параметров <tex>w</tex>.
-
===Результат===
+
'''Результат:'''
-
<tex>\{(FPR_i, TPR_i)\}_{i=0}^l </tex> — последовательность из <tex>(l+1)</tex> точек на координатной плоскости из области <tex>[0,1] \times [0,1]</tex>, аппроксимирующая RoC-кривую по обучающей выборке <tex>X^l</tex>.
+
* <tex>\{(\textrm{FPR}_i, \textrm{TPR}_i)\}_{i=0}^m </tex> — последовательность из <tex>(m+1)</tex> точек ROC-кривой;
 +
* <tex>\textrm{AUC}</tex> — площадь под ROC-кривой;
-
===Описание алгоритма===
+
1. вычислить количество представителей классов <tex>+1</tex> и <tex>-1</tex> в выборке:
 +
<tex>m_{-}\;:=\;\sum_{i=1}^m [y_i= -1], \ \ m_+\;:=\;\sum_{i=1}^m [y_i= +1] </tex>;
 +
2. упорядочить выборку <tex>X^m</tex> по убыванию значений <tex>f(x_i,w)</tex>;
 +
3. установить начальную точку ROC-кривой:
 +
<tex>(\textrm{FPR}_0,\textrm{TPR}_0)\;:=\;(0,0)</tex>;
 +
<tex>\textrm{AUC}\;:=\;0</tex>;
 +
4. для всех <tex> i\;:=\;1..m </tex>
 +
если <tex>(y_i = -1)</tex>, то сместиться на один шаг вправо:
 +
<tex>\textrm{FPR}_i\;:=\;\textrm{FPR}_{i-1} + \frac{1}{m_-}; \ \ \textrm{TPR}_i\;:=\;\textrm{TPR}_{i-1}</tex>;
 +
<tex>\textrm{AUC}\;:=\;\textrm{AUC} + \frac{1}{m_-}\textrm{TPR}_i</tex>;
 +
5. иначе сместиться на один шаг вверх:
 +
<tex>\textrm{FPR}_i\;:=\;\textrm{FPR}_{i-1}; \ \ \textrm{TPR}_i\;:=\;\textrm{TPR}_{i-1} + \frac{1}{m_+}</tex>;
-
1. Вычислим количество представителей классов {+1} и {-1} в обучающей выборке:
+
== Чувствительность и специфичность ==
-
<tex>l_-:= \sum_{i=1}^l [y_i= -1], \ l_+:= \sum_{i=1}^l [y_i= +1] </tex>;
+
Наряду с FPR и TPR используют также показатели ''чувствительности'' и ''специфичности'', которые также изменяются в интервале <tex>[0,1]</tex>:
-
2. Упорядочим выборку <tex>X^l</tex> по убыванию значения <tex>f(x_i,w)</tex>;
+
* ''чувствительность'' алгоритма <tex>a</tex> совпадает с <tex>\textrm{TPR}</tex>;
-
3. Начальная точка кривой — <tex>(FPR_0,TPR_0):=(0,0)</tex>;
+
* ''специфичность'' алгоритма <tex>a</tex> определяется как <tex>(1-\textrm{FPR})</tex>.
-
4. Повторять для всех <tex> i= \overline{1,l} </tex>:
+
<!-- [[Изображение:RoC-3.jpg|thumb|Рис. 3. Чувствительность и специфичность алгоритма на RoC-кривой]]-->
-
Если <tex>(y_i = -1)</tex>, то сместиться вправо:
+
-
<tex>FPR_i:= FPR_{i-1} + \frac{1}{l_-}, \ TPR_i:= TPR_{i-1}</tex>;
+
-
иначе сместиться вверх:
+
-
<tex>FPR_i:= FPR_{i-1} + \frac{1}{l_-}, \ TPR_i:= TPR_{i-1}+\frac{1}{l_+}</tex>;
+
-
== Функционал качества ==
+
Модель с высокой чувствительностью часто дает истинный результат при наличии положительного исхода (обнаруживает положительные примеры). Наоборот, модель с высокой специфичностью чаще дает истинный результат при наличии отрицательного исхода (обнаруживает отрицательные примеры). Если рассуждать в терминах медицинской диагностики, где модель классификации пациентов на больных и здоровых называется ''диагностическим тестом'', то получится следующее:
 +
* чувствительный ''диагностический тест'' проявляется в гипердиагностике – максимальном предотвращении пропуска больных;
 +
* специфичный ''диагностический тест'' диагностирует только доподлинно больных. Это важно в случае, когда, например, лечение больного связано с серьезными побочными эффектами и гипердиагностика пациентов нежелательна.
-
В качестве функционала качества, инвариантного относительно выбора цен ошибок, используют площадь под RoC-кривой. Эту величину также называют AUC (Area Under Curve). Чем больше значение AUC, тем «лучше» алгоритм.
+
== История ==
 +
 
 +
Термин ''операционная характеристика приёмника'' (Receiver Operating Characteristic, ROC) пришёл из теории обработки сигналов.
 +
Эту характеристику впервые ввели во время II мировой войны, после поражения американского военного флота в Пёрл Харборе в 1941 году, когда была осознана проблема повышения точности распознавания самолётов противника по радиолокационному сигналу. Позже нашлись и другие применения: медицинская диагностика, приёмочный контроль качества, кредитный скоринг, предсказание лояльности клиентов, и т.д.
== См. также ==
== См. также ==
Строка 65: Строка 107:
== Ссылки ==
== Ссылки ==
-
* [http://www.basegroup.ru/library/analysis/regression/logistic/ Логистическая регрессия и RoC-анализ]
+
* [http://www.basegroup.ru/library/analysis/regression/logistic/ Логистическая регрессия и ROC-анализ]
* [http://en.wikipedia.org/wiki/ROC_curve RoC-curve (english wikipedia)]
* [http://en.wikipedia.org/wiki/ROC_curve RoC-curve (english wikipedia)]
-
[[Категория:Линейные классификаторы]]
 
-
[[Категория:Машинное обучение]]
 
[[Категория:Классификация]]
[[Категория:Классификация]]
-
 
-
{{Задание|osa|Константин Воронцов|25 января 2010}}
 

Текущая версия

Содержание

Кривая ошибок или 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-кривая

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

Площадь под 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 году, когда была осознана проблема повышения точности распознавания самолётов противника по радиолокационному сигналу. Позже нашлись и другие применения: медицинская диагностика, приёмочный контроль качества, кредитный скоринг, предсказание лояльности клиентов, и т.д.

См. также

Ссылки

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