```python
%matplotlib inline
import numpy as np
import matplotlib.pyplot as plt
```

# Aprendizaje no supervisado

En esta lección se estudian dos algoritmos de aprendizaje no supervisado clásicos y ampliamente utilizados: PCA como representante de los algoritmos de reducción de dimensionalidad y KMeans como representando de los algoritmos de agrupamiento/clustering

## Principal Component Analysis (PCA)

A continuación se presentan los fundamentos teóricos tras el algoritmo PCA. En seguida veremos como utilizar la implementación de PCA de la librería `sklearn` para hacer reducción de dimensionalidad en base de datos con atributos continuos

### Formalismo matemático

PCA es un procedimiento estadístico que busca una **transformación ortogonal** que **maximice la varianza** de los datos 

Matemáticamente, podemos escribir un conjunto de datos $\{x_i\}$ con $i=1,2,\ldots, N$ y $x_i \in \mathbb{R}^D$, como una matriz $X \in \mathbb{R}^{N\times D}$

La transformación está representada por una matriz $W \in \mathbb{R}^{D\times D}$ y los datos transformados se obtienen mediante una multiplicación matricial

$$
X' = X W
$$

Una transformación es ortogonal si cumple $W^T W = I$ es decir que la transformación traspuesta es equivalente a su inversa. Para encontrar una transformación que maximice la varianza de los datos debemos obtener primero la matriz de correlación de $X$ definida por

$$
C = \frac{1}{N} X^T X
$$

donde $C \in \mathbb{R}^{D\times D}$ y donde asumimos que la media de $X$ es cero. Notemos que la matriz de correlación de los datos transformados es $\frac{1}{N} X'^T X' = \frac{1}{N} W^T X^T X W = W^T C W$ con lo que podemos escribir la siguiente función objetivo

$$
\max_W W^T C W \text{ sujeto a } W^T W = I
$$

Usando *multiplicadores de Lagrange* para incluir la restricción en el objetivo y derivando e igualando a cero obtemos lo siguiente

$$
\begin{align}
\frac{d}{dW} W^T C W + \Lambda(I- W^T W) &= 0 \nonumber \\ 
(C - \Lambda) W &= 0 \nonumber
\end{align}
$$

donde $\Lambda = \lambda I$ y $\lambda = (\lambda_1, \lambda_2, \ldots, \lambda_D)$

Esto se conoce como el problema de los valores $\lambda$ y vectores propios $W$ de la matriz $C$. 

### Ejemplo

Sean los siguientes datos bidimensionales


```python
X = np.random.multivariate_normal([0, 0], [[0.5, -0.7], [-0.7, 1]], size=1000)
```

Usaremos PCA para encontrar los ejes coordenados de máxima varianza y graficarlos 

Para resolver el problema de valores propios usaremos `np.linalg.eigh` que recibe una matriz cuadrada y retorna sus valores y vectores propios


```python
import scipy.linalg
# Restamos la media
X_ = X - np.mean(X, axis=0, keepdims=True)
# Calculamos la covarianza
C = np.dot(X_.T, X_)/len(X_)
# Calculamos los valores y vectores propios de la covarianza
L, W = scipy.linalg.eigh(C)
# Proyectamos
U = np.dot(X, W)

# Visualización de datos y proyección
arrow_args = {'width': 0.05, 'length_includes_head': True, 'alpha': 0.5}
fig, ax = plt.subplots(1, 2, figsize=(6, 3), dpi=120, 
                       tight_layout=True, sharex=True, sharey=True)
ax[0].scatter(X[:, 0], X[:, 1], s=10);
for i, c in enumerate(['g', 'r']):
    ax[0].arrow(0, 0, W[i, 0], W[i, 1], color=c, **arrow_args)
ax[0].set_aspect('equal'); 
ax[1].set_aspect('equal');
ax[0].set_xlim([-3.5, 3.5])
ax[1].scatter(U[:, 0], U[:, 1])
ax[1].spines['bottom'].set_color('g')
ax[0].set_ylabel('Atributo 1')
ax[0].set_xlabel('Atributo 2')
ax[1].set_ylabel('Componente principal 1')
ax[1].set_xlabel('Componente principal 2')
ax[1].spines['left'].set_color('r')
ax[0].set_title('Datos originales')
ax[1].set_title('Datos proyectados');
```

