Кривая ошибок
Материал из MachineLearning.
(Первое приближение статьи) |
(переработка, обновление, формулы, иллюстрации) |
||
Строка 1: | Строка 1: | ||
{{Задание|osa|Константин Воронцов|25 января 2010}} | {{Задание|osa|Константин Воронцов|25 января 2010}} | ||
- | '''Кривая ошибок''' или '''ROC-кривая''' – часто применяемый способ представления | + | '''Кривая ошибок''' или '''ROC-кривая''' – часто применяемый способ представления характеристик качества бинарного классификатора. |
== Кривая ошибок в задаче классификации == | == Кривая ошибок в задаче классификации == | ||
Строка 9: | Строка 9: | ||
Параметр <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>\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>. Поэтому при решении | + | Нетрудно заметить, что в задаче существенны не сами параметры <tex>\lambda_y</tex>, а их отношение: <tex>\frac{\lambda_{-1}}{\lambda_{+1}}</tex>. Поэтому при решении задач используются функционалы, инвариантный, относительно этого отношения. |
+ | |||
+ | == TPR и FPR == | ||
Рассмотрим два следующих функционала: | Рассмотрим два следующих функционала: | ||
- | 1. False Positive Rate | + | 1. False Positive Rate доля объектов выборки <tex>X^l</tex> '''ошибочно''' отнесённых алгоритмом <tex>a</tex> к классу {+1}: |
+ | |||
+ | <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> | ||
+ | |||
+ | 2. True Positive Rate доля объектов выборки <tex>X^l</tex> '''правильно''' отнесённых алгоритмом <tex>a</tex> к классу {+1}: | ||
+ | |||
+ | <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-кривая показывает зависимость количества верно классифицированных положительных объектов из <tex>X^l</tex> (по оси Y) от количества неверно классифицированных отрицательных объектов из <tex>X^l</tex> (по оси X). | ||
+ | |||
+ | [[Изображение:RoC-1.jpg|thumb|Рис.1. «Случайное гадание»]] На рисунке 1 приведена RoC-кривая, соответствующая алгоритму «случайного гадания», когда классификация объекта происходит методом «подбрасывания монетки» с вероятностью исходов <tex>\frac12</tex>. | ||
+ | |||
+ | [[Изображение:RoC-2.jpg|thumb|Рис.2. Хороший случай]] На рисунке 2 изображён общий случай. Визуально, чем выше лежит кривая, тем лучше характеристики качества алгоритма. | ||
+ | |||
+ | == Алгоритм построения RoC-кривой == | ||
+ | |||
+ | На основе обучающей выборки <tex>X^l</tex> можно очень эффективно аппроксимировать RoC-кривую для заданного классификатора. Ниже приведён алгоритм, строящий эту зависимость. | ||
+ | |||
+ | ===Вход=== | ||
+ | * Обучающая выборка <tex>X^l</tex> | ||
+ | * <tex>f(x_i,w), \ i=\overline{1,l}</tex> — вероятность того, что <tex>x_i</tex> принадлежит классу {+1}. | ||
+ | |||
+ | ===Результат работы=== | ||
+ | <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>. | ||
+ | |||
+ | ===Описание алгоритма=== | ||
+ | |||
+ | 1. Вычислим количество представителей классов {+1} и {-1} в обучающей выборке: | ||
+ | <tex>l_-:= \sum_{i=1}^l [y_i= -1], \ l_+:= \sum_{i=1}^l [y_i= +1] </tex>; | ||
+ | 2. Упорядочим выборку <tex>X^l</tex> по убыванию значения <tex>f(x_i,w)</tex>; | ||
+ | 3. Начальная точка кривой — <tex>(FPR_0,TPR_0):=(0,0)</tex>; | ||
+ | 4. Цикл для всех <tex> i= \overline{1,l} </tex>: | ||
+ | 5. Если <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, тем «лучше» алгоритм. |
Версия 19:25, 6 января 2010
![]() | Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |
Кривая ошибок или ROC-кривая – часто применяемый способ представления характеристик качества бинарного классификатора.
Содержание |
Кривая ошибок в задаче классификации
Рассмотрим задачу логистической регрессии в случае двух классов. Традиционно, один из этих классов будем называть классом «с положительными исходами», другой - «с отрицательными исходами» и обозначим множество классов через . Рассмотрим линейный классификатор для указанной задачи:
.
Параметр полагается равным
, где
– штраф за ошибку на объекте класса
,
. Эти параметры выбираются из эмперических соображений и зависят от задачи.
Нетрудно заметить, что в задаче существенны не сами параметры , а их отношение:
. Поэтому при решении задач используются функционалы, инвариантный, относительно этого отношения.
TPR и FPR
Рассмотрим два следующих функционала:
1. False Positive Rate доля объектов выборки ошибочно отнесённых алгоритмом
к классу {+1}:
2. True Positive Rate доля объектов выборки правильно отнесённых алгоритмом
к классу {+1}:
ROC-кривая показывает зависимость количества верно классифицированных положительных объектов из (по оси Y) от количества неверно классифицированных отрицательных объектов из
(по оси X).
Алгоритм построения RoC-кривой
На основе обучающей выборки можно очень эффективно аппроксимировать RoC-кривую для заданного классификатора. Ниже приведён алгоритм, строящий эту зависимость.
Вход
- Обучающая выборка
-
— вероятность того, что
принадлежит классу {+1}.
Результат работы
— последовательность из
точек на координатной плоскости из области
, аппроксимирующая RoC-кривую по обучающей выборке
.
Описание алгоритма
1. Вычислим количество представителей классов {+1} и {-1} в обучающей выборке:; 2. Упорядочим выборку
по убыванию значения
; 3. Начальная точка кривой —
; 4. Цикл для всех
: 5. Если
, то сместиться вправо:
; иначе сместиться вверх:
;
Функционал качества
В качестве функционала качества, инвариантного относительно выбора цен ошибок, используют площадь под RoC-кривой. Эту величину также называют AUC (Area Under Curve). Чем больше AUC, тем «лучше» алгоритм.