Unit 4: Unsupervised Learning

I. Orientation

Unsupervised learning is a machine-learning paradigm in which an algorithm discovers structure in data without target labels. Given observations (X={x_1,x_2,\ldots,x_n}), the objective is to identify groups, lower-dimensional representations, or recurring relationships that describe the data. Unlike supervised learning, success is evaluated through structure, compactness, separation, reconstruction quality, or usefulness in a later task.

• No target variable: Training data contain input features but no known class or output label.
• Similarity-based structure: The result depends on how similarity or distance is defined, such as Euclidean distance or cosine similarity.
• Feature dependence: Different measurement scales can change results; standardization is often necessary.
• Exploratory purpose: Methods help reveal hidden groups, anomalies, correlations, and compact representations.
• Model assumptions: Every method imposes assumptions, such as spherical clusters in K-Means or dense regions in DBSCAN.
• Evaluation convention: Internal measures include silhouette score, within-cluster sum of squares, explained variance, and support-confidence-lift measures for rules.

II. Clustering — Grouping Similar Observations

Clustering partitions or organizes observations so that members of the same group are more similar to one another than to members of other groups. It is used in customer segmentation, document organization, image analysis, and robot environment interpretation.

A. Clustering

Clustering assigns data points to groups according to a chosen similarity measure rather than a pre-existing class label.

• Input: A dataset with (n) observations and (p) features, represented as an (n\times p) matrix.
• Within-cluster similarity: Points in one cluster should have small pairwise distances.
• Between-cluster separation: Different clusters should be relatively far apart.
• Distance choice: Euclidean distance is common for numeric data; Manhattan distance can be more robust to coordinate-wise differences.
• Hard versus soft assignment: Hard clustering gives each point one cluster, while soft clustering gives membership probabilities or degrees.
• Preprocessing: Standardizing temperature in degrees and distance in meters prevents the larger numerical scale from dominating distance calculations.

B. K-Means Clustering

K-Means Clustering divides data into a specified number (k) of clusters by repeatedly assigning points to the nearest centroid and updating the centroids.

• Objective: Minimize the within-cluster sum of squared errors (SSE).

SSE = sum over clusters j and points xi in Cj of ||xi - μj||²

Here, (C_j) is cluster (j), (x_i) is a data point, and (\mu_j) is the centroid of cluster (j).

• Algorithm steps:
  1. Choose (k) initial centroids.
  2. Assign each point to its nearest centroid.
  3. Recalculate each centroid as the mean of its assigned points.
  4. Repeat assignment and updating until assignments or centroids stabilize.
• Worked example: For one-dimensional values (2,3,10,11) with (k=2), initial centroids near (2) and (10) produce groups ({2,3}) and ({10,11}), with final centroids (2.5) and (10.5).
• Choosing (k): The elbow method plots SSE against (k) and looks for a point where additional clusters provide limited improvement; silhouette analysis also compares cohesion and separation.
• Limitations: K-Means requires (k) in advance, is sensitive to initialization and outliers, and works best with compact, similarly sized, approximately spherical clusters.

C. Hierarchical Clustering

Hierarchical Clustering builds a nested tree of clusters, called a dendrogram, so that groups can be examined at several levels of granularity.

• Agglomerative procedure: Start with every observation as a separate cluster, repeatedly merge the closest pair, and stop when one cluster remains or a selected level is reached.
• Divisive procedure: Start with all observations in one cluster and repeatedly split them into smaller groups.
• Linkage rule: The distance between clusters may be defined as:
  • Single linkage: Minimum distance between any two members; it can create chaining.
  • Complete linkage: Maximum member distance; it tends to form compact groups.
  • Average linkage: Mean pairwise distance between clusters.
  • Ward linkage: Merge that causes the smallest increase in within-cluster variance.
• Dendrogram interpretation: Cutting a tree at a selected height produces a chosen number of clusters; the vertical merge height represents dissimilarity.
• Strength: The method does not require selecting (k) before building the hierarchy and can reveal nested structure.
• Limitation: Naive implementations often require substantial time and memory for large datasets, and early merges cannot normally be undone.

