Árboles de Decisión – DT

Un árbol de decisión DT (Decision Tree)  es un modelo de predicción de las alternativas posibles a una serie de decisiones relacionadas.

De otra forma, es un método de aprendizaje supervisado no paramétrico para el reconocimiento y clasificación de patrones que permite crear un modelo para predecir el valor de una variable (Atributo) mediante el aprendizaje de reglas de decisión derivadas de las características de los datos. Su objetivo es encontrar una forma de representación de la decisión que sea lo más simple y precisa posible. Es una de las principales técnicas predictivas en el descubrimiento del conocimiento, basándose en datos y observaciones pasadas, predice el futuro.

 

En nuestro caso, las decisiones son datos manejados por un algoritmo, con estructura de clasificación o regresión, que anticipa matemáticamente la mejor opción. En otras palabras, inducen un modelo del dominio de entrada de datos a partir de un conjunto dado de observaciones. Tienen dos funciones: Facilitar el recuento de todas las posibilidades, datos o sucesos, y hacer operativo el cálculo de la probabilidad de los mismos. Es uno de los métodos de aprendizaje inductivo más usado y también muy eficiente en la minería de datos. Se basan en gran medida en métodos estadísticos y de probabilidad.

 

Una de las grandes ventajas de los árboles de decisión, respecto de otras técnicas, es la posibilidad de unir fácilmente varios de ellos y provocar predicciones más seguras con un coste computacional más bajo. Pero no todo es tan fácil, en un entorno caracterizado por la incertidumbre y la imprecisión, debidas al ruido o la variación residual en los datos, no se realiza bien la clasificación, por lo tanto, tener información incierta o imprecisa en relación con cualquier parámetro del problema puede llevar a resultados deficientes, para superar esta limitación se han introducido teorías que pudieran representar la incertidumbre en distintos tipos de árboles:

 

  • Difusos.
  • Convicción.
  • Posibilista.

Los iremos viendo con más detalle en nuevos artículos.

Un poco de historia.

Tratado de Aritmética de Lorenzo el Magnífico Filippo Calandri.
Trattato di arithmetica

Es difícil encontrar el origen de la toma de decisiones y su evolución hasta nuestros dias, pero también es evidente que es consustancial con el origen de los animales y su nivel intelectual.

 

Una de las primeras preguntas documentadas que contiene la intencionalidad de establecer un camino adecuado para obtener una decisión correcta es la de Filippo Calandri que publica en 1.491 «Trattato di arithmetica«, donde plantea el problema del «Reparto de la apuesta» o del «Juego interrumpido» o del «Reparto de puntos», nombres que ha ido tomando a lo largo del tiempo. Este problema cae dentro del estudio de las probabilidades pero también en el de la toma de decisiones.

 

Soluciones se propusieron muchas, las de Luca Pacioli, Gerolamo Cardano, Niccolo Tartaglia, Pierre de Fermat y Jacques Bernoulli con su concepto de «esperanza moral» de 1.738.

 

Después de un par de siglos más, en 1.931, Frank P. Ramsey propuso su teoría de la toma de decisiones, basada en la probabilidad subjetiva y de utilidad. En 1.937 Bruno de Finetti, desde el lado de la incertidumbre, también contribuye a la estructura de la probabilidad subjetiva. Un poco más tarde se llega a las proposiciones de la moderna teoría de la utilidad para la toma de decisiones bajo incertidumbre, desarrollada en 1.944 por John von Neumann y Oskar Morgenstern en base a las ideas de Bernoulli. A partir de aquí hay otros muchos más contribuidores, pero sobrepasa el objetivo de este artículo.

John von Neumann y Oskar Morgenstern
Morgenstern y Neumann

 

Neumann y Morgenstern postularon un conjunto de axiomas usando solo probabilidades objetivas y demostraron que se podría asignar una utilidad a cada consecuencia, de manera tal que el tomador de decisiones prefiera la alternativa con la utilidad más alta esperada para actuar.

 

Hasta los años 80 del siglo pasado, los modelos de árboles de decisión tuvieron mucha popularidad en el entorno científico, médico e industrial debido a su capacidad de aprendizaje y sobre todo por su aplicación en las denominadas EIS (Executive information system) Sistemas de información estratégico. Durante un periodo corto se guardaron en el «cajón de sastre», ya que muchos algoritmos conducían a estructuras de árboles excesivamente ajustados debido a la naturaleza heurística y codiciosa de estos algoritmos.

 

A partir de 1.990 hubo un nuevo interés en su utilización, la acumulación de grandes cantidades de datos en los denominados «Data Wharehouse» por parte de grandes empresas y en la posibilidad de tratarlos con el «Datamining» la Minería de datos, Big Data, y junto con las nuevas tendencias del aprendizaje automático, reconocimiento facial y de objetos, les volvió a dar la importancia que tuvieron en su nacimiento.

 

Cómo es un Árbol de Decisión.

Una «romántica» explicación, en compañía de un matemático, es darnos un paseo en otoño y observar los árboles del camino. Un árbol, de decisión, por lo general comienza con un único tronco (nodo) que representa una característica, de él pueden salir ramas (decisión o regla) que llegan a otro nodo que a su vez puede volverse a ramificar, hasta finalizar en las puntas (hojas), en nuestro caso el nodo terminal o resultado posible.

 

Pero resulta que su representación general es al revés, el tronco es la raíz principal y su desarrollo es hacia abajo, completamente invertido, también se representa horizontalmente. Entonces, lo lógico sería denominarlo raíces de decisión o representarlo hacia arriba, sí, pero le daríamos la vuelta a décadas y …, mejor seguir la corriente ?, además, la representación gráfica de éstos es distinta en función de los distintos criterios de autores y herramientas.

 

Existen muchas y diferentes variantes de árboles de decisión en la literatura y su representación topa con referencias cruzadas, casos especiales, integración y evolución de distintos algoritmos y algunas cuantas cosas más. De forma general se agrupan en función del tipo de problema, la forma en la cual se inducen y el tipo de estructura.

 

Los datos que manejan los árboles se representan con tres tipos diferentes de elementos: Atributos/Predictores, Valores y Clases. Los Atributos se pueden usar para clasificar los datos existentes (árboles de clasificación) o para aproximar funciones de valores reales (árboles de regresión). Tenemos dos tipos básicos de árboles de decisión:

Árbol de clasificación
Árbol de clasificación

 

  • De clasificación, cuando las variables son discretas, numéricas que tienen un número contable de valores en un intervalo cualquiera.  Predice el valor de una variable categórica (objetivo o clase) mediante la construcción de un modelo basado en uno o más predictores o atributos. En cada terminal / hoja asigna una etiqueta de clase, generalmente la clase mayoritaria de todas las instancias que alcanzan esa hoja en particular.

 

  • De regresión, cuando las variables son continuas, numéricas que tienen un número infinito
    Árbol de regresión
    Árbol de regresión

    de valores en un intervalo cualquiera. El árbol predice el valor del objetivo mediante la construcción de un modelo basado en uno o más predictores (variables numéricas y categóricas).  El diagrama del árbol seleccionado tiene cuatro hojas, el color de las hojas representa el valor de respuesta predicho, que es el promedio observado para las observaciones en esa hoja. El nodo 4 tiene el valor de respuesta más bajo y el nodo 3 tiene el valor más alto.

 

 

