Unit 2-

Modeling and Evaluation

Introduction : The basic learning process for a machine is divided into

three parts:

1. Data Input 2.Abstraction 3. Generalization

To understood these aspects, consider an example: The detective

department of New City Police has got a tip that in a campaign gathering for the upcoming election, a criminal is going to launch an attack on the main candidate.

Data Input: The criminal database, a list of such criminals along with

their photographs has been collected. Also, the photos taken by security cameras positioned at different places near the gathering are available with the detective department.

Abstraction: match the photos and find certain salient physical features like the shape of the jaw, the slope of the forehead, the size of the eyes,

the structure of the ear, etc.

Generalization: generalization of abstracted feature-based data. From the abstracted feature based data, it is observed that most of the criminals have a shorter distance between the inner corners of the eyes, a smaller angle between the nose and the corners of the mouth, a higher curvature to the upper lip, etc.

Model:

Structured representation of raw input data to the meaningful pattern is called a model.

​

​

Training: The process of assigning a model, and fitting a specific model to a data set is called model training. Once the model is trained, the raw input data is summarized into an abstracted form.

​

​

Bias:  Bias is a systematic error that occurs due to wrong assumptions in the machine learning process. 

Target function: A machine learning algorithm creates its cognitive capability by building a mathematical formulation or function, known as target function, based on the features in the input data set.

Hyper-parameters: In machine learning someone has to provide some non-learnable parameters, also called hyper-parameters. Without these human inputs, machine learning algorithms cannot be successful.

The goal

SELECTING A MODEL

is to develop a model to find the association between the

potential influencing factors and the response.

[Ex] : To eliminate all criminal activities in the region. So, the model is developed to find the pattern of criminal activities. For that to see the association between criminal incidents has any relation with an average income of the local population, weapon sales, the inflow of immigrants, and other factors.

In machine learning paradigm, the potential factors of criminal activities

e.g. average income of the local population, weapon sales, the inflow of immigrants, etc. are input variables. They are also called predictors, attributes, features, independent variables, or simply variables.

​

The criminal incidents is an output variable (also called response or dependent variable).

​

Input variables can be denoted by X, while individual input variables are represented as X₁ , X₂ , X₃ , …, X_n and output variable by symbol Y. The relationship between X and Y is represented in the general form:

Y = f (X) + e, where ‘f ’ is the target function and ‘e’ is a

random error term.

Cost function : Also called as error function helps to measure the extent to which the model is going wrong in estimating the relationship between X and Y. In that sense, cost function can tell how bad the model is performing. For example, R-squared is a cost function of regression model.

Loss function : It is similar to cost function – only difference being loss function is usually a function defined on a data point, while cost function is for the entire training data set.

​

Objective function: An objective function serves as a critical tool for quantifying the performance of a model concerning its defined goals.

​

• Objective function takes in data and model (along with parameters) as input and returns a value. Target is to find values of model parameter to maximize or minimize the return value.

There are three broad categories of machine learning approaches used for

resolving different types of problems.

1. Supervised
1. Classification
2. Regression
2. Unsupervised
• Clustering
• Association analysis
• Reinforcement

Multiple factors play a role when to select the model for solving a machine learning problem. The most important factors are

1. the kind of problem to solve using machine learning and
2. the nature of the underlying data.

It is very difficult to give a generic guidance related to which machine learning has to be selected. In other words, there is no one model that works best for every machine learning problem. This is what ‘No Free Lunch’ theorem also states.

Machine learning algorithms are broadly of two types:

supervised learning - primarily focus on solving predictive problems

unsupervised learning - which solve descriptive problems.

​

1. Predictive models

• try to predict certain value using the values in an input data set.
• to establish a relation between the target feature, i.e. the feature being predicted, and the predictor features.
• have a clear focus on what they want to learn and how they want to learn.

​

• Predictive models, in turn, may need to predict the value of a category or class to which a data instance belongs to.

[Ex]: 1. Predicting win/loss in a cricket match 2. Predicting whether a transaction is fraud 3. Predicting whether a customer may move to another product

The prediction of target features of categorical value are known as classification models.

The target feature is known as a class and the categories to which classes are divided into are called levels.

Some of the popular classification models include k-Nearest Neighbor

(kNN), Naïve Bayes, and Decision Tree.

​

Predictive models may also be used to predict numerical values of the target feature based on the predictor features.

[Ex]: 1. Prediction of revenue growth in the succeeding year

2. Prediction of rainfall amount in the coming monsoon
3. Prediction of potential flu patients and demand for flu shots next

winter

The models which are used for prediction of the numerical value of the target feature of a data instance are known as regression models. Linear Regression and Logistic Regression models are popular regression models.

Categorical values can be converted to numerical values and vice versa.

[Ex]: for stock price growth prediction, any growth percentage lying between certain ranges may be represented by a categorical value,

e.g.

0%–5% as low

5%– 10% as moderate

10%–20% as high

and > 20% as booming

In a similar way, a categorical value can be converted to numerical value,

e.g. in the tumor malignancy detection problem, replace , benign as 0 and malignan as 1.

​

This way, the models can be used interchangeably, be used for both classifications as well as for regression.

There are multiple factors to be considered while selecting a model.

​

For example, while selecting the model for prediction, the training data size is an important factor to be considered.

​

If the training data set is small, low variance models like Naïve Bayes are supposed to perform better because model overfitting needs to be avoided in this situation.

​

Similarly, when the training data is large, low bias models like logistic regression should be preferred. Because they can represent complex relationships in a more effective way.

Few models like Support Vector Machines and Neural Network can also be used.

Descriptive models

Unsupervised learning or descriptive models are used to describe a data set or gain insight from a data set.

There is no target feature or single feature of interest in case of unsupervised learning.

