CST 413 Machine Learning - Module 4

Unsupervised Learning: Complete Exam Guide

PART 1: SIMILARITY MEASURES & DISTANCE METRICS

1.1 EUCLIDEAN DISTANCE

Definition: Represents the shortest distance between two points, calculated as the straight-line distance.

Formula for 2D:

d = √[(p₁ - q₁)² + (p₂ - q₂)²]

Formula for n-Dimensions:

Dₑ = [∑(pᵢ - qᵢ)²]^(1/2) where i = 1 to n

Problem 1: Calculate Euclidean distance between A(3,4) and B(6,8)

Solution:

d = √[(3-6)² + (4-8)²]
d = √[(-3)² + (-4)²]
d = √[9 + 16]
d = √25
d = 5 units

Problem 2: Find Euclidean distance between point P(1,2,3) and Q(4,5,6) in 3D space

Solution:

Dₑ = [∑(pᵢ - qᵢ)²]^(1/2)
Dₑ = [(1-4)² + (2-5)² + (3-6)²]^(1/2)
Dₑ = [(-3)² + (-3)² + (-3)²]^(1/2)
Dₑ = [9 + 9 + 9]^(1/2)
Dₑ = [27]^(1/2)
Dₑ = 5.196 units
1.2 MANHATTAN DISTANCE
Definition: Sum of absolute differences between points across all dimensions. Also called taxicab distance or
L1 distance.

Formula for 2D:

d = |p₁ - q₁| + |p₂ - q₂|

Formula for n-Dimensions:

Dₘ = ∑|pᵢ - qᵢ| where i = 1 to n

Problem 3: Calculate Manhattan distance between A(3,4) and B(6,8)

Solution:

d = |3-6| + |4-8|
d = |-3| + |-4|
d=3+4
d = 7 units

Comparison with Euclidean: Manhattan distance (7) > Euclidean distance (5) for the same points.

Problem 4: Find Manhattan distance for P(1,2,3) and Q(4,5,6)

Solution:

Dₘ = |1-4| + |2-5| + |3-6|

Dₘ = |-3| + |-3| + |-3|
Dₘ = 3 + 3 + 3
Dₘ = 9 units

1.3 MINKOWSKI DISTANCE

Definition: Generalized form of Euclidean and Manhattan distances.

Formula:

D = [∑(pᵢ - qᵢ)^p]^(1/p) where i = 1 to n

Properties:
 When p = 1 → Manhattan distance

When p = 2 → Euclidean distance

When p = ∞ → Chebyshev distance (max difference)

Problem 5: Calculate Minkowski distance with p=3 between A(1,2) and B(4,6)

Solution:

D = [∑(pᵢ - qᵢ)³]^(1/3)
D = [(1-4)³ + (2-6)³]^(1/3)
D = [(-3)³ + (-4)³]^(1/3)
D = [-27 + (-64)]^(1/3)
D = [-91]^(1/3)
D = -4.498 (for odd p, result can be negative)

1.4 HAMMING DISTANCE

Definition: Measures similarity between two strings of equal length by counting positions where characters
differ.

Problem 6: Find Hamming distance between "euclidean" and "manhattan"

Solution:

euclidean
manhattan
--------
e-m (differ) ✗
u-a (differ) ✗
c-n (differ) ✗
l-h (differ) ✗
i-a (differ) ✗
d-t (differ) ✗
e-t (differ) ✗
a-a (same) ✓
n-n (same) ✓

Hamming distance = 7

1.5 COSINE SIMILARITY

Definition: Measures similarity between two vectors by calculating cosine of angle between them. Ranges from
-1 to 1.

Formula:

Cosine Similarity = (x · y) / (||x|| × ||y||)

Where:
x · y = dot product = ∑(xᵢ × yᵢ)
||x|| = magnitude of x = √(∑xᵢ²)
||y|| = magnitude of y = √(∑yᵢ²)

Problem 7: Calculate cosine similarity between x = {3, 2, 0, 5} and y = {1, 0, 0, 0}

Solution:

Step 1: Calculate dot product (x · y)

