Главная       Скачать       Коммерческая поддержка       FAQ       Forum       О нас       Английская версия

Лес деревьев решений

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

Содержание

    1 Алгоритм RDF (random decision forest)
    2 Обсуждение алгоритма
    3 Работа с лесом деревьев решений
    4 Настройка алгоритма RDF
    5 Формат обучающего множества
    6 Кодирование номинальных переменных в обучающем множестве
    7 Manual entries

Алгоритм RDF (random decision forest)

Алгоритм RDF является модификацией оригинального алгоритма Random Forest, разработанного Лео Брейманом (Leo Breiman) и Адель Катлер (Adele Cutler). Этот алгоритм сочетает в себе две идеи: использование комитета деревьев решений, получающего результат путем голосования, и идею рандомизации процесса обучения. Ниже приведено краткое описание алгоритма:

  1. Пусть обучающее множество имеет размер N, а число независимых переменных равно M. Введем дополнительно три параметра: коэффициент r (0 ≤ r ≤ 1), число признаков m ≤ M, число деревьев NTrees ≥ 1.
  2. На основе исходного обучающего множества сгенерируем случайную выборку размером r·N (без повторений). Элементы, не попавшие в выборку, используем в дальнейшем для оценки ошибки обобщения.
  3. На основе сгенерированной выборки построим дерево решений. В ходе построения очередного узла дерева из M имеющихся переменных, на основе которых можно разделить дерево, выберем m случайных. Решение о разбиении принимается на основе лучшего возможного выбора из m случайно выбранных переменных. Дерево строится до исчерпания обучающено множества и не подвергается прунингу.
  4. Процедура повторяется NTrees раз. Полученные деревья объединяются в комитет, принимающий решение путем голосования.

Обсуждение алгоритма

Достоинствами алгоритма являются:

Вместе с тем, можно отметить и недостатки алгоритма:

Работа с лесом деревьев решений

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

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

Настройка алгоритма RDF

Алгоритм содержит три основных параметра, нуждающихся в настройке: коэффициент r, говорящий нам, какую часть обучающего множества мы будем использовать для построения индивидуальных деревьев; число деревьев NTrees; а также число NFeatures - количество переменных, используемых при построении индивидуальных деревьев. Ниже эти параметры рассмотрены более подробно.

Коэффициент r, находящийся в диапазоне от 0 до 1, влияет на терпимость алгоритма к шуму в обучающем множестве. Слабым местом оригинального алгоритма Бреймана является то, что он не в полной мере компенсирует склонность индивидуальных деревьев к переобучению. Вспомним, что нерегуляризированное дерево решений в точности запоминает обучающее множество. Использованная в оригинальном алгоритме процедура выбора N элементов с повторениями приводит к тому, что в обучающую выборку попадает примерно 0.632 элементов полного обучающего множества (что соответствует значению r=0.632) - а значит примерно 63% индивидуальных деревьев в точности запомнят любой произвольно выбранный элемент обучающего множества и получат большинство в ходе процедуры голосования. Таким образом, при наличии шума в обучающем множестве алгоритм Бреймана с высокой долей точности повторит все ошибки обучающего множества, не сумев восстановить подавленную шумом закономерность. Эта проблема имеет различные решения: можно регуляризировать индивидуальные деревья (как предложено в статье по ссылке выше) или сглаживать шум, управляя вариативностью индивидуальных деревьев при помощи коэффициента r (как реализовано в ALGLIB). Рекомендуемые значения r - от 0.66 (низкий уровень шума) до 0.05 (очень высокий уровень шума). Выбор осуществляется на основе отношения между ошибкой на обучающем множестве и ошибкой обобщения (рассчитанной при помощи тестового множества или out-of-bag оценки) - если отношение значительно меньше единицы, уменьшайте r и повторно постройте модель.

Прочие параметры алгоритма значительно проще в настройке. Количество деревьев NTrees рекомендуется делать на уровне 50-100, а число NFeatures выбирается автоматически и устанавливается на уровне половины от общего числа переменных.

Формат обучающего множества

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

Кодирование номинальных переменных в обучающем множестве

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

Manual entries

C++ dforest subpackage   
C# dforest subpackage   

This article is intended for personal use only.

Скачать ALGLIB

C#

Исходный код на C#

Downloads page

 

C++

Исходный код на C++

Downloads page

 

C++, арифметика высокой точности

Исходный код на C++, использующий библиотеки MPFR/GMP.

Исходный код GMP доступен на сайте gmplib.org. Исходный код MPFR доступен на сайте www.mpfr.org.

Downloads page

 

FreePascal

Исходный код на Free Pascal.

Downloads page

 

Delphi

Исходный код на Delphi.

Downloads page

 

VB.NET

Исходный код на VB.NET.

Downloads page

 

VBA

Исходный код на VBA.

Downloads page

 

Python

Исходный код на Python (CPython и IronPython).

Downloads page

 

 

ALGLIB® - numerical analysis library, 1999-2017.
ALGLIB is registered trademark of the ALGLIB Project.