Предположим, вы пишете для популярного фантастического блога, и вас попросили написать новую историю для публикации в этом месяце.
Начинать с нуля было бы сложно, не так ли?
Вы, вероятно, проверили бы любые данные пользовательской аналитики, которые вы могли бы прочитать. Пройдясь по статистике, вы узнаете, что большинство читаемых постов связаны с историями о приключениях главного героя в неизведанной стране. Вы также обнаружили, что люди в возрасте от 13 до 19 лет читают больше любовных историй, чем другие группы. Большинство комментируемых постов связаны с фантастическими историями, вероятно, потому, что людям нравится больше обсуждать их.
Вы пришли к выводу, что написание истории, связанной с приключениями, любовной историей и фантастическим фоном, имеет смысл для популярного поста.
Итак, то, что вы сделали выше, является центральным для того, что на самом деле делают деревья решений, они разбивают проблему на основе различных входных данных, учитывая, что они хотят максимизировать метрику. В вашем случае вы хотели максимизировать популярность своих сообщений, поэтому вы разделили своих читателей и, наконец, вы приступили к написанию отличной истории с высокой вероятностью стать популярной (ну, многое зависит и от автора!!).
Древо решений
Дерево решений — это непараметрические (предполагающие отсутствие конкретного распределения данных) контролируемые методы обучения, которые помогают решать как задачи классификации, так и проблемы регрессии.
Он в основном использует схему рекурсивного разделения для разбиения пространства признаков на более мелкие области (с использованием прямоугольников с параллельными осями), где он использует такие показатели, как голосование большинством (в случае классификации) или усреднение (в случае регрессии) и, следовательно, любая точка данных из этого будет предсказано, что регион будет иметь значение метрики.
Как обучается дерево решений?
DT использует следующие основные шаги при обучении:
- Разделите функциональное пространство, если это возможно, в противном случае остановитесь
- Если разделы созданы, раздел на этих разделах
- Вернуться к шагу 1
Вы должны подумать: «Значит, разделение — это центральная идея, я понял», верно? Нет, это не так просто, как кажется, многое происходит под капотом, как мы увидим.
По-видимому, приведенный выше алгоритм обучения был бы вычислительно сложным, потому что задача о разбиении сама по себе является NP-полной (вычислительно невозможной), поэтому мы используем жадный подход (свойство жадного выбора) для рекурсивного разбиения и, таким образом, делаем его вычислительно выполнимым. По сути, мы используем некоторую меру и разбиение на основе увеличения этой меры жадным образом, а не проверяем все возможные комбинации.
Еще одна проблема, которая часто возникает, заключается в том, что дерево, созданное из вышеперечисленных шагов, может быть очень сложным и может переопределять данные, т. Е. Дерево очень хорошо изучило обучающие данные, но не может изучить общий шаблон, из-за чего оно плохо работает на тестовом наборе. (или реальные данные). Чтобы уменьшить эту проблему, мы могли бы использовать обрезку, когда мы вырезаем (обрезаем) сложные части дерева, чтобы убедиться, что оно запоминает важный шаблон. Существуют различные методы, которые помогают нам сделать то, что мы увидим позже.
Разметка
Как мы видели выше, для создания разделов используется жадный подход.
Созданные новые разделенные области должны гарантировать, что они имеют более низкий беспорядок, чем исходная область. Для этого нам нужно найти две вещи:
- Входная переменная для разделения (например, var1 или var2)
- Значение точки разделения входной переменной (например, var1 ›6 , поэтому точка разделения равна 6)
В общем случае мы обычно следуем процедуре, которая проходит через все пары k входных данных и их s наилучшее разделение точки
Как правило, мы создаем два раздела, но также возможно создание более двух разделов, так почему же мы сохраняем разделы двоичными? ну, потому что это помогает нам сохранить нашу модель простой и масштабируемой.
Хорошо, но где дерево?
Вам, наверное, интересно, что мы видели, как обучаются деревья решений, но мы нигде не видели никаких деревьев, верно?
Что ж, рекурсивное разбиение делит пространство функций, и на каждом этапе создаются новые разделы и далее разбиваются, пока мы не достигнем точки, в которой дальнейшее разбиение невозможно или не будет выполнен критерий остановки.
Если мы визуализируем этот процесс, он напоминает древовидную структуру данных, где последние неразделяемые точки называются листом дерева, а первый шаг разбиения — корнем, а все точки разделения представлены узлами.
Таким образом, дерево решений — это, по сути, перевернутое дерево!!
Требования к алгоритму дерева решений
- критерий выбора наилучшего сплита (функция и стоимость сплита)
- критерий прекращения разделения или прекращения роста дерева
- правило предсказания класса (классификация) или значения (регрессия) наблюдения
Второе требование является самым сложным:
- Если дерево слишком глубокое: Переоснащение, высокая изменчивость
- Если дерево недостаточно глубокое: недообучение, большое смещение
Узнайте больше о компромиссе смещения и дисперсии здесь.
Для этого у нас есть много параметров и, настраивая их, мы можем контролировать глубину, мы проверим их позже в посте.
Как выбрать лучший сплит/раздел?
Проверяем, хороши ли новые созданные разделы, если они:
- уменьшают беспорядок (неоднородность) по сравнению с исходным пространством
- увеличивают однородность внутри разделенных регионов (большинство точек данных должны быть похожими и принадлежать к одному классу или иметь одинаковое среднее значение)
Теперь нам нужна функция для измерения беспорядка или примеси, с помощью которой мы можем сравнить примесь в исходном пространстве признаков и разделенном пространстве признаков и, таким образом, найти разделение, которое максимизирует эту разницу примеси между ними, эту разницу также называется Получением информации.
Получение информации
Это мера, которая помогает нам найти наиболее «информативное» разделение.
Информативное разделение означает разделение, которое уменьшает максимальную нечистоту/беспорядок между родительским узлом и дочерним узлом.
IG = беспорядок в родительском узле — среднее значение беспорядка в дочерних узлах
Теперь давайте посмотрим, какие свойства необходимы для функции примеси/беспорядка:
- Это должно иметь высокое значение, если классы, присутствующие в разделе, относятся к обоим типам в одинаковой пропорции.
- Он должен иметь более низкое значение, если классы, представленные в разделе, однородны.
Следующие показатели помогают нам сделать это:
Коэффициент ошибочной классификации
Это доля наблюдений, не принадлежащих к наиболее распространенному классу.
где p представляет собой долю наблюдений в рассматриваемой нами области, относящихся к i-му классу.
Индекс Джини или примесь
Это мера того, как часто случайно выбранный элемент из набора был бы неправильно помечен, если бы он был помечен случайным образом в соответствии с распределением меток в подмножестве. Он принимает небольшое значение, если все p близки к нулю или единице.
где m — количество классов, а p — вероятность неправильного отнесения элемента к классу i.
Пример: Предположим, у нас есть 2 класса красный и синий и 10 точек, где 5 относятся к красному классу и 5 относятся к синему классу.
теперь мы пройдемся по всем классам и попытаемся найти вероятность неправильной классификации точек данных.
Следовательно, для максимальной примеси (т.е. равного количества обоих классов) gini возвращает максимальное значение 0,5.
Максимальное значение: 0,5 (равные пропорции классов)
Минимальное значение: 0 (присутствует только один класс)
Энтропия или отклонение
где m — количество классов, а p — доля наблюдений, принадлежащих классу i.
Энтропия — это ожидаемое количество битов, необходимых для кодирования класса случайно выбранного наблюдения.
Интерпретация теории информации: код оптимальной длины присваивает = log(p) бит сообщению с вероятностью p.
Пример. Предположим, у вас есть набор данных с 16 наблюдениями, из которых 9 наблюдений относятся к классу A, а 7 наблюдений относятся к классу B.
Максимальное значение: 1 (равные пропорции классов)
Минимальное значение: 0 (присутствует только один класс)
Посмотрите этот хороший пост Себастьяна Рашки о том, почему уровень ошибочной классификации не является предпочтительным в наши дни.
Таким образом, каждый раз, когда нам нужно разделить, мы просто вычисляем текущую примесь, используя один из вышеперечисленных методов, и находим все возможные комбинации функций разделения и их значений разделения, затем мы выбираем комбинацию, расчетная примесь которой при вычитании из примеси родительского узла дает максимальное значение.
Итак, когда перестать выращивать дерево?
Переходя ко второму требованию, мы должны знать, когда прекратить дальнейшее разбиение узлов, чтобы мы могли найти дерево, которое не соответствует данным больше или меньше.
Но почему?
По сути, дерево решений будет соответствовать обучающему набору на 100% (при условии отсутствия шума в метках) без критериев остановки, но это не означает, что оно будет иметь такую же производительность на невидимом тестовом наборе. Это означает, что то, чему научился DT, плохо обобщается или просто бесполезно для прогнозирования будущих наблюдений.
Следовательно, мы стараемся, чтобы наше дерево было достаточно сложным, чтобы не подгонять, но и не подгонять тренировочные данные.
Ниже приведены несколько способов просто контролировать размер дерева:
- Фиксированная глубина
Учитывая заданную глубину и не выращивайте дерево выше этой глубины.
- Минимальное количество образцов на листе
Учитывая узел, мы разделяем его только в том случае, если количество выборок превышает некоторое значениеk.
- Увеличение объема информации
Для заданного узла мы разделяем только в том случае, если наилучшее разделение увеличивает прирост информации (IG) выше заданного значения k,что является минимально необходимым IG для разделения.
Примечание.
Следует отметить, что приведенные выше критерии остановки для управления размером дерева не являются полностью надежными или удовлетворительными, поскольку метод выращивания дерева является жадным. Каждый сплит близорук, т.е. мы не проверяем все возможные комбинации (которые бесконечны). Таким образом, разделение, которое может быть плохим на данном шаге, может привести к очень хорошим разделениям на следующих шагах, и это странное поведение оставляет много места для надежности.
Использованная литература:
- Очень познавательные слайды лекций Джулии Шоллер здесь.
Это все для части 1.
В следующей части мы увидим, как правила прогнозирования используются для того, чтобы наши деревья могли предсказывать как дискретные, так и непрерывные выходные данные, и мы рассмотрим плюсы и минусы деревьев решений и сравним их с другими алгоритмами машинного обучения.
Это сообщение является первой частью сообщений о деревьях решений.
