Представлена в редакцию

1. Алгоритм «Случайный лес» 
Перед тем как давать описание работы алгоритма «Случайный лес» [13, 14], введем 
определение бинарного решающего дерева [15, 16] для классификации бинарных объек-
тов. 
Бинарное решающее дерево – это бинарное дерево, в котором: 
˗ каждой внутренней вершине приписана функция: 
, 
(1) 
где
– множество возможных значений признаков классов ( – число классов); 
˗ каждой листовой вершине приписана метка класса
где – воз-
можные классы. 
Рассмотрим теперь алгоритм , который определяет класс объекта , используя 
бинарное решающее дерево. Начиная с корневой вершины
рекурсивно выполняются 
следующие действия: 
1. Проверяется, является данная вершина листовой. Если вершина является листо-
вой, то возвращается метка класса, соответствующая данной листовой вершине, и 
алгоритм завершает работу. 

---

Машиностроение и компьютерные технологии
 
26 
2. Если вершина не является листовой, то вычисляется значение функции
. Если 
значение функции равно 0, то вычисляется
, если равно 1, то вычисляется 
. Под
и
понимается соответственно левая и правая вершина относи-
тельно текущей вершины
Под функциями
понимаются как правило одномерные предикаты, которые срав-
нивают значение одного из признаков с порогом: 
, 
(2) 
где – набор признаков одного объекта, 
– признак, который был выбран для данной вершины. 
– значение -го признака объекта, 
– значение порога. 
Определение того какой признак и какой порог использовать для определенной вер-
шины происходит на этапе построения. Построение бинарного решающего дерева проис-
ходит следующим образом. 
Пусть существует обучающая выборка: 
, 
(3) 
где
– набор признаков одного объекта. 
Каждая вершина разбивает выборку на две части
и
, при этом и определяются таким образом, чтобы выбранный средний ин-
декс неоднородности образованных выборок был минимален. Разбиение каждой вершины 
должно производится до достижения условия останова (например, в выборке присутству-
ет только один класс объектов), после чего полученная вершина объявляется листом. 
Индекс неоднородности вычисляется для произвольной выборки , содержащей 
объекты из классов . В данной работе в качестве индекса неоднородности использу-
ется индекс Джини [17], вычисляемый для бинарных объектов по следующей формуле: 
(4) 
где
– доля объектов класса 0 в выборке , 
– доля объектов класса 1 в выборке
«Случайный лес» - это множество решающих деревьев. В задаче классификации ре-
шение принимается голосованием по большинству среди выданных ответов. Все деревья 
строятся независимо по следующей схеме: 
˗ Выбирается подвыборка обучающей выборки размера с повторениями – по ней 
строится дерево (для каждого дерева своя подвыборка). 
˗ Для построения каждого расщепления в дереве просматриваются (квадратный ко-
рень из общего количества признаков ) случайных признаков (для каждого нового 
расщепления свои случайные признаки). 
˗ Выбираются наилучшие признак и расщепление по нему. Дерево строится до исчерпа-
ния выборки (пока в листьях не останутся представители только одного класса), если 

---

Машиностроение и компьютерные технологии
 
27 
не заданы ограничения (высота дерева, число объектов в листьях и число объектов в 
подвыборке, при котором проводится расщепление).