Unsupervised learning is a type of machine learning where models are trained on unlabeled data. The system tries to learn the inherent patterns, structures, and relationships from the data without any explicit guidance or correct answers.

The primary goal of unsupervised learning is to explore the data and find meaningful representations. This is often used for:

• Data Exploration: Gaining insights into the structure of a dataset.
• Preprocessing: As a feature engineering step for subsequent supervised learning tasks.

Unsupervised learning tasks can be broadly grouped into several categories:

• Clustering: Grouping similar data points together.
• Dimensionality Reduction: Reducing the number of variables while preserving important information.
• Association Rule Learning: Discovering relationships between variables in large datasets.

Covered Techniques

This document covers the following key unsupervised learning techniques:

• Clustering
  • k-Means Clustering
  • Hierarchical Clustering
  • DBSCAN
  • Gaussian Mixture Models (GMM)
• Dimensionality Reduction
  • Principal Component Analysis (PCA)
  • t-Distributed Stochastic Neighbor Embedding (t-SNE)
• Association Rule Learning
  • Apriori
  • FP-Growth

Clustering

Clustering is the task of partitioning a set of objects into groups (called clusters) such that objects in the same cluster are more similar to each other than to those in other clusters.

k-Means Clustering

k-Means is one of the most fundamental and widely-used unsupervised algorithms. It is a centroid-based clustering algorithm that aims to partition n observations into k clusters, where each observation belongs to the cluster with the nearest mean (cluster centroid).

Mathematical Framework

The objective of k-Means is to minimize the within-cluster sum of squares (WCSS), also known as inertia: J = Σ(from j=1 to k) Σ(for x in Cⱼ) ||x - μⱼ||²

• k: The number of clusters.
• Cⱼ: The set of points in cluster j.
• μⱼ: The centroid (mean) of cluster j.

This is an NP-hard problem, so k-Means uses an iterative heuristic called Lloyd's algorithm to find a local minimum.

Algorithm Steps

1. Initialization: Choose k initial centroids. A smart initialization like k-means++ is often used to improve convergence and results.
2. Assignment Step: Assign each data point to the cluster of its nearest centroid.
3. Update Step: Recalculate the centroid for each cluster as the mean of all data points assigned to it.
4. Convergence: Repeat the assignment and update steps until the centroids no longer move or the assignments no longer change.

Determining the Optimal k

Since k must be specified beforehand, several methods are used to find an optimal value:

• Elbow Method: Plot the WCSS for a range of k values. The "elbow" point, where the rate of decrease sharply slows, is a good estimate for k.
• Silhouette Analysis: Measures how well-separated the resulting clusters are. A higher average silhouette score indicates a better clustering.

Advantages

• Simplicity and Speed: It is easy to implement and computationally efficient, scaling well to large datasets.
• Interpretability: The resulting clusters are easy to understand.

Limitations

• Requires k to be specified: The number of clusters must be chosen beforehand.
• Spherical Cluster Assumption: Assumes that clusters are convex and isotropic (spherical), which is not always true.
• Sensitivity to Initialization: The final clustering can depend on the initial choice of centroids.
• Sensitive to Outliers: The mean-based calculation makes it susceptible to outliers.

Hierarchical Clustering

Hierarchical clustering builds a tree-like hierarchy of clusters called a dendrogram. This method does not require the number of clusters to be specified in advance and allows for the exploration of data structure at multiple levels of granularity.

There are two main approaches:

1. Agglomerative (Bottom-Up): Starts with each data point as its own cluster and iteratively merges the closest pair of clusters until only one cluster remains.
2. Divisive (Top-Down): Starts with all data points in a single cluster and recursively splits them until each data point is its own cluster. Agglomerative is more common.

Mathematical Framework (Agglomerative)

The key component is the linkage criterion, which defines the distance between two clusters.

• Single Linkage: The distance between the closest pair of points in the two clusters. Tends to produce long, "chained" clusters.
• Complete Linkage: The distance between the farthest pair of points. Produces more compact, spherical clusters.
• Average Linkage: The average distance between all pairs of points. A balance between single and complete linkage.
• Ward's Linkage: Merges the pair of clusters that results in the minimum increase in the total within-cluster variance. This is often a good default choice.

The Dendrogram

The output is a dendrogram, which visualizes the merging process. The height of the merge in the dendrogram represents the distance at which the clusters were combined. By cutting the dendrogram at a certain height, a specific number of clusters can be obtained.

Advantages