Based on the value of all features, interesting patterns or insights are derived about the data set.

Descriptive models which group together similar data instances, i.e. data instances having a similar value of the different features are called clustering models.

[Ex]:1. Customer grouping or segmentation based on social,

demographic, ethnic, etc. factors

2. Grouping of music based on different aspects like genre, language,

time-period, etc.

3. Grouping of commodities in an inventory

The most popular model for clustering is k-Means.

Descriptive models related to pattern discovery is used for market basket analysis of transactional data.

• In market basket analysis, based on the purchase pattern available in the transactional data, the possibility of purchasing one product based on the purchase of another product is determined. [Ex]:Transactional data may reveal a pattern that generally a customer who purchases milk also purchases biscuit at the same time. This can be useful for targeted promotions or in-store set up. Promotions related to biscuits can be sent to customers of milk products or vice versa. Also, in the store products related to milk can be placed close to biscuits.

​

TRAINING A MODEL (FOR SUPERVISED LEARNING)

The methods are

1. Holdout method
2. K-fold Cross-validation method
1. 10-fold cross-validation (10-fold CV)
2. Leave-one-out cross-validation (LOOCV)
3. Bootstrap sampling
4. Lazy vs. Eager learner

1.Holdout method: A model is trained using the labelled input data. The test data may not be available immediately. Also, the label value of the test data is not known. That is the reason why a part of the input data is held back (that is how the name holdout originates) for evaluation of the model.

This subset of the input data is used as the test data for evaluating the performance of a trained model. In general 70%–80% of the input data (which is obviously labelled) is used for model training. The remaining 20%–30% is used as test data for validation of the performance of the model.

However, a different proportion of dividing the input data into training and test data is also acceptable. This method of partitioning the input data into two parts – training and test data , which is by holding back a part of the input data for validating the trained model is known as holdout method.

• Once the model is trained using the training data, the labels of the test data are predicted using the model‟s target function. Then the predicted value is compared with the actual value of the label. This is possible because the test data is a part of the input data with known labels.
• The performance of the model is measured by the accuracy of prediction of the label value. In certain cases, the input data is partitioned into three portions – a training and a test data, and a third validation data.

​

​

• The validation data is used in place of test data, for measuring the model performance.

​

​

• It is used in iterations and to refine the model in each iteration.

​

​

• The test data is used only for once, after the model is refined and finalized, to measure and report the final performance of the model as a reference for future learning efforts.

• An obvious problem in this method is that the division of data of different classes into the training and test data may not be proportionate. This situation is worse if the overall percentage of data related to certain classes is much less compared to other classes.
• This may happen despite the fact that random sampling is employed for test data selection. This problem can be addressed to some extent by applying stratified random sampling in place of sampling.
• In case of stratified random sampling, the whole data is broken into several homogenous groups or strata and a random sample is selected from each such stratum. This ensures that the generated random partitions have equal proportions of each class.

​

Simple random samples and stratified random samples are both statistical measurement tools. 

​

​

A simple random sample is used to represent the entire data population.

​

​

A stratified random sample divides the population into smaller groups, or strata, based on shared characteristics.

• 2. K-fold Cross-validation method

Holdout method employing stratified random sampling approach still heads into issues in certain specific situations. A special variant of holdout method, called repeated holdout, is sometimes used. In repeated holdout, several random holdouts are used to measure the model performance. In the end, the average of all performances is taken.

As multiple holdouts have been drawn, the training and test data (and also validation data, in case it is drawn) are more likely to contain representative data from all classes and resemble the original input data closely. This process of repeated holdout is the basis of k-fold cross- validation technique. In k-fold cross-validation, the data set is divided into kcompletely distinct or non-overlapping random partitions called folds.

The value of „k‟ in k-fold cross-validation can be set to any number.

However, there are two approaches which are extremely popular:

1. 10-fold cross-validation (10-fold CV)
2. Leave-one-out cross-validation (LOOCV)

​

10-fold cross-validation is by far the most popular approach. In this approach, for each of the 10-folds, each comprising of approximately 10% of the data, one of the folds is used as the test data for validating model performance trained based on the remaining 9 folds (or 90% of the data). This is repeated 10 times, once for each of the 10 folds being used as the test data and the remaining folds as the training data. The average performance across all folds is being reported.

Each of the circles resembles a record in the input data set whereas the different circles indicate the different classes that the records belong to. The entire data set is broken into „k‟ folds – out of which one fold is selected in each iteration as the test data set. The fold selected as test data set in each of the „k‟ iterations is different. The circles resemble the records in the input data set, the contiguous circles represented as folds do not mean that they are subsequent records in the data set. The records in a fold are drawn by using random sampling technique.

​

Leave-one-out cross-validation (LOOCV) is an extreme case of k- fold cross-validation using one record or data instance at a time as a test data. This is done to maximize the count of data used to train the model. It is obvious that the number of iterations for which it has to be run is equal to the total number of data in the input data set. Hence, obviously, it is computationally very expensive and not used much in practice.

3. Bootstrap sampling

• Bootstrap sampling or simply bootstrapping is a popular way to identify training and test data sets from the input data set. It uses the technique of Simple Random Sampling with Replacement (SRSWR), which is a well-known technique in sampling theory for drawing random samples.

​

• Bootstrapping randomly picks data instances from the input data set, with the possibility of the same data instance to be picked multiple times. This essentially means that from the input data set having „n‟ data instances, bootstrapping can create one or more training data sets having

„n‟ data instances, some of the data instances being repeated multiple

times.

​

• This technique is particularly useful in case of input data sets of small size, i.e. having very less number of data instances

Difference between CV and BS

4. Lazy vs. Eager learner

