Бинарный линейный классификатор

Бинарный линейный классификатор
XN={(x1,y1),…, (xN,yN)}, xi∈ RP, yi ∈{-1,+1}
Цель: каждый новый входной вектор x отнести к одному их двух классов – положительному «+1» или отрицательному «+1»

Примеры задач Data mining
классификация – отнесение объекта к одной из категорий (классов) на основании его признаков
регрессия – прогнозирование значения непрерывного количественного признака объекта на основании прочих его признаков
кластеризация – разбиение множества объектов на группы на основании признаков этих объектов так, чтобы внутри групп объекты были похожи между собой сильнее, чем вне одной группы
Задачи классификации и регрессии – это задачи обучения с учителем.

Линейная модель классификации

Пример нелинейного разделения классов

Confusion matrix (матрица ошибок классификации)

Метрики качества классификации
Доля правильных ответов:
Малоинформативна в задачах с неравными классами.
Пример. Допустим, мы хотим оценить работу спам-фильтра почты. У нас есть 100 не-спам писем, 90 из которых наш классификатор определил верно, и 10 спам-писем, 5 из которых классификатор также определил верно. Предположим, класс1- спам, а класс -1 -не спам
гда accuracy:
Если мы просто будем предсказывать все письма как не-спам, то получим более высокую accuracy
0.864
0.909

Метрики качества классификации
precision (точность) и recall (полнота).
Precision показывает долю объектов, названных классификатором положительными и при этом действительно являющимися положительными, а recall показывает, какую долю объектов положительного класса из всех объектов положительного класса нашел алгоритм.
Precision не позволяет записывать все объекты в один класс, так как в этом случае растет значение FP. Recall демонстрирует способность алгоритма обнаруживать данный класс вообще, а precision — способность отличать этот класс от других классов.

AUC-ROC –площадь под кривой ошибок
TPR - это полнота, а FPR показывает, какую долю из объектов отрицательного класса алгоритм предсказал неверно.
Кривая ошибок или ROC-кривая – графическая характеристика качества бинарного классификатора, зависимость доли верных положительных классификаций от доли ложных положительных классификаций при варьировании порога решающего правила.

AUC-ROC –площадь под кривой ошибок
В идеальном случае, когда классификатор не делает ошибок (FPR = 0, TPR = 1), площадь под кривой, равна 1; в противном случае, когда классификатор случайно выдает вероятности классов, AUC-ROC = 0.5.
Каждая точка на графике соответствует выбору некоторого порога вероятности, разделяющего положительный и отрицательный класс.
Критерий AUC-ROC устойчив к несбалансированным классам и может быть интерпретирован как вероятность того, что случайно выбранный положительный объект будет иметь более высокую вероятность быть положительно определенным данным классификатором, чем случайно выбранный отрицательный объект.
Площадь под кривой в данном случае показывает качество алгоритма (больше — лучше), кроме этого, важной является крутизна самой кривой — мы хотим максимизировать TPR, минимизируя FPR, а значит, наша кривая в идеале должна стремиться к точке (0,1).

Чувствительность и специфичность
Наряду с FPR и TPR при оценке качества классификации используют также понятия чувствительности и специфичности, которые изменяются в интервале [0,1]:
чувствительность алгоритма совпадает с TPR (долей положительных объектов, правильно классифицированных алгоритмом);
специфичность алгоритма определяется как 1-FPR (это доля отрицательных объектов, правильно классифицированных алгоритмом).
Модель с высокой чувствительностью чаще дает истинный результат при наличии положительного исхода (хорошо обнаруживает положительные примеры). Наоборот, модель с высокой специфичностью чаще дает истинный результат при наличии отрицательного исхода (хорошо обнаруживает отрицательные примеры).

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

Графическая иллюстрация нелинейного разделения классов
На рисунки приведен пример классификации объектов по двум непрерывным признакам. Объекты, относящиеся к разным классам, отмечены знаками "+" и "–".

Использование деревьев решений в задачах регрессии

Этапы построения дерева решений
1. Выбор критерия точности прогноза
2. Выбор типа ветвления
3. Определение момента прекращения ветвлений
4. Определение "подходящих" размеров дерева
Выбор критерия точности прогноза
Accuracy, precision, recall – в задачах классификации
МSE,MAE– в задачах регрессии

Выбор типа ветвления (criterion)
Есть различные способы выбирать очередной признак для текущего ветвления:
Алгоритм ID3, где выбор атрибута происходит на основании прироста информации ( Gain ).
Алгоритм C4.5 (улучшенная версия ID3), где выбор атрибута происходит на основании нормализованного прироста информации ( Gain Ratio).
Алгоритм CART где выбор атрибута происходит на основании индекса Джини.

Энтропия
Энтропия Шеннона для системы с s возможными состояниями:

Прирост информации (ID3)

Прогноз игры в футбол
Первый вариант дерева
Второй вариант дерева

Вычисление энтропии и прироста информации

Нормализованный прирост информации (C4.5)

Индекс Gini (CART)

Правила разбиения (CART)

Правила остановки
Минимальное число объектов, при котором выполняется расщепление (min_samples_split). В этом варианте ветвление прекращается, когда все терминальные вершины, содержащие более одного класса, содержат не более чем заданное число объектов (наблюдений).
Минимальное число объектов в листьях (min_samples_leaf)
Доля неклассифицированных. В этом варианте ветвление прекращается, когда все терминальные вершины, содержащие более одного класса, содержат не более чем заданную долю неправильно классифицированных объектов (наблюдений).
Максимальная глубина деревьев (max_depth)

Механизм отсечения дерева (CART)

Иллюстрация переобучения

Случайный лес (Random forest)
Случайный лес — алгоритм машинного обучения, заключающийся в использовании комитета (ансамбля) деревьев решений.

Обучение случайного леса