Clustering Jerárquico – Aglomerativo

Vamos a ver la técnica de Clustering Jerárquico Aglomerativo. Es un enfoque de abajo hacia arriba (bottom up). Este enfonque es más popular que el Clustering Divisivo. También vamos a utilizar el enlace completo como Criterio de Enlaces. También se podría usar Enlaces Promedio.

Primero, importemos las librerías necesarias:

import numpy as np 
import pandas as pd
from scipy import ndimage 
from scipy.cluster import hierarchy 
from scipy.spatial import distance_matrix 
from matplotlib import pyplot as plt 
from sklearn import manifold, datasets 
from sklearn.cluster import AgglomerativeClustering 
from sklearn.datasets.samples_generator import make_blobs 
%matplotlib inline

Generando los Datos Aleatorios

Vamos a generar un conjunto de datos usando la clase make_blobs. Para ello usamos los siguientes parámetros:

  • n_samples: Total de puntos divididos equitativamente entre los clusters. Elegimos un número entre 10-1500
  • centers: El número de centros para generar, o las ubicaciones de centro fijas. Elegimos arrays de coordenadas x, y para generar los centros.
  • cluster_std: El desvío estándar de los clusters. Mientras más grande el número, más separados estarán los clusters. Elegimos un número entre 0.5-1.5

Guarda el resultado en X1 y en y1.

X1, y1 = make_blobs(n_samples=50, centers=[[4,4], [-2, -1], [1, 1], [10,4]], cluster_std=0.9)

Dibujo de la distribución de los puntos de los datos generados al azar

plt.scatter(X1[:, 0], X1[:, 1], marker='o') 
<matplotlib.collections.PathCollection at 0x7f9669b85dd8>

Clustering Aglomerativo

Comenzaremos haciendo el clustering de los datos aleatorios de los puntos que hemos creado.
La clase de Clustering Aglomerativo necesita dos entradas:

  • n_clusters: El número de clusters a formar y el número de centroides a generar. Pondremos 4
  • linkage: Criterio de Enlace a utilizar. El criterio de enlace determina la distancia a usar entre varias observaciones. El algoritmos agrupará en pares los clusters que minimizarán este criterio. El valor que vamos a utilizar es ‘complete’ (Se recomienda también intentar todo con ‘average’)

Guardamos el resultado en una variable llamada agglom

agglom = AgglomerativeClustering(n_clusters = 4, linkage = 'average')

Ajustamos el modelo con X2 y y2 a partir de los datos generados anteriormente.

agglom.fit(X1,y1)
AgglomerativeClustering(affinity='euclidean', compute_full_tree='auto',
            connectivity=None, linkage='average', memory=None,
            n_clusters=4, pooling_func='deprecated')

El siguiente código muestra el clustering.

# Crear una figura de 6 pulgadas (aprox 15cm) por 4 pulgadas (aprox 10 cm).
plt.figure(figsize=(6,4))

# Estas dos líneas de código se usan para reducir los puntos de datos,
# porque sino los puntos de datos se verían muy separados y dispersos.

# Crear un rango mínimo y máximo de X1.
x_min, x_max = np.min(X1, axis=0), np.max(X1, axis=0)

# Obtener la distancia promedio para X1.
X1 = (X1 - x_min) / (x_max - x_min)

# Este loop muestra todos los puntos de datos.
for i in range(X1.shape[0]):
    # Reemplaza los puntos de datos con su valor de cluster respectivo 
    # (ej. 0) está codificado con un mapa de colores (plt.cm.spectral)
    plt.text(X1[i, 0], X1[i, 1], str(y1[i]),
             color=plt.cm.nipy_spectral(agglom.labels_[i] / 10.),
             fontdict={'weight': 'bold', 'size': 9})

# Elimina los ticks x, ticks y, y los ejes x e y
plt.xticks([])
plt.yticks([])
#plt.axis('off')

# Muestra el punteado de los datos originales ántes de clustering
plt.scatter(X1[:, 0], X1[:, 1], marker='.')
# Muestra el punteo
plt.show()

