Dimensionality Reduction to aid medical investigation

In machine learning and data science problems, the main objective remains to find the most relevant features that plays a dominant role in determining and influencing the output results.

In most data science problems, the dataset is overfilled with numerous features that results in overfitting and adds to huge training costs (both at cloud and device) and makes the process considerably slow. Successful research investigations has helped scientists, researchers and data scientists to evaluate algorithms that eliminates the curse of dimensionality, in different domains.

The algorithms developed over time aims to resolve some of the basic problems including:

• Reducing dimension of training data set by restoring variance and keeping relevant information intact.

• Reducing training time and cost.

• Structure ways of effective visualizations.

Trust me dimensionality reduction plays a major part in image, audio, video analysis particularly in investigating and curing diseases in our everyday life. Its importance cannot be overlooked in the field of medical research where each and every hospital, clinics and diagnostic centers use machine learning (PCA, ICA, Manifold dimensionality reduction) techniques for diagnosing diseases and prescribing patients with right medicines.

In this blog, I primarily discuss about:

• Algorithms on dimensionality reduction including PCA (Principal Component Analysis), ICA (Independent Component Analysis) and Projection & Manifold Learning.

• Applications in various field with special emphasis of Manifold Learning in the field of research.

Principal Component Analysis (PCA):

As the first step to determine the PCA, is to perform eigenvalue decomposition of a covariance matrix, let’s first understand the concept of eigenvectors and eigenvalues before going into the details of PCA.

EigenVectors

Almost all vectors change direction, when they are multiplied by a matrix A. Eigenvectors (x) behaves as a kind of constant vectors or exceptional vectors that are in the same direction as Ax. Here the multiplied result Ax consists of the matrix A and the eigenvector x.

EigenValues

For the above equation, the scalar ⋋ is termed the eigenvalue of A. It further represents whether the exceptional vector (x) is stretched or shrunk or reversed or left. When ⋋ =0, Ax=0x implies eigenvector x is in null space.

The matrix A gets projected into another space as determined by the direction of eigenvector. For Ax = b , the output vector b represents the new transformed space.

Eigenvector behave like a weathervane that changes in length without any change in direction. It always points to the same direction and space, that the matrix is pushing all vectors toward.

• PCA determines the directions along which the data has maximum variance by analyzing the importance of the data along these directions. When we have three or multiple dimensions, PCA is successful in returning two-dimensional planes. The third dimension lyes orthogonal to the plane. Further, PCA is capable of assigning positive weights to vectors that represent points lying on the two-dimensional planes in compared to the third plane which has a weight of zero.

• PCA is an useful tool for finding patterns in high-dimensional data when the data lies on or close to a d-dimensional linear sub-space. PCA prioritizes dimensionality (by dropping low-variance dimensions in addition to centering, rotating and scaling data) that aids in detecting outliers, speedy convergence in clustering algorithms and further improving neural network’s convergence speed and the overall quality of results.

Kernel PCA

Kernel PCA is an enhanced PCA method that incorporates a kernel function to determine principal components in different high-dimensional space, thereby facilitating solution of non-linear problems. KPCA finds new directions based on kernel matrix. KPCA is limited by an inability to determine importance of variables in contrast to linear PCA where it is possible to identify key variables that contribute to PCA score profiles.

Independent Component Analysis (ICA) :

ICA is a computational method for separating a multivariate signals into additive subcomponents. ICA works under the assumption that the subcomponents comprising the signal sources of the main signal are built from non-Gaussian sources. Moreover they are statistically independent from each other.

ICA plays a dominant role in medical research in biomedical signal extraction and separation. Biomedical signals from many sources including hearts, brains and endocrine systems pose greatest challenge to researchers, radiologists for identifying each body part. Researchers need to separate weak signals arriving from multiple sources that is contaminated with artifacts and noise.

The below figure is an example of how signal from disparate sources mixed in varied proportions is identified by ICA. ICA aims to decompose the signals into subcomponents to identify the activity of distinct signal sources.

Signal from disparate sources mixed in varied proportions is identified by ICA. ICA aims to decompose the signals into subcomponents to identify the activity of distinct signal sources. As per definition, ICA exhibits the following properties.

• Linear projections which are not necessarily orthogonal to each other.

• Generalization of PCA where principal components are nearly statistically independent.

• Source data comprises of linear mixtures of non-gaussian unknown latent variables.

Manifold Learning

