11
Métodos Descriptivos
Otros tipos de asociaciones:
Asociaciones entre jerarquías. Si existen jerarquías entre los ítems (p.ej. las familias de productos de un comercio o de un supermercado) a veces sólo es interesante buscar asociaciones inter-jerarquía y no intra-jerarquía. Esto puede reducir mucho el espacio de búsqueda.
Asociaciones negativas. A veces nos interesa conocer asociaciones negativas, p.ej. “80% de los clientes que compran pizzas congeladas no compran lentejas”. El problema es mucho más difícil en general, porque, cuando hay muchos ítems, existen muchas más combinaciones que no se dan que las que se dan.
Asociaciones con valores no binarios y/o continuos: se deben binarizar. P.ej. Si se tiene un atributo a con k posibles valores v1, …, vk (k > 2) se sustituye por k atributos con la condición (a=vi).
Con los atributos continuos se discretizan en rangos (0-5, 6-10, 11-15, …) y luego se hace el mismo procedimiento.
Asociaciones relacionales (Dehaspe and de Raedt 1997b).
12
Métodos Descriptivos
Patrones Secuenciales:
Se trata de establecer asociaciones del estilo:
“si compra X en T comprará Y en T+P”
Ejemplo:
13
Métodos Descriptivos
Patrones Secuenciales:
Ejemplo (cont.):
14
Métodos Descriptivos
Patrones Secuenciales:
Ejemplo (cont.):
Mary
15
Métodos Descriptivos
Patrones Secuenciales:
Métodos Representativos (Agrawal Srikant 1995, 1996)
AprioriAll
AprioriSome
DynamicSome
Problema: los usuarios quieren especificar restricciones sobre el tiempo máximo y mínimo entre eventos secuenciales.
Extensiones:
Minería de patrones secuenciales con restricciones.
P.ej. Sólo permitir las secuencias si los elementos adyacentes (p.ej. compras) suceden en un intervalo menor a dos meses.
16
Métodos Descriptivos
Dependencias Funcionales:
A ^ B ^ C ? D
Significa: para los mismos valores de A, B y C tenemos un solo valor de D. Es decir D es función de A, B y C.
Si representamos la parte izquierda como un conjunto de condiciones, podemos establecer una relación de orden entre las dependencias funcionales.
Esto genera un semi-retículo.
A ^ B ^ C
A ^ B
B ^ C
A ^ C
A
B
C
La búsqueda se realiza en este retículo.
(Mannila & Räihä 1994)
coste exponencial
FDEP (Flach & Savnik 1999) incluye: a) simple top-down algorithm,
b) bottom-up algorithm, and
c) bi-directional algorithm.
17
Métodos Descriptivos
Diferencias asociaciones/dependencias, dependencias funcionales y clasificación:
1. Asociaciones y Dependencias: A=a ^ B=b ^ C=c –> D=d ^ E=e
2. Asociaciones Negativas. A=a ^ B=b ^ C=c –> D<>d ^ E<>e
3. Dependencias Funcionales: A ^ B ^ C –> D
Si existe una tupla tal que A=X ^ B=Y ^ C=Z ^ D=W
entonces para cualquier otra tupla que
A=X ^ B=Y ^ C=Z entonces D=W.
O dicho de otra manera…
( SELECT MAX(COUNT(DISTINCT D))
FROM R
GROUP BY A, B, C; ) = 1;
4. Clasificación: establecen (clarifican) una dependencia funcional.
(puede ser un conjunto de dependencias de valor (1))
18
Métodos DescriptivosAprendizaje No Supervisado
Clustering (Segmentación):
Se trata de buscar agrupamientos naturales en un conjunto de datos tal que tengan semejanzas.
Métodos de Agrupamiento:
Jerárquicos: los datos se agrupan de manera arborescente (p.ej. el reino animal).
No jerárquicos: generar particiones a un nivel.
(a) Paramétricos: se asumen que las densidades condicionales de los grupos tienen cierta forma paramétrica conocida (p.e. Gaussiana), y se reduce a estimar los parámetros.
(b) No paramétricos: no asumen nada sobre el modo en el que se agrupan los objetos.
19
Métodos DescriptivosAprendizaje No Supervisado
Clustering (Segmentación). Métodos jerárquicos:
Un método sencillo consiste en ir separando individuos según su distancia (en concreto medidas derivadas de enlazado, linkage) e ir aumentando el límite de distancia para hacer grupos. Esto nos da diferentes agrupaciones a distintos niveles, de una manera jerárquica:
Se denomina Dendograma o Hierarchical Tree Plot:
20
Métodos DescriptivosAprendizaje No Supervisado
Clustering (Segmentación). Métodos jerárquicos:
Minimal Spanning Tree Clustering Algorithm
Algoritmo (dado un número de clusters deseado C).
Inicialmente considera cada ejemplo como un clúster.
Agrupa el par de clusters más cercanos para formar un nuevo cluster.
Repite el proceso anterior hasta que el número de clusters = C.
21
Métodos DescriptivosAprendizaje No Supervisado
Clustering (Segmentación). Métodos paramétricos:
El algoritmo EM (Expectation Maximization, Maximum Likelihood Estimate) (Dempster et al. 1977).
Gráficas:
Enrique Vidal
22
Métodos DescriptivosAprendizaje No Supervisado
Clustering (Segmentación). Métodos No Paramétricos
Métodos:
k-NN
k-means clustering,
online k-means clustering,
centroides
SOM (Self-Organizing Maps) o Redes Kohonen.
Otros específicos:
El algoritmo Cobweb (Fisher 1987).
El algoritmo AUTOCLASS (Cheeseman & Stutz 1996)
23
Clustering (Segmentación). Métodos No Paramétricos
1-NN (Nearest Neighbour):
Dado una serie de ejemplos en un espacio, se conecta cada punto con su punto más cercano:
La conectividad entre puntos genera los grupos.
A veces hace grupos pequeños.
Existen variantes: k-NN o como el spanning tree que para de agrupar cuando llega a un número de grupos.
Métodos DescriptivosAprendizaje No Supervisado
(Gp:) G1
(Gp:) G2
(Gp:) G3
(Gp:) G4
24
Clustering (Segmentación). Métodos No Paramétricos
k-means clustering:
Se utiliza para encontrar los k puntos más densos en un conjunto arbitrario de puntos.
Algoritmo:
1. Dividir aleatoriamente los ejemplos en k conjuntos y calcular la media (el punto medio) de cada conjunto.
2. Reasignar cada ejemplo al conjunto con el punto medio más cercano.
3. Calcular los puntos medios de los k conjuntos.
4. Repetir los pasos 2 y 3 hasta que los conjuntos no varíen.
Métodos DescriptivosAprendizaje No Supervisado
25
k-means clustering:
El valor de k se suele determinar heurísticamente.
Problemas:
Si se sabe que hay n clases, hacer k=n puede resultar en que, algunas veces, algún grupo use dos centros y dos grupos separados tengan que compartir centro.
Si k se elige muy grande, la generalización es pobre y las agrupaciones futuras serán malas.
Determinar el k ideal es difícil.
Métodos DescriptivosAprendizaje No Supervisado
Clustering (Segmentación). Métodos No Paramétricos
26
Clustering (Segmentación). Métodos No Paramétricos
On-line k-means clustering (competitive learning):
Refinamiento incremental del anterior.
Algoritmo:
1. Inicializar aleatoriamente k puntos, llamados centros.
2. Elegir el siguiente ejemplo y ver cuál es el centro más cercano. Mover el centro hacia el ejemplo. (p.ej. Distancia/2)
3. Repetir el paso 2 para cada ejemplo.
4. Repetir los pasos 2 y 3 hasta que los ejemplos capturados por cada centro no varíen.
Métodos DescriptivosAprendizaje No Supervisado
27
El valor de k se suele determinar heurísticamente.
Problemas:
Si k se elige muy pequeño, hay grupos que se quedan sin centro.
Si k se elige muy grande, hay centros que se quedan huérfanos.
Aunque esto es preferible a…
Incluso con k exacto, puede haber algún centro que quede huérfano.
Variación muy popular: LVQ (linear-vector quantization) (Kohonen 1984).
Métodos DescriptivosAprendizaje No Supervisado
Clustering (Segmentación). Métodos No Paramétricos
28
SOM (Self-Organizing Maps) o Redes Kohonen
También conocidos como LVQ (linear-vector quantization) o redes de memoria asociativa (Kohonen 1984).
Métodos DescriptivosAprendizaje No Supervisado
La matriz de neuronas de la última capa forma un grid bidimensional.
Clustering (Segmentación). Métodos No Paramétricos
29
SOM (Self-Organizing Maps) o Redes Kohonen
Durante el entrenamiento cada uno de los nodos de este grid compite con los demás para ganar cada uno de los ejemplos. Finalmente los nodos fuertes (representados con colores más oscuros) ganan más ejemplos que los nodos débiles. Al final del aprendizaje la red se estabiliza y sólo unas pocas combinaciones de pares (X,Y) obtienen registros. Estos son los grupos formados.
Métodos DescriptivosAprendizaje No Supervisado
También puede verse como una red que reduce la dimensionalidad a 2.
Por eso es común realizar una representación bidimensional con el resultado de la red para buscar grupos visualmente.
Clustering (Segmentación). Métodos No Paramétricos
30
Otros Métodos Descriptivos
Análisis Estadísticos:
Estudio de la distribución de los datos.
Estimación de Densidad
Detección datos anómalos.
Análisis de dispersión (p.ej. las funciones de separabilidad pueden considerarse como técnicas muy simples no supervisadas).
Muchas veces, estos análisis se pueden utilizar previamente para determinar el método más apropiado para un aprendizaje supervisado
También se utilizan mucho para la limpieza y preparación de datos para el uso de métodos supervisados.
 Página anterior | Volver al principio del trabajo | Página siguiente  |