Algoritmos de Minería “Las ideas sencillas, frecuentemente

funcionan bien” Un atributo hace todo (1-Rule) Estructura lógica capturada en un árbol de

decisión (ID3) Todos los atributos contribuyen Reglas independientes

Reglas de clasificación

Antecedente consecuente Antecedente: precondiciones, son la serie

de pruebas que se realizan sobre los atributos.

Consecuente: conclusión, da la clase o clases que aplican a las instancias cubiertas por la regla

Modelado Estadístico

Todos los atributos contribuyen Los atributos se consideran:

• Iguales en importancia• Independientes

Se toma en cuenta la frecuencia del par atributo-valor por clase

No realista, ¡pero funciona!

Modelado estadístico

Está basado en la regla de probabilidad condicional de Bayes

Si se tiene una hipótesis H, y una evidencia E entonces:

P[H|E] = P[E|H] P[H]/ P[E] • H : Play=Yes• E : Combinación de valores del nuevo día

Naive Bayes

P[H|E] = P[E1|H] P[E2|H] P[E3|H] P[E4|H] P[H]

P[E]

• Los números encontrados se convierten en probabilidades normalizandolos de forma que sumen 1

P[H1|E] = P[E1|H] ... P[En|H] P[H]

P[E|H1] +... +P[E|Hm]

Ejemplooutlook Play Temp Play humidity Play windy Play

overcast Yes cool No high No false Noovercast Yes cool Yes high No false Noovercast Yes cool Yes high No false Yesovercast Yes cool Yes high No false Yes

rain No hot No high Yes false Yesrain No hot No high Yes false Yesrain Yes hot Yes high Yes false Yesrain Yes hot Yes normal No false Yesrain Yes mild No normal Yes true Nosunny No mild No normal Yes true Nosunny No mild Yes normal Yes true Nosunny No mild Yes normal Yes true Yessunny Yes mild Yes normal Yes true Yessunny Yes mild Yes normal Yes true Yes

Frecuencias

yes no yes no yes no yes nosunny hot high true

overcast mild normal falserainy cold

Outlook Temperature Humidity Windy

yes noPlay

Probabilidades ObservadasProbabilidad a Priori

Ejemplo

yes no yes no yes no yes nosunny 2 3 hot 2 2 high 3 4 true 3 3

overcast 4 0 mild 4 2 normal 6 1 false 6 2rainy 3 2 cold 3 1

Outlook Temperature WindyHumidity

yes no9 5

Play

yes no yes no yes no yes nosunny 2/9 3/5 hot 2/9 2/5 high 3/9 4/5 true 3/9 3/5overcast 4/9 0/5 mild 4/9 2/5 normal 6/9 1/5 false 6/9 2/5rainy 3/9 2/5 cold 3/9 1/5

Outlook Temperature Humidity Windy

yes no9/14 5/14

Play

Ejemplo Nuevo díaOutlook Temp Humidity Windy playSunny Cool High True ?

Pos. Yes = 2/9 x 3/9 x 3/9 x 3/9 x 9/14 = 0.0053Pos. No = 3/5 x 1/5 x 4/5 x 3/5 x 5/14 = 0.0206

Prob. Yes = 0.0053 = 20.5 % 0.0053 + 0.0206

Prob. No = 0.0206 = 79.5 % 0.0053 + 0.0206

Ejercicio Lentes de Contacto

Edad Problema Astigmatismo Prod. lágrimas LentesJoven Miopía No Reducida NingunoJoven Miopía No Normal BlandosJoven Miopía Si Reducida NingunoJoven Miopía Si Normal DurosJoven Hipermetropía No Normal BlandosJoven Hipermetropía Si Reducida NingunoJoven Hipermetropía Si Normal DurosAdulto Miopía No Reducida NingunoAdulto Miopía No Normal BlandosAdulto Miopía Si Reducida NingunoAdulto Hipermetropía No Reducida NingunoAdulto Hipermetropía No Normal BlandosAdulto Hipermetropía Si Reducida NingunoAdulto Hipermetropía Si Normal Ninguno

