1

MINERIA DE DATOS

Javier Hernndez Cceres, MSc

INGENIERIA DE SISTEMAS

UNIVERSIDAD DEL MAGDALENA

Santamarta

ColombiaTABLA DE CONTENIDO

31. Introduccin

31.1 Motivacin

41.2 Areas relacionadas

51.3 Componentes

61.4 Proceso de Descubrimiento

81.5 Metas de Minera de Datos

131.6 Aplicaciones

151.7 Retos

151.8 Otros aspectos relacionados

162. Aprendizaje

183. Aprendizaje Basado en Similaridades (SBL)

193.1 Induccin de rboles de Decisin

304. Aprendizaje de Reglas

375. Reglas de Asociacin

436.1 Probabilidad

496.2 Aprendizaje Bayesiano

566.3 Clasificador Bayesiano naive

SOFTWARE

1. WEKA. http://www.cs.waikato.ac.nz/~ml/weka/index.html2. APRIORI. http://fuzzy.cs.uni-magdeburg.de/~borgelt/software.html

3. Bases de datos para pruebas. http://ftp.ics.uci.edu/pub/machine-learning-databases/

ARTICULOS

1. From data mining to knowledge discovery in databases, Usama Fayyad, Gregory Piatetsky-Shapiro y Padhraic Smyth. http://dii.uchile.cl/~in65a/download/2001/fayyad.pdf2. Developing innovative applications in agriculture using data mining, Sally Jo Cunningham y Geoffrey Holmes. http://www.cs.waikato.ac.nz/~ml/publications.html1. Introduccin1.1 Motivacin

La tecnologa actual nos permite capturar y almacenar una gran cantidad de datos.

Tratar de encontrar patrones, tendencias y anomalas es uno de los grandes retos de vida moderna.

Cdigo de barras, automatizacin de procesos en general, avances tecnolgicos en almacenamiento de informacin y abaratamiento de precios en memoria, son algunos de los factores que han contribuido a la generacin msiva de datos.

Se ha estimado que la cantidad de datos almacenados en el mundo en bases de datos se duplica cada 20 meses.

Las tcnicas tradicionales de anlisis de informacin no han tenido un desarrollo equivalente.

La velocidad en que se almacenan datos es muy superior a la velocidad en que se analizan.

Existe un gran interes comercial por explotar los grandes volumenes de informacin almacenada.

Se cree que se est perdiendo una gran cantidad de informacin y conocimiento valioso que se podra extraer de los datos.

Al Descubrimiento de Conocimiento de Bases de Datos (KDD) a veces tambin se le conoce como minera de datos (Data Mining).

Sin embargo, muchos autores se refieren al proceso de minera de datos como el de la aplicacin de un algoritmo para extraer patrones de datos y a KDD al proceso completo (pre-procesamiento, minera, post-procesamiento).

Descubrimiento de Conocimiento en Bases de Datos:

Proceso de extraccin no trivial para identificar patrones que sean vlidos, novedosos, potencialmente tiles y entendibles, a partir de datos

Proceso: KDD involucra varios pasos y es iteractivo, al encontrar informacin til en los datos, se realizan mejores preguntas

Vlido: se utilizan principalmente los datos y se espera que los patrones puedan aplicarse en el futuro

Novedoso: desconocido con anterioridad

til: aplicable y cumpliento las metas del usuario

Entendible: que nos lleve a la comprensin, muchas veces medido por el tamao

A veces se hace una mezcla de medidas de utilidad, novedad, simplicidad y validez para establecer que tan interesantes pueden ser los patrones. Esta medida, generalmente est definida por el usuario, y es parte de los parmetros de operacin de los algoritmos de minera.

En este sentido, podemos decir que un patrn representa conocimiento si su medida de interesante rebasa un cierto umbral.

El proceso de KDD consiste en usar mtodos de minera de datos (algoritmos) para extraer (identificar) lo que se considera como conocimiento de acuerdo a la especificacin de ciertos parmetros usando una base de datos junto con pre-procesamientos y post-procesamientos.

Se estima que la extraccin de patrones (minera) de los datos ocupa solo el 15% - 20% del esfuerzo total del proceso de KDD.

Metas:

(i) Procesar automticamente grandes cantidades de datos crudos,

(ii) identificar los patrones ms significativos y relevantes, y

(iii) presentarlos como conocimiento apropiado para satisfacer las metas del usuario.

1.2 Areas relacionadas

Figure 1.1: Areas relacionadas de KDD.

KDD es un nuevo campo interdisciplinario que involucra investigacin de reas tales como:

Tecnologas de bases de datos y bodegas de datos: maneras eficientes de almacenar, accesar y manipular datos

Aprendizaje computacional, estadstica, computacin suave (redes neuronales, lgica difusa, algoritmos genticos, razonamiento probabilstico): desarrollo de tcnicas para extraer conocimiento a partir de datos

Reconocimiento de patrones: desarrollo de herramientas de clasificacin

Visualizacin: interfaz entre humanos y datos, y entre humanos y patrones

Cmputo de alto desempeo: mejora de desempeo de algoritmos debido a su complejidad y a la cantidad de datos

1.3 Componentes

Figure 1.2: Componentes de KDD.

Conocimiento del dominio y preferencias del usuario: Incluye el diccionario de datos, informacin adicional de las estructuras de los datos, restricciones entre campos, metas o preferencias del usuario, campos relevantes, listas de clases, jerarquas de generalizacin, modelos causales o funcionales, etc.

El objetivo del conocimiento del dominio es orientar y ayudar en la bsqueda de patrones interesantes (aunque a veces puede causar resultados contraproducentes).

Se tiene que hacer un balance entre eficiencia y completes del conocimiento.

Control del descubrimiento: Toma el conocimiento del dominio, lo interpreta y decide qu hacer (en la mayoria de los sistemas el control lo hace el usuario).

Interfaces: Con la base de datos y con el usuario

Foco de atencin: Especifica qu tablas, campos y registros accesar. Tiene que tener mecanismos de seleccin aleatoria de registros tomando muestras estadsticamente significativas, puede usar predicados para seleccionar un subconjunto de los registros que comparten cierta caracterstica, etc.

Algunas tcnicas para enfocar la atencin incluyen:

Agregacin: junta valores (por ejemplo, los ms bajos y los ms altos)

Particin de datos: en base a valores de atributos (por ejemplo, slo aquellos datos que tengan ciertos valores)

Proyeccin: ignorar algn(os) atributo(s)

Particin y proyeccin implican menos dimensiones. Agregacin y proyeccin implican menos dispersin.

Extraccin de patrones: Donde patrn se refiere a cualquier relacin entre los elementos de la base de datos. Pueden incluir medidadas de incertidumbre. Aqu se aplican una gran cantidad de algoritmos de aprendizaje y estadsticos.

Evaluacin: Un patrn es interesante en la medida que sea confiable, novedoso y til respecto al conocimiento y los objetivos del usuario. La evaluacin normalmente se le deja a los algoritmos de extraccin de patrones que generalmente estn basados en significancia estadstica (sin embargo, no es ni debe ser el nico criterio).

1.4 Proceso de Descubrimiento

El proceso de descubrimiento de conocimiento en bases de datos involucra varios pasos:

1. Entendimiento del dominio de aplicacin, el conocimiento relevante a usar y las metas del usuario. Esta es la tarea que puede llegar a consumir el mayor tiempo.

2. Seleccionar un conjunto o subconjunto de bases de datos, seleccionar y enfocar la bsqueda en subconjuntos de variables, y seleccionar muestras de datos (instancias) en donde realizar el proceso de descubrimiento.

Los datos tradicionalmente han sido tablas ASCII y la tendencia es utilizar manejadores de bases de datos y almacenes de datos que estn optimizados para realizar un proceso analtico.

3. Limpieza y prepocesamiento de datos, diseando una estrategia adecuada para manejar ruido, valores incompletos, secuencias de tiempo, casos extremos (si es necesario), etc.

4. Seleccin de la tarea de descubrimiento a realizar, por ejemplo, clasificacin, agrupamiento o clustering, regresin, etc.

5. Seleccin de l o de los algoritmos a utilizar

Figure 1.3: Proceso general de KDD.

6. Transformacin de datos al formato requirido por el algoritmo especfico de minera de datos

7. Llevar a cabo el proceso de minera de datos. Se buscan patrones que pueden expresarse como un modelo o simplemente que expresen dependencias de los datos.

El modelo encontrado depende de su funcin (e.g, clasificacin) y de su forma de representarlo (e.g., rboles de decisin, reglas, etc.)

Se tiene que especificar un criterio de preferencia para seleccionar un modelo dentro de un conjunto posible de modelos.

Se tiene que especificar la estrategia de bsqueda a utilizar (normalmente est predeterminada en el algoritmo de minera)

8. Interpretar los resultados y posiblemente regresar a los pasos anteriores.

Esto puede involucrar repetir el proceso, quizas con otros datos, otros algoritmos, otras metas y otras estrategias.

Este es un paso crucial en donde se requiere tener conocimiento del dominio.

La interpretacin puede beneficiarse de procesos de visualizacin, y sirve tambin para borrar patrones redundantes o irrelevantes.

9. Incorporar el conocimiento descubierto al sistema (normalmente para mejorarlo) lo cual puede incluir resolver conflictos potenciales con el conocimiento existente.

10. El conocimiento se obtiene para realizar acciones, ya sea incorporandolo dentro de un sistema de desempeo o simplemente para almacenarlo y reportarlo a las personas interesadas.

En este sentido, KDD implica un proceso interactivo e iterativo involucrando la aplicacin de varios algoritmos de minera de datos.

1.5 Metas de Minera de Datos

