Привет! Это третья статья из нашей серии. Сегодня мы наконец добрались до машинного обучения. Это будет захватывающе!

Краткое содержание статьи

  1. Вступление
  2. Древо решений
  • Как построить дерево решений
  • Алгоритм построения дерева
  • Другие критерии качества для разделения в задачах классификации
  • Как дерево решений работает с числовыми характеристиками
  • Ключевые параметры дерева
  • Класс DecisionTreeClassifier в Scikit-learn
  • Дерево решений в задаче регрессии

3. Метод ближайших соседей

  • Метод ближайших соседей в реальных приложениях
  • Класс KNeighborsClassifier в Scikit-learn

4. Выбор параметров модели и перекрестная проверка

5. Примеры применения и сложные случаи

  • Метод деревьев решений и ближайших соседей в задаче прогнозирования оттока клиентов
  • Сложный случай для деревьев решений
  • Деревья решений и k-NN в задаче распознавания рукописных цифр MNIST
  • Сложный случай для метода ближайших соседей.

6. Плюсы и минусы деревьев решений и метода ближайших соседей.

7. Задание №3

8. Полезные ресурсы

Следующий материал лучше рассматривать как блокнот Jupyter и его можно воспроизвести локально с помощью Jupyter, если вы клонируете репозиторий курсов.

1. Введение

Прежде чем мы углубимся в материал для статьи на этой неделе, давайте поговорим о типе проблемы, которую мы собираемся решить, и ее месте в захватывающей области машинного обучения. Книга Т. Митчелла Машинное обучение (1997) дает классическое общее определение машинного обучения следующим образом:

Считается, что компьютерная программа учится на опыте E в отношении некоторого класса задач T и показателя эффективности P, если ее производительность при выполнении задач в T, измеряемый P, улучшается с опытом E.

В различных настройках задачи T, P и E могут относиться к совершенно разным вещам. Вот некоторые из самых популярных задач T в машинном обучении:

  • отнесение экземпляра к одной из категорий по признакам;
  • регрессия - прогноз числовой целевой характеристики на основе других характеристик экземпляра;
  • кластеризация - определение разделов экземпляров на основе характеристик этих экземпляров, чтобы члены внутри групп были более похожи друг на друга, чем члены других групп;
  • обнаружение аномалий - поиск экземпляров, которые «сильно не похожи» на остальную часть выборки или на некоторую группу экземпляров;
  • и многое другое.

Хороший обзор представлен в главе Основы машинного обучения книги Глубокое обучение (Ян Гудфеллоу, Йошуа Бенжио, Аарон Курвиль, 2016).

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

Пример

Классификация и регрессия - это задачи обучения с учителем. Например, как кредитное учреждение, мы можем захотеть спрогнозировать невозврат кредита на основе данных, собранных о наших клиентах. Здесь опыт E - это доступные данные для обучения: набор экземпляров (клиентов), набор функций (например, возраст, зарплата , тип ссуды, прошлые дефолты по ссуде и т. д.) для каждого и целевая переменная (независимо от того, не выполнили ли они дефолт по ссуде). Эта целевая переменная является просто фактом невыполнения обязательств по ссуде (1 или 0), поэтому помните, что это проблема (бинарной) классификации. Если бы вы вместо этого прогнозировали на сколько времени платеж по ссуде просрочен, это превратилось бы в проблему регрессии.

Наконец, третий термин, используемый в определении машинного обучения, - это показатель оценки производительности алгоритма P. Такие показатели различаются для разных задач и алгоритмов, и мы обсудим их по мере того, как мы изучаем новые алгоритмы. Сейчас мы будем ссылаться на простую метрику алгоритмов классификации - долю правильных ответов - точность - в тестовом наборе.

Давайте рассмотрим две задачи обучения с учителем: классификацию и регрессию.

2. Дерево решений

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

С точки зрения машинного обучения его можно рассматривать как простой классификатор, определяющий подходящую форму публикации (книга, статья, глава книги, препринт, публикация в «Высшей школе экономики и СМИ») на основе контента. (книга, брошюра, статья), тип журнала, тип оригинальной публикации (научный журнал, сборники) и т. д.

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

