Построение бинарных классификаторов. Теория.

==**ROC-кривая**==

Перед введением понятия ROC-кривой необходимо предварительно объяснить из какой задачи оно появляется. Вообще, при решении проблемы классификации объекты имеют маркировку либо “Да”, либо “Нет”, и предсказаний также возможно только два, что приводит к четырём возможностям: “Да” для самого объекта и “Да” в предсказании, “Да” для самого объекта и “Нет” в предсказании и так далее. В целом, истинные значения и предсказания складываются в матрицу 2×2 (ниже пример такой матрицы для ста объектов)

|=|=”Да” объекта |=”Нет” объекта|
|=”Да” предсказания| 60| 10|
|=”Нет” предсказания| 5| 25|

Естественно, что классификатор тем лучше, чем меньше у него внедиагональных элементов. И потому достаточно часто используемой характеристикой является так называемая //accuracy// (более подробно можно прочитать [[http://en.wikipedia.org/wiki/Accuracy_and_precision|здесь]])

//accuracy// = {количество правильно распознанных объектов} / {количество всех объектов}

В вышеприведённом примере, //accuracy// = (60 + 25)/(60 + 10 + 5 + 25) = 85%

Однако, несмотря на интуитивную понятность этой характеристики, существуют задачи, которые с её помощью решить нельзя. Допустим, что в задаче фрода нам важно не столько правильно распознать ситуации нарушения/не нарушения пользователем правил, сколько с высокой надёжностью выявить всех возможных нарушителей. Возможно, что выявленное множество будет достаточно малым, чтобы позволить дополнительную ручную проверку. В этом случае мы готовы пожертвовать точностью “Нет” предсказания ради того, чтобы точно идентифицировать все “Да” объекта, или другими словами, чтобы в вышеприведённом примере во второй строке первого столбца стоял 0 или число как можно меньшее. Но так как при этом мы всё же не хотим все объекты записывать в положительно определённые, необходимо найти какой-то баланс и эту задачу и решает ROC-кривая.

