Chapter 4

Basics of Feature Engineering

Overview:
 Feature and Feature Engineering
 Feature transformation: Construction and extraction
 Feature subset selection : Issues in high-dimensional
data, key drivers, measure and overall process
 Features and Feature Engineering
• Feature:
An attribute of a data set that is used in a machine learning process.

The features in a data set are also called its dimensions.

(a data set having ‘n’ features is called an n-dimensional data set.)

Iris Dataset
 Feature Engineering
 Refers to the process of translating a data set into features
such that these features are able to represent the data set more
effectively and result in a better learning performance.

 Elements: 1. Feature transformation

2. Feature subset selection
 Feature Transformation
• Transforms the data (structured or unstructured) into a new
set of features which can represent the underlying problem
which machine learning is trying to solve.

• Variants: 1. Feature construction

2. Feature extraction

Both are sometimes known as feature discovery.

• Feature Construction:
 Process discovers missing information about the
relationships b/w features and augments the feature space by
creating additional features.

 If there are ‘n’ features, after feature construction ‘m’ more

features or dimensions may get added.
The data set will become ‘n + m’ dimensional.
• Feature extraction:
Process of extracting or creating a new set of features from the
original set of features using some functional mapping.
 Feature Transformation
 Two imp. goals of feature transformation:
• Achieving best reconstruction of the original features in the
data set
• Achieving highest efficiency in the learning task
 Feature Construction
• Involves transforming a given set of input features to generate a new
set of more powerful features.

• Example:
 Situations in which it is essential to use Feature
Construction
 When features have categorical value and machine learning
needs numeric value inputs.
 When features having numeric (continuous) values and need
to be converted to ordinal values.
 When text-specific feature construction needs to be done.
Encoding Categorical (Nominal) Variables
Feature construction (encoding nominal variables)
Encoding Categorical (Ordinal) Variables

Feature construction (encoding ordinal variables)

Transforming Numeric (Continuous)
Features to Categorical Features)
 Text-Specific Feature Construction
Text plays a major role in the flow of information.
Text mining is an important area of research.

 Almost all machine learning models need numerical data as input. So

the text data in the data sets need to be transformed into numerical
features.

 Text data (Corpus) is converted to a numerical representation

following a process is known as Vectorization.
 Three major steps that are followed:
1. Tokenize
2. Count
3. Normalize

 In order to tokenize a corpus, the blank spaces and

punctuations are used as delimiters to separate out the words,
or tokens.

 Next, the number of occurrences of each token is counted,

for each document.
 Tokens are weighted with reducing importance when they occur in
the majority of the documents.

 A matrix is then formed with each token representing a column and a

specific document of the corpus representing each row.

 Each cell contains the count of occurrence of the token in a specific

document. This matrix is known as a document-term matrix (also
known as a term document matrix).
Feature construction (text-specific)
 Feature Extraction
 New features are created from a combination of original
features.

 Commonly used operators for combining the original

features include,
1. For Boolean features: Conjunctions, Disjunctions,
Negation, etc.
2. For nominal features: Cartesian product, M of N, etc.
3. For numerical features: Min, Max, Addition, Subtraction,
Multiplication, Division, Average, Equivalence, Inequality, etc.
Popular feature extraction algorithms used in
machine learning:

o Principal Component Analysis

o Singular Value Decomposition
o Linear Discriminant Analysis
 Principal Component Analysis
• Key to the success of machine learning lies in the fact that the features
are less in number as well as the similarity between each other is very
less.

• In PCA, a new set of features are extracted from the original features
which are quite dissimilar in nature.
(an n- dimensional feature space gets transformed to an m- dimensional
feature space, where the dimensions are orthogonal to each other.)

i.e. completely independent of each other.

• Concept of Vector:

 Vector is a quantity having both magnitude and direction.

(Can determine the position of a point relative to another point
in the Euclidean space.)

 Vector space = Set of vectors.

(Property that they can be represented as a linear combination
of a smaller set of vectors, called basis vectors.)
 Any vector ‘v’ in a vector space can be represented as,

where, a represents ‘n’ scalars and u represents the basis vectors.

Basis vectors are orthogonal to each other.

Two orthogonal vectors are completely unrelated or independent

of each other.
 In terms of Machine Learning (or Data Set)..

 The feature vector can be transformed to a vector space of

the basis vectors which are termed as principal components.

(Principal components, just like the basis vectors, are

orthogonal and completely unrelated to each other. )
Objectives of PCA:
 The new features are distinct, i.e. the covariance between the
new features.

 The principal components are generated in order of the

variability in the data that it captures.
(The first principal component should capture the maximum variability,
the second principal component should capture the next highest
variability etc.)

The sum of variance of the new features or the principal

components should be equal to the sum of variance of the
original features.
Steps:
• Calculate the covariance matrix of a data set.
• Calculate the eigenvalues of the covariance matrix.
• The eigenvector having highest eigenvalue represents the
direction in which there is the highest variance. (Helps to find
first PC)
• The eigenvector having the next highest eigenvalue
represents the direction in which data has the highest
remaining variance and also orthogonal to the first direction.
(Helps to find second PC))
• Like this, identify the top ‘k’ eigenvectors having top ‘k’
eigenvalues so as to get the ‘k’ principal components.
 Singular Value Decomposition (SVD)