**Discusión:** 

- El eje rojo acumula un 99.5% de la varianza
- El eje verde es ortogonal al rojo
- Los nuevos ejes están decorrelacionados c/r a los originales

### Reducción de dimensionalidad con PCA

Una aplicación típica de PCA es la reducción de dimensionalidad

Recordemos

- La matriz $W$ tiene las mismas dimensiones que $C$
- Las columnas de $W$ son los vector propios
- Cada vector propio tiene un valor propio asociado

Considerar que 

> El valor propio $\lambda_i$ asociado a la columna $i$ de $W$ corresponde a la "cantidad de varianza" de dicha columna

Para obtener una proyección que disminuya la dimensionalidad necesitamos una matriz $\widehat W \in \mathbb{R}^{D\times \hat D}$. Podemos obtener $\widehat W$ uniendo un subconjunto de las columnas de $W$. En particular nos interesa proyectar a los vectores propios de mayor varianza. 

- Para tareas de visualización de datos podemos retener los 2 o 3 componentes principales de mayor varianza
- Para tareas más generales de reducción de dimensionalidad o decorrelación de atributos debemos encontrar una dimensión $\hat D < D$ apropiada
- Un criterio típico es ordenar los vectores propios de mayor a menor y retener aquellos que acumulen un 90% de la varianza
- **Importante:** Si proyectamos con $\widehat W$ la transformación no es invertible porque estamos "descartando" información. Es una compresión de tipo *lossy*

### PCA con `scikit-learn`

