Árbol de decisión alternativo

Un árbol de decisión alternante (ADTree) es un método de aprendizaje automático para la clasificación. Generaliza los árboles de decisión y tiene conexiones con el boosting .

Un árbol ADTree consta de una alternancia de nodos de decisión, que especifican una condición de predicado, y nodos de predicción, que contienen un único número. Un árbol ADTree clasifica una instancia siguiendo todos los caminos en los que todos los nodos de decisión son verdaderos y sumando los nodos de predicción recorridos.

Los árboles ADT fueron introducidos por Yoav Freund y Llew Mason. ^{[ 1 ]} Sin embargo, el algoritmo presentado contenía varios errores tipográficos. Posteriormente, Bernhard Pfahringer, Geoffrey Holmes y Richard Kirkby presentaron aclaraciones y optimizaciones. ^{[ 2 ]} Existen implementaciones disponibles en Weka y JBoost.

Los algoritmos de boosting originales normalmente utilizaban árboles de decisión o árboles de decisión como hipótesis débiles. Por ejemplo, el boosting de árboles de decisión crea un conjunto de${\displaystyle T}$tocones de decisión ponderados (donde${\displaystyle T}$ es el número de iteraciones de boosting), que luego votan sobre la clasificación final de acuerdo con sus pesos. Los nodos de decisión individuales se ponderan según su capacidad para clasificar los datos.

Potenciar un aprendiz simple da como resultado un conjunto no estructurado de${\displaystyle T}$Las hipótesis dificultan la inferencia de correlaciones entre atributos. Los árboles de decisión alternados introducen estructura al conjunto de hipótesis al requerir que se basen en una hipótesis generada en una iteración anterior. El conjunto resultante de hipótesis puede visualizarse en un árbol según la relación entre una hipótesis y su "padre".

Otra característica importante de los algoritmos potenciados es que los datos reciben una distribución diferente en cada iteración. A las instancias mal clasificadas se les asigna un peso mayor, mientras que a las instancias clasificadas correctamente se les asigna un peso menor.

Un árbol de decisión alternante (ADTree) consta de nodos de decisión y nodos de predicción. Los nodos de decisión especifican una condición de predicado. Los nodos de predicción contienen un único número. Los ADTrees siempre tienen nodos de predicción como raíz y hojas. Un ADTree clasifica una instancia siguiendo todos los caminos en los que todos los nodos de decisión son verdaderos y sumando los nodos de predicción recorridos. Esto difiere de los árboles de clasificación binaria como CART ( árbol de clasificación y regresión ) o C4.5 , en los que una instancia sigue solo un camino a través del árbol.

Ejemplo

El siguiente árbol se construyó utilizando JBoost en el conjunto de datos spambase ^{[ 3 ]} (disponible en el repositorio de aprendizaje automático de la UCI). ^{[ 4 ]} En este ejemplo, el spam se codifica como1 y el correo electrónico regular está codificado como−1 .

La siguiente tabla contiene parte de la información correspondiente a una sola instancia.

La instancia se puntúa sumando todos los nodos de predicción por los que pasa. En el caso de la instancia anterior, la puntuación se calcula como

El resultado final de0,657 es positivo, por lo que la instancia se clasifica como spam. La magnitud del valor es una medida de confianza en la predicción. Los autores originales enumeran tres niveles potenciales de interpretación para el conjunto de atributos identificados por un ADTree:

• Cada nodo individual puede evaluarse en función de su propia capacidad predictiva.
• Los conjuntos de nodos en la misma ruta pueden interpretarse como si tuvieran un efecto conjunto.
• El árbol puede interpretarse como un todo.

Se debe tener cuidado al interpretar los nodos individuales, ya que las puntuaciones reflejan una ponderación diferente de los datos en cada iteración.

Las entradas al algoritmo de árbol de decisión alternante son:

• Un conjunto de entradas${\displaystyle (x_{1},y_{1}),\ldots ,(x_{m},y_{m})}$dónde${\displaystyle x_{i}}$es un vector de atributos y${\displaystyle y_{i}}$es -1 o 1. Las entradas también se denominan instancias.
• Un juego de pesas${\displaystyle w_{i}}$correspondiente a cada instancia.

El elemento fundamental del algoritmo ADTree es la regla. Una regla consta de una precondición, una condición y dos puntuaciones. Una condición es un predicado de la forma "atributo <comparación> valor". Una precondición es simplemente una conjunción lógica de condiciones. La evaluación de una regla implica un par de sentencias if anidadas:

1 si (precondición) 2 si (condición) 3 devolver puntuación_uno 4 de lo contrario 5 devuelve puntuación_dos 6 fin si 7 sino 8 devolver 0 9 fin si

El algoritmo también requiere varias funciones auxiliares:

• ${\displaystyle W_{+}(c)}$devuelve la suma de los pesos de todos los ejemplos etiquetados positivamente que satisfacen el predicado${\displaystyle c}$
• ${\displaystyle W_{-}(c)}$devuelve la suma de los pesos de todos los ejemplos etiquetados negativamente que satisfacen el predicado${\displaystyle c}$
• ${\displaystyle W(c)=W_{+}(c)+W_{-}(c)}$devuelve la suma de los pesos de todos los ejemplos que satisfacen el predicado${\displaystyle c}$

El algoritmo es el siguiente:

1 función ad_tree 2 entradas Conjunto de m instancias de entrenamiento 3 4 w i = 1/ m para todo i 5 ${\displaystyle a={\frac {1}{2}}{\textrm {ln}}{\frac {W_{+}(verdadero)}{W_{-}(verdadero)}}}$ 6 R 0 = una regla con puntuaciones a y 0 , precondición "verdadera" y condición "verdadera". 7 ${\displaystyle {\mathcal {P}}=\{true\}}$ 8 ${\displaystyle {\mathcal {C}}=}$el conjunto de todas las condiciones posibles 9 para${\displaystyle j=1\dots T}$ 10 ${\displaystyle p\in {\mathcal {P}},c\in {\mathcal {C}}}$obtener valores que minimicen${\displaystyle z=2\left({\sqrt {W_{+}(p\wedge c)W_{-}(p\wedge c)}}+{\sqrt {W_{+}(p\wedge \neg c)W_{-}(p\wedge \neg c)}}\right)+W(\neg p)}$ 11 ${\displaystyle {\mathcal {P}}+=p\wedge c+p\wedge \neg c}$ 12 ${\displaystyle a_{1}={\frac {1}{2}}{\textrm {ln}}{\frac {W_{+}(p\wedge c)+1}{W_{-}(p\wedge c)+1}}}$ 13 ${\displaystyle a_{2}={\frac {1}{2}}{\textrm {ln}}{\frac {W_{+}(p\wedge \neg c)+1}{W_{-}(p\wedge \neg c)+1}}}$ 14 R j = nueva regla con precondición p , condición c y pesos a 1 y a 2 15 ${\displaystyle w_{i}=w_{i}e^{-y_{i}R_{j}(x_{i})}}$ 16 fin para 17 conjunto de retorno de R j

El conjunto${\displaystyle {\mathcal {P}}}$crece mediante dos precondiciones en cada iteración, y es posible derivar la estructura de árbol de un conjunto de reglas tomando nota de la precondición que se utiliza en cada regla sucesiva.

La figura 6 del artículo original ^{[ 1 ]} demuestra que los árboles ADTrees suelen ser tan robustos como los árboles de decisión potenciados y los árboles de decisión simples potenciados . Por lo general, se puede lograr una precisión equivalente con una estructura de árbol mucho más simple que los algoritmos de partición recursiva.

• Introducción a Boosting y ADTrees (incluye numerosos ejemplos gráficos de árboles de decisión alternados en la práctica).
• Software JBoost que implementa árboles AD.