Linear Methods for Streaming Feature Construction

Linear methods for streaming feature construction are techniques that involve
creating new features in a linear fashion from streaming data, often with a focus on
efficiency and adaptability to data arriving sequentially. These methods are suitable
for real-time or near-real-time applications were data streams continuously. Here are
some linear methods for streaming feature construction:

(i) Principal Component Analysis (PCA)

(ii) Linear Discriminant Analysis (LDA)

Principal Component Analysis

Principal Component Analysis is an unsupervised learning algorithm that is used for

the dimensionality reduction in machine learning. It is a statistical process that
converts the observations of correlated features into a set of linearly uncorrelated
features with the help of orthogonal transformation. These new transformed
features are called the Principal Components. It is one of the popular tools that is
used for exploratory data analysis and predictive modeling. It is a technique to draw
strong patterns from the given dataset by reducing the variances.

PCA generally tries to find the lower-dimensional surface to project the high-
dimensional data.

PCA works by considering the variance of each attribute because the high attribute
shows the good split between the classes, and hence it reduces the dimensionality.
Some real-world applications of PCA are image processing, movie
recommendation system, optimizing the power allocation in various
communication channels. It is a feature extraction technique, so it contains the
important variables and drops the least important variable.

The PCA algorithm is based on some mathematical concepts such as:

o Variance and Covariance

o Eigenvalues and Eigen factors

Some common terms used in PCA algorithm:

o Dimensionality: It is the number of features or variables present in the given

dataset. More easily, it is the number of columns present in the dataset.

o Correlation: It signifies that how strongly two variables are related to each other.
Such as if one changes, the other variable also gets changed. The correlation value
ranges from -1 to +1. Here, -1 occurs if variables are inversely proportional to each
other, and +1 indicates that variables are directly proportional to each other.

o Orthogonal: It defines that variables are not correlated to each other, and hence
the correlation between the pair of variables is zero.

o Eigenvectors: If there is a square matrix M, and a non-zero vector v is given. Then

v will be eigenvector if Av is the scalar multiple of v.

o Covariance Matrix: A matrix containing the covariance between the pair of

variables is called the Covariance Matrix.

Principal Components in PCA

As described above, the transformed new features or the output of PCA are the Principal
Components. The number of these PCs are either equal to or less than the original
features present in the dataset. Some properties of these principal components are given
below:

o The principal component must be the linear combination of the original features.

o These components are orthogonal, i.e., the correlation between a pair of variables is
zero.

o The importance of each component decreases when going to 1 to n, it means the 1

PC has the most importance, and n PC will have the least importance.

Steps for PCA algorithm

1. Getting the dataset

Firstly, we need to take the input dataset and divide it into two subparts X and Y,
where X is the training set, and Y is the validation set.
2. Representing data into a structure
Now we will represent our dataset into a structure. Such as we will represent the two-
dimensional matrix of independent variable X. Here each row corresponds to the data
items, and the column corresponds to the Features. The number of columns is the
dimensions of the dataset.

3. Standardizing the data

In this step, we will standardize our dataset. Such as in a particular column, the features
with high variance are more important compared to the features with lower variance.
If the importance of features is independent of the variance of the feature, then we will
divide each data item in a column with the standard deviation of the column. Here we
will name the matrix as Z.

4. Calculating the Covariance of Z

To calculate the covariance of Z, we will take the matrix Z, and will transpose it. After
transpose, we will multiply it by Z. The output matrix will be the Covariance matrix of Z.

5. Calculating the Eigen Values and Eigen Vectors

Now we need to calculate the eigenvalues and eigenvectors for the resultant covariance
matrix Z. Eigenvectors or the covariance matrix are the directions of the axes with high
information. And the coefficients of these eigenvectors are defined as the eigenvalues.

6. Sorting the Eigen Vectors

