Алгоритм дерева решений

Этот пост посвящен основам деревьев решений, их структуре и алгоритмическому дизайну.

Введение

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

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

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

Чем деревья решений отличаются от других моделей машинного обучения

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

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

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

Потеря предсказательной силы в деревьях решений

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

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

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

Функции стоимости для задач регрессии и классификации.

Деревья решений можно использовать для задач регрессии так же, как и другие линейные регрессоры. Мы делаем прогнозы для данного наблюдения, а затем пытаемся минимизировать среднеквадратичное значение наблюдений. Прогноз в дереве регрессии — это среднее значение наблюдений в листовом узле, в который попадает наша данная выборка. Функция стоимости представлена ​​ниже:

Здесь J — это общее количество сформированных подпространств, а R_j представляет одну из этих областей. y_Rj — это средний ответ из подобласти, который служит прогнозом для всех наблюдений, попадающих в эту область.

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

Когда мы используем деревья решений для задач классификации, каждый конечный узел представляет уникальный класс, который может принимать конкретное наблюдение. Если листовой узел имеет наблюдения с разными классами, то он не является хорошим предсказателем для любого данного наблюдения, поскольку он может принадлежать любому из этих заданных классов. С другой стороны, листовой узел, в котором есть наблюдения, принадлежащие одному классу, является хорошим предиктором, потому что, если наблюдение попадает в этот листовой узел, то весьма вероятно, что он имеет данный класс. Gini представляет вероятность того, что две точки конечного узла принадлежат одному и тому же классу. Он находится в диапазоне от 0 до 1, где 1 является самым чистым узлом с наблюдениями одного класса. Формула индекса Джини приведена ниже:

Здесь p(i) представляет вероятность данного класса, а C представляет общее количество классов. примесь Джинни определяется по следующей формуле:

Значение 1 для Джинни дает значение 0 для примеси Джинни. Примесь Джинни служит мерой для проверки производительности модели дерева решений, поскольку идеальная модель дерева решений должна иметь наименьшее количество примеси Джинни в каждом из своих листовых узлов. Аналогичной функцией стоимости является энтропия узла.

Обрезка деревьев

Следующим критерием оптимизации является длина дерева. Большие деревья с большим количеством внутренних узлов имеют высокую дисперсию и склонны к переобучению данных, в то время как деревья меньшего размера с небольшим количеством внутренних узлов имеют низкую дисперсию. Наша цель — найти оптимальную длину дерева с нужным количеством смещения и дисперсии. Один из способов добиться этого — создать большое дерево, а затем двигаться в обратном направлении, удаляя внутренние узлы без существенного ущерба для точности модели. Это называется обрезкой деревьев. Таким образом, наше результирующее дерево является поддеревом исходного большого дерева. Функция стоимости обрезки деревьев описана ниже:

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

Заключение

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

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

Рекомендации

• Введение в статистическое обучение, 2-е издание. Вы можете найти книгу здесь