В нашем следующем случае мы решаем задачу бинарной классификации (одобряем / отклоняем ссуду) по признакам «Возраст», «Собственность», «Доход» и «Образование».

Дерево решений как алгоритм машинного обучения по сути то же самое, что и диаграмма, показанная выше; мы включаем поток логических правил вида «значение функции a меньше x и значение функции b меньше y … = ›Категория 1» в древовидную структуру данных. Преимущество этого алгоритма в том, что они легко интерпретируемы. Например, используя приведенную выше схему, банк может объяснить клиенту, почему ему было отказано в ссуде: например, клиент не владеет домом, а его доход составляет менее 5000.

Как мы увидим позже, многие другие модели, хотя и более точные, не обладают этим свойством и могут рассматриваться как подход черного ящика, когда сложнее интерпретировать, как входные данные были преобразованы в выходные. Благодаря этой понятности и сходству с человеческим процессом принятия решений (вы можете легко объяснить свою модель своему боссу) деревья решений приобрели огромную популярность. C4.5, представитель этой группы методов классификации, даже первый в списке 10 лучших алгоритмов интеллектуального анализа данных (10 лучших алгоритмов интеллектуального анализа данных, Знания и информационные системы, 2008. PDF).

Как построить дерево решений

Ранее мы видели, что решение о предоставлении ссуды принимается на основании возраста, активов, дохода и других переменных. Но на какую переменную смотреть в первую очередь? Давайте обсудим простой пример, когда все переменные являются двоичными.

Вспомните игру «20 вопросов», на которую часто ссылаются при представлении деревьев решений. Вы, наверное, играли в эту игру - один человек думает о знаменитости, а другой пытается угадать, задавая только вопросы «да» или «нет». Какой вопрос задаст угадывающий в первую очередь? Конечно, они спросят тот, который больше всего сужает количество оставшихся вариантов. На вопрос: «Это Анджелина Джоли?» в случае отрицательного ответа оставит в поле зрения всех знаменитостей, кроме одной. Напротив, вопрос: «Знаменитость - женщина?» уменьшит возможности примерно до половины. То есть функция «пол» отделяет набор данных о знаменитостях намного лучше, чем другие функции, такие как «Анджелина Джоли», «Испанец» или «любит футбол». Это рассуждение соответствует концепции получения информации на основе энтропии.

Энтропия

Энтропия Шеннона определяется для системы с N возможными состояниями следующим образом:

где Pi - вероятность нахождения системы в i -м состоянии. Это очень важное понятие, используемое в физике, теории информации и других областях. Энтропию можно описать как степень хаоса в системе. Чем выше энтропия, тем менее упорядочена система и наоборот. Это поможет нам формализовать «эффективное разделение данных», о котором мы упоминали в контексте «20 вопросов».

Пример игрушки

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

Есть 9 синих шаров и 11 желтых шаров. Если случайно вытащить шар, то он будет синим с вероятностью p1 = 9/20 и желтым с вероятностью p2 = 11/20, что дает нам энтропию S0 = -9/20 log2 (9/20) - 11 / 20 log2 (11/20) ≈ 1. Это значение само по себе может мало сказать нам, но давайте посмотрим, как изменится значение, если мы разделим шары на две группы: с положением меньше или равным 12 и больше чем 12.

В левой группе 13 шаров, 8 синих и 5 желтых. Энтропия этой группы S1 = -5/13 log2 (5/13) - 8/13 log2 (8/13) ≈ 0,96. В правой группе 7 шаров, 1 синий и 6 желтых. Энтропия правой группы равна S2 = -1/7 log2 (1/7) - 6/7 log2 (6/7) ≈ 0,6. Как видите, энтропия уменьшилась в обеих группах, особенно в правой. Поскольку энтропия, по сути, является степенью хаоса (или неопределенности) в системе, уменьшение энтропии называется приростом информации. Формально информационный прирост (IG) для разделения на основе переменной Q (в данном примере это переменная «x ≤ 12») определяется как

где q - количество групп после разделения, Ni - количество объектов из выборки, в которых переменная Q равна i -ое значение. В нашем примере наше разделение дало две группы (q = 2), одна с 13 элементами (N1 = 13), другая с 7 (N2 = 7). Следовательно, мы можем вычислить прирост информации как

