Lecture L18: Clustering and Description Length Minimization

What is the mathematical formalization of "how different" two observations are in cluster detection?

The dissimilarity metric $\delta(x_i,x_j)$.

What is a common choice for the dissimilarity metric in Euclidean feature spaces?

The Euclidean distance.

What is the primary goal of the clustering problem given $k$ clusters?

To map data points to clusters such that pairs of points within the same cluster are more similar to each other than to points in different clusters.

What defines a non-overlapping/hard clustering?

Each point belongs to exactly one cluster, meaning $C_i \cap C_j = \emptyset$for$i,j \in \{1,...,k\}$.

What defines an overlapping/fuzzy/soft clustering?

A point may belong to multiple clusters with varying degrees, meaning $C_i \cap C_j \ne \emptyset$for$i,j \in \{1,...,k\}$.

Name three important applications of cluster analysis.

Exploratory data analysis, recommender systems, and image segmentation.

Why do practical algorithms for finding an optimal clustering use heuristics instead of exhaustive search?

Because finding an optimal clustering based on metrics like Euclidean distance is an NP-hard optimization problem.

What happens to the loss $L$as the number of clusters$k$increases in k-means?

The loss$L$is a monotone decreasing function of$k$, meaning it always favors larger $k$.

What is the value of the loss $L$when$k=n$ in k-means clustering?

$L=0$.

Why can't we use cross-validation to determine the optimal number of clusters?

Because cluster detection is an unsupervised learning problem and lacks ground-truth labels to validate against.

What two factors must be balanced when selecting the optimal number of clusters?

Explanatory power (low loss) against model complexity (number of clusters).

What is the model selection problem in the context of scientific theories?

Multiple different theories or models can be consistent with a given phenomenon, such as the heliocentric and geocentric models reproducing planetary positions.

What is the principle of parsimony?

It is the idea that we should balance fit and complexity because simpler models generalize better to new observations.

Why is the minimum loss criterion alone insufficient for model selection?

Because it will always favor the most complex model.

How can a model be explicitly discouraged from becoming too complex?

By explicitly penalizing model complexity.

What assumption is made about the partition of observations $D$ in centroid-based clustering?

It is assumed that observations are partitioned into $k$ non-overlapping clusters $C_j \subseteq D$.

How is the centroid of a cluster defined in centroid-based clustering?

The centroid $\overline{c}_j$ is defined as the mean coordinate or position of all observations in that cluster.

To which cluster is a new observation naturally assigned in centroid-based clustering?

To the cluster with the closest centroid, meaning it falls within the Voronoi region of that centroid.

What is the mathematical formula for the loss function $L$ that a good centroid-based clustering aims to minimize?

$L = \frac{1}{n} \sum_{j=1}^{k} \sum_{x_i \in C_j} \delta(x_i, \overline{c}_j)$.

What does the loss function $L$ measure in centroid-based clustering?

It measures the average distance of points from their respective cluster centers.

What does the function $\delta(x, y)$ typically represent in the centroid-based clustering loss function?

The Euclidean distance between $x$ and $y$.

What motivates the use of an iterative algorithm for centroid-based clustering?

The fact that centroids change when points are reassigned, requiring alternating steps of reassigning points and recomputing centroids until they converge.

Who are the two scientists credited with the initial idea and the formalization of the k-means clustering algorithm?

Hugo Steinhaus in 1956 and James MacQueen in 1967.

What is the primary objective of Lloyd's algorithm for k-means clustering?

To iteratively assign every point to the cluster with the closest centroid and then recompute centroids as the mean of the assigned points.

Why is convergence guaranteed in Lloyd's algorithm?

Each iteration reduces or maintains the loss function, as point reassignment lowers loss given current centroids, and recomputation lowers loss given current assignments.

Does Lloyd's algorithm guarantee a global optimum?

No, it can converge to a local minimum.

Why is it common to rerun the k-means algorithm multiple times?

Because the final result depends on the random initialisation of centroids, and rerunning it with different initialisations helps avoid poor local minima.

What is the effect of a poor random initialisation of centroids in k-means?

It can lead to slow convergence and suboptimal clustering results.

How are cluster centroids updated in each iteration of Lloyd's algorithm?

They are recomputed as the mean coordinate of all observations assigned to that cluster.

What is the condition for assigning an observation $x_i$ to a cluster $C_s$ in k-means?

The observation is assigned to the cluster with the closest centroid, defined as $s = \text{argmin}_{j \in \{1,...,k\}} \delta(x_i, \overline{c}_j)$.