# K-means clustering

## Introduction

K-means is still one of the fundamental clustering algorithms. It is used in such diverse fields as Natural Language Processing (NLP), social sciences and medical sciences.

The core idea behind K-means is that we want to group data in clusters. Data points will be assigned to a specific cluster depending on it's distance to a cluster's center, usually called the centroid.

It is important to note that typically, the mean distance to a centroid is used to partition the clusters, however, difference distances can be used and different pivot points. An example is the K-medoids clustering algorithm.

We will define the two main steps of a generic K-means clustering algorithm, namely the data assignement and the centroid update step.

### Data assignement

The criteria to determine whether a point is closer to one centroid is typically an Euclidean distance ($$L^2$$) . If we consider a set of $$n$$ centroids $$C$$, such that

$C = \lbrace c_1, c_2, \dots, c_n \rbrace$

We assign each data point in $$\mathcal{D}=\lbrace x_1, x_2, \dots, x_n \rbrace$$ to the nearest centroid according to its distance, such that

$\underset{c_i \in C}{\arg\min} \; dist(c_i,x)^2$

As mentioned previously $$dist(\cdot)$$ is typically the standard ($$L^2$$) Euclidean distance. We define the subset of points assigned to a centroid $$i$$ as $$S_i$$.

### Centroid update step

This step corresponds to updating the centroids using the mean of add points assign to a cluster, $$S_i$$. That is

$c_i=\frac{1}{|S_i|}\sum_{x_i \in S_i} x_i$

# Partitioning

Different algorithms can be used for cluster partitioning, for instance:

• PAM
• CLARA
• CLARANS

## PAM

To illustrate the PAM partitioning method, we will use a synthetic dataset created along the guidelines in synthetic data generation.

# Elbow method

In order to use the "Elbow method" we calculate the Within-Cluster Sum of Squares (WCSS) for a varying number of clusters, $$K$$.

import numpy as np
import matplotlib.pyplot as plt
import pandas as pd
import sklearn

import warnings
warnings.filterwarnings("ignore")

dataset = pd.read_csv('data/mall-customers.zip')
X = dataset.iloc[:, [3, 4]].values

from sklearn.cluster import KMeans
wcss = []
for i in range(1, 11):
kmeans = KMeans(n_clusters = i, init = 'k-means++', random_state = 42)
kmeans.fit(X)
wcss.append(kmeans.inertia_)

from plotutils import *

plt.plot(range(1, 11), wcss)
plt.xlabel('Number of clusters')
plt.ylabel('WCSS')
plt.show()


kmeans = KMeans(n_clusters = 5, init = "k-means++", random_state = 42)
y_kmeans = kmeans.fit_predict(X)

ps = 30
plt.scatter(X[y_kmeans == 0, 0], X[y_kmeans == 0, 1], s = ps, c = colours[0], label = 'Cluster1')
plt.scatter(X[y_kmeans == 1, 0], X[y_kmeans == 1, 1], s = ps, c = colours[1], label = 'Cluster2')
plt.scatter(X[y_kmeans == 2, 0], X[y_kmeans == 2, 1], s = ps, c = colours[2], label = 'Cluster3')
plt.scatter(X[y_kmeans == 3, 0], X[y_kmeans == 3, 1], s = ps, c = colours[3], label = 'Cluster4')
plt.scatter(X[y_kmeans == 4, 0], X[y_kmeans == 4, 1], s = ps, c = colours[4], label = 'Cluster5')
plt.scatter(kmeans.cluster_centers_[:, 0], kmeans.cluster_centers_[:, 1], s = 100, c = 'black', label = 'Centroids')
plt.xlabel('Annual Income (k\$)')
plt.ylabel('Spending Score (1-100)')
plt.legend()

plt.show()