Оказывается, разделение шаров на две группы по принципу «координата меньше или равна 12» дало нам более упорядоченную систему. Давайте продолжим делить их на группы, пока все шары в каждой группе не станут одного цвета.

Для правой группы мы можем легко увидеть, что нам нужен только один дополнительный раздел, используя «координату, меньшую или равную 18». Но для левой группы нам нужно еще три. Обратите внимание, что энтропия группы, в которой все шары одного цвета, равна 0 (log2 (1) = 0).

Мы успешно построили дерево решений, которое предсказывает цвет шара в зависимости от его положения. Это дерево решений может не сработать, если мы добавим какие-либо шары, потому что оно идеально подходит для обучающего набора (начальные 20 мячей). Если бы мы хотели преуспеть в этом случае, дерево с меньшим количеством «вопросов» или разделений было бы более точным, даже если оно не идеально подходит для обучающей выборки. Мы обсудим проблему переоснащения позже.

Алгоритм построения дерева

Мы можем убедиться, что дерево, построенное в предыдущем примере, является оптимальным: потребовалось всего 5 «вопросов» (обусловленных переменной x), чтобы дерево решений идеально соответствовало обучающей выборке. При других условиях разделения результирующее дерево будет глубже, т.е. потребуется больше «вопросов», чтобы получить ответ.

В основе популярных алгоритмов построения дерева решений, таких как ID3 или C4.5, лежит принцип жадной максимизации прироста информации: на каждом шаге алгоритм выбирает переменную, которая дает наибольший прирост информации при расщеплении. Затем процедура повторяется рекурсивно до тех пор, пока энтропия не станет равной нулю (или некоторому небольшому значению для учета переобучения). Различные алгоритмы используют разные эвристики для «ранней остановки» или «отсечения», чтобы избежать построения переобученного дерева.

Другие критерии качества для разделения в задачах классификации

Мы обсудили, как энтропия позволяет формализовать разделы в дереве. Но это только одна эвристика; есть другие.

Максимальное увеличение этого критерия можно интерпретировать как максимизацию количества пар объектов одного класса, находящихся в одном поддереве (не путать с индексом Джини).

На практике ошибка неправильной классификации почти никогда не используется, и неопределенность Джини и получение информации работают аналогично.

Для бинарной классификации энтропия и неопределенность Джини принимают следующий вид:

где (p + - вероятность наличия у объекта метки +).

Если мы построим график этих двух функций против аргумента p +, мы увидим, что график энтропии очень близок к графику неопределенности Джини, удвоенной. Поэтому на практике эти два критерия практически идентичны.

Пример

Давайте рассмотрим подгонку дерева решений к некоторым синтетическим данным. Мы сгенерируем образцы из двух классов, оба с нормальным распределением, но с разными средствами.

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

Давайте попробуем разделить эти два класса, обучив Sklearn дерево решений. Мы будем использовать параметр max_depth, ограничивающий глубину дерева. Визуализируем получившуюся разделительную границу.

А как выглядит само дерево? Мы видим, что дерево «разрезает» пространство на 8 прямоугольников, т.е. у дерева 8 листьев. Внутри каждого прямоугольника дерево будет делать прогноз в соответствии с меткой большинства объектов внутри него.

Как мы можем «прочитать» такое дерево?

Вначале было 200 образцов (экземпляров), по 100 каждого класса. Энтропия исходного состояния была максимальной, S = 1. Затем было выполнено первое разделение выборок на 2 группы путем сравнения значения x2 с 1,211 (найдите эту часть границы на рисунке выше). При этом энтропия как левой, так и правой группы уменьшилась. Процесс продолжается до глубины 3. В этой визуализации чем больше выборок первого класса, тем темнее оранжевый цвет вершины; чем больше образцов второго класса, тем темнее синий цвет. Вначале количество выборок из двух классов одинаково, поэтому корневой узел дерева белый.

Как дерево решений работает с числовыми характеристиками

Предположим, у нас есть числовая функция «Возраст», которая имеет множество уникальных значений. Дерево решений будет искать лучшее (в соответствии с некоторым критерием получения информации) разбиение, проверяя двоичные атрибуты, такие как «Возраст

Рассмотрим пример. Предположим, у нас есть следующий набор данных:

Мы видим, что дерево использовало следующие 5 значений для оценки по возрасту: 43,5, 19, 22,5, 30 и 32 года. Если вы присмотритесь, это именно средние значения между возрастами, в которых целевой класс «переключается» с 1 на 0 или с 0 на 1. Чтобы проиллюстрировать далее, 43,5 - это среднее значение для 38 и 49 лет; 38-летний клиент не вернул ссуду, тогда как 49-летний клиент вернул. Дерево ищет значения, при которых целевой класс переключает свое значение в качестве порога для «отсечения» количественной переменной.

Учитывая эту информацию, как вы думаете, почему здесь нет смысла рассматривать такую ​​функцию, как «Возраст‹ 17,5 »?

Давайте рассмотрим более сложный пример, добавив переменную «Зарплата» (в тысячах долларов в год).

Если отсортировать по возрасту, целевой класс («невыполнение кредита») переключается (с 1 на 0 или наоборот) 5 раз. А если сортировать по зарплате, переключается 7 раз. Как дерево теперь будет выбирать объекты? Давайте посмотрим.

Мы видим, что дерево разделено как по заработной плате, так и по возрасту. Более того, пороговые значения для сравнения характеристик составляют 43,5 и 22,5 года и 95 тысяч и 30,5 тысяч в год. Опять же, мы видим, что 95 - это среднее значение между 88 и 102; человек с зарплатой 88 тыс. оказался «плохим», а человек с 102 тыс. - «хорошо». То же самое и с 30,5к. То есть искали только несколько значений для сравнения по возрасту и заработной плате. Почему дерево выбрало эти особенности? Потому что они дали лучшее разделение (согласно неопределенности Джини).

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

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

Чтобы проиллюстрировать, если мы разделим на «Зарплата ≤ 34,5», левая подгруппа будет иметь энтропию 0 (все клиенты «плохие»), а правая - 0,954 (3 «плохих» и 5 «хороших»). », Вы можете проверить это сами, так как это будет частью задания). Прирост информации составляет примерно 0,3. Если мы разделим на «Зарплата ≤ 95», левая подгруппа будет иметь энтропию 0,97 (6 «плохо» и 4 «хорошо»), а правая будет иметь энтропию 0 (группа, содержащая только один объект). Прирост информации составляет около 0,11. Если мы таким образом вычислим прирост информации для каждого раздела, мы сможем выбрать пороговые значения для сравнения каждой числовой характеристики перед построением большого дерева (с использованием всех функций).

Больше примеров дискретизации числовых признаков можно найти в сообщениях типа это или это. Одна из наиболее известных научных работ по этой теме - Об обработке непрерывнозначных атрибутов при генерации дерева решений (У. М. Файяд. КБ Ирани, Машинное обучение, 1992).

Ключевые параметры дерева

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

Есть два исключения, когда деревья построены на максимальную глубину:

  • Случайный лес (группа деревьев) усредняет ответы отдельных деревьев, построенных на максимальной глубине (позже мы поговорим о том, почему вы должны это делать)
  • Обрезка деревьев. При таком подходе дерево сначала строится на максимальную глубину. Затем снизу вверх некоторые узлы дерева удаляются путем сравнения качества дерева с этим разделом и без него (сравнение выполняется с использованием перекрестной проверки, подробнее об этом ниже).

На рисунке ниже показан пример разделительной границы, построенной в переоборудованном дереве.

Наиболее распространенные способы решения проблемы переобучения в деревьях решений следующие:

  • искусственное ограничение глубины или минимального количества выборок в листьях: строительство дерева просто останавливается в какой-то момент;
  • обрезка дерева.

Класс DecisionTreeClassifier в Scikit-learn

Основные параметры класса sklearn.tree.DecisionTreeClassifier:

  • max_depth - максимальная глубина дерева;
  • max_features - максимальное количество функций для поиска лучшего раздела (это необходимо при большом количестве функций, потому что было бы «дорого» искать разделы для всех функций);
  • min_samples_leaf - минимальное количество выборок в листе. Этот параметр предотвращает создание деревьев, в которых любой лист будет иметь только несколько элементов.

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

Дерево решений в задаче регрессии

При прогнозировании числовой переменной идея построения дерева остается прежней, но критерии качества меняются.

