1)i.

Distinguish between Locally Weighted Regression (LWR) and Linear

Regression
Locally Weighted Regression (LWR) Linear Regression

Locally Weighted Regression (LWR) is a non-

parametric supervised learning algorithm that In the simplest form, the linear regression model can be created
performs local regression by combining regression by fitting a line among the scattered data points.
model with nearest neighbor’s model.

LWR is also referred to as a memory-based method as

it requires training data while prediction but uses only The idea of linear regression is based on Ordinary Least Square
the training data instances locally around the point of (OLS) approach.
interest.

Using nearest neighbors algorithm, we find the

instances that are closest to a test instance and fit In this method, the data points are modelled using a straight
linear function to each of those ‘K’ nearest instances in line.
the local regression model.

The key idea is that we need to approximate the linear

functions of all ‘K’ neighbors that minimize the error Ordinary linear regression finds out a linear relationship between
such that the prediction line is no more linear but the input x and the output y.
rather it is a curve.

The cost function is modified for locally weighted

The regression line is the line of best fit for which the sum of
linear regression including the weights only for the
the squares of residuals is minimum.
nearest neighbor points.

The weight function used is a Gaussian kernel that

gives a higher value for instances that are close to the
Linear regression is modelled as a minimization function.
test instance, and for instances far away, it tends to
zero but never equals to zero.

ii. Distinguish between Multiple Linear Regression and Logistic Regression

Multiple Linear Regression Logistic Regression

Multiple regression model involves multiple predictors or Logistic regression is suitable for binary classification
independent variables and one dependent variable. problem.

Linear regression predicts the numerical response but is not

suitable for predicting the categorical variables. When
This is an extension of the linear regression problem.
categorical variables are involved, it is called classification
problem.

The basic assumptions of multiple linear regression are

that the independent variables are not highly correlated Here, the output is often a categorical variable.
and hence multicollinearity problem does not exist.

Also, it is assumed that the residuals are normally Logistic regression is used as a binary classifier and works by
distributed. predicting the probability of the categorical variable.

For example, the multiple regression of two variables x₁ In general, it takes one or more features x and predicts the
Multiple Linear Regression Logistic Regression

and x₂ is given as: y = f(x₁,x₂) = a₀ + a₁x₁ + a₂x₂ response y.

In general, this is given for ‘n’ independent variables as: y Logistic regression tries to model the probability of the
= f(x₁,x₂,x₃,...,xₙ) = a₀ + a₁x₁ + a₂x₂ + ... + aₙxₙ + ε particular response variable.

(x₁, x₂, ..., xₙ) are predictor variables, y is the dependent Linear regression generated value is in the range −∞ to +∞,
variable, (a₀, a₁, ..., aₙ) are the coefficients of the whereas the probability of the response variable ranges
regression equation and ε is the error term. between 0 and 1.

Predicts a numerical response. Predicts probability / categorical response variable.

2)
The class is predicted as “fail”
3) Make use of entropy and information gain to discover the root node for
the decision tree for the following dataset using ID3 algorithm
4) 6.1.1 Structure of a Decision Tree
• A decision tree has a structure that consists of a root node, internal nodes/decision nodes, branches, and
terminal nodes/leaf nodes.

• The topmost node in the tree is the root node.

• Internal nodes are the test nodes and are also called as decision nodes.

• These nodes represent a choice or test condition of an input attribute and the outcome or outputs of the test
condition are the branches emanating from this decision node.

• The branches are labelled as per the outcomes or output values of the test condition.

• Each branch represents a sub-tree or subsection of the entire tree.

• Every decision node is part of a path to a leaf node.

• The leaf nodes represent the labels or the outcome of a decision path.

• The labels of the leaf nodes are the different target classes a data instance can belong to.
 • Every path from root to a leaf node represents a logical rule that corresponds to a conjunction test attributes
and the whole tree represents a disjunction of these conjunctions.

