Обобщения решающих деревьев

Обобщение правил ветвления

Вместо правил $x^i\le h$ (признак меньше порога) во внутренних узлах дерева можно применять и другие правила:

• Например, при использовании категориального признака $x^i$ можно построить столько дочерних вершин, сколько есть уникальных категорий и, в зависимости от категории $x^i$, спускаться в соответствующую вершину. Дерево тогда уже не будет бинарным.

• Можно разбить множество значений признака на набор из $K$ непересекающихся полуинтервалов: $(-\infty,h_1],(h_1,h_2],...(h_{K-2},h_{K-1}],(h_{K-1},+\infty)$ и осуществлять спуск в дочернюю вершину $j$, если признак $x^i$ попадает в $j$-й полуинтервал.

• В каждом внутреннем узле $t$ можно спускаться в левую или правую дочернюю вершину на основе правила

  $$\mathbf{\mathbf{x}}^T \mathbf{w}_t\le w_{t0},$$

  при этом вектора коэффициентов $\mathbf{w}_t$ и пороги $w_{t0}$ у каждого узла будут свои. Тогда каждый внутренний узел сможет дробить признаковое пространство не только перпендикулярно осям, а под произвольным углом на основе линейной классификации.

• В качестве проверяемой функции в узле $t$ можно брать произвольную функцию $f_t(\mathbf{x})$. Например, если взять $f_t(\mathbf{x})=\|\mathbf{x}\|$, то правило $\|\mathbf{x}\|\le h$ будет направлять объекты в левую и правую дочернюю вершину в зависимости от того, попал ли объект внутрь шара определённого радиуса или нет.

Обобщение правил прогнозирования в листьях

Вместо назначения константного прогноза в листьях дерева, в каждом листе $t$ можно строить прогноз по некоторой функции (например, линейной):

$$\hat{y}_t(\mathbf{x})=f_t(\mathbf{x})$$

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

Более оптимальная настройка дерева

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