In this step, we will take all the eigenvalues and will sort them in decreasing order, which
means from largest to smallest. And simultaneously sort the eigenvectors accordingly in
matrix P of eigenvalues. The resultant matrix will be named as P*.

7. Calculating the new features Or Principal Components

Here we will calculate the new features. To do this, we will multiply the P* matrix to the
Z. In the resultant matrix Z*, each observation is the linear combination of original
features. Each column of the Z* matrix is independent of each other.

8. Remove less or unimportant features from the new dataset.

The new feature set has occurred, so we will decide here what to keep and what to
remove. It means, we will only keep the relevant or important features in the new
dataset, and unimportant features will be removed out.
Applications of Principal Component Analysis

o PCA is mainly used as the dimensionality reduction technique in various AI

applications such as computer vision, image compression, etc.

o It can also be used for finding hidden patterns if data has high dimensions.
Some fields where PCA is used are Finance, data mining, Psychology, etc.

Linear Discriminant Analysis (LDA)

Linear Discriminant Analysis (LDA) is one of the commonly used dimensionality

reduction techniques in machine learning to solve more than two-class
classification problems. It is also known as Normal Discriminant Analysis (NDA) or
Discriminant Function Analysis (DFA).
This can be used to project the features of higher dimensional space into lower-
dimensional space in order to reduce resources and dimensional costs. In this
topic, "Linear Discriminant Analysis (LDA) in machine learning”, we will
discuss the LDA algorithm for classification predictive modelling problems,
limitation of logistic regression, representation of linear Discriminant analysis
model, how to make a prediction using LDA, how to prepare data for LDA,
extensions to LDA and much more. So, let's start with a quick introduction to
Linear Discriminant Analysis (LDA) in machine learning.
What is Linear Discriminant Analysis (LDA)?
Although the logistic regression algorithm is limited to only two-class, linear
Discriminant analysis is applicable for more than two classes of classification
problems.
Linear Discriminant analysis is one of the most popular dimensionality
reduction techniques used for supervised classification problems in
machine learning. It is also considered a pre-processing step for modelling
differences in ML and applications of pattern classification.
Whenever there is a requirement to separate two or more classes having multiple
features efficiently, the Linear Discriminant Analysis model is considered the most
common technique to solve such classification problems. For e.g., if we have two
classes with multiple features and need to separate them efficiently. When we
classify them using a single feature, then it may show overlapping.
To overcome the overlapping issue in the classification process, we must increase
the number of features regularly.

Example:

Let's assume we have to classify two different classes having two sets of data points
in a 2-dimensional plane as shown below image:

However, it is impossible to draw a straight line in a 2-d plane that can separate
these data points efficiently but using linear Discriminant analysis; we can
dimensionally reduce the 2-D plane into the 1-D plane. Using this technique, we can
also maximize the separability between multiple classes.

How Linear Discriminant Analysis (LDA) works?

Linear Discriminant analysis is used as a dimensionality reduction technique in

machine learning, using which we can easily transform a 2-D and 3-D graph into a
1-dimensional plane.

Let's consider an example where we have two classes in a 2-D plane having an X-Y
axis, and we need to classify them efficiently. As we have already seen in the above
example that LDA enables us to draw a straight line that can completely separate
the two classes of the data points. Here, LDA uses an X-Y axis to create a new axis
by separating them using a straight line and projecting data onto a new axis.

Hence, we can maximize the separation between these classes and reduce the 2-D
plane into 1-D.
To create a new axis, Linear Discriminant Analysis uses the following criteria:

o It maximizes the distance between means of two classes.

o It minimizes the variance within the individual class.

Using the above two conditions, LDA generates a new axis in such a way that it can
maximize the distance between the means of the two classes and minimizes the
variation within each class.

In other words, we can say that the new axis will increase the separation between the
data points of the two classes and plot them onto the new axis.

Why LDA?

o Logistic Regression is one of the most popular classification algorithms that

perform well for binary classification but falls short in the case of multiple
classification problems with well-separated classes. At the same time, LDA
handles these quite efficiently.