• The decision tree model, in general, represents a collection of logical rules of classification in the form of a tree
structure.

• Decision networks, otherwise called as influence diagrams, have a directed graph structure with nodes and
links.

• It is an extension of Bayesian belief networks that represents information about each node's current state, its
possible actions, the possible outcome of those actions, and their utility.

• The concept of Bayesian Belief Network (BBN) is discussed in Chapter 9.

Symbols used in Decision Tree

• A circle is used to represent a root node.

• A diamond symbol is used to represent a decision node or the internal nodes.

• All leaf nodes are represented with a rectangle.

A Decision Tree Consists of Two Major Procedures

1. Building the Tree

Goal

• Construct a decision tree with the given training dataset.

• The tree is constructed in a top-down fashion.

• It starts from the root node.

• At every level of tree construction, we need to find the best split attribute or best decision node among all
attributes.

• This process is recursive and continued until we end up in the last level of the tree or finding a leaf node
which cannot be split further.

• The tree construction is complete when all the test conditions lead to a leaf node.

• The leaf node contains the target class or output of classification.

Output

• Decision tree representing the complete hypothesis space.

2. Knowledge Inference or Classification

Goal

• Given a test instance, infer to the target class it belongs to.

Classification

• Inferring the target class for the test instance or object is based on inductive inference on the constructed
decision tree.

• In order to classify an object, we need to start traversing the tree from the root.
 • We traverse as we evaluate the test condition on every decision node with the test object attribute value and
walk to the branch corresponding to the test’s outcome.

• This process is repeated until we end up in a leaf node which contains the target class of the test object.

Output

• Target label of the test instance.

Advantages of Decision Trees

1. Easy to model and interpret.

2. Simple to understand.

3. The input and output attributes can be discrete or continuous predictor variables.

4. Can model a high degree of nonlinearity in the relationship between the target variables and the predictor
variables.

5. Quick to train.

Disadvantages of Decision Trees

1. It is difficult to determine how deeply a decision tree can be grown or when to stop growing it.

2. If training data has errors or missing attribute values, then the decision tree constructed may become unstable
or biased.

3. If the training data has continuous valued attributes, handling it is computationally complex and has to be
discretized.

4. A complex decision tree may also be over-fitting with the training data.

5. Decision tree learning is not well suited for classifying multiple output classes.

6. Learning an optimal decision tree is also known to be NP-complete.

Regular Paper
2) Types of Regression Methods
The classification of regression methods is shown in Figure 5.3.

Regression Methods

1. Linear Regression Methods

• Single linear regression

• Multiple linear regression

2. Non-linear Regression

• Polynomial regression

3. Logical Regression
Linear Regression

• It is a type of regression where a line is fitted upon given data for finding the linear relationship between one
independent variable and one dependent variable to describe relationships.

Multiple Regression

• It is a type of regression where a line is fitted for finding the linear relationship between two or more
independent variables and one dependent variable to describe relationships among variables.

Polynomial Regression

• It is a type of non-linear regression method of describing relationships among variables where Nᵗʰ degree
polynomial is used to model the relationship between one independent variable and one dependent variable.

• Polynomial multiple regression is used to model two or more independent variables and one dependent
variable.

Logistic Regression

• It is used for predicting categorical variables that involve one or more independent variables and one
dependent variable.

• This is also known as a binary classifier.

Lasso and Ridge Regression Methods

• These are special variants of regression method where regularization methods are used to limit the number
and size of coefficients of the independent variables.

Limitations of Regression Method

1. Outliers

• Outliers are abnormal data.

• It can bias the outcome of the regression model, as outliers push the regression line towards it.

2. Number of Cases

• The ratio of independent and dependent variables should be at least 20 : 1.

• For every explanatory variable, there should be at least 20 samples.

• Atleast five samples are required in extreme cases.

3. Missing Data

• Missing data in training data can make the model unfit for the sampled data.

4. Multicollinearity