Manifold learning for dimensionality reduction has recently gained much attention to assist image processing tasks such as segmentation, registration, tracking, recognition, and computational anatomy.

The drawbacks of PCA in handling dimensionality reduction problems for non-linear weird and curved shaped surfaces necessitated development of more advanced algorithms like Manifold Learning.

There are different variants of Manifold Learning that solves the problem of reducing data dimensions and feature-sets obtained from real world problems representing uneven weird surfaces by sub-optimal data representation. This kind of data representation selectively chooses data points from a low-dimensional manifold that is embedded in a high-dimensional space in an attempt to generalize linear frameworks like PCA.

Manifolds give a look of flat and featureless space that behaves like Euclidean space. Manifold learning problems are unsupervised where it learns the high-dimensional structure of the data from the data itself, without the use of predetermined classifications and loss of importance of information regarding some characteristic of the original variables.

The goal of the manifold-learning algorithms is to recover the original domain structure, up to some scaling and rotation. The nonlinearity of these algorithms allows them to reveal the domain structure even when the manifold is not linearly embedded. It uses some scaling and rotation for this purpose.

Manifold learning algorithms are divided in to two categories:

• Global methods: Allows high-dimensional data to be mapped from high-dimensional to low-dimensional such that the global properties are preserved. Examples include Multidimensional Scaling (MDS), Isomaps covered in the following sections.

• Local methods: Allows high-dimensional data to be mapped to low dimensional such that local properties are preserved. Examples are Locally linear embedding (LLE), Laplacian eigenmap (LE), Local tangent space alignment (LSTA), Hessian Eigenmapping (HLLE) covered in the following sections.

The different learning algorithms discovers different parameters and mechanisms to deduce a low-dimensional representation of the data with algorithms like Isomap, Locally Linear Embedding, Laplacian Eigen-maps, Semidefinite Embedding, etc.

The algorithms related to manifold learning and its applications vary in:

• Intensity of images

• Coordinate transformations, for instance different morphic warps between the images.

• Number of images to be analyzed to interpret similar group of objects.

The different algorithms of Manifold Learning when run on swiss_roll dataset for 10 neighbors and 2 components (which are un-correlated forming the reduced feature set with maximum variation) , for 5000 points is given below, in the code snippet.

from time import time
import matplotlib
matplotlib.use('TkAgg')
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
from matplotlib.ticker import NullFormatter
import numpy as np
import pandas as pd
from sklearn import manifold, datasets
n_points = 5000
X, color = datasets.samples_generator.make_swiss_roll(n_points, random_state=0)
n_neighbors = 10
n_components = 2
df = pd.read_csv('data/falldeteciton.csv')
X1 = df.iloc[0:n_points, [4,5,6]].values
fig = plt.figure(figsize=(15, 8))
plt.suptitle("Manifold Learning with %i points, %i neighbors"
 % (n_points, n_neighbors), fontsize=14)


ax = fig.add_subplot(251, projection='3d')
ax.scatter(X[:, 0], X[:, 1], X[:, 2], c=color, cmap=plt.cm.Spectral)
ax.view_init(4, -72)
methods = ['standard', 'ltsa', 'hessian', 'modified']
labels = ['LLE', 'LTSA', 'Hessian LLE', 'Modified LLE']


for i, method in enumerate(methods):
 t0 = time()
 Y = manifold.LocallyLinearEmbedding(n_neighbors, n_components,
 eigen_solver='auto',
 method=method).fit_transform(X)
 t1 = time()
 print("%s: %.2g sec" % (methods[i], t1 - t0))
 ax = fig.add_subplot(252 + i)
 plt.scatter(Y[:, 0], Y[:, 1], c=color, cmap=plt.cm.Spectral)
 plt.title("%s (%.2g sec)" % (labels[i], t1 - t0))
 ax.xaxis.set_major_formatter(NullFormatter())
 ax.yaxis.set_major_formatter(NullFormatter())
 plt.axis('tight')


t0 = time()
Y = manifold.Isomap(n_neighbors, n_components).fit_transform(X)
t1 = time()
print("Isomap: %.2g sec" % (t1 - t0))
ax = fig.add_subplot(257)
plt.scatter(Y[:, 0], Y[:, 1], c=color, cmap=plt.cm.Spectral)
plt.title("Isomap (%.2g sec)" % (t1 - t0))
ax.xaxis.set_major_formatter(NullFormatter())
ax.yaxis.set_major_formatter(NullFormatter())
plt.axis('tight')