El proceso de minera involucra ajustar modelos o determinar patrones a partir de datos. Este ajuste normalmente es de tipo estadstico, en el sentido que se permite un cierto ruido o error dentro del modelo.

Los algoritmos de minera de datos realizan en general tareas de descripcin (de datos y patrones), de prediccin (de datos desconocidos) y de segmentacin (de datos). Otras, como anlisis de dependencias e identificacin de anomalias se pueden utilizar tanto para decripcin como para prediccin.

Descripcin: normalmente esada para annilisis preliminar de los datos (resumen, caractesticas de los datos, casos extremos, etc.). Con esto, el usuario se |emphsensibiliza con los datos y su estructura.

Busca derivar descripciones concisas de caractersticas de los datos (e.g., medias, desviaciones estandares, etc.).

La Prediccin la podemos dividir en dos: Clasificacin y Estimacin.

Clasificacin: Los datos son objetos caracterizados por atributos que pertenecen a diferentes clases (etiquetas discretas).

La meta es inducir un modelo para poder predecir una clase dados los valores de los atributos.

Se usan por ejemplo, rboles de decisin, reglas, anlisis de discriminantes, etc.

Estimacin o Regresin: las clases son continuas.

La meta es inducir un modelo para poder predecir el valor de la clase dados los valores de los atributos.

Se usan por ejemplo, rboles de regresin, regresin lineal, redes nueronales, kNN, etc.

Segmentacin: separacin de los datos en subgrupos o clases interesantes.

Las clases pueden ser exhaustivas y mutuamente exclusivas o jerrquicas y con traslapes.

Se puede utilizar con otras tcnicas de minera de datos: considerar cada subgrupo de datos por separado, etiquetarlos y utilizar un algoritmo de clasificacin.

Se usan algoritmos de clustering, SOM (self-organization maps), EM (expectation maximization), k-means, etc.

Normalmente el usuario tiene una buena capacidad de formar las clases y se han desarrollado herramientas visuales interactivas para ayudar al usuario.

Anlisis de dependencias: El valor de un elemento puede usarse para predecir el valor de otro. La dependencia puede ser probabilstica, puede definir una red de dependencias o puede ser funcional (leyes fsicas).

Tambin se ha enfocado a encontrar si existe una alta proporcin de valores de algunos atributos que ocurren con cierta medida de confianza junto con valores de otros atributos.

Se pueden utilizar redes bayesianas, redes causales, y reglas de asociacin.

Deteccin de desviaciones, casos extremos o anomalias: Detectar los cambios ms significativos en los datos con respecto a valores pasados o normales. Sirve para filtrar grandes volmenes de datos que son menos probables de ser interesantes. El problema est en determinar cundo una desviacin es significativa para ser de inters.

Componentes bsicas:

Las componentes bsicas de los mtodos de minera son:

1. Lenguaje de representacin del modelo: es muy importante que se sepan las suposiciones y restricciones en la representacin empleada para construir modelos.

2. Evaluacin del modelo: En cuanto a predictividad se basa en tcnicas de validacin cruzada (cross validation) en cuanto a calidad descriptiva del modelo se basan en principios como el de mxima verosimilitud (maximum likelihood) o en el principio de longitud de descripcin mnima o MDL (minimum description length).

3. Mtodo de bsqueda: se puede dividir en bsqueda de parmetros y bsqueda del modelo y determinan los criterios que se siguen para encontrar los modelos (hiptesis).

Algunas de las tcnicas ms comunes:

Arboles de decisin y reglas de clasificacin: realizan cortes sobre una variable (lo cual limita su expresividad, pero facilita su comprensin). Generalmente se usan tcnicas heursticas en su construccin (e.g., ID3, C4.5, CN2). Ver figura1.4.

Figure 1.4: Prediccin de Ozono en la Ciudad de Mxico.

Mtodos de clasificacin y regresiones no-lineales: tratan de ajustar combinaciones de funciones lineales y no-lineales, por ejemplo, redes nueronales (e.g., backpropagation), mtodos de splines adaptativos, etc. Ver figura1.5

Figure 1.5: Red Neuronal portotpica.

Mtodos basados en ejemplos prototpicos: se hacen aproximaciones en base a los ejemplos o casos ms conocidos (Examplar-based learning y Case-based resoning). El problema es cmo determinar una medida de similaridad adecuada. Ver figura1.6.

Figure 1.6: Aprendizaje basado en instancias.

Modelos grficos de dependencias probabilsticas: bsicamente redes bayesianas, en donde la evaluacin se basa en probabilidad y el encontrar el modelo en heursticas. Ver figura1.7.

Figure 1.7: Red bayesiana de seguros de coches.

Reglas de Asociacin: reglas que relacionan un conjunto de pares atributo-valor con otros pares atributo-valor. Por ejemplo:

Clustering: agrupan datos cuya distancia multidimensional intreclase es pequea e interclase es grande. Ver figura1.9.

Figure 1.9: Ejemplo de Clustering.

1.6 Aplicaciones

En la actualidad, existe una gran cantidad de aplicaciones, en reas tales como:

astronoma: clustering y clasificacin de cuerpos celestes

biologa molecular: prediccin de substancias cancergenas, genoma humana, etc.

aspectos climatolgicos: prediccin de tormentas, etc.

medicina: caracterizacin y prediccin de enfermedades

industria y manufactura: diagnstico de fallas

mercadotcnia: identificar clientes susceptibles de responder a ofertas de productos y servicios por correo, seleccin de sitios de tiendas, relaciones entre caractersticas personales y el tipo de productos comprados, etc.

inversin en casas de bolsa y banca: anlisis de clientes, aprobacin de prestamos, etc.

deteccin de fraudes y comportamientos inusuales: telefnicos, seguros, electricidad, etc.

anlisis de canastas de mercado para mejorar la organizacin de tiendas

Interpretacin de estadsticas en deportes

Web mining: anlisis de logs, anlisis de comportamiento de los usuarios de un sitio, personalizacin (hacer recomendaciones de acuerdo a caractersticas conocidas del usuario).

Recursos humanos: apoyo en la seleccin de empleados.

Banca: anlisis de clientes para otorgamiento de crditos

...

Criterios para seleccionar aplicaciones:

Criterios prcticos: (i) existe potencialmente un impacto significativo, (ii) no hay mtodos alternativos, (iii) existe soporte del cliente para su desarrollo, y (iv) no existen problemas de legalidad o violacin a informacin privilegiada

Criterios tcnicos: (i) existen suficientes datos, (ii) atributos relevantes, (iii) poco ruido en los datos, y (iv) conocimiento del dominio

Problemas de aplicacin:

Algunos de los problemas que pueden surgir al tratar de realizar aplicaciones de KDD son:

entrenamiento insuficiente

herramientas de soporte inadecuadas

abundancia de patrones

cambios rpidos de los datos en el tiempo

datos complejos (espaciales, imagenes, texto, audio, video)

Algunas Historias:

Clientes que compran paales tienden a comprar cerveza

Personas mayores (arriba de 65) no responden a ofertas de cuentas de retiro. Publicidad: es obvio! Consulto: es publicidad quien manda las ofertas!

Casi el 5% de clientes de un banco nacieron el 11 del noviembre de 1911. Razn: el campo fecha de nacimiento es obligatorio y la forma ms fcil para pasar al siguiente campo de captura es tecleando 111111

Clientes de nombre cortos en un banco tienden a ahorrar grandes cantidades de dinero y luego retirarlas. Razn: nombre orientales.

Los que compran coches rojos en Francia tienden a no pagar su prestamo de coche. Esto es casualidad? habla de la personalidad de los qye compran coches rojos? es irrelevante para un institucin de prestamo?

1.7 Retos

Volmen de datos (mega, giga y hasta terabytes)

Alta dimensionalidad

Sobreajuste (overfitting) de modelos en los datos

Evaluacin de significancia estadstica

Datos y conocimiento dinmicos (datos en BD y los patrones encontrados cambian continuamente)

Ruido, incertidumbre (tanto en datos como en conocimiento del dominio y en patrones descubiertos) y datos incompletos y/o esparsos

Relaciones complejas entre campos, jerarquas, relaciones entre atributos, nuevos atributos., etc.

Entendimiento de patrones

Incorporacin de conocimiento del dominio

Interaccin activa del usuario

Integracin con otros sistemas

Informacin redundante (puede ``descubrirse'' erroneamente)

1.8 Otros aspectos relacionados

La tendencia es proveer al usuario herramientas y facilidades para poder realizar KDD.

Desde este punto de vista, el proceso de KDD involucra interacciones complejas a travs del tiempo entre un humano y una base de datos usando un conjunto de herramientas heterogneas.

Dentro de las herramientas adicionales podemos citar:

Ayudas para analizar datos; entendimiento de la estructura, covertura y calidad de los datos

Herramientas para seleccionar herramientas, ajustarlas y refinar el modelo

Visualizacin de datos y de patrones

Integracin de modulos (la salida de uno sirva de entrada en otro)

Segmentacin (seleccin) y discretizacin de datos

Incorporar conocimiento del dominio

Interpretacin de salidas

Descubrimiento de la tarea a realizar

Limpieza de datos (sin eliminar datos interesantes)

Acoplamiento fuerte con bases de datos

Desarrollo de algoritmos ms eficientes, escalables y su paralelizacin

2. Aprendizaje

Posiblemente la caracterstica ms distintiva de la inteligencia humana es el aprendizaje.

Incluye:

adquisicin de conocimiento

desarrollo de habilidades a travs de instruccin y prctica

organizacin de conocimiento

descubrimiento de hechos

...

De la misma forma el aprendizaje computacional (ML) se encarga de estudiar y modelar computacionalmente los procesos de aprendizaje en sus diversas manifestaciones. En general, se busca contruir programas que mejoren automticamente con la experiencia.

