3. От дерева решений к лесу
решений.
Лесом решений называют набор
из нескольких деревьев решений. Эти деревья могут быть получены различными методами
(или одним методом, но с различными параметрами работы), по разным выборкам
наблюдений за одним и тем же явлением, путем привлечения различных
характеристик. Такое «многостороннее» рассмотрение задачи, как правило,
приводит к улучшению качества прогнозирования и к лучшему пониманию
закономерностей исследуемого явления.
Пусть имеется набор деревьев
и произвольное наблюдение x. Каждое дерево дает свой прогноз для х.
Как найти общее («коллективное») решение для прогнозируемой величины Y ?
Наиболее простым способом получения «коллективного» прогноза, которое дает данный лес решений, является метод «голосования» (задача РО) или метод «усреднения» (задача РА).
При использовании метода
«голосования» наблюдению x приписывается тот класс, которому отдает предпочтение
большинство деревьев из набора. В случае задачи регрессионного анализа
прогнозируемое значение получается усреднением прогнозов по всем деревьям.
Рассмотрим, например, набор деревьев регрессии, изображенный на рис. 18. Пусть
имеется наблюдение x=(3,4,8). Тогда коллективное решение будет равно
Y(x)=1/3(10.2+6.3+11.2)=9.233.
Рис.18
Кроме простого усреднения или голосования с равными вкладами каждого «голосующего», можно использовать процедуру, в которой учитывается число ошибок, совершенных каждым деревом на обучающей выборке: чем меньше ошибок, тем больший вес имеет соответствующий голос.
Для оценивания качества
построенного леса решений можно использовать способы аналогичные тем, которые
использовались для единичного дерева. При этом может использоваться как
контрольная выборка, так и скользящий экзамен или перекрестная проверка.
Рассмотрим подробнее
некоторые способы формирования леса решений.
3.1 Последовательное исключение характеристик.
Данный метод состоит из
нескольких этапов, на каждом из которых
стоится свое дерево по полному набору наблюдений, но с привлечением разного набора
характеристик. На первом этапе используются все имеющиеся характеристики.
Характеристика, которая соответствует корню построенного дерева, является
наиболее информативной, поскольку, во-первых, именно от нее зависит дальнейшее
движение по дереву, а, во-вторых, при ветвлении корневой вершины используется
полный набор наблюдений. На следующем этапе, при построении второго дерева,
используются все характеристики, кроме вышеупомянутой. Это делается с целью
получить вариант дерева, наиболее радикально отличающийся от предыдущего, т.е.
обнаружить новый набор закономерностей. На следующих этапах последовательно
исключаются характеристики, соответствующие корневым вершинам уже построенных
деревьев. Поскольку исключаются наиболее информативные характеристики, качество
деревьев, как правило, может лишь ухудшаться от этапа к этапу.
Алгоритм прекращает работу,
как только будет построено заданное число деревьев, либо показатель качества
достигнет заданной минимально допустимой величины.
3.2 Использование различных подвыборок.
Основная идея данного метода состоит в том, чтобы использовать различные части исходной обучающей выборки для формирования деревьев (для построения каждого дерева используется весь набор характеристик). При этом качество итогового («коллективного») решения, как правило, улучшается. Это можно объяснить тем, что прогнозы, даваемые случайными (неустойчивыми) закономерностями на различных подвыборках, в итоговом прогнозе не имеют «решающего голоса». В то же время действительно устойчивые закономерности на различных подвыборках только «подтверждаются».
Рассмотрим три основные
метода получения подвыборок: метод случайных подвыборок, перекрестный и
адаптивный метод.
Первый метод (случайных подвыборок) состоит в том, что для построения очередного дерева формируется подвыборка путем случайного независимого отбора объектов исходной выборки. Вероятность отбора для каждого объекта одинакова. Объем подвыборки задается заранее (например, 70% от исходной). После построения дерева на основе анализа данной подвыборки, отобранные наблюдения возвращаются в исходную выборку, и процесс повторяется заданное число раз. При этом каждый объект может неоднократно попадать в анализируемую подвыборку. В зарубежной литературе данный метод называется «bagging» («bootstrap aggregation»).
Метод случайных подвыборок
характеризуется также тем, что некоторые объекты исходной выборки могут быть ни
разу не включены в анализируемые подвыборки. Чтобы добиться гарантированного
включения, можно использовать перекрестный метод, который использует тот
же принцип, что и метод перекрестной проверки, описанный выше (параграф 2.8).
Выборка случайным образом делится на L приблизительно одинаковых по
объему частей, затем каждая часть поочередно "выбрасывается", а
оставшиеся части объединяются в подвыборку, по которой и строится очередное
дерево решений.
Адаптивный метод (в зарубежной литературе
называемый «boosting») основан на следующей идее. Вначале, по всей исходной
выборке строится первое дерево решений. Как правило, для части объектов
прогноз, даваемый деревом, будет отличаться от наблюдаемых значений. При
построении второго дерева, больше внимания уделяется тем объектам, у которых
больше ошибка, с целью ее уменьшить. Построенное дерево также будет давать
погрешности для некоторых объектов, и третье дерево должно строится так, чтобы
уменьшить эти ошибки. Данная процедура повторяется заданное число раз, или до
тех пор, пока погрешность станет меньше приемлемой величины.
Учет погрешностей может быть
проведен следующим способом. Каждому объекту исходной выборки приписывается
некоторая вероятность его отбора в подвыборку. При построении первого дерева,
как и в процедуре случайных подвыборок, значение этой вероятности одно и то же
для всех объектов. На следующих этапах, вероятность отбора каждого объекта
изменяется. В задаче РО, неправильно классифицированные объекты получают
приращение вероятности на заданную величину. В задаче РА, приращение
вероятности прямо пропорционально абсолютной величине квадрата погрешности.
Таким образом, для построения очередного дерева формируется подвыборка
заданного объема путем случайного отбора объектов в соответствии с текущим
распределением вероятностей.
Как показывают исследования,
из трех описанных методов последний метод чаще позволяет в наибольшей степени уменьшить
ошибку коллективного прогноза.