• Eager learning follows the general principles of machine learning – it tries to construct a generalized, input independent target function during the model training phase.
• It follows the typical steps of machine learning, i.e. abstraction and generalization and comes up with a trained model at the end of the learning phase. Hence, when the test data comes in for classification, the eager learner is ready with the model and doesn‟t need to refer back to the training data.
• Eager learners take more time in the learning phase than the lazy learners. Some of the algorithms which adopt eager learning approach include Decision Tree, Support Vector Machine, Neural Network, etc.
• Lazy learning completely skips the abstraction and generalization processes, in context of a typical machine learning process. In that respect, lazy learner doesn’t ‘learn’ anything. It uses the training data in exact, and uses the knowledge to classify the unlabelled test data.

• Since lazy learning uses training data as-is, it is also known as rote learning (i.e. memorization technique based on repetition). Due to its heavy dependency on the given training data instance, it is also known as instance learning. They are also called non-parametric learning.
• Lazy learners take very little time in training because not much of training actually happens. However, it takes quite some time in classification as for each tuple of test data, a comparison-based assignment of label happens. One of the most popular algorithm for lazy learning is k nearest neighbor.

Parametric learning models have finite number of parameters. In case of non-parametric models, the number of parameters is potentially infinite. Models such as Linear Regression and Support Vector Machine, since the coefficients form the learning parameters, they are fixed in size. Hence, these models are clubbed as parametric.

On the other hand, in case of models such as k-Nearest Neighbor (kNN) and decision tree, number of parameters grows with the size of the training data. Hence, they are considered as non-parametric learning models.

MODEL REPRESENTATION AND INTERPRETABILITY

The goal of supervised machine learning is to learn or derive a target function which can best determine the target variable from the set of input variables. A key consideration in learning the target function from the training data is the extent of generalization. This is because the input data is just a limited, specific view and the new, unknown data in the test data set may be differing quite a bit from the training data. Fitness of a target function approximated by a learning algorithm determines how correctly it is able to classify a set of data it has never seen.

1.Underfitting : If the target function is kept too simple, it may not be able to capture the essential nuances and represent the underlying data well. A typical case of underfitting may occur when trying to represent a non-linear data with a linear model . Many times underfitting happens due to unavailability of sufficient training data. Underfitting results in both poor performance with training data as well as poor generalization to test data. Underfitting can be avoided by

1. using more training data
2. reducing features by effective feature selection

2. Overfitting: It refers to a situation where the model has been designed in such a way that it emulates the training data too closely. In such a case, any specific deviation in the training data, like noise or outliers, gets embedded in the model. It adversely impacts the performance of the model on the test data. Overfitting , occur as a result of trying to fit an excessively complex model to closely match the training data.

The target function, in these cases, tries to make sure all training data points are correctly partitioned by the decision boundary. However, this exact nature is not replicated in the unknown test data set. Hence, the target function results in wrong classification in the test data set. Overfitting results in good performance with training data set, but poor generalization and hence poor performance with test data set. Overfitting can be avoided by

1. using re-sampling techniques like k-fold cross validation 2. hold back of a validation data set 3. remove the nodes which have little or no predictive power for the given machine learning problem.

Both underfitting and overfitting result in poor classification quality which is reflected by low classification accuracy.

3. Bias – variance trade-off : In supervised learning, the class value assigned by the learning model built based on the training data may differ from the actual class value. This error in learning can be of two types – errors due to „bias‟ and error due to „variance‟.

Errors due to ‘Bias’ : Errors due to bias arise from simplifying assumptions made by the model to make the target function less complex or easier to learn. In short, it is due to underfitting of the model. Parametric models generally have high bias making them easier to understand/interpret and faster to learn. These algorithms have a poor performance on data sets, which are complex in nature and do not align with the simplifying assumptions made by the algorithm. Underfitting results in high bias and make classification errors when trained using training data

Errors due to ‘Variance’ : Different training data sets (randomly sampled from the input data set) are used to train the model. Ideally the difference in the data sets should not be significant and the model trained using different training data sets should not be too different. So, in case of overfitting, since the model matches the training data, even a small difference in test data gets magnified. Overfitting results in high variance and make classification errors when tested using test data

So, the problems in training a model can happen because either

(a) the model is too simple and hence fails to interpret the data

or

(b) the model is extremely complex and magnifies even small

differences in the training data. From these,

Increasing the bias will decrease the variance, and Increasing the variance

will decrease the bias.

• Parametric algorithms demonstrate high bias but low variance.
• Non-parametric algorithms demonstrate low bias and high

variance.

The best solution is a model with low bias as well as low variance.

However, that may not be possible in reality. Hence, the goal of supervised machine learning is to achieve a balance between bias and variance. The learning algorithm chosen and the user parameters which can be configured is a trade-off between bias and variance. [Ex]: In supervised algorithm k-Nearest Neighbors or kNN, the user configurable parameter „k’ can be used to do a trade-off between bias and variance. In one hand, when the value of „k’ is decreased, the model becomes simpler to fit and bias increases. On the other hand, when the value of ‘k’ is increased, the variance increases.

EVALUATING PERFORMANCE OF A MODEL

To evaluate the model based on ,

1 Supervised learning - classification

2. Supervised learning – regression
3. Unsupervised learning – clustering

​

1 Supervised learning - classification

In classification model, to assign class label to the target feature based

on the value of the predictor features.

[Ex]: The problem of predicting the win/loss in a cricket match, the classifier will assign a class value win/loss to target feature based on the predictor features like whether the team won the toss, number of spinners in the team, number of wins the team had in the tournament, etc.

To evaluate the performance of the model, the number of correct classifications or predictions made by the model has to be recorded. A classification is said to be correct if, say for example in the given problem, it has been predicted by the model that the team will win and it has actually won.