Aprendizaje: cambios adaptivos en el sistema para hacer la misma tarea(s) de la misma problacin de una manera ms eficiente y efectiva la prxima vez [Simon, 83].

Aprendizaje: un programa de computadora se dice que aprende de experiencia E con respecto a una clase de tareas T y medida de desempeo D, si su desempeo en las tareas en T, medidas con D, mejoran con experiencia E [Mitchell, 97].

Muchas veces los objetivos dependen de la perspectiva que se les de:

ingenieril (resolver tareas)

simulacin cognitiva

anlisis terico

Instruir una mquina a realizar cierta tarea lleva mucho tiempo. ML trata de suavizar la carga mediante herramientas que pueden automatizarlo.

Desde el punto de vista de sistemas basados en conocimiento...

``...knowledge is currently acquired in a very painstaking way; individual computer scientists work with individual experts to explicate the expert's heuristics - the problem of knowledge acquisition is the critical bottleneck in artificial intelligence.'' Feigenbaum and McCorduck [Feigenbaum, pp. 79-80]

``Knowledge engineers have generally assumed that the procedural knowledge which drives an expert's skilled behavior can be elicited by dialogue. The findings of the past decade in brain science, cognitive psychology and commercial software do not support this idea. Evidence is lacking that skills, having once reached the ``automization'' stage, can be de-automized by dialogue so as to make their inner workings accessible to introspective report.'' Donald Michie [Michie, pp. 1]

Algunos ejemplos de aplicaciones que usan aprendizaje:

Sistemas de reconocimiento de voz (e.g., SPHINX, Lee 89),

Manejo de vehculos autnomos (ALVINN, Pomerleau 89)

Clasificacin de nuevas estructuras de astronoma (SkyCat, Fayyad et al. 95)

Aprendiendo a jugar Backgammon (TD-Gammon, Tesauro 92)

Aprendizaje tiene muchas reas relacionadas:

Inteligencia Artificial: manejo simblico, bsqueda, uso de conocimiento del dominio

Mtodos Bayesianos: teorema de Bayes, algoritmos para estimar valores de variables no observadas

Teora de complejidad computacional: cotas tericas de complejidad, nmero de ejemplos para aprender, etc.

Teora de informacin: medidas de entropa, principio de longitud de descripcin mnima.

Filosofa: principio de Occam, induccin

Psicologa y neurobiologa: modelos de aprendizaje y neuronales

Estadstica: caracterizacin de errores, niveles de confianza, pruebas.

Criterios de aprendizaje (Michie)

dbil: utiliza datos para mejorar su desempeo en nuevos datos

fuerte: se pueden ver explcitamente los conceptos generados

extra fuerte: se puede ver su mejora de una manera operacionalmente efectiva (i.e., permite al experto mejorar su desempeo al ver como el sistema de aprendizaje mejora el suyo)

3. Aprendizaje Basado en Similaridades (SBL)

AtributosClase

Peludo?Edad?Tamao?

siviejograndelen

nojovengrandeno len

sijovenmedianolen

siviejopequeono len

sijovenpequeono len

sijovengrandelen

nojovenpequeono len

noviejograndeno len

Arbol de decisin.

If Tamao = mediano Then len

If Tamao = grande and Peludo = si Then len

If Tamao = pequeo Then no len

If Tamao = grande and Peludo = no Then no len

3.1 Induccin de rboles de Decisin

Existe una serie de algoritmos desarrollados desde los principios de los 60's para la construccin de rboles de decisin. CLS (Hunt et al., 1966), ID3 (Quinlan, 1979), CART (Breiman et al., 1984), ACLS (Niblett et al., 1982), ASSISTANT (Cestnik et al., 1987), C4.5 (Quinlan, 1993), etc.

Muchos de estos desarrollos se han convertido en herramientas comerciales, por ejemplo, RuleMaster(1984), Ex-Tran(1984), Expert-Ease (1983), y C5/See5 (2000). Por otro lado, la gran mayoria de los ambientes de KDD incluyen alguna version de ID3 o de CART.

El aprendizaje de rboles de decisin es uno de los ms sencillos y fciles de implementar y a su vez de los ms poderosos.

Un rbol de decisin toma de entrada un objeto o situacin descrita por un conjunto de atributos y regresa una decisin ``verdadero/falso''.

En general pueden tener un rango ms amplio que simples funciones Booleanas, pero por simplicidad, consideremos primero slo estas.

Cada nodo interno corresponde a una prueba en el valor de uno de los atributos y las ramas estn etiquetadas con los posibles valores de la prueba.

Cada hoja especifica el valor de la clase.

Expresividad

Los rboles de decisin estn limitados a hablar de un solo objeto, osea, son escencialmente proposicionales, siendo cada prueba de atributo una proposicin.

Por lo mismo no podemos usar los rboles de decisin para expresar pruebas sobre dos o ms objetos diferentes, e.g. Claro que podramos aadir un atributo Booleano que se llame: RestMsBaratoCerca, pero es intratable para todas las combinaciones de atributos.

Por otro lado, los rboles de decisin son completamente expresivos dentro de la clase de lenguajes proposicionales. Osea que cualquier funcin Booleana puede ser descrita por un rbol de decisin.

Trivialmente, podemos tomar cada fila como un camino en la construccin de un rbol. Sin embargo, la tabla es exponencial en el nmero de atributos.

