K-means Clustering

What is K-means clustering?

K-means clustering is an unsupervised learning method used to divide data into K groups, called clusters.

It is called unsupervised because the data does not already have labels.
The algorithm tries to find natural groups in the data.

Main idea
K-means groups observations so that:

observations in the same cluster are similar;

observations in different clusters are different.

Each cluster has a centre point called a centroid.

A centroid is the average position of all the points in that cluster.

What does K mean?

The value of K is the number of clusters chosen before running the algorithm.

For example:

If K = 2, the algorithm forms 2 clusters.

If K = 3, the algorithm forms 3 clusters.
If K = 5, the algorithm forms 5 clusters.

So, the number of clusters must be chosen before applying K-means.

How the K-means algorithm works

Suppose we choose K = 3.

Step 1: Choose initial centroids

The algorithm first chooses 3 starting centre points.

These are often chosen randomly.

Step 2: Assign points to the nearest centroid

Each data point is assigned to the cluster with the closest centroid.

Distance is usually measured using Euclidean distance.

For two points,

(x1 , y1 )

and

(x2 , y2 )

the Euclidean distance is:

d = √(x1 − x2 )2 + (y1 − y2 )2

Step 3: Update the centroids

After assigning the points to clusters, the centroid of each cluster is recalculated.

The new centroid is the mean of all the points in that cluster.

Step 4: Repeat
The algorithm repeats these two steps:

1. assign each point to the nearest centroid;

2. update the centroids.

This continues until the clusters stop changing.

Objective of K-means
K-means tries to minimize the total distance between each point and its cluster centroid.

The objective function is:

K
∑ ∑ ∥xi − µk ∥2
k=1 i∈Ck

where:

K is the number of clusters;

Ck is cluster k;
xi is a data point;
µk is the centroid of cluster k;
∥xi − µk ∥2 is the squared distance between a point and its centroid.

In simple words, K-means tries to make each cluster as compact as possible.

Simple example
Suppose we have data on students using:

hours studied;
test marks.

K-means may group the students into clusters such as:

Cluster Possible interpretation

Cluster 1 Low study hours and low marks

Cluster 2 Medium study hours and medium marks

Cluster 3 High study hours and high marks

The algorithm does not know these group names beforehand.

We interpret the clusters after the algorithm has grouped the data.

Important points
K-means works best when:

clusters are roughly circular;

clusters have similar sizes;
there are no extreme outliers;
variables are on similar scales.

Scaling is important because K-means is based on distance.

For example, if one variable is income and another variable is age, income may dominate the distance calculation because it has larger values.

Therefore, variables are often standardized before using K-means.

Advantages of K-means
K-means is useful because:

it is simple to understand;
it is fast;
it works well for large datasets;
it is easy to implement.

Disadvantages of K-means
K-means has some limitations:

the number of clusters K must be chosen beforehand;

results can depend on the initial centroids;
it is sensitive to outliers;
it does not work well for irregularly shaped clusters;
it assumes distance is meaningful.

Choosing K
A common method for choosing K is the elbow method.

The idea is to run K-means for different values of K , such as:

K = 1, 2, 3, 4, 5, …

For each value of K , calculate the within-cluster sum of squares.

As K increases, the within-cluster sum of squares decreases.

The best value of K is often chosen at the point where the decrease starts to slow down.

This point is called the elbow.

Summary
K-means clustering is a method that groups data into K clusters.

It works by:

1. choosing initial centroids;

2. assigning points to the nearest centroid;
3. updating the centroids;
4. repeating until the clusters stop changing.

The goal is to form clusters where points are close to their own centroid and far from other cluster centroids.

Hierarchical Clustering
Hierarchical clustering is an unsupervised learning method used to group observations into clusters. It is called hierarchical because it builds a tree-like structure of clusters. This
tree is called a dendrogram. Unlike K-means clustering, hierarchical clustering does not require us to choose the number of clusters at the start.

Main idea
Hierarchical clustering groups observations based on how similar or close they are.

The closer two observations are, the more likely they are to be grouped together.

The method creates a hierarchy, starting either from:

each observation as its own cluster;

or all observations in one big cluster.