Dendograma Asociado al Clustering Aglomerativo Jerárquico

Recuerda que una matriz de distancia contiene la distancia de cada punto hacia cualquier otro punto del set de datos. Usamos la función distance_matrix, la cual necesita dos entradas. Usamos la Matriz de Confusión, X2 como ambas entradas para guardar la matriz de distancia en una variable de nombre dist_matrix. Recuerda que los valores de distancia son simétricos, con una diagonal de ceros. Esta es una forma de asegurarse que tu matriz es correcta. Imprimimos dist_matrix para asegurarnos que es correcta:

dist_matrix = distance_matrix(X1,X1) 
print(dist_matrix)
[[0.         0.768101   0.99584945 ... 0.3722758  1.09321893 0.97574908]
 [0.768101   0.         0.243825   ... 0.63657093 0.34126614 0.24149435]
 [0.99584945 0.243825   0.         ... 0.87975678 0.09840829 0.04685827]
 ...
 [0.3722758  0.63657093 0.87975678 ... 0.         0.97587667 0.87704455]
 [1.09321893 0.34126614 0.09840829 ... 0.97587667 0.         0.1212985 ]
 [0.97574908 0.24149435 0.04685827 ... 0.87704455 0.1212985  0.        ]]

Usando la clase de enlace de la jerarquía, pasamos los parámetros:

  • La matriz de distancia
  • ‘complete’ se refiere al enlace completo

Guardamos el resultado en una variable de nombre Z

Z = hierarchy.linkage(dist_matrix, 'complete')

Un clustering jerárquico se visualiza como un dendograma. Cada agrupamiento se representa por una linea horizontal. La coordenada y de la linea horizontal se refiere a la similitud entre dos clusters que se agruparon, donde las observaciones se visualizan como clusters individuales. Moviéndose para arriba desde la capa inferior hacia el nodo superior, un dendograma nos permite reconstruir la historia de agrupamientos que resultaron en el clustering representado.
Guardamos el dendograma en una variable llamada dendro. Al hacer esto, el dendograma también se dibujará. Utilizando la clase dendrograma de la jerarquía, se pasa en el parámetro Z

Z = hierarchy.linkage(dist_matrix, 'complete')

Si usamos el enlace promedio podemos ver cómo el dendograma cambia.

Z = hierarchy.linkage(dist_matrix, 'average')
dendro = hierarchy.dendrogram(Z)

Ejmplo con datos de Vehículos

Imaginemos que una fábrica de vehículos desarrolla prototipos para un nuevo vehículo. Antes de presentar el nuevo modelo, el fabracante quiere saber que vehículos existen en el mercado similares al prototipo, es decir, cómo se pueden agrupar los vehículos, qué grupo es el más parecido al del modelo y de esta forma, qué modelos competirán con el nuevo.
Nuestro objetivo es utilizar métodos de clustering para encontrar los clusters más diferentes de vehículos. Se resumirán los vehículos actuales y ayudará al proceso de fabricación para tomar mejores decisiones para hacer modelos más simples.

Descargar los datos

Para descargar los datos, usaremos !wget

!wget -O cars_clus.csv https://s3-api.us-geo.objectstorage.softlayer.net/cf-courses-data/CognitiveClass/ML0101ENv3/labs/cars_clus.csv
--2020-02-21 17:21:39--  https://s3-api.us-geo.objectstorage.softlayer.net/cf-courses-data/CognitiveClass/ML0101ENv3/labs/cars_clus.csv
Resolving s3-api.us-geo.objectstorage.softlayer.net (s3-api.us-geo.objectstorage.softlayer.net)... 67.228.254.196
Connecting to s3-api.us-geo.objectstorage.softlayer.net (s3-api.us-geo.objectstorage.softlayer.net)|67.228.254.196|:443... connected.
HTTP request sent, awaiting response... 200 OK
Length: 17774 (17K)

Saving to: ‘cars_clus.csv’

cars_clus.csv 100%[===================>] 17.36K –.-KB/s in 0.02s

