16. Clustering#

Un clúster es una agrupación de objetos que comparten similitudes, y los objetos que pertenecen a diferentes clústeres presentan diferencias. Encontrar grupos en los datos es el objetivo principal de la agrupación en clústeres.

El objetivo es minimizar las diferencias dentro de cada grupo y maximizar las diferencias entre los clústeres.

La agrupación en clústeres consiste en dividir un conjunto de datos finito sin etiquetar en subconuntos de datos diferenciados que emergen de estreucturas subyacentes en los datos.

Sea

\[ \mathbf{X}= \{\mathbf{x}_1,\mathbf{x}_2,\ldots,\mathbf{x}_i,\ldots,\mathbf{x}_N\} \]

un conjunto de objetos de entrada donde \(\mathbf{x}_i = \left(x_{i1},x_{i2},\ldots,x_{ij},\ldots,x_{id}\right) \in \mathbb{R}^d\), y \(x_{ij}\) es una característica (atributo, dimensión o variable). Una partición \(K\) de \(\mathbf{X}\), \(C = \{C_1,\ldots,C_K\}\) (\(K\leq N\)) es una partición dura si:

  • Cada clúster debe tener al menos un elemento: \(C_i\neq \emptyset\), \(i=1,\ldots,K\).

  • La unión de todos los clústers es el conjunto de entrada \(\mathbf{X}\): \(\bigcup_{i=1}^KC_i=\mathbf{X}\).

  • Si un objeto pertenece a un cluster, no puede pertenecer a otro cluster: \(C_i\cap C_j = \emptyset\), \(i,j=1,\ldots,K\) and \(i\neq j\).

16.1. K-means#

El algoritmo k-means es quizás el método de agrupación más utilizado. Después de haber sido estudiado durante varias décadas, sirve como base para muchas técnicas de agrupación más sofisticadas.

16.1.1. Ejemplo#

Veamos un ejemplo de k-means mediante la generación de clústers aleatorios (make_blobs) y k=3.

Preámbulo y datos

#%matplotlib notebook
import numpy as np
import pandas as pd
import seaborn as sn
import matplotlib.pyplot as plt

from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans
from shared_utilities import plot_labelled_scatter

X, y = make_blobs(random_state = 10)

kmeans = KMeans(n_init = 3,n_clusters = 3)
kmeans.fit(X)

plot_labelled_scatter(X, kmeans.labels_, ['Cluster 1', 'Cluster 2', 'Cluster 3'])
_images/2c530138aa843618d5fa258d1187c7d2b67b8924ff768d40c89e2075c8573ed2.png

Algoritmo

Entradas:

  • Conjunto de patrones en \(\mathbb{R}^n\).

  • \(k\) número de grupos a formar.

Salidas:

  • Una partición del espacio de patrones, tal que, optimiza la varianza global.

Inicio:

Asignar aleatoreamente un número, del 1 a \(K\) a cada observación. Estos funcionan como asignaciones iniciales para las observaciones.

Repetición

  1. Para cada uno de los K conglomerados, calcular el centroide del conglomerado. El k-ésimo centroide del grupo es el vector de las \(p\) medias de características para las observaciones en el k-ésimo grupo.

  2. Asignar cada observación al conglomerado cuyo centroide es el más cercano (donde más cercano se define utilizando la distancia euclidiana).

Hasta La última partición obtenida, (idéntica a la de la iteración anterior ) es la respuesta final del algoritmo.

16.1.2. Ejemplo: clasificación de frutas#

Ejemplo que muestra k-medias para encontrar 4 conglomerados en el conjunto de datos de frutas. Tenga en cuenta que, en general, es importante escalar las características individuales antes de aplicar la agrupación en clústeres de k-medias.

from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans
from shared_utilities import plot_labelled_scatter
from sklearn.preprocessing import MinMaxScaler
import pandas as pd

uu = 'https://raw.githubusercontent.com/vmoprojs/DataLectures/refs/heads/master/fruit_data_with_colors.txt'
fruits = pd.read_table(uu)
X_fruits = fruits[['mass','width','height', 'color_score']].to_numpy()
y_fruits = fruits[['fruit_label']] - 1

X_fruits_normalized = MinMaxScaler().fit(X_fruits).transform(X_fruits)  

kmeans = KMeans(n_init = 4, random_state = 0,n_clusters = 4)
kmeans.fit(X_fruits_normalized)

