MINERÍA DE DATOS Y EL PROCESO DE KDD

Fayyad (1996)

 Técnicas de Minería de Datos

ARBOL REGLAS AGRUPAMIENTO RED NEURONAL
AGRUPAMIENTO O CLUSTERING
 El clustering es uno de los métodos de aprendizaje no supervisado
más importantes y busca caracterizar conceptos desconocidos a partir
de los ejemplos disponibles.
 Generalmente, en un problema real se desconoce la clase y es allí
donde el agrupamiento puede ayudar a identificar las características
comunes entre instancias.
 Al no disponer de la clase utiliza una medida de similitud para
determinar el parecido entre instancias.
¿CÓMO LOS AGRUPARÍAS?
¿CÓMO LOS AGRUPARÍAS?
ELEMENTOS BÁSICOS DEL AGRUPAMIENTO
 Identificar las características relevantes de cada tipo de elemento.
 Indicar la manera en que se realizará la comparación (DISTANCIA)
AGRUPAMIENTO O CLUSTERING
 El resultado de aplicar una técnica de clustering es una serie de
agrupamientos o clusters formados al particionar las instancias.
Long.eje mayor

Color
AGRUPAMIENTO - OBJETIVO
AGRUPAMIENTO O CLUSTERING
 Permite encontrar grupos de instancias con características similares.
 Aplicaciones
 Identificar grupos y describirlos
 Detectar clientes con características similares para ofrecer servicios
adecuados.
 Identificar alumnos con rendimientos académicos similares con el
objetivo de reducir la deserción escolar.
 Detección de casos anómalos
 Detección de fraudes.
CALIDAD DEL AGRUPAMIENTO OBTENIDO

 Un buen método de agrupamiento producirá grupos de alta calidad en

los cuales
 El parecido entre los elementos que componen un mismo grupo es
alto (intra-cluster).
 El parecido entre los elementos de grupos distintos es bajo (inter-
cluster).
AGRUPAMIENTO - OBJETIVO
 Minimizar la distancia entre los elementos de un mismo cluster
(intra-cluster)
 Maximizar la distancia entre clusters (inter-cluster)
PROCESO DE AGRUPAMIENTO
 Seleccionar las características relevantes
 Definir una representación adecuada.
 Definir la medida de similitud a utilidad (medida de distancia).
Depende del problema.
 Aplicar un algoritmo de agrupamiento
 Validar los grupos obtenidos y de ser necesario volver a repetir el
proceso.
PROCESO DE AGRUPAMIENTO
TIPOS DE ALGORITMOS DE AGRUPAMIENTO
 Algoritmo Partitivo
 Particionan los datos creando un número K de clusters.
 Una instancia pertenece a un único grupo.

 Algoritmo Jerárquico
 Generan una estructura jerárquica de clusters que permiten ver las particiones de
las instancias con distinta granularidad.
 Una instancia pertenece a un único grupo.

 Algoritmo probabilista
 Los clusters se generan con un método probabilístico
ALGORITMOS DE CLUSTERING PARTITIVOS
 Obtiene una única partición de los datos
K-MEDIAS
 El algoritmo K-Medias fue propuesto por MacQueen, en 1967.
 Requiere conocer a priori el número K de grupos a formar.
 El algoritmo está basado en la minimización de la distancia interna (la
suma de las distancias de los ejemplos asignados a un agrupamiento al
centroide de dicho agrupamiento).
 De hecho, este algoritmo minimiza la suma de las distancias al cuadrado
de cada ejemplo al centroide de su agrupamiento.
K-MEDIAS
 Características
 El algoritmo es sencillo y eficiente.
 Procesa los ejemplos secuencialmente (por lo que requiere un
almacenamiento mínimo).
 Está sesgado por el orden de presentación de los ejemplos (los
primeros ejemplos determinan la configuración inicial de los
agrupamientos)
 Su comportamiento depende enormemente del parámetro K.
ALGORITMO K-MEDIAS
 Elegir aleatoriamente K ejemplos de entrada como centros iniciales.
 Repetir
 Redistribuir los ejemplos entre los clusters utilizando la mínima
distancia euclídea al cuadrado como clasificador.
 Calcular los centros de los K clusters.
hasta que no cambien los centros de los clusters

KMedias.py
Agrupando los ejemplos de PuntosClusters.csv usando
k-medias con k = 3 clusters