D. Concept of DBSCAN

The Concept of DBSCAN is density-based clustering, in which dense regions become clusters and sparse regions separate them.

• Core parameters: (\varepsilon) is the neighborhood radius, and MinPts is the minimum number of points needed in that neighborhood.
• Core point: A point has at least MinPts observations, including itself, within distance (\varepsilon).
• Border point: It lies within a core point’s neighborhood but has too few neighbors to be core itself.
• Noise point: It is neither core nor density-reachable from a core point and is labelled an outlier.
• Process: Starting from a core point, DBSCAN expands through neighboring core points and includes reachable border points.
• Strength: It can find irregularly shaped clusters and does not require the number of clusters beforehand.
• Limitation: A single (\varepsilon) may not suit regions with different densities; results also depend strongly on the distance metric and parameter selection.

III. Dimensionality Reduction and Principal Component Analysis — Compact Representations

Dimensionality reduction transforms data with many features into fewer informative variables while attempting to preserve important structure. It supports visualization, faster computation, noise reduction, and mitigation of redundant features.

A. Dimensionality Reduction

Dimensionality Reduction replaces a (p)-dimensional representation with one containing (q) dimensions, where (q<p), while preserving selected information.

• Feature selection: Retain original variables, such as choosing three useful sensor channels from twenty.
• Feature extraction: Construct new variables from combinations of the originals; PCA is a principal example.
• Benefits: Fewer dimensions reduce storage and computation, and a two- or three-dimensional representation can make clusters visually inspectable.
• Curse of dimensionality: As (p) grows, data become sparse and distances become less discriminative, reducing clustering reliability.
• Trade-off: Removing dimensions may discard rare but meaningful signals, so the reduced representation must be validated against the intended task.
• Data preparation: Centering and often scaling are important because a feature measured in large units can otherwise dominate the transformation.

B. Principal Component Analysis

Principal Component Analysis (PCA) creates orthogonal directions, called principal components, ordered by the amount of variance they explain.

• First component: Find a unit vector (w_1) maximizing the variance of projected observations (Xw_1).
• Later components: Each new component is orthogonal to earlier components and captures the greatest remaining variance.
• Covariance basis: For centered data matrix (X), compute the covariance matrix:

Σ = (1 / (n - 1)) XᵀX

Here, (n) is the number of observations, (X) is centered, and (\Sigma) is the feature covariance matrix.

• Eigenvectors and eigenvalues: Eigenvectors of (\Sigma) give component directions; corresponding eigenvalues give their variances.
• Projection: If (W_q) contains the first (q) component vectors, reduced coordinates are:

Z = XWq

Here, (Z) is the reduced dataset and (q) is the retained dimension.

• Explained variance ratio: If retained eigenvalues are (\lambda_1,\ldots,\lambda_q), their information proportion is:

EVR = (λ1 + λ2 + ... + λq) / (λ1 + ... + λp)

• Interpretation: A component is a weighted combination of original features; a large loading indicates strong contribution, but it does not automatically represent a causal factor.
• Limitations: PCA is linear, sensitive to scaling and outliers, and preserves variance rather than necessarily preserving class separation or nonlinear geometry.

IV. Pattern Discovery — Finding Co-occurring Events

Pattern Discovery identifies regularities in collections of events or features. In transactional data, the central output is an association rule such as (A\Rightarrow B), meaning that transactions containing itemset (A) frequently also contain itemset (B).

A. Pattern Discovery

Pattern Discovery converts repeated co-occurrence into interpretable descriptions that can support recommendations, diagnosis, or monitoring.

• Itemset: A set of items, such as ({\text{bread},\text{milk}}), occurring together in a transaction.
• Frequency: A pattern is useful only if it occurs often enough or has meaningful predictive association.
• Interpretation: A discovered relationship is correlational; the rule (A\Rightarrow B) does not prove that (A) causes (B).
• Applications: Market-basket analysis, web-click sequences, equipment-event monitoring, and symptom co-occurrence all treat observations as collections of events.