• A matrix factorization technique commonly used in linear
algebra.
• SVD of a matrix A (m × n) is a factorization of the form,

• where, U and V = orthonormal matrices

U is an m × m unitary matrix
V is an n × n unitary matrix
∑ is an m × n rectangular diagonal matrix
• The diagonal entries of ∑ are known as singular values of
matrix A.
• The columns of U and V are called the left-singular and
right-singular vectors of matrix A, respectively.
Expected Properties of SVD of a Data
Matrix:
 Patterns in the attributes are captured by the right-singular vectors,
i.e. the columns of V.
 Patterns among the instances are captured by the left-singular, i.e. the
columns of U.
 Larger a singular value, larger is the part of the matrix A that it
accounts for and its associated vectors.
 New data matrix with ‘k’ attributes is obtained using the equation D =
D × [v , v , … , v ] Thus, the dimensionality gets reduced to k.s SVD
is often used in the context of text data.
 Linear Discriminant Analysis
• Intends to transform a data set into a lower dimensional
feature space.

• Unlike PCA, the focus of LDA is not to capture the data set
variability. Instead, LDA focuses on class separability.
( i.e. separating the features based on class separability so as to avoid over-fitting of
the machine learning model.)

• LDA calculates eigenvalues and eigenvectors within a class

and inter-class scatter matrices.
Steps:
• Calculate the mean vectors for the individual classes.

• Calculate intra-class and inter-class scatter matrices.

• Calculate eigenvalues and eigenvectors for S w and Sb , where

Sw is the intra-class scatter matrix and S b is the inter-class
scatter matrix.
• Identify the top ‘k’ eigenvectors having top ‘k’ eigenvalues.
 Feature Subset Selection
• Intends to select a subset of system attributes or features
which makes a most meaningful contribution in a machine
learning activity.

• Issues in high-dimensional data:

With the rapid innovations in the digital space, the volume of
data generated has increased to an unbelievable extent.
At the same time, breakthroughs in the storage technology area have made
storage of large quantity of data quite cheap.
 ‘High-dimensional’ refers to the high number of variables or
attributes or features present in certain data sets.

(Domains like DNA analysis, geographic information systems (GIS),

social networking, etc.)

Often have hundreds or thousands of dimensions or attributes, e.g.

DNA microarray data can have up to 450,000 variables (gene probes)
• Very high quantity of computational resources and high amount of
time will be required, model may be very difficult to understand.

• Also, this “noise” degrade the performance of

supervised/unsupervised learning.
• The objective of feature selection is three-fold:

 Having faster and more cost-effective (i.e. less need for

computational resources) learning model.
 Improving the efficiency of the learning model.
 Having a better understanding of the underlying model that
generated the data.
 Key drivers of Feature Selection:
Feature Relevance and Redundancy
 Feature Relevance
• In supervised learning, the input data set which is the
training data set, has a class label attached.
• Each of the predictor variables, is expected to contribute
information to decide the value of the class label.
• In case a variable is not contributing any information, it is
said to be irrelevant. In case the information contribution for
prediction is very little, the variable is said to be weakly
relevant.
• Remaining variables, which make a significant contribution
to the prediction task are said to be strongly relevant
variables.
In Unsupervised Learning..
• There is no training data set or labelled data. Grouping of
similar data instances are done and similarity of data
instances are evaluated based on the value of different
variables.
• Certain variables do not contribute any useful information for
deciding the similarity of dissimilarity of data instances.
• Hence, those variables make no significant information
contribution in the grouping process.
• These variables are marked as irrelevant variables in the
context of the unsupervised machine learning task.
 Feature Redundancy
• A feature may contribute information which is similar to the
information contributed by one or more other features.

• All features having potential redundancy are candidates for

rejection in the final feature subset.

• Only a small number of representative features out of a set of

potentially redundant features are considered for being a part
of the final feature subset.
Measures of Feature Relevance and
Redundancy
• The measure of feature relevance is determined by assessing
the quantity of information a feature provides.

• For supervised learning, mutual information is considered as

a good measure of information contribution of a feature to
decide the value of the class label.

Higher the value of mutual information of a feature, more

relevant is that feature.
Marginal entropy of the class, H(C) =

Marginal entropy of the feature ‘x’, H( f ) =

K = number of classes, C = class variable, f = feature set that take

discrete values. and K = number of classes, C = class variable, f =
feature set that take discrete values.
In case of Unsupervised Learning..
• There is no class variable. Hence, feature-to-class mutual
information cannot be used to measure the information
contribution of the features.

• The entropy of the set of features without one feature at a

time is calculated for all the features.

• The entropy of a feature f is calculated using Shannon’s

formula, is used only for features that take discrete values.
• Shanon’s formula:
Measures of Feature Redundancy
There are several measures used to assess the similarity of
information contribution, with some of the prominent ones
including:

1. Correlation-based measures
2. Distance-based measures
3. Other coefficient-based measure
 Correlation-based Similarity Measure
 Correlation is a measure of linear dependency between two
random variables.

 Pearson’s product moment correlation coefficient is one of

the most popular and accepted measures of correlation
between two random variables.
 For two random feature variables F1 and F2 , Pearson
correlation coefficient is defined as,
 Correlation values range between +1 and –1.

 A correlation of 1 (+ / –) indicates perfect correlation, i.e. the two

features having a perfect linear relationship.

 In case the correlation is 0, then the features seem to have no

linear relationship.

 Generally, for all feature selection problems, a threshold value is

adopted to decide whether two features have adequate similarity or
not.
 Distance-based Similarity Measure
 The most common distance measure is the Euclidean
distance, which, between two features F and F are calculated,

where F1 and F2 are features of an n-dimensional data set.

• A more generalized form of the Euclidean distance is the
Minkowski distance, measured as,

• Minkowski distance takes the form of Euclidean distance

(also called L norm) when r = 2.

• At r = 1, it takes the form of Manhattan distance (also

called L norm)
• Frequently used Manhattan distance to calculate the
distance b/w binary vectors is Hamming Distance.

Example: The Hamming distance between two vectors

01101011 and 11001001 is 3
 Other Similarity Measures
• Jaccard index/coefficient is used as a measure of similarity
between two features.

• The Jaccard distance, a measure of dissimilarity between two

features, is complementary of Jaccard index.
• For two features having binary values, Jaccard index is
measured as,

where, n11 = number of cases where both the features have value
1
n01 = number of cases where the feature 1 has value 0 and feature
2 has value 1
n10 = number of cases where the feature 1 has value 1 and feature
2 has value 0

Jaccard distance, d = 1 - J
• Simple matching coefficient (SMC) is almost same as
Jaccard coeficient except the fact that it includes a number of
cases where both the features have a value of 0.

where, n11 = number of cases where both the features have value 1
n01 = number of cases where the feature 1 has value 0 and feature 2 has
value 1
n10 = number of cases where the feature 1 has value 1 and feature 2 has
value 0
n00 = number of cases where both the features have value 0
• Cosine similarity which is one of the most popular measures
in text classification.
Calculate the cosine similarity of x and y, where x = (2, 4, 0, 0,
2, 1, 3, 0, 0) and y = (2, 1, 0, 0, 3, 2, 1, 0, 1).
• Cosine similarity actually measures the angle between x and
y vectors.
• If cosine similarity has a value 1, the angle between x and y
is 0° which means x and y are same except for the magnitude.
• If cosine similarity is 0, the angle between x and y is 90°.
Hence, they do not share any similarity (in case of text data,
no term/word is common).
Overall Feature Selection Process

Feature selection process

Subset generation:
• Procedure which ideally should produce all possible candidate subsets.
• For n-dimensional dataset, possible subsets are 2 n.
• As the value of ‘n’ becomes high, finding an optimal subset from all
the 2 candidate subsets becomes intractable.
• Different approximate search strategies are employed to find candidate
subsets for evaluation.
• The search that start with an empty set and keep adding features. This
search strategy is termed as a Sequential forward selection.

• A search may start with a full set and successively remove features.
This strategy is termed as Sequential backward elimination.

• In certain cases, search start with both ends and add and remove
features simultaneously. This strategy is termed as a Bi-directional
selection.
• Each candidate subset is then evaluated and compared with
the previous best performing subset based on certain
evaluation criterion.
• If the new subset performs better, it replaces the previous
one.
• The cycle of subset generation and evaluation continues till a
pre-defined stopping criterion is fulfilled.
Stopping Criteria:
1. The search completes.
2. Some given bound (e.g. a specified number of iterations) is
reached.
3. Subsequent addition (or deletion) of the feature is not
producing a better subset.
4. A sufficiently good subset (e.g. a subset having better
classification accuracy than the existing benchmark) is
selected.
Next..

• The selected best subset is validated either against prior

benchmarks or by experiments using real-life or synthetic but
authentic data sets.

• In case of supervised learning, the accuracy of the learning model

may be the performance parameter considered for validation.

• In case of unsupervised learning, the cluster quality may be the

parameter for validation.
 Feature Selection Approaches
1. Filter approach
2. Wrapper approach
3. Hybrid approach
4. Embedded approach
 Filter Approach

Statistic Measure: Pearson’s correlation, information gain, Fisher score,

analysis of variance (ANOVA), Chi-Square, etc.
 Wrapper Approach

• Identification of best feature subset is done using the induction

algorithm as a black box.
• Computationally very expensive.
• Performance is generally superior compared to filter approach.
 Hybrid Approach
• Takes the advantage of both filter and wrapper approaches.

• A typical hybrid algorithm makes use of both the statistical

tests as used in filter approach to decide the best subsets for a
given cardinality and a learning algorithm to select the final
best subset among the best subsets across different
cardinalities.
Embedded approach