где n - количество выборок в листе, Yi - значение целевой переменной. Проще говоря, минимизируя дисперсию вокруг среднего, мы ищем функции, которые делят обучающий набор таким образом, что значения целевой функции в каждом листе примерно равны.

Пример

Давайте сгенерируем данные, распределенные функцией

с некоторым шумом. Затем мы обучим на нем дерево и покажем, какие прогнозы оно дает.

Мы видим, что дерево решений аппроксимирует данные кусочно-постоянной функцией.

3. Метод ближайших соседей

Метод ближайших соседей (k-Nearest Neighbors, или k-NN) - еще один очень популярный метод классификации, который также иногда используется в задачах регрессии. Это, как и деревья решений, один из наиболее понятных подходов к классификации. Основная интуиция заключается в том, что вы похожи на своих соседей. Более формально метод следует гипотезе компактности: если расстояние между примерами измерено достаточно хорошо, то похожие примеры с гораздо большей вероятностью принадлежат к одному классу.

Согласно методу ближайших соседей, зеленый шар будет классифицироваться как «синий», а не «красный».

В качестве другого примера, если вы не знаете, как пометить Bluetooth-гарнитуру в онлайн-списке, вы можете найти 5 похожих гарнитур, и, если 4 из них помечены как «аксессуары» и только 1 как «Технологии», то вы он также будет помечен как «аксессуары».

Чтобы классифицировать каждый образец из набора тестов, необходимо выполнить следующие операции по порядку:

  1. Рассчитайте расстояние до каждого образца в обучающей выборке.
  2. Выделите k образцов из обучающей выборки с минимальным расстоянием до них.
  3. Класс тестовой выборки будет наиболее частым среди этих k ближайших соседей.

Метод довольно легко адаптируется к задаче регрессии: на шаге 3 он возвращает не класс, а число - среднее (или медиану) целевой переменной среди соседей.

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

Ближайшие соседи - это хорошо проработанный подход. Существует множество важных теорем, утверждающих, что для бесконечных наборов данных это оптимальный метод классификации. Авторы классической книги Элементы статистического обучения считают k-NN теоретически идеальным алгоритмом, использование которого ограничивается только вычислительной мощностью и проклятием размерности.

Метод ближайших соседей в реальных приложениях

  • k-NN может служить хорошей отправной точкой (базой) в некоторых случаях;
  • В соревнованиях Kaggle k-NN часто используется для построения мета-характеристик (т. Е. Прогнозов k-NN в качестве входных данных для других моделей) или для суммирования / смешивания;
  • Метод ближайших соседей распространяется на другие задачи, такие как системы рекомендаций. Первоначальным решением может быть рекомендация продукта (или услуги), популярного среди ближайших соседей человека, для которого мы хотим порекомендовать;
  • На практике на больших наборах данных часто используются приближенные методы поиска ближайших соседей. Существует ряд библиотек с открытым исходным кодом, реализующих такие алгоритмы; посетите библиотеку Spotify Annoy.

Качество классификации / регрессии с k-NN зависит от нескольких параметров:

  • Количество соседей k.
  • Измерение расстояния между выборками (обычно это расстояния Хэмминга, Евклида, косинуса и Минковского). Обратите внимание, что для большинства этих показателей требуется масштабирование данных. Проще говоря, мы не хотим, чтобы функция «зарплата», которая составляет порядка тысяч, влияла на расстояние больше, чем на «возраст», который обычно меньше 100.
  • Веса соседей (каждый сосед может вносить разные веса; например, чем дальше образец, тем меньше вес).

Класс KNeighborsClassifier в Scikit-learn

Основными параметрами класса sklearn.neighbors.KNeighborsClassifier являются:

  • веса: uniform (все веса равны), distance (вес обратно пропорционален расстоянию от тестового образца) или любая другая определяемая пользователем функция;
  • алгоритм (необязательно): brute, ball_tree, KD_tree или auto. В первом случае ближайшие соседи для каждого тестового примера вычисляются путем поиска по сетке по обучающему набору. Во втором и третьем случаях расстояния между примерами хранятся в дереве, чтобы ускорить поиск ближайших соседей. Если вы установите для этого параметра значение auto, правильный способ поиска соседей будет автоматически выбран на основе обучающего набора.
  • leaf_size (необязательно): порог перехода к поиску по сетке, если алгоритм поиска соседей BallTree или KDTree;
  • метрика: minkowski, manhattan, euclidean, chebyshev или другие.