x · y = (3×1) + (2×0) + (0×0) + (5×0)
x·y=3+0+0+0=3

Step 2: Calculate magnitude of x

||x|| = √(3² + 2² + 0² + 5²)
||x|| = √(9 + 4 + 0 + 25)
||x|| = √38 = 6.164

Step 3: Calculate magnitude of y

||y|| = √(1² + 0² + 0² + 0²)
||y|| = √1 = 1

Step 4: Calculate cosine similarity

Cosine Similarity = 3 / (6.164 × 1)
Cosine Similarity = 3 / 6.164
Cosine Similarity ≈ 0.487

Interpretation: Value of 0.487 indicates moderate similarity between vectors.

Problem 8: Find cosine similarity between a = {1, 0, 1} and b = {1, 1, 0}

Solution:
 a · b = (1×1) + (0×1) + (1×0) = 1

||a|| = √(1² + 0² + 1²) = √2 = 1.414

||b|| = √(1² + 1² + 0²) = √2 = 1.414

Cosine Similarity = 1 / (1.414 × 1.414)

Cosine Similarity = 1 / 2
Cosine Similarity = 0.5

PART 2: K-MEANS CLUSTERING

2.1 K-MEANS ALGORITHM

Overview: Unsupervised learning algorithm that groups data into k clusters based on inherent similarity.

Steps:

1. Initialization: Randomly select k cluster centroids

2. Assignment Step: Assign each data point to nearest centroid

3. Update Step: Recalculate centroids by averaging points in each cluster

4. Repeat: Continue until centroids don't change or max iterations reached

Problem 9: Perform K-means clustering with k=2 for dataset: {2, 4, 10, 12, 3, 20}

Solution:

Iteration 1:

Initial centroids: C₁ = 2, C₂ = 20

Assign points to nearest centroid:

Point 2: distance to C₁ = 0, distance to C₂ = 18 → Cluster 1

Point 4: distance to C₁ = 2, distance to C₂ = 16 → Cluster 1
Point 10: distance to C₁ = 8, distance to C₂ = 10 → Cluster 1
Point 12: distance to C₁ = 10, distance to C₂ = 8 → Cluster 2
Point 3: distance to C₁ = 1, distance to C₂ = 17 → Cluster 1
Point 20: distance to C₁ = 18, distance to C₂ = 0 → Cluster 2

Cluster 1: {2, 4, 10, 3}

Cluster 2: {12, 20}

Update centroids:
 C₁ = (2 + 4 + 10 + 3) / 4 = 19 / 4 = 4.75
C₂ = (12 + 20) / 2 = 32 / 2 = 16

Iteration 2: Assign points with new centroids (C₁ = 4.75, C₂ = 16):

Point 2: |2 - 4.75| = 2.75, |2 - 16| = 14 → Cluster 1

Point 4: |4 - 4.75| = 0.75, |4 - 16| = 12 → Cluster 1
Point 10: |10 - 4.75| = 5.25, |10 - 16| = 6 → Cluster 1
Point 12: |12 - 4.75| = 7.25, |12 - 16| = 4 → Cluster 2
Point 3: |3 - 4.75| = 1.75, |3 - 16| = 13 → Cluster 1
Point 20: |20 - 4.75| = 15.25, |20 - 16| = 4 → Cluster 2

Cluster 1: {2, 4, 10, 3}

Cluster 2: {12, 20}

Update centroids:

C₁ = (2 + 4 + 10 + 3) / 4 = 4.75
C₂ = (12 + 20) / 2 = 16

Convergence: Centroids unchanged → Algorithm terminates

Final Clusters:

Cluster 1: {2, 3, 4, 10}

Cluster 2: {12, 20}

2.2 K-MEANS CHARACTERISTICS

Advantages:

Relatively efficient algorithm

Simple to understand and implement

Scales well to large datasets

Disadvantages:

1. Dependency on Initial Guess: Final results sensitive to initialization

2. Sensitivity to Outliers: Extreme values distort clustering

3. Assumption of Round Clusters: Struggles with non-spherical clusters

 4. Need to Know k: Must pre-specify number of clusters