El proceso inicia
tomando k=3
ejemplos como
centros iniciales
Agrupando los ejemplos de PuntosClusters.csv usando
k-medias con k = 3 clusters

Para cada ejemplo se

identifica el centro más
cercano usando alguna
medida de proximidad

𝑿 = 𝒙𝟏 , 𝒙𝟐
Ci = 𝒄𝒊𝟏 , 𝒄𝒊𝟐 i=1,2,3
dist2(Ci,X) = (𝒄𝒊𝟏 − 𝒙𝟏 )𝟐 + (𝒄𝒊𝟐 − 𝒙𝟐 )𝟐
Agrupando los ejemplos de PuntosClusters.csv usando
k-medias con k = 3 clusters

Para cada ejemplo se

identifica el centro más
cercano usando alguna
medida de proximidad
Agrupando los ejemplos de PuntosClusters.csv usando
k-medias con k = 3 clusters

Repetir esto para

todos los ejemplos.

Asignar cada
ejemplo al centro
más cercano
Agrupando los ejemplos de PuntosClusters.csv usando
k-medias con k = 3 clusters

Recalcular la
posición de los
centros.

 Cada centro se reubica

promediando los valores
de los atributos de los
ejemplos que los
conforman.
Agrupando los ejemplos de PuntosClusters.csv usando
k-medias con k = 3 clusters

Recalcular la
posición de los
centros.

 Cada centro se reubica

promediando los valores
de los atributos de los
ejemplos que los
conforman.
Agrupando los ejemplos de PuntosClusters.csv usando
k-medias con k = 3 clusters

 Repetir ambos pasos

 Asignar cada ejemplo al
centro más cercano
 Recalcular los centros
hasta que los centros
no cambien
Agrupando los ejemplos de PuntosClusters.csv usando
k-medias con k = 3 clusters

 Repetir ambos pasos

 Asignar cada ejemplo al
centro más cercano
 Recalcular los centros
hasta que los centros
no cambien
Agrupando los ejemplos de PuntosClusters.csv usando
k-medias con k = 3 clusters

 Repetir ambos pasos

 Asignar cada ejemplo al
centro más cercano
 Recalcular los centros
hasta que los centros
no cambien
Agrupando los ejemplos de PuntosClusters.csv usando
k-medias con k = 3 clusters

 Repetir ambos pasos

 Asignar cada ejemplo al
centro más cercano
 Recalcular los centros
hasta que los centros
no cambien
Agrupando los ejemplos de PuntosClusters.csv usando
k-medias con k = 3 clusters

 Repetir ambos pasos

 Asignar cada ejemplo al
centro más cercano
 Recalcular los centros
hasta que los centros
no cambien
Agrupando los ejemplos de PuntosClusters.csv usando
k-medias con k = 3 clusters

 Repetir ambos pasos

 Asignar cada ejemplo al
centro más cercano
 Recalcular los centros
hasta que los centros
no cambien
Agrupando los ejemplos de PuntosClusters.csv usando
k-medias con k = 3 clusters

 Repetir ambos pasos

 Asignar cada ejemplo al
centro más cercano
 Recalcular los centros
hasta que los centros
no cambien
Agrupando los ejemplos de PuntosClusters.csv usando
k-medias con k = 3 clusters

 Repetir ambos pasos

 Asignar cada ejemplo al
centro más cercano
 Recalcular los centros
hasta que los centros
no cambien
Agrupando los ejemplos de PuntosClusters.csv usando
k-medias con k = 3 clusters

 Repetir ambos pasos

 Asignar cada ejemplo al
centro más cercano
 Recalcular los centros
hasta que los centros
no cambien
Agrupando los ejemplos de PuntosClusters.csv usando
k-medias con k = 3 clusters

El modelo resultante
estará definido por los
centros (individuos
promedio) de cada grupo.

𝐶1 = 4.9972 , 4.9380

𝐶2 = 7.5672 , 5.9504

𝐶3 = 6.4782 , 7.9324
Utilizando el modelo obtenido con k-medias

 A qué grupo asignaría el nuevo ejemplo? A cuál de los 3 se parece más?

Calcular la
distancia del nuevo
ejemplo a cada
centro y asignarlo
al cluster más
cercano
DEMOSTRACIÓN DE K-MEANS MEDIANTE UN EJEMPLO DE
CARTAS DE PÓKER

https://www.youtube.com/watch?v=zHbxbb2ye3E
 K-MEDIAS DESDE RAPIDMINER