4. Выбор параметров модели и перекрестная проверка

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

Часто это делается одним из двух способов:

  • зарезервировать часть набора данных (удерживаемый / удерживаемый набор). Мы резервируем часть обучающего набора (обычно от 20% до 40%), обучаем модель на оставшихся данных (60–80% исходного набора) и вычисляем показатели производительности для модели (например, точность) на удержании. -выходной набор.
  • перекрестная проверка. Наиболее частым случаем здесь является k-кратная перекрестная проверка.

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

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

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

5. Примеры применения и сложные случаи

Метод деревьев решений и ближайших соседей в задаче прогнозирования оттока клиентов

Давайте прочитаем данные в DataFrame и обработаем их. Сохраните Состояние в отдельном Series объекте и удалите его из фрейма данных. Мы обучим первую модель без функции State, а затем посмотрим, поможет ли она.

Давайте выделим 70% набора для обучения (X_train, y_train) и 30% для набора удержания (X_holdout, y_holdout). Комплект удержания не будет задействован в настройке параметров моделей. Воспользуемся им в конце, после настройки, чтобы оценить качество полученной модели. Обучим 2 модели: дерево решений и k-NN. Мы не знаем, какие параметры являются хорошими, поэтому предположим несколько случайных: глубина дерева 5 и количество ближайших соседей равно 10.

Давайте оценим качество предсказания по нашему набору удержаний с помощью простого показателя - доли правильных ответов (точности). Дерево решений сработало лучше - процент правильных ответов составляет около 94% (дерево решений) против 88% (k-NN). Обратите внимание, что эта производительность достигается за счет использования случайных параметров.

Теперь давайте определим параметры дерева с помощью перекрестной проверки. Мы настроим максимальную глубину и максимальное количество функций, используемых для каждого разделения. Вот суть того, как работает GridSearchCV: для каждой уникальной пары значений max_depth и max_features вычислите производительность модели с 5-кратной перекрестной проверкой, а затем выберите лучшую комбинацию параметров.

Перечислим лучшие параметры и соответствующую среднюю точность перекрестной проверки.

Нарисуем получившееся дерево. Из-за того, что это не совсем игрушечный пример (максимальная глубина 6), картинка не такая уж и маленькая, но вы можете «пройтись» по дереву, если локально откроете соответствующее изображение, загруженное из репозитория курса.

Теперь давайте настроим количество соседей k для k-NN:

Здесь дерево оказалось лучше, чем алгоритм ближайших соседей: точность 94,2% / 94,6% для перекрестной проверки и удержания соответственно. Деревья решений работают очень хорошо, и даже случайный лес (давайте сейчас представим его как группу деревьев, которые лучше работают вместе) в этом примере не может обеспечить лучшую производительность (95,1% / 95,3%), несмотря на то, что обучение длилось намного дольше.

Сложный случай для деревьев решений

Чтобы продолжить обсуждение плюсов и минусов рассматриваемых методов, давайте рассмотрим простую задачу классификации, в которой дерево будет работать хорошо, но делает это «чрезмерно сложным» способом. Давайте создадим набор точек на плоскости (2 объекта), каждая точка будет одного из двух классов (+1 для красного или -1 для желтого). Если вы посмотрите на это как на проблему классификации, это покажется очень простым: классы разделены линией.

Однако граница, которую строит дерево решений, слишком сложна; плюс само дерево очень глубокое. Кроме того, представьте, насколько плохо дерево будет распространяться на пространство за пределами квадратов 30 x 30, которые обрамляют обучающую выборку.

Мы получили эту слишком сложную конструкцию, хотя решение представляет собой прямую линию x1 = x2.

Метод одного ближайшего соседа работает лучше, чем дерево, но все же не так хорош, как линейный классификатор (наша следующая тема).

Деревья решений и k-NN в задаче распознавания рукописных цифр MNIST