plot_labelled_scatter(X_fruits_normalized, kmeans.labels_, 
                      ['Cluster 1', 'Cluster 2', 'Cluster 3', 'Cluster 4'])
_images/1eac6072404824f9b7f6a93e761a81be44d3d0e971938887a419edc4a6cc59a3.png 
# https://scikit-learn-extra.readthedocs.io/en/latest/index.html
from sklearn_extra.cluster import KMedoids
kmedoides = KMedoids(n_clusters = 4, random_state = 0)
kmedoides.fit(X_fruits_normalized)

plot_labelled_scatter(X_fruits_normalized, kmedoides.labels_, 
                      ['Cluster 1', 'Cluster 2', 'Cluster 3', 'Cluster 4'])
_images/b512385e1c3f377c3d9fff4c4b6b2201a135bae64fad050687f082986b3cbbd7.png

16.2. Clustering Jerárquico: Aglomerativo#

Una desventaja potencial del agrupamiento K-medias es que requiere que especifiquemos previamente el número de agrupamientos K.

El agrupamiento jerárquico es un enfoque alternativo que no requiere que nos comprometamos con una elección particular de K.

El agrupamiento jerárquico tiene una ventaja adicional sobre el agrupamiento K-medias, ya que da como resultado una atractiva representación basada en árboles de las observaciones, llamada dendrograma.

Algoritmo

Entradas:

  • Conjunto de patrones en cualquier espacio.

Salidas:

  • Dendograma de agrupamiento

Inicio:

  • Seleccionar una función de comparación entre patrones.

  • Calcular la Matriz Global de Semejanza/Diferencia entre grupos.

Repetición

  1. Identificar la menor diferencia entre grupos y fusionar dichos grupos en un nuevo grupo con etiqueta única.

  2. Actualizar la matriz de sem/dif, eliminando el renglón y columna de los grupos fusionados y agregando un nuevo renglón y columna para el nuevo grupo

  3. Registrar la fusión realizada en el dendrograma

Hasta Terminar cuando todos los patrones se encuentren agrupados en un solo grupo.

En Python, el método AgglomerativeClustering nos permite ejecutar clustering jerárquico.

from sklearn.datasets import make_blobs
from sklearn.cluster import AgglomerativeClustering
from shared_utilities import plot_labelled_scatter

X, y = make_blobs(random_state = 10)

cls = AgglomerativeClustering(n_clusters = 3)
cls_assignment = cls.fit_predict(X)

plot_labelled_scatter(X, cls_assignment, 
        ['Cluster 1', 'Cluster 2', 'Cluster 3'])
_images/a985ac4c7a7928368232808217f8bd30055fb44f67fa26f7ba17e55c2f8e29ab.png 
X, y = make_blobs(random_state = 10, n_samples = 10)
plot_labelled_scatter(X, y, 
        ['Cluster 1', 'Cluster 2', 'Cluster 3'])
print(X)
_images/a01ad60831aaa2e7909a1fa73eda4569764b7cf9a18bd5ffc81ee1c05b5ad530.png 
[[  5.69192445  -9.47641249]
 [  1.70789903   6.00435173]
 [  0.23621041  -3.11909976]
 [  2.90159483   5.42121526]
 [  5.85943906  -8.38192364]
 [  6.04774884 -10.30504657]
 [ -2.00758803  -7.24743939]
 [  1.45467725  -6.58387198]
 [  1.53636249   5.11121453]
 [  5.4307043   -9.75956122]]

Creamos el dendograma

from scipy.cluster.hierarchy import dendrogram,linkage
plt.figure()
dendrogram(linkage(X, 'complete'))
plt.show()
_images/b93f2f1218bcf6985338c3b9c8f830d12224f139950154cc15ee2e2c6977fc9b.png

  • Cada hoja del dendrograma representa una de las \(n\) observaciones.

  • A medida que subimos por el árbol, algunas hojas comienzan a fusionarse en ramas. Estos corresponden a observaciones que son similares entre sí.

  • Cuanto antes (más abajo en el árbol) se produzcan fusiones, más similares serán los grupos de observaciones entre sí. Por otro lado, las observaciones que se fusionan más tarde (cerca de la parte superior del árbol) pueden ser bastante diferentes.

  • La altura de esta fusión, medida en el eje vertical, indica cuán diferentes son las dos observaciones. Por lo tanto, las observaciones que se fusionan en la parte inferior del árbol son bastante similares entre sí, mientras que las observaciones que se fusionan cerca de la parte superior del árbol tenderán a ser bastante diferentes.