2020-02-21 17:21:40 (833 KB/s) – ‘cars_clus.csv’ saved [17774/17774]

Veamos las características de los fabricantes que se han secopilado sobre los modelos existentes.

filename = 'cars_clus.csv'

#Read csv
pdf = pd.read_csv(filename)
print ("Forma del set de datos: ", pdf.shape)

pdf.head(5)
Forma del set de datos:  (159, 16)
manufact model sales resale type price engine_s horsepow wheelbas width length curb_wgt fuel_cap mpg lnsales partition
0 Acura Integra 16.919 16.360 0.000 21.500 1.800 140.000 101.200 67.300 172.400 2.639 13.200 28.000 2.828 0.0
1 Acura TL 39.384 19.875 0.000 28.400 3.200 225.000 108.100 70.300 192.900 3.517 17.200 25.000 3.673 0.0
2 Acura CL 14.114 18.225 0.000  

null

3.200 225.000 106.900 70.600 192.000 3.470 17.200 26.000 2.647 0.0
3 Acura RL 8.588 29.725 0.000 42.000 3.500 210.000 114.600 71.400 196.600 3.850 18.000 22.000 2.150 0.0
4 Audi A4 20.397 22.255 0.000 23.990 1.800 150.000 102.600 68.200 178.000 2.998 16.400 27.000 3.015 0.0

Los conjuntos de datos incluyen el precio en miles (price), tamaño de motor (engine_s), caballos de fuerza (horsepow), distancia entre ejes (wheelbas), ancho (width), largo (length), peso en vació (curb_wgt), capacidad de combustible (fuel_cap) y eficiencia de combustible (mpg).

Limpieza de Datos

Limpiemos el set de datos eliminando filas que tienen valores nulos:

print ("Shape of dataset before cleaning: ", pdf.size)
pdf[[ 'sales', 'resale', 'type', 'price', 'engine_s',
       'horsepow', 'wheelbas', 'width', 'length', 'curb_wgt', 'fuel_cap',
       'mpg', 'lnsales']] = pdf[['sales', 'resale', 'type', 'price', 'engine_s',
       'horsepow', 'wheelbas', 'width', 'length', 'curb_wgt', 'fuel_cap',
       'mpg', 'lnsales']].apply(pd.to_numeric, errors='coerce')
pdf = pdf.dropna()
pdf = pdf.reset_index(drop=True)
print ("Forma del dataset luego de la limpieza: ", pdf.size)
pdf.head(5)
Shape of dataset before cleaning:  2544
Forma del dataset luego de la limpieza:  1872
manufact model sales resale type price engine_s horsepow wheelbas width length curb_wgt fuel_cap mpg lnsales partition
0 Acura Integra 16.919 16.360 0.0 21.50 1.8 140.0 101.2 67.3 172.4 2.639 13.2 28.0 2.828 0.0
1 Acura TL 39.384 19.875 0.0 28.40 3.2 225.0 108.1 70.3 192.9 3.517 17.2 25.0 3.673 0.0
2 Acura RL 8.588 29.725 0.0 42.00 3.5 210.0 114.6 71.4 196.6 3.850 18.0 22.0 2.150 0.0
3 Audi A4 20.397 22.255 0.0 23.99 1.8 150.0 102.6 68.2 178.0 2.998 16.4 27.0 3.015 0.0
4 Audi A6 18.780 23.555 0.0 33.95 2.8 200.0 108.7 76.1 192.0 3.561 18.5 22.0 2.933 0.0

Selección de Característica

Elijamos nuestro set en cuestión:

featureset = pdf[['engine_s',  'horsepow', 'wheelbas', 'width', 'length', 'curb_wgt', 'fuel_cap', 'mpg']]

Normalización

Ahora podemos normalizar el set. MinMaxScaler transforma poniendo en escala a un rango. Por omisión es (0, 1). Es decir, las escalas dee estimación se traducen cada una individualmente de forma tal de quedar entre cero y uno.