o LDA can also be used in data pre-processing to reduce the number of features,
just as PCA, which reduces the computing cost significantly.

o LDA is also used in face detection algorithms. In Fisher faces, LDA is used to
extract useful data from different faces. Coupled with eigenfaces, it produces
effective results.

Drawbacks of Linear Discriminant Analysis (LDA)

Although, LDA is specifically used to solve supervised classification problems for two
or more classes which are not possible using logistic regression in machine learning.
But LDA also fails in some cases where the Mean of the distributions is shared. In this
case, LDA fails to create a new axis that makes both the classes linearly separable.
To overcome such problems, we use non-linear Discriminant analysis in machine
learning.

Extension to Linear Discriminant Analysis (LDA)

Linear Discriminant analysis is one of the most simple and effective methods to solve
classification problems in machine learning. It has so many extensions and variations as
follows:

1. Quadratic Discriminant Analysis (QDA): For multiple input variables, each

class deploys its own estimate of variance.

2. Flexible Discriminant Analysis (FDA): it is used when there are non-linear

groups of inputs are used, such as splines.

3. Flexible Discriminant Analysis (FDA): This uses regularization in the estimate

of the variance (actually covariance) and hence moderates the influence of
different variables on LDA.

Real-world Applications of LDA

Some of the common real-world applications of Linear discriminant Analysis are given
below:

o Face Recognition
Face recognition is the popular application of computer vision, where each face is
represented as the combination of a number of pixel values. In this case, LDA is
used to minimize the number of features to a manageable number before going
through the classification process. It generates a new template in which each
dimension consists of a linear combination of pixel values. If a linear combination is
generated using Fisher's linear discriminant, then it is called Fisher's face.

o Medical
In the medical field, LDA has a great application in classifying the patient disease
on the basis of various parameters of patient health and the medical treatment
which is going on. On such parameters, it classifies disease as mild, moderate, or
severe. This classification helps the doctors in either increasing or decreasing the
pace of the treatment.
o Customer Identification
In customer identification, LDA is currently being applied. It means with the
help of LDA; we can easily identify and select the features that can specify the
group of customers who are likely to purchase a specific product in a shopping
mall. This can be helpful when we want to identify a group of customers who
mostly purchase a product in a shopping mall.

o For Predictions
LDA can also be used for making predictions and so in decision making. For
example, "will you buy this product” will give a predicted result of either one
or two possible classes as a buying or not.

o In Learning
Nowadays, robots are being trained for learning and talking to simulate human
work, and it can also be considered a classification problem. In this case, LDA
builds similar groups on the basis of different parameters, including pitches,
frequencies, sound, tunes, etc.

Difference between Linear Discriminant Analysis and PCA

Below are some basic differences between LDA and PCA:

o PCA is an unsupervised algorithm that does not care about classes and labels
and only aims to find the principal components to maximize the variance in the
given dataset. At the same time, LDA is a supervised algorithm that aims to
find the linear discriminants to represent the axes that maximize separation
between different classes of data.

o LDA is much more suitable for multi-class classification tasks compared to PCA.
However, PCA is assumed to be an as good performer for a comparatively
small sample size.

o Both LDA and PCA are used as dimensionality reduction techniques, where
PCA is first followed by LDA.
How to Prepare Data for LDA

Below are some suggestions that one should always consider while preparing the
data to build the LDA model:

o Classification Problems: LDA is mainly applied for classification problems to

classify the categorical output variable. It is suitable for both binary and multi-
class classification problems.

o Gaussian Distribution: The standard LDA model applies the Gaussian

Distribution of the input variables. One should review the univariate
distribution of each attribute and transform them into more Gaussian-looking
distributions. For e.g., use log and root for exponential distributions and Box-
Cox for skewed distributions.

o Remove Outliers: It is good to firstly remove the outliers from your data
because these outliers can skew the basic statistics used to separate classes in
LDA, such as the mean and the standard deviation.

