Embed Size (px)
Citation preview
Técnicas de Minería de
Datos
Centro Universitario Valle de México
Maestría en Ciencias de la Computación
Minería de Datos
Dra. Maricela Quintana LópezElaborado por:
Unidad de competencia III: Proceso de Análisis SupervisadoTécnicas de Minería de Datos
Objetivo: Presentar los algoritmos de análisis
supervisado, específicamente de clasificación.
Conocimientos: One rule, Inductive Decision Tree ID3,
índice Gini.
Árboles de decisión◦ 1-Rule◦ ID3◦ GINI
Reglas de Clasificación◦ 1-Rule◦ Naive Bayes◦ PRISM
CLASIFICACIÓN
“Las ideas sencillas, frecuentemente funcionan bien”
Un atributo hace todoTodos los atributos contribuyenEstructura lógica capturada en un árbol de decisión
Reglas independientesetc...
Algoritmos de Minería
El método más simple es llamado “1-rule” Genera un árbol de decisión de un nivel Conjunto de reglas que prueban un atributo
en particular Cada rama corresponde a un valor distinto
del atributo
Inferencia de Reglas
La asignación de la clase para la rama será la más frecuente en el conjunto de entrenamiento (clase mayoritaria)
La tasa de error se calcula contando las instancias que no tienen la clase mayoritaria
Cada atributo genera un conjunto distinto de reglas, una regla por cada valor del atributo
Es necesario calcular la tasa de error para elegir el mejor conjunto de reglas
Método 1-Rule
Para cada atributoPara cada valor del atributo:
Calcular la frecuencia de cada claseDeterminar la clase mayoritaria CMConstruye el árbol ó la regla:
si valor de atributo entonces CM Calcular la tasa de error de las reglas
Escoger las reglas con la menor tasa de error
Método 1-Rule
outlook temperature humidity windy Playovercast hot high false Playrain mild high false Playrain cool normal false Playovercast cool normal true Playsunny cool normal false Playrain mild normal false Playsunny mild normal true Playovercast mild high true Playovercast hot normal false Playsunny hot high false Don't Playsunny hot high true Don't Playrain cool normal true Don't Playsunny mild high false Don't Playrain mild high true Don't Play
1-Rule para el Golf
¿Error total?
4 0
3 2
2 3
Play
Play
Don’t Play
1-Rule para el Golf
¿Error total?
Ejercicio
Conjunto attribute rules errors total errors1 outlook sunny --> no 2/5 4/14
overcast --> yes 0/4rainy --> yes 2/5
2 temperature hot --> no 2/4 5/14mild --> yes 2/6cool --> yes 1/4
3 humidity high --> no 3/7 4/14normal --> yes 1/7
4 windy false --> yes 2/8 5/14true --> no 3/6
Elegir el mejor atributo
1-Rule para el Golf
Árboles de decisión
Reglas
Resultado
if (outlook == sunny) then don’t playif (outlook == rainy) then playif (outlook == overcast) then play
Outlook
Don’t Play
Play Play
sunny overcastrainy
Valores faltantes◦ Es tratado como otro valor del atributo
if outlook = missing then yes
Atributos numéricos◦ Convertirlos
Valores faltantes y atributos numéricos
Golf con valores numéricosoutlook temperature humidity windy play
overcast 64 65 true yesrainy 65 70 true no rainy 68 80 false yessunny 69 70 false yesrainy 70 96 false yesrainy 71 91 true nosunny 72 95 false noovercast 72 90 true yesrainy 75 80 false yessunny 75 70 true yessunny 80 90 true noovercast 81 75 false yesovercast 83 86 false yessunny 85 85 false no
Particiónoutlook Temp play play play play
overcast 64 yes 64.5 yes yes yesrainy 65 no 66.5 no no no rainy 68 yes yes yes yessunny 69 yes yes yes yesrainy 70 yes 70.5 yes yes yesrainy 71 no no no nosunny 72 no 72 no no noovercast 72 yes yes yes yesrainy 75 yes yes yes yessunny 75 yes 77.5 yes yes yessunny 80 no 80.5 no no noovercast 81 yes yes yes yesovercast 83 yes 84 yes yes yessunny 85 no no no no
If temperature <=77.5 then Play=yeselse Play = No
Ejercicio
Solución
If (humidity <=82.5) or (humidity>95.5) then play else don’t play
Utiliza la técnica de Divide y Conquista
Procedimiento inductivo
La salida es un árbol de decisión
Top-Down induction of decision trees
Desarrollada y refinada por Ross Quinlan de la universidad de Sydney, Australia
Conocido como ID3
Árboles de Decisión
Clasifica patrones con atributos no numéricos
Mejorado con el uso del radio de ganancia
Variaciones ◦C4.5, ◦C5
ID3 (Inductive Decision Tree)
Puede expresarse recursivamente1. Seleccionar un atributo2. Colocar una rama para cada valor
del atributo3. Dividir las instancias en
subconjuntos uno por cada valor4. Repetir el proceso para cada rama
utilizando el subconjunto apropiado5. Si las instancias de una rama son de
la misma clase, el proceso termina para esa rama.
Árboles de Decisión
1. Seleccionar un atributo
Estatura Cabello Ojos Clasealto negro azul abajo negro azul aalto rubio azul oalto rojo azul oalto rubio café abajo rubio azul obajo rubio café aalto negro café a
Por atributo
Estatura Clase Cabello Clase Ojos Clasealto a negro a azul aalto a negro a azul aalto a negro a azul oalto o rojo o azul oalto o rubio a azul obajo a rubio a café abajo a rubio o café abajo o rubio o café a
Intuitivamente, cualquier hoja con instancias de solo una clase no tendrá que dividirse después
Se desea que quede un árbol pequeño
Medida de la pureza de cada nodo Escoger el atributo que produzca los nodos hijos mas puros
¿Cuál es el mejor atributo?
Información Se mide en fracciones de bit, y frecuentemente es menor a 1
Se asocia a cada nodo y se calcula con base al número de instancias de cada clase en él
Representa la cantidad de información esperada que sería necesaria para clasificar una instancia dada
Medida de Pureza
Propiedades esperadas◦Cuando queda una sola clase, la
información debe ser cero◦Cuando el número de instancias de cada
clase es igual, la información alcanza su máximo valor
La función que satisface estas propiedades es conocida como entropía
Información
Entropía
n
iiin pppppEntropía
1221 log,,,
Pi proporción de elementos en la clase Información del Sistema Información del atributo Información de cada rama Ganancia del atributo Se busca el atributo que provee la mayor
ganancia en información.
1. Seleccionar un atributo
Estatura Cabello Ojos Clasealto negro azul abajo negro azul aalto rubio azul oalto rojo azul oalto rubio café abajo rubio azul obajo rubio café aalto negro café a
Información del sistema
La entropía del sistema es:
0.4237949407 + 0.5306390622
954.083log8
38
5log85
22
)log()log(, 22212121 ppppppEntropía
Información de CabelloEjemplo
01log1
33log3
3
2
2
01log1
11log1
1
2
2
12
121212102
12
2log1log2122
1log212
42log4
24
2log42
222
22
Entropía sistema: 0.954 Entropía de la rama negro: 0 Entropía de la rama rojo: 0 Entropía de la rama rubio:1 Entropía de cabello:
Ganancia de cabello: Entropía del sistema – Entropía de Cabello G(cabello) = 0.954 -0.5 = 0.454
5.0184
081
083
Ganancia al evaluar ojos
Ejemplo
9709505945.0
4421793565.0528771238.05
3log53
52log5
222
Entropía sistema: 0.954 Entropía de la rama café: 0 Entropía de la rama azul: 0.971 Entropía de ojos:
Ganancia de ojos:
0.954 -0.607 = 0.347
607.0083
971.085
Estatura Clasealto aalto aalto aalto oalto obajo abajo abajo o
9709505945.0
4421793565.0528771238.05
3log53
52log5
222
9182958341.0
5283208336.03899750005.03
1log31
32log3
222
Entropía sistema: 0.954 bit Entropía de la rama bajo: 0.9183 Entropía de la rama alto: 0.971 Entropía de estatura:
Ganancia de estatura:
0.954 -0.9512 = 0.0028
9512375.09183.083
971.085
Cabello Clase Estatura Cabello Clase Ojos
negro a alto negro a azul
negro a alto negro a azul
negro a bajo negro a café
rojo o alto rojo o azul
rubio a alto rubio o azul
rubio o alto rubio o azul
rubio a bajo rubio a café
rubio o bajo rubio a café
outlook temperature humidity windy Playovercast hot high false Playrain mild high false Playrain cool normal false Playovercast cool normal true Playsunny cool normal false Playrain mild normal false Playsunny mild normal true Playovercast mild high true Playovercast hot normal false Playsunny hot high false Don't Playsunny hot high true Don't Playrain cool normal true Don't Playsunny mild high false Don't Playrain mild high true Don't Play
rainy
outlook
yesyesnonono
yesyesyesnono
yesyesyesyes
sunny overcast
temperature
yesyesnono
yes yesyesno
yesyesyesyesnono
hot mild cool
humidity
yesyesyesnononono
yesyesyesyesyesyesno
highnormal
windy
yesyesyesyesyesyesnono
yesyesyesnonono
false true
No se considera ningún atributo.
IS([9,5]) = -(9/14) lg (9/14) - (5/14) lg (5/14) = 0.4097 + 0.5305
= 0.940
Información del sistema
De cada rama◦ ISunny ([2,3]) = 0.5287 + 0.4421 0.971◦ IOvercast ([4,0]) = 0◦ IRainy ([3,2]) = 0.4421 + 0.5287 0.971
Del atributo◦ IOutlook =
Información
693.0
971.0145
0144
971.0145
GOutlook = IS - IOutlook= 0.940 - 0.693 = 0.247
GTemperature = IS - ITemperature= 0.940 - 0.911 = 0.029
GHumidity = IS - IHumidity= 0.940 - 0.788 = 0.152
GWindy = IS - IWindy= 0.940 - 0.892 = 0.048
Ganancia
outlook
temperature
nono
yesno
yes
hot mild cool
... ...
sunny
humidity
nonono
yesyes
high normal
... ...
outlook
sunny
... ...
outlook
sunny
windy
yesyesnono
yesno
false true
ISOutlook = 0.971 ITemperature = 0.4 GTemperature = 0.571 IHumidity = 0 GHumidity = 0.971 IWindy = 0.95098 GWindy = 0.020
Outlook - Sunny
ISOutlook = 0.971 ITemperature = 0.95098 GTemperature = 0.20 IHumidity = 0.95098 GHumidity = 0.20 IWindy = 0 GWindy = 0.971
Outlook - Rainy
outlook
windyhumidity yes
no yes yes no
sunnyovercast
rainy
high normalfalse true
Atributos altamente ramificados Atributo identificador = información 0
No es bueno para predecir la clase de instancias desconocidas
La medida de ganancia de información tiende a preferir atributos con dominios grandes
Radio de Ganancia
ID code
no no yes yes no
a b mn
c ...
Se obtiene considerando el número y tamaño de los nodos hijos en los cuales el atributo divide al conjunto sin tomar en cuenta cualquier información acerca de la clase
Se realiza la información de la partición
Radio de Ganancia
outlook temperatureinfo: 0.693 info: 0.911gain: 0.940- 0.693 0.247 gain: 0.940-0.911 0.029split info:info ( [ 5, 4, 5 ] ) 1.577 split info: info ( [ 4,6,4 ] ) 1.362gain ratio; 0.247/ 1.577 0.156 0.029/ 1.362 0.021
humidity windyinfo: 0.788 info: 0.892gain: 0.940- 0.788 0.152 gain: 0.940-0.892 0.048split info:info ( [ 7, 7 ] ) 1 split info: info ( [ 8, 6 ] ) 0.985gain ratio: 0.152 0.152 gain ratio: 0.048/ 0.985 0.049
577406283.15163871206.05305095811.02
144log14
414
5log1452 22
El índice Gini es una medida para determinar el grado al que una población comparte un recurso.
El índice Gini básicamente nos indica la equidad en la distribución de un recurso.
Los valores del índice Gini van de 0 a 1, siendo 0 la mayor equidad en la distribución y 1 representa el mayor grado de desigualdad posible.
El Índice Gini
Para calcular el índice Gini se utiliza la siguiente fórmula:
Nota: p(j|t) es la frecuencia relativa de la clase j en el nodo t.
La medida de información en un nodo es máximo 1-1/nc que es cuando existe una distribución uniforme y esto realmente no nos resulta interesante. El caso es interesante cuando el resultado es 0 ya que todos los registros pertenecen a una misma clase.
El Índice Gini
Un ejemplo de esta medida es:
Para poder hacer una separación, necesitamos del índice Gini de separación:
Esto se calcula cuando dividimos un nodo p en k particiones o hijos.
Donde ni es el número de registros en el hijo i y n es el número de registros en el nodo que se esta investigando.
El Índice Gini Como Separador
Basados en el criterio anterior, calculamos el índice Gini de separación para todas las posibles particiones y la que tenga el valor menor será la elegida para dividir el nodo.
Este criterio es utilizado en software como CART, SLIQ y SPRINT.
El Índice Gini Como Separador
Para hacer algunos experimentos y comprobar resultados, pueden acudir a la siguiente dirección:
http://www.cs.ualberta.ca/~aixplore/learning/DecisionTrees/Applet/DecisionTreeApplet.html
Applet De Prueba
Referencias
Witten I, & Frank E. Data Mining: Practical Machine Learning Tools and Technical with Java implementations. Morgan Kaufmann 2005.
Orallo Hernández J; Ramírez Quintana M; Ferri Ramírez C. Introducción a la Minería de Datos. Pearson 2008.
Referencias
Pawet Cichosz; Data Mining Algorithms explained using R. Wiley 2015.
Richard J. Roiger and Michael W. Geatz. Data Mining: A tutorial – based primer. Addison Wesley 2003.
Guion Explicativo
Este Material sirve para:◦ Explicar en qué consiste el aprendizaje
supervisado, particularmente la tarea de clasificación.
◦ Se presentan 3 algoritmos: One-Rule ID3 ID3 con Radio de Ganancia Índice GINI
Guion Explicativo
Las diapositivas deben verse en orden, y deben revisarse aproximadamente en 6 horas.
A continuación se presenta una tabla para relacionar las dispositivas con los contenidos del curso.
Guion Explicativo
Nombre del Material: Técnicas de Minería de DatosObjetivo: Presentar al alumno el aprendizaje supervizado, especificamente, algoritmos
de clasificación.
Diapositivas Explicación1 - 3 Se utilizan para ubicar el material dentro de la unidad de aprendizaje.4-5 Se presentan el tema de clasificación6-19 Se muestra el algoritmo One-Rule con valores nominales y numéricos,
ejemplos y ejercicios20-48 Árboles de Decisión, Algoritmo ID3 de Ross Quinlan49-52 Se muestra como mejorar el resultado del ID3 utilizando el Radio de Ganancia
53-57 Se presenta el índice GINI utilizado en el algoritmo CART58-59 Fuentes de Información Consultadas
