Self-Organizing Maps: Clustering, Topology, and Applications

TAKEAWAYS:

• Self-Organizing Maps (SOMs) are unsupervised neural networks that map high-dimensional input data onto a lower-dimensional grid while preserving topological relationships.
• SOMs use competitive learning and lateral interactions to organize data into clusters, making them useful for visualization and exploratory data analysis.
• The training process involves adjusting weights of neighboring neurons based on the winner-takes-all rule and a neighborhood function (e.g., Gaussian).
• SOMs are widely used in customer segmentation, image compression, and anomaly detection due to their ability to reveal hidden patterns in data.
• Unlike k-means, SOMs preserve the spatial structure of data, making them superior for tasks requiring topological mapping.
• Real-world applications include fraud detection in banks (e.g., Nabil Bank), route optimization in Pathao, and sentiment analysis in social media.

What is a Self-Organizing Map (SOM)?

A Self-Organizing Map (SOM) is an unsupervised neural network that transforms high-dimensional input data into a two-dimensional discrete grid while preserving the topological relationships between data points. Unlike supervised learning, SOMs do not require labeled data, making them ideal for exploratory data analysis and pattern recognition.

Key Components of a SOM:

1. Input Layer: Receives high-dimensional data (e.g., features from a dataset).
2. Output Layer (Map Grid): A 2D grid of neurons (e.g., 10×10) where each neuron represents a cluster or a region in the input space.
3. Weights: Each neuron has a weight vector of the same dimension as the input data.
4. Neighborhood Function: Defines how much influence a winning neuron has on its neighbors during training (e.g., Gaussian or bubble function).

How SOMs Work:

SOMs use competitive learning and lateral interactions to organize data. The training process involves:

1. Initialization: Randomly initialize weights for all neurons.
2. Input Presentation: Present an input vector from the dataset.
3. Winner Selection: Find the Best Matching Unit (BMU), the neuron whose weight vector is closest to the input (using Euclidean distance).
4. Weight Update: Adjust the weights of the BMU and its neighbors to move closer to the input vector. The update magnitude decreases with distance from the BMU.
5. Repeat: Iterate for all input vectors until convergence (weights stabilize).

Visualizing the SOM Training Process

graph LR
    A["Input Data (High-Dim)"] --> B["SOM Grid (2D)"]
    B --> C["Neurons with Weights"]
    C --> D["Winner Neuron (BMU)"]
    D --> E["Update BMU & Neighbors"]
    E --> F["Repeat for All Data"]
    F --> G["Converged SOM"]

Worked Example: SOM for Customer Segmentation

Suppose a bank (e.g., Nabil Bank) wants to segment customers based on their transaction history. The dataset has 3 features:

• Age (normalized to [0,1])
• Monthly Income (normalized to [0,1])
• Credit Score (normalized to [0,1])

Step 1: Initialize a 5×5 SOM grid with random weights. Step 2: Train the SOM using 100 customer records.

Step 3: After training, the SOM grid reveals clusters:

• Top-left: High-income, high-credit-score customers.
• Bottom-right: Low-income, low-credit-score customers.

Visualization of the SOM Grid After Training:

Caption: SOM grid showing customer segments after training. The BMU (Best Matching Unit) is highlighted in blue.

Training Algorithm: The Kohonen Learning Rule

The SOM training algorithm is based on the Kohonen learning rule, which involves:

1. Winner-Takes-All (WTA): Only the BMU and its neighbors are updated.

2. Neighborhood Function: Defines the influence of the BMU on neighbors. Common functions:

   • Gaussian: $h_{c,i}(t)=\exp \left(-\frac{\Vert r_c-r_i{\Vert }^2}{2\sigma (t{)}^2}\right)$
     • $r_c$: Position of the BMU.
     • $r_i$: Position of neighbor $i$.
     • $\sigma (t)$: Neighborhood radius (decreases over time).
   • Bubble: $h_{c,i}(t)=1$ if $\Vert r_c-r_i\Vert \le \sigma (t)$, else 0.

3. Weight Update Rule: $$w_i(t+1)=w_i(t)+\eta (t)\cdot h_{c,i}(t)\cdot (x(t)-w_i(t))$$

   • $\eta (t)$: Learning rate (decreases over time).
   • $x(t)$: Input vector at time $t$.

Worked Example: Updating Weights in a SOM

Assume:

• Input vector $x=[0.5,0.8,0.3]$.
• BMU at position $(2,2)$ with weight $w_{2,2}=[0.4,0.7,0.2]$.
• Neighborhood function: Gaussian with $\sigma (t)=1.0$.
• Learning rate $\eta (t)=0.1$.

Step 1: Calculate the neighborhood influence for neuron at $(1,2)$: $$h_{2,2;1,2}(t)=\exp \left(-\frac{\Vert (2,2)-(1,2){\Vert }^2}{2\cdot 1.0^2}\right)=\exp (-0.5)\approx 0.6065$$

Step 2: Update weights for neuron $(1,2)$: $$w_{1,2}(t+1)=w_{1,2}(t)+0.1\cdot 0.6065\cdot ([0.5,0.8,0.3]-w_{1,2}(t))$$ (Assume $w_{1,2}(t)=[0.3,0.6,0.1]$) $$w_{1,2}(t+1)=[0.3,0.6,0.1]+0.06065\cdot [0.2,0.2,0.2]=[0.312,0.612,0.112]$$