1. Agglomerative Hierarchical Clustering

Agglomerative hierarchical clustering is a bottom-up approach. It starts with each observation in its own cluster. Then, at each step, the two closest clusters are merged. This
continues until all observations are in one large cluster.

Steps
Suppose we have n observations.

Step 1: Start with individual clusters

Each observation begins as its own cluster.

So, if there are n observations, we start with n clusters.

Step 2: Calculate distances

Calculate the distances between all pairs of clusters.

At the beginning, each cluster contains only one observation.

Step 3: Merge the closest clusters

Find the two clusters with the smallest distance and merge them.

Step 4: Update distances

After merging clusters, update the distances between the new cluster and the remaining clusters.

The way distances are updated depends on the linkage method.

Step 5: Repeat
Repeat the process until all observations are grouped into one cluster.

In simple words
Agglomerative clustering works like this:

n clusters → n − 1 clusters → n − 2 clusters → ⋯ → 1 cluster

2. Divisive Hierarchical Clustering

Divisive hierarchical clustering is a top-down approach. It starts with all observations in one large cluster. Then, the cluster is split into smaller clusters. This continues until each
observation is in its own cluster.

Steps
Step 1: Start with one cluster
All observations begin in one large cluster.

Step 2: Split the cluster

The large cluster is divided into two smaller clusters.

Step 3: Continue splitting

The process continues by splitting clusters into smaller groups.

Step 4: Stop
The process stops when each observation is in its own cluster or when the desired number of clusters is reached.

In simple words
Divisive clustering works like this:

1 cluster → 2 clusters → 3 clusters → ⋯ → n clusters

Dendrogram
A dendrogram is a tree diagram that shows how clusters are formed. It is used to visualize hierarchical clustering.

How to read a dendrogram

In a dendrogram:

each observation starts at the bottom;

branches join together when clusters are merged;
the height at which branches join shows the distance between clusters.

Clusters that join at a low height are more similar.

Clusters that join at a high height are less similar.

Choosing the number of clusters

To choose the number of clusters, we can cut the dendrogram at a certain height.

For example:

cutting the dendrogram low gives more clusters;

cutting the dendrogram high gives fewer clusters.

The number of vertical lines crossed by the cut gives the number of clusters.

Distance between observations

Before clustering, we need to measure how far apart observations are. A common choice is Euclidean distance.

For two points,

(x1 , y1 )

and

(x2 , y2 )

the Euclidean distance is:

d = √(x1 − x2 )2 + (y1 − y2 )2

In general, for two observations xi and xj , the distance can be written as:

d(xi , xj )

Linkage methods
A linkage method tells us how to measure the distance between two clusters.

Suppose we have two clusters, A and B.

1. Single Linkage
Single linkage uses the minimum distance between points in two clusters.

d(A, B) = min d(i, j)

i∈A, j∈B

It looks at the closest pair of points between the two clusters.

Single linkage:

connects clusters using the nearest points;

can form long, chain-like clusters;
is sensitive to noise and outliers.

2. Complete Linkage
Complete linkage uses the maximum distance between points in two clusters.

d(A, B) = max d(i, j)

i∈A, j∈B

It looks at the farthest pair of points between the two clusters.

Complete linkage:

forms tight, compact clusters;

avoids clusters that are too spread out;
is the opposite of single linkage.

3. Average Linkage
Average linkage uses the mean distance between all pairs of points in two clusters.

1
d(A, B) = ∑ ∑ d(i, j)
|A||B| i∈A j∈B

Average linkage:

is a compromise between single linkage and complete linkage;

considers all pairwise distances;
often produces balanced clusters.

Quick comparison of linkage methods

Linkage method Distance used Main idea

Single linkage Minimum distance Closest pair of points

Complete linkage Maximum distance Farthest pair of points

Average linkage Mean distance Average of all pairwise distances

Advantages of hierarchical clustering

Hierarchical clustering is useful because:

it does not require choosing the number of clusters at the start;

it gives a visual representation using a dendrogram;
it can use different linkage methods;
it helps us understand the structure of the data.

Disadvantages of hierarchical clustering

Hierarchical clustering also has limitations:

it can be computationally expensive for large datasets;

once clusters are merged or split, the decision cannot easily be undone;
results depend on the distance measure and linkage method chosen;
it can be sensitive to outliers.

Hierarchical clustering vs K-means clustering

Feature Hierarchical clustering K-means clustering

Number of clusters Does not need K at the start Must choose K at the start

Output Dendrogram Cluster labels and centroids

Method Builds a hierarchy Reassigns points to centroids

Flexibility Can choose clusters after viewing dendrogram Must decide K before running

Speed Slower for large datasets Faster for large datasets

Summary
Hierarchical clustering is an unsupervised learning method that groups observations into clusters by building a hierarchy.

The result is shown using a dendrogram.

There are two main types:

1. Agglomerative clustering, which starts with individual observations and merges them.
2. Divisive clustering, which starts with one large cluster and splits it.

The distance between clusters is determined using linkage methods such as:

single linkage;
complete linkage;
average linkage;
centroid linkage.

Hierarchical clustering is useful because it shows the structure of the data and does not require choosing the number of clusters before running the algorithm.

k-NN Clustering and KDE Density Estimation Notes

What is k-NN clustering?
k-NN clustering is a density-based clustering method.

It is based on the idea that clusters are found in areas where the data points are dense.

Unlike k-NN classification, k-NN clustering does not use known class labels.

So, k-NN clustering is an unsupervised learning method.

Main idea
The main idea is:

clusters are formed around high-density regions

A high-density region is an area where many observations are close together.

A low-density region is an area where observations are far apart.

So, k-NN clustering tries to identify the dense regions in the data and group observations according to those regions.

k-NN Density Estimation

Definition
In k-nearest neighbour density estimation, the density at a point x is estimated by looking at the distance from x to its k-th nearest neighbour.

The density estimate is:

k
f^(x) =
nV (x)

where:

k is the number of nearest neighbours;

n is the sample size;
V (x) is the volume around x needed to contain the k nearest neighbours.

Intuition
If the k nearest neighbours are very close to x, then the volume V (x) is small.

This means the density is high.

If the k nearest neighbours are far away from x, then the volume V (x) is large.

This means the density is low.

Therefore:

small neighbourhood ⇒ high density

and

large neighbourhood ⇒ low density

Role of k
The value of k controls the smoothness of the density estimate.

A small value of k gives a very local density estimate.

A large value of k gives a smoother density estimate.

So:

small k ⇒ more detailed, less smooth

and

large k ⇒ smoother, less detailed

However, k should usually not be too close to the sample size n.

If k is too large, the method becomes too smooth and may hide important cluster structure.

k-NN Mode Seeking Clustering

What is mode seeking?
A mode is a local maximum of the density function.

In simple words, a mode is a peak in the density.

In clustering, each mode can represent the centre of a dense region.

So:

mode = high-density peak

Main idea of k-NN mode seeking

k-NN mode seeking clustering works by moving observations toward nearby points with higher estimated density.

Eventually, points move toward a density mode.

Observations that move toward the same mode are placed in the same cluster.

Steps of k-NN mode seeking clustering

Step 1: Estimate density
Estimate the density at each observation using k-NN density estimation.

Step 2: Find higher-density neighbours

For each observation, find a nearby observation with a higher density estimate.

Step 3: Move toward higher density

Each observation is linked to a neighbour with higher density.

This creates a path from low-density points to high-density points.

Step 4: Identify modes

The process continues until a point has no nearby point with higher density.

That point is a density mode.

Step 5: Form clusters

All observations that move toward the same mode are grouped into the same cluster.

In simple words
k-NN mode seeking clustering follows the idea:

point → higher density point → mode

Points that end at the same mode belong to the same cluster.

KDE as an Alternative to k-NN Density Estimation

What is KDE?
Kernel Density Estimation, or KDE, is another non-parametric method used to estimate the density of data.

Instead of using the distance to the k-th nearest neighbour, KDE places a smooth kernel function over each observation.

The densities from all the kernels are then added together to form a smooth density estimate.

KDE formula
For observations x1 , x2 , … , xn , the KDE at point x is:
n
1 x − xi
f^(x) = ∑K( )
nh h
i=1