t0 = time()
mds = manifold.MDS(n_components, max_iter=100, n_init=1)
Y = mds.fit_transform(X)
t1 = time()
print("MDS: %.2g sec" % (t1 - t0))
ax = fig.add_subplot(258)
plt.scatter(Y[:, 0], Y[:, 1], c=color, cmap=plt.cm.Spectral)
plt.title("MDS (%.2g sec)" % (t1 - t0))
ax.xaxis.set_major_formatter(NullFormatter())
ax.yaxis.set_major_formatter(NullFormatter())
plt.axis('tight')


t0 = time()
se = manifold.SpectralEmbedding(n_components=n_components,
 n_neighbors=n_neighbors)
Y = se.fit_transform(X)
t1 = time()
print("SpectralEmbedding: %.2g sec" % (t1 - t0))
ax = fig.add_subplot(259)
plt.scatter(Y[:, 0], Y[:, 1], c=color, cmap=plt.cm.Spectral)
plt.title("SpectralEmbedding (%.2g sec)" % (t1 - t0))
ax.xaxis.set_major_formatter(NullFormatter())
ax.yaxis.set_major_formatter(NullFormatter())
plt.axis('tight')
t0 = time()
tsne = manifold.TSNE(n_components=n_components, init='pca', random_state=0)
Y = tsne.fit_transform(X)
t1 = time()
print("t-SNE: %.2g sec" % (t1 - t0))
#ax = fig.add_subplot(2, 5, 10)
ax = fig.add_subplot(267)
plt.scatter(Y[:, 0], Y[:, 1], c=color, cmap=plt.cm.Spectral)
plt.title("t-SNE (%.2g sec)" % (t1 - t0))
ax.xaxis.set_major_formatter(NullFormatter())
ax.yaxis.set_major_formatter(NullFormatter())
plt.axis('tight')
plt.show()

• IsoMap Algorithm : One of the earliest approaches to manifold learning can be viewed as an extension of Multi-dimensional Scaling (MDS) or Kernel PCA. IsoMap aims for a lower-dimensional embedding which maintains geodesic distances between all points. The following figure explains how distances are evaluated for all points.

“Evaluate estimated geodesic distances between all pairs in X.”

“Use dynamic programming to approximate the geodesic of far off points by the shortest path along retained distances”.

This figure illustrates how A. Neighborhood graph is constructed using a fixed radius/K-means algorithm B. Shortest paths/ Geodesic distances are computed and C. d-dimensional embedding is applied with MDS.

• Locally linear embedding (LLE): One of the dimensionality reduction algorithms is LLE thats maps to a lower-dimensional projection of the data by evaluating the best non-linear embedding among a series of local Principal Component Analyses. It uses regularization parameter ‘r’, when the number of neighbors is greater than the number of input dimensions. This also leads to regularization problem that manifests itself in embeddings and distorts the underlying geometry of the manifold. This problem is handled by using multiple vectors in each neighborhood leading to modified locally linear embedding (MLLE), and the function is invoked with the keyword method = ‘modified’ , where n_neighbors > n_components.

• Local tangent space alignment (LTSA) : This algorithm behaves similar to LLE described above, with the only difference of characterizing the local geometry at each neighborhood via its tangent space. Then low-dimensional data is deduced by reducing higher dimensions by applying PCA on the neighboring data points such that the local linear relations of the original data are preserved. The resulting low dimensional dataset represents the neighboring point’s coordinates and serves to approximate the tangent space at the point. It also performs a global optimization to align these local tangent spaces to learn the embedding. The function is invoked by specification of keyword with method = ‘ltsa’. The below figures further illustrates this.

• Hessian Eigen Mapping (Hessian-based LLE: HLLE): This dimensionality reduction solution involves solving the regularization problem of LLE. In addition it can reduce dimensions for multi-class problems. It circulates around a hessian-based quadratic form. The revolving mature is further noticed at each neighborhood which is used to recover the locally linear structure. It suffers from the drawback of poor scaling for huge data size. However, improvements with scikit-learn library incorporates optimizations to make its cost comparable to that of other LLE variants for small output dimension. It requires specification of keyword with method = ‘hessian’ , and n_neighbors > n_components * (n_components + 3) / 2.

• Spectral Embedding: This algorithm as illustrated in the figure below aims to calculate a non-linear embedding by finding a low dimensional representation of the data using a spectral decomposition of the graph Laplacian. The decomposition results in a graph that approximates the low dimensional manifold in the high dimensional space, ensuring the fact local distances are preserved and points which appear closer on the manifold are also mapped closer in the low dimensional space.