Based on the number of correct and incorrect classifications or predictions made by a model, the accuracy of the model is calculated. There are four possibilities with regards to the cricket match win/loss prediction:

1. the model predicted win and the team won
2. the model predicted win and the team lost
3. the model predicted loss and the team won
4. the model predicted loss and the team lost In this problem, the class of interest is ‘win’.

The first case, i.e. the model predicted win and the team won is a case where the model has correctly classified as the class of interest. These cases are referred as True Positive (TP) cases.

The second case, i.e. the model predicted win and the team lost is a case where the model incorrectly classified as the class of interest. These cases are referred as False Positive (FP) cases.

The third case, i.e. the model predicted loss and the team won is a case where the model has incorrectly classified as not the class of interest. These cases are referred as False Negative (FN) cases.

The fourth case, i.e. the model predicted loss and the team lost is a case where the model has correctly classified as not the class of interest. These cases are referred as True Negative (TN) cases.

Confusion matrix : A matrix containing correct and incorrect predictions in the form of TPs, FPs, FNs and TNs is known as confusion matrix. The win/loss prediction of cricket match has two classes of interest – win and loss. For that , it will generate a 2 × 2 confusion matrix. For a classification problem involving three classes, the confusion matrix would be 3 × 3, etc.

​

Let‟s assume the confusion matrix of the win/loss prediction of cricket match problem to be as below:

In context of the above confusion matrix, total count of TPs = 85,

count of FPs = 4, count of FNs = 2 and count of TNs = 9.

Accuracy: It is given by total number of correct classifications (either the class of interest, i.e. True Positive or not the class of interest, i.e. True Negative) divided by total number of classifications done.

Error Rate : The total number of misclassifications (either the class of interest, i.e. False Positive or not the class of interest, i.e. False Negative) divided by total number of classifications done.

(or) Error Rate : 1- accuracy

Sometimes, correct prediction, both TPs as well as TNs, may happen by coincidence. Since these occurrences boost model accuracy, ideally it should not happen. Kappa value of a model indicates the adjusted the model accuracy. It is calculated using the formula below:

In certain learning problems using classification model, it is critical to have extremely low number of FN cases is needed. Though it is a .case of misclassification and will impact model accuracy. This happens more in problems from medical domains like disease prediction problem.

[Ex]: if a tumor is malignant but wrongly classified as benign by the classifier, then such misclassification is fatal. It does not matter if tumours which are benign are wrongly classified as malignant.

So, for these problems there are some measures of model performance which are more important than accuracy. Two such critical measurements are sensitivity and specificity of the model.

Sensitivity : The proportion of TP cases to the total of TP and FN cases. (or) the ratio of actual(positive) cases to predicted as actual(positive) cases.

​

Specificity: The proportion of TN cases to the total of TN and FP cases. (or) the ratio of actual(negative) cases to predicted as actual(negative) cases.

There are two other performance measures of a supervised learning model which are similar to sensitivity and specificity. These are precision and recall. While precision gives the proportion of positive predictions which are truly positive, recall gives the proportion of TP cases over all actually positive cases.

F-measure : It is another measure of model performance which combines the precision and recall. It takes the harmonic mean of precision and recall as calculated as

Problem 1: Suppose a computer program for recognizing dogs in photographs identifies 8 dogs in a picture containing 12 dogs and some cats. In the 8 dogs identified, five actually are dogs while the rest are cats. calculate the Precision and recall of the computer program.

Solution:

Confusion Matrix

Assume Positive sample as dogs

Precision : TP/(TP+FP) = 5/8 Recall : TP/(TP+FN) = 5/12

Problem2 : Let there be 10 balls (6 white and 4 red balls) in a box and let it be required to pick up the red balls from them. Suppose we pick up 7 balls as the red balls, of which only 2 are actually red balls. what are the values of Precision and recall in picking red balls .

Solution: Confusion Matrix

Assume Positive sample as red balls

Precision : TP/(TP+FP) = 2/7

Recall : TP/(TP+FN) = 2/4

Problem 3: Suppose 10000 patients get tested for a flu . Out of them 9000 are actually healthy and 1000 are actually sick. For the sick people, a test was positive for 620 and negative for 380 . For healthy people the same test was positive for 180 and negative for 8820. Construct a confusion Matrix for the data and compute accuracy, Precision and recall for the data.

Solution: Confusion Matrix

Assume Positive sample as sick people

Accuracy : TP+TN/(TP+TN+FP+FN) = 620+8820/10000=0.944

Precision : TP/(TP+FP) = 620/800 = 0.775 Recall : TP/(TP+FN) = 620/1000=0.62

Exercise Problem: While predicting malignancy of tumour of a set of

patients using a classification model, following are the data recorded:

1. Correct predictions – 15 malignant, 75 benign
2. Incorrect predictions – 3 malignant, 7 benign

Calculate the error rate, Kappa value, sensitivity, precision, and F-

measure of the model.

Solution:

Confusion Matrix

Assume Positive sample as malignant

Receiver operating characteristic (ROC) curves

Accuracy is the most popular measure, there are quite a number of other measures to evaluate the performance of a supervised learning model. However, visualization is an easier and more effective way to understand the model performance. It also helps in comparing the efficiency of two models.

Receiver Operating Characteristic (ROC) curve helps in visualizing

the performance of a classification model at all threshold levels.

The curve plots two parameters:

• True Positive Rate(TPR)
• False Positive Rate(FPR)

True Positive Rate(TPR) or Recall or Sensitivity : It is the fraction of

positive examples correctly classified. So, TPR = TP/(TP+FN)

​

False Positive Rate(FPR) : It is the fraction of negative examples incorrectly classified. So, FPR = FP/(FP+TN)

To draw ROC curve , plot the values of FPR in x-axis and values of TPR in y-axis.