Anciano Miopía No Reducida NingunoAnciano Miopía No Normal NingunoAnciano Miopía Si Reducida NingunoAnciano Miopía Si Normal DurosAnciano Hipermetropía No Reducida NingunoAnciano Hipermetropía Si Reducida NingunoAnciano Hipermetropía Si Normal Ninguno

Lentes de Contacto

Eliminando

3 instancias

Edad Lentes B N D Problema Lentes B N DAdulto Blandos Hipermetropía BlandosAdulto Blandos Hipermetropía BlandosAdulto Ninguno Hipermetropía DurosAdulto Ninguno Hipermetropía NingunoAdulto Ninguno Hipermetropía NingunoAdulto Ninguno Hipermetropía NingunoAdulto Ninguno Hipermetropía Ninguno

Anciano Duros Hipermetropía NingunoAnciano Ninguno Hipermetropía NingunoAnciano Ninguno Hipermetropía NingunoAnciano Ninguno Miopía BlandosAnciano Ninguno Miopía BlandosAnciano Ninguno Miopía DurosAnciano Ninguno Miopía DurosJoven Blandos Miopía NingunoJoven Blandos Miopía NingunoJoven Duros Miopía NingunoJoven Duros Miopía NingunoJoven Ninguno Miopía NingunoJoven Ninguno Miopía NingunoJoven Ninguno Miopía Ninguno

Lentes de Contacto

Astigmatismo Lentes B N D Prod. lágrimas Lentes B N DNo Blandos Normal BlandosNo Blandos Normal BlandosNo Blandos Normal BlandosNo Blandos Normal BlandosNo Ninguno Normal DurosNo Ninguno Normal DurosNo Ninguno Normal DurosNo Ninguno Normal NingunoNo Ninguno Normal NingunoNo Ninguno Normal NingunoSi Duros Reducida NingunoSi Duros Reducida NingunoSi Duros Reducida NingunoSi Ninguno Reducida NingunoSi Ninguno Reducida NingunoSi Ninguno Reducida NingunoSi Ninguno Reducida NingunoSi Ninguno Reducida NingunoSi Ninguno Reducida NingunoSi Ninguno Reducida NingunoSi Ninguno Reducida Ninguno

Lentes de Contacto

Edad B N D Problema B N D Astig B N D Lagrimeo B N DAdulto 2 5 0 Hipermetropía 2 7 1 No 4 6 0 Normal 4 3 3

Anciano 0 6 1 Miopía 2 7 2 Si 0 8 3 Reducido 0 11 0Joven 2 3 2

Edad B N D Problema B N D Astig B N D Lagrimeo B N DAdulto 2/4 5/14 0/3 Hipermetropía 2/4 7/14 1/3 No 4/4 6/14 0 Normal 4/4 3/14 3/3

Anciano 0/4 6/14 1/3 Miopía 2/4 7/14 2/3 Si 0/4 8/14 3/3 Reducido 0/4 11/14 0/3Joven 2/4 3/14 2/3

Lentes de Contacto

Edad Problema Astigmatismo Prod. lágrimas LentesJoven Hipermetropía No Reducida ?Adulto Miopía Si Normal ?

Anciano Hipermetropía No Normal ?

B N D4 14 3

4/21 14/21 3/21

Ej 1) Pos B = (2/4) (2/4) (4/4) (0)(4/21) = 0 Pos D = (2/3) (1/3) (0) (0) (3/21) = 0 Pos N = (3/14)(7/14)(6/14)(11/14)(14/21)= 0.024 Pr = 100%

Ej 2) Pos B = (2/4) (2/4) (0) (1)(4/21) = 0 Pos D = (0) (2/3) (3/4) (1) (3/21) = 0 Pos N = (5/14)(7/14)(8/14)(3/14)(14/21) = 0.0145 Pr=100%

