Arboles de Decision

Vamos a ver arboles de Decision para clasificar por target(etiquetas), todo empieza desde el nodo raiz, y para decidir en que rama ir ( dividimos el set de datos), se evalua el feature(valor) de acuerdo a un criterio, ejemplo, un nodo podria tener el criterio si el tamaño de una perro es mayor o igual a 1 metro, entonces vas por una rama, pero si es menor a un metro vamos a otra rama, esto hasta llegar a un nodo hoja, cada nodo hoja tendra una etiqueta(target) que definira donde sera clasificado.

Datos que podrian Interesarle para comprender mejor:

Dale click a las imagenes para ver su informacion

Ejemplos de arboles de decision:

-ID3 [Quinlan, 1979]

-C4.5 [Quinlan, 1993]

-C5.0 (Última versión de Quinlan, propietaria. Mejora sobre C4.5)

-CART (similar a C4.5, soporta regresión, ver scikit-learn).

Arboles De Decision: Ventajas

-Las ventajas de Arboles de Decision en la clasificicacioin, es que podemos interpretar y entender como hizo la clasificacion, es decir como eligio a partir de un atributo o atributos que rama eligio y finalmente en que nodo hoja cayo clasificado. Por eso se le dice aveces que es una caja blanca ya que podemos entender como hizo la clasificacion, cosa que si fuera otro algoritmo de Machine Learning es complicado verlo, Ejemplo Redes Neuronales, es complico ver como hizo la clasificacion, ya que las neuronas, los pesos, las capas su interaccion para lograr la clasificacion no es algo facil de interpretar o entender.

-Funcionan con datos numericos o categoricos.

-Requieren poca preparacion de los datos, a diferencia de knn o una red neuronal donde se necesita normalizar los datos numericos, aca no es importante eso, ya que solo debemos evaluar el valor, no importa su escala, ya que solo importa splitear el set de datos de acuerdo al valor en el nodo

-Buena Performance en Dataset grandes

-Ayudan a la seleccion de Features, si un feature aparece mas arriba del arbol de decision signfica que es un feature importante, pero si no aparece signifcia que no es tan importante, concluimos nos da pistas de la importancia de los features, en las librerias hay funciones que te dicen la importancia de cada feature.

Arboles de Decision: Limitaciones

Encontrar el arbol optimo es un problema NP-complete (Conjuntos de problemas en el que podemos comprobar en tiempo razonable si una respuesta al problema es correcto o no), esto se hace con un algoritmo greedy para encontrar un optimo local

-Arboles demasiado complejo pueden llevar a un overfitting, ya sea porque el arbol es muy profundo, que hila fino con los split, ademas de hacer tantas divisiones, llegando a nodos hojas que tiene uno o pocos datos que los representen, entonces esos arboles que son muy complejos pueden ocasionar un overfitting, esto se logra cambiando algun hiperparametro del arbol, o haciendole una poda al arbol, que sea mas simple y que generalice mejor nuevos puntos

ID3

Es el primer algoritmo de arbol de decision de 1979, que es un algoritmo de tipo greedy, es decir,

-Ene cada paso realiza el mejor split en dos

-Que elige el mejor feature que nos da mayor ganancia de informacion, para splitear y llegar a nodos hojas de clase.

-Esto se repite recursivamente con el conjunto de datos acotado que vaya quedando en cada nodoEjmplo Si en el primer nodo quedo que el atributo de mayor ganancia era el tamaño, entonces, y se hizo en el nodo la division de que tamaño es mayor o igual a un metro o menor a un metro, y en el nodo de tamaño menor a un metro solo me van a quedar datos con esa condicion y ahi se va a evaluar cual de los otros atributos que tenga mi setdatos menos el que deje en un nodo mas arriba de este( tamaño) tiene la mayor ganancia de informacion, que es la ganacia, la ganacia es la entropia del feature, mientras tenga menor entropia con respecto a los otros features, este sera de mayor ganacia.

-Es solo par atributos categoricos, y esta version no permite datos numericos

Ejemplo:Problema de Clasificacion para saber si contratamos o no , en base a estos atributos.

Ahora vamos a calcular la Entropia del set de datos:

Entropia del set de datos de un feature en ID3
Entropia del set de datos de un feature en ID3

