Inteligencia Artificial - Aprendizaje automático · AlgoritmoID3(ejemplo1) I Conjuntodeentrenamiento: Ej. Cielo Temperatura Humedad Viento JugarTenis D 1 Soleado Alta Alta Débil

Inteligencia ArtificialAprendizaje automático

Departamento de Ciencias de la Computacióne Inteligencia Artificial

Universidad de Sevilla

CCIA, US Inteligencia Artificial IA 1 / 57

Aprendizaje

I Definiciones de aprendizaje:I Cualquier cambio en un sistema que le permita realizar la misma

tarea de manera más eficiente la próxima vez (H. Simon)I Modificar la representación del mundo que se está percibiendo

(R. Michalski)I Realizar cambios útiles en nuestras mentes (M. Minsky)


Aprendizaje

I Aprendizaje automático: construir programas que mejoranautomáticamente con la experiencia

I Ejemplos de tareas:I Construcción de bases de conocimiento a partir de la experienciaI Clasificación y diagnósticoI Minería de datos, descubrir estructuras desconocidas en grandes

grupos de datosI Resolución de problemas, planificación y acción


Tipos de aprendizaje y paradigmas

I Tipos de aprendizajeI SupervisadoI No supervisadoI Con refuerzo

I ParadigmasI Aprendizaje por memorizaciónI Clasificación (Clustering)I Aprendizaje inductivoI Aprendizaje por analogíaI DescubrimientoI Algoritmos genéticos, redes neuronales


Ejemplo de aprendizaje

I Conjunto de entrenamientoI Ejemplos: días en los que es recomendable (o no) jugar al tenisI Representación como una lista de pares atributo–valor

Ej. Cielo Temperatura Humedad Viento JugarTenisD1 Soleado Alta Alta Débil -D2 Soleado Alta Alta Fuerte -D3 Nublado Alta Alta Débil +D4 Lluvia Suave Alta Débil +…

I Objetivo: Dado el conjunto de entrenamiento, aprender elconcepto «Días en los que se juega al tenis»I Se trata de aprendizaje supervisado

I Problema: ¿Cómo expresar lo aprendido?I En este tema, veremos algoritmos para aprender árboles de

decisión, reglas, modelos probabilísticos,...


Aprendizaje deárboles de decisión


Árboles de decisión

I Ejemplos de árboles de decisión

Cielo

LluviaSoleado Nublado

+Viento

Debil

+

Humedad

Alta

+− −

Normal Fuerte


Árboles de decisión

I Ejemplos de árboles de decisiónColor

Rojo Verde Azul

Forma

Redondo Cuadrado

Grande

Tamaño

Pequeño

Grande

−Tamaño

Pequeño

+ −

+ −

+


Árboles de decisiónI Árboles de decisión

I Nodos interiores: atributosI Arcos: posibles valores del nodo origenI Hojas: valor de clasificación (usualmente + ó −, aunque podría

ser cualquier conjunto de valores, no necesariamente binario)I Representación de una función objetivo

I Disyunción de reglas proposicionales:(Cielo=Soleado ∧ Humedad=Alta → JugarTenis=

−)∨ (Cielo=Soleado ∧ Humedad=Normal →JugarTenis= +)∨ (Cielo=Nublado → JugarTenis= +)∨ (Cielo=Lluvioso ∧ Viento=Fuerte →JugarTenis= −)∨ (Cielo=Lluvioso ∧ Viento=Debil → JugarTenis=+)

I Capaz de representar cualquier subconjunto de instanciasCCIA, US Inteligencia Artificial IA 9 / 57

Aprendizaje de árboles de decisión

I Objetivo: aprender un árbol de decisión consistente con losejemplos, para posteriormente clasificar ejemplos nuevos

I Ejemplo de conjunto de entrenamiento:Ej. Cielo Temperatura Humedad Viento JugarTenisD1 Soleado Alta Alta Débil -D2 Soleado Alta Alta Fuerte -D3 Nublado Alta Alta Débil +D4 Lluvia Suave Alta Débil +…


Algoritmo ID3

Algoritmo ID3ID3(Ejemplos, Atributo-objetivo, Atributos)1. Si todos los Ejemplos son positivos, devolver un nodo

etiquetado con +2. Si todos los Ejemplos son negativos, devolver un nodo