where:

n is the sample size;

h is the bandwidth;
K is the kernel function;
xi is the i-th observation;
x is the point where the density is estimated.

Bandwidth
The bandwidth h controls the smoothness of the KDE.

A small bandwidth gives a very detailed density estimate.

A large bandwidth gives a smoother density estimate.

So:

small h ⇒ less smooth, more detailed

and

large h ⇒ more smooth, less detailed

Why KDE can replace k-NN density estimation

KDE can be used as an alternative to k-NN density estimation because both methods estimate density without assuming a specific probability distribution.

Both methods are non-parametric density estimation methods.

The difference is how they estimate density.

Method Main idea

k-NN density estimation Uses distance to the k-th nearest neighbour

KDE Places a smooth kernel around each observation

Key difference between k-NN density estimation and KDE

In k-NN density estimation:

the number of neighbours k is fixed;

the neighbourhood size changes depending on the data density.

In KDE:

the bandwidth h is fixed;

the number of points contributing to the estimate changes depending on the data density.

k-NN Density vs KDE

Feature k-NN Density Estimation KDE

Type Non-parametric Non-parametric

Main tuning parameter k Bandwidth h

Main idea Uses distance to the k-th nearest neighbour Uses kernel weights around each point

Smoothness Can be less smooth Usually smoother

Neighbourhood Adaptive size Fixed bandwidth

Density high when k neighbours are close Many points are close to x

Density low when k neighbours are far Few points are close to x

k-NN Clustering Using KDE

Main idea
Instead of estimating density using k-NN, we can estimate density using KDE.

Then clustering is still based on finding density modes.

The difference is that the density estimate comes from KDE instead of k-NN.

So:

k-NN density estimate can be replaced by KDE

Steps using KDE

Step 1: Estimate density using KDE
Use KDE to estimate the density at each observation.

Step 2: Find high-density regions

Identify where the KDE has peaks.

These peaks are the modes.

Step 3: Move observations toward modes

Each observation is associated with a nearby density mode.

Step 4: Form clusters

Observations linked to the same KDE mode are placed in the same cluster.

In simple words
Using KDE in mode seeking clustering means:

estimate smooth density → find modes → form clusters

The modes of the KDE represent the centres of dense regions.

 k-NN Clustering vs k-NN Classification
k-NN clustering and k-NN classification are not the same.

Feature k-NN Clustering k-NN Classification

Learning type Unsupervised Supervised

Labels needed? No Yes

Purpose Find natural groups Predict class labels

Uses density? Yes, in mode seeking Not usually

Output Clusters Predicted classes

Advantages of k-NN Mode Seeking Clustering

k-NN mode seeking clustering is useful because:

it is non-parametric;
it does not assume a specific distribution;
it can find clusters based on density;
it can identify clusters through density modes;
it is an alternative to mean shift clustering.

Disadvantages of k-NN Mode Seeking Clustering

k-NN mode seeking clustering has limitations:

it can be computationally expensive;

the choice of k affects the results;
it can be sensitive to noise;
it may struggle in high-dimensional data;
density estimation becomes harder as dimension increases.

Relationship to Mean Shift Clustering

k-NN mode seeking clustering is an alternative to mean shift clustering.

Both methods are based on density modes.

Mean shift usually uses KDE to estimate the density and then moves points toward density peaks.

k-NN mode seeking uses k-NN density estimation, but KDE can be used as an alternative.

So:

k-NN mode seeking ≈ density mode seeking

and

mean shift ≈ KDE mode seeking

Important exam points

True or False style facts
Statement 1
k should usually be close to n when executing k-NN mode seeking clustering.

False.

If k is too close to n, the density estimate becomes too smooth and may hide cluster structure.

Statement 2
k-NN mode seeking clustering and k-NN classification are essentially the same.

False.

k-NN mode seeking clustering is unsupervised and density-based.

k-NN classification is supervised and uses labelled data.

Statement 3
k-NN mode seeking clustering is computationally expensive.

True.

It can be computationally expensive because distances between many observations need to be calculated.