Según los datos a tratar nos podemos encontrar con:

  • Valores binarios. Solo es posible una división, se generaran dos ramas a partir del nodo a dividir.
  • Valores categóricos (Nominales). Son cualitativos no ordenados y se expresan de dos maneras, la primera es una división de múltiples vías que usa tantas particiones como valores distintos. La segunda es usar una división binaria para obtener los valores en dos subconjuntos. Podemos realizar la división a través de (xi ∈ C) hasta probar todos los valores. Por ejemplo: color de piel, sexo, etc.
  • Valores continuos. Son valores numéricos que tienen características cuantitativas. Con ellos se pueden realizar operaciones numéricas regulares, medias, desviaciones, etc. También se pueden expresar utilizando divisiones binarias, siendo la condición del tipo (xi ≤ r).
  • Valores ordinales: Son similares a los nominales ya que son categóricos y cualitativos, la diferencia radica en que tienen información para ordenarlos. Se pueden expresar como divisiones binarias o de múltiples vías, pero es fundamental no alterar la propiedad de orden de los valores. Por ejemplo: tipo de neumáticos en función de la velocidad (Q, R, S, T, H, V, ZR,…).

Cuando tratemos con árboles utilizaremos frecuentemente estos conceptos:

  • Costo. Se refiere a dos conceptos diferentes: el costo de medición para determinar el valor de una determinada propiedad (atributo) exhibida por el objeto y el costo de clasificación errónea al decidir que el objeto pertenece a la clase X cuando su clase real es Y.
  • Sobreajuste (Overfitting).  Se produce cuando los datos de entrenamiento son pocos o contienen incoherencias. Al tomar un espacio de hipótesis H, se dice que una hipótesis h ∈ H  sobreajusta un conjunto de entrenamiento C si existe alguna hipótesis alternativa h’ ∈ H tal que h clasifica mejor que h’ los elementos del conjunto de entrenamiento, pero h’ clasifica mejor que h el conjunto completo de posibles instancias.
  • Poda (Prunning). La poda consiste en eliminar una rama de un nodo transformándolo en una hoja (terminal), asignándole la clasificación más común de los ejemplos de entrenamiento considerados en ese nodo.
  • La validación cruzada. Es el proceso de construir un árbol con la mayoría de los datos y luego usar la parte restante de los datos para probar la precisión del árbol.

Operativamente un árbol de decisión debe manejar características ordenadas y desordenadas, y después, dividir el conjunto de datos en subconjuntos según sus características, tratando de que sean lo suficientemente pequeños para que contengan datos que caigan dentro de una clase o etiqueta, por ejemplo: Femenino o Masculino. La división se realiza en cada nodo no terminal, a través de una función discriminante, óptima localmente, hasta que todas las muestras en el nodo pertenezcan a una clase o hasta que se cumpla un criterio de detención, esto es, una división binaria recursiva.

 

Generalizando, la construcción de un árbol de decisión se basaría en:

  • La selección de atributos. La selección implica buscar todas las combinaciones posibles de atributos en los datos para encontrar qué subconjunto de ellos funciona mejor para la predicción. Existen distintas opiniones en cómo abordar esta selección debido a que diferentes métodos dan diferentes resultados. La proposición sería, utilizar la ganancia de información, el ratio de ganancia o el algoritmo RELIEF y como resultado el valor promedio de todos los métodos utilizados.
  • El conjunto de preguntas binarias. En la entrada tendremos un vector x = (x1,x2,…xn), que puede contener variables discretas o continuas. Sabiendo que la división del nodo depende de una sola variable, el conjunto de preguntas (P) deberían de ser:
    • Si la variable xi es continua, entonces P contiene las preguntas de la forma { Es xi ≤ r }, donde r ∈ ℜ
    • En caso contrario es categórica, P contiene las preguntas de la forma {¿ xi ∈ C ? }, donde C es cualquier subconjunto de {y1,y2,…yn}
  • El método usado para dividir los nodos. Cada método, función discriminante, debe determinar cuál es la mejor forma de dividir los datos en cada nivel.
  • La técnica para parar el crecimiento del árbol o podarlo. Una idea sería controlar el error de clasificación (con el índice de Gini o la Entropía), en el conjunto de datos de prueba, de manera que se detendrá cuando el índice seleccionado comience a aumentar.
  • La asignación a cada terminal / hoja de un valor de la variable de respuesta (regresión) o a una clase (clasificación).
  • El tratamiento de los valores perdidos (faltan). Es posible que algunos de los valores de las características no estén, en ese caso tenemos que llenarlos de alguna forma, la siguiente puede servir:
    • Si el valor que falta es de una característica ordenada, la rellenamos con el valor medio de la muestra de esa característica.
    • Si es una característica no ordenada, la rellenamos con el valor más probable de esa característica del conjunto de datos.

Esta información se almacena para que se pueda realizar el mismo llenado para el conjunto de prueba.

 

La complejidad en la creación de un árbol de decisión óptimo es: NP-Completa. En 1.976 Laurent Hyafil y Ronald L. Rivest lo demuestran para un árbol binario mínimo. En 1.991, por lados separados, G. E. Naumov lo hace desde tablas de decisión, y J.Murphy y R. L. McCraw también lo hacen para árboles con el menor número de nodos y en 1.995 Thomas Hancock, Tao Jiang, Ming Li y John Tromp terminan de confirmarlo.

 

Cómo construimos un árbol básico. Antes de entrar a construir un árbol de decisión es necesario tener en cuenta que, debemos centrarnos en encontrar atributos que devuelvan la mayor Ganancia de información, es decir, las ramas más homogéneas. Una rama con entropía 0 es un nodo terminal / hoja, una rama con entropía mayor a 0 necesita una división adicional. Establecer los métodos y técnicas que emplearemos (poda, validación cruzada, etc.) o seleccionar una herramienta que nos permita acelerar nuestro trabajo por ejemplo arboles-de-decisión WEKA (Waikato Environment for Knowledge Analysis).

 

Los datos nos llegan en un fichero ARFF, representados por una variable (Atributo) y su valor. A partir de aquí comenzamos a trabajar desde un nodo primario:

  1. ¿Cuál atributo usamos como raíz?.
  2. Dibujamos una rama para cada valor posible.
  3. En los nuevos nodos se vuelve a realizar recursivamente la misma pregunta (2).
  4. Paramos la recursión de una rama si todos sus valores tienen el mismo atributo.

En el ejemplo, los datos son los que aparecen en numerosas publicaciones (jugar al tenis, futbol,…). La representación gráfica puede ser la más adecuada.

 

Las reglas de decisión quedarían así:

  • R1 Si (cielo=soleado) y (Humedad=Normal) jugar.
  • R2 Si (cielo=soleado) y (Humedad=Alta) No jugar.
  • R3 Si (cielo=Nublado) jugar.
  • R4 Si (cielo=Lluvioso) y (Viento=Fuerte) No jugar.
  • R5 Si (cielo=Lluvioso) y (Viento=Débil) jugar.

 