Special points in ROC space:

(0,0) - Always negative prediction (1,0) – Wrong prediction

(0,1) - Perfect prediction

(1,1) - Always positive prediction

Case1: (0,0) means FPR=0, TPR=0;

FPR = FP/(FP+TN) 🡪 FP=0 means No negative sample is predicted as +ve. TPR = TP/(TP+FN)🡪 TP=0 means No positive sample is predicted as +ve. So, it always perform negative prediction.

Case2: (1,1) means FPR=1, TPR=1;

FPR = FP/(FP+TN) 🡪 TN=0 means No negative sample is predicted as -ve. TPR = TP/(TP+FN)🡪 FN=0 means No positive sample is predicted as -ve. So, it always perform positive prediction.

Case3: (0,1) means FPR=0, TPR=1;

FPR = FP/(FP+TN) 🡪 FP=0 means No negative sample is predicted as +ve. TPR = TP/(TP+FN)🡪 FN=0 means No positive sample is predicted as -ve. So, it always perform perfect prediction.

Case4: (1,0) means FPR=1, TPR=0;

FPR = FP/(FP+TN) 🡪 TN=0 means No negative sample is predicted as -ve. TPR = TP/(TP+FN)🡪 TP=0 means No positive sample is predicted as +ve. So, it always perform worst prediction.

Problem : Construct ROC curve and Compute AUC for the data.

Solution : Find TPR and FPR for all threshold.

The prediction of target features of categorical value are known as classification models.

The target feature is known as a class and the categories to which classes are divided into are called levels.

Some of the popular classification models include k-Nearest Neighbor (kNN), Naïve Bayes, and Decision Tree.

​

Prediction of the numerical value of the target feature of a data instance are known as regression models.

Linear Regression and Logistic Regression models are popular regression models.

Supervised learning – regression

A well-fitted regression model is, predicted values close to actual values. Hence, a regression model which ensures that the difference between predicted and actual values is low can be considered as a good model. A very simple problem of real estate value prediction solved using linear regression model.

If area is the predictor variable (say x) and value is the target variable

(say y), the linear regression model can be represented in the form:

y = α + βx

Residual Value : For a certain value of x, say x^̂ , the value of y is predicted as ŷ whereas the actual value of y is Y . The distance between the actual value y and the predicted value ŷ , is known as residual. The regression model can be considered to be fitted well if the difference between actual and predicted value, i.e. the residual value is less.

R-squared Value : It is used to evaluate the model fitness. It is also known as the coefficient of determination, or for multiple regression, the coefficient of multiple determination. The R-squared value lies between 0 to 1 (0%–100%) with a larger value representing a better fit. It is calculated as

3. Unsupervised learning - Clustering

The two challenges in the process of clustering:

1. Not known how many clusters can be formulated from a particular data set.
2. Even if the number of clusters is given, the same number of clusters can be formed with different groups of data instances.

​

[Ex]: if clustering is applied for identifying customer segments for a marketing campaign of a new product launch, the clustering can be considered successful only if the marketing campaign ends with a success.

There are two popular approaches which are adopted for cluster quality

evaluation.

1. Internal evaluation 2. External evaluation

1. Internal evaluation : The internal evaluation methods generally measure cluster quality based on homogeneity of data belonging to the same cluster and heterogeneity of data belonging to different clusters. The homogeneity/heterogeneity is decided by some similarity measure.

For example, silhouette coefficient, which is one of the most popular internal evaluation methods, uses distance (Euclidean or Manhattan distances most commonly used) between data elements as a similarity measure. The value of silhouette width ranges between –1 and +1, with a high value indicating high intra cluster homogeneity and inter cluster heterogeneity. For a data set clustered into k clusters, silhouette width is calculated as:

2. External evaluation: In this approach, class label is known for the data set subjected to clustering.

However, the known class labels are not a part of the data used in clustering. The cluster algorithm is assessed based on how close the results are compared to those known class labels.

For example, purity is one of the most popular measures of cluster algorithms – evaluates the extent to which clusters contain a single class. For a data set having n data instances and c known class labels which generates k clusters, purity is measured as:

IMPROVING PERFORMANCE OF A MODEL

To improve model performance by applying two different methods.

1. Model parameter tuning
2. Ensemble method – Different types
1. bootstrap aggregating or bagging
2. boosting - Adaptive boosting or AdaBoost
3. Random Forest

​

Model parameter tuning: It is the process of adjusting the model fitting options. For example, in the popular classification model k-Nearest Neighbour (kNN), using different values of k or the number of nearest neighbours to be considered, the model can be tuned. In the same way, a number of hidden layers can be adjusted to tune the performance in neural networks model. Most machine learning models have at least one parameter which can be tuned.

Ensemble method :

To increase the performance of one model, several models may be combined together.

This approach of combining different models with diverse strengths is known as ensemble.

Ensemble helps in averaging out biases of the different underlying models and also reducing the variance.

Ensemble methods combine weaker learners to create stronger ones.

A performance boost can be expected even if models are built as usual and then ensembled.

​

Following are the typical steps in ensemble process:

• Build a number of models based on the training data
• For diversifying the models generated, the training data subset can be varied using the allocation function. Sampling techniques like bootstrapping may be used to generate unique training data sets.
• Alternatively, the same training data may be used but the models combined are quite varying, e.g, SVM, neural network, kNN, etc.
• The outputs from the different models are combined using a combination function.
• A very simple strategy of combining, say in case of a prediction task using ensemble, can be majority voting of the different models combined. For example, 3 out of 5 classes predict win and 2 predict loss - then the final outcome of the ensemble using majority vote would be a

win

Bootstrap aggregating or Bagging

Boosting is an ensemble learning method that combines a set of weak learners into a strong learner to minimize training errors.

