Scribd
Upload
3 views2 pages

Clustering Methods Objective Functions

The document outlines various clustering methods used in unsupervised learning, including K-Means, Hierarchical Clustering, DBSCAN, Gaussian Mixture Model (GMM), and Spectral Clustering. Each method is described with its mathematical model and objective function, focusing on how data points are grouped based on similarity. Key concepts include distance metrics, density connectivity, and probabilistic modeling.

Uploaded by

malikmateen123123
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
3 views2 pages

Clustering Methods Objective Functions

The document outlines various clustering methods used in unsupervised learning, including K-Means, Hierarchical Clustering, DBSCAN, Gaussian Mixture Model (GMM), and Spectral Clustering. Each method is described with its mathematical model and objective function, focusing on how data points are grouped based on similarity. Key concepts include distance metrics, density connectivity, and probabilistic modeling.

Uploaded by

malikmateen123123
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Clustering Methods: Mathematical Models and Objective Functions

Clustering is an unsupervised learning approach that groups data points into clusters such
that points in the same cluster are more similar to each other than to those in other clusters.
The similarity is usually defined using a distance metric (e.g., Euclidean distance).

Below are the key clustering methods along with their mathematical formulations and
objectives.

1. K-Means Clustering
Mathematical Model:

Given a dataset X = {x₁, x₂, ..., xₙ} with n data points, we want to partition it into K clusters C
= {C₁, C₂, ..., Cₖ}. Each cluster Cⱼ has a centroid μⱼ, calculated as:

μⱼ = (1 / |Cⱼ|) Σₓᵢ∈Cⱼ xᵢ

Objective Function:

J = Σⱼ=1ᵏ Σₓᵢ∈Cⱼ ||xᵢ - μⱼ||²

2. Hierarchical Clustering
Mathematical Model:

This method builds a hierarchy of clusters either in a bottom-up (agglomerative) or top-


down (divisive) manner. Each pair of clusters Cᵢ, Cⱼ are merged based on a linkage criterion.

Objective Function (Distance Criteria):

Single Linkage: D(Cᵢ, Cⱼ) = min ||x - y|| for x ∈ Cᵢ, y ∈ Cⱼ


Complete Linkage: D(Cᵢ, Cⱼ) = max ||x - y|| for x ∈ Cᵢ, y ∈ Cⱼ
Average Linkage: D(Cᵢ, Cⱼ) = mean ||x - y|| for x ∈ Cᵢ, y ∈ Cⱼ

3. DBSCAN (Density-Based Spatial Clustering of Applications with Noise)


Mathematical Model:

DBSCAN defines clusters as high-density regions separated by low-density areas. It uses


two parameters: ε (neighborhood radius) and MinPts (minimum points in neighborhood).

Objective Function:

DBSCAN has no explicit global objective function. The goal is to maximize density
connectivity, ensuring:
- Core points: at least MinPts in ε-neighborhood.
- Density reachability: points reachable from core points belong to the same cluster.
4. Gaussian Mixture Model (GMM)
Mathematical Model:

Assume the data is generated from a mixture of K Gaussian distributions:


p(x) = Σₖ=1ᵏ πₖ N(x | μₖ, Σₖ)

where πₖ are mixture weights, μₖ are means, and Σₖ are covariance matrices.

Objective Function:

Maximize the log-likelihood:


L(θ) = Σᵢ=1ⁿ log [Σₖ=1ᵏ πₖ N(xᵢ | μₖ, Σₖ)]
Parameters are estimated using the Expectation-Maximization (EM) algorithm.

5. Spectral Clustering
Mathematical Model:

Spectral clustering constructs a similarity graph G where nodes represent data points and
edges represent similarity.
Compute the graph Laplacian L = D - W, where W is the similarity matrix and D is the degree
matrix.

Objective Function:

Minimize the normalized cut (Ncut):


Ncut(A, B) = (cut(A,B)/assoc(A,V)) + (cut(A,B)/assoc(B,V))
where cut(A,B) = Σ_{i∈A, j∈B} wᵢⱼ.

Summary Table
Method Mathematical Model Objective Function

K-Means Assign points to nearest Minimize within-cluster


centroid variance

Hierarchical Merge/split clusters Based on linkage distance


recursively

DBSCAN Density-based clustering Maximize density


connectivity

GMM Probabilistic Gaussian Maximize log-likelihood


components

Spectral Clustering Graph-based eigen Minimize normalized cut


decomposition (Ncut)

You might also like