Clasificación según el tipo de función discriminante.

Los árboles de decisión pueden clasificarse en grupos según el tipo de función discriminante aplicada en los nodos no terminales:

  • Univariable. Univariado significa que un nodo interno se divide de acuerdo con el valor de un solo atributo. En cada nodo la función solo puede realizar una serie de divisiones ortogonales en base al eje de xi (hiperplanos de ejes paralelos), dando lugar a árboles más grandes y una generalización pobre. Existen dos características intrínsecas en este tipo de árboles:
    1. Se pueden obtener árboles complicados o inexactos si el límite de decisión del conjunto de datos no es ortogonal a los ejes de características.
    2. El costo computacional aumenta si los atributos son de tipo numérico o si hay un gran número de características.

Ejemplo de algunos algoritmos que los tratan son ID3, CART o C4.5.

 

  • Multivariable u Oblicuo. Son árboles cuyos hiperplanos de separación no son necesariamente paralelos a los ejes, pudiendo tener una dirección arbitraria. Suelen ser más pequeños y, en ciertos casos, tienen una mejor precisión de clasificación que los univariados, sin embargo, la característica a interpretar desaparece.

Cada prueba puede basarse en más de una característica. El algoritmo de construcción no selecciona el mejor atributo sino la mejor combinación lineal de los atributos. La combinación lineal consiste en la multiplicación de pesos con cada característica xi , así que básicamente hay dos operaciones principales en los algoritmos multivariable:

 

    • Selección de características para determinar cuál de ellas usar.
    • Los pesos wi de esas características. La decisión se podría ver como un perceptrón de una sola capa y así, wi y w0 , se pueden determinar entrenando un perceptrón con salida 0/1, haciendo una división binaria.

Debido a que las características, en la división lineal combinada, se multiplican por los coeficientes, debemos convertir las características simbólicas en características numéricas, al realizar esta conversión, todas las características son numéricas y por tanto todas las divisiones son binarias.

Por otro lado, si las características en un árbol mult-ivariable vienen desordenadas, debemos convertir cada característica desordenada i, en una representación numérica y así poder realizar una combinación lineal de las mismas. Por lo tanto, la característica i no ordenada la convertiremos en un conjunto de características múltiples como i1, i2, i3 … en donde ij = 1 si xi toma el valor aj y 0 en caso contrario.

Al final del anterior preproceso, hemos convertido las características (algunas ordenadas algunas desordenadas) x1, x2, … xm en características ordenadas como x1, x21, x22, x23 .. x2m, x31, x32, x33 .. x3m, x4, .., xm donde x1, x4 están ordenadas y  x2j, x3j … son características no ordenadas. Se debe tener en cuenta que la conversión anterior aumentanda la complejidad computacional. Existen dos tipos básicos:

    • Lineal. Utiliza funciones discriminantes lineales. En cada nodo se divide el espacio de entrada en dos vías
    • No lineal. Utiliza funciones discriminantes no lineales. En cada nodo se divide el espacio de entrada arbitrariamente, a costa de una mayor complejidad y un mayor riesgo de sobrealimentación. Algunos algoritmos utilizan un perceptrón multicapa.

 

  •  Omnivariados. Es una proposición realiza por Olcay Taner Yıldız y Ethem Alpaydın en 2.001. En este caso los nodos pueden ser univariados, multivariados lineal o no lineales, dependiendo del resultado de las pruebas estadísticas comparativas de precisión, lo que hace coincidir la complejidad del nodo con el sub-problema definido por los datos que llegan a ese nodo. Dicha arquitectura libera al diseñador de elegir el tipo de nodo apropiado, haciendo la selección del modelo automáticamente en cada nodo. Pero tiene un tiempo de entrenamiento superior.

 

Métodos de división.

La división consiste en seleccionar la variable más adecuada para fraccionar el árbol, esta pequeña toma de decisión afecta mucho al rendimiento del árbol y no es trivial. Después de esta selección, se toma el valor de la variable que proporciona la mejor división, esto se hace para llegar a las diferentes clases con el menor número de divisiones y errores.

 

Las divisiones se aplican en el contexto de los nodos o sus conjuntos de datos, de modo que la división de un nodo y la división de los datos de un nodo son dos nombres para la misma operación. El objetivo final es determinar la variable correcta asociada con el umbral correcto para maximizar la homogeneidad de los subgrupos / ramas. Los algoritmos empleados se basan en gran medida en métodos estadísticos y de probabilidad. Los dos métodos básicos son:  el propuesto en 1.984 por Leo Breiman que se basa en una combinación lineal de características o el de Quinlan, en 1.986, basado en la división por una característica.

 

Univariados. Existen varios métodos para el tratamiento de estos árboles según:

  • El origen de la medida: teoría de la información, dependencia y distancia.
  • La estructura de la medida: criterios basados en la impureza y normalizados, y criterios binarios.

Los más utilizados son los basados en la impureza, están representados por los que cumplen con:

dada una variable aleatoria x con n valores discretos, distribuidos según V = (v1, v2, …, vn), una medida de impureza es una función φ: [0, 1] n → R que cumple las siguientes condiciones:

  • φ (V) ≥0
  • φ (V) es mínimo si ∃i tal que el componente vi = 1.
  • φ (V) es máximo si ∀i, 1 ≤ i ≤ n, vi = 1 / n.
  • φ (V) es simétrico con respecto a los componentes de V.
  • φ (V) es diferenciable en todas partes, en su rango.
  • Ganancia de información.
  • Índice de Gini.
  • Ratio de error. Es el porcentaje de ítems mal clasificados. Esta medida no tiene buen poder discriminador debido a: si que tenemos un sistema de dos clases, en el que y es la clase mayoritaria no solo en X, sino en todas las particiones disponibles de X. La tasa de error considerará a todas esas particiones de igual preferencia.
  • Índice de probabilidad Chi-cuadrado χ2 . Es un método estadístico que mide la independencia entre una distribución observada y otra teórica. Trata de probar la hipótesis nula de que dos variables son independientes, es decir, la ocurrencia de un valor de una variable no induce la ocurrencia del valor de otra. En los árboles de decisión, entre la variable de la división y la variable de la clase.
  • DKM. Es un método basado en impurezas diseñado por Dietterich, Kearns y Mansour. Para clases con atributos binarios se ha demostrado que este método crea árboles más pequeños que para los construidos con C4.5.
  • Distancia normalizada de la información. Es una proposición de Ramón López de Mántaras. La distancia entre un atributo Y y una regla de división S,  es la suma de las dos entropías condicionales que luego se normaliza dividiendo por su entropía conjunta. Resuelve los problemas de partición desequilibrada de ganancia de información en ID3 y la relación de ganancia en C4.5.
  • Criterios binarios.
    • Twoing. Es un medidor de impureza puro, alternativo a Gini. Trata problemas de múltiples clases según criterios de solo dos de ellas, las agrupa en dos superclases y después realiza un análisis de las mismas. Cuando el número original de clases era grande y se trataba de verificar todas las posibilidades provocaba un colapso combinatorio. Esta problemática generó la incorporación de una mejora: En lugar de analizar todas las divisiones para todos los grupos de clases, propusieron un procedimiento (criterio de dosificación) para determinar las superclases óptimas para cada posible división demostrando que para una división binaria dada, se obtiene una disminución máxima de impureza cuando una superclase contiene la mayoría de las clases y la segunda las clases restantes. Este resultado permite mantener la complejidad computacional baja mejorando resultados.
    • Dosificación, Este criterio está en CART como una alternativa al índice de Gini.
    • ORT Medida de la ortogonalidad. Propuesto por Usama Fayyad e Keki Irani en 1.992, miden el ángulo del coseno entre los vectores de probabilidad de clase de las dos particiones. Si la división pone todas las instancias de una clase dada en una partición pero no en la otra, entonces los dos vectores son ortogonales y el coseno es 0. Para un conjunto S, de ejemplos de entrenamiento, y una prueba τ que induce una partición binaria en Sτ y S-τ  teniendo los vectores de clase V1 y V2, respectivamente, la medida de ortogonalidad se define como: ORT (τ, S) = 1 − cosθ (V1, V2).
    • Otras medidas de los vectores: Distancia Kolmogorov-Smirnov, Hellinger y Divergencia Jensen-Shannon.
  • AUC (Area under the ROC Curve). Selecciona el atributo que obtiene el área máxima bajo la envoltura convexa de la curva ROC, este criterio supera en precisión a otros métodos. Es importante tener en cuenta que no realiza una comparación entre la impureza del nodo padre y la impureza ponderada de los hijos después de la división. Representa la probabilidad de que un ejemplo positivo, elegido al azar, se clasifique correctamente con mayor seguridad que una muestra negativa elegida al azar. ROC (Receiver Operating Characteristic) genera un gráfico que muestra el rendimiento de un modelo de clasificación en todos los umbrales de la misma. Una de las maneras fáciles de calcular el valor AUC es usar la regla trapezoidal, suma todos los trapecios debajo de la curva.
  • SSV (Separability of Split Value). Es un criterio de separabilidad que puede aplicarse a diferentes algoritmos de clasificación. Está diseñado para descubrir las mejores divisiones de características continuas o las mejores combinaciones de valores simbólicos de características discretas. Es una alternativa a los criterios más utilizados de la medida de la ganancia de información o el índice de Gini. Refleja la idea de que es ventajoso dividir pares de vectores que pertenecen a diferentes clases, mientras que se deben evitar los pares de vectores de la misma clase.

 

Multivariados. En la división multivariable varios atributos pueden intervenir en la división de un solo nodo. El reto en este tipo de árboles es encontrar el mejor método y la mayoría de ellos se basan en la combinación lineal de los atributos de entrada. Encontrar la mejor combinación lineal se puede realizar utilizando una búsqueda codiciosa / voraz, con programación lineal, análisis discriminante lineal y otros.

 

 

 

Algoritmos aplicados en los árboles de decisión.

Aunque los métodos son diferentes para los diferentes algoritmos, todos ellos tienen la siguiente premisa, ser «voraces», es decir, encontrar una variable que proporcione la máxima ganancia de información o divida los datos de la manera más homogénea.

 

Los algoritmos que construyen el árbol lo realizan para tratar un conjunto de datos con el objetivo de reducir el error de generalización, pero también se pueden definir otras funciones como reducir el número de nodos o la profundidad. La elaboración de un árbol óptimo tiene un nivel de complejidad alto (NP-completa), es una labor difícil, pero viable para pequeños problemas. En consecuencia, se requieren métodos heurísticos para resolver el problema, el más comun es de arriba hacia abajo TDIDT (Top-Down Induction of Decision Tree) como CLS, ID3, C4.5 entre otros.

 

En Redes neuronales.

En las redes neuronales los árboles se tratan como un problema de optimización anidado. En los nodos, el algoritmo de gradiente descendente se usa para encontrar wi (y w0) que reduce el error cuadrático medio y, por lo tanto, encuentra una buena división para los dos grupos de distintas clases. Para la optimización externa se podrá utilizar cualquier método que encuentre la mejor división de clases en dos grupos.

 

Para el trabajo en los nodos se puede utilizar una red neuronal separada para cada nodo del árbol, con tres tipos diferentes de modelos: Perceptrones lineales (multivariados lineales), perceptrones multicapa (multivariados no lineales) y una combinación de ellos.

 

  • Modelo de Perceptrón Lineal. Los xi corresponden a los valores normalizados de los atributos para cada instancia, los wi corresponden a los coeficientes de los atributos y –w0 es un desplazamiento independiente de la entrada. El entrenamiento de esta red se realiza mediante un algoritmo del gradiente descendente estocástico para reducir el criterio de error de mínimos cuadrados (sig es la función sigmoidea o logística). Tomamos (xt, dt) como datos de entrenamiento, donde xt es la enésima instancia de t y dt es la salida deseada para esa instancia que es 1 para el hijo / nodo izquierdo y 0 para el hijo / nodo derecho. yt es la salida real encontrada por la fórmula:

  • Modelo de Perceptrón Multicapa. La salida yt se encuentra como:

Los parámetros whi y Th, son respectivamente los pesos de la primera y la segunda capa. H es el número de unidades ocultas y se toma d/2, como la mitad del número de entradas.

 

  • Modelo Hibrido. Pensamos que lo mejor puede ser encontrar una forma de combinar métodos lineales y no lineales, debido a que los métodos no lineales tienen demasiados parámetros y son propensos a sobreajuste y no son interpretables. La forma de trabajar sería entrenar en cada nodo un perceptrón tanto lineal como no lineal y utilizar una prueba estadística para verificar si existe una diferencia de rendimiento significativa entre los dos. Si el rendimiento del perceptrón multicapa es mejor, está claro, elegimos ese modelo y en caso contrario el del perceptrón lineal. De todas formas el % lo marcaremos a nuestra elección, teniendo claro que el perceptrón lineal es el más simple.

 

Evolución de los algoritmos (2.016).

 

