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

дерево принятия решений — дерево решений

Предисловие переводчика: если Вам хочется попробовать немного Machine Learning и не хочется выходить за пределы родного dotnet - Вы можете воспользоваться фреймворком Accord Net. Статья за авторством César Souza создателя вышеупомянутого фреймворка поможет сделать первые шаги в этом направлении и в качестве примера решить небольшую задачку при помощи алгоритма деревьев принятия решений.

Ещё хотел бы добавить замечательный перевод Андрея Будая проясняющий работу алгоритмов ID3 и C4.5 и математику стоящую за ними

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

Скачать образец приложения и исходный код
Скачать полную версию Accord.NET Framework

Введение

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

Дерево в заголовке было создано с использованием программного обеспечения Context Free на основе грамматики от davdrn.

Обучение деревьев принятия решений

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

Наиболее примечательными и классическими примерами для обучения дерева решений являются алгоритмы ID3 (Quinlan, 1986) и C4.5 (Quinlan, 1993).

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

Однако прирост информации оказывает приоритет по отношению к атрибутам с большим количеством возможных значений (Mitchell, 1997). Способ преодоления этого отклонения заключается в выборе новых атрибутов выбора на основе альтернативного критерия, такого как коэффициент прироста (Quinlan, 1986), который определяется как:

В нормированном приросте информации (GainRatio) термин разбиение информации (SplitInformation) ослабляет важность атрибутов со многими, равномерно распределенными, возможными значениями.

Итерационный дихотомизатор 3 (ID3)

Алгоритм, представленный ниже, представляет собой немного изменённую версию исходного алгоритма ID3, представленную Quinlan. Изменения были сделаны для поддержки нескольких выходных меток. В каждой рекурсии алгоритма атрибут, который наилучшим образом классифицирует набор примеров (пары входных\выводных переметров или данные) в соответствии с некоторыми критериями выбора, такими как InfoGain или GainRatio .

ID3(список примеров, 
    целевой_атрибут, 
    атрибуты)
    
  Создайте новый корневой узел для дерева.
  Если все примеры имеют целевой_атрибут, принадлежащий к одному классу C ,
    
    Возвращаем дерево с единственным корневым узлом с меткой C .
    
  Если аттрибутов нет, то
    Возвращаем дерево с единственным корневым узлом с наиболее распространенной меткой целевого_атрибута в примерах.
  Иначе
    Находим атрибут A, который наилучшим образом классифицирует примеры 
    // A ← max(GainRatio(целевой_атрибут, аттрибут)) 
    В корень решения записываем атрибут A
    Для каждого возможного значения значение v[i] атрибута A,
      Добавьте новое ветвление под корнем, соответствующее проверке A = v[i]
      Пусть примеры v[i] являются подмножеством списка примеров со значением v[i] для A
      Если примеры v[i] пусты, тогда
        Ниже этого ветвления добавьте новый листовой узел C наиболее распространенным значением целевого_атрибута в примерах .
      Иначе ниже этого разветвления добавьте поддерево, заданное рекурсией:
        ID3 (примеры v[i], целевой_атрибут, атрибуты не включающие аттрибут A)
    Конец
  Возвращаем корень

Проблемы и недостатки обучения дерева решений

Несмотря на то, что деревья решений полагаются на Бритву Оккама, во время управления обучением, ни алгоритм ID3, ни C4.5 не гарантируют получение меньшего или более общего дерева. Это происходит потому, что их обучение основано исключительно на эвристике, а не на критериях действительной оптимальности. Следующий пример из ( Esmeir & Markovitch, 2007 ) иллюстрирует изучение концепции XOR (исключительное или) алгоритмом ID3. В этом примере A3 и A4 являются несущественными атрибутами, абсолютно не влияющими на целевой ответ. Однако, несмотря на отсутствие значения, ID3 выберет один из них, и добавит в результирующее дерево. Фактически, ID3 выберет несущественный атрибут A4 как корень полученного дерева.

{align=“right”}

A1	A2	A3	A4	метка
1	0	0	1	+
0	1	0	0	+
0	0	0	0	-
1	1	0	0	-
0	1	1	1	+
0	0	1	1	-
1	0	1	1	+

Одним из осложнений обучения в дереве решений является то, что проблема поиска меньшего согласованного дерева (в смысле правильной классификации всех учебных образцов), как известно, является NP-полной (Hyafil & Rivest, 1976). Более того, разделительная поверхность решения, генерируемая такими деревьями, всегда формируется параллельными разрезами вдоль оси пространства атрибутов, что может быть строго субоптимальным решением (Bishop, 2007, стр. 666). Пример, данный Бишопом, хорошо иллюстрирует эту проблему: например, для разделения классов, оптимальный запас решения которых на 45 градусов от одной из осей, потребуется большое количество параллельных разрезов по сравнению с одним разрезом по диагонали, например как это может быть дано любой линейной машиной решения. Другим недостатком традиционных алгоритмов обучения дерева решений является то, что большинство методов требуют только постоянного времени обучения и, как таковые, не позволяют пользоваться дополнительным временем обучения для поиска лучших решений. Работа ( Esmeir & Markovitch, 2007 ) посвящена решению этой проблемы.

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

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