• No need to specify k: The number of clusters can be chosen after the fact by examining the dendrogram.
• Provides a data hierarchy: The dendrogram reveals the nested structure of the data.
• Intuitive Visualization: The dendrogram is easy to interpret.

Limitations

• Computational Complexity: The naive implementation is O(n³), making it very slow for large datasets.
• Irreversible: Once a merge or split is made, it cannot be undone.
• Sensitive to Noise: Can struggle with noisy data and outliers.

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

DBSCAN is a density-based clustering algorithm that groups together points that are closely packed together, marking as outliers points that lie alone in low-density regions. It is particularly effective at discovering clusters of arbitrary shapes and handling noise.

Mathematical Framework

DBSCAN is defined by two key parameters:

• ε (epsilon): The radius of the neighborhood around a data point.
• MinPts: The minimum number of data points required to form a dense region.

Based on these parameters, points are classified into three types:

1. Core Point: A point that has at least MinPts neighbors (including itself) within its ε-neighborhood.
2. Border Point: A point that is not a core point but is in the ε-neighborhood of a core point.
3. Noise Point (Outlier): A point that is neither a core nor a border point.

Cluster Definition

A cluster is formed by a set of density-connected points. Two points are density-connected if they are linked by a path of core points, where each step in the path is within an ε-distance. A cluster consists of all core points and all border points that are reachable from them.

Advantages

• Finds Arbitrary Shapes: Does not assume clusters are spherical.
• Handles Noise: Has a built-in mechanism for identifying outliers.
• No need to specify k: The number of clusters is determined automatically.

Limitations

• Parameter Sensitivity: Performance is sensitive to the choice of ε and MinPts.
• Varying Densities: Struggles with datasets that have clusters of significantly different densities.
• Curse of Dimensionality: The concept of density becomes less meaningful in high-dimensional spaces.

Gaussian Mixture Models (GMM)

Gaussian Mixture Models are a probabilistic, model-based clustering algorithm. GMM assumes that the data points are generated from a mixture of a finite number of Gaussian distributions with unknown parameters. This allows for soft clustering, where each data point has a probability of belonging to each cluster.

Mathematical Framework

The model represents the probability distribution of the data as a weighted sum of K Gaussian components: p(x) = Σ(from k=1 to K) πₖ * N(x | μₖ, Σₖ)

• K: The number of Gaussian components (clusters).
• πₖ: The mixing coefficient (weight) for component k.
• N(x | μₖ, Σₖ): The multivariate Gaussian distribution for component k, defined by its mean μₖ and covariance Σₖ.

Expectation-Maximization (EM) Algorithm

The parameters (πₖ, μₖ, Σₖ) are learned using the Expectation-Maximization (EM) algorithm, an iterative process for finding maximum likelihood estimates in models with latent variables.

1. Initialization: Initialize the parameters, often using the results of k-Means.
2. E-Step (Expectation): For each data point, calculate the posterior probability (responsibility) that it belongs to each component k. This is the "soft" assignment.
3. M-Step (Maximization): Update the model parameters (πₖ, μₖ, Σₖ) using the responsibilities calculated in the E-step.
4. Convergence: Repeat the E and M steps until the log-likelihood of the data converges.

Advantages

• Soft Clustering: Provides probabilistic assignments, which can be more informative.
• Cluster Shape Flexibility: The use of covariance matrices allows GMMs to model elliptical clusters of different shapes and orientations.
• Probabilistic Foundation: It is a generative model, meaning it can be used to generate new data points that resemble the original data.

Limitations

• Complex: More complex and computationally expensive than k-Means.
• Convergence Issues: The EM algorithm can get stuck in local optima.
• Singularities: Can have issues with singular covariance matrices if a component has too few points.

Dimensionality Reduction

Dimensionality reduction is the process of reducing the number of input variables in a dataset. This is important for visualizing high-dimensional data, reducing computational cost, and mitigating the "curse of dimensionality."

Principal Component Analysis (PCA)

PCA is a linear dimensionality reduction technique that transforms the data into a new coordinate system. The new axes (principal components) are orthogonal and are ordered by the amount of variance they explain in the data. The first principal component captures the most variance, the second captures the second most, and so on.

Mathematical Framework

PCA finds the principal components by performing an eigenvalue decomposition on the covariance matrix of the data. The eigenvectors of the covariance matrix are the principal components, and the corresponding eigenvalues represent the amount of variance captured by each component.

Alternatively, PCA can be computed using Singular Value Decomposition (SVD) of the centered data matrix, which is often more numerically stable.

Key Steps