Árboles de decisión, Algoritmos, Modelos y Herramientas
Año Acrónimo Autor Comentario
1.963 AID John A. Sonquist y James N. Morgan Automatic Interaction Detection. Su idea más importante fue especificar una variable independiente para una regresión lineal y buscar divisiones que optimizasen el ajuste de la regresión en las ramas. En ocasiones, una variable de entrada domina la variable dependiente, de modo que los datos solo se dividen un poco más. Aplicando la técnica de regresión eliminan ese efecto dominante y continúan con la división.  No incluyen el tratamiento de los valores perdidos. En 1.971 se publicó la tercera versión denominándose SEARCH que fue mantenida hasta 1.996.
1.966 CLS 1-9 Earl B. HuntEarl B. Hunt, Janet Marin y Philip J. Stone Concept Learning System. Son algoritmos diseñados en base a la inducción, es el precursor de ID3. Hasta la versión CLS-8 construyen árboles binarios, mientras que CLS-9 permite multi criterio. Es el trabajo pionero en la inducción descendente de árboles que intenta reducir el costo de clasificar un objeto, utiliza una estrategia de búsqueda similar al minimax. En cada etapa, explora el espacio de posibles tomas de decisiones a una profundidad fija, elige una acción para reducir el costo en este espacio limitado y luego se mueve hacia abajo en el árbol. Dependiendo de la profundidad de búsqueda anticipada elegida, CLS puede requerir una cantidad sustancial de cómputo. Requiere que cada propiedad utilizada para describir objetos tenga solo valores de un conjunto específico.
1.967 ELISEE J. C. Cellard,B. Labbé y G. Savitsky Exploration of Links and Interactions through Segmentation of an Experimental Ensemble. Es un método binario para variables dependientes categóricas.
1.969 IDEA L. I. Press, M. S. Rogers y G. H Shure Interactive Data Exploration and Analysis. Herramienta para el crecimiento de árboles que permite multicriterio.
1.972 THAID J.N. Morgan y R.C. Messenger THeta AID. Es una ampliación de AID para resultados categóricos utilizando el criterio Theta.
1.972 MAID M.W. Gillo Es una versión extendida de AID para variables de resultado cuantitativas multicriterio.
1.979 SVM Vladimir N. Vapnik Support Vector Machines. Ver SVM
1.980 CHAID Gordan V. Kass y Doug Hawkins Chi-square Automatic Interaction Detector. Es una evolución mejorada de AID y THAID con supervisión estadística. El criterio para dividir está basado en χ2 y para terminar el proceso se requiere definir de antemano un umbral. Utiliza el ajuste de Carlo E. Bonferroni para el número de valores categóricos de la variable de entrada, mitigando así el sesgo hacia entradas con muchos valores. También incluye el proceso de los valores perdidos.
1.983-79 ID3

J. Ross QuinlanJ. Ross Quinlan

Dichotomiser Iterativo 3. Continúa el concepto de CLS. Comienza con la selección del mejor atributo para probar en la raíz del árbol. Para encontrar el mejor atributo, cada atributo de instancia se pone en una prueba estadística para determinar qué tan bien clasifica los ejemplos de entrenamiento. La mejor característica se selecciona y se usa como un nodo de prueba. Luego se crea un hijo del nodo raíz para cada valor posible del atributo a, es decir, dos hijos para entidades ordenadas como xi < a y xi > a, y n hijos para una entidad no ordenada como xi = a1, xi = a2xian , donde n es el número de diferentes valores posibles de la característica xi. Todo el proceso se repite recursivamente con los ejemplos de capacitación asociados con cada nodo secundario para seleccionar el mejor atributo para probar en ese punto del árbol. Es un algoritmo que siempre va hacia adelante y se le denomina de búsqueda «voraz». Requiere que cada propiedad utilizada para describir objetos tenga solo valores de un conjunto específico. .
1.983 ACLS

Tim Niblett

A. Patterson y T. Niblett

Es una generalización de ID3 y de CLS, pero permite propiedades que tienen valores enteros no restringidos, este tipo de capacidad ha permitido aplicarlo a tareas difíciles como el reconocimiento de imágenes.
1.984 ASSISTANT

Ivan Bratko Igor Kononenko

Igor Kononenko, Ivan Bratko y Egidija Roškarr

Permite atributos con valores continuos (reales). En lugar de insistir en que las clases se separen permite formar una jerarquía, de modo que una clase puede ser una división más fina de otra. Incluye otros algoritmos para elegir un conjunto de entrenamiento «bueno» de los objetos disponibles. Se ha utilizado en áreas de la salud con resultados positivos.
1.984 CART

Leo BreimanCharles StoneJerome FriedmanRichard-Olshen

Leo Breiman, Jerome Friedman, Richard Olshen y Charles Stone

Classification and Regression Tree. Fue primer algoritmo de árbol de decisión oblicuo. Construye árboles binarios recursivos de clasificación o de regresión multivariable lineal. Originalmente se aplicaba sólo para la predicción de los datos univariados. Cuando la variable es :
  • Binaria, cada valor define un grupo para una división.
  • Discreta, todas las combinaciones de los grupos son asumidas (para un valor n, se prueban los subconjuntos (2n – 2) /2).
  • Continua, todos los posibles puntos de corte se prueban (para n registros, como máximo se prueban  n – 1 puntos de corte).

Su misión es producir no uno, sino una secuencia de árboles podados anidados, todos los cuales son árboles óptimos candidatos. El árbol de «tamaño correcto» se identifica al evaluar el rendimiento predictivo de cada árbol. Los datos se manejan tal como vienen, no se filtran. Los árboles crecen a un tamaño máximo sin regla de detención y luego se podan mediante la poda complejidad de costo. La siguiente división a ser eliminada es la que menos contribuye al rendimiento general del árbol en los datos de entrenamiento (y se pueden eliminar más de una a la vez).

1.984 CART-LC L. Breiman, J.Friedman, R. Olshen y C. Stone

CART Linear Combination. Es una versión de CART donde el conjunto de divisiones permitidas se amplia para incluir todas las combinaciones lineales divididas. Pero resolver este conjunto de combinaciones lineales utilizando una búsqueda heurística determinista es costoso computacional. En cada nodo encuentra iterativamente valores óptimos para cada uno de los coeficientes. Los hiperplanos se generan y prueban hasta que los beneficios marginales se vuelven más pequeños que una constante dada.

Forma de todas las combinaciones ineales:

1.988 RECPAM Antonio Ciampi, Roxane du Berger, H.Gerry Taylor y JohanneThiffault RECursive Partition and AMalgamation. Es un método para construir árboles de regresión a partir de datos que permite el tratamiento explícito de una gran variedad de variables de respuesta. Su enfoque de clasificación encuentra clases que se describen en términos de algunas de las variables, de tal manera que la distribución conjunta de todas las variables es, al menos aproximadamente, homogénea dentro de las clases y distinta entre clases. Trata simultáneamente variables categóricas y continuas
1.988 FACT

Wei-Yin Loh

Wei-Yin Loh y Nunta Vanichsetakul

Es un algoritmo que combina CART y LDA (Análisis Discriminante Lineal). El análisis discriminante es el método clásico para predecir la pertenencia a un grupo en función de las características predictivas.

FACT puede utilizar más de una función discriminante y usa un algoritmo de costo de clasificación errónea diferente a CART y basado en las funciones discriminantes.

1.988 CN2

Peter ClarkTim Niblett

Peter Clark y Tim Niblett

Es una variante de ID3, se basa en la reducción de la entropía media para seleccionar el atributo que genera cada partición (cada nodo del árbol), seleccionando aquél con el que la reducción es máxima. Los nodos del árbol están etiquetados con nombres de atributos, las ramas con los posibles valores del atributo, y las hojas (Terminales) con las diferentes clases. Permite clasificar ejemplos con atributos que toman valores continuos.

1.988

2.018

Earth – MARS J. H. FriedmanStephen-Milborrow TREVOR-HASTIE

J. H. Friedman (S. Milborrow, T.Hastie, R Tibshirani + otros 111)

