Unsupervised Learning: Clustering & Dimensionality Reduction

TAKEAWAYS:

• Clustering groups unlabeled data into meaningful clusters (e.g., customer segmentation) using distance metrics like Euclidean or Manhattan.
• K-means iteratively assigns points to centroids and updates centroids until convergence, but struggles with non-spherical clusters.
• Hierarchical clustering builds a dendrogram (tree of clusters) using agglomerative or divisive approaches, ideal for small datasets.
• Dimensionality reduction (PCA, t-SNE) projects high-dimensional data into 2D/3D while preserving structure, critical for visualization and speed.
• Real-world use: E-sewa clusters users by transaction patterns; Daraz reduces product features for faster search; Ncell optimizes network traffic via PCA.
• Exam focus: Know the math (Euclidean distance, covariance matrices), pseudocode, and when to use each method (e.g., K-means for scalability, hierarchical for interpretability).

---

1. Clustering: Grouping Unlabeled Data

Clustering is an unsupervised learning technique that organizes data into groups (clusters) based on similarity. Unlike supervised learning, there are no predefined labels—only the data itself guides the grouping.

Key Concepts

• Cluster: A collection of similar data points.
• Centroid: The mean position of all points in a cluster (for K-means).
• Distance Metrics: How similarity is measured (Euclidean, Manhattan, Cosine).
• Objective: Maximize intra-cluster similarity and minimize inter-cluster similarity.

Why Clustering?

• Exploratory Data Analysis (EDA): Discover hidden patterns (e.g., customer segments in eSewa).
• Anomaly Detection: Identify outliers (e.g., fraud in bank transactions).
• Data Compression: Reduce storage by grouping similar data (e.g., image pixels).

---

Figure 1: K-means iteration loop (simplified).

---

2. K-means Clustering: Step-by-Step

K-means is the most popular clustering algorithm. It works as follows:

Algorithm Steps

1. Initialize: Choose k random centroids (e.g., C1 = (1,1), C2 = (5,4)).
2. Assign: For each point, compute Euclidean distance to all centroids and assign to the nearest one.
3. Update: Recalculate centroids as the mean of all points in each cluster.
4. Repeat: Steps 2–3 until centroids no longer move (convergence).

Euclidean Distance Formula

For points P = (x1, y1) and Q = (x2, y2): $$\text{Distance}=\sqrt{(x2-x1{)}^2+(y2-y1{)}^2}$$

Worked Example: One Iteration

Data Points: (1,1), (2,1), (4,3), (5,4) Initial Centroids: C1 = (1,1), C2 = (5,4)

New Centroids:

• C1_new = mean((1,1), (2,1)) = (1.5, 1)
• C2_new = mean((4,3), (5,4)) = (4.5, 3.5)

---

Advantages/Disadvantages

---

3. Hierarchical Clustering: Building a Cluster Tree

Unlike K-means, hierarchical clustering creates a dendrogram (tree of clusters). There are two approaches:

1. Agglomerative: Start with each point as its own cluster; merge the closest pairs.
2. Divisive: Start with one cluster; recursively split it.

Linkage Criteria

• Single: Distance between closest points in clusters.
• Complete: Distance between farthest points.
• Average: Mean distance between all pairs.

Worked Example: Agglomerative Clustering

Data: A(1,2), B(1.5,1.8), C(5,8), D(5.1,8.1) Steps:

1. Compute all pairwise distances (Euclidean).
2. Merge A and B (smallest distance = 0.28).
3. Merge C and D (distance = 0.1).
4. Merge the two clusters (distance between (A,B) and (C,D) = 6.5).

---

Figure 2: Dendrogram for hierarchical clustering (simplified).

---

When to Use Hierarchical Clustering?

• Small datasets (n < 10,000).
• Need for interpretability (e.g., biological taxonomy).
• Non-spherical clusters.

---

4. Dimensionality Reduction: Simplifying Data

High-dimensional data (e.g., images, text) is hard to visualize and slow to process. Dimensionality reduction projects data into fewer dimensions while preserving structure.

Key Methods

---

5. Principal Component Analysis (PCA)

PCA transforms data into a new coordinate system where:

1. The first axis (PC1) captures the most variance.
2. The second axis (PC2) captures the next most variance, and so on.

Steps