from sklearn.preprocessing import MinMaxScaler
x = featureset.values #returns a numpy array
min_max_scaler = MinMaxScaler()
feature_mtx = min_max_scaler.fit_transform(x)
feature_mtx [0:5]
array([[0.11428571, 0.21518987, 0.18655098, 0.28143713, 0.30625832,
        0.2310559 , 0.13364055, 0.43333333],
       [0.31428571, 0.43037975, 0.3362256 , 0.46107784, 0.5792277 ,
        0.50372671, 0.31797235, 0.33333333],
       [0.35714286, 0.39240506, 0.47722343, 0.52694611, 0.62849534,
        0.60714286, 0.35483871, 0.23333333],
       [0.11428571, 0.24050633, 0.21691974, 0.33532934, 0.38082557,
        0.34254658, 0.28110599, 0.4       ],
       [0.25714286, 0.36708861, 0.34924078, 0.80838323, 0.56724368,
        0.5173913 , 0.37788018, 0.23333333]])

Agrupando utilizando Scipy

En esta parte, usaremos el paquete Scipy para agrupar el set de datos. Primero, calcularemos la matriz de distancia.

import scipy
leng = feature_mtx.shape[0]
D = scipy.zeros([leng,leng])
for i in range(leng):
    for j in range(leng):
        D[i,j] = scipy.spatial.distance.euclidean(feature_mtx[i], feature_mtx[j])

En el clustering aglomerativo, en cada iteración, el algoritmo debe actualizar la matriz para refrejar la distancia del nuevo cluster formado a partir de los clusters restantes. Los métodos siguientes los soporta Scipy para calcular la distancia entre los recientementes formados clusters y para cada: – simple – completo – promedio – ponderado – centroide
Usaremos completo para nuestro caso, pero si deseas puedes cambiar para ver los diferentes resultados.

import pylab
import scipy.cluster.hierarchy
Z = hierarchy.linkage(D, 'complete')

Esencencialmente, el clustering jerárquico no necesita de un número específico de clusters. Sin embargo, algunas aplicaciones que queremos una partición de clusters disjuntos como si fueran clustering tradicional. Por lo tanto podrás usar una linea en el medio:

from scipy.cluster.hierarchy import fcluster
max_d = 3
clusters = fcluster(Z, max_d, criterion='distance')
clusters
array([ 1,  5,  5,  6,  5,  4,  6,  5,  5,  5,  5,  5,  4,  4,  5,  1,  6,
        5,  5,  5,  4,  2, 11,  6,  6,  5,  6,  5,  1,  6,  6, 10,  9,  8,
        9,  3,  5,  1,  7,  6,  5,  3,  5,  3,  8,  7,  9,  2,  6,  6,  5,
        4,  2,  1,  6,  5,  2,  7,  5,  5,  5,  4,  4,  3,  2,  6,  6,  5,
        7,  4,  7,  6,  6,  5,  3,  5,  5,  6,  5,  4,  4,  1,  6,  5,  5,
        5,  6,  4,  5,  4,  1,  6,  5,  6,  6,  5,  5,  5,  7,  7,  7,  2,
        2,  1,  2,  6,  5,  1,  1,  1,  7,  8,  1,  1,  6,  1,  1],
      dtype=int32)

También, podrás determinar la cantidad de clusters directamente:

from scipy.cluster.hierarchy import fcluster
k = 5
clusters = fcluster(Z, k, criterion='maxclust')
clusters
array([1, 3, 3, 3, 3, 2, 3, 3, 3, 3, 3, 3, 2, 2, 3, 1, 3, 3, 3, 3, 2, 1,
       5, 3, 3, 3, 3, 3, 1, 3, 3, 4, 4, 4, 4, 2, 3, 1, 3, 3, 3, 2, 3, 2,
       4, 3, 4, 1, 3, 3, 3, 2, 1, 1, 3, 3, 1, 3, 3, 3, 3, 2, 2, 2, 1, 3,
       3, 3, 3, 2, 3, 3, 3, 3, 2, 3, 3, 3, 3, 2, 2, 1, 3, 3, 3, 3, 3, 2,
       3, 2, 1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 3, 3, 1, 1, 1,
       3, 4, 1, 1, 3, 1, 1], dtype=int32)