Однако, несмотря на все эти недостатки, деревья решений играют важную роль как основу многих успешных алгоритмов. Одно интересное успешное применение происходит в области обнаружения объектов на изображениях. Первый алгоритм обнаружения лиц в реальном времени (Viola & Jones, 2001) основан на вырожденном дереве решений (также известном как каскад). Алгоритм распознавания тела и сегментации, используемый игровой платформой Xbox 360, используемой для обработки изображений глубины, созданных его спутником-датчиком Kinect, в равной степени основан на использовании деревьев решений ( Shotton, et al., 2011 ). Также имеет место алгоритм FAST для обнаружения точек интереса в изображениях (Rosten & Drummond, 2006).

Я хочу отметить, что алгоритмы Viola-Jones и FAST доступны в Accord.NET Framework (Viola-Jones - HaarObjectDetector также было недавно обновление для поддержки нескольких потоков, поэтому не стесняйтесь экспериментировать с ним!).

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

Исходный код

Код, представленный в этом разделе, фактически является частью платформы Accord.NET . Accord.NET Framework является расширенным фреймворком на базе уже очень популярного платформы AForge.NET , в котором добавлены и предоставлены новые алгоритмы и методы для машинного обучения, компьютерного зрения и ещё многое.

Простарнство имён Accord.MachineLearning.DecisionTree состоит из следующих классов:

DecisionTree , основной класс, представляющий дерево решений, с такими методами, как Compute для вычисления классификации дерева с учетом входного вектора;
DecisionNode , класс узла для дерева решений, который может содержать или не иметь дочерние узлы, содержащиеся под коллекцией дочерних элементов, представленной элементом DecisionBranchNodeCollection ;
DecisionVariable , класс, определяющий характер каждой переменной, обрабатываемой деревом, например, если переменная непрерывна, дискретна, которая является их ожидаемым или допустимым диапазоном;
DecisionBranchNodeCollection , класс, содержащий дочерние узлы вместе с информацией о том, какой атрибут данных следует сравнивать с дочерними узлами во время рассуждений.

Отношения классов можно увидеть на следующей диаграмме:

Доступными алгоритмами обучения являются либо алгоритм ID3, рассмотренный выше, либо его улучшенная версия C4.5 (которая может обрабатывать непрерывные переменные, но в настоящее время еще не поддерживает обрезку), оба алгоритма предложены и выполнены Россом Куинланом(Ross Quinlan).

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

Использование кода

Рассмотрим, например, знаменитый пример “Play Tennis” от Tom Mitchell (1998):

DataTable data = new DataTable("Mitchell's Tennis Example");

data.Columns.Add("Day", "Outlook", "Temperature", "Humidity", "Wind", "PlayTennis");

data.Rows.Add("D1",  "Sunny",    "Hot",  "High",   "Weak",   "No" );
data.Rows.Add("D2",  "Sunny",    "Hot",  "High",   "Strong", "No" ); 
data.Rows.Add("D3",  "Overcast", "Hot",  "High",   "Weak",   "Yes");
data.Rows.Add("D4",  "Rain",     "Mild", "High",   "Weak",   "Yes"); 
data.Rows.Add("D5",  "Rain",     "Cool", "Normal", "Weak",   "Yes"); 
data.Rows.Add("D6",  "Rain",     "Cool", "Normal", "Strong", "No" ); 
data.Rows.Add("D7",  "Overcast", "Cool", "Normal", "Strong", "Yes");
data.Rows.Add("D8",  "Sunny",    "Mild", "High",   "Weak",   "No" );  
data.Rows.Add("D9",  "Sunny",    "Cool", "Normal", "Weak",   "Yes"); 
data.Rows.Add("D10", "Rain",     "Mild", "Normal", "Weak",   "Yes"); 
data.Rows.Add("D11", "Sunny",    "Mild", "Normal", "Strong", "Yes");
data.Rows.Add("D12", "Overcast", "Mild", "High",   "Strong", "Yes"); 
data.Rows.Add("D13", "Overcast", "Hot",  "Normal", "Weak",   "Yes"); 
data.Rows.Add("D14", "Rain",     "Mild", "High",   "Strong", "No" );

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

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