ROC расшифровывается как **R**eceiver **O**perating **C**haracteristic, т.е. рабочая характеристика приёмника и более-менее полное введение в это понятие можно прочитать на [[https://ru.wikipedia.org/wiki/ROC-%D0%BA%D1%80%D0%B8%D0%B2%D0%B0%D1%8F|вики]]. Для целей данной статьи достаточно понимать, что практически все классификаторы возвращают не метку объекта, а вероятность принадлежности объекта к тому или иному классу, то есть типичный ответ выглядит так

|=Объекты|=Вероятность “Да”|=Вероятность “Нет”|
|объект 1| 80%| 20%|
|объект 2| 49%| 51%|
|объект 3| 30%| 70%|

В этом случае для того, чтобы отнести объект к тому или иному классу, нужно выбрать какой-то порог вероятности, по которому будет происходить конечная классификация. В простейшем случае такой порог выбирается равным 50% и в этом примере объекты 2 и 3 будут промаркированы как “Нет”. Однако, с точки зрения фрода объект 2 является подозрительным и поэтому имеет смысл сдвинуть порог до 48%. Естественно, что выбирая различные пороги, будем получать разное количество правильно и неправильно определённых объектов и если нанести все точки на график, то как раз и получится ROC-кривая

[[image:roc_example.jpeg|link=source]]

Здесь по оси Y отложена //sensitivity//(чувствительность) – доля правильно идентифицированных объектов класса “Да” (в первом примере эта величина равна 60/(60 + 5) ~ 0.92), а по оси X доля правильно идентифицированных объектов класса “Нет” (в первом примере эта величина равна 25/(25 + 10) ~ 0.71). Как видно, чем больше правильно идентифицированных объектов класса “Да”, тем хуже определение объектов класса “Нет” и наоборот. При этом всегда есть две предельные точки, с //sensitivity// 0 и 1, соответственно когда все объекты маркируются “Нет” или все объекты маркируются “Да”. Классификатор получается тем лучше, чем сильнее ROC-кривая прижимается к верхнему левому углу, и идеальная кривая выглядит следующим образом

[[image:ideal_roc.jpeg|link=source]]

Таким образом задачей будет построение не просто классификаторов обладающих высокой //accuracy//, а классификаторов с наилучшей ROC-кривой, так как это позволит убить сразу двух зайцев: построить хороший классификатор и при этом дать возможность оптимизации классификатора под конкретную задачу. Более того, как будет показано ниже, перекалибровка результатов классификатора позволяет повысить конечную точность вычислений.

Для сравнения различных ROC-кривых используется метрика AUC – **A**rea **U**nder **C**urve (площадь под кривой), чем она больше, тем лучше ROC-кривая. Допуская некоторую вольность речи в ходе вычислений вместо AUC будет использовать слово ROC. Никакой несогласованности при этом не возникает, так как ROC-кривая означает график ROC-кривой, а число, называемое ROC обозначает площадь под этой кривой.

==**Тестирование и кросс-валидация**==

Одной из основных проблем различных методов классификации является переобучение, то есть ситуация, когда алгоритм настолько хорошо обучается на имеющихся данных, что производит правильную идентификацию в 100% случаев. И это было бы хорошо, но к сожалению практика показывает, что столь хорошо обученные методы начинают сильно ошибаться, когда их пытаются применить к новым данным. Это связано обычно с тем, что в исходных данных содержатся не имеющие значения шумы и попросту неправильные значения. Поэтому первый шаг, который имеет смысл сделать – это разбить исходные данные на две выборки, обучающую и проверочную. После обучения модели на обучающей выборке необходимо проверить её на проверочной выборке и в качестве меры качества обучения оценивать результаты полученные на проверочной выборке.

Однако, это не единственная операция которую нужно сделать. Допустим, что будет сравниваться несколько алгоритмов между собой, каждый из которых будет обучаться на обучающей выборке и проверяться на проверочной. При этом возникает опасность того, что эффективность работы алгоритмов будет зависеть от разбиения выборки. Может так оказаться (и оказывается), что на одних и тех же данных при одном разбиении выигрывает один алгоритм, а при другом разбиении – другой алгоритм. Чтобы уменьшить зависимость от разбиения производят операцию кросс-валидации. Она состоит в том, что выборка разбивается на несколько частей (стандартно берётся 10) и затем последовательно каждая из частей фиксируется как проверочная, а на оставшихся производится обучение. В результате получается набор характеристик, на каждой из проверочных выборок, который усредняется и уже это число используется в качестве меры эффективности алгоритма. Подобный подход позволяет снизить влияние разбиения на оценку качества алгоритма и к тому же даёт оценку дисперсии точности алгоритма.

Чтобы ещё больше снизить зависимость от разбиения иногда проводят процедуру повторной кросс-валидации. При этом процедура кросс-валидации повторяется несколько раз, с разными вариантами разбиения и в результате набирается достаточно богатая статистика, чтобы можно было достаточно корректно судить об эффективности того или иного метода, правда подобный подход используется не всегда, так как обычно он очень ресурсоёмкий. Однако, надо всё же обратить внимание на то, что кросс-валидация сама по себе не даёт точное значение эффективности наилучшего алгоритма, на практике значения полученные в результате кросс-валидации и на реальных данных могут заметно отличаться. Процесс кросс-валидации лишь позволяет сравнить разные алгоритмы между собой, показывая, какой алгоритм даёт хорошие результаты при этом мало завися от степени зашумлённости исходных данных, то есть в каком-то смысле оценивает алгоритм сам по себе, а не в зависимости от качества и вида входных данных.

Подытоживая, процедура оценки эффективности алгоритмов и выбор наилучшего метода будет осуществляться по следующей схеме

# Выборка разибвается на обучающую и проверочную.
# Выбирается семейство алгоритмов и на обучающей выборке производится процедура повторной кросс-валидации. По результатам проверки выбирается наилучший алгоритм.
# Лучший алгоритм из пункта 2 проверяется на проверочной выборке и производится сравнение данных кросс-валидации с данными полученными на тестовой выборки. Если результат не устраивает, то выбирается новое семейство алгоритмов и повторяются пункты 2-3.

Tagged , , , , , , . Bookmark the permalink.

One Response to Построение бинарных классификаторов. Теория.

  1. anon says:

    у ROC-кривой по оси абсцисс откладывается False Positive Rate, а не специфичность == 1 – FPR

Leave a Reply

Your email address will not be published. Required fields are marked *