Advantages and Disadvantages of SOMs

Applications of SOMs in the Real World

1. Fraud Detection in Banks (e.g., Nabil Bank, Global IME)

• How it works: SOMs are trained on normal transaction patterns. Transactions that map far from any cluster are flagged as anomalies.
• Example: A sudden large withdrawal by a customer with a low credit score would appear in a sparse region of the SOM grid, triggering an alert.

2. Route Optimization in Ride-Sharing Apps (e.g., Pathao)

• How it works: SOMs cluster pickup/dropoff locations to identify high-demand zones. This helps optimize driver dispatching.
• Example: A 10×10 SOM grid of Kathmandu’s traffic zones reveals that areas near Thapathali and Kalanki have the highest demand during rush hours.

3. Image Compression (e.g., Used in Daraz Product Images)

• How it works: SOMs reduce the dimensionality of image pixels, preserving essential features while compressing data.
• Example: A 256×256 RGB image (786,432 dimensions) can be mapped to a 16×16 SOM grid, reducing storage without losing critical visual details.

4. Sentiment Analysis in Social Media

• How it works: SOMs cluster tweets or reviews based on word embeddings (e.g., TF-IDF or word2vec), grouping positive, negative, and neutral sentiments.
• Example: A SOM trained on Nepali Twitter data might show a cluster of tweets about "load shedding" in red (negative sentiment) and another about "new smartphone launches" in green (positive sentiment).

5. Traffic Pattern Analysis (e.g., NTC, Kathmandu Traffic Management)

• How it works: SOMs analyze GPS data from vehicles to identify congestion hotspots and optimize traffic signal timings.
• Example: A SOM of GPS coordinates from buses in Ring Road reveals that the stretch between Bhotahity and Putalisadak is always congested during 8–10 AM.

SOM vs. Other Clustering Methods

Step-by-Step: Implementing a SOM in Python (Conceptual)

While full code is beyond this note, here’s how you’d structure a SOM implementation using libraries like MiniSom:

from minisom import MiniSom
import numpy as np

# Step 1: Load and normalize data (e.g., customer data)
data = np.loadtxt("customers.csv", delimiter=",")
data_normalized = (data - np.min(data, axis=0)) / (np.max(data, axis=0) - np.min(data, axis=0))

# Step 2: Initialize SOM (e.g., 10x10 grid, 3 input dimensions)
som = MiniSom(x=10, y=10, input_len=3, sigma=0.5, learning_rate=0.5)
som.random_weights_init(data_normalized)
som.train_random(data_normalized, 100)  # Train for 100 epochs

# Step 3: Visualize the SOM
from pylab import bone, pcolor, colorbar, plot, show
bone()
pcolor(som.distance_map().T)
colorbar()
markers = ['o', 's', '^']
colors = ['r', 'g', 'b']
for i, x in enumerate(data_normalized):
    w = som.winner(x)
    plot(w[0]+0.5, w[1]+0.5, markers[i%3]+' '+colors[i%3])
show()

Output Visualization:

Common Pitfalls and How to Avoid Them

1. Poor Initialization:

   • Problem: Random initialization can lead to poor convergence.
   • Solution: Use PCA to initialize weights linearly or use som.random_weights_init(data).

2. Incorrect Grid Size:

   • Problem: Too small → underfitting; too large → overfitting.
   • Solution: Start with a small grid (e.g., 5×5) and increase if clusters are too coarse.

3. Improper Learning Rate and Neighborhood Radius:

   • Problem: Too high → chaotic updates; too low → slow learning.
   • Solution: Use a decreasing schedule (e.g., $\eta (t)=0.5\cdot (1-t/T)$, where $T$ is max epochs).

4. Ignoring Data Normalization:

   • Problem: Features on different scales bias the distance metric.
   • Solution: Normalize data to [0,1] or use standardization (z-score).

Exam Tip

For the TU/NEB exam, expect questions on:

1. Definitions:

   • Explain what a SOM is and its key components (input layer, map grid, weights).
   • Define Best Matching Unit (BMU) and neighborhood function.

2. Training Process:

   • Describe the Kohonen learning rule step-by-step.
   • Sketch a SOM grid and mark the BMU and its neighbors during an update.

3. Applications:

   • Give two real-world examples (e.g., fraud detection in banks, route optimization in Pathao) and explain how SOMs are used.
   • Compare SOMs with k-means or hierarchical clustering in a table.

4. Worked Examples:

   • Be ready to calculate weight updates for a given input and BMU.
   • Interpret a SOM grid visualization (e.g., identify clusters or anomalies).

5. Practical Implementation:

   • Know the steps to train a SOM in Python (even if you don’t code, explain the libraries like MiniSom).
   • Discuss hyperparameters (grid size, learning rate, neighborhood radius) and their impact.

Common Exam Questions:

• "How does a SOM preserve topological relationships?"
• "Why is SOM better than k-means for visualizing high-dimensional data?"
• "Explain the role of the neighborhood function in SOM training."
• "Give an example of how SOMs can be used in Nepali businesses (e.g., NTC, Daraz)."

Pro Tip: Draw a SOM grid on paper during the exam to explain concepts visually. For numerical questions, always show step-by-step calculations (e.g., weight updates).