Para muchas funciones, los rboles son relativamente pequeos. Sin embargo, para otras funciones puede requerir un rbol exponencialmente grande. Por ejemplo, la funcin paridad (i.e., regresa 1 si la suma de 1's es par) o la funcin de mayora (regresa 1 si ms de la mitad de la entrada es un 1).

Para n atributos, hay 2n filas. Podemos considerar la salida como una funcin definida por 2n bits. Con esto hay 22n posibles funciones diferentes para n atributos (para 6 atributos, hay 2 x 1019).

Por lo mismo, tenemos que usar algn algoritmo ingenioso para encontrar una hiptesis consistente en un espacio de bsqueda tan grande.

Induccin de rboles de decisin a partir de ejemplos

Un ejemplo es descrito por los valores de los atributos y el valor del predicado meta. El valor del predicado meta se le llama la clasificacin del ejemplo.

Si el predicado es verdadero, entonces el ejemplo es positivo, sino el ejemplo es negativo.

En caso de existir ms clases, los ejemplos de una sola clase son positivos y el resto de los ejemplos son considerados negativos.

Cuando se tiene un conjunto de ejemplos (datos), normalmente se divide aleatoriamente en dos subconjuntos. Uno de entrenamiento (con el cual se construye la hiptesis) y otro de prueba (con el que se prueba la hiptesis encontrada).

Ms formalmente:

1. Junta una gran cantidad de ejemplos

2. Dividelos en dos conjuntos disjuntos: entrenamiento y prueba

3. Usa el algoritmo de aprendizaje para generar una hiptesis H

4. Mide el porcentage de clasificacin correcta de H en el conjunto de prueba

5. Repite los pasos 1 - 4 para diferentes tamaos de conjuntos de entrenamiento y diferentes conjuntos seleccionados aleatoriamente

Encontrar un rbol puede ser trivial (e.g., construir un camino por cada ejemplo). Sin embargo, no es bueno para predecir casos no vistos. El problema es que s'olo memoriza lo visto, por lo que no extrae ningn patrn de los ejemplos (por lo que no podemos esperar que extrapole).

El extraer un patrn significa el poder describir una gran cantidad de ejemplos en forma concisa. Esto tambin sigue un principio general en los algoritmos de induccin llamada: Ockham's razor (muchas veces escrito como Occam): dar preferencia a hiptesis ms simples que sean consistentes con todas las observaciones.

Encontrar el rbol ms pequeo es intratable, pero se pueden usar heursticas para encontrar rboles pequeos.

Idea: probar primero el atributo ms ``importante'' (el que diferencia mejor los ejemplos).

Despus que el primer atributo particiona los ejemplos, cada subconjunto es un nuevo problema de aprendizaje a su vez, con menos ejemplos y un atributo menos. Este proceso recursivo tiene 4 posibles resultados (ver tabla3.1):

1. Si existen ejemplos positivos y negativos, escoge el mejor atributo para particionarlos

2. Si todos los atributos restantes son positivos (o negativos), termina y regresa True (o False)

3. No quedan ejemplos (no ha sido observado un ejemplo con esa combinacin de atributos). Regresa un default en base a la clasificacin mayoritaria de su nodo padre

4. No hay ms atributos, pero seguimos con ejemplos positivos y negativos (i.e., existen ejemplos con la misma descripcin, pero diferente clasificacin). Posiblemente por ruido y/o falta de atributos y/o dominio no determinstico. Posible solucin: tomar la clasificacin mayoritaria

El rbol resultante no necesariamente es el ``correcto''. Para eso lo probamos con el conjunto de prueba.

Table 3.1: Algoritmo de construccin de rboles de decisin.

Table 3.2: Tabla de ejemplos para decidir si jugar o no golf.

AmbienteTemp.HumedadVientoClase

soleadoaltaaltanoN

soleadoaltaaltasiN

nubladoaltaaltanoP

lluviamediaaltanoP

lluviabajanormalnoP

lluviabajanormalsiN

nubladobajanormalsiP

soleadomediaaltanoN

soleadobajanormalnoP

luviamedianormalnoP

soleadomedianormalsiP

nubladomediaaltasiP

NubladoaltanormalnoP

LluviamediaaltasiN

Figure 3.1: Arbol de decisin para jugar Golf.

Aplicaciones:

Es la tcnica que posiblemente se ha usado ms en aplicaciones reales. Tres ejemplos:

GASOIL (1986): Diseo de sistemas de separacin de hidrocarburos en plataformas petroleras de BP, 2,800 reglas, 1 ao-hombre de tiempo de desarrollo, 0.1 de mantenimiento, mejor que expertos y ahorro de millones de dolares.

BMT (1990): Congfiguracin de equipo de proteccin de incendios en edificios, > 30,000 reglas, 9 aos hombre de desarrollo y 2 de mantenimiento (comparado con: MYCIN: 400 reglas, 100 aos-hombre de desarrollo o R1/XCON: 8,000 reglas, 180 aos-hombre de desarrollo y 30 de mantenimiento).

Aprendiendo a volar (1992): En lugar de construir un modelo preciso de la dinmica del sistema, se aprendi un mapeo adecuado entre el estado actual y la decisin de control correcta para volar un Cessna en un simulador de vuelo. Los datos se obtuvieron de 3 pilotos experimentados haciendo un plan de vuelo asignado 30 veces. Cada accin del piloto creaba un ejemplo. Se usaron 90,000 ejemplos descritos por 20 atributos. Se uso C4.5 que genero un rbol y se convirti a C. Se insert en el simulador y logro volar. Los resultados fueron sorprendentes en el sentido de que aparte de aprender a volar a veces tomaba decisiones mejores que las de sus ``maestros''

Cmo le hace?

La medida utilizada en ESCOGE-ATRIBUTO debe de tener su valor mximo cuando el atributo sea perfecto (i.e., discrimine perfectamente ejemplos positivos y negativos) y mnimo cuando el atributo no sea relevante.

Una posibilidad es basar la medida en la cantidad de informacin que da el atributo (basado en la teora de Shanon y Weaver '49).

La cantidad de informacin mide la (im)pureza en una coleccin arbitraria de ejemplos.

La cantidad de informacin recibida respecto a la ocurrencia de un evento es inversamente proporcional a la probabilidad de ocurrencia de dicho evento.

La informacin se mide en bits (un bit de informacin es suficiente para responder Verdadero/Falso a una pregunta cuya respuesta no se sabe).

Si se tienen vi posibles respuestas con probabilidades P(vi), el contenido de informacin es:

Nos representa el contenido promedio de informacin para los diferentes eventos (ver figura3.2).

Figure 3.2: Funcin de Entropa.

En el caso de los rboles de decisin queremos estimar las probabilidades de las respuestas. Esto se hace por la proporcin de ejemplos positivos y negativos.

Si se tienen p ejemplos positivos y n ejemplos negativos, entonces:

Un solo atributo normalmente no nos proporciona toda esta informacin, pero podemos estimar cuanta, viendo cuanta informacin necesitamos despus de utilizar ese atributo,

Cada atributo A, divide a los ejemplos del conjunto de entrenamiento en subconjuntos de acuerdo a los v valores del atributo.

Cada subconjutno Ei tiene pi ejemplos positivos y ni ejemplos negativos, por lo que para cada rama necesitamos:

cantidad de informacin para responder a una pregunta.

Un ejemplo aleatorio tiene el valor i-simo del atributo A con probabilidad:

Por lo que en promedio, despus de probar el atributo A, necesitamos:

La cantidad de informacin que ganamos al seleccionar un atributo est dada por:

La ganancia de A me dice el nmero de bits que ahorramos para responder a la pregunta de la clase de un ejemplo, dado que conocemos el valor del atributo A.

Dicho de otra forma, mide que tan bien un atributo separa a los ejemplos de entrenamiento de acuerdo a la clase meta.

La funcin evaluatoria escoge el atributo de mayor ganancia.

Por ejemplo, si calculamos la ganancia para el atributo para los datos de la tabla3.2 (asumimos que 0 log2(0) = 0):

Para Ambiente: soleado: p1=2,n1=3,I(p1,n1)=0.971 nublado: p2=4,n2=0,I(p2,n2)=0 lluvia: p3=3,n3=2,I(p3,n2)=0.971 Entropa(Ambiente) = Para Humedad: alta: p1=3,n1=4,I(p1,n1)=0.985 normal: p2=6,n2=1,I(p2,n2)=0.592 Entropa(Humedad) = 0.798

Para Viento: no: p1=6,n1=2,I(p1,n1)=0.811 si: p2=3,n2=3,I(p2,n2)=1.0 Entropa(Viento) = 0.892

Para Temperatura, Entropa(Temperatura) = 0.9111

Las ganancias son entonces: Ganancia(Ambiente) = 0.246 (MAX) Ganancia(Humedad) = 0.151 Ganancia(Viento) = 0.048 Ganancia(Temperatura) = 0.029

Por lo que ID3 escoge el atributo Ambiente como nodo raz y pocede a realizar el mismo proceso con los ejemplos de cada rama.

Para Ambiente tenemos tres subconjuntos: soleado (2+,3-), nublado (4+,0-), lluvioso (3+,2-). Para nublado, no tenemos que hacer nada, mas que asignarle la clase P.

Por ejemplo, para soleado hariamos el mismo proceso: Ganancia(Humedad) = 0.97 - [(3/5)0 + (2/5)0] = 0.97 (MAX) Ganancia(Temperatura) = 0.97 - [(2/5)0 + (2/5)1 + (1/5)0] = 0.570 Ganancia(Viento) = 0.97 - [(2/5)1 + (3/5)0.918] = 0.019

Uso del Arbol de Decisin

Con el rbol construido, podemos preguntar si esta bien jugar el sbado en la maana con ambiente soleado, temperatura alta, humedad alta y con viento, a lo cual el bol me responde que no.

ID3 sigue una estrategia hill-climbing, sin backtracking, incrementando en cada paso la complejidad del rbol. Utiliza todos los ejemplos, con los cuales estrae estadsticas y que lo hace ms robusto que un algoritmo incrementarl y por otro lado lo hace facilmente extendible para manejar ruido. Tiende a preferir construir rboles pequeos con atributos con ganancia de informacin alta cerca de la raz.

Criterio de Seleccin:

El criterio de seleccin basado en contenido de informacin tiende a favorecer atributos que tienen ms valores.

Por ejemplo, si un atributo tiene valores aleatorios o es un identificador nico de cada ejemplo (su clasificacin sera perfecta y su informacin despus al seleccionarlo sera 0 (ganancia mxima). Con esto el algoritmo bsico construye un rbol de un solo nivel o decision stump.

Posible solucin: rbol binario, dividiendo los posibles valores de los atributos en dos. Desventaja: rboles difciles de entender + computacionalmente caro (2nsubconjuntos para n valores).

Otra solucin: Para compensar esto se defini una razn de ganancia de informacin. Esto es dividir la ganancia de informacin entre la informacin de la divisin (la cantidad de informacin en los ejemplos que se dividi).

La informacin de la divisin (split information) se define como:

Esto es, la entropa de los datos con respecto a los valores del atributo (versus entropa con respecto a la clase).

E.g., si un atributo binario divide el conjunto de ejemplos en dos subconjuntos de igual tamao, el contenido de informacin de su divisin es 1. Mientras que un atributo que divide los ejemplos en 14 subconjuntos de tamao 1, sera: 14 (1/14 log2 (1/14)) = log2(1/14).

Sin embargo, no siempre funciona ya que puede sobrecompensar. Una prctica comn es usar el atributo de la razn de ganancia de informacin mxima dado que su ganancia de informacin es al menos tan grande como el promedio de ganacia de informacin del resto de los atributos.

Extensiones:

Hasta ahora hemos visto como funciona el algoritmo con atributos con valores discretos finitos y con datos sin ruido. Veremos ahora algunas extensiones para estos casos.

Atributos numricos:

Qu hacer si un atributo es numrico?

Lo que normalmente se hace es que se ordena el atributo numrico, se identifican ejemplos adyacentes que tengan valor de clase diferente y se consideran como candidatos los puntos mdeios de divisin del valor del atributo. A cada uno de estos se le calcula su ganancia de informacin.

Supongamos que en el ejemplo de la tabla 3.2 la temperatura toma valores enteros, y que los desplegamos en forma ordenada (de menor a mayor) juntando los valores iguales:

646568697071727580818385

PNPPPNNPNPPN

PP

Existen 8 posibles lugares de corte que separan el valor de la clase. Para cada uno de ellos se puede calcular su ganancia de informacin tomando el punto medio. Por ejemplo, si se toma el punto 71.5, Temperatura < 71.5 tiene 4 P y 2 N, mientras que Temperatura > 71.5 tiene 5 P y 3 N.

Cada posible particin entra en competencia con el resto de los atributos y el de mayor ganancia de informacin es el que se selecciona.

Esto implica que en el caso de atributos numricos, estos pueden aparecer varias veces en una rama de un rbol.

Para evitar ordenar ejemplos cada que se selecciona un atributo, se guarda con cada subconjunto el orden de acuerdo a un atributo numrico. Esto se puede hacer al principio y no volverlo a repetir.

Valores faltantes:

Una forma de tratar valores faltantes es como si fueran otra posible valor del atributo. Esto solo funciona si el valor faltante tiene un significado especial en algun sentido.

Ignorar los datos es demasiado drstico ya que algunas veces el valor del atributo puede no ser relevante para tomar una decisin.

Algunas propuestas para atacar el problema de atributos sin valor:

ASSISTANT (Kononenko et al.) usan Bayes para determinar la probabilidad de que un atributo asuma cierto valor.

El dato ms probable se puede usar, o dividir en valores fraccionarios

Usar el mismo mtodo para conocer los valores, cambiando columnas (i.e., el atributo se vuelve la clase) y luego se utiliza el rbol para determinar el valor.

Darle un valor de desconocido, sin embargo, esto incrementa el valor de ganacia en informacin.

Distruir los objetos con valores desconocidos entre los demas. En donde se calcula la ganacia en informacin como si pi fuera:

y una forma similar para ni.

La otra ``cara de la moneda'' es c'omo clasificar (dado que se tiene un rbol) un objeto con atributos desconocidos.

Idea: seguir todas las posibles ramas pero tomando en cuenta que algunas son ms probables que otras (tienen mas datos que la sorportan).

Al final se puede calcular el nivel de ``confianza'' para una clasificacin.

Si se sabe cierta informacin acerca del posible valor del atributo, se puede usar algn mtodo probabilstico.

Atributos o clases con diferente costo:

Puede darse el caso que los atributos tengan diferente costo (por ejemplo, puede ser ms costoso obtener su valor). Para esto se puede dividir la ganacia de informacin de cada atributo entre su costo, para favorecer atributos de menor costo.

En particular, se observ que la diferente funcin resultaba adecuada:

Otra alternativa (Nez, '88):

donde

determina la importancia relativa entre costo y ganancia de informacin.

Recientemente se han estado estudiado el crear rboles cuando el costo de (error en la) clasificacin es diferente (e.g., dianosticar cancer). Esto afecta en general el proceso de crecer y de podar (ver abajo) los rboles.

Ruido y ``Overfitting''

Algunas de las ventajas de ID3 es que es til en dominios con un alto grado de no homogeneidad (diferentes relaciones entre atributos en diferentes regiones del espacio de problemas) y alta dimensionalidad (muchos atributos).

En general, podemos hablar de que a pesar de que falte informacin relevante, se pueda construir un rbol con los atributos irrelevantes.

Con muchas posibles hiptesis se tiene que tener cuidado en no encontrar ``regularidades con poco sentido'' a partir de los datos. A este problema se le llama overfitting y afecta a todos los tipos de aprendizaje (i.e., no slo a los rboles de decisin).

Definicin: dado un espacio de hiptesis H, una hiptesis h ( H se dice que sobreajusta los datos de entrenamiento si existe otra hiptesis h ( H, tal que htiene errores ms pequeos que h' en los ejemplos de entrenamiento, pero h' tiene errores ms pequeos que h en toda la distribucin de ejemplos.

Uno de los problemas a los que se enfrentan los sistemas de aprendizaje, y que provocan el sobreajuste, es cuando los ejemplos de entrenamiento contienen ruido:

valores de atributos erroneos, subjetivos

clasificacin equivocada

valores desconocidos

Con ruido, se pueden tener dos ejemplos con los mismos valores de atributos, pero clase diferente. En presencia de rudo, el algoritmo bsico (ID3) tiende a construir rboles de decisin que son ms grandes de lo necesario, y no clasifican adecuadamente.

En el caso de rboles de decisin se tiene que decidir:

cmo trabajar con atributos inadecuados

cundo al aadir atributos extra no mejora la prediccin del rbol de decisin

En general, podemos hablar de dos mtodos utilizados para manejar ruido (basados en la condicin de terminacin):

pruning (o pre-pruning): cambiar el criterio de paro del rbol de decisin para ``podar'' ramas.

post-pruning: ``podar'' ramas una vez construdo el rbol.

Anlisis de Complejidad:

La complejidad de contruir un rbol es:

O(mn log n) + O(n (log n)2)

Donde n es el nmero de datos y m el nmero de atributos.

El primer trmino se refiere a construir un rbol de decisin sin considerar podado. El segundo trmino se refiere cuando realizamos podado. Esto es independiente de que los atributos sean continuos o no.

4. Aprendizaje de Reglas

El aprendizaje de reglas normalmente produce resultados ms fciles de entender.

Splitting vs. Covering

La estrategia bsica de la construccin de rboles de decisin se basa en splitting, esto es, dividir el conjunto de datos en subconjuntos considerando un atributo seleccionado por una heurstica particular. Aqui se consideran todas las clases dentro de la particin.

La idea bsica es aadir atributos al rbol que se esta construyendo buscando maximizar la separacin entre las clases.

La estrategia utilizada para aprender reglas, est basada en covering, esto es, encontrar condiciones de reglas (par atributo-valor) que cubra la mayor cantidad de ejemplos de una clase, y la menor del resto de las clases. Se considera el cubrir una sola clase.

La idea bsica es aadir pruebas a cada regla que se esta construyendo buscando maximizar covertura minimizando errores (ver figura4.1).

Figure 4.1: Splitting vs. Covering.

1R

Vamos a ver primero un sistema muy simple (1R) que es el equivalente a un decision stump.

La idea es hacer reglas que prueban un solo par atributo-valor. Se prueban todos los pares atributo-valor y se selecciona el que ocasione el menor nmero de errores.

Table 4.1: Algoritmo de 1R

En el caso de la tabla3.2 el nmero total de errores para el atributo Ambiente es 4, para Temperatura es 5, para Humedad es 4 y para Viento es 5.

Se rompe arbitrariamente los empates y nos quedariamos con las siguientes reglas:

If Ambiente = soleado Then Clase = N (cubre 5 y tiene 2 errores)

If Ambiente = nublado Then Clase = P (cubre 4 y tiene 0 errores)

If Ambiente = lluvioso Then Clase = P (cubre 5 y tiene 2 errores)

Los valores faltantes en 1R se tratan como un nuevo valor y los atributos continuos se hace una divisin simple.

Primero se ordenan los atributos con respecto a la clase (como lo vimos con rboles de decisin).

Se sugieren puntos de particin en cada lugar donde cambia la clase.

Si existen dos clases diferentes con el mismo valor, se mueve el punto de particin a un punto intermedio con el siguiente valor hacia arriba o abajo dependiendo de donde est la clase mayoritaria.

Un problema ms serio es que el algoritmo tendra a favorecer contruir reglas para cada una de las particiones, lo cual le da una clasificacin perfecta (pero muy poca prediccin futura).

Lo que se hace es que se exige que cada particin tenga un nmero mnimo de ejemplos de la clase mayoritaria.

Cuando hay clases adyacentes con la misma clase mayoritaria, estas se juntan.

Ejemplo:

6465686970717272757580818385

PNPPPNNPPPNPPN

Tomando los puntos intermedios sera: 64.5, 66.5, 70.5, 72, 77.5, 80.5 y 84.

Considerando los ejemplos de diferente clase, podemos mover la frontera de 72 a 73.5.

PNPPPNNPPPNPPN

Si tomamos al menos 3 elementos por particin (en resultados experimentales con varios dominios, este valor se fijo a 6):

PNPPPNNPPPNPPN

Si juntamos clases con la misma clase mayoritaria, nos queda:

PNPPPNNPPPNPPN

Lo cual nos dara una regla del tipo:

If Temperatura 77.5 Then Clase = N (cubre 4 y tiene 2 errores)

En la segunda regla se hizo una seleccin aleatoria, ya que se tenia un empate.

PRISM

Es un algoritmo bsico de aprendizaje de reglas que asume que no hay ruido en los datos (ver table4.2).

Sea t el nmero de ejemplos cubiertos por la regla y p el nmero de ejemplos positivos cubiertos por la regla. Lo que hace PRISM es aadir condiciones a reglas que maximicen la relacin p/t (relacin entre ejemplos positivos cubiertos y ejemplos cubiertos en total sea mayor).

Figure 4.2: Aprendizaje de Reglas

Table 5.2: Algoritmo de PRISM

Este algoritmo, como va eliminando los ejemplos que va cubriendo cada regla, las reglas que se construyen tienen que interpretarse en orden (las nuevas reglas se disean solo para cubrir los casos que faltan).

Reglas que dependen del su orden para su interpretacin se conocen como decision lists o listas de decisin.

Reglas que no dependen del orden son ms modulares, pero pueden producir varias clasificaciones o no predecir nada.

Con varias clasificaciones se puede seleccionar la regla que cubra ms ejemplos, y cuando no se tiene una clasificacin, escoger la clase mayoritaria.

Las reglas ordenadas son en general ms rpidas de producir ya que van reduciendo el nmero de ejemplos a considerar.

AQ

Desarrollado originalmente por Michalski (79) (reimplementado y mejorado por otros autores, AQ11, AQ15).

Su salida en un conjunto de reglas clasificatorios del tipo `if...then...'

Esto es til en aplicaciones de sistemas expertos basadas en reglas y normalmente son ms fciles de entender que los rboles de decisin.

El algoritmo de AQ, induce un conjunto de reglas de decisin, una para cada clase.

Cada regla es de la forma: if then , donde: es una combinacin Booleana de pruebas de atributos.

La prueba bsica de un atributo se llama selector (e.g., sangre = caliente).

Una conjuncin de selectores es llamado un complex (e.g., sangre = caliente & pelo = si),

Una disjuncin de complexes es llamado un cover (e.g., (sangre = caliente & pelo = si) OR leche = si).

Un complex vaco, cubre todos los ejemplos, mientras que un cover vaco no cubre ningn ejemplo.

Un cover es almacenado junto con el valor de la clase asociada (e.g., Si (sangre = caliente & pelo = si) OR leche = si Entonces clase = mamfero).

AQ selecciona un ejemplo de una clase (positivo) y toma selectores de ste, hasta que no se cubra ningn ejemplo de cualquier otra clase (negativo), para formar un complex. Cada complex encontrado es aadido al cover hasta que se cubran todos los ejemplos positivos (ver tabla4.3).

La operacin bsica del algoritmo es de generar un complex (una conjuncin de pruebas de atributos) que cubre (es satisfecha por) un subconjunto de los ejemplos de entrenamiento.

El complex forma la parte de condicin de la regla de produccin `if condicin then predice clase', donde clase es la clase ms comn en los ejemplos (de entrenamiento) que satisface la condicin. La bsqueda se hace especializando complexes candidatos hasta encontrar uno que cubra una gran cantidad de ejemplos de una sola clase y pocos de las demas clases.

La generacin de reglas se hace en etapas; cada etapa genera una sola regla y luego elimina los ejemplos de entrenamiento cubiertos por la regla. Este proceso se repite hasta que se encuentran suficientes reglas para cubrir todos los ejemplos de la clase escogida. Este proceso se repite para cada clase.

Para generar una sola regla, AQ primero selecciona un ejemplo ``semilla'' para la regla, y empieza con la regla ms general `if true then predice clase c' (i.e., `todos los ejemplos son de clase c'), donde c es la clase de la semilla.

Se exploran diferentes especializaciones de la regla hasta encontrar una que cubra slo ejemplos de la clase c y no cubra ejemplos de ninguna otra.

Se guardan varias ``mejores especializaciones hasta el momento'' las cuales se exploran en paralelo, por lo que AQ sigue una bsqueda tipo beam search en este espacio.

Al conjunto de soluciones exploradas se le llama star. AQ garantiza enconcontrar un conjunto completamente consistente de reglas con los datos de entrenamiento (si es que estas reglas existen).

Esta es una propiedad deseable en dominios sin ruido.

Table 4.3: Algoritmo AQ

Heurstica:

Para decidir que condicin es la ``mejor'', AQ tiene que evaluar:

qu condicin eliminar de star si su tamao excede un cierto valor mximo (dado por el usuario)

cul es la mejor condicin en el star final para usar como nueva regla

La heurstica particular depende de cada implementacin. Posibles heursticas son:

Sumar los ejemplos positivos cubiertos y los negativos excluidos (en caso de empate, preferir la ms corta).

Sumar el nmero de ejemplos clasificados correctamente dividido por el nmero total de ejemplos cubiertos.

Maximiza el nmero de ejemplos positivos cubiertos.

El ejemplo semilla se escoge de manera aleatoria y los ejemplos negativos se escogen de acuerdo a su distancia de la semilla (distancia = nmero de atributos con valores diferentes).

Valores desconocidos y numricos

Con valores desconocidos, en un algoritmo de covering lo mejor es hacer como si no aparean ninguna condicin (ignorarlos).

En este sentido, los algoritmos que aprenden decision lists tienen cierta ventaja, ya que ejemplos que parecen difciles al principio, se van quedando y al final se pueden resolver, en general, ms fcilmente.

Los atributos numricos se pueden tratar igual que con los rboles.

Construir reglas usando rboles

La idea es combinar una estrategia decovering con una de splitting.

Para construir una regla se construye un rbol podado (splitting) y la hoja con la mejor covertura se transforma en una regla. Una vez construida una regla se eliminan todos los ejemplos que cubre (covering) y se repite el proceso.

En lugar de construir un rbol completo, se construyen rboles parciales, expandiendo las hojas con mejores medidas de entropa.

5. Reglas de Asociacin

Las reglas de asociacin son parecidas a las reglas de clasificacin.

Se encuentran tambin usando un procedimiento de covering. Sin embargo, en el lado derecho de las reglas, puede aparecer cualquier par o pares atributo-valor.

Para encontrar ese tipo de reglas se debe de considerar cada posible combinacin de pares atributo-valor del lado derecho.

Para posteriormente podarlas usando covertura (nmero de instancias predichas correctamente) y precisin (proporcin de nmero de instancias a las cuales aplica la regla).

En reglas de asociacin, la covertura se llama soporte (support) y la precisin se llama confianza (confidence).

Se pueden leer como:

En realidad estamos interesados nicamente en reglas que tienen mucho soporte, por lo que buscamos (independientemente de que lado aparezcan), pares atributo-valor que cubran una gran cantidad de instancias.

A estos, se les llama item-sets y a cada par atributo-valor item.

Un ejemplo tpico de reglas de asociacin es el anlisis de la canasta de mercado. Bsicamente, encontrar asociaciones entre los productos de los clientes, las cuales pueden impactar a las estrategias mercadotcnicas.

Ya que tenemos todos los conjuntos, los transformamos en reglas con la confianza mnima requerida.

Algunos items producen ms de una regla y otros no producen ninguna.

Por ejemplo, si seguimos con los datos de la tabla3.2, el itemset:

humedad=normal, viento=no, clase=P

Puede producir las siguientes posibles reglas:

If humedad=normal and viento=no Then clase=P 4/4 If humedad=normal and clase=P Then viento=no 4/6 If viento=no and clase=P Then humedad=normal 4/6 If humedad=normal Then viento=no and clase=P 4/7 If viento=no Then clase=P and humedad=normal 4/8 If clase=P Then viento=no and humedad=normal 4/9 If true Then humedad=normal and viento=no and clase=P 4/12

Si pensamos en 100% de xito, entonces slo la primera regla cumple.

De hecho existen 58 reglas considerando la tabla completa que cubren al menos dos ejemplos con un 100% de exactitud (exaccuracy).

El proceso es mas o menos el siguiente y sigue dos pasos (Apriori, Agrawal et al. '94):

1. Genera todas los items sets con un elemento. Usa estos para generar los de dos elementos, y as sucesivamente.

Se toman todos los posibles pares que cumplen con las medidas mnimas de soporte. Esto permite ir eliminando posibles combinaciones ya que no todas se tienen que considerar.

2. Genera las reglas revisando que cumplan con el criterio mnimo de confianza.

Una observacin interesante, es que si una conjuncin de consecuentes de una regla cumple con los nivels mnimos de soporte y confianza, sus subconjuntos (consecuentes) tambin los cumplen.

Por el contrario, si alguno item no los cumple, no tiene caso considerar sus superconjuntos.

Esto da una forma de ir construyendo reglas, con un solo consecuente, y a partir de ellas construir de dos consecuentes y as sucesivamente.

Este mtodo hace una pasada por la base de datos cada para cada conjunto de items de diferente tamao.

El esfuerzo computacional depende principalmente de la covertura mnima requerida, y se lleva prcticamente todo en el primer paso.

El proceso de iteracin del primer paso se llama level-wise y va considerando los superconjuntos nivel por nivel.

Lo que se tiene es una propiedad anti-montona: si un conjunto no pasa una prueba, ninguno de sus subconjuntos la pasan.

Si un conjunto de items no pasa la prueba de soporte, ninguno de sus subconjuntos la pasan. Esto se aprovecha en la construccin de candidatos para no considerar todos.

Por ejemplo, consideremos la tabla5.1 con listas de compras de productos. La figura5.1 muestre este proceso con los datos de la tabla anterior.

Table 5.1: Datos de compras de productos.

id1p1,p2,p5

id2p2,p4

id3p2,p3

id4p1,p2,p4

id5p1,p3

id6p2,p3

id7p1,p3

id8p1,p2,p3,p5

id9p1,p2,p3

Figure 5.1: Generacin de candidatos por niveles. El primer nmero indica el producto y el nmero entre partesis las veces qu ocurre.

Una vez que tenemos los conjuntos de items, generar las reglas es relativamente sencillo.

Para cada conjunto l de items, genera todos sus subconjuntos.

Para cada subconjunto s ( l, genera una regla: s ( (l s) si:

Algunas mejoras:

Se han hecho algunas mejoras al algoritmo bsico de reglas de asociacin (Apriori) para hacerlo ms eficiente:

Usar tablas hash para reducir el tamao de los candidatos de los itemsets

Eliminar transacciones (elementos en la base de datos) que no contribuyan en superconjuntos a considerar

Dividir las transacciones en particiones disjuntas, evaluar itemsets locales y luego, en base a sus resultados, estimar los globales.

Hacer aproximaciones con muestreos en la lista de productos, para no tener que leer todos los datos

Evitar generar candidatos usando estructuras de datos alternativas, como por ejemplo, los FP-trees (Frequent Pattern tree).

Algunas extensiones:

Dentro de las extensiones principales, podemos citar:

1. Encontrar reglas de asociacin a diferentes niveles de abstraccin.

Normalmente se empieza con las clases superiores, y los resultados pueden servir para filtrar clases inferiores.

Por ejemplo, considerar reglas de asociacin sobre computadoras e impresoras, y luego sobre laptops y estaciones de trabajo, por un lado, y sobre impresoras laser y de punto por otro, etc.

Al proceder a las subclases se puede considerar:

un criterio de soporte uniforme

reduciendo el criterio para las subclases

considerar todas las subclases independientemente del criterio de soporte

tomando en cuenta el criterio de soporte de una de las superclases de un item o k superclases de k items

considerar items aunque el nivel de soporte de sus padres no cumplan con el criterio de soporte, pero que sea mayor que un cierto umbral.

Al encontrar reglas de asociacin a diferentes niveles de abstraccin es comn generar reglas redundantes o reglas que no nos dicen nada nuevo (e.g., la regla ms general, ya decia lo mismo), por lo que es necesario incorporar mecanismos de filtrado.

2. Encontrar reglas de asociacin combinando informacin de mltiples tablas o reglas de asociacin multidimensionales.

Los DataCubes pueden servir para encontrar reglas de asociacin multidimensionales.

3. Las reglas de asociacin, al igual que los rboles de decisin y las reglas de clasificacin que hemos visto, funcionan, en su forma original, con atributos discretos.

Al igual que en las otras tcnicas se han propuesto mecanismos para manjejar atributos continuos.

Los enfoques ms comunes son:

Discretizar antes de minar en rangos usando posiblemente jerarquas predefinidas.

Discretizar dinmicamente durante el proceso tratando de maximizar algn criterio de confianza o reduccin de longitud de reglas.

Por ejemplo, ACRS (Association Rule Clustering System), mapea atributos cuantitativos a una rejilla y luego utiliza clustering.

Primero asigna datos a ``contenedores'' delimitados por rangos (que despus pueden cambiar). Los esquemas ms comunes son: contendores del mismo tamao, contenedores con el mismo nmero de elementos, y contenedores con elementos uniformemente distribuidos.

Despus se encuentran reglas de asociacin utilizando los contenedores. Una vez que se tienen las reglas, stas se agrupan si forman rectngulos ms grandes dentro de la rejilla.

Discretizar utilizando informacin semntica, i.e., formar grupos con elementos cercanos (posiblemente haciendo clustering sobre los atributos). Una vez establecidos los clusters, encontrar las reglas de asociacin con esos clusters basados en distancias o similaridades.

Asociacin vs. Correlacin

El que se encuentre una regla de asociacin no necesariamente quiere decir que sea til.

Por ejemplo, si se analizan 10,000 compras, de las cuales 6,000 compraron videojuegos, 7,500 videos y 4,000 las dos, posiblemente se genere una regla: compra videojuegos => compra videos [soporte=4,000/10,000 = 40% y confianza=4,000/6,000 = 66%].

Sin embargo, el 75% de los clientes compran videos por lo que el comprar videojuegos reduce las posibilidades de comprar videos.

La ocurrencia de un itemset A es independiente de otro B si

En caso contrario, existe cierta dependencia o correlacin.

La correlacin entre dos eventos se define como:

Si es menor que 1, entonces la ocurrencia de uno decrece la ocurrencia del otro. Si es 1 son independientes y si es mayor que 1 la ocurrencia de uno favorece la ocurrencia de otro.

Con esto, se pueden encontrar reglas de asociacin correlacionadas. Se puede estimar si la correlacin es estadsticamente significativa usando una

Si un conjunto de elementos est correlacionado, cualquier superconjunto de este tambin lo est.

Esto puede ayudar a buscar los conjuntos mnimos correlacionados y construir a partir de ah sus superconjuntos.

Uso de restricciones

Se pueden usar restricciones sobre los tipos de datos, jerarquas, o formas posibles de las reglas a encontrar para reducir el espacio de bsqueda.

Las restricciones pueden ser: (i) antimontonas (si un conjunto no satisface una condicin, entonces tampoco la satisfacen sus superconjuntos), (ii) montonas (si un conjunto satisface una restriccin, entonces tambin la satisfacen todos sus superconjuntos), (iii) sucintas (succint) (podemos enumerar todos los conjuntos que satisfacen una restriccin), (iv) convertibles (podemos converir una restriccin a alguna de las clases anteriores), y (v) no convertibles.

Reglas de Asociacin, de Clasificacin y rboles de Decisin.

La tabla5.2 muestra una comparacin entre reglas de asociacin y de clasificacin.

Table 5.2: Reglas de Asociacin vs. Reglas de Clasificacin

Exploracin de dependenciasvs.Prediccin enfocada

Diferentes combinaciones devs.Predice un atributo (clase)

atributos dependientes ea partir de otros

independientes

Bsqueda completa (todas lasvs.bsqueda heurstica (se encuentra

reglas encontradas)un subconjunto de reglas)

Los rboles usan heurstica de evaluacin sobre un atributo, estan basados en splitting, y normalmente realizan sobreajuste seguido de podado.

Las reglas de clasificacin utilizan una heurstica de evaluacin de condicin (par atributo-valor), estan basados en covering, y utilizan sobre todo criterios de paro (y a veces sobreajuste y podado).

Las reglas de asociacin se basan en medidas de confianza y soporte, consideran cualquier conjunto de atributos con cualquier otro conjunto de atributos.

6.1 Probabilidad

Interpretaciones de Probabilidad

Existen diferentes interpretaciones de probabilidad, las ms comunes son:

Clsica: P(A)=N(A)/N

Frecuencia relativa: Subjetiva: P(A) = ``creencia en A'' (factor de apuesta)

Probabilidad

Definicin: Dado un experimento E y el espacio de muestreo S respectivo, a cada evento A le asociamos un nmero real P(A), el cual es la probabilidad de A y satisface las siguientes propiedades:

1.

2. P(S)=1

3.

, si A y B mutuamente exclusivos

Teorema 1:

Teorema 2:

Teorema 3:

Probabilidad Condicional

Si A y B son dos eventos en S, la probabilidad de que ocurra A dado que ocurri el evento B es la probabilidad condicional de A dado B, y se denota

.

La probabilidad condicional por definicin es:

, dado P(B) > 0

Ejemplo:

Para un dado, si s que cay impar, cul es la probabilidad de 3?

Similarmente:

De donde:

Esta expresin se conoce como el Teorema de Bayes, que en su forma ms general es:

El denominador se le conoce como el teorema de la probabilidad total.

Teorema 4:

Si B1,B2,...,Bk representan una particin (exclusivos, exhaustivos y mayores a cero) de S, y A es un evento respecto a S, entonces la probabilidad de A la podemos escribir como:

Eventos independientes

Dos eventos, A y B, son independientes si la ocurrencia de uno no tiene que ver con la ocurrencia de otro.

Por definicin, A es independiente de B si y slo si:

Esto implica que:

Independientes es diferente a mutuamente exclusivos.

Independencia condicional

Un evento A es condicionalmente independiente de otro B dado un tercer evento C, si el conocer C hace que A y B sean independientes. Es decir, si conozco C, B no tiene influencia en A. Esto es:

Ejemplo:

A - regar el jardn

B - prediccin del clima

C - lluvia

De la definicon de probabilidad condicional, podemos obtener una expreson para evaluar la probabilidad conjunta de Neventos:

Variables Aleatorias

Si a cada posible evento A le asignamos un valor numrico real, X(A), obtenemos una variable aleatoria. A cada valor de la variable le corresponde una probabilidad, P(X=k).

Las variables aleatorias pueden ser de dos tipos: discretas y continuas. Nosotros nos enfocaremos a variables discretas.

Ejemplos de variables aleatorias discretas: lanzar una moneda, lanzar un dado, nmero de fallas antes de darle al blanco.

Funcin acumulativa de probabilidad

Para una variable aleatoria X, se define la funcin acumulativa de probabilidad como la probabilidad de que la variable aleatoria sea menor a un valor x:

Es decir, corresponde a la sumatoria de la funcin de probabilidad de -( a x:

Propiedades:

1.

2.

3.

4.

Estadsticas de una variable aleatoria

Valores caractersticos de una variable aleatoria:

Modo: valor de probabilidad mxima

Media: valor medio (divide el rea en 2 partes iguales)

Momentos

promedio (valor esperado o primer momento):

valor promedio-cuadrado (segundo momento):

momento N:

Momentos ``centrales''

varianza:

desviacin estandar:

Variables Aleatorias de 2-Dimensiones

Definicin: Dado un experimento E con espacio de muestreo S. Si X y Y son dos funciones que le asignan nmeros reales a cada resultado posible, entonces (X,Y) es una variable aleatoria bidimensional.

Dadas dos variables aleatorias (discretas), X, Y, deben satisfacer lo siguiente:

1.

2.

Ejemplos: nmero de artculos terminados en dos lneas de produccin, nmero de pacientes con cancer y nmero de fumadores, etc.

Probabilidad marginal

Es la probabilidad particular de una de las variables dada un variable aleatoria bidimensional, y se define como:

Probabilidad condicional

Dada la probabilidad conjunta y marginal, la probabilidad condicional se define como:

Variables independientes

Dos variables aleatorias son independientes si su probabilidad conjunta es igual al producto de las marginales, esto es:

P(xi, yj) = P(xi) P(yj), ( (i, j)

Correlacin

El coeficiente de correlacin (() denota el grado de linearidad entre dos variables aleatorias y se define como:

La correlacin est dentro del intervalo: (([-1, 1], donde un valor de 0 indica no-orrelacionadas, y un valor de -1 1 indica una relacin lineal.

Independencia no-correlacin (pero no viceversa).

Distribucin Binomial

Una distribucin binomial de la probabilidad de observar r eventos (e.g., soles) de n muestras independientes con dos posibles resultados (e.g., tirar monedas).

El valor esperado es:

La varianza es: Var(x) = np(1 - p)

La desviacin estandar es:

Si n es grande, se aproxima a una distribucin Normal

Distribucin Normal o Gaussiana

El valor esperado es:

La varianza es:

La desviacin estandar es:

El Teorema Central del Lmite dice que la suma de un nmero grande de variables aleatorias independientes identicamente distribuidas siguen una distribucin Normal.

6.2 Aprendizaje Bayesiano

Aprendizaje Bayesiano es importante por:

ser prctico

provee un enfoque de comprensin (y diseo) de otros algoritmos

Algunas caractersticas:

Cada nuevo ejemplo puede aumentar o disminuir la estimacin de una hiptesis (flexibilidad - incrementalidad)

Conocimiento a priori se puede combinar con datos para determinar la probabilidad de las hiptesis

Da resultados con probabilidades asociadas

Puede clasificar combinando las predicciones de varias hiptesis

Sirve de estandar de comparacin de otros algoritmos

Problemas:

Se requieren conocer muchas probabilidades

Es computacionalmente caro (depende linealmente del nmero de hiptesis)

Lo que normalmente se quiere saber en aprendizaje es cul es la mejor hiptesis (ms probable) dados los datos.

Si denotamos P(D) como la probabilidad a priori de los datos (i.e., cuales datos son ms probables que otros), P(D|h) la probabilidad de los datos dada una hiptesis, lo que queremos estimar es: P(h|D), la probabilidad posterior de h dados los datos. Esto lo podemos estimar con Bayes.

Teorema de Bayes:

Para estimar la hiptesis ms probable o MAP (maximum a posteriori hypothesis):

Ya que P(D) es una constante independiente de h.

Si asumimos que todas las hiptesis son igualmente probables, entonces nos queda la hiptesis de mxima verosimilitud o ML (maximum likelihood):

Ejemplo:

Se tienen dos hiptesis: el paciente tiene un tipo de cancer o no tiene cancer.

Sabemos que solo el 0.008% de la poblacin tiene ese tipo de cancer. La prueba sobre cancer no es infalible, y nos da resultados positivos correctos en el 98% de los casos y nos da resultados negativos correctos en el 97% de los casos.

Esto es: P(cancer) = 0.008

Si a un paciente le dieron un resultado positivo en la pruebra:

Que al normalizar, nos da:

Por lo que sigue siendo mas probable que no tenga cancer.

Una forma de implantar un algoritmo Bayesiano es calculando para todas las posibles hiptesis su

y quedandose con la de mayor probabilidad. Obviamente esto es imprctico cuando se tienen muchas posibles hiptesis.

Tambin para hacerlo, necesitamos especificar los valores para P(h) y para P(D|h).

Si asumimos que no hay ruido y que todas las hiptesis son igualmente probables

sii D es consistente con h. Esto es:

donde, VSH,D es el subconjunto de hiptesis de H que es consistente con D (su espacio de versiones).

Por lo mismo, toda hiptesis consistente es una hiptesis MAP.

Lo que quiere decir, es que cualquier sistema de aprendizaje que nos de hiptesis consistentes, asumiendo que no hay ruido y que todas las hiptesis son igualmente probables, nos est dando hiptesis MAP.

Si tenemos un sistema de aprendizaje de general a especfico (o al revs) que busca especializaciones ms generales (o generalizaciones ms especficas), lo podemos caracterizar asumiendo que las hiptesis ms generales (o especficas) son ms probables que las otras.

En general, podemos caracterizar varios algoritmos de aprendizaje con un enfoque Bayesiano, al caracterizar sus distribuciones de probabilidad P(h) y P(D|h) .

Variables Continuas y Ruido

Los mtodos ms usados para buscar funciones con variables continuas a partir de datos con cierto ruido, son regresiones lneales, ajustes de polinomios y redes nueronales.

La idea es aprender funciones lo ms cercanas a f, en donde los datos estn descritos por: di = f(xi) + ei, donde f(xi) es la funcin sin ruido y ei es una variable aleatoria representando el error.

Asumimos que la distribucin de probabilidad de ei est dada por una distribucin Gaussiana (normal) con media cero.

De nuevo lo que queremos es encontrar la hiptesis ms probable:

Asumiento que los datos son independientes entre s dado h, la probabilidad se puede expresar como el producto de varias p(di | h) para cada dato:

Como el ruido sigue una distribucin Gaussiana con media cero y varianza , cada di debe de seguir la misma distribucin pero ahora centrada alrededor de f(xi).

Podemos maximizar tomando su logartimo (dado que es una funcin monotnica creciente):

Eliminando el primer trmino (que no depende de h):

Que es igual a minimizar lo mismo con el signo contrario. Al cambiar signo y eliminar constantes que no dependen de h nos queda:

Lo que nos dice que la hiptesis de mxima verosimilitud es la que minimiza la suma de los errores al cuadrado entre los datos observados (di) y los datos predichos (h(xi)), siempre y cuando el error siga una distribucin Normal con media cero.

Todo esto asume que el error est dado nicamente en el valor meta y no en los atributos que describen la meta.

Aprendiendo a Predecir Probabilidades

Otra aplicacin comn es querer aprender una funcin de probabilidad sobre un funcin que tiene dos posibles resultados (e.g., cul es la probabilidad de que tenga X enfermedad), asumiremos que son 1 y 0. Si los datos (D) son:

, donde di es el valor observado (0 o 1) de f(xi), y asumiendo que los datos son independientes:

Si xi es independiente de h (e.g., el tener un paciente particular es independiente de nuestras porcentajes de sobreviviencia), entonces:

Como h es la probabilidad de la funcin meta

, y en general:

Esto mismo lo podemos expresar como:

Por lo que:

La mxima verosimilitud es entonces:

Al eliminar el ltimo trmino (que no depende de h), tenemos:

Lo cual es una generalizacin de la distribucin Binomial (describe la probabilidad de que al tirar m monedas se tenga (d1, , dm) resultados asumiento que cada moneda tiene probabilidad h(xi) de salir sol).

En la descripcin de la distribucin binomial se asume que todas las monedas tienen la misma probabilidad de que salga sol.

Trabajando (de nuevo) con el logaritmo:

Lo cual, por su parecido con la medida de entropa, tambin se llama a su negativo, entropa cruzada (cross entropy).

Principio de Longitud de Descripcin Mnima

Como el proceso inductivo no es seguro se necesita alguna medida de calidad.

Normalmente se hace en base a evaluaciones con los ejemplos de entrenamiento y prueba.

Una alternativa es encontrar la hiptesis ms probable dados los datos.

El MDL est motivado al interpretar la definicin de hMAP en base a conceptos de teora de informacin.

Lo cual puede pensarse como el problema de disear el mensaje de transmisin de informacin ms compacto para transmitir la hiptesis y los datos dada la hiptesis.

MDL recomienda seleccionar la hiptesis que minimiza la suma de estas dos descripciones:

Si lo queremos aplicar a un rbol de decisin, tenemos que buscar una codificacin para los rboles de decisin y una para los ejemplos mal clasificados junto con su clasificacin.

Esto permite establecer un balance entre complejidad de la hiptesis (L(h)) y nmero de errores o calidad de la hitesis ( L(D | h) ).

La idea es detectar regularidades en los datos para que el cdigo de transmisin de la hiptesis con los datos sea menor que el de los datos solos.

Clasificador Bayesiano Optimo

En lugar de pregunarnos cul es la hiptesis ms probable, podemos preguntar, cul es la clasificacin ms probable para un ejemplo.

La clasificacin ms probable se puede obtener combinando las clasificaciones de todas las hiptesis aplicables pesadas por su probabilidad.

Si la clasificacin puede tomar un valor vj:

Y la clasificacin ptima ser:

Ejemplo:

Supongamos que tenemos dos clases 3 hiptesis ( h1, h2, h3) y que sus probabilidades dados los datos son ( 0.4,0.3,0.3) respectivamente. Si se tiene un nuevo ejemplo x que se clasifica como positivo por h1 pero negativo por h2 y h3, su clasificacin por la hiptesis MAP sera positivo, pero considerando todas las hiptesis sera negativo.

Aplicar el clasificador Bayesiano ptimo puede ser muy costoso.

Una posibilidad es seleccionar una hiptesis (h) aleatoriamente de acuerdo con la distribucin de probabilidad de las probabilidades posteriores de H, y usar h para predecir (Gibbs).

Se puede mostrar que el error esperado es a lo ms el doble del error esperado del clasificador Bayesiano ptimo.

6.3 Clasificador Bayesiano naive

Se utiliza cuando queremos clasificar una instancia descrita por un conjunto de atributos (ai's) en un conjunto finito de clases (V).

Clasificar un nuevo ejemplo de acuerdo con el valor ms probable dados los valores de sus atributos.

Usando Bayes:

P(vj) se puede estimar con la frecuencia de las clases, pero para P(a1, , an | vj) tenemos muy pocos elementos. El clasificador Bayesiana naive tambin llamado a veces idiot Bayes asume que los valores de los atributos son condicionalmente independientes dado el valor de la clase.

Osea: Por lo que:

Los valores P(ai | vj) se estiman con la frecuencia de los datos observados.

Nota: no se hace bsqueda de hiptesis, simplemente se cuentan frecuencias de ocurrencias.

Ejemplo:

Si tomamos el ejemplo de la tabla3.2 (de jugar golf), supongamos que tenemos el siguiente ejemplo que lo queremos clasificar con un naive Bayes:

Ambiente=soleado, Temperatura=baja, Humedad=alta, Viento=si

P(Clase=P) = 9/14 P(Clase=N) = 6/14

Que normalizando nos da:

.

Estimacin de Probabilidades

Hasta ahora hemos asumido que la probabilidad de un evento se puede estimar por su frecuencia

A pesar de ser una buena aproximacin, da estimaciones malas cuando tenemos pocos ejemplos.

Una alternativa es utilizar la estimacin m (m-estimate):

donde p es una estimacin a priori de lo que queremos estimar y m es una constante llamada ``tamao de muestra equivalente'' (equivalent sample size).

Una valor tpico para p es asumir que se tiene una distribucin uniforme, por lo que:

cuando existen k posibles valores.

m tambin se usa como estimador de ruido.

Ejemplo

Podemos usar un clasificador Bayesiano naive para aprender a clasificar textos de acuerdo a las preferencias de un usuario.

Suponemos que los ejemplos son documentos en texto asociados con una clase (e.g., me interesa y no me interesa, o poltica, deportes, espectculos, sociales, etc.). Suponiendo que las palabras son idependientes entre s y de su posicin en el texto (lo cual no es cierto, pero de todos modos se tienen buenos resultados):

Vocabulario = todas las palabras distintivas (eliminando palabras muy comunes y poco distintivas como artculos, puntuaciones, etc.)

Para cada clase: doc(clase) = subconjunto de textos de esa clase

Texto = concatenacin de todos los textos en doc(clase) n = nmero de palabras distintas en Texto Para cada palabra (w) en Vocabulario: nk = nmero de veces que aparece la palabra w en Texto

(se calcula la probabilidad considerando el estimador m,

con probabilidad uniforme en las clases (Laplace) y m = |Vocabulario|

Para clasificar un nuevo documento (considerando solo las palabras en el nuevo documento que teniamos en Vocabulario):