• If explanatory variables are highly correlated (0.9 and above), the regression is vulnerable to bias.

• Singularity leads to perfect correlation of 1.

 • The remedy is to remove explanatory variables that exhibit correlation more than 1.

• If there is a tie, then the tolerance (1 − R squared) is used to eliminate variables that have the greatest value.

3) Structure of a Decision Tree

• A decision tree has a structure that consists of a root node, internal nodes/decision nodes, branches, and
terminal nodes/leaf nodes.

• The topmost node in the tree is the root node.

• Internal nodes are the test nodes and are also called as decision nodes.

• These nodes represent a choice or test condition of an input attribute and the outcome or outputs of the test
condition are the branches emanating from this decision node.

• The branches are labelled as per the outcomes or output values of the test condition.

• Each branch represents a sub-tree or subsection of the entire tree.

• Every decision node is part of a path to a leaf node.

• The leaf nodes represent the labels or the outcome of a decision path.

• The labels of the leaf nodes are the different target classes a data instance can belong to.

• Every path from root to a leaf node represents a logical rule that corresponds to a conjunction test attributes
and the whole tree represents a disjunction of these conjunctions.

• The decision tree model, in general, represents a collection of logical rules of classification in the form of a tree
structure.

• Decision networks, otherwise called as influence diagrams, have a directed graph structure with nodes and
links.

• It is an extension of Bayesian belief networks that represents information about each node's current state, its
possible actions, the possible outcome of those actions, and their utility.

• The concept of Bayesian Belief Network (BBN) is discussed in Chapter 9.

Symbols used in Decision Tree

• A circle is used to represent a root node.

• A diamond symbol is used to represent a decision node or the internal nodes.

• All leaf nodes are represented with a rectangle.

Procedure to Construct a Decision Tree

Building the Tree

Goal

• Construct a decision tree with the given training dataset.

• The tree is constructed in a top-down fashion.

• It starts from the root node.

 • At every level of tree construction, we need to find the best split attribute or best decision node among all
attributes.

• This process is recursive and continued until we end up in the last level of the tree or finding a leaf node
which cannot be split further.

• The tree construction is complete when all the test conditions lead to a leaf node.

• The leaf node contains the target class or output of classification.

Output

• Decision tree representing the complete hypothesis space.

Knowledge Inference or Classification

Goal

• Given a test instance, infer to the target class it belongs to.

Classification

• Inferring the target class for the test instance or object is based on inductive inference on the constructed
decision tree.

• In order to classify an object, we need to start traversing the tree from the root.

• We traverse as we evaluate the test condition on every decision node with the test object attribute value and
walk to the branch corresponding to the test’s outcome.

• This process is repeated until we end up in a leaf node which contains the target class of the test object.

Output

• Target label of the test instance.

Example 6.1: How to draw a decision tree to predict a student’s academic performance

Target Feature

• The target feature is the student performance in the final examination whether he will pass or fail in the
examination.

Decision Nodes

The decision nodes are test nodes which check for conditions like:

• What’s the student’s class attendance?

• How did he perform in his class assignments?

• Did he do his home assignments properly?

• What about his assessment results?

• Did he participate in competitions or other events?

• What is the performance rating in group activities such as projects and presentations?

Table 6.1: Attributes and Associated Values

Attributes Values

Class attendance Good, Average, Poor

Class assignments Good, Moderate, Poor

Home-work assignments Yes, No

Assessment Good, Moderate, Poor

Participation in competitions or other events Yes, No

Group activities such as projects and presentations Yes, No

Exam Result Pass, Fail

Leaf Nodes

• The leaf nodes represent the outcomes, that is, either ‘pass’, or ‘fail’.

Construction

• A decision tree would be constructed by following a set of if-else conditions which may or may not include all
the attributes, and decision node outcomes are two or more than two.

• Hence, the tree is not a binary tree.

Note

• A decision tree is not always a binary tree.

• It is a tree which can have more than two branches.

