Unsupervised learning

One common use of computing in statistics and data science is data cleaning and preparation; you have practiced this in the first part of the assignment in SQL, and in previous assignments with R and Python.

Another common use is implementing statistical methods. For example, in a previous assignment you have written functions for the Huber loss and to fit a linear model.

Methods like linear regression belong to a class of methods called supervised learning: we have a set of explanatory variables, a response variable, and we want to predict the response. However, sometimes we don’t have a response variable, and we want to identify structure in a dataset. When there is no response variable, we are doing unsupervised learning. Examples of unsupervised learning include clustering and dimension-reduction, and you can learn a lot about unsupervised learning in STA 362 Multivariate Statistics.

Clustering

One type of unsupervised learning is clustering, in which we group observations which look “similar” into clusters. For example, consider the penguins data from the palmerpenguins package, which contains information about three species of penguin: Adelie, Chinstrap, and Gentoo. If we plot flipper length and bill length, we can see differences between the species:

library(palmerpenguins)
library(tidyverse)

penguins |>
  ggplot(aes(x = flipper_length_mm, y = bill_length_mm, color = species)) +
  geom_point() +
  labs(x = "Flipper length", y = "Bill length") +
  theme_bw()

But what if we didn’t know there were separate species of penguin? We would still see potential groups in the data, we just wouldn’t have labels for them:

penguins |>
  ggplot(aes(x = flipper_length_mm, y = bill_length_mm)) +
  geom_point() +
  labs(x = "Flipper length", y = "Bill length") +
  theme_bw()

A clustering algorithm tries to systematically identify groups in the data. Often, the number of clusters \(k\) is specified, and the algorithm clusters the observations into \(k\) groups of points which look similar to each other, and different from the other groups. For example, here is the output of a basic k-means clustering algorithm with \(k = 3\) on the flipper length and bill length measurements:

df <- penguins |>
  select(flipper_length_mm, bill_length_mm) |>
  drop_na() # remove missing values before clustering

# cluster with k = 3
clusters <- kmeans(df, 3, algorithm = "Lloyd", iter.max=20)$cluster

df |>
  mutate(cluster = as.factor(clusters)) |>
  ggplot(aes(x = flipper_length_mm, y = bill_length_mm, color = cluster)) +
  geom_point() +
  labs(x = "Flipper length", y = "Bill length") +
  theme_bw()

The resulting clusters align pretty closely with species, but not exactly.

The k-means algorithm

There are a variety of ways to conduct k-means clustering. The most straightforward (though not necessarily the best) is Lloyd’s algorithm:

1. Initialize: Given a value of \(k\), randomly select \(k\) observations from the dataset to be the initial group means.
2. Calculate distances: For every observation in the dataset, calculate the distance to each of the \(k\) group means.
3. Assign groups: Assign each observation to the nearest group mean.
4. Update means: For each group, re-calculate the new group mean as the mean of the points assigned to that group in step 3.
5. Iterate: Repeat steps 2 - 4 until convergence (the group assignments stop changing) or until a maximum number of iterations has been reached.

example_mat <- matrix(c(1:12), nrow = 6, byrow = T)
example_mat

##      [,1] [,2]
## [1,]    1    2
## [2,]    3    4
## [3,]    5    6
## [4,]    7    8
## [5,]    9   10
## [6,]   11   12

groups <- c(1, 1, 2, 2, 3, 3)

# group mean for group 1
colMeans(example_mat[groups == 1,])

## [1] 2 3

# group mean for group 2
colMeans(example_mat[groups == 2,])

## [1] 6 7

# group mean for group 1
colMeans(example_mat[groups == 3,])

## [1] 10 11

sqrt(rowSums(sweep(example_mat, 2, c(2, 3))^2))

## [1]  1.414214  1.414214  4.242641  7.071068  9.899495 12.727922

Implementation

In this assignment, you will write a k-means clustering function using Lloyd’s algorithm as described above.

Requirements:

Your function should take three inputs:

• The data to cluster
• The number of clusters, \(k\)
• The maximum number of iterations

Your function should return a list containing two components:

• The group assignments for each observation in the data
• A matrix containing the \(k\) group means

Your function should be applicable to any dataset; do not write it just in terms of the penguins data.

You may not:

• Use any existing implementation of the k-means algorithm
• Read any source code for other implementations of the algorithm
• Use AI to generate an implementation of the algorithm