B. Association Rule Mining

Association Rule Mining evaluates implications between itemsets using support, confidence, and lift.

• Support: The fraction of transactions containing (A\cup B).

support(A → B) = count(A ∪ B) / N

Here, (N) is the total number of transactions.

• Confidence: The conditional probability that (B) occurs when (A) occurs.

confidence(A → B) = support(A ∪ B) / support(A)

• Lift: The strength of association compared with independent occurrence.

lift(A → B) = confidence(A → B) / support(B)

• Meaning of lift: Lift greater than (1) indicates positive association, lift near (1) suggests approximate independence, and lift below (1) indicates negative association.
• Worked example: If 40 of 100 transactions contain bread, 30 contain milk, and 20 contain both, then support is (0.20), confidence for bread (\Rightarrow) milk is (20/40=0.50), and lift is (0.50/0.30\approx1.67).
• Limitations: Very common items can produce high confidence without strong usefulness; multiple testing can generate accidental patterns, so thresholds and domain validation matter.

C. Apriori Algorithm

The Apriori Algorithm efficiently searches for frequent itemsets by using the principle that every subset of a frequent itemset must also be frequent.

• Apriori property: If ({A,B}) fails the minimum-support threshold, every larger set containing ({A,B}) can be pruned.
• Candidate generation: Create candidate (k)-itemsets by joining frequent ((k-1))-itemsets.
• Candidate pruning: Remove a candidate if any of its ((k-1))-subsets is not frequent.
• Pseudocode:

L1 = frequent 1-itemsets
for k = 2 while L(k-1) is not empty:
    Ck = candidates generated from L(k-1)
    count support of candidates in each transaction
    Lk = candidates meeting minimum support
return all Lk

Here, (L_k) is the set of frequent (k)-itemsets and (C_k) is the candidate set.

• Rule generation: For a frequent set (F), test rules (A\Rightarrow F-A) against minimum confidence and possibly minimum lift.
• Limitation: Repeated database scans and candidate explosion make Apriori expensive when there are many items or low support thresholds; FP-Growth can reduce candidate generation.

V. Unsupervised Learning Application in Robotics and Sensor data — Discovering Environment and System State

Unsupervised methods help robots interpret streams of unlabeled measurements, identify operating modes, compress sensor signals, and detect unusual conditions when manually labelled data are scarce.

A. Unsupervised Learning application in Robotics and Sensor data

The application combines clustering, PCA, and pattern discovery with preprocessing designed for noisy, time-dependent sensor measurements.

• Sensor-state clustering: K-Means can group robot states using features such as wheel speed, motor current, battery voltage, and vibration; clusters may correspond to idle, cruising, turning, or load-bearing operation.
• Spatial interpretation: Range or lidar measurements can be clustered to separate nearby obstacle points from open-space readings, although geometric methods may be preferable when coordinates are central.
• Dimensionality reduction: PCA can compress correlated accelerometer channels before clustering, reducing a high-frequency signal to a few dominant vibration components.
• Anomaly detection: DBSCAN can label isolated readings as noise, useful for detecting a faulty range sensor or an unexpected collision signature.
• Temporal pattern discovery: Association rules can relate events such as high motor current, increased temperature, and wheel slip, revealing recurring combinations in robot logs.
• Preprocessing requirements: Synchronize timestamps, remove impossible values, normalize units, and use time-window features such as mean acceleration over a (1)-second interval.
• Operational limitations: Sensor drift, changing environments, uneven sampling, and different operating conditions can make a previously learned cluster invalid; human or safety-system verification is required before autonomous action.
• Evaluation: Compare clusters with physical operating modes, inspect false alarms, measure reconstruction error after PCA, and test whether discovered patterns improve navigation or maintenance decisions.