# Session 10: Unsupervised clustering with K-means

------------------------------------------------------
Introduction to Data Science & Machine Learning

*Pablo M. Olmos olmos@tsc.uc3m.es*

------------------------------------------------------

# Unsupervised Learning

In this notebook, we will study a particularly simple method to perform unsupervised learning over a dataset. In this case, we will use [K-means](https://www.datascience.com/blog/k-means-clustering) to divide our population in a set of **clusters**. In unsupervised learning, we expect that the structure behind our data can be interpreted or exploited for future applications.

This post is inspired by the excellent book [Python Data Science Handbook by Jake VanderPlas](https://jakevdp.github.io/PythonDataScienceHandbook/index.html). I mostly added all the theoretical background.


## Clustering with K-means

The K-means algorithm is rather simple. Given a **distance metric** $d(\mathbf{x},\mathbf{x}')$ and a number $K$ of clusters selected in advance, we perform as follows.

Until convergence:

1. Initialize $K$ *centroids* at random among points in the dataset. Denote the centroids as $\mathbf{c}_k$, $k=1,\ldots,K$.
2. For $i=1,\ldots,N$, assign point $\mathbf{x}^{(i)}$ to the cluster with the closest centroid. If $A(\mathbf{x}^{(i)})\in\{1,\ldots,K\}$ is the cluster assigned to point $\mathbf{x}^{(i)}$ then

\begin{align}
A(\mathbf{x}^{(i)}) = \arg \min_{\{1,\ldots,K\}} d(\mathbf{x}^{(i)},\mathbf{c}_k)
\end{align}

3. Recompute centroids as the mean across all points assigned to the same cluster. For $k=1,\ldots,K$,

\begin{align}
\mathbf{c}_k = \frac{1}{N_k} \sum_{i: A(\mathbf{x}^{(i)})= k} \mathbf{x}^{(i)},
\end{align}
where $\frac{1}{N_k}$ is the number of points assigned to cluster $k$.

4. Declare convergence if no changes between two consecutive iterations or maximum number of iterations achieved.



```python
import matplotlib.pyplot as plt
import numpy as np
import scipy.io
from sklearn.datasets.samples_generator import make_blobs
from sklearn.cluster import KMeans,MiniBatchKMeans

%matplotlib inline
```

### Lets create a toy data set


```python
X, y_true = make_blobs(n_samples=500, centers=6,
                       cluster_std=0.6, random_state=22)

plt.scatter(X[:, 0], X[:, 1], s=50);
plt.xlabel('$x_1$')
plt.ylabel('$x_2$')
```


```python
#Lets run Kmeans clustering
K=4

kmeans = KMeans(n_clusters=K)
kmeans.fit(X)
y_kmeans = kmeans.predict(X)
```

Let's visualize the results by plotting the data colored by these labels. We will also plot the cluster centers as determined by the k-means estimator:


```python
plt.scatter(X[:, 0], X[:, 1], c=y_kmeans, s=50, cmap='viridis')

centers = kmeans.cluster_centers_
plt.scatter(centers[:, 0], centers[:, 1], c='black', s=200, alpha=0.5)
```

## Selecting the number of clusters

The number $K$ of clusters represent the model complexity. When we set large number of clusters, we are assuming tha the data structure is very complex, and we might be certainly **overfitting** our data.

How to diagnose overfitting in unsupervised clustering? There are several approaches. A common one is to set a model performance metric and analyze how it depends on the model complexity.

In $K$-means, the natural choice is to analyze the **average distance of points w.r.t. their cluster**. This is in fact the function that we minimize to derive the $K$-means algorithm!
\begin{align}
\mathcal{L}(\mathbf{c}_1,\ldots,\mathbf{c}_K) = \frac{1}{K} \sum_{k=1}^K \sum_{i: A(\mathbf{x}^{(i)})= k} \frac{d(\mathbf{x}^{(i)},\mathbf{c}_k)}{N_k}
\end{align}

If we optimize the above function w.r.t. $\mathbf{c}_k$, $k=1,\ldots,K$, by implementing a [**coordinate gradient descent**](https://en.wikipedia.org/wiki/Coordinate_descent) we derive the $K$-means algorithm.

Lets plot the evolution of $\mathcal{L}(\mathbf{c}_1,\ldots,\mathbf{c}_K)$ for different values of $K$.



```python
kmeans.inertia_
```




    3213.6836424069884




```python
K_list = range(2,15)

L = []

for k in K_list:
    
    kmeans = KMeans(n_clusters=k)
    kmeans.fit(X)
    L.append((kmeans.inertia_)/(0.0+k*X.shape[0]))
    
    
plt.figure()
plt.plot(K_list,L)
plt.xlabel('$K$')
plt.ylabel('$L$')
plt.grid()
```

Clearly, the cost function becomes flat for large $K$ values. This means that we are making our model **more complex** but we are not essentially explaining our data better! A sign of **overfitting**.

Given the above figure, it would make sense to select a value of $K$ around 6 (which is also the true value in this case).

Be aware that this plot is dependent of the number of data points. Also, that the $K$-means solution is **highly dependent** on the intialization. Actually, it is usual to run it several times and select the solution that provides the smallest $\mathcal{L}(\mathbf{c}_1,\ldots,\mathbf{c}_K)$ function. In the [**Sklearn K-means library**](http://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html), it is controlled by the parameter *n_init*.


```python
N_list =[20,50,100,500]

K_list = range(2,8)



plt.figure()

for n in N_list:
    
    X, y_true = make_blobs(n_samples=n, centers=6,
                       cluster_std=0.6, random_state=22)    
    
    L = []
    
    for k in K_list:

        kmeans = KMeans(n_clusters=k,n_init=5)
        kmeans.fit(X)
        L.append((kmeans.inertia_)/(0.0+k*X.shape[0]))
    
    plt.plot(K_list,L,label='N_points='+str(n))
        
plt.xlabel('$K$')
plt.ylabel('$L$')
plt.grid()
plt.legend()
```

## Mini-batch $K$-means

Updating centroids at every $K$-means update using all datapoints can be costly for very large databases. An scalable and effective solution uses small **mini-batches** of data at every iteration.  This is known as **mini-batch** $K$-means, and it is also provided in the [**sklearn library**](http://scikit-learn.org/stable/modules/generated/sklearn.cluster.MiniBatchKMeans.html#sklearn.cluster.MiniBatchKMeans).

Compare the running times of the following two examples.




```python
# Without mini-batches. Full K-means

n =int(1e5)

K_list = range(2,8)

X, y_true = make_blobs(n_samples=n, centers=6,
                       cluster_std=0.6, random_state=22)   
L = []

batch = 100

for k in K_list:

    kmeans = MiniBatchKMeans(n_clusters=k,batch_size=batch,n_init=5)
    kmeans.fit(X)
    L.append((kmeans.inertia_)/(0.0+k*X.shape[0]))
    
    
plt.figure()
plt.plot(K_list,L)
plt.xlabel('$K$')
plt.ylabel('$L$')
plt.grid()
```

**Summary**: $K$-means is a simple and cheap algorithm for unsupervised clustering. However, it has fundamental weaknesses that we will explain when we introduce probabilisitic clustering using **Gaussian Mixture Models** and the **Expectation Maximization Algorithm**.


```python

```

df252dd488d5f065f04852b717f95549c6befa9b
ipynb
Jupyter Notebook
Notebooks/Session 10 K-means/Session_10_K_means_Clustering.ipynb
olmosUC3M/Introduction-to-Data-Science-and-Machine-Learning
33a908011a5673dcbc6136dfc1eae868ef32e6b4
MIT
2018-04-30T18:44:05.000Z
2020-09-13T23:53:11.000Z
Notebooks/Session 10 K-means/Session_10_K_means_Clustering.ipynb
olmosUC3M/Introduction-to-Data-Science-and-Machine-Learning
33a908011a5673dcbc6136dfc1eae868ef32e6b4
MIT
Notebooks/Session 10 K-means/Session_10_K_means_Clustering.ipynb
olmosUC3M/Introduction-to-Data-Science-and-Machine-Learning
33a908011a5673dcbc6136dfc1eae868ef32e6b4
MIT
2019-03-13T16:01:38.000Z
2019-03-13T16:01:38.000Z
Qwen/Qwen-72B
1. YES
2. YES