16.2.1. Funciones para fusionar grupos#

_images/10_fig1.png

  • Complete: Disimilitud máxima entre conglomerados. Calcule todas las diferencias por pares entre las observaciones en el grupo \(A\) y las observaciones en el grupo \(B\), y registre la mayor de estas diferencias.

  • Single: Disimilitud mínima entre conglomerados. Calcule todas las diferencias por pares entre las observaciones en el grupo \(A\) y las observaciones en el grupo \(B\), y registre la más pequeña de estas diferencias. El enlace único puede dar como resultado conglomerados extendidos y finales en los que las observaciones individuales se fusionan una a la vez.

  • Average: Diferencia media entre grupos. Calcule todas las diferencias por pares entre las observaciones en el grupo \(A\) y las observaciones en el grupo \(B\), y registre el promedio de estas diferencias.

  • Centroid: Disimilitud entre el centroide para el grupo \(A\) (un vector de medias de longitud \(p\)) y el centroide para el grupo \(B\).

En Python usamos los métodos:

  • dendrogram: para elaborar el dendograma.

  • linkage: Realiza agrupamiento jerárquico/aglomerativo.

plt.figure()
plt.title('Linkage: Complete')
dendrogram(linkage(X, 'complete'))
plt.show()

plt.figure()
plt.title('Linkage: Single')
dendrogram(linkage(X, 'single'))
plt.show()

plt.figure()
plt.title('Linkage: Average')
dendrogram(linkage(X, 'average'))
plt.show()

plt.figure()
plt.title('Linkage: Centroid')
dendrogram(linkage(X, 'centroid'))
plt.show()
_images/4d7898338b9ddae9ef9fa8f1044a685a5ed460069fd4068d17444332ac22aef6.png _images/c34dd92343852cee283b05fad54da412c722d874f3207f34831e6d88bb64a459.png _images/d3725e7afc65229397bb88c88a4eaeb7fa055d5ab9ca8217794f6ab279f396e7.png _images/9f91372fbf04cfc14f77b64008df397db877b81af5687f06ffc751f7dac881b0.png

16.3. DBSCAN clustering#

Es un algoritmo no supervisado que tienen por objetivo descubrir grupos a partir de formas arbitrarias de cualquier conjunto de datos y al mismo tiempo puede distinguir noise points que no forman parte de ningún grupo.

Parámetros

  • Epsilon (\(\epsilon\)): define el radio de una bola.

  • MinPts: Número mínimo de puntos requeridos dentro de la bola de radio \(\epsilon\)

Definiciones:

  • Bola Cerrada: \(B_{\epsilon}(p)=B(p;\epsilon)=\{x\in X\mid d(x,p)\leq \epsilon\}\), donde \(p\) es el centro y \(\epsilon\) es el radio

  • Core point: Si, dentro de la bola, contiene un número de puntos mayor o igual a MinPts

  • Border point: Si, dentro de la bola, contiene al menos un core point

  • Noise point: Si, dentro de la bola, no contiene ningún core point

_images/dbscan.jpg

En Python:

  • DBSCAN es el método para ejecutar el algortimo.

from sklearn.cluster import DBSCAN
from sklearn.datasets import make_blobs

X, y = make_blobs(random_state = 9, n_samples = 25)

dbscan = DBSCAN(eps = 2, min_samples = 2)

cls = dbscan.fit_predict(X)
print("Cluster membership values:\n{}".format(cls))

plot_labelled_scatter(X, cls + 1, 
        ['Noise', 'Cluster 0', 'Cluster 1', 'Cluster 2'])

Cluster membership values:
[ 0  1  0  2  0  0  0  2  2 -1  1  2  0  0 -1  0  0  1 -1  1  1  2  2  2
  1]
_images/06b2654b033d579fd8b7ae461df44cc9c1132ad62a7ba1600f2cb4fc38871673.png

16.3.1. Ejemplo: clasificación de clientes#

uu = "https://raw.githubusercontent.com/vmoprojs/DataLectures/master/Mall_Customers.csv"
datos = pd.read_csv(uu)


