variety of techniques to identify nuggets of information or decision-making knowledge in bodies of data, and extracting these in such a way that they can be put to use in the areas such as decision support, prediction, forecasting and estimation. The data is often voluminous, but as it stands of low value as no direct use can be made of it; it is the hidden information in the data that is useful.
Multidisciplinar. Areas y Técnicas Involucradas
Modelado de Dependencias:
asociaciones entre variables.
reglas y grafos (redes Bayesianas).
Componentes Principales:
compresión de la información.
Componentes Independientes:
extracción de características.
Agrupación:
hallar grupos de elementos.
Clasificación:
asignar elementos a clases.
Predicción:
estimación de valores.
Visualización:
representación gráfica.
Técnicas Involucradas
Nonlinear
Regression
Pattern
Finding
Computer Vision,
Signal Recognition
Flexible
Classification
Models
Scalable
Algorithms
Graphical
Models
Hidden
Variable
Models
Hidden
Markov
Models
Belief
Networks
Support
Vector
Machines
Mixture/
Factor Models
Classification
Trees
Association
Rules
Deformable
Templates
Model
Combining
Hot Topics (Statistics and Machine Learning)
Padhraic SmythInformation and Computer ScienceUniversity of California, Irvine
Objetivos. Un Primer Ejemplo
(Gp:) Un sistema de minería de datos aprende de los datos cómo particionar o calsificar los mismos en base a reglas de clasificación:
Ejemplo – Base de datos de clientes de un banco.
Pregunta – Un cliente que solicita un préstamo, es una buena inversión?
Regla típica formulada:
if STATUS = married and INCOME > 10000 and HOUSE_OWNER = yes
then INVESTMENT_TYPE = good
(Gp:) Clasificación:
(Gp:) Asociación:
(Gp:) Interesa obtener automáticamente reglas que relacionen unos atributos de la base de datos con otros, en base a alguna asociación:
Ejemplo – Base de datos de clientes de un banco.
Regla de Asociación:
if STATUS = married and INCOME > 10000 and HOUSE_OWNER = yes
then INVESTMENT_TYPE = good
Aplicaciones de la Minería de Datos.
(Gp:) En Internet
(Gp:) E-bussines. Perfiles de clientes, publicidad dirigida, fraude.
Buscadores "inteligentes". Generación de jerarquías, bases de conocimiento web.
Gestión del tráfico de la red. Control de eficiencia y errores.
(Gp:) Reglas de asociación:
El 60% de las personas que esquían viajan frecuentemente a Europa.
Clasificación:
Personas menores de 40 años y salario superior a 2000$ compran on-line frecuentemente.
Clustering:
Los usuarios A y B tienen gustos parecidos (acceden URLs similares).
Detección de "outliers"
El usuario A navega en Internet más del doble del tiempo promedio.
(Gp:) Gran cantidad de información (financiera, servicios, empresas, universidades, libros y hobbies), con complejas interrelaciones.
El 99% de la información no le interesa al 99% de la gente.
(Gp:) La publicidad en Internet es uno de los tópicos más actuales de Data Mining.
(Gp:) Ambiente dinámico
(Gp:) El Mundo de los Negocios
(Gp:) Banca. Grupos de clientes, préstamos, oferta de productos.
Compañías de seguros. Detección de fraude, administración de recursos.
Marketing. Publicidad dirigida, estudios de competencia.
(Gp:) Los data warehouse de las empresas contienen enormes cantidades de información sobre sus clientes y gestiones.
Ejemplo. Meteorología.
Meteorología. Teleconexiones (asociaciones espaciales), predicción.
Existen bases de datos con simulaciones de los campos atmosféricos en rejillas dadas.
Se dispone de gran cantidad de información en observatorios locales:
Precipitación, temperatura,
Viento, etc.
(Gp:) L
(Gp:) o
(Gp:) s
(Gp:)
(Gp:) 6
(Gp:)
(Gp:) p
(Gp:) r
(Gp:) i
(Gp:) m
(Gp:) e
(Gp:) r
(Gp:) o
(Gp:) s
(Gp:)
(Gp:) d
(Gp:) í
(Gp:) g
(Gp:) i
(Gp:) t
(Gp:) o
(Gp:) s
(Gp:)
(Gp:) s
(Gp:) o
(Gp:) n
(Gp:)
(Gp:) f
(Gp:) e
(Gp:) c
(Gp:) h
(Gp:) a
(Gp:)
(Gp:) c
(Gp:) o
(Gp:) n
(Gp:)
(Gp:) e
(Gp:) l
(Gp:)
(Gp:) f
(Gp:) o
(Gp:) r
(Gp:) m
(Gp:) a
(Gp:) t
(Gp:) o
(Gp:) :
(Gp:) a
(Gp:) a
(Gp:) m
(Gp:) m
(Gp:) d
(Gp:) d
(Gp:)
(Gp:) (
(Gp:) a
(Gp:) ñ
(Gp:) o
(Gp:) ,
(Gp:) m
(Gp:) e
(Gp:) s
(Gp:)
(Gp:) y
(Gp:)
(Gp:) d
(Gp:) í
(Gp:) a
(Gp:) )
(Gp:) p
(Gp:) o
(Gp:) s
(Gp:) i
(Gp:) c
(Gp:) i
(Gp:) ó
(Gp:) n
(Gp:)
(Gp:) 7
(Gp:) :
(Gp:)
(Gp:) 0
(Gp:) =
(Gp:) S
(Gp:) i
(Gp:) n
(Gp:)
(Gp:) P
(Gp:) r
(Gp:) e
(Gp:) c
(Gp:) i
(Gp:) p
(Gp:) i
(Gp:) t
(Gp:) a
(Gp:) c
(Gp:) i
(Gp:) ó
(Gp:) n
(Gp:)
(Gp:) 1
(Gp:) =
(Gp:) L
(Gp:) l
(Gp:) u
(Gp:) v
(Gp:) i
(Gp:) a
(Gp:)
(Gp:) 3
(Gp:) =
(Gp:) L
(Gp:) l
(Gp:) o
(Gp:) v
(Gp:) i
(Gp:) z
(Gp:) n
(Gp:) a
(Gp:)
(Gp:) 5
(Gp:) =
(Gp:) C
(Gp:) h
(Gp:) u
(Gp:) b
(Gp:) a
(Gp:) s
(Gp:) c
(Gp:) o
(Gp:) p
(Gp:) o
(Gp:) s
(Gp:) i
(Gp:) c
(Gp:) i
(Gp:) ó
(Gp:) n
(Gp:)
(Gp:) 8
(Gp:) :
(Gp:)
(Gp:) 0
(Gp:) =
(Gp:) S
(Gp:) i
(Gp:) n
(Gp:)
(Gp:) N
(Gp:) i
(Gp:) e
(Gp:) v
(Gp:) e
(Gp:)
(Gp:) 1
(Gp:) ,
(Gp:) 2
(Gp:) ,
(Gp:) 3
(Gp:)
(Gp:) o
(Gp:)
(Gp:) 4
(Gp:) =
(Gp:) N
(Gp:) i
(Gp:) e
(Gp:) v
(Gp:) e
(Gp:) p
(Gp:) o
(Gp:) s
(Gp:) i
(Gp:) c
(Gp:) i
(Gp:) ó
(Gp:) n
(Gp:)
(Gp:) 9
(Gp:) :
(Gp:)
(Gp:) 0
(Gp:) =
(Gp:) S
(Gp:) i
(Gp:) n
(Gp:)
(Gp:) G
(Gp:) r
(Gp:) a
(Gp:) n
(Gp:) i
(Gp:) z
(Gp:) o
(Gp:)
(Gp:) 1
(Gp:) ,
(Gp:) 2
(Gp:) ,
(Gp:) 3
(Gp:)
(Gp:) o
(Gp:)
(Gp:) 4
(Gp:) =
(Gp:) G
(Gp:) r
(Gp:) a
(Gp:) n
(Gp:) i
(Gp:) z
(Gp:) o
(Gp:) p
(Gp:) o
(Gp:) s
(Gp:) i
(Gp:) c
(Gp:) i
(Gp:) ó
(Gp:) n
(Gp:)
(Gp:) 1
(Gp:) 0
(Gp:) :
(Gp:)
(Gp:) 0
(Gp:) =
(Gp:) S
(Gp:) i
(Gp:) n
(Gp:)
(Gp:) T
(Gp:) o
(Gp:) r
(Gp:) m
(Gp:) e
(Gp:) n
(Gp:) t
(Gp:) a
(Gp:)
(Gp:) 1
(Gp:) =
(Gp:) T
(Gp:) o
(Gp:) r
(Gp:) m
(Gp:) e
(Gp:) n
(Gp:) t
(Gp:) a
(Gp:) p
(Gp:) o
(Gp:) s
(Gp:) i
(Gp:) c
(Gp:) i
(Gp:) ó
(Gp:) n
(Gp:)
(Gp:) 1
(Gp:) 1
(Gp:) :
(Gp:)
(Gp:) 0
(Gp:) =
(Gp:) S
(Gp:) i
(Gp:) n
(Gp:)
(Gp:) N
(Gp:) i
(Gp:) e
(Gp:) b
(Gp:) l
(Gp:) a
(Gp:)
(Gp:) 1
(Gp:) ,
(Gp:) 2
(Gp:) ,
(Gp:) 3
(Gp:)
(Gp:) o
(Gp:)
(Gp:) 4
(Gp:) =
(Gp:) N
(Gp:) i
(Gp:) e
(Gp:) b
(Gp:) l
(Gp:) a
(Gp:) p
(Gp:) o
(Gp:) s
(Gp:) i
(Gp:) c
(Gp:) i
(Gp:) ó
(Gp:) n
(Gp:)
(Gp:) 1
(Gp:) 2
(Gp:) :
(Gp:)
(Gp:) 0
(Gp:) =
(Gp:) S
(Gp:) i
(Gp:) n
(Gp:)
(Gp:) R
(Gp:) o
(Gp:) c
(Gp:) í
(Gp:) o
(Gp:)
(Gp:) 1
(Gp:)
(Gp:) o
(Gp:)
(Gp:) 6
(Gp:) =
(Gp:) R
(Gp:) o
(Gp:) c
(Gp:) í
(Gp:) o
(Gp:) p
(Gp:) o
(Gp:) s
(Gp:) i
(Gp:) c
(Gp:) i
(Gp:) ó
(Gp:) n
(Gp:)
(Gp:) 1
(Gp:) 3
(Gp:) :
(Gp:)
(Gp:) 0
(Gp:) =
(Gp:) S
(Gp:) i
(Gp:) n
(Gp:)
(Gp:) E
(Gp:) s
(Gp:) c
(Gp:) a
(Gp:) r
(Gp:) c
(Gp:) h
(Gp:) a
(Gp:)
(Gp:) 1
(Gp:)
(Gp:) o
(Gp:)
(Gp:) 6
(Gp:) =
(Gp:) E
(Gp:) s
(Gp:) c
(Gp:) a
(Gp:) r
(Gp:) c
(Gp:) h
(Gp:) a
(Gp:) p
(Gp:) o
(Gp:) s
(Gp:) i
(Gp:) c
(Gp:) i
(Gp:) ó
(Gp:) n
(Gp:)
(Gp:) 1
(Gp:) 4
(Gp:) :
(Gp:)
(Gp:) 0
(Gp:) =
(Gp:) S
(Gp:) i
(Gp:) n
(Gp:)
(Gp:) N
(Gp:) i
(Gp:) e
(Gp:) v
(Gp:) e
(Gp:)
(Gp:) c
(Gp:) u
(Gp:) b
(Gp:) r
(Gp:) i
(Gp:) e
(Gp:) n
(Gp:) d
(Gp:) o
(Gp:)
(Gp:) e
(Gp:) l
(Gp:)
(Gp:) S
(Gp:) u
(Gp:) e
(Gp:) l
(Gp:) o
(Gp:)
(Gp:) 1
(Gp:) =
(Gp:) N
(Gp:) i
(Gp:) e
(Gp:) v
(Gp:) e
(Gp:)
(Gp:) c
(Gp:) u
(Gp:) b
(Gp:) r
(Gp:) i
(Gp:) e
(Gp:) n
(Gp:) d
(Gp:) o
(Gp:)
(Gp:) e
(Gp:) l
(Gp:)
(Gp:) S
(Gp:) u
(Gp:) e
(Gp:) l
(Gp:) o
(Gp:) p
(Gp:) o
(Gp:) s
(Gp:) i
(Gp:) c
(Gp:) i
(Gp:) ó
(Gp:) n
(Gp:)
(Gp:) 1
(Gp:) 5
(Gp:) :
(Gp:)
(Gp:) 0
(Gp:) =
(Gp:) S
(Gp:) i
(Gp:) n
(Gp:)
(Gp:) N
(Gp:) e
(Gp:) b
(Gp:) l
(Gp:) i
(Gp:) n
(Gp:) a
(Gp:)
(Gp:) 1
(Gp:) =
(Gp:) N
(Gp:) e
(Gp:) b
(Gp:) l
(Gp:) i
(Gp:) n
(Gp:) a
(Gp:) p
(Gp:) o
(Gp:) s
(Gp:) i
(Gp:) c
(Gp:) i
(Gp:) ó
(Gp:) n
(Gp:)
(Gp:) 1
(Gp:) 6
(Gp:) :
(Gp:)
(Gp:) 0
(Gp:) =
(Gp:) S
(Gp:) i
(Gp:) n
(Gp:)
(Gp:) C
(Gp:) a
(Gp:) l
(Gp:) i
(Gp:) m
(Gp:) a
(Gp:)
(Gp:) 1
(Gp:) =
(Gp:) C
(Gp:) a
(Gp:) l
(Gp:) i
(Gp:) m
(Gp:) a
(Gp:) p
(Gp:) o
(Gp:) s
(Gp:) i
(Gp:) c
(Gp:) i
(Gp:) ó
(Gp:) n
(Gp:)
(Gp:) 1
(Gp:) 7
(Gp:) :
(Gp:)
(Gp:) 0
(Gp:) =
(Gp:) S
(Gp:) i
(Gp:) n
(Gp:)
(Gp:) V
(Gp:) i
(Gp:) e
(Gp:) n
(Gp:) t
(Gp:) o
(Gp:) >
(Gp:) 5
(Gp:) 0
(Gp:) k
(Gp:) m
(Gp:) /
(Gp:) h
(Gp:)
(Gp:) 1
(Gp:) =
(Gp:) V
(Gp:) i
(Gp:) e
(Gp:) n
(Gp:) t
(Gp:) o
(Gp:) >
(Gp:) 5
(Gp:) 0
(Gp:) k
(Gp:) m
(Gp:) /
(Gp:) h
(Gp:) p
(Gp:) o
(Gp:) s
(Gp:) i
(Gp:) c
(Gp:) i
(Gp:) ó
(Gp:) n
(Gp:)
(Gp:) 1
(Gp:) 8
(Gp:) :
(Gp:)
(Gp:) 0
(Gp:) =
(Gp:) S
(Gp:) i
(Gp:) n
(Gp:)
(Gp:) P
(Gp:) o
(Gp:) l
(Gp:) v
(Gp:) a
(Gp:) r
(Gp:) e
(Gp:) d
(Gp:) a
(Gp:)
(Gp:) 1
(Gp:) =
(Gp:) P
(Gp:) o
(Gp:) l
(Gp:) v
(Gp:) a
(Gp:) r
(Gp:) e
(Gp:) d
(Gp:) a
(Gp:) 8
(Gp:) 6
(Gp:) 0
(Gp:) 1
(Gp:) 0
(Gp:) 1
(Gp:) 5
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 1
(Gp:) 0
(Gp:) 8
(Gp:) 6
(Gp:) 0
(Gp:) 1
(Gp:) 0
(Gp:) 2
(Gp:) 1
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 1
(Gp:) 0
(Gp:) 8
(Gp:) 6
(Gp:) 0
(Gp:) 1
(Gp:) 0
(Gp:) 3
(Gp:) 5
(Gp:) 0
(Gp:) 0
(Gp:) 1
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 1
(Gp:) 0
(Gp:) 8
(Gp:) 6
(Gp:) 0
(Gp:) 1
(Gp:) 0
(Gp:) 4
(Gp:) 5
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 1
(Gp:) 0
(Gp:) 8
(Gp:) 6
(Gp:) 0
(Gp:) 1
(Gp:) 0
(Gp:) 5
(Gp:) 1
(Gp:) 0
(Gp:) 1
(Gp:) 1
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 1
(Gp:) 0
(Gp:) 8
(Gp:) 6
(Gp:) 0
(Gp:) 1
(Gp:) 0
(Gp:) 6
(Gp:) 1
(Gp:) 0
(Gp:) 1
(Gp:) 1
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 1
(Gp:) 0
(Gp:) 8
(Gp:) 6
(Gp:) 0
(Gp:) 1
(Gp:) 0
(Gp:) 7
(Gp:) 3
(Gp:) 0
(Gp:) 0
(Gp:) 1
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 1
(Gp:) 0
(Gp:) 8
(Gp:) 6
(Gp:) 0
(Gp:) 1
(Gp:) 0
(Gp:) 8
(Gp:) 5
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 1
(Gp:) 0
(Gp:) 8
(Gp:) 6
(Gp:) 0
(Gp:) 1
(Gp:) 0
(Gp:) 9
(Gp:) 5
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 1
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 8
(Gp:) 6
(Gp:) 0
(Gp:) 1
(Gp:) 1
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 1
(Gp:) 0
(Gp:) 0
(Gp:) 1
(Gp:) 1
(Gp:) 0
(Gp:) 0
(Gp:) 8
(Gp:) 6
(Gp:) 0
(Gp:) 1
(Gp:) 1
(Gp:) 1
(Gp:) 0
(Gp:) 0
(Gp:) 1
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
Relaciones entre atributos. Fórmulas y Reglas.
(Gp:) Una de las técnicas más habituales en data mining consiste en extraer las relaciones
relevantes que existan entre conjuntos de variables (itemsets) de la base de datos.
De esta forma se pueden detectar errores, fraudes, e inconsistencias fácilmente.
En el caso de bases de datos relacionales trabajaríamos con conjuntos formados por pares (atributo # valor) utilizando los registros de la base de datos. {Cliente = Pepe, Precio > 10$}
{Producto = Café}
(Gp:) Estas relaciones de asociación se pueden establecer en distintas formas:
(Gp:) Reglas if-then "reglas de asociación"
(Gp:) Son implicaciones de la forma X=>Y
if (X1= a, X3= c, X5= d) then (X4= b, X2= a)
(Gp:) La fiabilidad [confidence] es la proporción de
Aquellos registros con X que también contienen también a Y.
La relevancia [support] es la proporción de
registros que contienen tanto X como Y.
(Gp:) If Cliente is Pepeand Precio is lower than 10$ThenProducto = Café
confidence: 0.98The rule exists in 102 recordsSignificance level: error prob < 0.001
(Gp:) Asociaciones
(Gp:) Se buscan asociaciones de la forma:
(X1= a) <=> (X4= b)
De los n registros de la tabla, las dos igualdades
Son verdaderas o falsas simultáneamente
en rc casos:
fiabilidad de la asociación = rc /n
(Gp:) The value Pepe in the Cliente field is associated with the value Café in the Producto field
Rule’s fiab: 0.8
Reglas de Asociación:
(Hijos > 0) => Casado (100%, 2 casos).
Casado => Obeso (100%, 3 casos).
Asociaciones:
Casado e (Hijos > 0) están asociados (80%, 4 casos).
Obeso y casado están asociados (80%, 4 casos)
(Gp:) Ejemplo:
(Gp:) Fórmulas
(Gp:) A = B * C
Where: A = Total
B = Cantidad
C = Precio
Rule’s Accuracy Level: 0.99
The rule exists in 1890 records
(Gp:) Relaciones matemáticas X=f(Y,Z)=Y*Z
(Gp:) La fiabilidad denota el cociente entre el número de casos en que se cumple la fórmula (suponiendo un cierto error de redondeo) y el número total de casos.
(Gp:) Reglas de hortografía.
(Gp:) The value Pepe appears 52 times
in the Cliente field.
There are 2 case(s)
containing similar value(s)
{Pepr, Repe}
(Gp:) Estas reglas permiten detectar errores de ortografía. Un nombre es similar a otro pero la frecuencia en que aparecen ambos es muy diferente.
(Text Mining)
AIS [Agrawal, Imielinski & Swami]R. Agrawal, T. Imielinsky & A. SwamiIBM Almaden Research Center, 1993
Algoritmos de Búsqueda de Reglas de Asociación
La mayoría se basa en descomponer el problema en dos fases:
• FASE A: BÚSQUEDA DE GRANDES CONJUNTOS DE ATRIBUTOS.
Se buscan conjuntos de atributos con relevancia >= umbral. De momento no se busca separarlos en parte izquierda y parte derecha.
• FASE B: ESCLARECIMIENTO DE DEPENDENCIAS (REGLAS).
Se hacen particiones binarias y disjuntas de los conjuntos hallados y se calcula la confianza de cada uno. Se retienen aquellas reglas que tienen confianza >= umbral
Propiedad: cualquier subconjunto de un conjunto grande es también grande.
AIS es el primer algoritmo que se desarrolló para obtener reglas de asociación.
X=>Y [s,c] donde
Y es un único atributo,
s es la relevancia y
c su fiabilidad.
Dada una relevancia mínima Rmin:
1. i = 1 (tamaño de los conjuntos)
2. Generar un conjunto unitario en S1 para cada atributo.
3. Comprobar la relevancia de todos los conjuntos en Si. Eliminar aquellos cuya relevancia < Rmin.
4. Combinar los conjuntos en Si creando conjuntos de tamaño i+1 en Si+1.
5. Si Si no es vacío entonces i:= i+ 1. Ir a 3.
6. Si no , retornar S2 È S3 È … È Si
Fase A: Selección Grandes de Atributos
Este paso se lleva a cabo secuencialmente, recorriendo los registros de la base de datos siguiendo el contador i. Tras leer un registro de la base de datos, se hallan los conjuntos relevantes Si contenidos en el mismo. Si+1 se genera extendiendo los conjuntos hallados con otros atributos del registro.
(Gp:) Dados n registros y m atributos reglas posibles.
(Gp:) Complejidad computacional
FASE A:
S1 = {{1}, {2}, {3}, {4}, {5}} S’1:rel = {{1}:2, {2}:3, {3}:3, {5}:3}
S2 = {{1,2},{1,3},{1,5},{2, 3},{2, 5},{3, 5}} S’2:rel = {{1,3}:2, {2,3}:2, {2,5}:3, {3,5}:2}
S3 = {{1,2, 3}, {1,2, 5}, {1,3, 5}, {2,3, 5}} S’3:rel = {{2,3,5}:2}
Sfinal = S’2 È S’3 = {{1, 3}, {2, 3}, {2, 5}, {3, 5}, {2,3,5}}
Ejemplo
relevancia = 2
confianza = 0.75
FASE B:
{1} ® {3} : 1 {3} ® {1} : 0.67{2} ® {3} : 0.67 {3} ® {2} : 0.67{2} ® {5} : 1 {5} ® {2} : 1{3} ® {5} : 0.67 {5} ® {3} : 0.67{2,3} ® {5} : 1 {2,5} ® {3} : 0.67 {3,5} ® {2} : 1
El Algoritmo APRIORI
Fk : Set of frequent itemsets of size k
Ck : Set of candidate itemsets of size k
F1 = {single attribute sets} with minimum support
for ( k=2; Fk != 0; k++) do {
Ck+1 = New candidates generated from Fk
foreach entry t in the database do
Increment the count of all candidates in Ck+1 contained in t
Fk+1 = Candidates in Ck+1 with minimum support
}
Answer = Uk Fk
Every subset of a frequent itemset is also frequent=> a candidate itemset in Ck+1 can be pruned if even one of its subsets is not contained in Fk
Este algoritmo realizan múltiples pasadas sobre la base de datos para obtener los conjuntos de atributos relevantes.
En la primera pasada, se obtienen los items individuales cuya relevancia alcanza el umbral mínimo preestablecido: L[1] de conjuntos relevante.
En las siguientes iteraciones, se utiliza el último conjunto L[k] obtenido para generar un conjuntos de (k+1) atributos potencialmente relevantes (el conjunto de candidatos C[k+1]) y se obtiene la relevancia de estos candidatos para quedarnos sólo con aquéllos que son relevantes, que incluimos en el conjunto L[k+1]. Este proceso se repite hasta que no se encuentran más itemsets relevantes.
En el algoritmo AIS, los candidatos se generaban sobre la marcha, conforme se iban leyendo registros de la base de datos. Se generan innecesariamente conjuntos candidatos que de por sí nunca pueden llegar a ser relevantes.
Por su parte, en Apriori los candidatos se generan a partir de los conjuntos relevantes encontrados en la iteración anterior, única y exclusivamente. La idea subyacente es que, dado un itemset relevante, cualquier subconjunto suyo también es relevante.
Por lo tanto, los conjuntos de k atributos candidatos del conjunto C[k] pueden generarse a partir del conjunto L[k-1].
Fase de Combinación
Database D
C1
F1
C2
C2
F2
Scan D
Scan D
Ejemplo
eg1. John is a human
every human are mortals
therefore
John is mortal.
In logic:
human(John)
?h(human(h) ?mortal(h))
therefore: human(John) ?mortal(John) ? elim. rule
therefore: mortal(John) ?elim. rule
Lógica
La lógica proporciona un entorno para representar conocimiento en el que es fácil razonar.
Símbolos lógicos ~ NOT ? AND ? OR ? IMPLIES
Cuantificadores ? FOR ALL ? THERE EXISTS
Las expresiones lógicas se construyen en base a un conjunto reducido de símbolos y cuantificadores.
A language of PC, call it LPC is defined by the following rules:1. Variables p, q, r,… are in LPC. We call the above variables: undeterminate statements. 2. If a statement A is in LPC and a statement B is in LPC , then the statement (A&B) is in LPC .Similarly for the symbols: ?, ?.3. If a statement A is in LPC, then the statement ~A is in LPC .
Lógica. Representación de Conocimiento con LPC
(~A?B)
(((A?B)&(A?B)?B)
LPC is a set of statements which represent useful logical expressions for a given problem
Using the above rules and some other logical inference techniqes it is easy to reason on a given problem.
Inferencia Lógica. Deducción natural.
Natural deduction uses the definition of logical symbols for eliminating, or introducing, knowledge on a given expression.
Tablas de Verdad y Leyes Lógicas
~(~P) = P
(P Ú Q) = (~P ® Q) [or (~ P Ú Q) = (P ® Q)]
De Morgan’s laws:
~(P Ú Q) = (~P Ù ~Q)
~(P Ù Q) = (~P Ú ~Q)
Distributive laws:
P Ú (Q Ù R) = (P Ú Q) Ù (P Ú R)
P Ù (Q Ú R) = (P Ù Q) Ú (P Ù R)
Modus ponens
If P is true and P ® Q is true
then Q is true
Modus tolens
if P ® Q is true and Q is false or ~Q is true
then ~P is true
e. g., sick( student) ® not_ attend_ lecture( student)
~not_ attend_ lecture( student)
produces: ~sick( student)
Elimination
if P Ù Q is true
then P is true and Q is true
Reglas de Inferencia Lógica.
Componentes Principales:
compresión de la información.
Componentes Independientes:
extracción de características.
Modelado de Dependencias:
hallar asociaciones entre variables
redes Bayesianas
Agrupamiento:
hallar grupos de elementos
Clasificación:
asignar elementos a clases
Predicción:
estimación de valores
Visualización:
representación gráfica.
Redes Neuronales
Modelado de Dependencias (redes Bayesianas)
Redes Probabilísticas. Redes Bayesianas
Algunos problemas involucran
gran número de variables y se
conocen ciertas relaciones de
independencia entre ellas.
Obtener un modelo probabilístico
(Gp:) P
(Gp:) (
(Gp:) X
(Gp:) 1
(Gp:) ,
(Gp:)
(Gp:) X
(Gp:) 2
(Gp:) ,
(Gp:)
(Gp:) .
(Gp:) .
(Gp:) .
(Gp:) ,
(Gp:)
(Gp:) X
(Gp:) n
(Gp:) )
(Gp:) F
(Gp:) u
(Gp:) n
(Gp:) c
(Gp:) i
(Gp:) ó
(Gp:) n
(Gp:)
(Gp:) d
(Gp:) e
(Gp:) p
(Gp:) r
(Gp:) o
(Gp:) b
(Gp:) a
(Gp:) b
(Gp:) i
(Gp:) l
(Gp:) i
(Gp:) d
(Gp:) a
(Gp:) d
(Gp:)
(Gp:) c
(Gp:) o
(Gp:) n
(Gp:) j
(Gp:) u
(Gp:) n
(Gp:) t
(Gp:) a
(Gp:) {
(Gp:) X
(Gp:) 1
(Gp:) ,
(Gp:)
(Gp:) X
(Gp:) 2
(Gp:) ,
(Gp:)
(Gp:) .
(Gp:) .
(Gp:) .
(Gp:) ,
(Gp:)
(Gp:) X
(Gp:) n
(Gp:) }
(Gp:) C
(Gp:) t
(Gp:) o
(Gp:) .
(Gp:)
(Gp:) d
(Gp:) e
(Gp:)
(Gp:) v
(Gp:) a
(Gp:) r
(Gp:) i
(Gp:) a
(Gp:) b
(Gp:) l
(Gp:) e
(Gp:) s
(Gp:) a
(Gp:) l
(Gp:) e
(Gp:) a
(Gp:) t
(Gp:) o
(Gp:) r
(Gp:) i
(Gp:) a
(Gp:) s
(Gp:) I(X,Y|Z)
(Gp:) M
(Gp:) C
(Gp:) t
(Gp:) o
(Gp:) .
(Gp:)
(Gp:) d
(Gp:) e
(Gp:)
(Gp:) r
(Gp:) e
(Gp:) l
(Gp:) a
(Gp:) c
(Gp:) i
(Gp:) o
(Gp:) n
(Gp:) e
(Gp:) s
Factorización de la probabilidad !!
(Gp:) P
(Gp:) (
(Gp:) x
(Gp:) 1
(Gp:) ,
(Gp:) .
(Gp:) .
(Gp:) .
(Gp:) ,
(Gp:) x
(Gp:) n
(Gp:) )
(Gp:) =
(Gp:) n
(Gp:) i
(Gp:) =1
(Gp:) P
(Gp:) i
(Gp:) (
(Gp:) x
(Gp:) i
(Gp:) |
(Gp:) p
(Gp:) i
(Gp:) )
P
Lluvia Nieve Granizo Tormenta Niebla …
5 0 0 0 0 …
1 0 0 0 0 …
5 0 0 1 0 …
Relaciones de dependencia
Mediante un grafo dirigido donde cada variable tiene sus antecedentes.
Cuantificación
Funciones de prob.
condicionada.
 Página anterior | Volver al principio del trabajo | Página siguiente  |