Теперь давайте посмотрим, как эти два алгоритма работают с реальной задачей. Мы будем использовать sklearn встроенный набор данных для рукописных цифр. Эта задача - пример того, как k-NN работает на удивление хорошо.

Картинки здесь представляют собой матрицы 8х8 (интенсивность белого цвета для каждого пикселя). Затем каждая такая матрица «разворачивается» в вектор длиной 64, и мы получаем характеристическое описание объекта.

Давайте нарисуем рукописные цифры. Мы видим, что они различимы.

Затем давайте проведем тот же эксперимент, что и в предыдущем задании, но на этот раз изменим диапазоны настраиваемых параметров.

Давайте выберем 70% набора данных для обучения (X_train, y_train) и 30% для удержания (X_holdout, y_holdout). Набор удерживающих устройств не будет участвовать в настройке параметров модели; мы воспользуемся им в конце, чтобы проверить качество полученной модели.

Давайте обучим дерево решений и k-NN с нашими случайными параметрами и сделаем прогнозы на нашем удерживающем множестве. Мы видим, что k-NN работает намного лучше, но обратите внимание, что это со случайными параметрами.

Теперь давайте настроим параметры нашей модели, используя перекрестную проверку, как и раньше, но теперь мы учтем, что у нас больше функций, чем в предыдущей задаче: 64.

Давайте посмотрим на лучшую комбинацию параметров и соответствующую точность перекрестной проверки:

Это уже превышает 66%, но не совсем 97%. k-NN лучше работает с этим набором данных. В случае одного ближайшего соседа мы смогли достичь 99% предположений при перекрестной проверке.

Давайте обучим случайный лес на том же наборе данных, он работает лучше, чем k-NN для большинства наборов данных. Но у нас здесь есть исключение.

Вы правильно заметили, что мы не настраивали здесь никаких RandomForestClassifier параметров. Даже с настройкой точность обучения не достигает 98%, как это было с одним ближайшим соседом.

Заключение этого эксперимента (и общий совет): сначала проверьте простые модели на ваших данных: дерево решений и ближайшие соседи (в следующий раз мы также добавим в этот список логистическую регрессию). Возможно, эти методы уже работают достаточно хорошо.

Сложный случай для метода ближайших соседей.

Рассмотрим еще один простой пример. В задаче классификации одна из характеристик будет просто пропорциональна вектору ответов, но это не поможет для метода ближайших соседей.

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

Можно видеть, что k-NN с евклидовым расстоянием не очень хорошо работает с задачей, даже если вы изменяете количество ближайших соседей в широком диапазоне.

В отличие от этого, дерево решений легко «обнаруживает» скрытые зависимости в данных, несмотря на ограничение максимальной глубины.

Во втором примере дерево прекрасно решало проблему, в то время как k-NN испытывал трудности. Однако это скорее недостаток использования евклидова расстояния, чем метода. Это не позволило нам выявить, что одна функция намного лучше других.

6. Плюсы и минусы деревьев решений и метода ближайших соседей.

Плюсы и минусы деревьев решений

Плюсы:

  • Создание четких и понятных для человека правил классификации, например «Если возраст‹ 25 и интересуется мотоциклами, откажитесь в ссуде ». Это свойство называется интерпретируемостью модели.
  • Деревья решений можно легко визуализировать, т.е. как саму модель (дерево), так и прогноз для определенного тестового объекта (путь в дереве) можно «интерпретировать».
  • Быстрое обучение и прогнозирование.
  • Небольшое количество параметров модели.
  • Поддерживает как числовые, так и категориальные функции.