Calculamos probabilidad de si y no, P(si)=5/8 y P(no)=3/8 ” cantidad un conjunto / cantidad al total” (-1)*(5/8*((log5/8)/log2)-3/8((log3/8)/log2)=0.424+ 0.5306=0.9544

Calculo de Ganacia del Atributo(feature)Presencia

Calculo de Ganancia de informacion en ID3
Calculo de Ganancia de informacion en ID3

Lo que se hizo fue contar las veces que el atributo Presencia dijo que si y no a la clase contratado, ahi vemos que el dato buena, tiene de feature presencia buena 4 si y 0 no,

Vio h [4/4,0/4] = observar la entropia es minima osea la dispersion esta solo del lado del si. Entonces entropia igual a 0.

con h[0/2, 2/2]=0 observar que la entropia es minima osea la dispersion esta solo del lado del no. entonces entropia 0.

con h[1/2, 1/2]=1 la entropia es maxima ya que se distribujye en los dos de igual manera.

Entropia del feature presencia H(presencia)=p(buena sobre el total)*entropia buena+ p(mala sobre el total)*entropiamala +p(regular sobre el total)*entropiaregular

H(presencia)=4/8*(0) + 2/8*(0) + 2/8*(1)=0.25

calculo de ganacia de informacion del atributo presencia(feature), haciendo un split del atributo(feature) presencia como la entropia del conjunto de datos – entropia de presencia: GI(presencia)=0.9544-0.25=0.7044

Calculo de Ganancia informacion del atributo estudio:

Calculo de Ganancia de informacion en ID3
Calculo de Ganancia de informacion en ID3

solo voy hacer el H(Estudios=Univer)=3/5*((log3/5)/log2) + 2/5*((log2/5)/log2)=0.442+0.5287=0.971

Vemos que la Ganancia de informacion de Presencia es mayor que la ganacia de informacion de Estudios.

Ganancia de Informacion del Atributo Experiencia

Calculo de Ganancia de informacion en ID3
Calculo de Ganancia de informacion en ID3

Entonces el Feature que tiene la menor Entropia y por lo tanto mayor Ganacia de Informacion es el feature Presencia. entonces haremos el primer split por el atributo presencia

Arbol de clasificacion ID3
Arbol de clasificacion ID3

Vemos que por ser el de mayor ganancia, feature presencia sera nodo raiz, y va a preguntar sobre el tipo de presencia, se evaluara si llegamos a un nodo hoja o si seguimos spliteando, si la presencia es buena, vemos que clase ( de si va hacer o no contratado ) tiene una probabilidad 1 si, es decir si alguien tiene presencia buena, sera contratado, como es probalidad 1, llegamos a un nodo hoja, cuando preguntamos por presencia y es mala, sera de clase no contratado, con probabilidad 1 osea llegamos a otro nodo hoja, finalmente preguntamos porRegular, y tenemos que probabilidad de si y no es 1/2 por lo tanto vamos a seguir, ya que no definimos a que clase pertenecera las personas con presencia regular. Por lo tanto tenemos que splitear por otro atributo pero acotado a presencia regular( ver grafico de abajo) , este atributo tiene que ser uno que no hallamos usado y que tenga mayor Ganancia de informacion.

Vemos los atributos acotados por la presencia regular en ID3, son las filas 7 y 8
Vemos los atributos acotados por la presencia regular en ID3, son las filas 7 y 8

Entonces spliteamos por Experiencia, si preguntamos por si experiencia es baja , entonces sera solamente de clase no contratado con probabilidad 1, encambio si preguntamos por experiencia media es de clase contratado si contratado con probablidad 1.

Arbol de clasificacion ID3
Arbol de clasificacion ID3

ID3 Cuidados

-Riego de Overfitting, esto pasa al realizar preguntas a todas las hojas hasta que tengan una sola clase , nos ajustamos demasiados al set de entrenamiento, Para eso usamos un hiperparametro llamado minbucket que indica la cantidad minima de datos que tiene un nodo hoja, por lo tanto con esa cantidad minima, evitamos que se splitee en ese nodo, por lo tanto , el arbol no tendra demasiada profundidad, como consecuencia de esto no se producira overfitting, lo ultimo , las hojas del arbol indican las probablidad de cada clase, esto se hace,P(clase)=numero de registros de la clase/ total de registros de las clases de nodo hoja. Ejemplo podamos el arbol hasta presencia.

Entonces preguntamos si la presencia es regular, como lo podamos ahi, vamos a tener la respuesta con probabilidad, probabilidad de contratado si igual 1/2 y probablidad de no contratado igual a 1/2, es decir no llegamos a que todos los nodos hojas tengas una sola clase.

Arbol de Decision: c4.5

-Sucesor de ID3, porque acepta atributos numericos(acordarse que el otro aceptaba atributos categoricos), ademas acpeta atributos faltantes, pueden tener pesos a los atributos, y por ultimo poda del arbol para evitar overfitting

Ejemplo: agregamos un feature numerico.

   el arbol de decision  c4.5 con  feature numerico
Agregamos al dataset un feature numerico para probar como funciona el arbol de decision c4.5

Como se splitea un feature numerico?

La idea es buscar el split que mas ganancia de informacion genere, en este caso el split de 27, es el que genear a una entropia mas baja osea 0 , por lo tanto su ganancia de informacion sera la mas alta. Veamos las cuentas.

H(edad <=25)=H(cantidad de contratados/total, cantiadd de no contrados / total)=H(0/1,1/1)=0 osea la entropia es minima.

H(edad > 25)=H(6/7, 1/7)=- 6/7*(log(6/7)/log2) + -1/7*(log(1/7)/log2)=(0.1906+ 0.401 )=0.5917

y la ganacia de informacion es es GI(edad)= entropia del set de datos – 0.5917

y la Gi(edad) split 27= maxima comparado con la anterior, por lo tanto este sera el numero para splitear con el atributo edad

Ensambles

Se dice que los mejores algoritmos de Machine learning son combinaciones de varios algoritmos, es decir ejemplo usamos varios tipos de arboles de decision, y promediamos sus precision, asi obtenemos una precesion mayor del cual tendriamos si fuera un solo algoritmo de Machine Learning

En la practica ensamblar varios algoritmos para ganar una precision que comparado con la precision de un algoritmo solo, es casi infima, ejemplo ganar una precision de 0.0001, en la prcatica es decir en produccion no es coveniente, ya que se tardaria mas tiempo en entrenar, predecir, y ademas se utilzarian mayores recursos.Por lo tanto en la practica es preferiable perder precision , y que todo ande lo mas optimo posible, ahora si el caso es una competencia ejemplo de Kaggle, entonces esos 0.0001 de precision son importantes, es la diferencia entre ganar o no el torneo, por lo tanto en esas competencias se ve mucho los ensambles entre varios algoritmo de Machine Learning.

Ensambles:Tipo Bagging

Se trata de aplicar el mismo clasificador n veces usando Boostrapping, boostrapping es cuando tomamos un subsample al azar del set de datos original con reemplazo con el mismo tamaño del dataset original, es decir, tendremos n subsamples con el mismo tamaño pero con datos repetidos dejando afuera algunos datos para que ningun clasificador vea todos los datos del dataset original, y con la precision de los n clasificadores lo promediamos para obtener una mejor precision.

Ensambles:Tipo Bagging
Ensambles:Tipo Bagging

Vemos como tenemos el dataset de entrenamiento, y aplicamos la tecnica boostrapping para encontrar subset de entrenamiento, despues seran procesador por el algoritmo de ML del cual tendremos un resultado, despues de hacer todo esto, existen tecnicas para promediar, una es por medio de votos, de estos votos hacemos el promedio

Ensambles:Tipo Bagging
Ensambles:Tipo Bagging

Aca vemos que utilizamos 3 clasificadores lineales, donde cada dataset de entrenamiento se le aplica la tecnica boostraping, la parte en azul muestra los clasificados positivamente, mientras que los de color rojo muestra los clasificados negativamente, en el box1 aplicamos un clasificador lineal vertical,que clasificia bien los positivos, pero en los negativos vemos que clasifica mal 3 azules.En el box 2 , vemos que clasifica mal en la parte positiva a tres puntos negativos,pero en su parte negativa clasifica bien los negativos.Por ultimo el box3 Tenemos un clasificador lineal horizontal, en su parte positiva clasifica mal un punto negativo, en su clase negativa vemos que clasifica mal dos positivos.

Ahora despues de utilizar los 3 clasificadores, hacemos el promedio de los resultados por votos,entonces combinamos los votos de cada clasificador que son la cantidad de veces que aparece los puntos clasificados en cada clasificador y se queda el mayor veces que aparece en cada clasificador,Ejemplo: box1 los tres puntos positivos en la parte de arriba estan clasificados negativamente(1voto negativo), pero en el box2 y box3 esos tres puntos azules estan clasificados azules(2 votos positivos) por lo tanto esos tres puntos seran positivos en el clasificador final porque gano por votos, teniendo encuentra la interseccion de sus fronteras. Y asi con los demas puntos . Y como vemos combinando los tres clasificadores logramos que clasificara correctamente este set de datos .

Ventajas del Bagging

Disminuye la posibilidad de overfitting, ya que al utilizar el metodo de Boostrap con reemplazo al set de datos de entrenamiento, logramos que tenga el mismo tamaño del set de entrenamiento original, pero con datos repetidos y con registros que quedan afuera, por lo tanto cada clasificador no vera el dataset de entrenamiento en totalidad, reduciendo la probabilidad de overfiting.

-Registros OOB( out of Bag) : Al utilizar el boostrap para entrenar los clasificadores, tendremos por cada entrenamiento , registros afuera que lo usaremos para ver la precision del algoritmo( como si fuera un set test)

Boosting

Se basa en entrenar con un algoritmo simple,analizar sus resultados, Entrenar otro algoritmo simple donde se den mayor peso a los resultados para los cuales el anterior tuvo peor performance. El resultado final es en base a un promedio ponderado

Boosting, nuestro clasificador mas simple que aproxima el salario(y) con un promedio de todos los salarios
Boosting, nuestro clasificador mas simple que aproxima el salario(y) con un promedio de todos los salarios

Boosting, nuestro clasificador(f0) mas simple que aproxima el salario con un promedio de todos los salarios, y calculamos su error con valor real de salario(y) – fo de cada uno de los datos.

Ahora agarramos otro clasificador simple y estimamos los y-f0, clasificando si son menor a 23 o mayores a 23, haciendo su promedio en cada caso.

Como vemos de esta forma vamos ajustando el valor, vemos que ahora tenemos un nuevo valor respecto a los regresores, de esta forma vamos aplicando mas algoritmo simples en este caso a y-f1

Entonces se genera un nuevo arbol para predecir lo que predijo mal el anterior,La profundidad de los arboles de booting son mucho menor que los Bagging. 13.33

Deja un comentario

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