PCA está incluido en el módulo [`sklearn.decomposition`](https://scikit-learn.org/stable/modules/classes.html#module-sklearn.decomposition)

El constructor y sus argumentos más importantes son

```python
sklearn.decomposition.PCA(n_components=None, # Cantidad (int) o porcentaje de varianza (float) a retener
                          copy=True, # Si es falso, la data transformada reemplaza la original
                          whiten=False, # Reescala los datos para que tengan igual dispersión
                          ...
                         )
```

Los métodos más importantes de la clase `PCA` son

- `fit(X)`: Calcula la matriz de correlación y los vectores y valores propios
- `transform(X)`: Retorna la proyección de $X$
- `fit_transform(X)`: `fit` y `transform` en un solo paso
- `inverse_transform(hatX)`: Retorna los datos al espacio original (con pérdidas si $\hat D < D$)
- `get_covariance()`: Retorna la matriz de covarianza

Los atributos más importantes son

- `components_`: Los componentes principales (vectores propios)
- `singular_values_`: Los valores propios
- `explained_variance_ratio_`: El porcentaje de varianza asociado a cada vector propio 



### Ejemplo

Base de datos con **cuatro atributos numéricos** asociados a las características de un conjunto de 150 flores del género Iris separadas en 3 clases



A continuación se presenta un gráfico de dispersión para visualizar las relaciones entre los atributos


```python
import sklearn.datasets

iris_set = sklearn.datasets.load_iris()
X = iris_set.data
Y = iris_set.target

fig, ax = plt.subplots(3, 3, figsize=(8, 5), tight_layout=True, sharex=True, sharey=True)
for i in range(3):
    for j in range(i, 3):
        for y in range(3):
            ax[i, j].scatter(X[Y==y, i], X[Y==y, j+1], s=10, alpha=0.5)            

ax[0 ,0].set_ylabel('Sepal length')
ax[1 ,0].set_ylabel('Sepal width')
ax[2 ,0].set_ylabel('Petal length')
ax[2 ,0].set_xlabel('Sepal width')
ax[2 ,1].set_xlabel('Petal length')
ax[2 ,2].set_xlabel('Petal width');
```

Para hacer una visualización más concisa podemos usar PCA para reducir la dimensión de los datos de 4 a 2

Además podemos estudiar la contribución de cada atributo a los nuevos ejes


```python
import sklearn.decomposition

pca = sklearn.decomposition.PCA(n_components=2)
hatX = pca.fit_transform(X)
hatW = pca.components_

display("Vectores propios de los componentes más relevantes", hatW)
display("Valores propios", pca.singular_values_)
display("Porcentaje de varianza de cada vector propio", pca.explained_variance_ratio_)

fig, ax = plt.subplots(1, 2, figsize=(7, 3), dpi=120, tight_layout=True)
for y, name in enumerate(iris_set.target_names):
    ax[0].scatter(hatX[Y==y, 0], hatX[Y==y, 1], s=10, label=name)
ax[0].legend();
for ax_ in ax:
    ax_.set_ylabel('Vector propio 2'); ax_.set_xlabel('Vector propio 1')
ax[1].plot([0, 0], [-1 ,1], 'k--', alpha=0.5)
ax[1].plot([-0.5, 2], [0, 0],  'k--', alpha=0.5)
for i, name in enumerate(iris_set.feature_names):
    ax[1].arrow(0, 0, hatW[0, i], hatW[1, i], color='b', **arrow_args)
    ax[1].text(hatW[0, i], hatW[1, i], name)
```

**Análisis**

La figura de la izquierda son los datos de iris proyectados en los componentes principales más importantes. la figura de la derecha muestra la contribución de los atributos originales a cada uno de los vectores propios

- Podemos notar que el tipo de flor, es decir las clases de Iris, pueden separarse en el eje del vector propio 1
- Podemos ver también que las variables que tienen que ver con el sépalo están alineadas con el vector propio 2 (ángulo menor)
- En cambio las variables que tienen que ver con el pétalo están alineadas con el vector propio 1
- La clase de la flor tiene mayor relación con el pétalo que con el sépalo



## Clustering con algoritmo K-means

El objetivo general de los métodos de clustering es agrupar los datos en conjuntos (clusters) tal que:

- Los elementos dentro de un mismo cluster sean similares
- Los elementos dentro de un mismo cluster sean distintos a los elementos pertenecientes a otro cluster

esto nos permite revelar estructuras escondidas en los datos y así entenderlos mejor (análisis exploratorio).

Los algoritmos de clustering requieren definir un criterio para medir similitud entre los ejemplos. Lo más típico para datos numéricos es usar métricas de distancia como la [distancia euclidiana](https://es.wikipedia.org/wiki/Distancia_euclidiana) o la [distancia de manhattan/taxista](https://es.wikipedia.org/wiki/Geometr%C3%ADa_del_taxista)

Una vez definida la noción de distancia a utilizar se debe definir un criterio de agrupación. Dependiendo de la combinación entre estas definiciones surgen distintas familias de algoritmos de clustering 

- Algoritmos basados en representantes (centroides)
- Algoritmos basados en conectividad y jerarquías
- Algoritmos basados en modelos de densidad

En esta lección nos enfocaremos en un algoritmo clásico de clustering basado en representates: K-medias o *K-means*. 

### Formalismo matemático

El algoritmo de K-means requiere que el usuario especifique a priori el número de clusters a detectar, es decir que $K$, el número de clusters es un hiperparámetro del algoritmo. El algoritmo K-means es bastante simple y se resume en el siguiente diagrama esquemático



Detalles:

- Los centroides $\{c_j\}_{j=1,\ldots,K}$ son los centros de los clusters. 
- En el paso 2, el cluster asociado a la muestra $i$ se calcula usando la distancia euclidiana

$$
\begin{align}
y_i &= \text{arg}\min_{j=1,\ldots,K} \| x_i - c_j\|_2^2  \nonumber \\
&= \text{arg}\min_{j=1,\ldots,K} \sqrt{ \sum_{d=1}^D (x_{id} - c_{jd})^2}  \nonumber 
\end{align}
$$

- En el paso 3 los el centroide $j$ se actualiza como

$$
c_j = \frac{\sum_{i=1}^N \mathbb{1}(y_i = j) x_i}{\sum_{i=1}^N \mathbb{1}(y_i = j)}
$$

donde la función indicadora se define como

$$
\mathbb{1}(y_i = j) = \begin{cases} 1 & \text{si } y_i = j \\ 0 & \text{si } y_i \neq j \end{cases}
$$

es decir que el centroide es el promedio de las muestras asociadas a si mismo



### K-means con `scikit-learn`

K-means está incluido en el módulo [`sklearn.cluster`](https://scikit-learn.org/stable/modules/classes.html#module-sklearn.cluster)

El constructor y sus argumentos más importantes son

```python
sklearn.cluster.KMeans(n_clusters=8, # El número de grupos/clusters
                       init='k-means++', #El algoritmo de inicialización puede ser random o k-means++
                       n_init=10, # El número de inicializaciones que se prueban
                       max_iter=300, # El número máximo de iteraciones
                       tol=0.0001, # Si la diferencia entre los centroides en distintas iteraciones es menor que este valor, el algoritmo se detiene
                       ...
                      )
```

Los métodos más importantes de la clase [`KMeans`](https://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html#sklearn.cluster.KMeans) son

- `fit(X)`: Entrena y obtiene los centroides
- `predict(X)`: Retorna el índice del cluster más cercano para cada dato
- `fit_predict(X)`: `fit` y `predict` en un solo paso

Los atributos más importantes son

- `cluster_centers_`: Los centroides de los clusters
- `inertia_`: La suma de errores cuadrados



### Detalles prácticos

- K-means es sensible a los centroides iniciales. Es recomendable probar varias veces con distintas inicializaciones
- La correctitud de los clusters depende fuertemente de $K$. Se recomienda probar con distinto $K$ y evaluar los resultados usando el método del codo o el coeficiente de silueta. Veremos un ejemplo de esto más adelante
- K-means es un algoritmo rápido y que escala bien a datos masivos. Scikit-learn ofrece [`MinibatchKMeans`](https://scikit-learn.org/stable/modules/generated/sklearn.cluster.MiniBatchKMeans.html) para esos casos

**Variantes de K-means**

- Si los datos tiene outliers fuertes se puede reemplazar el promedio en el paso 3 de KMeans por la mediana, obteníendose el algoritmo de las k-medianas
- Si es un requisito que los centroides sean siempre ejemplos del dataset se puede usar el algoritmo de los [k-medoides](https://es.wikipedia.org/wiki/K-medoids)

**Debilidades de KMeans**

K-means asume que los clusters son 

- de "forma esférica" 
- de igual densidad. 

Si esto no se cumple puede ser mejor utilizar algoritmos más generales (y más costosos) como [Modelos de mezcla de gaussianas](https://scikit-learn.org/stable/modules/classes.html#module-sklearn.mixture) o [DBSCAN](https://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html#sklearn.cluster.DBSCAN). La siguiente figura de scikit-learn muestra el desempeño de distintos algoritmos de clustering ante datos con distinta geometría





Las filas corresponde a datos provenientes de distribuciones

- concéntricas
- con formas no lineales
- de distinto dispersión (densidad y tamaño)
- gaussiana pero no esférica (anisotrópicos)
- gaussian esférico
- uniforme

### Ejemplo

A modo de ejemplo se realiza un clustering con KMeans sobre el dataset Iris. 

Para escoger el mejor número de clusters se utiliza el coeficiente de silueta implementado en `sklearn.metrics`


```python
import sklearn.metrics 
import sklearn.cluster

iris_set = sklearn.datasets.load_iris()
X = iris_set.data

fig, ax = plt.subplots(4, 2, figsize=(5, 6), dpi=120, tight_layout=True)

for k, n_clusters in enumerate(range(2, 6)):
    # Clustering con kmeans
    kmeans = sklearn.cluster.KMeans(n_clusters=n_clusters)
    labels = kmeans.fit_predict(X)
    # Score de silueta promedio y por ejemplo
    score_promedio = sklearn.metrics.silhouette_score(X, labels)
    score_ejemplos = sklearn.metrics.silhouette_samples(X, labels)
    y_lower = 10
    for cluster in np.unique(labels):  
        ax[k, 1].scatter(hatX[labels==cluster, 0], hatX[labels==cluster, 1], s=10)
        
        scores_cluster_sorted = np.sort(score_ejemplos[labels==cluster])
        y_upper = y_lower + len(scores_cluster_sorted)
        ax[k, 0].fill_betweenx(np.arange(y_lower, y_upper), 0, scores_cluster_sorted, alpha=0.7)
        ax[k, 0].axvline(score_promedio, ls='--', c='k')
        ax[k, 0].set_title(f'K: {n_clusters}')
        ax[k, 0].set_xlim([0, 1])
        y_lower = y_upper + 10
    ax[-1, 0].set_xlabel('Coeficiente de silueta')
```

**Análisis**

La figura de la izquierda muestra los coeficientes de silueta de los ejemplos asociados a cada uno de los clusters. La linea punteada negra corresponde al coeficiente de silueta promedio. 

La figura de la derecha muestra un gráfico de dispersión de los datos con dimensionalidad reducida (PCA) donde el color corresponde a los clusters detecteados por KMeans

Tanto el caso de $K=4$ como $K=5$ presentan algunos clusters cuyos coeficientes de silueta son menores que el promedio. Por otro lado el caso $K=2$ presenta alta disparidad den el tamaño de los clusters. En el caso $K=3$ los clusters son de un tamaño más uniforme y todos los clusters tienen ejemplos que superan el coeficiente promedio.

Otra forma de guiar la selección del número de clusters es visualizar el decaimiento de la función de costo (suma de errores cuadráticos) en función del número de clusters 


```python
sse = []
n_clusters_test = range(2, 10)
for n_clusters in n_clusters_test:
    kmeans = sklearn.cluster.KMeans(n_clusters=n_clusters)
    kmeans.fit(X)
    sse.append(kmeans.inertia_)
    
fig, ax = plt.subplots(figsize=(5, 3), dpi=120, tight_layout=True)
ax.plot(n_clusters_test, sse)
ax.set_ylabel('Suma de errores\ncuadráticos')
ax.set_xlabel('K');
```

En este caso el mayor decaimiento en error cuadrático ocurre cuando pasamos de $K=2$ a $K=3$, lo cual indica que $K=3$ es una buena elección.

## ¿Qué aprendimos en esta lección?

- A proyectar datos usando PCA
- A agrupar datos usando KMeans


```python

```

61199d5412efccfb2c6e9dda96493e0e8e8e7244
ipynb
Jupyter Notebook
clases/unidad3/1_ML/ML3.ipynb
magister-informatica-uach/INFO147
3898eb6f589a22beefb5972a0c911bb9dd098c6d
Unlicense
2019-04-12T21:10:39.000Z
2021-10-12T14:30:09.000Z
clases/unidad3/1_ML/ML3.ipynb
magister-informatica-uach/INFO147
3898eb6f589a22beefb5972a0c911bb9dd098c6d
Unlicense
clases/unidad3/1_ML/ML3.ipynb
magister-informatica-uach/INFO147
3898eb6f589a22beefb5972a0c911bb9dd098c6d
Unlicense
2019-04-12T20:00:09.000Z
2021-06-17T21:48:53.000Z
Qwen/Qwen-72B
1. YES
2. YES