Минусы:

  • Деревья очень чувствительны к шуму во входных данных; вся модель может измениться, если обучающий набор будет немного изменен (например, удалить функцию, добавить несколько объектов). Это ухудшает интерпретируемость модели.
  • Разделительная граница, построенная деревом решений, имеет свои ограничения - она ​​состоит из гиперплоскостей, перпендикулярных одной из осей координат, что на практике уступает по качеству некоторым другим методам.
  • Нам нужно избегать переобучения путем обрезки, установки минимального количества выборок в каждом листе или определения максимальной глубины для дерева. Обратите внимание, что переоснащение является проблемой для всех методов машинного обучения.
  • Нестабильность. Небольшие изменения данных могут существенно изменить дерево решений. Эта проблема решается с помощью ансамблей деревьев решений (обсуждаемых в следующий раз).
  • Задача поиска оптимального дерева решений является NP-полной. На практике используются некоторые эвристики, такие как жадный поиск объекта с максимальным набором информации, но он не гарантирует нахождение глобального оптимального дерева.
  • Трудности с поддержкой отсутствующих значений в данных. По оценке Фридмана, для поддержки пробелов в данных в CART требуется около 50% кода (улучшенная версия этого алгоритма реализована в sklearn).
  • Модель может только интерполировать, но не экстраполировать (то же самое верно для случайных лесов и увеличения деревьев). То есть дерево решений делает постоянный прогноз для объектов, которые лежат за ограничивающей рамкой, установленной обучающим набором в пространстве признаков. В нашем примере с желтыми и синими шарами это будет означать, что модель дает одинаковые прогнозы для всех шаров с позициями ›19 или‹ 0.

Плюсы и минусы метода ближайших соседей

Плюсы:

  • Простая реализация.
  • Хорошо изучен.
  • Обычно этот метод является хорошим первым решением не только для классификации или регрессии, но и для рекомендаций.
  • Его можно адаптировать к определенной проблеме, выбрав правильные метрики или ядро ​​(в двух словах, ядро ​​может устанавливать операцию подобия для сложных объектов, таких как графы, сохраняя при этом подход k-NN одинаковым). Кстати, Александр Дьяконов, бывший топ-1 кагглер, любит простейшие k-NN, но с настроенной метрикой подобия объектов.
  • Хорошая интерпретируемость. Бывают исключения: если количество соседей велико, интерпретируемость ухудшается («Мы не давали ему ссуду, потому что он похож на 350 клиентов, из которых 70 - плохие, а это на 12% выше среднего. для набора данных »).

Минусы:

  • Метод считается быстрым по сравнению с композициями алгоритмов, но количество соседей, используемых для классификации, в реальной жизни обычно велико (100–150), и в этом случае алгоритм не будет работать так быстро, как дерево решений.
  • Если в наборе данных много переменных, трудно найти правильные веса и определить, какие характеристики не важны для классификации / регрессии.
  • Зависимость от выбранной метрики расстояния между объектами. Выбор евклидова расстояния по умолчанию часто необоснован. Вы можете найти хорошее решение, выполнив поиск по сетке по параметрам, но это отнимает много времени для больших наборов данных.
  • Теоретических способов выбора количества соседей нет - только поиск по сетке (хотя часто это верно для всех гиперпараметров всех моделей). В случае небольшого числа соседей метод чувствителен к выбросам, то есть склонен к переобучению.
  • Как правило, из-за проклятия размерности он не работает, когда функций много. Профессор Педро Домингос, известный член сообщества машинного обучения, говорит об этом здесь в своей популярной статье Несколько полезных вещей, которые нужно знать о машинном обучении; также проклятие размерности описано в книге Глубокое обучение в этой главе.

Информации много, но, надеюсь, эта статья надолго будет для вас отличным справочником :)

7. Задание №3.

Полные версии заданий объявляются каждую неделю в новом прогоне курса (1 октября 2018 г.). А пока вы можете потренироваться с демо-версией: Kaggle Kernel, nbviewer.

8. Полезные ресурсы

  • Деревья решений и k ближайших соседей описаны практически в каждой книге по машинному обучению. Мы рекомендуем «Распознавание образов и машинное обучение» (К. Бишоп) и «Машинное обучение: вероятностная перспектива» (К. Мерфи).
  • Книга «Машинное обучение в действии» (П. Харрингтон) проведет вас через реализации классических алгоритмов машинного обучения на чистом Python.
  • Библиотека Scikit-learn. Эти ребята упорно работают над написанием действительно понятной документации.
  • Scipy 2017 scikit-learn tutorial Алекса Грамфорта и Андреаса Мюллера.
  • Еще один курс ML с очень хорошими материалами.
  • Реализации многих алгоритмов машинного обучения. Хорошо для поиска деревьев решений и k-NN.
  • И многие другие, не стесняйтесь делиться в комментариях.

Автор: Юрий Кашницкий. Перевод и редакция: Кристина Буцко, Глеб Филатов, Юаньюань Пао.