Part17: Unsupervised Machine Learning: Kernel Principal Component Analysis and Multidimensional Scaling

Kernel PCA: An In-Depth Explanation

Kernel Principal Component Analysis (Kernel PCA) is an extension of Principal Component Analysis (PCA) that allows for the analysis of data that is not linearly separable. By using a kernel function to map data into a higher-dimensional space, Kernel PCA can uncover complex structures within the data that traditional PCA might miss.

PCA and Kernal PCA

How Kernel PCA Works

1. Data Mapping with Kernel Trick:

• Kernel PCA maps the original data into a higher-dimensional feature space using a kernel function.
• The kernel function k(xi​,xj​) computes the inner products between the images of the data points in the feature space, without explicitly computing the coordinates of the points in that space (the “kernel trick”).

2. Compute the Kernel Matrix:

• Construct a symmetric kernel matrix K where Kij​=k(xi​,xj​).

3. Center the Kernel Matrix:

• Center the kernel matrix to ensure that the data has zero mean in the feature space. This is done using the formula:

K′=K−1N​K−K1N​+1N​K1N​

where 1N is a matrix of ones divided by N (the number of data points).

4. Compute Eigenvalues and Eigenvectors:

• Perform eigenvalue decomposition on the centered kernel matrix K′. Let λ1,λ2,…,λN​ be the eigenvalues and α1,α2,…,αN​ be the corresponding eigenvectors.

5. Project Data onto Principal Components:

• The principal components are the projections of the data onto the eigenvectors in the feature space. The transformed data in the new feature space is given by:

Differences Between PCA and Kernel PCA

Linear vs. Non-Linear:

• PCA is a linear method and is only capable of capturing linear relationships in the data.
• Kernel PCA, on the other hand, can capture non-linear relationships by implicitly mapping the data into a higher-dimensional space using a kernel function.

Feature Space:

• In PCA, the data is transformed within the original feature space.
• In Kernel PCA, the data is transformed in a high-dimensional feature space determined by the kernel function.

Kernel Function:

• PCA does not use a kernel function.
• Kernel PCA uses kernel functions (e.g., polynomial, Gaussian RBF) to compute the inner products in the high-dimensional feature space.

Working of Kernel PCA: Step-by-Step

1. Select a Kernel: Choose a kernel function (e.g., polynomial, Gaussian RBF) based on the nature of the data and the problem at hand.
2. Construct the Kernel Matrix: Compute the kernel matrix KKK using the chosen kernel function for all pairs of data points.
3. Center the Kernel Matrix: Center the kernel matrix to have zero mean in the feature space.
4. Eigenvalue Decomposition: Perform eigenvalue decomposition on the centered kernel matrix to find the eigenvalues and eigenvectors.
5. Project Data: Project the original data onto the principal components (eigenvectors) in the high-dimensional feature space.

Data in 2D shows data is not linearly separable

Data in 3D

Now we can separate the data linearly.

Pros and Cons of Kernel PCA

Pros:

• Non-Linear Data: Capable of handling non-linear data structures and capturing complex patterns.
• Flexibility: Various kernel functions can be used to adapt to different types of data and problems.
• Higher Dimensional Insights: Allows for the analysis of data in higher-dimensional spaces without explicitly computing the coordinates.

Cons:

• Computationally Intensive: Kernel PCA can be more computationally intensive than linear PCA, especially for large datasets.
• Choice of Kernel: The performance of Kernel PCA heavily depends on the choice of the kernel function and its parameters.
• Interpretability: The results of Kernel PCA can be harder to interpret compared to linear PCA, especially when using complex kernel functions.

PCA vs Kernal PCA

Common Kernel Functions in Kernel PCA

1. Linear Kernel
2. Polynomial Kernel
3. Radial Basis Function (RBF) Kernel
4. Sigmoid Kernel

When to Use Different Kernel Functions

• Linear Kernel: Use when the data is linearly separable or when you suspect that a linear relationship might be sufficient.
• Polynomial Kernel: Use when the data has polynomial relationships of a certain degree.
• RBF Kernel: Use when the data is not linearly separable, and you suspect the data can be separated with a non-linear boundary.
• Sigmoid Kernel: Use in cases where you want to mimic the behaviour of neural networks.

Different types of Kernal PCA

Multidimensional Scaling (MDS)

Multidimensional Scaling (MDS) is a technique used in data analysis to visualize the similarity or dissimilarity of data points in a low-dimensional space. The primary goal of MDS is to place each data point in a low-dimensional space such that the pairwise distances between data points are preserved as much as possible. This helps in understanding the structure of the data and finding patterns or clusters within it.

How MDS Works

1. Input Data: The input to MDS is a distance matrix, which contains the pairwise distances between all data points. This distance matrix can be derived from the original data using various distance metrics (e.g., Euclidean distance, Manhattan distance, etc.).
2. Initialization: The algorithm starts by initializing the positions of data points in a low-dimensional space (typically 2D or 3D).
3. Optimization: MDS iteratively adjusts the positions of the data points in the low-dimensional space to minimize the difference between the pairwise distances in the original high-dimensional space and the low-dimensional space. This is usually done using an optimization method such as stress minimization.

Stress function: The most common objective function used in MDS is the stress function, which measures the disparity between the distances in the original space and the distances in the low-dimensional space. The goal is to minimize this stress function.

stress function

4. Output: The final output is a configuration of points in the low-dimensional space that best preserves the pairwise distances of the original data.

Types of MDS

1. Classical MDS (Metric MDS):

• Assumes that the distances in the original data are Euclidean.
• Seeks to preserve these Euclidean distances in the low-dimensional representation.

2. Non-metric MDS:

• Focuses on preserving the rank order of the distances rather than the exact distances themselves.
• Useful when the exact distances are not known or not reliable, but the order of distances is meaningful.

Multidimensional Scaling (MDS) Vs Principal Component Analysis (PCA)

PCA vs MDS

Non-Negative Matrix Decomposition

Non-Negative Matrix Factorization (NMF) is a group of algorithms in multivariate analysis and linear algebra where a matrix VVV is factorized into (usually) two matrices WWW and HHH, with the property that all three matrices have no negative elements. NMF is used in fields such as text mining, computer vision, and bioinformatics.

Key Concepts of NMF

1. Matrix Factorization: Given a non-negative matrix V of size m×n, NMF finds two non-negative matrices W (of size m×r ) and H (of size r×n) such that:

V≈WH

• Here, r is the rank of the factorization, which is typically much smaller than both m and n.

2. Non-Negativity: The constraint that all elements of V, W, and H must be non-negative is crucial. This makes the factorization interpretable in many applications because negative quantities often do not make sense (e.g., in image pixel values, word frequencies, etc.).

Use Cases of NMF

1. Topic Modelling in Text Mining: NMF can decompose a document-term matrix into two matrices: one representing topics and the other representing the contribution of each word to the topics. This helps in discovering latent topics in a corpus of documents.
2. Image Processing: In image processing, NMF can be used for parts-based representation. For instance, it can decompose an image into a combination of basic parts, such as in face recognition where faces are represented as combinations of features like eyes, noses, and mouths.
3. Recommender Systems: NMF can be applied to collaborative filtering in recommender systems, where user-item interaction matrices are factorized to discover latent factors representing users’ preferences and items’ properties.
4. Bioinformatics: NMF is used in bioinformatics for clustering genes and classifying diseases based on gene expression data.

Pros and Cons of NMF

Pros and Cons of NMF