Ahora, se trazará el dendograma:

fig = pylab.figure(figsize=(18,50))
def llf(id):
    return '[%s %s %s]' % (pdf['manufact'][id], pdf['model'][id], int(float(pdf['type'][id])) )

dendro = hierarchy.dendrogram(Z,  leaf_label_func=llf, leaf_rotation=0, leaf_font_size =12, orientation = 'right')

Clustering utilizando scikit-learn

Volvamos a construir el cluster, pero esta vez usando el paquete scikit-learn:

dist_matrix = distance_matrix(feature_mtx,feature_mtx) 
print(dist_matrix)
[[0.         0.57777143 0.75455727 ... 0.28530295 0.24917241 0.18879995]
 [0.57777143 0.         0.22798938 ... 0.36087756 0.66346677 0.62201282]
 [0.75455727 0.22798938 0.         ... 0.51727787 0.81786095 0.77930119]
 ...
 [0.28530295 0.36087756 0.51727787 ... 0.         0.41797928 0.35720492]
 [0.24917241 0.66346677 0.81786095 ... 0.41797928 0.         0.15212198]
 [0.18879995 0.62201282 0.77930119 ... 0.35720492 0.15212198 0.        ]]

Ahora, podemos usar la función ‘AgglomerativeClustering’ de la librería scikit-learn para agrupar el set de datos. Esta función hace un clustering jerárquico por medio de un enfoque de abajo hacia arriba (bottom up). El criterio de enlace determina la métrica utilizada para la estrategia de unificación:

  • Ward minimiza la suma de las diferencias cuadráticas dentro de todos los clusters. Es una enfoque minimizado y en este sentido se parece al la función de objetivo de k-medias pero está encarado con un enfoque jerárquico aglomerativo.
  • El Enlace máximo o completo, minimiza la distancia máxima entre las observaciones de pares de clusters.
  • El Enlace promedio minimiza el promedio de las distancias entre todas las observaciones de pares de clusters.
agglom = AgglomerativeClustering(n_clusters = 6, linkage = 'complete')
agglom.fit(feature_mtx)
agglom.labels_
array([1, 2, 2, 1, 2, 3, 1, 2, 2, 2, 2, 2, 3, 3, 2, 1, 1, 2, 2, 2, 5, 1,
       4, 1, 1, 2, 1, 2, 1, 1, 1, 5, 0, 0, 0, 3, 2, 1, 2, 1, 2, 3, 2, 3,
       0, 3, 0, 1, 1, 1, 2, 3, 1, 1, 1, 2, 1, 1, 2, 2, 2, 3, 3, 3, 1, 1,
       1, 2, 1, 2, 2, 1, 1, 2, 3, 2, 3, 1, 2, 3, 5, 1, 1, 2, 3, 2, 1, 3,
       2, 3, 1, 1, 2, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1,
       2, 0, 1, 1, 1, 1, 1])

Podemos agregar un nuevo campo a nuestro marco de datos para mostrar el cluster de cada fila:

pdf['cluster_'] = agglom.labels_
pdf.head()
manufact model sales resale type price engine_s horsepow wheelbas width length curb_wgt fuel_cap mpg lnsales partition cluster_
0 Acura Integra 16.919 16.360 0.0 21.50 1.8 140.0 101.2 67.3 172.4 2.639 13.2 28.0 2.828 0.0 1
1 Acura TL 39.384 19.875 0.0 28.40 3.2 225.0 108.1 70.3 192.9 3.517 17.2 25.0 3.673 0.0 2
2 Acura RL 8.588 29.725 0.0 42.00 3.5 210.0 114.6 71.4 196.6 3.850 18.0 22.0 2.150 0.0 2
3 Audi A4 20.397 22.255 0.0 23.99 1.8 150.0 102.6 68.2 178.0 2.998 16.4 27.0 3.015 0.0 1
4 Audi A6 18.780 23.555 0.0 33.95 2.8 200.0 108.7 76.1 192.0 3.561 18.5 22.0 2.933 0.0 2
import matplotlib.cm as cm
n_clusters = max(agglom.labels_)+1
colors = cm.rainbow(np.linspace(0, 1, n_clusters))
cluster_labels = list(range(0, n_clusters))

