Unsupervised Learning: Clustering and Autoencoders

Unsupervised Learning

Unsupervised learning techniques like clustering and autoencoders are used to find patterns in data without labeled outputs.

Clustering

Clustering aims to group similar objects together while ensuring that they are dissimilar to objects in other groups. The goal is to minimize intra-cluster distances and maximize inter-cluster distances.

Applications of Cluster Analysis

• Understanding: Clustering can help in grouping related documents for browsing, genes and proteins with similar functionality, and stocks with similar price fluctuations.
• Summarization: It reduces the size of large datasets by grouping similar data points.

Clustering Techniques

Various clustering techniques include:

• Partitioning Methods: k-Means, k-Medoids, k-Modes, Fuzzy c-means.
• Hierarchical Methods: Agglomerative and Divisive methods like AGNES, BIRCH, CURE, ROCK, Chamelon, DIANA, PAM, CLARA, CLARANS.
• Density-Based Methods: STING, DBSCAN, CLIQUE, DENCLUE, OPTICS, Wave Cluster.
• Graph-Based Methods: MST Clustering, OPOSSUM, SNN Similarity Clustering.
• Model-Based Clustering: EM Algorithm, Auto class, COBWEB, ANN Clustering.

Types of Clusterings

• Partitional Clustering: Divides data objects into non-overlapping subsets, where each object belongs to exactly one subset.
• Hierarchical Clustering: Organizes clusters as a hierarchical tree.

K-Means Clustering

K-means is a partitional clustering approach where the number of clusters, $K$, must be specified. Each cluster is associated with a centroid, and each point is assigned to the cluster with the closest centroid.

K-Means Algorithm Details

The algorithm iteratively assigns each point to the nearest centroid and re-computes the cluster centroids until the centroids stop changing.

• Initial centroids are often chosen randomly, leading to varying cluster results.
• The centroid is typically the mean of the points in the cluster.
• K-means converges for common proximity measures.
• Complexity: $O(n * K * I * d)$, where $n$ is the number of points, $K$ is the number of clusters, $I$ is the number of iterations, and $d$ is the number of attributes.

K-Means Objective Function

The Sum of Squared Error (SSE) is a common objective function used with the Euclidean distance measure.

SSE =
\sum{i=1}^{K} \sum{x \in Ci} dist^2(mi, x)

Where $x$ is a data point in cluster $C<em>i$ and $m</em>i$ is the centroid for cluster $C_i$. SSE improves in each iteration until it reaches a local or global minimum.

Importance of Choosing Initial Centroids

The choice of initial centroids significantly impacts the resulting clusters. Poor initial centroids can lead to suboptimal clusterings.

Solutions to Initial Centroids Problem

• Multiple Runs: Running the algorithm multiple times with different initial centroids.
• Strategic Selection: Selecting initial centroids that are widely separated (K-means++).
• Hierarchical Clustering: Using hierarchical clustering to determine initial centroids.

K-Means++

1. Select an initial point at random to be the first centroid.
2. For $k – 1$ steps:
3. For each of the $N$ points, $x<em>i$, $1 ≤ i ≤ N$, find the minimum squared distance to the currently selected centroids, $C</em>1, …, C<em>j$, $1 ≤ j < k$, i.e., $min</em>j d^2(C<em>j, x</em>i)$
4. Randomly select a new centroid by choosing a point with probability proportional to $min<em>j d^2(C</em>j, x_i)$

Pre-processing and Post-processing

• Pre-processing: Normalize the data and eliminate outliers before clustering.
• Post-processing: Eliminate empty clusters, split loose clusters, and merge close clusters.

Handling Empty Clusters

Strategies for handling empty clusters include:

• Choosing the point that contributes most to SSE and making it a new centroid.
• Choosing a point from the cluster with the highest SSE and making it a new centroid.

Limitations of K-Means

• Problems when clusters have differing sizes, densities, or non-globular shapes.
• Sensitivity to outliers.

Overcoming K-Means Limitations

Using many clusters to find parts of clusters and then putting them together.

Hierarchical Clustering

Hierarchical clustering produces a set of nested clusters organized as a hierarchical tree, visualized as a dendrogram.

Strengths of Hierarchical Clustering

• No need to assume a particular number of clusters; any desired number can be obtained by cutting the dendrogram at the proper level.
• Meaningful taxonomies can be derived.

Types of Hierarchical Clustering

• Agglomerative: Start with individual points as clusters and merge the closest pairs at each step until one or $k$ clusters are left.
• Divisive: Start with one all-inclusive cluster and split a cluster at each step until each cluster contains an individual point or there are $k$ clusters.

Traditional algorithms use a similarity or distance matrix to merge or split clusters.

Agglomerative Clustering Algorithm

