Sobre la historia de CART y rpart

25 Jun

Hace unos días conversábamos Raúl y yo sobre árboles de clasificación. En particular, hablábamos de CART, el algoritmo propietario de Salford Systems. Me intrigó saber cuál sería la diferencia entre dicho algoritmo y la alternativa existente en R, rpart.

El autor de dicho paquete, Terry Therneau,  tuvo la gentileza de ofrecer una introducción histórica al particular de la que ofrezco algunos fragmentos que traduzco yo mismo a continuación:

[…]

Tanto el programa comercial CART como la función rpart() están basados en el libro Classification and Regression Trees. Como lector y revisor de alguno de sus primeros borradores, llegué a dominar la materia. CART comenzó como un enorme programa en Fortran que escribió Jerry Friedman y que sirvió para contrastar las ideas contenidas en el libro. Tuve el código durante un tiempo y realicé algunos cambios, pero me resultó demasiado frustrante el trabajar con él. Fortran no es el lenguaje adecuado para un algoritmo recursivo […]. Salford Systems adquirió los derechos de dicho código e ignoro si alguna de las líneas origininales permanecen en él todavía. Mantuve muchas conversaciones con su principal programador (hace 15 o 20 años) sobre procedimientos para hacerlo más eficiente, esencialmente un problema interesante de indexación óptima.

La versión original de rpart coincidía con CART de manera casi absoluta. La única diferencia reseñable estaba en los surrogates: yo me decantaba por el surrogate con el mayor número de coincidencias mientras que CART lo hacía por el que tenía mayor porcentaje de coincidencias. La consecuencia es que rpart favorece aquellas variables con menos missings. Desde entonces, ambos programas han evolucionado. Yo no he tenido tiempo de trabajar de manera sustancial en rpart durante los últimos diez años. No es de extrañar, por tanto, que los gráficos y la visualización hayan quedado algo anticuados; lo que es más sorprendente es que todavía subsistan.

Rpart se llama rpart porque los autores registraron comercialmente el término CART. Era la mejor alternativa que se me ocurrió entonces. Me parece curioso que una de las consecuencias de haber registrado «CART» es que ahora se utilice «particionamiento recursivo» mucho más a menudo que CART como nombre genérico para los métodos basados en árboles.

[…]

El lector queda invitado a extraer sus propias conclusiones.

12 respuestas a «Sobre la historia de CART y rpart»

  1. buen artículo.
    Por cierto, esta mañana he asistido a una presentación sobre el SAS 9.2, en el que anuncian que antes de acabar este año habrá 51 actualizaciones de software y la posibilidad de que podamos descargar las herramientas-módulos desde web en vez de tener que meter una pila de CD´s en la máquina a la hora de instalarlo.Además han hecho mención en un ‘slide’ de powerpoint que van a intergrar R en SAS, aunque no me han sabido especificar hasta qué nivel estan hablando de integración, dicen que será capaz de leer funciones… ahí queda!
    Saludos desde Barcelona.

  2. Ejecuten estas líneas de código en R:

    > install.packages(«rpart»)

    Vamos a comenzar a trabajar con árboles en R. Prometo un monográfico de aproximación a este paquete y si es posible aplicaciones al mundo del marketing incluso.

  3. Sí, R se integrará con SAS (creo que escribí algo al respecto en este blog) a través de IML, tengo entendido. Sin embargo, poca gente sabe en qué quedará la cosa.

    Lo que sí es cierto es que existe ya un artículo en la base de conocimiento de SAS sobre cómo invocar R desde SAS (aunque sea con un «wrapper» alrededor de llamadas a través del sistema operativo a los ejecutables de R y lecturas y escrituras de ficheros de datos en texto).

  4. Carlos, ¿qué alternativas tenemos de rpart? Estoy con un monográfico sobre el tema (no con un capítulo del manual) y me gustaría analizar las posibles alternativas.

    Gracias.

  5. Hola…

    Pues yo comenzaría por los enlaces de la entrada que hice el otro día:

    https://analisisydecision.es/partykit-un-paquete-de-r-para-generar-y-manipular-arboles-de-decision/

    En particular, antes del monográfico, esperaría a ver qué tal queda el paquete partykit de R.

    Fuera de R hay bastantes alternativas. Aparte de las de SAS con el EM y Clementine, tienes, que yo haya probado, las de Weka, KNIME y RapidMiner.

    Más que en los árboles en sí, creo que la chicha está en métodos de combinación de árboles tipo bagging, «random forests», etc.

    Un saludo,

    Carlos J. Gil Bellosta
    http://www.datanalytics.com

  6. Mi pregunta iba más orientada a la segunda parte de tu respuesta. Tengo que buscar algo que me permita combinar árboles.

    La idea es que estaba simulando la cartera de un banco con 100.000 clientes y determinados saldos. Es evidente que rpart no podía con ello pero tiene que existir una forma de combinar distintos árboles.

    De todos modos pondré un monográfico muy ligerito sobre rpart que servirá también para aprender a generar números aleatorios con R.

    Saludos.

  7. Tienes, al menos, tres extensiones «distintas». Entrecomillo «distintas» porque todas comparten un mismo principio y un mismo defecto (que hace que no se usen tanto en la práctica como se debiera).

    El principio es que si en lugar de construir un árbol construyes muchos (de una manera más o menos sofisticada) y luego los «promedias», mejora tu capacidad de predicción.

    La mala es que los estimadores así construidos dejan ya de ser «interpretables», esfumándose así una de las ventajas competitivas de los árboles.

    Sopésese todo.

    Los paquetes de R a los que echar un vistazo son randomForests y adabag.

    Un saludo,

    Carlos J. Gil Bellosta
    http://www.datanalytics.com

    P.D.: Raúl, tienes por ahí un mensaje mío…

  8. Inicie mi trabajo con CART pero en vista a la inestabilidad de las predicciones, en base a los RMSE, pense en trabajar con Random forest, que efectivamente me arroja valores menores de RMSE. Mi duda es: ¿Como expreso matematicamente la funcion resultante?

  9. Hola, ¿qué tal?

    En resumen, no puedes. Un «random forest» es un conjunto de árboles de
    regresión (el número depende de la configuración) a los que se asigna
    ciertos pesos. La función resultante es muy prolija para ser
    (d)escrita analíticamente.

    Es una de las «pegas» de estos modelos.

    Un saludo,

    Carlos J. Gil Bellosta
    http://www.datanalytics.com

  10. Pingback: datanalytics » La historia de CART (una segunda parte)

  11. Hola a todos!
    me resultó sumamente útil el aporte que todos hicieron sobre el tema. Recién comienzo a trabajar con árboles de decisión utilizando Markov para el estudio de costo-efectividad y realmente no se cuál de los paquetes de R es el más adecuado para trabajar.
    Gracias!!!

Los comentarios están cerrados.