Algoritmo general de particionamiento recursivo

• Ultima modificación: 2023-03-11 | YouTube

• Considere el siguiente ejemplo:

• Este puede ser representado como una tabla de datos:

   x1  x2  clase
  ---------------
    1   1   rojo
    1   2   rojo
    1   3   rojo
    1   4   rojo
    2   1   rojo
    2   2   azul
    2   3   azul
    2   4   rojo
    3   1   gris
    3   2   azul
    3   3   azul
    3   4   rojo
    4   1   gris
    4   2   gris
    4   3   gris
    4   4   azul
  

• En el ejemplo, se tienen únicamente dos atributos x_1 y x_2, y un total de N ejemplos para construir el árbol.

• Para construir la primera instancia, se construyen todos los árboles posibles de profunidad 1 (un nodo). El primer árbol se construye usando como frontera de decisión el primer valor de x_1 en la muestra del ejemplo (véase la figura de abajo); el segundo árbol se construye con el segundo valor, y así sucesivamente. Una vez se recorren todos los valores de x_1, se recorren todos los valores de x_2 y así sucesivamente hasta agotar todas las variables explicativas (atributos).

• La mejor partición se escoje como aquella que clasifica el mayor número de ejemplos correctamente (o una métrica equivente) y se obtiene un primer árbol. Esto equivale a encontra la mejor partición de todo el espacio de características en dos regiones que clasifiquen de mejor forma los ejemplos usandos para el entrenamiento del modelo (véase la parte derecha de la figura anterior). En la figura anterior, se supone que la mejor clasificación se obtiene usando como punto de corte el dato x1[4].

• El algoritmo continua obteniendo una tercera región y para ello se debe decidir cuál de las dos regiones existentes se parte y en que orientación va dicho corte. El algoritmo prueba nuevamente cada punto del conjunto de datos como punto de corte de la siguiente manera: se hace x1[1] el nuevo punto de corte; si x1[1] está a la izquierda de x1[4], se esta partiendo dicha región y por lo tanto se agrega esta nueva partición en la parte correspondiente de la regla (primera partición de la figura de abajo). Se hace x1[2] el nuevo punto de corte; si se asume que x1[2] esta a la derecha de x1[4] entonces se agrega a la parte else del modelo óptimo; se procede así sucesivamente hasta hasta obtener todos los modelos posibles con dos cortes. Asumiendo que el mejor corte se obtiene para x2[6], el árbol queda como se presenta en el conjunto de reglas de la parte derecha de la siguiente figura.

• El proceso continua agregando un tercer corte, luego un cuarto y así sucesivamente. De ahí que el proceso se conozca como particionamiento recursivo.

• Nótese que el proceso puede realizarse hasta que se asigne una región única a cada uno de los datos, lo que resulta erróneo ya que el modelo simplemente memoriza la información usada para el entrenamiento (explique que es esto!). El proceso de crecimiento del árbol de decisión puede deternerse asignando un máximo a la profundidad del árbol (early stoping) o limitando la cantidad mínima de puntos que puede contener una región (pre-pruning).