• Multidimensional scaling (MDS) : This dimensionality reduction algorithm is one of the multivariate techniques to measure the similarity or dissimilarity in data by transforming the data to a low-dimensional space where the distances between the original high-dimensional (N-dimensional) space gets reflected to the low-dimensional space. The distance metric is measured in geometric spaces where the data ranges from ratings of similarity between objects to interaction frequencies of molecules, or trade indices between countries. Multidimensional scaling is also known for identifying news representation by minimizing the quantity called STRESS or SSTRESS.

• MDS Metric and Non-metric : MDS comprises of metric and non metric algorithms. In Metric MDS, the input similarity matrix is built from a metric (and thus respects the triangular inequality). It is further noticed that the distances between output two points are then set to be as close as possible to the similarity or dissimilarity data. In the non-metric version, the algorithms strives to maintain the order of the distances. In doing so it tries to seek for a monotonic relationship between the distances in the embedded space and the similarities/dissimilarities. The monotonic relationship yields larger or smaller distances at different scales corresponding to larger or smaller dissimilarities.

• t-Distributed Stochastic Neighbor Embedding (t-SNE) :It is a non-linear technique for dimensionality reduction. Its main usage lies in visualization of high-dimensional datasets. t-SNE first computes the probability of a similar group of points both in high-dimensional and low dimensional space to deduce the conditional probability of a point A chooses its neighbor as point B. Further, the conditional probabilities are minimized in higher and lower dimension space by minimizing sum of Kullback-Leibler divergence to have an efficient representation of points in low dimensional space from high dimensional space. However t-SNE does not give optimal results with dimensions > 3 as it gets stuck in local optima.

Applications of Manifold learning in medical research:

• Manifold learning makes it convenient to make observations about the presence of disease or markers of development in populations by allowing easy statistical comparisons between groups through low-dimensional image representations.

• Kernel PCA is widely known for dimensionality reduction on heterogeneous data sources when data from different sources are merged and evaluated to interpret the most prominent factors. For e.g. its used in reducing data dimensions for “non-linear” variations in metabolic data from living organisms. Kernel PCA is used to analyze metabolites strongly associated with diet, exemplifying the fact that increased hippurate is associated with a larger intake of variety of vegetables and fruits.

• Manifold learning facilitates medical research by generating synthetic images. The following picture illustrates a semi-automatic reference maps generation pipeline that combines the results provided by the pathologists (and other manual segmentation mechanisms) together with automatic segmentation techniques, to yield different versions of synthetic images (generated from transformations like rotations, crops, geometric distortions and scaling). It aids medical investigation by generating high quality images of implicit manifolds corresponding to different parts of the body.

• Classify image slices according to different regions of the body such as head, abdomen, and lower leg with the help of manifold structures that helps to clearly distinguish the images.For e.g. t-SNE is used to classify different tissues of the body, by identifying clusters based on similarity of the type of tissues. Different colors in the below figure illustrates body parts like cervix, heart, kidney, liver, brain, eyes , etc

• Locally Linear Embedding is used for brain function detection. The following figure depicts that the first three major dimensions of embeddings of the brain functional networks. Figure A portrays the embedding of the brain functional networks using LLE-SPD ( Symmetric Positive Definite (SPD)) in the LogEuclidean manifold space, while Figure B illustrates the embedding of the brain functional networks using LLE in the Euclidean space.

• Apply Independent Component Analysis (ICA) to evaluate a set of basis images/signal, and represent an input image/signal as linear combination of those. The below figure illustrates how ICA can be applied to isolate individual components in ECG.

References:

• https://jakevdp.github.io/PythonDataScienceHandbook/05.10-manifold-learning.html
• https://www.researchgate.net/publication/221624751_Manifold_learning_for_patient_position_detection_in_MRI
• https://sccn.ucsd.edu/~scott/pdf/ICA00b.pdf
• https://airccse.com/ijbes/papers/1214ijbes03.pdf
• http://web.mit.edu/6.454/www/www_fall_2003/ihler/slides.pdf
• http://www.jaist.ac.jp/~bao/VIASM-SML/Lecture/L4-Dimensionality%20reduction.pdf
• https://www.nature.com/articles/s41598-018-20121-w

Please let me know if there were any mistakes. Suggestions and feedbacks are welcome. Feel free to follow me at linkedin.