5. Local Optimum: May not find global optimal solution

6. Computational Cost: Expensive for very large datasets

Problem 10: Discuss why outliers affect K-means clustering.

Answer: K-means treats all data points equally. Outliers (extreme values) can pull centroids away from the true
cluster centers, distorting the clustering results. For example, if most data points are between 0-10 but one
outlier is 1000, the centroid moves significantly toward the outlier, creating inaccurate clusters.

PART 3: HIERARCHICAL AGGLOMERATIVE CLUSTERING

3.1 HIERARCHICAL CLUSTERING OVERVIEW

Definition: Builds a hierarchy of clusters using either bottom-up (agglomerative) or top-down (divisive)
approach.

Two Main Types:

1. Agglomerative (AGNES - Agglomerative Nesting)

Bottom-up approach

Starts with each point as single cluster

Repeatedly merges most similar clusters

Results in dendrogram

2. Divisive (DIANA - Divisive Analysis)

Top-down approach

Starts with all points in one cluster

Repeatedly splits most heterogeneous clusters

Inverse of agglomerative

Advantages over K-means:

No need to pre-specify number of clusters

Provides dendrogram for visualization

Better for identifying small clusters (agglomerative)

3.2 LINKAGE METHODS

3.2.1 SINGLE LINKAGE (Minimum Linkage)

Definition: Distance between two clusters = minimum distance between any two points in different clusters

Formula: D(A,B) = min(d(a,b)) where a ∈ A, b ∈ B

Characteristics:

Produces long, loose clusters

Susceptible to chaining effect

Good at identifying small clusters

3.2.2 COMPLETE LINKAGE (Maximum Linkage)

Definition: Distance between two clusters = maximum distance between any two points in different clusters

Formula: D(A,B) = max(d(a,b)) where a ∈ A, b ∈ B

Characteristics:

Produces compact, spherical clusters

More robust than single linkage

Avoids chaining problem

3.2.3 AVERAGE LINKAGE (Mean Linkage)

Definition: Distance between two clusters = average of all pairwise distances

Formula: D(A,B) = (1/|A|×|B|) × ∑∑d(a,b)

Characteristics:

Balance between single and complete linkage

More stable than single linkage

Computationally efficient

3.2.4 CENTROID LINKAGE

Definition: Distance between two clusters = distance between their centroids

Formula: D(A,B) = d(cₐ, cᵦ)

Characteristics:

Uses cluster centers (mean vectors)

 Fast computation

Sometimes produces unusual dendrograms

3.3 HIERARCHICAL CLUSTERING EXAMPLE

Problem 11: Perform hierarchical clustering with single linkage on dataset: {7, 10, 20, 28, 35}

Solution:

Step 1: Initialize - Each point is a cluster

C₁={7}, C₂={10}, C₃={20}, C₄={28}, C₅={35}

Step 2: Calculate pairwise distances

d(7,10) = 3 d(10,20) = 10 d(20,28) = 8 d(28,35) = 7

d(7,20) = 13 d(10,28) = 18 d(20,35) = 15
d(7,28) = 21 d(10,35) = 25
d(7,35) = 28

Step 3: Merge closest clusters Minimum distance = 3 between {7} and {10}

Merge: {7,10}, {20}, {28}, {35}

Step 4: Recalculate distances (Single Linkage)

d({7,10},20) = min(13,10) = 10
d({7,10},28) = min(21,18) = 18
d({7,10},35) = min(28,25) = 25
d(20,28) = 8
d(20,35) = 15
d(28,35) = 7

Step 5: Merge next closest Minimum = 7 between {28} and {35}

Merge: {7,10}, {20}, {28,35}

Step 6: Recalculate distances

 d({7,10},20) = 10
d({7,10},{28,35}) = min(21,25,18,18) = 18
d(20,{28,35}) = min(8,15) = 8

Step 7: Merge next closest Minimum = 8 between {20} and {28,35}

Merge: {7,10}, {20,28,35}

Step 8: Recalculate distances