The bagging technique combines multiple models trained on different subsets of data, whereas boosting trains the model sequentially, focusing on the error made by the previous model.

1. Bootstrap aggregating or Bagging: Bagging uses bootstrap sampling method to generate multiple training data sets. These training data sets are used to generate (or train) a set of models using the same learning algorithm. Then the outcomes of the models are combined by majority voting (classification) or by average (regression). Bagging is a very simple ensemble technique which can perform really well for unstable learners like a decision tree, in which a slight change in data can impact the outcome of a model significantly.

​

• Boosting : In this type of ensemble, weaker learning models are trained on resampled data and the outcomes are combined using a weighted voting approach based on the performance of different models. Adaptive boosting or AdaBoost is a special variant of boosting algorithm. It is based on the idea of generating weak learners and slowly learning

​

• Random forest: It is an ensemble of decision trees – hence the name random forest to indicate a forest of decision trees.

Feature Engineering

What is feature engineering? :

​

• Process of translating a data set into features
• These features are able to represent the data set more

effectively

• Result in a better learning performance.

​

Feature engineering is an important pre-processing step for machine learning.

​

It has two major 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.

There are two variants of feature transformation

1. feature construction
2. feature extraction

Both are sometimes known as feature discovery.

​

Feature construction process: It discovers missing information about the relationships between features and augments the feature space by creating additional features. Hence, if there are n features or dimensions in a data set, after feature construction m more features or dimensions may get added. So at the end, the data set will become n + m dimensional.

​

Feature extraction process: It extract or create a new set of features from the original set of features using some functional mapping.

FEATURE TRANSFORMATION

There are two distinct goals of feature transformation:

1. Achieving best reconstruction of the original features in the data set
2. Achieving highest efficiency in the learning task

​

Feature construction: It involves transforming a given set of input features to generate a new set of more powerful features.

​

[Ex]: A real estate data set having details of all apartments sold in a specific region.

The data set has three features – apartment length, apartment breadth, and price of the apartment.

If it is used as an input to a regression problem, such data can be training data for the regression model.

So given the training data, the model should be able to predict the price of an apartment.

Instead of using length and breadth of the apartment as a predictor, it is much convenient and makes more sense to use the area of the apartment, which is not an existing feature of the data set. So such a feature, namely apartment area, can be added to the data set. so, transform the three- dimensional data set to a four-dimensional data set, with the newly discovered feature apartment area being added to the original data set.

There are certain situations where feature construction is an essential

activity before start with the machine learning task. These situations are

• when features have categorical(Both nominal and ordinal) 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 : Any machine learning algorithm, whether it is a classification algorithm (like kNN) or a regression algorithm, requires numerical figures to learn from. Feature construction can be used to create new dummy features which are usable by machine learning algorithms. The dummy features have value 0 or 1 based on the categorical value for the original feature in that row. When creating dummy features, there is a chance for duplication and the value of one feature can be decided from the value of the other. To avoid this duplication, take one feature and eliminate the other.

[Ex]: A data set on athletes, and the data set has features age, city of origin, parents athlete (i.e. indicate whether any one of the parents was an athlete) and Chance of Win. The feature chance of a win is a class variable while the other features are predictor variables.

Original dataset

Creating Dummy features: The feature „City of origin‟ has three unique values namely City A, City B, and City C, three dummy features namely origin_ city_A, origin_city_B, and origin_city_C is created. In the same way, dummy features parents_athlete_Y and parents_athlete_N are created for feature Parents athlete and win_chance_Y and win_chance_N are created for feature Chance of win.

Encoding categorical (ordinal) variable: To transform ordinal variable to a numeric variable, create a new feature for ordinal feature and mapping a numeric value against each ordinal value.

[Ex]: A student data set and there are three variable – science marks, maths marks and grade . The grade is an ordinal variable with values A, B, C, and D. To transform this variable to a numeric variable, create a feature num_grade mapping a numeric value against each ordinal value. So, grades A, B, C, and D is mapped to values 1, 2, 3, and 4 in the transformed variable

Transforming numeric (continuous) features to categorical features: Sometimes there is a need of transforming a continuous numerical variable into a categorical variable. So, bin the numerical data into multiple categories based on the data range.

[Ex] A estate data set has a numerical feature apartment_price. If it is a real estate price prediction, which is a regression problem (or) real estate price category prediction, which is a classification problem.

Text-specific feature construction: In the current world, text is the most predominant medium of communication. The social networks like Facebook, Twitter , emails or Whatsapp, text plays a major role in the flow of information. Hence, text mining is an important area of research. Text data is in the form of unstructured data.(ie)

1. Text data do not have readily available features, like structured data sets, on which machine learning tasks can be executed.
2. 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, or corpus which is the more popular keyword, is converted to a numerical representation following a process is known as vectorization. In this process, word occurrences in all documents belonging to the corpus are consolidated in the form of bag-of-words. There are three major steps that are followed in vectorization :

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.

• Then the number of occurrences of each token is counted, for each

document.

• Lastly, 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 extraction : New features are created from a combination of original features. Some of the 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.

[Ex]: A data set with a feature set F_i (F₁ , F₂ , …, F_n ). After feature extraction using a mapping function f (F₁ , F₂ , …, F_n ) have a set of features

The eigenvalue is

which, when multiplied by a nonzero vector, equals to the vector

obtained by transformation operating on the vector.

Let us consider k x k square matrix A and v be a vector, then λ is a scalar

quantity represented in the following way:

AV = λV

AV =λIV

where λ is considered to be the eigenvalue of matrix A.

Where “I” is the identity matrix of the same order as A

Eigenvalues and Eigen Vectors

a scalar associated with a linear set of equations

The above equation can also be written as:

(A – λI)V = 0 (or) (A – λI) =0.

​

This equation can be represented in the determinant of matrix form.

| (A – λI) |=0

The above relation enables us to calculate eigenvalues λ easily.

Steps to Find Eigenvalues of a Matrix

In order to find the eigenvalues of a matrix, follow the steps below:

Step 1: Make sure the given matrix A is a square matrix. Also, determine

the identity matrix I of the same order.

Step 2: Estimate the matrix A – λI, where λ is a scalar quantity.

Step 3: Find the determinant of matrix A – λI and equate it to zero.

Step 4: From the equation thus obtained, calculate all the possible values of λ, which are the required eigenvalues of matrix A.

How to Find an Eigenvector?

Step1: Find the eigenvalues of the given matrix A, using the equation det ((A – λI) =0, where “I” is identity matrix as A. Denote each eigenvalue of λ₁, λ₂, λ₃….

Step2: Substitute the values in the equation AX = λ₁ or (A – λ₁ I) X = 0. Step3: Calculate the value of eigenvector X, which is associated with the eigenvalue.

Step4: Repeat the steps to find the eigenvector for the remaining eigenvalues.

y = -x means if x=1 then y=-1

​

Therefore the eigen vectors are

Most popular feature extraction algorithms used in machine learning

1. Principal Component Analysis(PCA)
2. Singular value decomposition (SVD)
3. Linear discriminant analysis (LDA)

​

Principal Component Analysis(PCA) : Every data set has multiple attributes or dimensions – many of which might have similarity with each other. In general, any machine learning algorithm performs better as the number of related attributes or features reduced. In other words, 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. This is the main guiding philosophy of principal component analysis (PCA) technique of feature extraction.

In PCA, a new set of features are extracted from the original features which are quite dissimilar in nature. So 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.

The objective of PCA is to make the transformation in such a way that

1. The new features are distinct, i.e. the covariance between the new features, i.e. the principal components is 0.
2. The principal components are generated in order of the variability in the data that it captures. Hence, the first principal component should capture the maximum variability, the second principal component should capture the next highest variability etc.
3. The sum of variance of the new features of the principal components should be equal to the sum of variance of the original features.

​

PCA works based on a process called eigen value decomposition of a covariance matrix of a data set.

Below are the steps to be followed:

1. First, calculate the covariance matrix of a data set.
2. Then, calculate the eigenvalues of the covariance matrix.
3. The eigenvector having highest eigenvalue represents the direction in which there is the highest variance. So this will help in identifying the first principal component.

4. 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. So this helps in identifying the second principal component.
5. Like this, identify the top k eigenvectors having top , k eigenvalues so as to get the k principal components.

Problem: Apply PCA technique to reduce the two dimension data

into one dimension for the given data set.

Step1 : Find n,N from dataset

Step 2: Compute mean for each feature or variable Step3: Compute Covariance matrix (S)

Step4: Find Eigen value(λ), Eigen vector(U) and Normalized Eigen vector (e) from Covariance matrix (S)

Step5: Derive new dataset that contain PCA values

Singular value decomposition

Singular value decomposition (SVD) is 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 are orthonormal matrices, U is an m × m unitary matrix, V is an n × n unitary matrix and ∑ 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.

SVD of a data matrix is expected to have the properties:

1. Patterns in the attributes are captured by the right-singular vectors, i.e.

the columns of V.

2. Patterns among the instances are captured by the left-singular, i.e. the

columns of U.

3. Larger a singular value, larger is the part of the matrix A that it accounts for and its associated vectors.
4. New data matrix with „k‟ attributes is obtained using the equation D = D

× [v₁ , v₂ , … , v_k ] Thus, the dimensionality gets reduced to k .

Linear Discriminant Analysis

Linear discriminant analysis (LDA) is another commonly used feature

extraction technique like PCA or SVD.

The objective of LDA is, to transform a data set into a lower dimensional

feature space.

However, 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.

Unlike PCA that calculates eigenvalues of the covariance matrix of the data set, LDA calculates eigenvalues and eigenvectors within a class and inter class scatter matrices.

The steps to be followed:

1. Calculate the mean vectors for the individual classes.
2. Calculate intra-class and inter-class scatter matrices.
3. Calculate eigenvalues and eigenvectors for S_W and S_B , where S_W is

the intra-class scatter matrix and S_B is the inter-class scatter matrix

4. Find Y = V^T X where V^T is the projection vector and X is the data

point

FEATURE SUBSET SELECTION

Feature selection is the most critical preprocessing activity in any machine learning project. It intends to select a subset of system attributes or features which makes a most meaningful contribution in a machine learning activity.

[Ex]: The student weight data set has features such as Roll Number, Age, Height, and Weight. It is understand that roll number can not have any effect in predicting student weight. So eliminate the feature roll number and build a feature subset to be considered in this machine learning problem. The subset of features is expected to give better results than the full set.

Understand the issues in feature selection

Issues in high-dimensional data: The two new application domains

1. biomedical research generates data sets having a number of features in

the range of a few tens of thousands.

2. The text data generated from different sources from social

Networking sites, emails, etc. also have extremely high dimensions. such high-dimensional data is a big challenge for any machine learning algorithm. High quantity of computational resources and high amount of time will be required. The performance of the model – both supervised and unsupervised machine learning task, also degrades due to unnecessary noise in the data. Also, a model built on an extremely high number of features may be very difficult to understand. For this reason, it is necessary to take a subset of the features instead of the full set.

The objective of feature selection is three-fold:

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

resources) learning model

2. Improving the efficiency of the learning model
3. 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. A model is based on the training data set – so that the model can assign class labels to new, unlabelled data. 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.

Any feature which is irrelevant in the context of a machine learning task is a attribute for rejection when selecting a subset of features. Consider whether the weakly relevant features are to be rejected or not on a case-to-case basis.