Statement 4
k-NN mode seeking is an alternative to mean shift clustering.

True.

Both methods are density-based and aim to find modes.

Statement 5
k-NN mode seeking uses non-parametric density estimation.

True.

It uses k-NN density estimation, and KDE can also be used as an alternative non-parametric density estimator.

Statement 6
k-NN mode seeking clustering is a density-based clustering algorithm.

True.

It forms clusters by identifying high-density regions and density modes.

Summary
k-NN clustering is a density-based unsupervised learning method.

It uses density estimation to identify high-density regions in the data.

In k-NN density estimation, density is based on the distance to the k-th nearest neighbour.

The formula is:

k
f^(x) =
nV (x)

KDE can be used as an alternative to k-NN density estimation.

The KDE formula is:

n
1 x − xi
f^(x) = ∑K( )
nh h
i=1

Both k-NN density estimation and KDE are non-parametric density estimation methods.

In mode seeking clustering, observations move toward regions of higher density.

Observations that move toward the same density mode are placed in the same cluster.

Model-Based Clustering
Model-based clustering is a clustering approach where we assume that the data comes from a mixture of probability distributions. Instead of only grouping observations based on
distance, model-based clustering assumes that each cluster is generated by an underlying statistical model.

In simple words:

Each cluster is represented by a probability distribution.

The aim is to estimate these distributions and decide which observation most likely belongs to which cluster.

1. Mixture Modelling Principles

In mixture modelling, we assume that the observed data comes from several hidden groups or populations.

Each group has its own probability distribution.

For example, suppose we have G clusters. Then the overall distribution of the data can be written as a mixture:

G
f(x) = ∑ πg fg (x)
g=1

where:

G is the number of clusters;

πg is the mixing proportion for cluster g;
fg (x) is the probability density function for cluster g;
x is an observation.

Mixing proportions
The value πg represents the probability that an observation belongs to cluster g.

The mixing proportions must satisfy:

0 ≤ πg ≤ 1

and

G
∑ πg = 1
g=1

So, all the cluster probabilities must add up to 1.

The mixture model says:

Overall data distribution = weighted combination of cluster distributions

Each cluster contributes to the overall distribution according to its mixing proportion.

Example
Suppose student marks come from three groups:

Cluster Interpretation

Cluster 1 Low-performing students

Cluster 2 Average-performing students

Cluster 3 High-performing students

Each group may have its own mean and variance.

The total distribution of marks is then a mixture of the three group distributions.

2. Gaussian Mixture Modelling

A Gaussian mixture model, also called a GMM, assumes that each cluster follows a normal distribution.

For G clusters, the model is:

G
f(x) = ∑ πg ϕ(x; µg , Σg )
g=1

where:

πg is the mixing proportion for cluster g;

ϕ(x; µg , Σg ) is the Gaussian density for cluster g;
µg is the mean vector of cluster g;
Σg is the covariance matrix of cluster g.

Meaning of the parameters

Each Gaussian cluster has:

a mean vector, µg ;
a covariance matrix, Σg ;
a mixing proportion, πg .

The mean vector controls the centre of the cluster.

The covariance matrix controls:

the spread of the cluster;

the shape of the cluster;
the orientation of the cluster.

Why Gaussian mixture models are useful

Gaussian mixture models are more flexible than K-means.

K-means assigns each observation to exactly one cluster based on distance.

GMM assigns each observation a probability of belonging to each cluster.

This is called soft clustering.

Soft clustering
In soft clustering, an observation can partially belong to more than one cluster.

For example:

Observation Probability of Cluster 1 Probability of Cluster 2

x1 0.90 0.10

x2 0.55 0.45

x3 0.20 0.80

Observation x2 is uncertain because it has similar probabilities for both clusters.

Hard clustering
Although GMM gives probabilities, we can still assign each observation to one cluster.

We assign the observation to the cluster with the highest probability.

For example, if:

P (Cluster 1 ∣ xi ) = 0.70

and

P (Cluster 2 ∣ xi ) = 0.30

then xi is assigned to Cluster 1.

Estimation Using the EM Algorithm

In model-based clustering, the cluster labels are unknown.

