Дерево принятия решений

5.2 Отсечение ребер

 

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

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

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

 

Рисунок 6 - Отсечение ребра после подсчета количества

успешно классифицированных примеров в каждом узле

5.3 Конгломерация и усиление

 

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

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

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

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

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

Заключение

 

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

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

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список литературы

 

1 http://www.williamspublishing.com/PDF/978-5-8459-1170-4/part.pdf

2 http://logic.pdmi.ras.ru/~sergey/teaching/ml/notes-01-dectrees.pdf

3 http://www.algorithmist.ru/2012/05/decision-trees-in-r.html