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 siguiente |