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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: {{Задание|osa|Константин Воронцов|25 января 2010}})
(Перенос абзаца в соседний раздел.)
 
(24 промежуточные версии не показаны)
Строка 1: Строка 1:
-
{{Задание|osa|Константин Воронцов|25 января 2010}}
+
{{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>\lambda_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> для многих классификаторов эквивалентно варьированию отношения цены ошибок на отрицательных и положительных объектах.
 +
На практике цены ошибок зависят от особенностей конкретной задачи (например, от различных экономических соображений или экспертных оценок) и могут многократно пересматриваться.
 +
 
 +
Заметим, что частным случаем линейного байесовского классификатора является [[логистическая регрессия]].
 +
 
 +
''ROC-кривая'' наглядно представляет, каким будет качество классификации при различных <tex>w_0</tex> и фиксированном <tex>w</tex>.
 +
 
 +
== 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. «Хороший» классификатор.]]
 +
 
 +
ROC-кривая показывает зависимость TPR от FPR при варьировании порога <tex>w_0</tex>.
 +
Она проходит из точки <tex>(0,0)</tex>, соответствующей максимальному значению <tex>w_0</tex>, в точку <tex>(1,1)</tex>, соответствующую минимальному значению <tex>w_0</tex>.
 +
 
 +
При <tex>w_0 \;>\, \max_{1=1..m} f(x_i,w)</tex> все объекты классифицируются как отрицательные, и ошибки возникают на всех положительных объектах, <tex>\textrm{FPR}=0</tex>, <tex>\textrm{TPR}=0</tex>.
 +
 
 +
При <tex>w_0 \;<\, \min_{1=1..m} f(x_i,w)</tex> все объекты классифицируются как положительные, и ошибки возникают на всех отрицательных объектах, <tex>\textrm{FPR}=1</tex>, <tex>\textrm{TPR}=1</tex>.
 +
 
 +
ROC-кривая монотонно не убывает.
 +
Чем выше лежит кривая, тем лучше качество классификации.
 +
 
 +
На рисунке 1 приведена ROC-кривая, соответствующая худшему случаю — алгоритму «случайного гадания».
 +
На рисунке 2 изображён общий случай.
 +
Лучший случай — это кривая, проходящая через точки <tex>(0,0);\; (0,1);\; (1,1)</tex>
 +
 
 +
''ROC-кривая'' может быть вычислена по любой выборке. Однако ''ROC-кривая'', вычисленная по обучающей выборке, является оптимистично смещённой влево-вверх вследствие [[переобучение|переобучения]]. Величину этого смещения предсказать довольно трудно, поэтому на практике ''ROC-кривую'' всегда оценивают по независомой тестовой выборке.
 +
 
 +
== Площадь под ROC-кривой AUC ==
 +
 
 +
Площадь под ROC-кривой AUC (Area Under Curve) является агрегированной характеристикой качества классификации, не зависящей от соотношения цен ошибок.
 +
Чем больше значение AUC, тем «лучше» модель классификации.
 +
Данный показатель часто используется для сравнительного анализа нескольких моделей классификации.
 +
 
 +
== Алгоритм построения ROC-кривой ==
 +
 
 +
Следующий алгоритм строит ROC-кривую за <tex>m</tex> обращений к дискриминантной функции.
 +
 
 +
'''Входные данные:'''
 +
* Выборка <tex>X^m</tex>
 +
* Функция <tex>f(x,w)</tex> при фиксированном векторе параметров <tex>w</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>;
 +
 
 +
== Чувствительность и специфичность ==
 +
Наряду с FPR и TPR используют также показатели ''чувствительности'' и ''специфичности'', которые также изменяются в интервале <tex>[0,1]</tex>:
 +
* ''чувствительность'' алгоритма <tex>a</tex> совпадает с <tex>\textrm{TPR}</tex>;
 +
* ''специфичность'' алгоритма <tex>a</tex> определяется как <tex>(1-\textrm{FPR})</tex>.
 +
<!-- [[Изображение:RoC-3.jpg|thumb|Рис. 3. Чувствительность и специфичность алгоритма на RoC-кривой]]-->
 +
 
 +
Модель с высокой чувствительностью часто дает истинный результат при наличии положительного исхода (обнаруживает положительные примеры). Наоборот, модель с высокой специфичностью чаще дает истинный результат при наличии отрицательного исхода (обнаруживает отрицательные примеры). Если рассуждать в терминах медицинской диагностики, где модель классификации пациентов на больных и здоровых называется ''диагностическим тестом'', то получится следующее:
 +
* чувствительный ''диагностический тест'' проявляется в гипердиагностике – максимальном предотвращении пропуска больных;
 +
* специфичный ''диагностический тест'' диагностирует только доподлинно больных. Это важно в случае, когда, например, лечение больного связано с серьезными побочными эффектами и гипердиагностика пациентов нежелательна.
 +
 
 +
== История ==
 +
 
 +
Термин ''операционная характеристика приёмника'' (Receiver Operating Characteristic, ROC) пришёл из теории обработки сигналов.
 +
Эту характеристику впервые ввели во время II мировой войны, после поражения американского военного флота в Пёрл Харборе в 1941 году, когда была осознана проблема повышения точности распознавания самолётов противника по радиолокационному сигналу. Позже нашлись и другие применения: медицинская диагностика, приёмочный контроль качества, кредитный скоринг, предсказание лояльности клиентов, и т.д.
 +
 
 +
== См. также ==
 +
 
 +
* [[Линейный классификатор]]
 +
* [[Логистическая регрессия]]
 +
 
 +
== Ссылки ==
 +
 
 +
* [http://www.basegroup.ru/library/analysis/regression/logistic/ Логистическая регрессия и ROC-анализ]
 +
* [http://en.wikipedia.org/wiki/ROC_curve RoC-curve (english wikipedia)]
 +
 
 +
[[Категория:Классификация]]

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

Содержание

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

См. также

Ссылки

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