We do not know which observation belongs to which cluster.

The Expectation-Maximisation algorithm, or EM algorithm, is used to estimate the model parameters when the cluster memberships are hidden.

EM algorithm
The EM algorithm has two main steps:

1. E-step
2. M-step

These steps are repeated until the estimates stop changing much.

E-step: Expectation step

In the E-step, we calculate the probability that each observation belongs to each cluster.

These probabilities are called posterior probabilities.

They can be written as:

τig = P (zi = g ∣ xi )

where:

τig is the probability that observation i belongs to cluster g;

zi is the hidden cluster label;
xi is the observed data point.

For a Gaussian mixture model:

πg ϕ(xi ; µg , Σg )
τig = G
∑h=1 πh ϕ(xi ; µh , Σh )

M-step: Maximisation step

In the M-step, we update the model parameters using the probabilities from the E-step.

The updated mixing proportion is:

n
1
πg = ∑ τig
n
i=1

The updated mean is:

n
∑i=1 τig xi
µg = n
∑i=1 τig

The updated covariance matrix is:

n
∑i=1 τig (xi − µg )(xi − µg )T
Σg = n
∑i=1 τig

EM algorithm summary
The EM algorithm works as follows:

1. Start with initial parameter values.

2. Compute cluster membership probabilities.
3. Update the parameters using those probabilities.
4. Repeat until convergence.

In simple words:

Estimate probabilities → update parameters → repeat

Mixtures in the Exponential Family

What is the exponential family?
The exponential family is a large class of probability distributions.

It includes many common distributions such as:

Normal distribution;
Poisson distribution;
Binomial distribution;
Gamma distribution;
Exponential distribution.

General mixture model

A mixture model does not have to use Gaussian distributions.

Instead, each cluster can follow a distribution from the exponential family.

The general mixture model is:

G
f(x) = ∑ πg fg (x; θg )
g=1

where:

fg (x; θg ) is the distribution for cluster g;

θg is the parameter for cluster g;
πg is the mixing proportion.

Examples
Different data types may require different mixture models.

Data type Possible mixture model

Continuous data Gaussian mixture

Count data Poisson mixture

Binary data Bernoulli mixture

Positive skewed data Gamma mixture

Waiting times Exponential mixture

Poisson mixture model

For count data, we can use a Poisson mixture model.

The model is:

G e−λg λxg
f(x) = ∑ πg
x!
g=1

where:

λg is the mean count for cluster g;

πg is the mixing proportion for cluster g.

This is useful when clustering count data, such as:

number of claims;
number of accidents;
number of purchases;
number of website visits.

Bernoulli mixture model

For binary data, we can use a Bernoulli mixture model.

The model is:

G
f(x) = ∑ πg pxg (1 − pg )1−x
g=1

where:

x can be 0 or 1;
pg is the probability of success in cluster g.

This is useful for clustering yes/no or success/failure data.

Some Extensions of Model-Based Clustering

Mixtures with different covariance structures
In Gaussian mixture models, the covariance matrices can be restricted in different ways.

This changes the shape of the clusters.

For example:

Covariance structure Meaning

Equal covariance All clusters have the same shape and size

Different covariance Clusters may have different shapes and sizes

Diagonal covariance Variables are assumed uncorrelated within clusters

Spherical covariance Clusters are round

Mixture of regressions
In mixture of regressions, each cluster has its own regression model.

This is useful when different groups follow different relationships.

For example:

y = β 0g + β 1g x + ϵ

where each cluster g has its own regression coefficients.

High-dimensional model-based clustering

For high-dimensional data, model-based clustering can be difficult because there are many parameters.

Possible solutions include:

dimension reduction;
parsimonious covariance structures;
factor analyzers;
variable selection.

Robust mixture models

Gaussian mixture models can be sensitive to outliers.

Robust extensions use distributions with heavier tails, such as the t-distribution.

A t-mixture model can handle outliers better than a Gaussian mixture model.

Model-based clustering with missing data

Mixture models can be extended to handle missing data.

This is useful because the EM algorithm can estimate missing values while estimating cluster membership.

Cluster Evaluation and Fit Measures