etiquetado con -3. Si Atributos está vacío, devolver un nodo etiquetado con el valor

más frecuente de Atributo-objetivo en Ejemplos.4. En otro caso:4.1. Sea A el atributo de Atributos que MEJOR clasifica Ejemplos4.2. Crear Árbol, con un nodo etiquetado con A.4.3. Para cada posible valor v de A, hacer:

* Añadir un arco a Árbol, etiquetado con v.* Sea Ejemplos(v) el subconjunto de Ejemplos con valor delatributo A igual a v.

* Si Ejemplos(v) es vacío:- Entonces colocar debajo del arco anterior un nodo etiquetadocon el valor más frecuente de Atributo-objetivo en Ejemplos.

- Si no, colocar debajo del arco anterior el subárbolID3(Ejemplos(v), Atributo-objetivo, Atributos-{A}).

4.4 Devolver Árbol


¿Cómo saber qué atributo clasifica mejor?

I Entropía de un conjunto de ejemplos D (resp. de unaclasificación):

Ent(D) = − |P ||D| · log2

|P ||D| −

|N ||D| · log2

|N ||D|

donde P y N son, respectivamente, los subconjuntos de ejemplospositivos y negativos de DI Notación: Ent([p+, n−]), donde p = |P | y n = |N |

I Intuición:I Mide la ausencia de «homogeneidad» de la clasificaciónI Teoría de la Información: cantidad media de información (en

bits) necesaria para codificar la clasificación de un ejemploI Ejemplos:

I Ent([9+, 5−]) = − 914 · log2 9

14 − 514 · log2 5

14 = 0.94I Ent([k+, k−]) = 1 (ausencia total de homogeneidad)I Ent([p+, 0−]) = Ent([0+, n−]) = 0 (homogeneidad total)


Ganancia de información

I Preferimos nodos con menos entropía (árboles pequeños)I Entropía esperada después de usar un atributo A en el árbol:∑

v∈V alores(A)|Dv ||D| · Ent(Dv)

donde Dv es el subconjunto de ejemplos de D con valor delatributo A igual a v

I Ganancia de información esperada después de usar unatributo A:Ganancia(D,A) = Ent(D)−

∑v∈V alores(A)

|Dv ||D| · Ent(Dv)

I En el algoritmo ID3, en cada nodo usamos el atributo con mayorganancia de información (considerando los ejemploscorrespondientes al nodo)


Algoritmo ID3 (ejemplo 1)

I Conjunto de entrenamiento:Ej. Cielo Temperatura Humedad Viento JugarTenisD1 Soleado Alta Alta Débil -D2 Soleado Alta Alta Fuerte -D3 Nublado Alta Alta Débil +D4 Lluvia Suave Alta Débil +D5 Lluvia Baja Normal Débil +D6 Lluvia Baja Normal Fuerte -D7 Nublado Baja Normal Fuerte +D8 Soleado Suave Alta Débil -D9 Soleado Baja Normal Débil +D10 Lluvia Suave Normal Débil +D11 Soleado Suave Normal Fuerte +D12 Nublado Suave Alta Fuerte +D13 Nublado Alta Normal Débil +D14 Lluvia Suave Alta Fuerte -



Normal

Humedad

Alta

[3+, 4−] [6+, 1−]

Viento

Fuerte Debil

[6+, 2−] [3+, 3−]

TemperaturaCielo

[2+, 2−] [4+, 2−] [3+, 1−]

BajaSuaveAltaLluvia

[2+, 3−] [3+, 2−][4+, 0−]

Soleado Nublado



I Entropía inicial: Ent([9+, 5−]) = 0.94

I Selección del atributo para el nodo raíz:I Ganancia(D,Humedad) =

0.94− 714 · Ent([3+, 4−])− 7

14 · Ent([6+, 1−]) = 0.151I Ganancia(D,Viento) =

0.94− 814 · Ent([6+, 2−])− 6

14 · Ent([3+, 3−]) = 0.048I Ganancia(D,Cielo) =

0.94− 514 · Ent([2+, 3−])− 4

14 · Ent([4+, 0−])− 5

14 · Ent([3+, 2−]) = 0.246 (mejor atributo)I Ganancia(D,Temperatura) =