​

Feature redundancy: The main objective of feature selection is to remove all features which are irrelevant and take subset of the features which are potentially redundant.

​

How to find out which of the features are irrelevant or which features have potential redundancy ?

Measures of feature relevance and redundancy Measures of feature relevance: 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. Mutual information can be calculated as follows:

MI(C, f ) = H(C) + H( f ) - H(C, f )

Where K = number of classes, C = class variable, f = feature set that take discrete values.

In case of unsupervised learning, the entropy of the set of features without one feature at a time is calculated for all the features. Then, the features are ranked in a descending order of information gain from a feature and top „β‟ percentage (value of „β‟ is a design parameter of the algorithm) of features are selected as relevant features. The entropy of a feature f is calculated using Shannon‟s formula below:

Measures of Feature redundancy

Feature redundancy is based on similar information contribution by multiple features. There are multiple measures of similarity of information contribution, salient ones being

1. Correlation-based measures
2. Distance-based measures
3. Other coefficient-based measure

1.Correlation-based measures: 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 F₁ and F₂ , 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.

2. Distance-based similarity measure: The most common distance measure is the Euclidean distance, which, between two features F₁ and F₂ are calculated as:

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.

Let‟s consider two features F and F having values (0,1, 1, 0, 1, 0, 1, 0)

and (1, 1, 0, 0, 1, 0, 0, 0).

Cosine Similarity: Let‟s take the example of a typical text classification problem. The text corpus needs to be first transformed into features with a word token being a feature and the number of times the word occurs in a document comes as a value in each row. There are thousands of features in such a text data set. However, the data set is sparse in nature as only a few words do appear in a document, and hence in a row of the data set. So each row has very few non-zero values. However, the non- zero values can be anything integer value as the same word may occur any number of times. Also, considering the sparsity of the data set, the 0-

0 matches (which obviously is going to be pretty high) need to be ignored. Cosine similarity which is one of the most popular measures in text classification is calculated as:

Jaccard Index

Overall feature selection process

Feature selection is the process of selecting a subset of features in a data set. A typical feature selection process consists of four steps:

1. generation of possible subsets
2. subset evaluation
3. stop searching based on some stopping criterion
4. validation of the result

Subset generation, which is the first step of any feature selection algorithm, is a search procedure which ideally should produce all possible candidate subsets. However, for an n-dimensional data set, 2ⁿ subsets can be generated. So, as the value of „n‟ becomes high, finding an optimal subset from all the 2ⁿ candidate subsets becomes intractable.

For that reason, different approximate search strategies are employed to

find candidate subsets for evaluation.

The search may start with an empty set and keep adding features. This

search strategy is termed as a sequential forward selection. (or)

The 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. This cycle of subset generation and evaluation continues till a pre-defined stopping criterion is fulfilled.

Some commonly used stopping criteria are

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.

​

​

Then 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. The accuracy of the model using the subset derived is compared against the model accuracy of the subset derived using some other benchmark algorithm. In case of unsupervised, the cluster quality may be the parameter for validation.

Feature selection approaches

There are four types of approach for feature selection:

1. Filter approach

3. Hybrid approach

2.Wrapper approach

4. Embedded approach

1.Filter approach: The feature subset is selected based on statistical measures on the features. No learning algorithm is employed to evaluate the goodness of the feature selected. Some of the common statistical tests conducted on features as a part of filter approach are – Pearson‟s correlation, information gain, Fisher score, analysis of variance (ANOVA), Chi-Square, etc.

2.Wrapper approach: Identification of best feature subset is done using the induction algorithm as a black box. The feature selection algorithm searches for a good feature subset using the induction algorithm itself as a part of the evaluation function. Since for every candidate subset, the learning model is trained and the result is evaluated by running the learning algorithm, wrapper approach is computationally very expensive. However, the performance is generally superior compared to filter approach.

3. Hybrid approach: It 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.
4. Embedded approach: It is quite similar to wrapper approach as it also uses and inductive algorithm to evaluate the generated feature subsets. However, the difference is it performs feature selection and classification simultaneously.

Solved Problems

1. Given two objects represented by the tuples (22, 1, 42, 10) and (20, 0, 36, 8):

1. Compute the Euclidean distance between the two objects.
2. Compute the Manhattan distance between the two objects.
3. Compute the Minkowski distance between the two objects, use r = 3.

​

a). Euclidean distance = √ (22 − 20)² + (1 − 0)² + (42 − 36)² + (10 − 8)²

= √ 45 = 6.7082.

​

(b) Manhattan distance = |22 − 20| + |1 − 0| + |42 − 36| + |10 − 8| = 11.

​

(c) Minkowski distance , using r = 3.

The Minkowski disance is d(i, j) = ³√ |22 − 20| ³ + |1 − 0| ³ + |42 −

36| ³ + |10 − 8| ³ = ³ √233 = 6.1534

Find the cosine similarity measure for the first two terms. x =(5, 0, 3, 0,

2, 0, 0, 2, 0,0) and y =(3, 0, 2, 0, 1, 1, 0, 1, 0,1).

Problems

Ex1: Two rows in a document-term matrix have values - (2, 3, 2, 0, 2, 3,

3, 0, 1) and (2, 1, 0, 0, 3, 2, 1, 3, 1). Find the cosine similarity.

​

Ex2: Find the Hamming distance between 10001011 and 11001111.

​

Ex3: Compare the Jaccard index and similarity matching coefficient of

two features having values (1, 1, 0, 0, 1, 0, 1, 1) and (1, 0, 0, 1, 1, 0, 0, 1)

Problem: Apply PCA technique to reduce the four dimension data

into two dimension for the given data set.

https://www.turing.com/kb/guide-to-principal-component-analysis