After fitting a clustering model, we need to decide whether the clustering is good.

We may want to answer questions such as:

How many clusters should we use?

Which model fits the data best?
Are the clusters well separated?
Are the clusters meaningful?

A. Likelihood
The likelihood measures how well the model explains the observed data.

For a mixture model, the likelihood is:

n G
L = ∏ ∑ πg fg (xi ; θg )
i=1 g=1

The log-likelihood is:

n G
ℓ = ∑ log(∑ πg fg (xi ; θg ))
i=1 g=1

A larger log-likelihood usually means a better fit.

However, using more clusters usually increases the likelihood, so we need penalties for model complexity.

B. AIC
The Akaike Information Criterion is:

AIC = −2ℓ + 2m
where:

ℓ is the log-likelihood;
m is the number of estimated parameters.

A smaller AIC indicates a better model.

C. BIC
The Bayesian Information Criterion is:

BIC = −2ℓ + m log(n)

where:

ℓ is the log-likelihood;
m is the number of estimated parameters;
n is the sample size.

A smaller BIC indicates a better model.

BIC penalizes model complexity more strongly than AIC, especially when the sample size is large.

D. Entropy
Entropy measures the uncertainty in cluster assignment.

For model-based clustering, entropy can be written as:

n G
E = − ∑ ∑ τig log(τig )
i=1 g=1

where:

τig is the posterior probability that observation i belongs to cluster g.

Low entropy means the clustering is more certain.

High entropy means many observations have uncertain cluster membership.

E. Posterior probabilities
Posterior probabilities show how strongly each observation belongs to each cluster.

If an observation has posterior probabilities:

(0.98, 0.01, 0.01)

then the assignment is very certain.

If an observation has posterior probabilities:

(0.40, 0.35, 0.25)

then the assignment is uncertain.

F. Confusion matrix
If true labels are available, a confusion matrix can be used to compare the cluster labels with the true labels.

However, in clustering, true labels are usually not available.

G. Silhouette coefficient
The silhouette coefficient measures how well an observation fits into its assigned cluster compared with other clusters.

For observation i:

bi − a i
si =
max(ai , bi )

where:

ai is the average distance from observation i to other observations in the same cluster;
bi is the smallest average distance from observation i to observations in another cluster.

The silhouette value lies between −1 and 1.

Silhouette value Interpretation

Close to 1 Well clustered

Close to 0 Between clusters

Close to −1 Possibly assigned to the wrong cluster

Model-Based Clustering vs K-means

Feature K-means Model-based clustering

Main idea Distance-based clustering Probability-based clustering

Cluster shape Usually spherical Can be elliptical or flexible

Assignment Hard assignment Soft assignment

Uncertainty Not directly measured Posterior probabilities available

Model selection Elbow method, silhouette AIC, BIC, likelihood, entropy

Assumption Clusters based on distance to centroid Data comes from mixture distributions

Advantages of Model-Based Clustering

Model-based clustering is useful because:

it gives a statistical model for the data;

it allows soft cluster assignment;
it provides probabilities of cluster membership;
it can compare models using AIC and BIC;
it can handle different cluster shapes;
it can be extended to different data types.

Disadvantages of Model-Based Clustering

Model-based clustering has some limitations:

it can be computationally expensive;

it depends on distributional assumptions;
it may be sensitive to starting values;
the EM algorithm may converge to a local maximum;
choosing the correct number of clusters can still be difficult.

Summary
Model-based clustering assumes that the data comes from a mixture of probability distributions.

The general mixture model is:

G
f(x) = ∑ πg fg (x; θg )
g=1

Gaussian mixture models assume each cluster follows a normal distribution.

The EM algorithm is commonly used to estimate the model parameters.

Mixture models can also be built using other distributions from the exponential family, such as Poisson, Bernoulli, Gamma, and Exponential distributions.

Cluster quality can be evaluated using:

log-likelihood;
AIC;
BIC;
entropy;
posterior probabilities;
silhouette coefficient.

Model-based clustering is more flexible than K-means because it allows probability-based clustering and can measure uncertainty in cluster membership.

In [ ]:

In [ ]:

In [ ]:

In [ ]: