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

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

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

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

• Можно разбить множество значений признака на набор из $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$.

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

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

Мягкие решающие деревья

В стандартном решающем дереве спуск каждого объекта производится только по одному пути. В мягких решающих деревьях (soft decision trees [5]) объект спускается одновременно по всем путям сразу с вероятностями, рассчитываемыму логистической регрессией в каждом узле.

Литература

1. Wikipedia: двоичное дерево.

2. Wikipedia: ID3 algorithm.

3. Wikipedia: C4.5 algorithm.

4. Esmeir S., Markovitch S. Lookahead-based algorithms for anytime induction of decision trees //Proceedings of the 21 international conference on Machine learning. – 2004. – С. 33.

5. Irsoy O., Yıldız O. T., Alpaydın E. Soft decision trees //Proceedings of the 21st international conference on pattern recognition (ICPR2012). – IEEE, 2012. – С. 1819-1822.