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

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

(Различия между версиями)

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

Версия 19:25, 6 января 2010

Данная статья является непроверенным учебным заданием.

Студент: Участник:osa

Преподаватель: Участник:Константин Воронцов

Срок: 25 января 2010

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.

Кривая ошибок или ROC-кривая – часто применяемый способ представления характеристик качества бинарного классификатора.

Кривая ошибок в задаче классификации

Рассмотрим задачу логистической регрессии в случае двух классов. Традиционно, один из этих классов будем называть классом «с положительными исходами», другой - «с отрицательными исходами» и обозначим множество классов через $Y=\{-1,+1\}$ . Рассмотрим линейный классификатор для указанной задачи: $a(x) = sign (f(x,w) - w_0)$ .

Параметр $w_0$ полагается равным $\frac{\lambda_{-1}}{\lambda_{+1}}$ , где $\lambda_y$ – штраф за ошибку на объекте класса $y$ , $y \in \{-1, +1\}$ . Эти параметры выбираются из эмперических соображений и зависят от задачи.

Нетрудно заметить, что в задаче существенны не сами параметры $\lambda_y$ , а их отношение: $\frac{\lambda_{-1}}{\lambda_{+1}}$ . Поэтому при решении задач используются функционалы, инвариантный, относительно этого отношения.

TPR и FPR

Рассмотрим два следующих функционала:

1. False Positive Rate доля объектов выборки $X^l$ ошибочно отнесённых алгоритмом $a$ к классу {+1}:

$FPR(a,X^l)=\frac{\sum_{i=1}^l [a(x_i) = +1][y_i = -1]}{\sum_{i=1}^l [y_i = -1]}$

2. True Positive Rate доля объектов выборки $X^l$ правильно отнесённых алгоритмом $a$ к классу {+1}:

$TPR(a,X^l)=\frac{\sum_{i=1}^l [a(x_i) = +1][y_i = +1]}{\sum_{i=1}^l [y_i = +1]}$

ROC-кривая показывает зависимость количества верно классифицированных положительных объектов из $X^l$ (по оси Y) от количества неверно классифицированных отрицательных объектов из $X^l$ (по оси X).

Рис.1. «Случайное гадание»

На рисунке 1 приведена RoC-кривая, соответствующая алгоритму «случайного гадания», когда классификация объекта происходит методом «подбрасывания монетки» с вероятностью исходов $\frac12$ .

Рис.2. Хороший случай

На рисунке 2 изображён общий случай. Визуально, чем выше лежит кривая, тем лучше характеристики качества алгоритма.

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

На основе обучающей выборки $X^l$ можно очень эффективно аппроксимировать RoC-кривую для заданного классификатора. Ниже приведён алгоритм, строящий эту зависимость.

Вход

Обучающая выборка $X^l$
$f(x_i,w), \ i=\overline{1,l}$ — вероятность того, что $x_i$ принадлежит классу {+1}.

Результат работы

$\{(FPR_i, TPR_i)\}_{i=0}^l$ — последовательность из $(l+1)$ точек на координатной плоскости из области $[0,1] \times [0,1]$ , аппроксимирующая RoC-кривую по обучающей выборке $X^l$ .

Описание алгоритма

1. Вычислим количество представителей классов {+1} и {-1} в обучающей выборке:
   ;
2. Упорядочим выборку  по убыванию значения ;
3. Начальная точка кривой — ;
4. Цикл для всех :
   5.  Если , то сместиться вправо:
        ;
       иначе сместиться вверх:
        ;

Функционал качества

В качестве функционала качества, инвариантного относительно выбора цен ошибок, используют площадь под RoC-кривой. Эту величину также называют AUC (Area Under Curve). Чем больше AUC, тем «лучше» алгоритм.

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D1%80%D0%B8%D0%B2%D0%B0%D1%8F_%D0%BE%D1%88%D0%B8%D0%B1%D0%BE%D0%BA»

Категория: Непроверенные учебные задания

@@ Строка 1: / Строка 1: @@
 {{Задание|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>\lambda_y</tex>, а их отношение: <tex>\frac{\lambda_{-1}}{\lambda_{+1}}</tex>. Поэтому при решении задачи логично использовать функционал, инвариантный относительно данного отношения.
+Нетрудно заметить, что в задаче существенны не сами параметры <tex>\lambda_y</tex>, а их отношение: <tex>\frac{\lambda_{-1}}{\lambda_{+1}}</tex>. Поэтому при решении задач используются функционалы, инвариантный, относительно этого отношения.
+== TPR и FPR ==
 Рассмотрим два следующих функционала:
-. False Positive Rate (<tex>FPR(a,X^l)</tex>)– доля объектов выборки <tex>X^l</tex> ложно положительно классификацированных алгоритмом <tex>a</tex>.
+. 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>
+. 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} в обучающей выборке:
+    <tex>l_-:= \sum_{i=1}^l [y_i= -1], \ l_+:= \sum_{i=1}^l [y_i= +1] </tex>;
+. Упорядочим выборку <tex>X^l</tex> по убыванию значения <tex>f(x_i,w)</tex>;
+. Начальная точка кривой — <tex>(FPR_0,TPR_0):=(0,0)</tex>;
+. Цикл для всех <tex> i= \overline{1,l} </tex>:
+.  Если <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>;
-. True Positive Rate (<tex>TPR(a,X^l)</tex>) – доля правильно положительно классифицированных объектов.
+== Функционал качества ==
-ROC-кривая показывает зависимость количества верно классифицированных положительных объектов (по оси Y) от количества неверно классифицированных отрицательных объектов (по оси X).
+В качестве функционала качества, инвариантного относительно выбора цен ошибок, используют площадь под RoC-кривой. Эту величину также называют AUC (Area Under Curve). Чем больше AUC, тем «лучше» алгоритм.

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

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

Версия 19:25, 6 января 2010

Содержание

Кривая ошибок в задаче классификации

TPR и FPR

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

Вход

Результат работы

Описание алгоритма

Функционал качества

Просмотры

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

Навигация

Поиск

Инструменты