Mercadeo

Solo disponible en BuenasTareas
  • Páginas : 8 (1776 palabras )
  • Descarga(s) : 0
  • Publicado : 9 de marzo de 2011
Leer documento completo
Vista previa del texto
´ Tema 8. Arboles de Clasificaci´n o
Abdelmalik Moujahid, I˜aki Inza, Pedro Larra˜aga n n Departamento de Ciencias de la Computaci´n e Inteligencia Artificial o Universidad del Pa´s Vasco–Euskal Herriko Unibertsitatea ı

10.1 Introducci´n o En este tema se va a presentar el paradigma conocido como ´rbol de clasificaci´n. En a o el mismo, bas´ndose en un particionamiento recursivo del dominio dedefinici´n de a o las variables predictoras, se va a poder representar el conocimiento sobre el problema por medio de una estructura de ´rbol. El paradigma que se presenta en este tema se a conoce tambi´n bajo el nombre de ´rbol de decisi´n. e a o En la Secci´n 10.2 se van a presentar las ideas en las que se fundamenta el algoritmo o b´sico de inducci´n del modelo a partir de datos, para tratar losalgoritmos ID3 y a o C4.5 en las secciones 10.3 y 10.4 respectivamente. 10.2 El Algoritmo B´sico a Veamos a continuaci´n a introducir las ideas fundamentales del denominado algorito mo T DIDT (Top Down Induction of Decision Trees) el cual puede ser contemplado como uniformizador de la mayor´ de los algoritmos de inducci´n de ´rboles de clasiıa o a ficaci´n a partir de un conjunto de datosconteniendo patrones etiqueados. o El pseudoc´digo del algoritmo T DIDT puede contemplarse en la Figura 1. La idea o

D conjunto de N patrones etiquetados, cada uno de los cuales est´ caracterizado por n a variables predictoras X1 , . . . , Xn y la variable clase C ´ Output: Arbol de clasificaci´n o Begin TDIDT if todos los patrones de D pertenecen a la misma clase c then resultado de la inducci´n es unnodo simple (nodo hoja) etiquetado como c o else begin 1. Seleccionar la variable m´s informativa Xr con valores x1 , . . . , xnr a r r 2. Particionar D de acorde con los nr valores de Xr en D1 , . . . , Dnr 3. Construir nr sub´rboles T1 , . . . , Tnr para D1 , . . . , Dnr a 4. Unir Xr y los nr sub´rboles T1 , . . . , Tnr con los valores x1 , . . . , xnr a r r end endif End TDIDT

Input:Figura 1: Pseudoc´digo del algoritmo TDIDT o

subyacente al algoritmo T DIDT es que mientras que todos los patrones que se correspondan con una determinada rama del ´rbol de clasificaci´n no pertenezcan a a o una misma clase, se seleccione la variable que de entre las no seleccionadas en esa
1

rama sea la m´s informativa o la m´s id´nea con respecto de un criterio previamente a a o establecido.La elecci´n de esta variable sirve para expandir el ´rbol en tantas ramas o a como posibles valores toma dicha variable. La Figura 2 muestra gr´ficamente unos patrones caracterizados por 2 variables prea

Figura 2: Representaci´n en el plano de distintos patrones caracterizados por 2 variables predictoras o X1 y X2 y una variable clase C con dos posibles valores

dictoras denotadas por X1 y X2 yuna variable clase C con dos valores posibles denotados por 1 y 2. Una posible representaci´n del conocimiento subyacente al doo minio del ejemplo mostrado en la Figura 2 lo podemos ver por medio del ´rbol de a clasificaci´n de la Figura 3. o Tal y como puede verse en la Figura 3, las variables predictoras se van a representar en el ´rbol de clasificaci´n insertadas en un c´ a o ırculo, mientrasque las hojas del ´rbol a se representan por medio de un rect´ngulo en el cual se inserta el valor de la variable a clase que el ´rbol de clasificaci´n asigna a aquellos casos que bajan por las correspona o dientes ramas del ´rbol de clasificaci´n. a o El ´rbol de clasificaci´n de la Figura 3 tiene para todas las ramas una profundidad de a o 2, siendo este concepto de profundidad el que proporciona unaidea de la complejidad del ´rbol de clasificaci´n. a o Por otra parte en este ejemplo dir´ ıamos que no existe ruido en el sentido de que las hojas son puras al contener tan s´lo patrones de un determinado tipo respecto de o la variable clase. N´tese que esta es una situaci´n no habitual en un problema de o o modelizaci´n de una situaci´n real. o o Finalmente vamos a expresar el ´rbol de...
tracking img