Multivariate Adaptive Regression Splines (MARS), nombre inicial que se transforma en Earth como herramienta de libre distribución. Es una técnica de regresión que funciona de manera similar a los árboles de regresión, pero utiliza funciones de base lineal en lugar de funciones escalonadas. Crea múltiples modelos de regresión en todo el rango de valores del predictor/atributo, lo hace mediante la partición de los datos y ejecuta un modelo de regresión en cada partición diferente. Los términos se eliminan en orden creciente de reducción de errores. La métrica de error es la estadística de validación cruzada generalizada (GCV).
1.991 Exhaustive CHAID David Biggs, Barry De Ville y Ed Suen Es una mejora de CHAID: Admite una heurística más completa para encontrar, en cada nodo, la forma óptima de agrupar las categorías de cada predictor. Realiza una aproximación más adecuada para el factor de corrección de Bonferroni que evita la discriminación de variables nominales con un gran número de categorías.
1.991 MAPS Andrew R. BarronAndrew R. Barron y Xiangyu Xiao Multivariate Adaptive Polynomial Synthesis. Sigue la estrategia y muchas características de MARS, la diferencia básica es la utilización de polinomios globales en lugar de splines. Proporciona una opción para restringir el orden de interacción de los términos candidatos para que no sea mayor que un límite específico.
1.991 LMDT Paul-E.-UtgoffCarla E. Brodley
Paul E. Utgoff y Carla E. Brodley
Linear Machine Decision Trees. Es un algoritmo oblicuo / multivariado que construye una máquina lineal para dividir cada nodo. La máquina es un conjunto de k funciones discriminantes lineales combinadas en una sola máquina para clasificar los objetos de datos en una de las k clases del problema que se está resolviendo.
Para hacer que los modelos fuesen lo más simples y precisos posibles incorporaron una técnica para eliminar variables durante los procesos de aprendizaje. Propusieron repetir el entrenamiento después de la eliminación de la característica que menos contribuye a la discriminación. Las mejores soluciones se registran y las nuevas deben compararse con ellas para estimar si los resultados no se degradan.
1.992 M5 J. Ross QuinlanJ. Ross Quinlan

Construye modelos basados en árboles pero, mientras que los árboles de regresión tienen valores en sus hojas, los árboles que M5 construye pueden tener modelos lineales multivariados. Puede abordar tareas con una dimensión muy alta, cientos de atributos, superior a CART y MARS

 

1.992 Decision Stump

Wayne Iba Pat Langley

Wayne Iba y Pat Langley

Es un árbol de decisión de un nivel. Tiene un nodo interno que está conectado directamente a los nodos de terminación. Un solo nodo raíz decide cómo clasificar las entradas según una sola entidad. Cada hoja representa un valor de entidad posible, la etiqueta de clase que debe asignarse a las entradas cuyas características tienen ese valor.
1.993 OC1 Sreerama K. MurthyRichard Beigel Sreerama K. Murthy, Simon Kasif, Steven Salzberg y
Richard Beigel
Es una extensión de CART. Busca la mejor división univariada así como la mejor división oblicua, y solo emplea la división oblicua cuando mejora la división univariada. Utiliza tanto una búsqueda heurística determinista (CART) para encontrar el óptimo local y una búsqueda no determinista (SADT) para escapar de óptimos locales. Durante la búsqueda determinista perturba los coeficientes del hiperplano secuencialmente (de la misma manera que lo hace CART) hasta que no se obtiene una ganancia significativa de acuerdo con una medida de impureza.
1.993 SADT David Heath, Simon Kasif y Steven Salzberg Simulated Annealing of Decision Trees. Crea árboles oblicuos-multivariado de forma aleatoria. Para encontrar buenos valores para los coeficientes del hiperplano, en cada nodo de un árbol, coloca primero un hiperplano en una ubicación canónica, y luego perturba iterativamente todos los coeficientes en pequeñas cantidades aleatorias. Si bien el uso de la aleatorización le permite evitar algunos mínimos locales, por otro lado pierde eficiencia al ser más lento que CART-LC, LMDT o OC1, a veces considera decenas de miles de hiperplanos en un solo nodo antes de que finalice un ciclo.
1.993 T1 Holte Un árbol de decisión de un nivel que clasifica instancias usando solo un atributo. Los valores que faltan se tratan como un «valor especial». Soporta tanto atributos continuos como nominales.
1.993 C4.5 J. Ross QuinlanJ. Ross Quinlan Es una extensión del algoritmo ID3. Se basa en la utilización del criterio de ratio de ganancia. En el método se consigue evitar que las variables con mayor número de posibles valores salgan beneficiadas en la selección. Incorpora  el  MLPC (Multi-Level Pruned Classifier) como algoritmo de poda.

1.968

1.993

MML

Christropher S. Wallace

Jon D. Patrick y Christropher S. Wallace

Minimum Message Length. La longitud mínima de mensaje es una teoría de la inferencia inductiva, donde el modelo preferido es el que reduce la longitud de mensaje esperada. En 1.968  Wallace y David Boulton desarrollaron el programa «SNOB» para la clasificación no supervisada que fue la primera aplicación de esa teoría. En 1.993 Patrick y Wallance lo codifican para árboles de decisión, haciendo que no se sobredimensionen, sean poco profundos, no necesiten poda y sean excelentes para predicciones probabilísticas.
1.994 CAL5 Wolfgang Müller y Fritz Wysotzki
Algoritmo de inducción para la clasificación y predicción que convierte los atributos de valor real en intervalos utilizando herramientas estadísticas. Los árboles se recortan automáticamente con la ayuda de un umbral para las probabilidades estimadas de una clase en un intervalo. Por medio de este umbral el usuario puede controlar la complejidad del árbol.
1.994 RLDT

George H. John

George H. John

Robust Linear Decision Trees. Es un método que puede inducir árboles de decisión oblicuos, el método se basa en una función discriminante lineal para descubrir los mejores puntos de división. Resuelven iterativamente un problema de optimización utilizando gradientes. Su función tiene la firma:

1.995 Ridor Brian R. Gaines y Paul Compton RIpple-DOwn Rule learner. Es un generador de reglas superior a PART y JRip. El algoritmo genera primero la regla predeterminada y luego genera las excepciones de la misma, junto con la menor tasa de error. En un segundo paso y de forma reiterativa, genera las «mejores» excepciones para cada excepción. Por lo tanto, realiza una expansión tipo árbol de excepciones. Las excepciones son un conjunto de reglas que predicen clases distintas de las predeterminadas. IREP se usa para generar las excepciones,.
1.995 Random forest

Tin Kam Ho

Es un algoritmo de aprendizaje supervisado, está compuesto de distintos métodos que hacen uso de áboles de decisión como elementos básicos. Permite la construcción de un «bosque de árboles» al azar, todos ligeramente diferentes. Es eficiente para estimar los datos faltantes y al Igual que REPTree, elige el mejor árbol de los creados. Es un algoritmo muy preciso que se puede usar tanto para regresión como para clasificación.
1.995 AdaBoost

Yoav Freund Robert E. Schapire

Yoav Freund y Robert E. Schapire