1. Standardize the data: It is crucial to scale the features to a common range.
2. Compute the covariance matrix: Calculate the covariance between all pairs of features.
3. Compute eigenvectors and eigenvalues: Find the principal components and their corresponding variance.
4. Select principal components: Choose the top k eigenvectors that capture a desired amount of variance (e.g., 95%).
5. Project the data: Transform the original data onto the new, lower-dimensional subspace defined by the selected components.

Advantages

• Reduces Overfitting: By removing noise and redundant features.
• Removes Multicollinearity: The resulting principal components are orthogonal (uncorrelated).
• Improves Performance: Speeds up training of machine learning algorithms.

Limitations

• Linearity Assumption: Assumes the principal components are a linear combination of the original features.
• Interpretability: The new features (principal components) are combinations of the original features and can be difficult to interpret.
• Information Loss: It is a lossy compression method; some information is lost.

t-Distributed Stochastic Neighbor Embedding (t-SNE)

t-SNE is a non-linear dimensionality reduction technique that is particularly well-suited for visualizing high-dimensional datasets in 2D or 3D. It models the similarity between high-dimensional data points as a probability distribution and then optimizes a similar distribution in the low-dimensional space.

Mathematical Framework

1. High-Dimensional Similarities: t-SNE converts the high-dimensional Euclidean distances between data points into conditional probabilities that represent similarities. It uses a Gaussian distribution centered on each point to model these probabilities.
2. Low-Dimensional Similarities: It models the similarities between the corresponding low-dimensional points using a Student's t-distribution with one degree of freedom. The heavy tails of the t-distribution allow dissimilar points to be modeled far apart in the low-dimensional map, helping to alleviate the "crowding problem."
3. Optimization: The algorithm minimizes the Kullback-Leibler (KL) divergence between the two distributions of pairwise similarities using gradient descent, effectively arranging the points in the low-dimensional space to best represent the high-dimensional structure.

Key Hyperparameter: Perplexity

Perplexity is related to the number of nearest neighbors that are considered for each point. Typical values are between 5 and 50. It influences the balance between preserving local and global structure.

Advantages

• Reveals Local Structure: Excellent at visualizing the underlying structure of data, such as clusters.
• Handles Non-linear Structures: Can find complex manifolds in the data.

Limitations

• Computational Cost: The standard algorithm is computationally intensive (O(n²)). Approximations like Barnes-Hut t-SNE can speed it up to O(n log n).
• Not a Clustering Algorithm: While it reveals clusters, it is not a clustering algorithm itself and can sometimes create the illusion of clusters where none exist.
• Global Structure is not preserved: The distances and relative sizes of clusters in a t-SNE plot are not directly interpretable. It is a visualization technique, not an analysis tool.

Association Rule Learning

Association rule learning is a rule-based machine learning method for discovering interesting relationships between variables in large datasets. The most common application is Market Basket Analysis, which aims to find associations between products frequently purchased together.

Key Metrics

• Support: Measures how frequently an itemset appears in the dataset. Support(X) = (Transactions containing X) / (Total transactions)
• Confidence: Measures how often a rule has been found to be true. It's the conditional probability of Y given X. Confidence(X → Y) = Support(X ∪ Y) / Support(X)
• Lift: Measures how much more often X and Y occur together than if they were statistically independent. Lift(X → Y) = Support(X ∪ Y) / (Support(X) * Support(Y))
  • Lift > 1: Indicates a positive correlation.
  • Lift < 1: Indicates a negative correlation.
  • Lift = 1: Indicates no correlation.

Apriori Algorithm

Apriori is a classic algorithm for mining frequent itemsets and learning association rules. It is based on the Apriori property: "All non-empty subsets of a frequent itemset must also be frequent."

How it works

1. Set a minimum support threshold.
2. Find all itemsets with one item that meet the threshold (frequent 1-itemsets).
3. Iteratively generate candidate k-itemsets from frequent (k-1)-itemsets.
4. Prune the candidates by checking if all their subsets are frequent (the Apriori property).
5. Repeat until no more frequent itemsets are found.
6. Generate rules from the final frequent itemsets that meet a minimum confidence threshold.

FP-Growth Algorithm

The FP-Growth (Frequent Pattern Growth) algorithm is an efficient alternative to Apriori. It avoids the costly candidate generation step by constructing a compact, tree-based data structure called an FP-tree.

How it works

1. It scans the database once to find the frequent 1-itemsets and orders them.
2. It scans the database a second time to construct the FP-tree, which stores the transaction data in a compressed form.
3. It extracts frequent itemsets directly from the FP-tree by recursively mining it.

FP-Growth is significantly faster than Apriori, especially for large datasets.