1. Standardize: Scale features to zero mean and unit variance.
2. Compute Covariance Matrix: Measures how features vary together.
3. Eigen Decomposition: Find eigenvalues and eigenvectors.
4. Select Top k Components: Choose eigenvectors with largest eigenvalues.
5. Project Data: Multiply data by selected eigenvectors.

Worked Example: PCA on 2D Data

Data:

X = [ [1, 2], [2, 3], [3, 3], [4, 5] ]

1. Standardize:
   • Mean of X1 = 2.5, X2 = 3.5.
   • Subtract mean: X1_new = [-1.5, -0.5, 0.5, 1.5], X2_new = [-1.5, -0.5, -0.5, 1.5].
2. Covariance Matrix: $$\text{Cov}=\left[\begin{array}{cc}1.25& 1.25\\ 1.25& 1.25\end{array}\right]$$
3. Eigenvectors:
   • PC1 = [0.707, 0.707] (captures 100% variance in this case).
   • PC2 = [-0.707, 0.707] (captures 0% variance).
4. Project Data: Multiply by PC1 to get 1D representation.

---

Real-World Application: NTC Network Traffic

NTC uses PCA to reduce the dimensionality of network traffic data (e.g., from 100 features to 3) for faster anomaly detection. This helps identify congestion patterns without losing critical information.

---

6. When to Use Which Method?

---

In the Real World

1. eSewa Customer Segmentation

   • Idea Used: K-means clustering.
   • How: Groups users by transaction frequency, amount, and service type (e.g., electricity, tax) to personalize offers. For example:
     • Cluster 1: High-frequency, low-amount users (students).
     • Cluster 2: Low-frequency, high-amount users (businesses).
   • Impact: Targeted discounts for each segment (e.g., 10% off for students during exam season).

2. Daraz Product Recommendations

   • Idea Used: PCA + K-means.
   • How: Reduces product features (e.g., from 50 attributes to 3) for faster similarity search. Then clusters similar products to recommend alternatives (e.g., "Customers who bought this also bought...").
   • Example: A user searches for "running shoes." PCA compresses the feature space, and K-means finds the nearest product clusters (e.g., "Nike Air," "Adidas Ultraboost").

3. Ncell Network Optimization

   • Idea Used: Hierarchical clustering.
   • How: Groups cell towers by signal strength and user density to optimize routing. For example:
     • Cluster 1: High-traffic towers in Kathmandu (prioritize bandwidth).
     • Cluster 2: Low-traffic towers in rural areas (reduce energy use).
   • Result: 20% reduction in latency during peak hours.

4. Pathao Driver Routing

   • Idea Used: Dimensionality reduction (t-SNE).
   • How: Visualizes driver locations in 2D to identify hotspots (e.g., dense clusters near Thamel or Lakshmi Path). Helps dispatchers allocate drivers efficiently.
   • Example: At 8 PM, t-SNE reveals a cluster of idle drivers near the airport—Pathao sends them to Lakshmi Path.

5. NEPSE Stock Market Analysis

   • Idea Used: PCA.
   • How: Reduces 50+ stock indicators (e.g., P/E ratio, volume) to 3 principal components to spot trends. Investors use this to avoid overfitting to noisy data.
   • Example: PC1 might represent "growth stocks," PC2 "dividend stocks"—helping diversify portfolios.

---

7. Exam Tip: How to Score Full Marks

1. For K-means:

   • Always show the distance calculation (Euclidean formula).
   • Draw a small diagram of clusters after each iteration.
   • Mention convergence criteria (e.g., centroids move < ε).

2. For Hierarchical Clustering:

   • Sketch a dendrogram (even a rough one).
   • Explain linkage criteria (single/complete/average).
   • Compare with K-means in a table (speed vs. interpretability).

3. For PCA:

   • Write the covariance matrix and eigenvalue steps.
   • Show a before/after projection (e.g., 2D → 1D).
   • Relate to variance preservation (e.g., "PC1 captures 70% variance").

4. Common Pitfalls:

   • Forget to standardize data before PCA (critical for features on different scales).
   • Assume K-means works for any k—mention the "elbow method" for choosing k.
   • Ignore the real-world tie-in: Always link your answer to a Nepalese example (e.g., "Like NTC optimizing towers...").

5. Past Exam Patterns:

   • Short notes: Define clustering, compare K-means vs. hierarchical.
   • Numerical: Perform 1–2 iterations of K-means (as in the 2022 PU exam).
   • Theory: Explain why PCA is useful (dimensionality curse, speedup).

---