Example 6.2: Predict a student’s academic performance whether he will pass or fail

Table 6.2: Attributes and Associated Values

Attributes Values

Assessment ≥50, <50

Assignment Yes, No

Exam Result Pass, Fail

Procedure

• Consider the root node is ‘Assessment’.

• If a student’s marks are ≥50, the root node is branched to leaf node ‘Pass’.

• If the assessment marks are <50, it is branched to another decision node.

• If the decision node in next level of the tree is ‘Assignment’ and if a student has submitted his assignment, the
node branches to ‘Pass’ and if not submitted, the node branches to ‘Fail’.
 •
Logical Rules

• if (Assessment > 50) then ‘Pass’

• else if (Assessment < 50) then

o if (Assignment = Yes) then ‘Pass’

o else if (Assignment = No) then ‘Fail’

Procedure to Construct a Decision Tree using ID3 Algorithm

Not found in the provided content.

The uploaded pages contain:

• Structure of a Decision Tree

• Building the Tree

• Knowledge Inference or Classification

• Example 6.1

• Example 6.2

But they do not contain the ID3 Algorithm or its steps/procedure.

Please upload the page(s) containing ID3 Algorithm, and I will provide the complete answer exactly from the book,
including every point and step.
4)
1)
 2)

3)

5) i) Distinguish between Regression and Correlation

Regression Correlation

Correlation among two variables can be done effectively using

Regression is about predicting one variable given another
a Scatter plot, which is a plot between explanatory variables
variable.
and response variables.

While correlation is about relationships among variables, It is a 2D graph showing the relationship between two
Regression Correlation

say x and y, regression is about predicting one variable variables.

given another variable.

The Pearson correlation coefficient is the most common test

Regression analysis quality is determined by factors such
for determining correlation and is an association between two
as correlation and causation.
variables.

The correlation coefficient is denoted by r. Correlation indicates association between two variables.

Regression is about prediction. Correlation is about relationship among variables.

ii) Distinguish between Regression and Causation

Regression Causation

Regression is about predicting one variable given another Causation is about causal relationship among variables, say x
variable. and y.

Regression relationship is not same as causation Causation means knowing whether x causes y to happen or
relationship. vice versa.

Regression does not imply cause-and-effect relationship. Cause is often denoted as x implies y.

Causation identifies whether one variable is the cause of

Regression may show relationship among variables.
another.

Examples

• The correlation between economical background and marks scored does not imply that economic background
causes high marks.

• Similarly, the relationship between higher sales of cool drinks due to a rise in temperature is not a causal
relation.

• Even though high temperature is the cause of cool drinks sales, it depends on other factors too.

iii) Distinguish between Linearity and Non-linearity Relationships

Linearity Relationship Non-linearity Relationship

The linearity relationship between the variables means

the relationship between the dependent and A non-linear relationship exists in functions such as exponential
independent variables can be visualized as a straight function and power function.
line.

The functions like exponential function (y = axᵇ) and power

The line of the form, y = ax + b can be fitted to the
function (y = x/(ax + b)) are non-linear relationships between the
data points that indicate the relationship between x
dependent and independent variables that cannot be fitted in a
and y.
line.

By linearity, it is meant that as one variable increases,

the corresponding variable also increases in a linear These relationships cannot be represented by a straight line.
manner.
Linearity Relationship Non-linearity Relationship

Example: y = ax + b Examples: y = axᵇ and y = x/(ax + b)

Important Questions

1) 4.2 Nearest-Neighbor Learning (k-NN)

• A natural approach to similarity-based classification is k-Nearest-Neighbors (k-NN), which is a non-parametric

method used for both classification and regression problems.

• It is a simple and powerful non-parametric algorithm that predicts the category of the test instance according
to the ‘k’ training samples which are closer to the test instance and classifies it to that category which has the
largest probability.

• A visual representation of this learning is shown in Figure 4.1.

• There are two classes of objects called C₁ and C₂ in the given figure.

