Un árbol de decisión alternativo (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 consiste en una alternancia de nodos de decisión, que especifican una condición de predicado, y nodos de predicción, que contienen un solo número. Un ADTree clasifica una instancia siguiendo todas las rutas para las que todos los nodos de decisión son verdaderos y sumando los nodos de predicción que se atraviesan.
Historia
ADTrees fueron presentados por Yoav Freund y Llew Mason. [1] Sin embargo, el algoritmo presentado tenía varios errores tipográficos. Más tarde, 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 generalmente usaban tocones 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 es el número de iteraciones de impulso), que luego votan sobre la clasificación final de acuerdo con sus pesos. Los tocones de decisión individuales se ponderan de acuerdo con su capacidad para clasificar los datos.
Impulsar a un alumno simple da como resultado un conjunto desestructurado de hipótesis, lo que dificulta inferir correlaciones entre atributos. Los árboles de decisión alternos introducen estructura al conjunto de hipótesis al requerir que se construyan a partir de 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".
Otra característica importante de los algoritmos potenciados es que los datos reciben una distribución diferente en cada iteración. Las instancias que están mal clasificadas reciben un peso mayor, mientras que las instancias clasificadas con precisión reciben un peso reducido.
Estructura de árbol de decisión alternante
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 de predicado. Los nodos de predicción contienen un solo número. ADTrees siempre tienen nodos de predicción como raíz y hojas. Un ADTree clasifica una instancia siguiendo todas las rutas para las que 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 el que una instancia sigue solo un camino a través del árbol.
Ejemplo
El siguiente árbol fue construido usando JBoost en el conjunto de datos de spambase [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 se codifica como−1 .
![An ADTree for 6 iterations on the Spambase dataset.](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/7/7d/Spambase_adtree_example.png/800px-Spambase_adtree_example.png)
La siguiente tabla contiene parte de la información para una sola instancia.
Característica | Valor |
---|---|
char_freq_bang | 0,08 |
word_freq_hp | 0.4 |
capital_run_length_longest | 4 |
char_freq_dollar | 0 |
word_freq_remove | 0,9 |
word_freq_george | 0 |
Otras características | ... |
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
Iteración | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
Valores de instancia | N / A | .08 <.052 = f | .4 <.195 = f | 0 <.01 = t | 0 <0,005 = t | N / A | .9 <.225 = f |
Predicción | -0,093 | 0,74 | -1,446 | -0,38 | 0,176 | 0 | 1,66 |
La puntuación final de 0.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 los conjuntos de nodos en la misma ruta tienen un efecto conjunto
- El árbol se puede interpretar como un todo.
Se debe tener cuidado al interpretar los nodos individuales, ya que las puntuaciones reflejan una nueva ponderación de los datos en cada iteración.
Descripción del algoritmo
Las entradas al algoritmo de árbol de decisión alterno son:
- Un conjunto de entradas dónde es un vector de atributos y es -1 o 1. Las entradas también se denominan instancias.
- Un juego de pesas correspondiente a cada instancia.
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 de la forma "atributo
1 si (condición previa)2 si (condición)3 devuelve score_one4 más 5 devuelve score_two6 finaliza si 7 más 8 devuelve 09 finaliza si
El algoritmo también requiere varias funciones auxiliares:
- devuelve la suma de los pesos de todos los ejemplos etiquetados positivamente que satisfacen el predicado
- devuelve la suma de los pesos de todos los ejemplos etiquetados negativamente que satisfacen el predicado
- devuelve la suma de los pesos de todos los ejemplos que satisfacen el predicado
El algoritmo es como sigue:
1 función ad_tree2 entradas Conjunto de m instancias de entrenamiento3 4 w i = 1 / m para todo i 5 6 R 0 = una regla con las puntuaciones de una y 0 , condición previa "verdadero" y el estado "verdadero".7 8 el conjunto de todas las condiciones posibles 9 para 10 obtener valores que minimicen 11 12 13 14 R j = nueva regla con precondición p , condición c , y ponderaciones a 1 y a 2 15 16 fin para 17 juego de retorno de R j
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.
Resultados empíricos
La Figura 6 en el documento original [1] demuestra que los ADTrees son típicamente tan robustos como los árboles de decisión mejorados y los tocones de decisión mejorados . Por lo general, se puede lograr una precisión equivalente con una estructura de árbol mucho más simple que los algoritmos de particionamiento recursivos.
Referencias
- ^ a b Yoav Freund y Llew Mason. El algoritmo de árbol de decisión alterno. Actas de la 16a Conferencia Internacional sobre Aprendizaje Automático, páginas 124-133 (1999)
- ^ Bernhard Pfahringer, Geoffrey Holmes y Richard Kirkby. Optimización de la inducción de árboles de decisión alternos. Actas de la Quinta Conferencia de Asia Pacífico sobre los avances en el descubrimiento de conocimientos y la minería de datos. 2001, págs. 477-487
- ^ "Repositorio de aprendizaje automático de UCI" . Ics.uci.edu . Consultado el 16 de marzo de 2012 .
- ^ "Repositorio UCI Machine Learning" . Ics.uci.edu . Consultado el 16 de marzo de 2012 .
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.