Algoritmos

Algoritmos de clasificación

C4.5 es un algoritmo usado para generar un árbol de decision desarrollado por Ross Quinlan.¹ C4.5 es una extensión del algoritmo ID3 desarrollado anteriormente por Quinlan. Los árboles de decisión generador por C4.5 pueden ser usados para clasificación, y por esta razón, C4.5 está casi siempre referido como un clasificador estadístico.

Algoritmo

C4.5 construye árboles de decisión desde un grupo de datos de entrenamiento de la misma forma en que lo hace ID3, usando el concepto de entropía de información. Los datos de entrenamiento son un grupo ${\displaystyle S={s_{1},s_{2},...}}$ de ejemplos ya clasificados. Cada ejemplo ${\displaystyle s_{i}={x_{1},x_{2},...}}$ es un vector donde ${\displaystyle x_{1},x_{2},...}$ representan los atributos o características del ejemplo. Los datos de entrenamiento son aumentados con un vector ${\displaystyle C={c_{1},c_{2},...}}$ donde ${\displaystyle c_{1},c_{2},...}$ representan la clase a la que pertenece cada muestra.

En cada nodo del árbol, C4.5 elige un atributo de los datos que más eficazmente dividen el conjunto de muestras en subconjuntos enriquecidos en una clase u otra. Su criterio es el normalizado para ganancia de información (diferencia de entropía) que resulta en la elección de un atributo para dividir los datos. El atributo con la mayor ganancia de información normalizada se elige como parámetro de decisión. El algoritmo C4.5 divide recursivamente en sublistas más pequeñas.

Este algoritmo tiene unos pocos casos base.

• Todas las muestras en la lista pertenecen a la misma clase. Cuando esto sucede, simplemente crea un nodo de hoja para el árbol de decisión diciendo que elija esa clase.
• Ninguna de las características proporciona ninguna ganancia de información. En este caso, C4.5 crea un nodo de decisión más arriba del árbol utilizando el valor esperado de la clase.
• Instancia de la clase previamente no vista encontrada. Una vez más, C4.5 crea un nodo de decisión más arriba en el árbol con el valor esperado.

Pseudocódigo

En pseudocódigo, el algoritmo general para construir árboles de decisión es:²

1. Comprobar los casos base
2. Para cada atributo a
   1. Encontrar la ganancia de información normalizada de la división de a
3. Dejar que a_best sea el atributo con la ganancia de información normalizada más alta
4. Crear un nodo de decisión que divida a_best
5. Repetir en las sublistas obtenidas por división de a_best, y agregar estos nodos como hijos de nodo

Implementaciones

J48 es una implementación open source en lenguaje de programación Java del algoritmo C4.5 en la herramienta weka de minería de datos.

Mejoras desde el algoritmo ID3

En C4.5 se hicieron un número de mejoras a ID3. Algunas de ellas son:

• Manejo de ambos atributos continuos y discretos - A fin de manejar atributos continuos, C4.5 crea un umbral y luego se divide la lista en aquellos cuyo valor de atributo es superior al umbral y los que son menores o iguales a él.³
• Manejo de los datos de formación con valores de atributos faltantes - C4.5 permite valores de los atributos para ser marcado como? para faltantes. Los valores faltantes de los atributos simplemente no se usa en los cálculos de la ganancia y la entropía.
• Manejo de atributos con costos diferentes.
• Podando árboles después de la creación - C4.5 se remonta a través del árbol una vez que ha sido creado e intenta eliminar las ramas que no ayudan, reemplazándolos con los nodos de hoja.

Mejoras en Algoritmo C5.0/See5

Quinlan continuó con la creación del C5.0 y el See5 (C5.0 para Unix / Linux, See5 para Windows) con fines comerciales. C5.0 ofrece una serie de mejoras en el C4.5. Algunas de estas son:⁴

• Velocidad - C5.0 es significativamente más rápido que el C4.5 (varios órdenes de magnitud)
• El uso de memoria - C5.0 es más eficiente que el C4.5
• Árboles de decisión más pequeños - C5.0 obtiene resultados similares a C4.5 con árboles de decisión mucho más pequeños.
• Soporte para boosting - Boosting mejora los árboles y les da una mayor precisión.
• Ponderación - C5.0 le permite ponderar los distintos casos y tipos de errores de clasificación.
• Winnowing - una opción automática de C5.0 consiste en aplicar un algoritmo de clasificación (algoritmo Winnow) a los atributos para eliminar aquellos que sean de poca ayuda.

Los Fuentes de una versión para Linux de un único subproceso de C5.0 están disponibles bajo licencia GPL. También se encuentra disponible una implementacion del algoritmo en R.