Adaptive Boosting. Es el primer algoritmo práctico de refuerzo. Se centra en los problemas de clasificación y pretende convertir un conjunto de clasificadores débiles en uno fuerte. El algoritmo se puede usar para reducir significativamente el error de cualquier algoritmo de aprendizaje que genere de forma consistente clasificadores cuyo rendimiento sea un poco mejor que con el azar. La ecuación final para la clasificación se puede representar como:Donde:

ht (x) es la salida del clasificador débil t para la entrada x

ωt es el peso asignado al clasificador.

ωt se calcula de la siguiente manera: ωt = 0.5 * ln ((1 – E) / E). El peso del clasificador se basa en la tasa de error E.

1.996 BAGGING Leo Breiman

Leo Breiman

Genera conjuntos de entrenamiento aleatoriamente y por lo tanto los clasificadores se pueden calcular en paralelo.
1.996 SLIQ

Rakesh Agrawal Jorma Rissanen

Manish Mehta, Rakesh Agrawal y Jorma Rissanen

Supervised Learning in Quest. Es un clasificador que puede manejar atributos numéricos y categóricos. Utiliza una técnica de clasificación previa que se integra con una estrategia de crecimiento, en un primer nivel, para permitir la clasificación de los conjuntos de datos residentes (memoria o almacenamiento). Para la fase de poda utiliza un algoritmo que se basa en el Principio de Longitud de Descripción Mínima, este algoritmo da como resultado árboles compactos y precisos.
1.996 SPRINT

 Rakesh Agrawal

John Shafer, Rakesh Agrawal y Manish Mehta

Es sinónimo de algoritmo escalable de inducción de árbol de decisión multivariado.  Es un clasificador rápido que no se basa en el algoritmo de Hunt para construir el árbol, sino que parte el conjunto de datos de entrenamiento de forma recursiva, utilizando la técnica de codicia «voraz» de primer plano, hasta que cada partición pertenezca al mismo nodo hoja o clase.

Elimina las restricciones de memoria que imponía SLIQ. El algoritmo es la primera paralelización escalable de un clasificador donde todos los procesadores trabajan juntos para construir un modelo coherente y único. La combinación de estas características hace que el algoritmo propuesto sea una herramienta adaptada para la minería de datos.

 1.997  LTree João Ao Gama

Probabilistic Linear Trees. Los árboles lineales probabilísticos surgen de una combinación de tres ideas: Combinan un árbol de decisión con el criterio de divide y vencerás, análisis lineal discriminante y la inducción constructiva.

En cada división de un nodo se realizan dos pasos independientes:

  • Construcción de nuevos atributos. Son combinaciones lineales de las características de los existentes.
  • La utilización de técnicas de división univariadas.

Se ha demostrado que se ejecuta bien en términos de precisión y tiempo de aprendizaje en comparación con otros sistemas multivariaticos como CART, LMDT o OC1.

1.997 QUEST Wei-Yin Loh Wei-Yin Loh y Yu-Shan Shih

Quick, Unbiased, Efficient, Statistical Tree. Tiene un sesgo insignificante respecto de los árboles de clasificación basados ​​en algoritmos de búsqueda exhaustivos, ya que tienden a sesgarse hacia la selección de variables que permiten más divisiones.

La forma de selección es similar a la del método FACT, pero produce divisiones binarias y el árbol final puede seleccionarse mediante una regla de detención directa o mediante poda.

1.997 FIRM Hawkins Formal Inference-based Recursive Modeling.
1.998 CLOUDS Alsabti Multivariado
1.999 MART J. H. Friedman Multiple Additive Regression Trees. Múltiples árboles de regresión aditiva es una metodología para tratar de resolver los problemas de predicción en la regresión y clasificación. Es uno de los métodos denominados «Boosting». Presta resistencia a valores atípicos, valores perdidos y la inclusión de números potencialmente grandes de variables predictivas irrelevantes que tienen poco o ningún efecto en el resultado.
1.999 APDT  P. Shanti Sastry Shesha ShahShesha Shah y P. Shanti Sastry Alopex Perceptron Decision Tree. Es un inductor de árboles de decisión oblicuo que utiliza un criterio de división basado en el nivel de no separabilidad de las instancias de entrada. Toma el algoritmo de un Perceptron para estimar el número de instancias no separables que pertenecen a cada una de las particiones binarias proporcionadas por un hiperplano inicial. Luego emplea el algoritmo Alopex, de K.P. Unnikrishnan y K.P. Venugopal, para ajustar los pesos del hiperplano teniendo en cuenta la necesidad de reducir el nuevo criterio de división en función del grado de separabilidad de las particiones.
2.000 CMP Wang and Zaniolo Multivariado
2.000 LDT

Olcay Taner Yildiz Ethem Alpaydin

Olcay Taner Yildiz y Ethem Alpaydin

Linear Decision Trees. Crea árboles binarios realizando un análisis discriminante en cada nodo (con opciones de divisiones univariadas o multivariadas y análisis lineal discriminante) y después análisis discriminante cuadrático de las clases con representantes en el nodo, que se agrupan en dos superclases. Sigue la idea del análisis discriminante lineal de Fisher (FDA).
2.000 PUBLIC Rastogi y Shim Integra el crecimiento y la poda utilizando el costo de MDL para reducir la complejidad computacional.
2.000 VFDT

   Pedro DomingosGeoff Hulten

Pedro Domingos y Geoff Hulten

Very Fast Decision Tree (Hoeffding Decision Tree -HDT-). Es un algoritmo para la clasificación de flujo de datos. Utiliza el límite de Hoeffding para decidir el número mínimo de instancias que llegan para lograr cierto nivel de confianza al dividir el nodo. Se está utilizando para la minería de datos (Data Mining).
2.001 CVFDT Geoff Hulten, Laurie Spencer y Pedro Domingos Concept-adapting Very Fast Decision Tree. Es una extensión de VFDT que añade la capacidad de detectar y responder a cambios en el proceso de generación de ejemplos. CVFDT funciona manteniendo su modelo con una ventana deslizante de ejemplos, esto le facilita aprender un nuevo modelo sin partir de cero.
2.001 CRUISE Wei-Yin Loh Hyunjoong Kim  y Wei-Yin Loh Classification Rule with Unbiased Interaction Selection and Estimation. Programa de libre distribución, es una versión muy mejorada de FACT: Divide cada nodo en tantos sub-nodos como el número de clases en la variable de respuesta. Tiene sesgo insignificante en la selección de variables. Tiene varias formas de lidiar con los valores faltantes. Puede detectar interacciones locales entre pares de variables predictoras.
2.003 RandomTree

Philip S. YuWei Fan 

Wei Fan, Haixun Wang, Philip S. Yu y Sheng Ma

Considera un conjunto de K atributos elegidos al azar para dividirse en cada nodo. Aleatorio aquí significa que cada árbol en el conjunto de árboles tiene la misma probabilidad de ser muestreado y, por lo tanto, de hacer una distribución uniforme de los árboles. Los árboles aleatorios se pueden generar de manera eficiente y la combinación de grandes conjuntos de árboles aleatorios generalmente conduce a modelos precisos.
La profundidad de cada árbol es igual a la mitad del número total de características presentes en los datos. No realiza podas.
2.003 VFML

Pedro DomingosGeoff Hulten