• When given a test instance T, the category of this test instance is determined by looking at the class of k = 3
nearest neighbors.

• Thus, the class of this test instance T is predicted as C₂.

Characteristics of k-NN

• The algorithm relies on the assumption that similar objects are close to each other in the feature space.

• k-NN performs instance-based learning which just stores the training data instances and learning instances case
by case.

• The model is also ‘memory-based’ as it uses training data at time when predictions need to be made.

• It is a lazy learning algorithm since no prediction model is built earlier with training instances and classification
happens only after getting the test instance.

• The algorithm classifies a new instance by determining the ‘K’ most similar instances (i.e., k nearest neighbors)
and summarizing the output of those ‘K’ instances.
 • If the target variable is discrete then it is a classification problem, so it selects the most common class value
among the ‘K’ instances by a majority vote.

• However, if the target variable is continuous then it is a regression problem, and hence the mean output
variable of the ‘K’ instances is the output of the test instance.

• The most popular distance measure such as Euclidean distance is used in k-NN to determine the ‘K’ instances
which are similar to the test instance.

• The value of ‘K’ is best determined by tuning with different ‘K’ values and choosing the ‘K’ which classifies the
test instance more accurately.

Algorithm 4.1: k-NN

Inputs

• Training dataset T

• Distance metric d

• Test instance t

• The number of nearest neighbors k

Output

• Predicted class or category

Prediction: For test instance t,

1.

• For each instance i in T, compute the distance between the test instance t and every other instance i in the
training dataset using a distance metric (Euclidean distance).

Continuous attributes

• Euclidean distance between two points in the plane with coordinates (x₁,y₁) and (x₂,y₂) is given as:

d((x_1,y_1),(x_2,y_2))=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}

Categorical attributes (Binary)

• Hamming Distance:

• If the value of the two instances is same, the distance d will be equal to 0 otherwise d = 1.

2.

• Sort the distances in an ascending order and select the first k nearest training data instances to the test
instance.

3.

• Predict the class of the test instance by majority voting (if target attribute is discrete valued) or mean (if target
attribute is continuous valued) of the k selected nearest instances.

Data Normalization / Standardization

 • Data normalization/standardization is required when data (features) have different ranges or a wider range of
possible values when computing distances and to transform all features to a specific range.

• This is probably done to eliminate the influence of one feature over another (i.e., to give all features equal
chances).

• For example if one feature has values in the range of [0–1] and another feature has values in the range of [0–
100], then the second feature will influence more even if there is a small variation in the first feature.

Factors Affecting k-NN Performance

• k-NN classifier performance is strictly affected by three factors such as:

1. the number of nearest neighbors (i.e., selection of k),

2. distance metric and

3. decision rule.

• If the k value selected is small then it may result in overfitting or less stable and if it is big then it may include
many irrelevant points from other classes.

• The choice of the distance metric selected also plays a major role and it depends on the type of the
independent attributes in the training dataset.

Limitation of k-NN

• The k-NN classification algorithm best suits lower dimensional data as in high-dimensional space the nearest
neighbors may not be very close at all.

2) 4.3 Weighted K-Nearest-Neighbor Algorithm

• The Weighted k-NN is an extension of k-NN.

• It chooses the neighbors by using the weighted distance.

• The k-Nearest Neighbor (k-NN) algorithm has some serious limitations as its performance is solely dependent
on choosing the k nearest neighbors, the distance metric used and the decision rule.

• However, the principle idea of Weighted k-NN is that k closest neighbors to the test instance are assigned a
higher weight in the decision as compared to neighbors that are farther away from the test instance.

• The idea is that weights are inversely proportional to distances.

• The selected k nearest neighbors can be assigned uniform weights, which means all the instances in each
neighborhood are weighted equally or weights can be assigned by the inverse of their distance.

• In the second case, closer neighbors of a query point will have a greater influence than neighbors which are
further away.

Algorithm 4.2 : Weighted k-NN

Inputs

• Training dataset T
 • Distance metric d

• Weighting function w(i)

• Test instance t

• The number of nearest neighbors K

Output

• Predicted class or category

Prediction: For test instance t

1.

• For each instance i in Training dataset T, compute the distance between the test instance t and every other
instance i using a distance metric (Euclidean distance).

Continuous attributes

• Euclidean distance between two points in the plane with coordinates (x₁, y₁) and (x₂, y₂) is given as:

d((x_1,y_1),(x_2,y_2))=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}

Categorical attributes (Binary)

• Hamming Distance:

• If the values of two instances are the same, the distance d will be equal to 0.

• Otherwise d = 1.

2.

• Sort the distances in the ascending order and select the first ‘K’ nearest training data instances to the test
instance.

3.

• Predict the class of the test instance by weighted voting technique (Weighting function w(i)) for the k selected
nearest instances:

Steps

• Compute the inverse of each distance of the ‘K’ selected nearest instances.

• Find the sum of the inverses.

• Compute the weight by dividing each inverse distance by the sum. (Each weight is a vote for its associated
class).

• Add the weights of the same class.

• Predict the class by choosing the class with the maximum vote.

3) 4.4 Nearest Centroid Classifier

 • A simple alternative to k-NN classifiers for similarity-based classification is the Nearest Centroid Classifier.

• It is a simple classifier and also called as Mean Difference classifier.

• The idea of this classifier is to classify a test instance to the class whose centroid/mean is closest to that
instance.

Algorithm 4.3 : Nearest Centroid Classifier

Inputs

• Training dataset T

• Distance metric d

• Test instance t

Output

• Predicted class or category

Procedure

1.

• Compute the mean/centroid of each class.

2.

• Compute the distance between the test instance and mean/centroid of each class (Euclidean Distance).

3.

• Predict the class by choosing the class with the smaller distance.

4) 4.5 Locally Weighted Regression (LWR)

• Locally Weighted Regression (LWR) is a non-parametric supervised learning algorithm that performs local
regression by combining regression model with nearest neighbor’s model.

• LWR is also referred to as a memory-based method as it requires training data while prediction but uses only
the training data instances locally around the point of interest.

• Using nearest neighbors algorithm, we find the instances that are closest to a test instance and fit linear
function to each of those ‘k’ nearest instances in the local regression model.

• The key idea is that we need to approximate the linear functions of all ‘k’ neighbors that minimize the error
such that the prediction line is no more linear but rather it is a curve.

Ordinary Linear Regression

• Ordinary linear regression finds out a linear relationship between the input x and the output y.

Given training dataset T,

• Hypothesis function hβ(x), the predicted target output is a linear function where β₀ is the intercept and β₁ is
the coefficient of x.

It is given in Eq. (4.1) as,

h_{\beta}(x)=\beta_0+\beta_1x

Cost Function

• The cost function is such that it minimizes the error difference between the predicted value hβ(x) and true
value ‘y’ and it is given as in Eq. (4.2).

J(\beta)=\frac{1}{2}\sum_{i=1}^{m}(h_{\beta}(x_i)-y_i)^2

where,

• ‘m’ is the number of instances in the training dataset.

Cost Function for Locally Weighted Linear Regression

• Now the cost function is modified for locally weighted linear regression including the weights only for the
nearest neighbor points.

• Hence, the cost function is given as in Eq. (4.3).

J(\beta)=\frac{1}{2}\sum_{i=1}^{m}w_i(h_{\beta}(x_i)-y_i)^2

where,

• wᵢ is the weight associated with each xᵢ.

Weight Function

• The weight function used is a Gaussian kernel that gives a higher value for instances that are close to the test
instance, and for instances far away, it tends to zero but never equals to zero.

• wᵢ is computed in Eq. (4.4) as,

w_i=e^{-\frac{(x_i-x)^2}{2\tau^2}}
4)

5)
6)
7)