0.94− 414 · Ent([2+, 2−])− 6

14 · Ent([4+, 2−])− 4

14 · Ent([3+, 1−]) = 0.02

I El atributo seleccionado es Cielo



I Árbol parcialmente construido:

?

Cielo

Soleado Nublado Lluvia

+ ?



I Selección del atributo para el nodo Cielo=SoleadoI DSoleado = {D1, D2, D8, D9, D11} con entropía

Ent([2+, 3−]) = 0.971I Ganancia(DSoleado,Humedad) =

0.971− 35 · 0− 2

5 · 0 = 0.971 (mejor atributo)I Ganancia(DSoleado,Temperatura) =

0.971− 25 · 0− 2

5 · 1− 15 · 0 = 0.570

I Ganancia(DSoleado,Viento) =0.971− 2

5 · 1− 35 · 0.918 = 0.019

I El atributo seleccionado es Humedad



I Selección del atributo para el nodo Cielo=Lluvia:I DLluvia = {D4, D5, D6, D10, D14} con entropía

Ent([3+, 2−]) = 0.971I Ganancia(DLluvia,Humedad) =

0.971− 25 · 1− 3

5 · 0.918 = 0.820I Ganancia(DLluvia,Temperatura) =

0.971− 35 · 0.918− 2

5 · 1 = 0.820I Ganancia(DLluvia,Viento) =

0.971− 35 · 0− 2

5 · 0 = 0.971 (mejor atributo)I El atributo seleccionado es Viento



I Árbol finalmente aprendido:

Cielo

LluviaSoleado Nublado

+Viento

Debil

+

Humedad

Alta

+− −

Normal Fuerte



I Conjunto de entrenamiento:Ej. Color Forma Tamaño ClaseO1 Rojo Cuadrado Grande +O2 Azul Cuadrado Grande +O3 Rojo Redondo Pequeño -O4 Verde Cuadrado Pequeño -O5 Rojo Redondo Grande +O6 Verde Cuadrado Grande -



I Entropía inicial en el ejemplo de los objetos, Ent([3+, 3−]) = 1

I Selección del atributo para el nodo raíz:I Ganancia(D,Color) =

1− 36 ·Ent([2+, 1−])− 1

6 ·Ent([1+, 0−])− 26 ·Ent([0+, 2−]) = 0.543

I Ganancia(D,Forma) =1− 4

6 · Ent([2+, 2−])− 26 · Ent([1+, 1−]) = 0

I Ganancia(D,Tamaño) =1− 4

6 · Ent([3+, 1−])− 26 · Ent([0+, 2−]) = 0.459

I El atributo seleccionado es Color



I Árbol parcialmente construido:

?

Color

Rojo Verde Azul

− +



I Selección del atributo para el nodo Color=Rojo:I DRojo = {O1, O3, O5} con entropía Ent([2+, 1−]) = 0.914

I Ganancia(DRojo,Forma) =0.914− 1

3 · Ent([1+, 0−])− 23 · Ent([1+, 1−]) = 0.247

I Ganancia(DRojo,Tamaño) =0.914− 2

3 · Ent([2+, 0−])− 13 · Ent([0+, 1−]) = 0.914

I El atributo seleccionado es Tamaño



I Árbol finalmente aprendido:

Grande

Color

Rojo Verde Azul

−Tamaño

Pequeño

+

+ −


Búsqueda y sesgo inductivo

I Búsqueda local en un espacio de hipótesisI Espacio de todos los árboles de decisiónI Un único árbol candidato en cada pasoI Sin retroceso (peligro de óptimos locales), búsqueda en escaladaI Decisiones tomadas a partir de conjuntos de ejemplos

I Sesgo inductivoI Se prefieren árboles más cortos sobre los más largosI Sesgo preferencial, implícito en la búsquedaI Principio de la navaja de Occam


Algunas cuestiones prácticas a resolver enaprendizaje automático

I Validar la hipótesis aprendidaI ¿Podemos cuantificar la bondad de lo aprendido respecto de la

explicación real?I Sobreajuste

I ¿Se ajusta demasiado lo aprendido al conjunto deentrenamiento?


Medida del rendimiento del aprendizaje

I Conjuntos de entrenamiento y prueba (test)I Aprender con el conjunto de entrenamientoI Medir el rendimiento en el conjunto de prueba:

I proporción de ejemplos bien clasificados en el conjunto de pruebaI Repetición de este proceso

I Curva de aprendizajeI Estratificación: cada clase correctamente representada en el

entrenamiento y en la pruebaI Si no tenemos suficientes ejemplos como para apartar un

conjunto de prueba: validación cruzadaI Dividir en k partes, y hace k aprendizajes, cada uno de ellos

tomando como prueba una de las partes y entrenamiento el resto.Finalmente hacer la media de los rendimientos.

I En la práctica: validación cruzada, con k = 10 y estratificación


Sobreajuste y ruido

I Una hipótesis h ∈ H sobreajusta los ejemplos de entrenamiento siexiste h′ ∈ H que se ajusta peor que h a los ejemplos pero actúamejor sobre la distribución completa de instancias.

I Ruido: ejemplos incorrectamente clasificados. Causa sobreajusteI Ejemplo: supongamos que, por error, se incluye el ejemplo

<Azul,Redondo,Pequeño> como ejemplo negativoI El árbol aprendido en este caso sería (sobreajustado a los datos):

Color

Rojo Verde Azul

Grande

−Tamaño

+ −

Pequeño

+

Color

Rojo Verde Azul

Forma

CuadradoGrande

−Tamaño

+ − − +

RedondoPequeño


Sobreajuste y ruido

I Otras causas de sobreajuste:I Atributos que en los ejemplos presentan una aparente regularidad

pero que no son relevantes en realidadI Conjuntos de entrenamiento pequeños

I Maneras de evitar el sobreajuste en árboles de decisión:I Parar el desarrollo del árbol antes de que se ajuste perfectamente

a todos los datosI Podar el árbol a posteriori

I Poda a posteriori, dos aproximaciones:I Transformación a reglas, podado de las condiciones de las reglasI Realizar podas directamente en el árbolI Las podas se producen siempre que reduzcan el error sobre un

conjunto de prueba


Podado de árboles

Algoritmo de poda para reducir el error1. Dividir el conjunto de ejemplos en Entrenamiento y Prueba2. Árbol=árbol obtenido por ID3 usando Entrenamiento3. Continuar=True4. Mientras Continuar:* Medida = proporción de ejemplos en Prueba correctamenteclasificados por Árbol

* Por cada nodo interior N de Árbol:- Podar temporalmente Árbol en el nodo N y sustituirlo por unahoja etiquetada con la clasificación mayoritaria en ese nodo

- Medir la proporción de ejemplos correctamente clasificados enel conjunto de prueba.

* Sea K el nodo cuya poda produce mejor rendimiento* Si este rendimiento es mejor que Medida, entoncesÁrbol = resultado de podar permanentemente Árbol en K

* Si no, Continuar=Falso5. Devolver Árbol


Otras cuestiones prácticas del algoritmo ID3

I Extensiones del algoritmo:I Atributos con valores contínuosI Otras medidas para seleccionar atributosI Otras estimaciones de errorI Atributos sin valoresI Atributos con coste

I Algoritmos C4.5 y C5.0 (Quinlan)


Clasificación mediante modelosprobabilísticos: naive Bayes


Clasificadores naive Bayes

I Supongamos un conjunto de atributos A1, . . . , An cuyos valoresdeterminan un valor en un conjunto finito V de posibles «clases»o «categorías»

I Tenemos un conjunto de entrenamiento D con una serie de tuplasde valores concretos para los atributos, junto con su clasificación

I Queremos aprender un clasificador tal que clasifique nuevasinstancias 〈a1, . . . , an〉I Es decir, el mismo problema en el tema de aprendizaje de árboles

de decisión (pero ahora lo abordaremos desde una perspectivaprobabilística).


Clasificadores naive BayesI Podemos diseñar un modelo probabilístico para un problema de

clasificación de este tipo, tomando los atributos y la clasificacióncomo variables aleatorias

I El valor de clasificación asignado a una nueva instancia〈a1, . . . , an〉, notado vMAP vendrá dado por

argmaxvj∈V

P (vj|a1, . . . , an)

I Aplicando el teorema de Bayes podemos escribirvMAP = argmax

vj∈VP (a1, . . . , an|vj)P (vj)