Ej 3) Pos B = (0/14).... = 0 Pos D = (1/3) (1/3) (0) .... = 0 Pos N = (6/14)(7/14)(6/14)(3/14)(14/21)= 0.0131 Pr = 100%

Problemas

Valores de un atributo que no se presentan La probabilidad de la clase dado que el

atributo tiene el valor ausente sería cero causando que todo el término sea cero.

La corrección es agregar uno a cada valor y compensar. (Estimador de Laplace MF. P)

2/9, 3/9, 4/9 cambian por 3/12, 4/12, 5/12

Problemas

Valores Faltantes• Nueva instancia: se omite• Conj. Entrenamiento: no cuenta

Atributos numéricos• Se supone que tienen una distribución de

probabilidad “Normal” o “Gaussiana”• Se calcula la media x y la desviación estándar

Atributos Numéricos

n

xx

n

ii

1

1

2

12

n

xxn

ii

2

2

2

2

1)(

x

exf

Ejemplooutlook temperature humidity windy play

sunny 85 85 false nosunny 80 90 true noovercast 83 86 false yesrainy 70 96 false yesrainy 68 80 false yesrainy 65 70 true no overcast 64 65 true yessunny 72 95 false nosunny 69 70 false yesrainy 75 80 false yessunny 75 70 true yesovercast 72 90 true yesovercast 81 75 false yesrainy 71 91 true no

Yes No yes no yes no yes no yes nosunny 2 3 83 85 86 85 false 6 2 9 5overcast 4 0 70 80 96 90 true 3 3rainy 3 2 68 65 80 70

64 72 65 9569 71 70 9175 8075 7072 9081 75

sunny 2/9 3/52/9 3/5 M 73 74.6 M 79.1 86.2 false 6/9 2/5 9/14 5/14overcast 4/9 0/54/9 0/5 D 6.2 7.9 D 10.2 9.7 true 3/9 3/5rainy 3/9 2/53/9 2/5

playOutlook Temperature Humidity Windy

Outlook Temp Hum Windy Play

Sunny 66 90 True ?

0340.02.62

1)|66(

2

2

)2.6(2

7366

eyesTf

Ejemplo

Pos. Yes = 2/9 x 0.034 x 0.0221 x 3/9 x 9/14 = 0.000036

Pos. No = 3/5 x 0.0279 x 0.038 x 3/5 x 5/14 = 0.000136

Prob. Yes = 0.000036 = 20.9 % 0.000036 + 0.000136

Prob. No = 0.000136 = 79.1 % 0.000036 + 0.000136

Inferencia de Reglas

Algoritmo de cobertura Considerar cada clase buscando la forma de

cubrir todas las instancias en la clase, y al mismo tiempo excluir a las instancias que no pertenecen a la clase.

Es llamado de cobertura porque en cada etapa se identifica una regla que “cubre” la mayoría de las instancias.

Método PRISM

Para cada clase se busca construir las reglas (agregando términos), que cubran todas las instancias de esa clase.

Al agregar un termino, suponga que la nueva regla cubre un total de t instancias, de las cuales p son ejemplos de la clase y t-p están en otras clases (errores de la regla).

Escoger el término que maximiza p/t

b

a aa

a

a a

b

b bb

bb

b

x

yb

aaa

aa

a

b

b bb

b

b

b

bb

by

1.2

baa

a

aa

a

b

b bb b

b

b

bb

b2.6

1.2

x > 1.2 ?

b Y > 2.6 ?

b a

no

no

yes

yes

Espacio de instancias

Regla hasta el momento

Regla después deañadir un nuevo término

Método PRISMPara cada clase C

Inicializar E con el conjunto de instancias

Mientras E contenga instancias de la clase C

Crear la regla R: ? C

Hasta que R sea perfecta (o más atributos) haz:

Para cada atributo A no mencionado en R, y valor v

Considerar agregar A=v en el lado Izquierdo de R

Seleccionar A y v que maximicen la precisión p/t

(si existen iguales escoger el de mayor p)

Agregar A=v a R

Eliminar las instancias cubiertas por R de E

AG SP AS TP RL

young hypermetrope yes normal hardyoung myope yes normal hardyoung hypermetrope no reduced noneyoung hypermetrope yes reduced noneyoung myope no reduced noneyoung myope yes reduced noneyoung hypermetrope no normal softyoung myope no normal soft

presbyopic myope yes normal hardpresbyopic hypermetrope no reduced nonepresbyopic hypermetrope yes reduced nonepresbyopic hypermetrope yes normal nonepresbyopic myope no reduced nonepresbyopic myope no normal nonepresbyopic myope yes reduced nonepresbyopic hypermetrope no normal soft

pre - presbyopic myope yes normal hardpre - presbyopic hypermetrope no reduced nonepre - presbyopic hypermetrope yes reduced nonepre - presbyopic hypermetrope yes normal nonepre - presbyopic myope no reduced nonepre - presbyopic myope yes reduced nonepre - presbyopic hypermetrope no normal softpre - presbyopic myope no normal soft

Ejemplo: Lentes

Si ? Hard Ag = young 2/8 0.25

= pre-presbyopic 1/8 0.125= presbyopic 1/8 0.125

SP = myope 3/12 0.25= hypermetrope 1/12 0.083

AS = no 0/12 0= yes 4/12 0.333

TP = reduced 0/12 0= normal 4/12 0.333

Si (AS=Yes) Hard

AG SP AS TP RL

young hypermetrope yes normal hardyoung myope yes normal hard

presbyopic myope yes normal hardpre - presbyopic myope yes normal hard

young hypermetrope yes reduced noneyoung myope yes reduced none

presbyopic hypermetrope yes reduced nonepresbyopic hypermetrope yes normal nonepresbyopic myope yes reduced none

pre - presbyopic hypermetrope yes reduced nonepre - presbyopic hypermetrope yes normal nonepre - presbyopic myope yes reduced none

Si (AS = Yes) & ? Hard Ag = young 2/4 0.5

= pre-presbyopic 1/4 0. 25= presbyopic 1/4 0. 25

SP = myope 3/6 0.5= hypermetrope 1/6 0.016

TP = reduced 0/6 0= normal 4/6 0.66

Si (AS=Yes)&(TP=Normal) Hard

AG SP AS TP RL

young hypermetrope yes normal hardyoung myope yes normal hard

presbyopic myope yes normal hardpre - presbyopic myope yes normal hard

presbyopic hypermetrope yes normal nonepre - presbyopic hypermetrope yes normal none

Si (AS = Yes) &(TP=Normal) & ? Hard Ag = young 2/2 1

= pre-presbyopic 1/2 0.5= presbyopic 1/4 0.5

SP = myope 3/3 1= hypermetrope 1/3 0.33

Si (AS=Yes)&(TP=Normal)&(SP=Myope) Hard

AG SP AS TP RL

young hypermetrope no normal softyoung myope no normal soft

presbyopic hypermetrope no normal softpre - presbyopic hypermetrope no normal softpre - presbyopic myope no normal soft

young hypermetrope no reduced noneyoung hypermetrope yes reduced noneyoung myope no reduced noneyoung myope yes reduced none

presbyopic hypermetrope no reduced nonepresbyopic hypermetrope yes reduced nonepresbyopic hypermetrope yes normal nonepresbyopic myope no reduced nonepresbyopic myope no normal nonepresbyopic myope yes reduced none

pre - presbyopic hypermetrope no reduced nonepre - presbyopic hypermetrope yes reduced nonepre - presbyopic hypermetrope yes normal nonepre - presbyopic myope no reduced nonepre - presbyopic myope yes reduced none

young hypermetrope yes normal hard

The contac lens data

Reglas para RL=Hard

If (AS = Yes) & (TP = Normal) &

(SP = Myope) HARD

If (AG = Young) & (AS = Yes) &

(TP = Normal) HARD