Árbol de decisión alterno

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

Un 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 ADTree clasifica una instancia siguiendo todas las rutas para las cuales todos los nodos de decisión son verdaderos y sumando los nodos de predicción que se atraviesan.

Historia

Los ADTrees fueron presentados por Yoav Freund y Llew Mason. ^[1] Sin embargo, el algoritmo presentado tenía varios errores tipográficos. Posteriormente Bernhard Pfahringer, Geoffrey Holmes y Richard Kirkby presentaron aclaraciones y optimizaciones. ^[2] Las implementaciones están disponibles en Weka y JBoost.

Motivación

Los algoritmos de impulso originales normalmente utilizaban muñones de decisión o árboles de decisión como hipótesis débiles. Como ejemplo, impulsar los tocones de decisión crea un conjunto de tocones de decisión ponderados (donde está el número de iteraciones de impulso), que luego votan en la clasificación final de acuerdo con sus ponderaciones. Las decisiones individuales se ponderan según su capacidad para clasificar los datos. ${\displaystyle T}$ ${\displaystyle T}$

Impulsar a un alumno simple da como resultado un conjunto de hipótesis no estructuradas, lo que dificulta inferir correlaciones entre atributos. Los árboles de decisión alternos introducen estructura al conjunto de hipótesis al requerir que se basen en una hipótesis que se produjo en una iteración anterior. El conjunto de hipótesis resultante se puede visualizar en un árbol basado en la relación entre una hipótesis y su "padre". ${\displaystyle T}$

Otra característica importante de los algoritmos potenciados es que a los datos se les asigna una distribución diferente en cada iteración. Las instancias que están mal clasificadas reciben una ponderación mayor, mientras que las instancias clasificadas con precisión reciben una ponderación reducida.

Estructura de árbol de decisión alterna

Un árbol de decisión alterno consta de nodos de decisión y nodos de predicción. Los nodos de decisión especifican una condición predicada. Los nodos de predicción contienen un solo número. Los ADTrees siempre tienen nodos de predicción como raíz y hojas. Un ADTree clasifica una instancia siguiendo todas las rutas para las cuales todos los nodos de decisión son verdaderos y sumando los nodos de predicción que se atraviesan. Esto es diferente 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 una ruta a través del árbol.

Ejemplo

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

Un ADTree para 6 iteraciones en el conjunto de datos de Spambase.

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

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

La puntuación 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:

• Los nodos individuales pueden evaluarse por su propia capacidad predictiva.
• Se puede interpretar que conjuntos de nodos en el mismo camino tienen un efecto conjunto.
• El árbol se puede interpretar como un todo.

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

Descripción del algoritmo

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

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

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

1 si (condición previa)2 si (condición)3 puntuación de retorno_uno4 más
5 devuelven puntuación_dos6 finaliza si
7 más
8 regresa 09 terminar 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 como sigue:

1 función ad_tree2 entradas Conjunto de m instancias de entrenamiento34 w i = 1/ m para todo i
5
6 R 0 = una regla con puntuaciones a y 0 , condición previa "verdadera" y condición "verdadera". ${\displaystyle a={\frac {1}{2}}{\textrm {ln}}{\frac {W_{+}(true)}{W_{-}(true)}}}$7
8 el conjunto de todas las condiciones posibles
9 para
10 obtienen valores que minimizan
11
12
13
14 R j = nueva regla con precondición p , condición c y pesos a 1 y a 2
15
16 final para
17 conjunto de retorno de R j ${\displaystyle {\mathcal {P}}=\{true\}}$ ${\displaystyle {\mathcal {C}}=}$  ${\displaystyle j=1\dots T}$ ${\displaystyle p\in {\mathcal {P}},c\in {\mathcal {C}}}$  ${\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)}$ ${\displaystyle {\mathcal {P}}+=p\wedge c+p\wedge \neg c}$ ${\displaystyle a_{1}={\frac {1}{2}}{\textrm {ln}}{\frac {W_{+}(p\wedge c)+1}{W_{-}(p\wedge c)+1}}}$ ${\displaystyle a_{2}={\frac {1}{2}}{\textrm {ln}}{\frac {W_{+}(p\wedge \neg c)+1}{W_{-}(p\wedge \neg c)+1}}}$ ${\displaystyle w_{i}=w_{i}e^{-y_{i}R_{j}(x_{i})}}$

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

Resultados empíricos

La Figura 6 en el artículo original ^[1] demuestra que los ADTrees suelen ser tan robustos como los árboles de decisión impulsados ​​y los tocones de decisión impulsados . Normalmente, se puede lograr una precisión equivalente con una estructura de árbol mucho más simple que los algoritmos de partición recursivos.

Referencias

1. Freund, Y.; Masón, L. (1999). "El algoritmo de aprendizaje del árbol de decisión alterno" (PDF) . Actas de la Decimosexta Conferencia Internacional sobre Aprendizaje Automático (ICML '99). Morgan Kaufman. págs. 124-133. ISBN 978-1-55860-612-8.
2. Pfahringer, Bernhard; Holmes, Geoffrey; Kirkby, Richard (2001). "Optimización de la inducción de árboles de decisión alternos" (PDF) . Avances en descubrimiento de conocimiento y minería de datos. PAKDD 2001 . Apuntes de conferencias sobre informática. vol. 2035. Saltador. págs. 477–487. doi :10.1007/3-540-45357-1_50. ISBN 978-3-540-45357-4.
3. "Conjunto de datos de la base de spam". Repositorio de aprendizaje automático de la UCI . 1999.
4. Dua, D.; Graff, C. (2019). "Repositorio de aprendizaje automático de la UCI". Universidad de California, Irvine, Facultad de Información y Ciencias de la Computación.

enlaces externos

• Una introducción a Boosting y ADTrees (tiene muchos ejemplos gráficos de árboles de decisión alternos en la práctica).
• Software JBoost que implementa ADTrees.