d({7,10},{20,28,35}) = min(13,21,10,18,25,25) = 10

Step 9: Final merge

{7,10,20,28,35}

Dendrogram (Single Linkage):

___________________
|
_______|_______
| |
___|___ {20,28,35}
| | |
{7} {10} ____|____
| |
{20} __|__
| |
{28} {35}

3.4 COMPLETE LINKAGE EXAMPLE

Problem 12: Perform hierarchical clustering with complete linkage on dataset: {7, 10, 20, 28, 35}

Solution:

Using same initial pairwise distances...

Step 1-2: Merge {7,10} (distance = 3)

Step 3: Recalculate distances (Complete Linkage)

 d({7,10},20) = max(13,10) = 13
d({7,10},28) = max(21,18) = 21
d({7,10},35) = max(28,25) = 28
d(20,28) = 8
d(20,35) = 15
d(28,35) = 7

Step 4: Merge {28,35} (distance = 7)

Step 5: Recalculate

d({7,10},20) = 13
d({7,10},{28,35}) = max(21,28) = 28
d(20,{28,35}) = max(8,15) = 15

Step 6: Merge {20} with {28,35} (distance = 15)

Step 7: Final merge {7,10} with {20,28,35} (distance = 28)

Note: Complete linkage produces more compact clusters than single linkage.

PART 4: PRINCIPAL COMPONENT ANALYSIS (PCA)

4.1 PCA OVERVIEW

Definition: Statistical method transforming high-dimensional data into lower dimensions while preserving
maximum information.

Key Concepts:

Identifies new axes called principal components

Components are orthogonal (uncorrelated)

Ordered by variance explained

First component explains most variance

Applications:

Data visualization

Noise reduction

Feature extraction

Data compression
4.2 WHY DIMENSIONALITY REDUCTION IS NEEDED

Problems with High Dimensionality:

1. Computational Complexity: Processing time grows exponentially

2. Overfitting: Models fit noise instead of patterns

3. Difficulty in Visualization: Can't visualize beyond 3D

4. Redundancy: Correlated features convey similar information

5. Curse of Dimensionality: Sparse data in high dimensions

4.3 STEPS OF PCA

Step 1: Data Standardization

Subtract mean from each feature

Divide by standard deviation

Formula: X_standardized = (X - mean) / std_dev

Ensures all features have equal importance

Step 2: Compute Covariance Matrix

Measures relationships between features

Shows which features vary together

Step 3: Calculate Eigenvalues and Eigenvectors

Eigenvalues: Amount of variance in each direction

Eigenvectors: Directions of principal components

Step 4: Sort Eigenvalues and Eigenvectors

Arrange eigenvalues in descending order

Reorder eigenvectors accordingly

Step 5: Select Principal Components

Choose top k components

Can use elbow method or explained variance ratio

4.4 PCA NUMERICAL EXAMPLE

Problem 13: Apply PCA to dataset:
 Data:
Feature X: [2.5, 0.5, 2.2, 1.9, 3.1, 2.3, 0.0, 0.1]
Feature Y: [2.4, 0.7, 2.9, 2.2, 3.0, 2.7, 1.3, 1.4]

Solution:

Step 1: Standardize Data

Mean of X = 1.575
Mean of Y = 2.15
Std Dev X ≈ 1.097
Std Dev Y ≈ 0.861

Standardized values:
Point 1: [(2.5-1.575)/1.097, (2.4-2.15)/0.861] = [0.844, 0.290]
Point 2: [(0.5-1.575)/1.097, (0.7-2.15)/0.861] = [-0.983, -1.681]
... (continue for all points)

Step 2: Create Covariance Matrix

C = [ [cov(X,X) cov(X,Y)]
[cov(Y,X) cov(Y,Y)] ]

Approximately:
C = [ [1.0 0.8]
[0.8 1.0] ]

Step 3: Calculate Eigenvalues and Eigenvectors

Eigenvalues: λ₁ ≈ 1.8, λ₂ ≈ 0.2

Eigenvectors:
v₁ = [0.707, 0.707] (direction of maximum variance)
v₂ = [-0.707, 0.707] (orthogonal to v₁)