o Same Variance: As LDA always assumes that all the input variables have the
same variance, hence it is always a better way to firstly standardize the data
before implementing an LDA model. By this, the Mean will be 0, and it will
have a standard deviation of 1.
3. Feature-Based Time-Series Analysis

3.1 The Time Series Data Type

The passing of time is a fundamental component of the human experience and the
dynamics of real-world processes is a key driver of human curiosity. On observing a leaf in
the wind, we might contemplate the burstiness of the wind speed, whether the wind
direction now is related to what it was a few seconds ago, or whether the dynamics might
be similar if observed tomorrow. This line of questioning about dynamics has been followed
to understand a wide range of real-world processes, including in seismology (e.g.,
recordings of earthquake tremors), biochemistry (e.g., cell potential fluctuations),
biomedicine (e.g., recordings of heart rate dynamics), ecology (e.g., animal population
levels over time), astrophysics (e.g., radiation dynamics), meteorology (e.g., air pressure
recordings), economics (e.g., inflation rates variations), human machine interfaces (e.g.,
gesture recognition from accelerometer data), and industry (e.g., quality control sensor
measurements on a production line). In each case, the dynamics can be captured as a set
of repeated measurements of the system over time, or a time series. Time series are a
fundamental data type for understanding dynamics in real-world systems. Note that
throughout this work we use the convention of hyphenating “time-series” when used as an
adjective, but not when used as a noun (as “time series”). In general, time series can be
sampled non-uniformly through time, and can therefore be represented as a vector of time
stamps, ti, and associated measurements, xi. However, time series are frequently sampled
uniformly through time (i.e., at a constant sampling period, ∆t), facilitating a more compact
representation as an ordered vector x = (x1, x2, ..., xN), where N measurements have
been taken at times t = (0, ∆t, 2∆t, ...,(N − 1)∆t). Representing a uniformly sampled time
series as an ordered vector allows other types of real-valued sequential data to be
represented in the same way, such as spectra (where measurements are ordered by
frequency), word length sequences of sentences in books (where measurements are
ordered through the text), widths of rings in tree trunks (ordered across the radius of the
trunk cross section), and even the shape of objects (where the distance from a central
point in a shape can be measured and ordered by the angle of rotation of the shape) .
Some examples are shown in Fig. 4.1. Given this common representation for sequential
data, methods developed for analysing time series (which order measurements by time),
can also be applied to understand patterns in any sequential data.
Figure: Sequential data can be ordered in many ways, including A temperature measured
over time (a time series), B a sequence of ring widths, ordered across the cross section
of a tree trunk, and C a frequency spectrum of astrophysical data (ordered by
frequency). All of these sequential measurements can be analyzed by methods that take
their sequential ordering into account, including time-series analysis methods.
While the time series described above are the result of a single
measurement taken repeatedly through time, or univariate time series, measurements
are frequently made from multiple parts of a system simultaneously, yielding multivariate
time series. Examples of multivariate time series include measurements of the activity
dynamics of multiple brain regions through time, or measuring the air temperature, air
pressure, and humidity levels together through time. Techniques have been developed to
model and understand multivariate time series, and infer models of statistical
associations between different parts of a system that may explain its multivariate
dynamics. Methods for characterizing inter-relationships between time series are vast,
including the simple measures of statistical dependencies, like linear cross correlation,
mutual information, and to infer causal (directed) relationships using methods like
transfer entropy and Granger causality. A range of information-theoretic methods for
characterizing time series, particularly the dynamics of information transfer between time
series, are described and implemented in the excellent Java Information Dynamics
Toolkit (JIDT). Feature-based representations of multivariate systems can include both
features of individual time series, and features of inter-relationships between (e.g., pairs
of) time series. However, in this chapter we focus on individual univariate time series
sampled uniformly through time (that can be represented as ordered vectors, xi).