1. Compute the proximity matrix.
2. Let each data point be a cluster.
3. Repeat:
4. Merge the two closest clusters.
5. Update the proximity matrix.
6. Until only a single cluster remains.

Defining Inter-Cluster Distance

Methods include:

• MIN (Single Linkage)
• MAX (Complete Linkage)
• Group Average
• Distance Between Centroids
• Ward’s Method (uses squared error)

MIN or Single Link

Proximity between two clusters is based on the two closest points in the different clusters.

MAX or Complete Linkage

Proximity between two clusters is based on the two most distant points in the different clusters.

Group Average

Proximity between two clusters is the average of pairwise proximity between points in the two clusters.

proximity(Clusteri, Clusterj) =
\frac{\sum{p \in Clusteri}
\sum{p' \in Clusterj} proximity(p, p')}{|Clusteri| * |Clusterj|}

Cluster Similarity: Ward’s Method

Similarity of two clusters is based on the increase in squared error when two clusters are merged.

Hierarchical Clustering: Time and Space Requirements

• Space: $O(N^2)$
• Time: $O(N^3)$, which can be reduced to $O(N^2 log(N))$ with cleverness.

Hierarchical Clustering: Problems and Limitations

• Once a decision is made to combine two clusters, it cannot be undone.
• No global objective function is directly minimized.
• Sensitivity to noise and outliers.
• Difficulty handling clusters of different sizes and non-globular shapes.
• Breaking large clusters.

Density-Based Clustering

Clusters are regions of high density separated by regions of low density.

DBSCAN

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) is a density-based algorithm.

• Density: Number of points within a specified radius (Eps).
• Core Point: A point with at least a specified number of points (MinPts) within Eps.
• Border Point: Not a core point but within the neighborhood of a core point.
• Noise Point: Any point that is not a core point or a border point.

DBSCAN Algorithm

1. Label all points as core, border, or noise points.
2. Eliminate noise points.
3. Put an edge between all core points within a distance Eps of each other.
4. Make each group of connected core points into a separate cluster.
5. Assign each border point to one of the clusters of its associated core points.

When DBSCAN Works Well

• Resistant to noise.
• Can handle clusters of different shapes and sizes.

When DBSCAN Does NOT Work Well

• Varying densities.
• High-dimensional data.

DBSCAN: Determining EPS and MinPts

Plot sorted distance of every point to its $k^{th}$ nearest neighbor to determine suitable values.

Cluster Validity

Evaluating the “goodness” of the resulting clusters is essential to avoid finding patterns in noise, compare clustering algorithms, and compare different sets of clusters.

Measuring Cluster Validity Via Correlation

Correlation of ideal similarity and proximity matrices for the K-means clusterings.

Internal Measures: SSE

SSE (Sum of Squared Error) measures the goodness of a clustering structure without respect to external information. It is useful for comparing two clusterings or clusters and estimating the number of clusters.

Autoencoders

Autoencoders are neural networks used for representational learning, aiming to learn a compressed, encoded representation of input data.

Neural Networks as Function Approximation

Given an input $x$ and output $y$, there exists a mapping from input space to output space as $x \rightarrow y$, where $y = f(x) + \epsilon$. The goal is to find an estimate of $f(x)$, denoted as $\hat{f}(x)$.

Representational Learning

Autoencoders learn the function $\hat{y} = x$, aiming to reconstruct the input.

Self-Supervised Learning

Train two networks to minimize the reconstruction loss function:

$\mathcal{L} = \sigma (x<em>i - \hat{x}</em>i)^2$

Simplest Autoencoder

Encode with a fully connected network (FCN).

Bottleneck

Autoencoders compress the input into a smaller representation (bottleneck) and then reconstruct it.

Latent Variables and Latent Layer

Autoencoders perform semi-supervised or self-supervised learning, using the input data as the target output.

Autoencoders in Action

Training with a variety of images is crucial for good generalization.

A Better Autoencoder

MNIST data can be used to train a simple autoencoder with a one-layer FCN encoder and decoder.

Exploring Autoencoders

Exploring the latent space helps understand the information it contains. If it does not contain any information, then changing the values randomly won’t change the output.

Applying to Novel Input

Check if the trained autoencoder works with new, unseen images.

Convolutional Autoencoders

Use convolutional layers for image data to improve performance.

Over-Complete Autoencoders

An over-complete autoencoder has latent space with greater dimension than the input. It helps balance sensitivity and insensitivity to the inputs, avoiding memorization or overfitting.

Variational Autoencoders (VAE)

Variational Autoencoders improve upon standard autoencoders by keeping track of means and standard deviations in the latent space, preserving details better.

A History of Generative AI Models

• 2014-2017: VAE and GAN era.
• 2018-2019: Transformer era.
• 2020-Now: The Big Model Era, including large language models and multimodal models.