Step 4: Explained Variance Ratio

Total variance = 1.8 + 0.2 = 2.0

PC1 explains: 1.8/2.0 = 90%
PC2 explains: 0.2/2.0 = 10%

Step 5: Dimensionality Reduction

 Use only PC1 to reduce from 2D to 1D

Retain 90% of information

Project original data onto first eigenvector

PART 5: COMPARISON OF ALGORITHMS

K-means vs Hierarchical Clustering

Feature K-means Hierarchical

Approach Partitional Hierarchical

Input Must specify k No k needed

Output k clusters Dendrogram

Initialization Sensitive Less sensitive

Scalability Better for large data Slower for large data

Cluster Shape Spherical Any shape

Outlier Sensitivity High Moderate

Time Complexity O(nkd·i) O(n²) to O(n³)

 

PART 6: COMMON EXAM QUESTIONS & ANSWERS

Q1: What is the difference between supervised and unsupervised learning?

Answer: Supervised learning uses labeled training data to predict outputs. Unsupervised learning finds patterns
in unlabeled data without predefined outputs.

Q2: Why is standardization important in PCA?

Answer: Standardization ensures all features contribute equally regardless of their original scale. Without it,
features with larger values would dominate the analysis.

Q3: What is dendrogram and its use?

Answer: A dendrogram is a tree diagram showing hierarchical relationships between clusters. It helps visualize
which clusters are most similar and decide where to cut the tree to get desired number of clusters.

Q4: State limitations of K-means.

Answer:

1. Dependency on initial centroids

2. Sensitivity to outliers
 3. Assumes spherical clusters

4. Must pre-specify k

5. Can converge to local optimum

6. Computationally expensive for very large datasets

Q5: Compare single and complete linkage methods.

Answer: Single linkage uses minimum distance (produces loose clusters, prone to chaining). Complete linkage
uses maximum distance (produces compact clusters, more robust). Complete linkage generally gives better
results.

Q6: Why is cosine similarity preferred over Euclidean distance in text analysis?

Answer: Cosine similarity measures angle between vectors, not magnitude. In text analysis, document length
shouldn't affect similarity, making cosine similarity more appropriate.

Q7: How does PCA handle correlated features?

Answer: PCA creates new uncorrelated features (principal components) by finding directions of maximum
variance. This eliminates redundancy in correlated features.

Q8: Explain the elbow method in K-means.

Answer: Plot inertia (within-cluster sum of squares) vs. number of clusters (k). Find the "elbow" point where
adding more clusters doesn't significantly reduce inertia. This k value is optimal.

PRACTICE PROBLEMS
Problem Set 1: Distance Metrics

1. Calculate Euclidean distance: A(1,2,3), B(4,5,6)

2. Calculate Manhattan distance: X(5,10), Y(2,3)

3. Calculate cosine similarity: u={2,3,1}, v={1,0,2}

4. Find Hamming distance: "ALGORITHM" and "ALTRUISTIC"

Problem Set 2: K-means

5. Apply K-means (k=3) to: {1, 2, 3, 8, 9, 10} with initial centroids 1, 3, 9

6. Discuss why K-means failed to converge in certain scenarios

Problem Set 3: Hierarchical Clustering

7. Build dendrogram using average linkage for: {5, 10, 15, 20, 25}
 8. Compare results using single vs. complete linkage

Problem Set 4: PCA

9. Explain steps to reduce 5D data to 2D using PCA

10. How much variance is retained when selecting top 3 principal components?

KEY FORMULAS REFERENCE

Euclidean Distance: d = √[∑(pᵢ-qᵢ)²]

Manhattan Distance: d = ∑|pᵢ-qᵢ|
Minkowski Distance: d = [∑(pᵢ-qᵢ)ᵖ]^(1/p)
Cosine Similarity: cos(θ) = (x·y)/(||x||×||y||)
PCA Variance: Var = (λᵢ/∑λⱼ) × 100%

Good luck with your exam! Practice these problems and understand the concepts thoroughly.