Utilice los datos del
archivo
PuntosClusters.csv
K-MEDIAS DESDE RAPIDMINER
K-MEDIAS DESDE RAPIDMINER
K-MEDIAS DESDE RAPIDMINER
 Modelo obtenido como resultado del agrupamiento con k=3
VISUALIZACIÓN DE LOS GRUPOS
VISUALIZACIÓN DE LOS GRUPOS
VISUALIZANDO LOS VALORES DE CLASE EN CADA GRUPO

Es preciso disponer del label original y

de la etiqueta de cluster por lo que no
debe estar tildada esta opción
VISUALIZANDO LOS VALORES DE CLASE EN CADA GRUPO

Falta configurarlo
VISUALIZANDO LOS VALORES DE CLASE EN CADA GRUPO
VISUALIZANDO LOS VALORES DE CLASE EN CADA GRUPO
RESULTADO DE LA AGREGACIÓN
 EJEMPLO 2 - AGRUPANDO FLORES DE IRIS

 Se dispone de información 3 tipos de flores Iris

Setosa Versicolor Virginica

https://archive.ics.uci.edu/ml/datasets/Iris
EJEMPLO 2 - AGRUPANDO FLORES DE IRIS

Id sepallength sepalwidth petallength petalwidth class

1 5,1 3,5 1,4 0,2 Iris-setosa
2 4,9 3,0 1,4 0,2 Iris-setosa
… … … … … …
95 5,6 2,7 4,2 1,3 Iris-versicolor
96 5,7 3,0 4,2 1,2 Iris-versicolor
97 5,7 2,9 4,2 1,3 Iris-versicolor
… … … … … …
149 6,2 3,4 5,4 2,3 Iris-virginica
150 5,9 3,0 5,1 1,8 Iris-virginica

https://archive.ics.uci.edu/ml/datasets/Iris
EJEMPLO 2 – CARACTERÍSTICAS DE FLORES DE IRIS
EJEMPLO 2 - AGRUPANDO FLORES DE IRIS
 Sebusca identificar atributos con valores distintos entre
grupos
EJEMPLO 2 - AGRUPANDO CON K-MEDIAS (K=3)
 Normalizando linealmente entre 0 y 1 los valores de cada atributo
ANTES de agrupar se obtiene lo siguiente:
EJEMPLO 2 - AGRUPANDO CON K-MEDIAS (K=3)
 Normalizando los atributos ANTES de agrupar (transformación Z de
Rapid Miner) se obtiene lo siguiente:
EJEMPLO 2 - AGRUPANDO FLORES DE IRIS
EJEMPLO 2 - AGRUPANDO FLORES DE IRIS
TIPOS DE ALGORITMOS DE AGRUPAMIENTO
 Algoritmo Partitivo
 Particionan los datos creando un número K de clusters.
 Una instancia pertenece a un único grupo.

 Algoritmo Jerárquico
 Generan una estructura jerárquica de clusters que permiten ver las particiones de
las instancias con distinta granularidad.
 Una instancia pertenece a un único grupo.

 Algoritmo probabilista
 Los clusters se generan con un método probabilístico
ALGORITMO DE CLUSTERING JERÁRQUICOS
Todos los algoritmos
jerárquicos producen
como resultado un
dendrograma

A partir del
dendrograma se pueden
obtener distintas
particiones (estructuras
de clusters) de los datos
ALGORITMO DE CLUSTERING JERÁRQUICOS
AGRUPAMIENTO JERARQUICO
ALGORITMO JERÁRQUICO AGLOMERATIVO

 Paso 1: A cada instancia se le asigna un cluster, de modo que

inicialmente si hay N instancias se tienen N clusters de 1 elemento
cada uno.
 Paso 2: Calcular la distancia entre clusters y unir en uno solo a
los dos más cercanos.
 Paso 3: Calcular la distancia del nuevo cluster a los restantes.
 Paso 4: Repetir los pasos 2 y 3 hasta que todas las instancias
pertenezcan al mismo cluster
MEDIDAS DE CONECTIVIDAD
(LINKAGE MEASURES )

 Enlace simple (single-linkage)

 La similitud entre dos clusters se calcula como la similitud de los dos
puntos más cercanos pertenecientes a los diferentes clusters.
𝐦𝐢𝐧{𝒅𝒊𝒔𝒕 𝒂, 𝒃 : 𝒂 ∈ 𝑨, 𝒃 ∈ 𝑩}
MEDIDAS DE CONECTIVIDAD
(LINKAGE MEASURES )

 Enlace completo (complete-linkage)

 La similitud entre dos clusters se calcula como la similitud de los dos puntos