I Y ahora, simplemente estimar las probabilidades de la fórmulaanterior a partir del conjunto de entrenamiento

I Problema: necesitaríamos una gran cantidad de datos paraestimar adecuadamente las probabilidades P (a1, . . . , an|vj)


Clasificadores naive Bayes

I Podemos simplificar el aprendizaje suponiendo que los atributosson (mútuamente) condicionalmente independientes dado el valorde clasificación (de ahí lo de «naive»)

I La situación se representa entonces por la red:V

A A A1 n2

I En ese caso, tomamos como valor de clasificación:

vNB = argmaxvj∈V

P (vj)∏i

P (ai|vj)


Estimación de probabilidades naive BayesI Para el proceso de aprendizaje, sólo tenemos que estimar las

probabilidades P (vj) (probabilidades a priori) y P (ai|vj)(probabilidades condicionadas). Son muchas menos que en el casogeneral.

I Mediante cálculo de sus frecuencias en el conjunto deentrenamiento, obtenemos estimaciones de máxima verosimilitudde esas probabilidades:

P (vj) =#(V = vj)

NP (ai|vj) =

#(Ai = ai, V = vj)

#(V = vj)

donde N es el número total de ejemplos, #(V = vj) es elnúmero de ejemplos clasificados como vj y #(Ai = ai, V = vj)es el número de ejemplos clasificados como vj cuyo valor en elatributo Ai es ai.


Clasificador naive Bayes: un ejemplo

I Vamos a aplicar el clasificador a un ejemplo ya conocido, usadoen el tema de árboles de decisión:

Ej. Cielo Temperatura Humedad Viento JugarTenisD1 Soleado Alta Alta Débil -D2 Soleado Alta Alta Fuerte -D3 Nublado Alta Alta Débil +D4 Lluvia Suave Alta Débil +D5 Lluvia Baja Normal Débil +D6 Lluvia Baja Normal Fuerte -D7 Nublado Baja Normal Fuerte +D8 Soleado Suave Alta Débil -D9 Soleado Baja Normal Débil +D10 Lluvia Suave Normal Débil +D11 Soleado Suave Normal Fuerte +D12 Nublado Suave Alta Fuerte +D13 Nublado Alta Normal Débil +D14 Lluvia Suave Alta Fuerte -



I Supongamos que queremos predecir si un día soleado, detemperatura suave, humedad alta y viento fuerte es bueno parajugar al tenis

I Según el clasificador Naive Bayes:

vNB = argmaxvj∈{+,−}

P (vj)P (soleado|vj)P (suave|vj)P (alta|vj)P (fuerte|vj)

I Así que necesitamos estimar todas estas probabilidades, lo quehacemos simplemente calculando frecuencias en la tabla anterior:I p(+) = 9/14, p(−) = 5/14, p(soleado|+) = 2/9,

p(soleado|−) = 3/5, p(suave|+) = 4/9, p(suave|−) = 2/5,p(alta|+) = 3/9, p(alta|−) = 4/5, p(fuerte|+) = 3/9 yp(fuerte|−) = 3/5



I Por tanto, las dos probabilidades a posteriori son:I P (+)P (soleado|+)P (suave|+)P (alta|+)P (fuerte|+) =

9/14·2/9·4/9·3/9·3/9 = 0.007I P (−)P (soleado|−)P (suave|−)P (alta|−)P (fuerte|−) =

5/14·3/5·2/5·4/5·3/5 = 0.0411

I Así que el clasificador devuelve la clasificación con mayorprobabilidad a posteriori, en este caso la respuesta es − (no es undía bueno para jugar al tenis)


Detalles técnicos sobre las estimaciones

I Si alguna de las probabilidades es cercana a 0 y tenemos pocosejemplos en el conjunto de entrenamiento, lo más seguro es quela estimación de esa probabilidad sea 0

I Esto plantea dos problemas:I La inexactitud de la propia estimaciónI Afecta enormemente a la clasificación que se calcule, ya que se

multiplican las probabilidades estimadas y por tanto si una deellas es 0, anula a las demás

I Una primera manera de abordar el problema: usar logaritmos delas probabilidades.I Los productos se transforman en sumas

vNB = argmaxvj∈V

[log(P (vj)) +∑i

log(P (ai|vj))]


Suavizado