Pedro Domingos y Geoff Hulten

Very Fast Machine Learning. Es un conjunto de herramientas, árboles y APIs que ayudan al usuario a desarrollar nuevos algoritmos de aprendizaje, también contiene varias colección de algoritmos de aprendizaje y aprendizaje escalable. Lo mejor de todo es que es de libre disposición y permite aprender de (VFDT y CVFDT). Los autores fueron apoyados por: Chun-Hsiang Hung, Matthew Richardson y Laurie Spencer.
 2.003  SODI Sigurdur OlafssonJun-Youl Lee y Sigurdur Olafsson Second Order Decision tree Induction.  Tiene el inconveniente de que la descripción de la hipótesis para cada nodo es más compleja que el desarrollado por otros algoritmos, pero el tamaño del árbol tiende a ser menor, genera menos reglas de decisión, son más intuitivas y la precisión de los árboles mejora respecto de otros métodos.
2.004 RTA

Elise DusseldorpJacqueline-j-meulman

Elise Dusseldorp y Jacque Meulman

Regression Trunk Approach. Combina los árboles de regresión y el análisis de regresión múltiple de la siguiente forma: usa árboles de regresión pequeños para descubrir los efectos de la interacción y posteriormente usa la regresión lineal múltiple para probar los efectos de esa interacción.
2.006 VFDTc João GamaJoão Gama, Ricardo Fernandes y Ricardo Rocha Es un algoritmo derivado de VFDT. Los autores indican que mejoran a VFDT en la capacidad de manejar datos continuos, el uso de técnicas de clasificación más potentes en las hojas de los árboles y la capacidad de detectar y reaccionar ante la deriva del concepto.
2.010 MOA

Bernhard-PfahringerGeoff-HolmesRichard-Kirkby

G. Holmes, R. Kirkby y B. Pfahringer

Massive Online Analysis. Es un entorno de software para implementar algoritmos y ejecutar experimentos en línea aprendiendo de flujos de datos. (JAVA).
2.013 Fisher-DT A. López-Chau, Jair Cervantes, L. López-García y F. García Lamont Es un algoritmo que se denomina así por utilizar la reducción de la dimensión del discriminante lineal de Fisher. Es capaz de clasificar perfectamente los objetos que pertenecen a conjuntos de datos que son linealmente separables. Utiliza un atributo artificial para dividir los datos de forma recursiva y crear un árbol de decisión oblicuo.
2.016 VHT Nicolas Kourtellis, Gianmarco F. Morales y Arinto Murdopo Vertical Hoeffding Tree. Es un algoritmo de transmisión distribuida para árboles de decisión mediante paralelismo vertical. El algoritmo se implementa sobre Apache SAMOA.
2.017 StreamDM

zhang-jiajinJianfeng-QianGeoff-HolmesBernhard-Pfahringer

Zhang Jiajin, Wei Fan, Cheng He, Jianfeng Zhang, Jianfeng Qian, B. Pfahringer y Geoff Holmes

C++ Data Stream Mining System. Herramienta competidora de VFML que, de momento, implementa árboles de decisión más rápidos y que contiene más algoritmos de clasificación que VFML. Orientada al flujo de datos, «big data streams».
2.018 EFDT Chaitanya Manapragada,
Geoffrey I. Webb
y Mahsa Salehi
Extremely Fast Decision Tree. Es un algoritmo para la clasificación de flujo de datos que tiene un análisis estadístico que le permite un aprendizaje más rápido y con menos datos respecto a VFDT. El algoritmo «espera hasta estar seguro» de que puede añadir una nueva rama en el árbol. Esto hace que se vea menos afectado por la complejidad de la tarea de aprendizaje, pero incurre en una sobrecarga computacional para hacerlo.

Ejemplo computacional.

 

Clasificador árbol de decisión con Weka
Clasificador árbol de decisión con Weka

 

 

Resultados Fichero de entrenamiento
En la columna de la derecha está el contenido del fichero de entrenamiento. Abajo el resultado de tratarlo con algunas funciones que implementa Weka. Existen muchas más, pero con el ejemplo se puede tener una idea de lo fácil que es solicitarlas. Se ha utilizado lenguaje Java, pero también se podría abordar con otros que admitan sus librerías. @relation Campeonato
@attribute outlook{MarcM, Jorje, Valen}
@attribute circuito numeric
@attribute maxveloc numeric
@attribute puntosAc numeric
@attribute penaliza {TRUE, FALSE}
@attribute gana {Si, No}
@data
MarcM, 5 285 85 FALSE, No
MarcM, 4 290 90 TRUE, No
Jorje, 3 286 86 FALSE, Si
MarcM, 5 285 85 FALSE, No
MarcM, 4 290 90 TRUE, No
Valen, 4 296 96 FALSE, Si
Jorje, 3 286 86 FALSE, Si
Valen, 4 280 80 FALSE, No
Valen, 6 270 70 TRUE, No
Jorje, 4 265 65 TRUE, Si
MarcM, 2 295 95 FALSE, No
MarcM, 5 270 70 FALSE, Si
Valen, 5 280 80 FALSE, No
MarcM, 5 270 70 TRUE, Si
Jorje, 2 290 90 TRUE, Si
Jorje, 1 275 75 FALSE, Si
Valen, 3 261 91 TRUE, No
Valen, 1 294 91 TRUE, Si
Valen, 2 290 91 TRUE, Si
Valen, 6 270 70 TRUE, No
Jorje, 6 265 65 TRUE, Si
MarcM, 7 295 95 FALSE, No
MarcM, 6 270 70 FALSE, Si
Valen, 7 280 80 FALSE, No
MarcM, 7 270 70 TRUE, Si
MarcM, 8 255 85 FALSE, Si
MarcM, 9 208 97 TRUE, No
Jorje, 9 266 86 FALSE, No
MarcM, 9 255 85 FALSE, Si
MarcM, 8 290 96 TRUE, Si
Valen, 9 266 96 FALSE, No
Jorje, 9 266 83 FALSE, No
Valen, 8 209 99 FALSE, Si
Valen, 9 200 75 TRUE, No
Jorje, 9 255 65 TRUE, Si
MarcM, 8 295 92 FALSE, No
MarcM, 9 270 72 FALSE, Si
Valen, 8 200 83 FALSE, Si
MarcM, 9 200 73 TRUE, Si
Jorje, 8 207 96 TRUE, No
Jorje, 9 255 75 FALSE, Si
Valen, 9 211 71 TRUE, Si
Valen, 9 296 93 TRUE, No
Valen, 9 216 91 TRUE, Si
Valen, 8 200 79 TRUE, No
Jorje, 9 257 65 TRUE, Si
MarcM, 7 255 95 FALSE, No
MarcM, 8 235 73 FALSE, Si
Valen, 9 205 80 FALSE, No
MarcM, 9 240 70 TRUE, Si

 

 

6 thoughts on “Árboles de Decisión – DT

  1. Hi there! I could have sworn I’ve visited this website before but after going through a few
    of the articles I realized it’s new to me. Nonetheless, I’m definitely
    happy I found it and I’ll be book-marking it and checking back
    often!

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

5 × uno =