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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Первое приближение статьи)
(Перенос абзаца в соседний раздел.)
 
(23 промежуточные версии не показаны)
Строка 1: Строка 1:
-
{{Задание|osa|Константин Воронцов|25 января 2010}}
+
{{TOCright}}
 +
'''Кривая ошибок''' или '''ROC-кривая''' – графичекая характеристика качества бинарного классификатора, зависимость доли верных положительных классификаций от доли ложных положительных классификаций при варьировании порога решающего правила. Преимуществом ROC-кривой является её инвариантность относительно отношения [[цена ошибки|цены ошибки]] I и II рода.
-
'''Кривая ошибок''' или '''ROC-кривая''' – часто применяемый способ представления результатов двухклассовой (бинарной) [[классификация|классификации]].
+
== Задача классификации ==
 +
Рассмотрим задачу [[классификация|классификации]] в случае двух классов, называемых «положительным» и «отрицательным». Обозначим множество классов через <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>Y=\{-1,+1\}</tex>. Рассмотрим [[линейный классификатор]] для указанной задачи: <tex>a(x) = sign (f(x,w) - w_0) </tex>.
+
Для [[байесовский классификатор|байесовского классификатора]] при достаточно общих предположениях доказано, что оптимальное значение порога <tex>w_0</tex> зависит только от соотношения цены ошибок:
 +
:: <tex>w_0 = \ln\frac{\lambda_{-1}}{\lambda_{+1}},</tex>
 +
тогда как оптимальное значение вектора параметров <tex>w</tex>, наоборот, зависит от выборки и не зависит от цены ошибок.
 +
Таким образом, варьирование порога <tex>w_0</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>\lambda_y</tex>, а их отношение: <tex>\frac{\lambda_{-1}}{\lambda_{+1}}</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>
-
1. False Positive Rate (<tex>FPR(a,X^l)</tex>)– доля объектов выборки <tex>X^l</tex> ложно положительно классификацированных алгоритмом <tex>a</tex>.
+
== ROC-кривая ==
 +
[[Изображение:RoC-1.jpg|thumb|Рис.1. «Случайное гадание».]]
 +
[[Изображение:RoC-2.jpg|thumb|Рис.2. «Хороший» классификатор.]]
-
2. True Positive Rate (<tex>TPR(a,X^l)</tex>) – доля правильно положительно классифицированных объектов.
+
ROC-кривая показывает зависимость TPR от FPR при варьировании порога <tex>w_0</tex>.
 +
Она проходит из точки <tex>(0,0)</tex>, соответствующей максимальному значению <tex>w_0</tex>, в точку <tex>(1,1)</tex>, соответствующую минимальному значению <tex>w_0</tex>.
-
ROC-кривая показывает зависимость количества верно классифицированных положительных объектов (по оси Y) от количества неверно классифицированных отрицательных объектов (по оси X).
+
При <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 году, когда была осознана проблема повышения точности распознавания самолётов противника по радиолокационному сигналу. Позже нашлись и другие применения: медицинская диагностика, приёмочный контроль качества, кредитный скоринг, предсказание лояльности клиентов, и т.д.

См. также

Ссылки

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