# Crear una figura de 6 pulgadas (aprox 15cm) por 4 pulgadas (aprox 10cm).
plt.figure(figsize=(16,14))

for color, label in zip(colors, cluster_labels):
    subset = pdf[pdf.cluster_ == label]
    for i in subset.index:
            plt.text(subset.horsepow[i], subset.mpg[i],str(subset['model'][i]), rotation=25) 
    plt.scatter(subset.horsepow, subset.mpg, s= subset.price*10, c=color, label='cluster'+str(label),alpha=0.5)
#    plt.scatter(subset.horsepow, subset.mpg)
plt.legend()
plt.title('Clusters')
plt.xlabel('horsepow')
plt.ylabel('mpg')
Text(0, 0.5, 'mpg')


Como se puede ver, es una distribución de cada cluster utilizando una trama esparcida, pero no está muy claro dónde es el centroide de cada cluster. Es más, hay 2 tipos de vehículos en nuestro set de datos, «truck» (valor de 1 en la columna tipo) y «car» (valor 1 en la columna tipo). Asi que los usaremos para distinguir las clases y sumarizar el cluster. Primero contamos la cantidad de casos de cada grupo:

pdf.groupby(['cluster_','type'])['cluster_'].count()
cluster_  type
0         1.0      6
1         0.0     47
          1.0      5
2         0.0     27
          1.0     11
3         0.0     10
          1.0      7
4         0.0      1
5         0.0      3
Name: cluster_, dtype: int64

Ahora, podemos examinar a las características de cada cluster:

agg_cars = pdf.groupby(['cluster_','type'])['horsepow','engine_s','mpg','price'].mean()
agg_cars
horsepow engine_s mpg price
cluster_ type
0 1.0 211.666667 4.483333 16.166667 29.024667
1 0.0 146.531915 2.246809 27.021277 20.306128
1.0 145.000000 2.580000 22.200000 17.009200
2 0.0 203.111111 3.303704 24.214815 27.750593
1.0 182.090909 3.345455 20.181818 26.265364
3 0.0 256.500000 4.410000 21.500000 42.870400
1.0 160.571429 3.071429 21.428571 21.527714
4 0.0 55.000000 1.000000 45.000000 9.235000
5 0.0 365.666667 6.233333 19.333333 66.010000

Es obvio que tenemos 3 clusters principales donde están la mayoría de los vehículos en ellos.

  • Coches:
    • Cluster 1: con algo mpg, y poco caballos de fuerza.
    • Cluster 2: con buenos mpg y caballos de fuerza, pero un precio más alto que el promedio.
    • Cluster 3: con bajo mpg, muchos caballos de fuerza y el precio más alto de todos.
  • Camiones:
    • Cluster 1: con el más alto mpg entre los camiones, y lo más bajo en caballos de fuerza y precio.
    • Cluster 2: con bajo mpg y media de caballos de fuerza, pero el precio más alto que el promedio.
    • Cluster 3: con bueno mpg y caballos de fuerza, bajo precio.

Notar que no utilizamos type, y price de autos en el proceso de clustering, sino que utilizamos clustering Jerárquico para discriminar los clusters con una precisión bastante alta.

plt.figure(figsize=(16,10))
for color, label in zip(colors, cluster_labels):
    subset = agg_cars.loc[(label,),]
    for i in subset.index:
        plt.text(subset.loc[i][0]+5, subset.loc[i][2], 'type='+str(int(i)) + ', price='+str(int(subset.loc[i][3]))+'k')
    plt.scatter(subset.horsepow, subset.mpg, s=subset.price*20, c=color, label='cluster'+str(label))
plt.legend()
plt.title('Clusters')
plt.xlabel('horsepow')
plt.ylabel('mpg')
Text(0, 0.5, 'mpg')