🟦Решающие деревья

Критерий информативности

\(H(R)\)- impurity (хаотичность).

Показывает разнородность объектов в R.

\[ Q(R_m, j, t) = H(R_m) - \frac{|R_l|}{|R_m|} H(R_l) - \frac{|R_r|}{|R_m|} H(R_r) \to \max \]

Для простоты можно написать следующим образом:

\[ \frac{|R_l|}{|R_m|} H(R_l) - \frac{|R_r|}{|R_m|} H(R_r) \to \min \]

где \(R_m\) - объекты из выборки, попавшие в текущую вершину. \(Q\) - критерий информативности, хотим, чтобы хаотичность в дочерних вершинах значительно уменьшилась.

В задачах классификации используют следующие критерии:

• энтропийный: \(H(X_m) = - \sum_{k=1}^{K} p_k \log{p_k}\)

• Джини: \( \sum_{k=1}^{K} p_k (1-p_k) = 1-\sum_{k=1}^{K}p_k^2\)

В регрессии, например вот такой: \(H(X_m) = \frac{1}{|X_m|} \sum_{i}(y_i - y_{ср})\)

Если деревья переобучаются, то можно использовать prunning (стрижку).

Связь деревьев и линейных моделей

Пусть \(w_1, w_2, ..., w_n\) - прогнозы листов, \(J_1, J_2, ..., J_n\) - листы, тогда можно написать следующим образом:

\(a(x) = \sum_{j=1}^{n} w_j [x\in J_j]\)