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

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

 

 

 

2.4 Листовые узлы и переменные отклика

 

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

 

Рисунок 3 - Соответствие между значениями, хранящимися

в каждом листовом узле, и  переменными отклика

 

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

3 Классификация и регрессия

 

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

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

 

Рисунок 4 - Использование выборки данных для управления

переходом по дереву решений

 

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

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

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

 

4 Формирование дерева

 

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

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

 

4.1 Описание алгоритма рекурсивного секционирования

 

Алгоритм, впервые предложенный Куинланом, действует по принципу рекурсивного секционирования набора данных и инкрементного построения дерева. В основе алгоритма рекурсивного секционирования лежит принцип ‘‘разделяй и властвуй’’. Алгоритм применяется с целью формирования дерева, позволяющего распределять по категориям выборки данных; набор данных разбивается на грубо классифицированные подмножества, после чего предпринимается еще одна попытка, до тех пор пока классификация не станет идеальной (или, по крайней мере, достаточно качественной). Этот процесс является рекурсивным, и в ходе его осуществления формируется дерево решений.

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

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

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

 

4.2 Разбиение наборов данных

 

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

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

Рисунок 5 - Рекурсивное секционирование по одному узлу, приводящее

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

 

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

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

 

 

Энтропия определяется как  сумма взвешенных логарифмических значений для каждого класса i, а pi обозначает долю выборок, относящихся к классу i (иными словами, количество выборок |Si| в общем количестве выборок в наборе данных |S|).

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

 

 

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

 

5 Процедура обучения

 

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

 

5.1 Управление набором данных

 

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

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

1) Обучающее множество, которое используется в алгоритме рекурсивного секционирования.

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

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

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