más lejanos pertenecientes a los diferentes clusters.
𝐦𝐚𝐱{𝒅𝒊𝒔𝒕 𝒂, 𝒃 : 𝒂 ∈ 𝑨, 𝒃 ∈ 𝑩}
MEDIDAS DE CONECTIVIDAD
(LINKAGE MEASURES )

 Enlace promedio (average-linkage)

 La distancia entre dos grupos se calcula promediando las distancias entre
todos los pares que se puedan formar tomando una instancia de cada cluster.
𝟏
෍ ෍ 𝒅𝒊𝒔𝒕(𝒂, 𝒃)
𝑨 |𝑩|
𝒂∈𝑨 𝒃∈𝑩
EJEMPLO
 Aplique un algoritmo jerárquico aglomerativo para agrupar las
instancias A, B, C y D cuya matriz de distancias se indica a
continuación

A B C D
A 0 14 10 6
B 14 0 8 4
C 10 8 0 5
D 6 4 5 0
 8 C
B 5
4
EJEMPLO USANDO ENLACE SIMPLE D
14
6 10

A C B D

B-D
 8 C
B 5
4
EJEMPLO USANDO ENLACE SIMPLE D
14
6 10

A C B D

B-D

B-C-D
 8 C
B 5
4
EJEMPLO USANDO ENLACE SIMPLE D
14
6 10

A C B D

B-D

B-C-D

A-B-C-D
 8 C
B 5
4
EJEMPLO USANDO ENLACE COMPLETO D
14
6 10

A C B D

B-D
 8 C
B 5
4
EJEMPLO USANDO ENLACE COMPLETO D
14
6 10

A C B D

B-D

B-C-D
 8 C
B 5
4
EJEMPLO USANDO ENLACE COMPLETO D
14
6 10

A C B D

B-D

B-C-D

A-B-C-D
CLUSTERING JERÁRQUICO CON RAPID MINER

Clustering
(Agglomerative Clustering)
CLUSTERING JERÁRQUICO CON RAPID MINER
CLUSTERING JERÁRQUICO CON RAPID MINER
 Puede seleccionarse la cantidad de grupos para cortar el
dendrograma

Flatten Clustering

Probar con distintos números de clusters y observar los resultados

AGRUPAMIENTO PROBABILISTA

 Los algoritmos basados en probabilidad, en lugar de asociar una

instancia a un único cluster, utilizan la probabilidad de que las
instancias pertenezcan a cada uno de los clusters.
 Utilizan un conjunto de k distribuciones de probabilidad para
representar k clusters.
 El problema es determinar los parámetros que modelan las
distribuciones
ALGORITMO EM (EXPECTATION - MAXIMIZATION)
 Estimar los valores de los parámetros que modelan los clustes.
 Repetir hasta que no mejoren los agrupamientos
 Esperanza (expectation): Utiliza los valores de los parámetros,
iniciales o proporcionados por el paso Maximization, obteniendo
diferentes formas de la fdp (función de densidad de probabilidad)
buscada.
 Maximización (maximization): Recalcular los parámetros de la
distribución haciendo uso de los datos proporcionados por el paso
anterior.
ALGORITMO EM (EXPECTATION - MAXIMIZATION)
 Se puede usar siempre que se conozca la forma de la distribución
(ej : gaussiana)
 Ventajas
 Suele dar buenos resultados por ser más general que otros métodos
de agrupamiento.
 Es simple de implementar.

 Desventajas
 Puede converger a un óptimo local.
 Tiene un costo computacional alto en especial si se utilizan muchas
distribuciones de probabilidad.
EJEMPLO – PUNTOSCLUSTERS.CSV

Expectation Maximization
Clustering
MODELO OBTENIDO
 Para cada cluster se indica
 La cantidad de ejemplos
 La probabilidad de que un ejemplo
pertenezca a cada cluster
 La media (centroide)
 La matriz de covarianza que
define la forma de la gaussiana
EJERCICIO
 Analice los valores del atributo X2 del archivo PuntosClusters.csv
utilizando:
 K-medias con K=2
 Agrupamiento jerárquico visualizando sólo 2 grupos
 EM con K=2
ALGORITMO K-MEDIAS CON K=2
AGRUPAMIENTO JERÁRQUICO
ALGORITMO EM