C4.5 es una extensión del software del algoritmo ID3 básica diseñada por Quinlan para tratar los siguientes temas no tratados por ID3:

• Evitar el sobreajuste de los datos
  • La determinación de la profundidad a crecer un árbol de decisión.
• la poda de error reducida.
• Regla posterior a la poda.
• Manejo de atributos continuos.
  • por ejemplo, temperatura
• La elección de una medida de la selección atributo apropiado.
• Manejo de datos de entrenamiento con la falta de valores de atributo.
• Manejo de atributos con diferentes costos.
• La mejora de la eficiencia computacional.

Se instala para su uso en Grendel (grendel.icd.uregina.ca), pero puede ser configurado en un equipo local de la siguiente manera:

C4.5 Release 8 Instrucciones de instalación para UNIX

1. Descargar el código fuente C4.5.
2. Descomprimir el archivo:
   1. Tipo "tar xvzf c4.5r8.tar" (no se admite universalmente), o, alternativamente,
   2. Tipo "gunzip c4.5r8.tar.gz" para descomprimir el archivo gzip, y luego
      escribir "tar xvf c4.5r8.tar" para descomprimir el archivo tar.
3. Cambiar a ./R8/Src
4. Tipo de "hacer todo" para compilar los ejecutables.
5. Ponga los ejecutables en un subdirectorio "bin" e incluirlo en el camino para el uso de línea de comandos.

Páginas manuales

• C4.5 : utilizando el generador C4.5 árbol de decisión.
• verbosa C4.5 : la interpretación de salida generada por C4.5.

• c4.5rules : utilizando el generador de reglas C4.5.
• c4.5rules detallados : salida interpretar generada por c4.5rules.

• consulte : utiliza un árbol de decisión para clasificar los artículos.
• consultr : utiliza un conjunto de reglas para clasificar objetos.

Ejemplos

Haga clic en los siguientes enlaces para ejemplos de uso C4.5:

• Ejemplo 1 - Golf
  • Un ejemplo sencillo, detallado de cómo C4.5 y el trabajo C4.5rules.
• Ejemplo 2 - Sunburn
  • El ejemplo quemaduras solares revisited.
• Ejemplo 3 - homónimos
• El uso avanzado de, y una aplicación práctica de, C4.5 y C4.5rules.

algoritmo ID3 es utilizado dentro del ámbito de la inteligencia artificial. Su uso se engloba en la búsqueda de hipótesis o reglas en él, dado un conjunto de ejemplos.

El conjunto de ejemplos deberá estar conformado por una serie de tuplas de valores, cada uno de ellos denominados atributos, en el que uno de ellos, ( el atributo a clasificar ) es el objetivo, el cual es de tipo binario ( positivo o negativo, sí o no, válido o inválido, etc. ).

De esta forma el algoritmo trata de obtener las hipótesis que clasifiquen ante nuevas instancias, si dicho ejemplo va a ser positivo o negativo.

ID3 realiza esta labor mediante la construcción de un árbol de decisión.

Los elementos son:

• Nodos: Los cuales contendrán atributos.
• Arcos: Los cuales contienen valores posibles del nodo padre.
• Hojas: Nodos que clasifican el ejemplo como positivo o negativo.

El algoritmo

Id3(Ejemplos, Atributo-objetivo, Atributos )
   Si todos los ejemplos son positivos devolver un nodo positivo
   Si todos los ejemplos son negativos devolver un nodo negativo
   Si Atributos está vacío devolver el voto mayoritario del valor del atributo objetivo en 
                                                                                  Ejemplos
   En otro caso
        Sea A Atributo el MEJOR de atributos
        Para cada v valor del atributo hacer
              Sea Ejemplos(v) el subconjunto de ejemplos cuyo valor de atributo A es v 
              Si Ejemplos(v) está vacío devolver un nodo con el voto mayoritario del
                                                              Atributo objetivo de Ejemplos
              Sino Devolver Id3(Ejemplos(v), Atributo-objetivo, Atributos/{A})

Obsérvese que la construcción del árbol se hace forma recursiva, siendo las tres primeras líneas y la penúltima los casos base que construyen los nodos hojas.

Elección del mejor atributo

La elección del mejor atributo se establece mediante la entropía. Eligiendo aquel que proporcione una mejor ganancia de información. La función elegida puede variar, pero en su forma más sencilla es como esta:

${\displaystyle -\left({\frac {\left\vert p\right\vert }{\left\vert d\right\vert }}\right)\log _{2}\left({\frac {\left\vert p\right\vert }{\left\vert d\right\vert }}\right)-\left({\frac {\left\vert n\right\vert }{\left\vert d\right\vert }}\right)\log _{2}\left({\frac {\left\vert n\right\vert }{\left\vert d\right\vert }}\right)}$