I Problema en la estimaciones:I Probabilidades nulas o casi nulas, por ausencia en el conjunto de

entrenamiento de algunos valores de atributos en algunascategorías

I SobreajusteI Idea: suponer que tenemos m ejemplos adicionales, cuyos valores

se distribuyen teóricamente a priori de alguna manera.I Estimación suavizada de una probabilidad, a partir de

observaciones: n′+m·pn+m

I n′ y n: número de ejemplos favorables y totales observadosI p: estimación a priori de la probabilidad que se quiere estimar.I m: tamaño de muestreo equivalente, indica el número de

ejemplos adicionales (ficticios)


Suavizado aditivo (o de Laplace)

I Un caso particular de lo anterior se suele usar para la estimaciónde las probabilidades condicionales en naive Bayes:

P (ai|vj) =#(Ai = ai, V = vj) + k

#(V = vj) + k|Ai|donde k es un número fijado y |Ai| es el número de posiblesvalores del atributo |Ai|.

I Intuitivamente: se supone que además de los del conjunto deentrenamiento, hay k ejemplos en la clase vj por cada posiblevalor del atributo Ai

I Usualmente k = 1, pero podrían tomarse otros valoresI Elección de k: experimentando con los distintos rendimientos

sobre un conjunto de validación


Aprendizaje basadoen instancias: kNN


Clasificación mediante vecino más cercano

I Una técnica alternativa a construir el modelo probabilístico escalcular la clasificación directamente a partir de los ejemplos(aprendizaje basado en instancias)

I Idea: obtener la clasificación de un nuevo ejemplo a partir de lascategorías de los ejemplos más «cercanos».I Debemos manejar, por tanto, una noción de «distancia» entre

ejemplos.I En la mayoría de los casos, los ejemplos serán elementos de Rn y

la distancia, la euclídea.I Pero se podría usar otra noción de distancia

I Ejemplo de aplicación: clasificación de documentos


El algoritmo k-NN

I El algoritmo k-NN (de k nearest neighbors):I Dado un conjunto de entrenamiento (vectores numéricos con

una categoría asignada) y un ejemplo nuevoI Devolver la categoría mayoritaria en los k ejemplos del conjunto

de entrenamiento más cercanos al ejemplo que se quiere clasificar


Distancias para k-NN

I Posibles distancias usadas para definir la «cercanía»:I Euclídea: de(x,y) =

√∑ni=1(xi − yi)2

I Manhattan: dm(x,y) =∑n

i=1 |xi − yi|I Hamming: número de componentes en las que se difiere.

I La euclídea se usa cuando cada dimensión mide propiedadessimilares y la Mahattan en caso contrario; la distancia Hammingse puede usar aún cuando los vectores no sean numéricos.

I Normalización: cuando no todas las dimensiones son del mismoorden de magnitud, se normalizan las componentes (restando lamedia y dividiendo por la desviación típica)


Algunas observaciones sobre k-NN

I Elección de k:I Usualmente, basándonos en algún conocimiento específico sobre

el problema de clasificaciónI También como resultado de pruebas en conjuntos más pequeños

(conjuntos de validación)I Si la clasificación es binaria, preferiblemente impar, para intentar

evitar empates (k=5, por ejemplo)I Variante en kNN : para cada clase c, sumar la similitud (con el

que se quiere clasificar) de cada ejemplo de esa clase que estéentre los k más cercanos. Devolver la clase que obtenga mayorpuntuación.I Así un ejemplo cuenta más cuanto más cercano esté


Clustering


ClusteringI Como última aplicación del aprendizaje estadístico, trataremos

técnicas de agrupamiento o clusteringI Se trata de dividir un conjunto de datos de entrada en

subconjuntos (clusters), de tal manera que los elementos de cadasubconjunto compartan cierto patrón o características a prioridesconocidas

I En nuestro caso, los datos serán números o vectores de númerosy el número de clusters nos vendrá dado

I Aprendizaje no supervisado: no tenemos información sobre quécluster corresponde a cada dato.

I Aplicaciones de clustering:I Minería de datosI Procesamiento de imágenes digitalesI Bioinformática


Dos ejemplos

I Color quantization:I Una imagen digital almacenada con 24 bits/pixel (aprox. 16

millones de colores) se tiene que mostrar sobre una pantalla quesólo tiene 8 bits/pixel (256 colores)