dbDat = datos.iloc[:,3:5]
dbDat.describe()
AnnualIncome SpendingScore
count 200.000000 200.000000
mean 60.560000 50.200000
std 26.264721 25.823522
min 15.000000 1.000000
25% 41.500000 34.750000
50% 61.500000 50.000000
75% 78.000000 73.000000
max 137.000000 99.000000 
plt.figure()
plt.scatter(dbDat.AnnualIncome,dbDat.SpendingScore)
plt.show()
_images/f965bb5dcf99c9ed5c5177fffd58e3cebc84e619cbfff07872a4ad4d489ab8ef.png 
from scipy.spatial import distance_matrix
dd = pd.DataFrame(distance_matrix(dbDat.values, dbDat.values), index=dbDat.index, columns=dbDat.index)
n = len(np.sort(dd.values))
dd = np.sort(dd.values[np.triu_indices(n, k = 1)])

plt.figure()
plt.plot(dd)
plt.show()
_images/c6329e683059f7300503c1d34cc2102057e00b3ad47f80d4e11821fe215242b3.png 
dbscan = DBSCAN(eps = 10, min_samples = 3)

cls = dbscan.fit_predict(dbDat)
print("Cluster membership values:\n{}".format(cls))

plot_labelled_scatter(dbDat.values, cls + 1, 
        ['Noise', 'Cluster 0', 'Cluster 1', 'Cluster 2'])

Cluster membership values:
[ 0  0  0  0  0  0  0  1  0  0  0  1  0  0  0  0  0  0  0  1  0  0  0  0
  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  0  0  0  2  0  2  0  2  3  2  3  2  0  2  3  2  3  2  3  2  3  2  0  2
  3  2  0  2  3  2  3  2  3  2  3  2  3  2  3  2  0  2  3  2  3  2  3  2
  3  2  3  2  3  2  3  2  3  2  3  2  3  2  3  2  3  2  3 -1  3  2  3 -1
 -1 -1 -1 -1 -1 -1 -1 -1]
_images/9fffda6f3dc94c0aa5eaec2781cead3f33d766319b7de997ee9b044cb63b7538.png

Un ejemplo combinado

www = "https://stat.ethz.ch/Teaching/Datasets/WBL/crime2.dat"
crime = pd.read_csv(www,sep=" ")
crime.describe()
murder rape robbery assault burglary larceny auto.theft
count 50.000000 50.00000 50.000000 50.000000 50.000000 50.000000 50.000000
mean 7.444000 25.73400 124.092000 211.300000 1291.904000 2671.288000 377.526000
std 3.866769 10.75963 88.348567 100.253049 432.455711 725.908707 193.394418
min 0.900000 9.00000 13.300000 43.800000 446.100000 1239.900000 144.400000
25% 4.225000 18.32500 64.950000 148.850000 1000.075000 2248.900000 245.775000
50% 7.300000 24.10000 106.050000 197.600000 1265.050000 2617.450000 333.850000
75% 10.100000 32.52500 155.850000 282.575000 1529.825000 3007.600000 460.125000
max 15.800000 51.60000 472.600000 485.300000 2453.100000 4467.400000 1140.100000 
from sklearn.decomposition import PCA
from sklearn.preprocessing import StandardScaler

# Antes de aplicar ACP, cada variable debe ser centrada y de varianza igual a 1
X_normalized = StandardScaler().fit(crime).transform(crime) 

pca = PCA(n_components = 2).fit(X_normalized)

X_pca = pca.transform(X_normalized) # nuevos componentes
print('varianza explicada',pca.explained_variance_ratio_) # vaianza explicada

grupos = KMeans(n_clusters = 3)
grupos.fit(X_pca)

plot_labelled_scatter(X_pca, grupos.labels_, ['Cluster 1', 'Cluster 2', 'Cluster 3'])

varianza explicada [0.58785136 0.17696026]

/Users/victormorales/opt/anaconda3/lib/python3.9/site-packages/sklearn/cluster/_kmeans.py:1412: FutureWarning: The default value of `n_init` will change from 10 to 'auto' in 1.4. Set the value of `n_init` explicitly to suppress the warning
  super()._check_params_vs_input(X, default_n_init=10)
_images/7e09806a6e4f1aab818f5f4429f045fbedb920f58e995a8ce44ef82cf091738f.png 
dbscan = DBSCAN(eps = 0.8, min_samples = 3)

cls = dbscan.fit_predict(X_pca)
print(np.unique(cls))
plot_labelled_scatter(X_pca, cls + 1, 
        ['Noise', 'Cluster 0', 'Cluster 1', 'Cluster 2'])

[-1  0  1  2]
_images/87bcf52f167e2a1df853a8b6e1e20dfb56d44b9d2a8f7ad07eda89592c92d84a.png