Кодовая книга эффективно трансформирует любое различное возможное значение переменной в целочисленный символ. Например, «Sunny» также может быть представлено целым ярлыком 0, «Overcast» на «1», «Дождем» на «2», а также для других переменных. Так:

// Create a new codification codebook to

// convert strings into integer symbols

Codification codebook = new Codification(data);

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

DecisionVariable[] attributes =
{
  new DecisionVariable("Outlook",     3), // 3 possible values (Sunny, overcast, rain)

  new DecisionVariable("Temperature", 3), // 3 possible values (Hot, mild, cool)  

  new DecisionVariable("Humidity",    2), // 2 possible values (High, normal)    

  new DecisionVariable("Wind",        2)  // 2 possible values (Weak, strong) 
};

int classCount = 2; // 2 possible output values for playing tennis: yes or no

Давайте продолжим и создадим наш DecisionTree:

DecisionTree tree = new DecisionTree(attributes, classCount);

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

// Create a new instance of the ID3 algorithm

ID3Learning id3learning = new ID3Learning(tree);


// Translate our training data into integer symbols using our codebook:

DataTable symbols = codebook.Apply(data); 

int[][] inputs = symbols.ToIntArray("Outlook", "Temperature", "Humidity", "Wind"); 

int[] outputs = symbols.ToIntArray("PlayTennis").GetColumn(0);


// Learn the training instances!

id3learning.Run(inputs, outputs);

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

int[] query = codebook.Translate("Sunny", "Hot", "High", "Strong");
  
int output = tree.Compute(query);
  
string answer = codebook.Translate("PlayTennis", output); 
// answer will be "No".

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

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

Однако, это больше, чем просто диаграмма, мы можем также генерировать .NET Expression Tree, описывающее наше дерево решений. Деревья выражений представляют собой код в виде дерева выражений, который затем может быть прочитан, изменен или скомпилирован . Компилируя выражение DecisionTree, мы можем генерировать код «на лету» и позволить JIT компилировать его на нитивный код во время выполнения, что значительно улучшает производительность нашего дерева решений:

// Convert to an expression tree
var expression = tree.ToExpression();

// Compiles the expression to IL
var func = expression.Compile();

И вот получившийся код C#, полученный путем компиляции выражения в лямбда-функцию, сбрасывая функцию в динамическую сборку, открывая и проверяя эту сборку с помощью ILSpy:

public static int Compute(double[] input)
{
  if (input[0] == 0.0)
  {
    if (input[2] == 0.0)
    {
      return 0;
    }
    if (input[2] == 1.0)
    {
      return 1; 
    } 
    throw new ArgumentException(
      "Input contains a value outside of expected ranges.", "input");  
  }
  else
  {
    if (input[0] == 1.0) 
    {    return 1; 
    } 
    if (input[0] != 2.0) 
    { 
      throw new ArgumentException(
        "Input contains a value outside of expected ranges.", "input");
    }
    if (input[3] == 0.0)
    {  
      return 1;   
    } 
    if (input[3] == 1.0) 
    {
      return 0; 
    }
    throw new ArgumentException(
      "Input contains a value outside of expected ranges.", "input");
  }
}

Вывод

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

Ссылки

Bishop, C. M., 2007. Pattern Recognition and Machine Learning (Information Science and Statistics). 1st ed. 2006. Corr. 2nd printing ed. s.l.:Springer
Fayyad, U. M. & Irani, K. B., 1992. On the Handling of Continuous-Valued Attributes in Decision Tree Generation. Machine Learning, January, 8(1), pp. 87-102.
Quinlan, J. R., 1986. Induction of decision trees. Machine Learning, 1(1), pp. 81-106.
Quinlan, J. R., 1993. C4.5: Programs for Machine Learning (Morgan Kaufmann Series in Machine Learning). 1 ed. s.l.:Morgan Kaufmann.
Shotton, J. et al., 2011. Real-Time Human Pose Recognition in Parts from Single Depth img. s.l., s.n.
Viola, P. & Jones, M., 2001. Robust Real-time Object Detection. s.l., s.n.
Mitchell, T. M., 1997. Decision Tree Learning. In:: Machine Learning (McGraw-Hill Series in Computer Science). s.l.:McGraw Hill.
Mitchell, T. M., 1997. Machine Learning (McGraw-Hill Series in Computer Science). Boston(MA): WCB/McGraw-Hill.
Esmeir, S. & Markovitch, S., 2007. Anytime Learning of Decision Trees. J. Mach. Learn. Res., May, Volume 8, pp. 891-933.
Hyafil, L. & Rivest, R. L., 1976. Constructing Optimal Binary Decision Trees is NP-complete. Information Processing Letters, 5(1), pp. 15-17.

Деревья принятия решений на C#

TOC