Donde p es el conjunto de los ejemplos positivos, n el de los negativos y d el total de ellos. Se debe establecer si el logaritmo es positivo o negativo

Un ejemplo

Ej.	Cielo	Temperatura	Humedad	Viento	Jugar tenis
D1	Sol	Alta	Alta	Débil	-
D2	Sol	Alta	Alta	Fuerte	-
D3	Nubes	Alta	Alta	Débil	+
D4	Lluvia	Suave	Alta	Débil	+
D5	Lluvia	Baja	Normal	Débil	+
D6	Lluvia	Baja	Normal	Fuerte	-
D7	Nubes	Baja	Normal	Fuerte	+
D8	Sol	Suave	Alta	Débil	-
D9	Sol	Baja	Normal	Débil	+
D10	Lluvia	Suave	Normal	Débil	+
D11	Sol	Suave	Normal	Fuerte	+
D12	Nubes	Suave	Alta	Fuerte	+
D13	Nubes	Alta	Normal	Débil	+
D14	Lluvia	Suave	Alta	Fuerte	-

En ese caso el árbol finalmente obtenido sería así:

                           Cielo
                          /   |  \
                         /    |   \
                Soleado /  Nublado \ Lluvia
                       /      |     \
                      /       +
               Humedad               Viento
              /    \                  |   \
             /      \                 |    \
        Alta/        \ Normal  Fuerte |     \ Débil
           /          \               |      \
          -           +               -       +

Algoritmo de ID3


En el aprendizaje del árbol de decisión, ID3 (Dichotomiser Iterativo 3) es un algoritmo usado para generar un árbol de decisión inventado por Ross Quinlan. ID3 es el precursor al algoritmo C4.5.

Algoritmo

El algoritmo ID3 se puede resumir así:

Tome todos los atributos no usados y cuente su entropía acerca de muestras de prueba
Elija el atributo para el cual la entropía es mínima (o, equivalentemente, la ganancia de información es máxima)
Haga el nodo que contiene ese atributo


El algoritmo es así:

ID3 (ejemplos, Target_Attribute, atributos)

Cree un nodo de la raíz para el árbol
Si todos los ejemplos son positivos, Vuelta la Raíz del árbol del nodo solo, con la etiqueta = +.
Si todos los ejemplos son negativos, Vuelta la Raíz del árbol del nodo solo, con la etiqueta =-.
Si el número de predecir atributos es vacío, entonces Vuelta la Raíz del árbol del nodo sola, con la etiqueta = la mayor parte de valor común del atributo objetivo en los ejemplos.
Por otra parte comience


A = El Atributo que mejor clasifica ejemplos.


El Árbol de decisión atribuye para la Raíz = A.


Para cada valor posible, de A,


Añada una nueva rama del árbol debajo de la Raíz, correspondiente a la prueba un =.


Deje a Ejemplos ser el subconjunto de ejemplos que tienen el valor para Un


Si los Ejemplos son vacío


Entonces debajo de esta nueva rama añaden un nodo de la hoja con la etiqueta = el valor objetivo más común en los ejemplos


Más debajo de esta nueva rama añaden el subárbol ID3 (Ejemplos , Target_Attribute, Atributos – un)
Final
Devuelva la raíz


La métrica ID3

Para evitar la sobreformación, los árboles de decisión más pequeños se deberían preferir sobre más grande. Este algoritmo por lo general produce pequeños árboles, pero no siempre produce el árbol más pequeño posible.

El paso de optimización hace el uso de la entropía de información:

Entropía

:

Donde:

es la entropía de información del juego;


es el número de valores diferentes del atributo en (la entropía se calcula para un atributo elegido)


es la frecuencia (la proporción) del valor en el juego


es el logaritmo binario


Una entropía de 0 identifica un juego absolutamente secreto.

La entropía es usada para determinar que nodo dividirse después en el algoritmo. Más alto la entropía, más alto el potencial para mejorar la clasificación aquí.

Ganancia

La ganancia se calcula para estimar la ganancia producida por una hendidura en un atributo:

:

Donde:

es la ganancia del juego después de una hendidura en el atributo


es la entropía de información del juego


es el número de valores diferentes del atributo en


es la frecuencia (la proporción) de los artículos que poseen como el valor para en


es el valor posible de


es un subconjunto de contener todos los artículos donde el valor de es


La ganancia cuantifica la mejora de la entropía dividiéndose en un atributo: más alto es mejor.