I ¿Cuál es la mejor correspondencia entre los colores de la imagenoriginal y los colores que pueden ser mostrados en la pantalla?

I Mezcla de distribuciones:I Tenemos una serie de datos con el peso de personas de un pais;

no tenemos información sobre si el peso viene de un varón o deuna mujer, pero sabemos que la distribución de pesos es de tiponormal, y que en los hombres es distinta que en las mujeres

I Atendiendo a los datos, ¿podemos aprender de qué dosdistribuciones de probabilidad vienen?


Clustering basado en distancia

I Idea: dado el número k de grupos o clusters, buscar k puntos ocentros representantes de cada cluster, de manera que cada datose considera en el cluster correspondiente al centro que tiene amenor «distancia»

I Como antes, la distancia sería específica de cada problema:I Expresará la medida de similitudI La distancia más usada es la euclídea


Un algoritmo clásico: k-medias

I Entrada: un número k de clusters, un conjunto de datos {xi}Ni=1

y una función de distanciaI Salida: un conjunto de k centros m1, . . . ,mk

k-medias(k,datos,distancia)1. Inicializar m_i (i=1,...,k) (aleatoriamente o con algún

criterio heurístico)2. REPETIR (hasta que los m_i no cambien):

2.1 PARA j=1,...,N, HACER:Calcular el cluster correspondiente a x_j, escogiendo,de entre todos los m_i, el m_h tal quedistancia(x_j,m_h) sea mínima

2.2 PARA i=1,...,k HACER:Asignar a m_i la media aritmética de los datosasignados al cluster i-ésimo

3. Devolver m_1,...,m_n


Idea gráfica intuitiva en el algoritmo de k-medias

■■

■

■

■ ■

Iteracion 1

Iteracion 3

Iteracion 0

Iteracion 2

■

■


Ejemplo en el algoritmo k-medias

I Datos sobre pesos de la población: 51, 43, 62, 64, 45, 42, 46, 45,45, 62, 47, 52, 64, 51, 65, 48, 49, 46, 64, 51, 52, 62, 49, 48, 62,43, 40, 48, 64, 51, 63, 43, 65, 66, 65, 46, 39, 62, 64, 52, 63, 64,48, 64, 48, 51, 48, 64, 42, 48, 41

I El algoritmo, aplicado con k = 2 y distancia euclídea, encuentrados centros m1 = 63.63 y m2 = 46.81 en tres iteraciones

I 19 datos pertenecen al primer cluster y 32 al segundo cluster


Cuestiones sobre el algoritmo k-mediasI Puede verse como un algoritmo de búsqueda local: encontrar los

centros mi que optimizan

ΣjΣibijd(xj,mi)2

donde bij vale 1 si xj tiene a mi como el centro más cercano, 0en otro caso.No garantiza encontrar el óptimo global.

I Inicialización: aleatoria o con alguna técnica heurística (porejemplo, partir los datos aleatoriamente en k clusters y empezarcon los centros de esos clusters)

I En la práctica, los centros con los que se inicie el algoritmo tienenun gran impacto en la calidad de los resultados que se obtengan

I Clusters vacíos: elegir un nuevo centro de manera aleatoria ousando alguna técnica heurística


Bibliografía

I Mitchell, T.M. Machine Learning (McGraw-Hill, 1997)I Caps. 3,6,8 y 10

I Russell, S. y Norvig, P. Artificial Intelligence (A ModernApproach) (3rd edition) (Prentice Hall, 2010)I Seccs. 18.1, 18.2, 18.3, 20.1 y 20.2

I Russell, S. y Norvig, P. Inteligencia Artificial (Un enfoquemoderno) (segunda edición en español) (Pearson Education,2004)I Seccs. 18.1, 18.2, 18.3, 18.8, 20.1, 20.2 y 20.4

I Witten, I.H. y Frank, E. Data mining (Second edition) (MorganKaufmann Publishers, 2005)I Cap. 3, 4, 5 y 6.


Documents

Inteligencia Artificial - Aprendizaje automático · AlgoritmoID3(ejemplo1) I Conjuntodeentrenamiento: Ej. Cielo Temperatura Humedad Viento JugarTenis D 1 Soleado Alta Alta Débil