Unit 2

UNIT - II: Nearest Neighbor- Based Models:

Introduction to Proximity Measures, Distance Measures, Non-Metric Similarity
Functions, Proximity Between Binary Patterns, Different Classification Algorithms
Based on the Distance Measures,K-Nearest Neighbor Classifier, Radius Distance
NearestNeighbor Algorithm, KNN Regression, Performance of Classifiers,
Performance of Regression Algorithms.

Nearest Neighbor –Based Models

Proximity measures are mathematical techniques used to calculate the similarity or

dissimilarity between data poi V nts. These pattern vectors can represent documents,
images or even audio or video files. It is used by machine learning algorithm to
compare and classify or group or make predictions using patterns.

It identifies the nearest neighbors. Predictions based on closeness to know sample.

There are many types of proximity measures they are

√ Euclidean distance

√ Cosine similarity

√ Jaccard similarity

√ Hamming distance

Euclidean D istance: Euclidean Distance is the straight-line distance between two

points in multi – dimensional space (like on a graph or map). It is also called as the
crow flies distance.

D(x,y)=(x1−y1)2+(x2−y2)2+ +(xn−yn)2

Imagine two points on a map: A(1, 1) and B(4, 5). The Euclidean distance between
them is: √((4 - 1)² + (5 - 1)²) = √(3² + 4²) = √25 = 5 units
Cosine similarity: Cosine similarity is a measure of similarity between two non-zero
vectors defined in an inner product space. It's commonly used in text analysis to
determine how similar documents are based on the frequency of shared terms.
1
Cosine Similarity : cos(θ)= x ⋅ y x⋅y

x=(2,1),y=(4,2)

x =22+12=5, y =42+22=20

Jaccard similarity : Jaccard similarity refers to a measure of similarity between two

sets of [Link] measures the ratio of the cardinaties of intersection over union
of two sets. It compare user preferences. It is used for comparing sets, binary vectors,
or categorical data .

Jaccard Similarity= A∪B A∩B

A∩BA \ BA∩B = Number of elements common to both sets

A∪BA \ BA∪B = Number of unique elements in either set
Hamming distance : It is a proximity measure that counts the number of positions at
which two strings (of equal length) are different . It is widely used for comparing
binary strings , DNA sequences, error detection codes, etc.

Two binary strings x and y of equal length

n
Hamming Distance(x,y)= ∑ i =1 [ xiyi]

X i is not equal to Y i = 1 if the bits differ at position i, else 0

n = length of the strings

Distance Measures

A distance measure is used to find the dissimilarity between patterns represented as

vectors. Patterns which are more similar they are closer. The distance function could
be a metric or a non – [Link] mosu popularly used distance metric is called as
minkowski [Link] is used to quantify the separation between two objects or points .

A metrics has 3 key attributes

Positive reflexivity: A distance function d(x,y)d(x, y)d(x,y) is said to satisfy positive

reflexivity. The distance between a point and itself is 0 . The distance between two
different points is always > 0.
2
Symmetry : Symmetry is one of the key properties of a function must satisfy to be a
valid distance (or metric). The distance from point A to point B is the same as from point B
to point A. Order doesn’t matter in distance measurement.
A distance function d(x,y) d(x, y) d(x,y) is said to be symmetric if:
d(x,y) = d(y,x) d(x, y) = d(y, x) d(x,y) = d(y,x)
Triangle Inequality : The triangle inequality is a fundamental property of a metric (valid
distance function). The direct distance from x to z is no greater than going from x to y
and then from y to z .
For any three points x,y,z a distance function d satisfies triangle inequality
d(x,z)≤d(x,y)+d(y,z)
Different types of similarity / dissimilarity measures between pattern vectors are
1. Minkowski Distance
2. Weighted Distance
3. Non –Metric Similarity Functions
4. Levenshtein Distance
5. Mutual Neighborhood Distance (MND)
6. Proximity Between Binary Patterns

1. Minkowski Distance :
Minkowski distance is a metric in a normed vector space that generalizes both
Euclidean and Manhattan distances. It provides a way to measure the distance
between two points in a multi-dimensional space, with the flexibility to adjust the
distance calculation based on a parameter p. he Minkowski Distance is a
generalization of both the Euclidean distance and the Manhattan distance.
L 1/k
D(x,y) = ∑ k=1 |P k -q k |
Where r is the parameter tht determines the type of metric.
P and Q are l –dimensional vectors.
Mathematical Properties
L norm Here r = and d(p,q) = maximum k = (|p(k) - q(k)), K € {1,2,3,….L}.
2)1/2
L2 norm Here r = 2 d(p,q) = | It is called as Euclidean distance
L1 norm Here r=1 and d (p,q) = |) It is known as city block distance / Manhattan
distance
Fractional norm : It is possible that r is a fraction. As a result distance is called as
fractional norm.

3
Consider two points in 3D space:
A = (2, 5, 8), B = (3, 1, 6)
For Manhattan Distance (p = 1)
D(A,B)= 2−3 + 5−1 + 8−6 =1+4+2=7D(A,B)= 2−3 + 5−1 + 8−6 =1+4+2=7
For Euclidean Distance (p = 2)
D(A,B)=(2−3)2+(5−1)2+(8−6)2D(A,B)=(2−3)2+(5−1)2+(8−6)2
D(A,B)=1+16+4=21≈4.58D(A,B)=1+16+4=21≈4.58
For Chebyshev Distance (p→∞)
D(A,B)=max( 2−3 , 5−1 , 8−6 )=max(1,4,2)=4D(A,B)=max( 2−3 , 5−1 , 8−6 )=max(1,4,2)=4

The importance of different norms will be examined while explaining the nearest
neighbor classifiers. Manhalanobis distance is another popular distance measure that
is used in classification. The squared Manhalanobis distance is given by distance
2 t -1
D (x,y) = (x - y) ∑ (x - y)
Real- Life Applications
1. Machine Learning & Clustering

4
2. Image Processing
3. Finance & Risk Analysis
4. Robotics & Path Planning
3. Weighted Distance Measure
A weighted distance measure assigns different importance (weights) to different
dimensions or components when calculating the distance between two data points.
It's a generalization of standard distance metrics like Euclidean or Hamming distance,
where each component contributes equally. This is useful when some features are
more important than others in determining similarity or distance.
n r 1/r
D(x,y)=( k =1 ∑ wik * (xk−yk) )
th
Where wk represents the weight associated with the k dimension or feature.
Let: x=(2,3) y=(5,7) Weights: w=(0.6,0.4) p =2 (Weighted Euclidean)
2
D(x,y)=0.6⋅(2−5)2+0.4⋅(3−7)
√0.6⋅9+0.4⋅16 =√5.4+6.4 =11.8 ≈3.435
4. Non - Metric Similarity Functions
The category includes similarity functions that do not obey the triangular or symmetry. They
are commonly used for image or string data and they are resistant to outliers or extremely
noisy data. The squard Euclidean distance is an example of a non – metric, but it provides the
same ranking as the Euclidean distance metric. It does not fulfill all properties of a distance
metric , such as:
Non- negativity
Identity of indiscernibles (d(x, x) = 0)
Symmetry (d(x, y) = d(y, x))
Triangle inequality (d(x, z) ≤ d(x, y) + d(y, z))

Non-metric Functions may violate:

Symmetry
Triangle Inequality
Zero Distance for identical objects
Characteristics of Non-Metric Similarity Functions
They may not satisfy properties like symmetry, non-negativity, or the triangle
inequality.
They are particularly useful in domains where data relationships are non-linear
or symbolic.
They focus on measuring similarity rather than distance.
They may not satisfy properties like symmetry, non-negativity, or the triangle
inequality.
They are particularly useful in domains where data relationships are non-linear or
symbolic.
They focus on measuring similarity rather than distance.
They may not satisfy properties like symmetry, non-negativity, or the triangle
5
inequality.
They are particularly useful in domains where data relationships are non-linear or
symbolic.
They focus on measuring similarity rather than distance.
They may not satisfy properties like symmetry, non-negativity, or the triangle
inequality.
They are particularly useful in domains where data relationships are non-linear or
symbolic.
They focus on measuring similarity rather than distance.
They may not satisfy properties like symmetry, non-negativity, or the triangle
inequality.
They are particularly useful in domains where data relationships are non-linear or
symbolic.
Common Non- Metric Similarity Functions
1. Cosine Similarity: Measures the cosine of the angle between two
vectors. Commonly used in text analysis.
S (x, y) = x. y / ||x| ||y||
Not a metric because:
Doesn’t satisfy triangle inequality.
Not a true “distance” but a similarity score

2. Jaccard Similarity
For sets A and B:
Jaccard(A,B) = |A∩B| / | A∩B|
Used for binary or set data.
Jaccard distance can be derived but Jaccard similarity itself is not a metric.

3. Overlap Coeffi cient

Similar to Jaccard but normalized by the smaller set:
Overlap (A,B)= A∩B / min ( A , B|)
Doesn’t satisfy triangle inequality.

4. Pearson Correlation Coeffi cient

Measures linear correlation between two variables.
Values range from –1 (inverse correlation) to +1 (perfect correlation).
Can be negative — so not non- negative → violates metric properties.

5. Mutual Information
Measures how much knowing one variable reduce uncertainty about another.
Violates symmetry.

Applications:
6
 Document similarity (Cosine)
Gene similarity (Mutual Information)
Recommendation systems (Jaccard)
Clustering non- metric data (e.g., hierarchical clustering with similarity matrices)
4. Levenshtein Distance
Levenshtein Distance is also known as edit distance. It measure the distance
between two strings. It is determined by calculating the minimum number of
mutations needed to transform strings s1 into string s2. The mutation can be one of
three operations changing a lettet, inserting a letter or deleting a letter. Mutation
means a change or alteration . The edit distance can be defined as.
1. Two empty strings match d(“ ”,” “)
2. Distance from an empty string d(s,” “) = d(“ ”,s) = ||s||
3. D(s1 + ch1, s2+ch2) = min [ d(s1,s2) + { if ch1 = ch2 then 0 else 1}
D(s1 + ch1, s2)+1, d(s1, s2+ch2) + 1]

Example:
Find the Levenshtein distance between:
"kitten" and "sitting"
Steps:
1. kitten → sitten (substitute 'k' with 's')
2. sitten → sittin (substitute 'e' with 'i')
3. sittin → sitting (insert 'g')
Levenshtein Distance = 3

Applications:
Spell checkers and autocorrect
DNA sequence comparison in bioinformatics
Plagiarism detection
Natural Language Processing (NLP)
Search algorithms with typo tolerance
Properties:
Non- negative
Symmetric
Satisfies triangle inequality
Hence, Levenshtein Distance is a metric
5. Mutual Neighborhood Distance (NMD)
Mutual Neighborhood Distance (NMD) between two data points x and y is based
on the common elements in their k-nearest neighbors .
Instead of directly computing distance (like Euclidean), NMD compares the
similarity of the neighborhood around two points.
7
 It measures how similar the local environments (neighbors) of two data points are.
NMD is a distance-based similarity measure used in pattern recognition , classification,
and clustering tasks. If two data points x and y share many of the same nearest
neighbors, they are considered similar → hence, they have low NMD . If they have
very different neighbors , they are considered distant → higher NMD.
Mutual Neighborhood Distance (NMD) is defined as:
NMD(x,y)=1 − k Nk(x)∩Nk(y) k
1. For a given point x, find its k nearest neighbors → N_k(x)
2. For another point y, find its k nearest neighbors → N_k(y)
Nk(x)∩Nk(y) - number of common neighbors
k: the total number of neighbors considered
The value ranges from 0 (very similar) to 1 (completely different)

Properties:
NMD is not a metric :
o It may not satisfy triangle inequality
o It is based on set overlap , not geometric distance
Useful in non-Euclidean spaces
Effective in high-dimensional or noisy datasets
Example
Let’s say we have 5 data points: A, B, C, D, E
N₂(A) = [ B, C]
N₂(D) = [ C, E]
NMD(A,D )= 1 / − [ B,C] ∩[ C,E] | / 2 = 1- 1/ 2 = 0.5
So, the NMD between A and D is 0.5
NMD is Used in
Clustering (e.g., Mutual k- NN clustering)
Classification (k- NN- based classifiers)
Anomaly detection
When neighborhood structure is more important than absolute distance .

1. Proximity Between Binary Patterns

To measure proximity (similar or close) between such binary vectors, we use similarity
or distance measures specifically designed for binary data. Binary patterns are
sequences made up of 0s and 1s, like: X = [1, 0, 1, 1, 0] , Y = [ 1, 1, 0, 1, 0]
Common Measures of Proximity Between Binary Patterns:

Hamming Distance
Hamming distance is the number of mismatching bits of the l –bit locations.

8
 Counts the number of bit positions where the two binary vectors differ.
Lower value → more similar
Example:
X = [1, 0, 1, 1, 0]
Y = [1, 1, 0, 1, 0]
Difference: [0, 1, 1, 0, 0] → 2 positions differ
Hamming Distance = 2

2. Jaccard Similarity
Focuses only on the positions where at least one of the vectors is 1.
Formula:
Jaccard(X,Y) = f11 / f01 + f10 + f11
where:
o f11: number of positions where both X and Y are 1
o f01 : X=0, Y=1
o f10 : X=1, Y=0
Example:
X = [1, 0, 1, 1, 0]
Y = [ 1, 1, 0, 1, 0]
f11=2 (positions 1 and 4)
f01=1 (position 2)
f10=1 (position 3)
Jaccard = 2 / 2+1+1 = 2 / 4 = 0.5

3. Simple Matching Coeffi cient (SMC)

Measures the proportion of matching bits (both 1s and 0s).
Formula:
SMC(X,Y) = f11+f00 / n

where f00 is the number of positions where both are 0, and n is the total number of
bits.
Example:
f11=2, f00=2, n =5

SMC = 2+2 / 5 = 0.8

1. Cosine Similarity

Treats binary vectors as vectors in space and computes cosine of the angle
between them.

Cosine(X,Y) = X . Y / ||X|| ||Y||

9
 In binary vectors, dot product counts f11

norm is square root of number of 1s.

Different classification algorithms based on the distance measures

Classification algorithms based on distance measures are used to classify data points
based on how "close" they are to other points in the feature space. These distance-
based classifiers generally rely on metrics like Euclidean, Manhattan, Minkowski,
Mahalanobis, or Cosine similarity to compute distances between data points.
1. Nearest Neighbour Classifier (NNC)
2. k- Nearest Neighbour Classifier (kNNC)
3. Weighted k- Nearest Neighbour (WkNN)
4. Radius distance Near Neighbours
5. Tree Based Nearest Neighbours
6. Branch and Bound Method
7. Leader clustering

1. Nearest Neighbour Classifier (NNC)The Nearest Neighbour Classifier is one of the

simplest classification algorithms in machine learning. It finds the closest (nearest)
data point from the training set and assigning its class to the new point.
Collect training data : You need a dataset with input features and known class
labels.
Get a new (test) data point : This is the data point whose class you want to predict.
Calculate distances: Measure how far the new point is from each point in the
training data. The most commonly used distance is Euclidean distance , but
others like Manhattan or Cosine similarity can also be used.
Find the nearest neighbor : Find the training point that has the smallest distance to
the new point.
Assign the class: The new data point is given the same class as its nearest
neighbor.

10
 .
Most common dista nce is Euclidean Distance
d(x,xi) = ∑n(xj−xi)2
where
x = test point
xi = training point
n= number of features
Training Data Feature 1 Feature 2 Class
A 2 4 Red
B 4 6 Blue
C 1 3 Blue

11
Test point : (2.5, 3.5)
Compute distance to each point → Find nearest → Assign class label of nearest point.
Eg: Apple –Weight - 150g, Color - red
Banana –Weight –140g, Color –yellow
New data Weight 145g, color –red
So it is similar to red

Advantages:
Very simple to understand and implement
No training needed (lazy learner)
Works well with small datasets
Adapts easily to new data

Disadvantages:
Slow for large datasets
Sensitive to irrelevant or scaled features

2. K- Nearest Neighbors (K- NN) Classifier

The K-Nearest Neighbors (K-NN) classifier is one of the simplest and most commonly
used machine learning algorithms for classification tasks. It is a lazy learning algorithm
that doesn't explicitly learn a model during training. Instead, it stores the training data
and makes predictions based on the "neighbors" (i.e., the closest data points) in the
feature space.

Steps for K- NN Classification:

1. Choose the number of neighbors ( K):
The number K determines how many neighbors the algorithm will
consider when making a prediction for a new data point. Typically, K is an
12
 odd number to avoid ties in classification.
2. Calculate the distance between the test point and all the training data points :
The most commonly used distance metric is Euclidean distance , but other
distance metrics like Manhattan distance , Minkowski distance, or Cosine
similarity can also be used.
3. Sort the distances :
Once the distances are calculated, the training points are sorted by
distance to the test point, in ascending order.

4. Select the K nearest neighbors :

The algorithm selects the K closest training points to the test point.
5. Make the prediction :
For classification, the predicted class is the majority class among the K
neighbors. For regression, the prediction is the average or weighted
average of the values of the K nearest neighbors.

Euclidean Distance Formula

The Euclidean distance between two points

Advantages of K- NN
1. Simple to Understand and Implement : K-NN is one of the most intuitive
algorithms, making it easy to understand and implement.
2. No Training Phase: K-NN is a lazy learner (also called a memory-based learner),
meaning it doesn't require training or model fitting. It just memorizes the
training dataset.
3. Non-parametric : K-NN doesn’t make any assumptions about the underlying
data distribution, making it useful for complex datasets with unknown
distributions.
4. Versatile: Can be used for both classification and regression tasks.

Disadvantages of K- NN
1. Computationally Expensive : Since it stores all the training data, making

13
 predictions can be slow, especially with large datasets.
2. Sensitive to the Choice of K : The performance can vary greatly with different
values of K. Small values of K can lead to over fitting , while large values of K
can lead to under fitting .
3. Sensitive to Irrelevant Features : K-NN is sensitive to irrelevant features and noisy
data. If the features are not well- scaled, the algorithm may perform poorly.
4. Memory Intensive : K-NN requires storing all the training data, which can be
problematic with large datasets.

Choosing the Optimal K Value

The choice of K is crucial in determining the algorithm's performance:
Small K (e.g., K=1) makes the model sensitive to noise, leading to overfitting.
Large K (e.g., K=20) smoothens the decision boundary, but can lead to
underfitting, especially if the dataset has complex patterns.
Cross-validation : One way to find the optimal value of K is to use cross-validation ,
which involves splitting the data into training and validation sets and
evaluating the performance for different values of K.

Feature Scaling in K- NN

Since K-NN uses distance metrics (like Euclidean distance) to measure the similarity
between points, feature scaling is critical. Features with larger numerical ranges (e.g.,
income in thousands vs. age in years) may dominate the distance calculation, leading
to incorrect predictions.
Normalization : Scale the features to a fixed range, typically [ 0, 1] .
Standardization : Scale the features so that they have a mean of 0 and a standard
deviation of 1.

3. Weighted K- Nearest Neighbors (Weighted K- NN)

The Weighted K-Nearest Neighbors (Weighted K-NN) algorithm is an extension of the
standard K-Nearest Neighbors (K-NN) algorithm. Instead of assigning equal weight to
all K nearest neighbors when making a classification or regression decision, the
Weighted K-NN assigns weights to the neighbors based on their distanc e. This makes
the predictions more acc urate because closer neighbors are given more importance.

How Weighted K- NN Works:

1. Select the value of K the number of neighbors .
2. Calculate the distance between the query point and all points in the training set
(commonly using Euclidean distance).
3. Sort the distances to find the K nearest neighbors.
4. Assign weights to the neighbors based on their distance. The typical approach is
to use the inverse of the distance : the closer a neighbor, the higher its weight.
The weight could be calculated as:
2
W i = 1 / d(x, xi)
5. Classify or Predict :
14
 o For classification: Assign the class label based on the weighted majority
vote of the K nearest neighbors.
o For regression: Calculate the weighted average of the K neighbors' values.

Weighting Function (Inverse Distance Weighting)

In the standard K-NN, each of the K neighbors has equal influence, but in the Weighted
K-NN , we give closer neighbors more influence. A common weighting function is the
inverse distance:
Weight of neighbor wi=1/d

Weighted K- NN Example for Classification:

Let's say we have a simple dataset with three classes (Red, Blue, Green) and three
features (X, Y):
X Y Clas
s

1 2
Red

2 3 Blu
e

3 1 Gre
en

5 4 Blu
e

4 4 Gre
en

Now, we want to classify a new point (3, 2) using Weighted K-NN with K=3.
1. Calculate Distances:
o Calculate the Euclidean distance from (3, 2) to each point in the dataset.
2. Find K Nearest Neighbors :
o The 3 nearest neighbors based on the distances are: (2, 3) [Blue], (1, 2)
[ Red] , and (3, 1) [ Green] .
3. Assign Weights :
The weights will be:
o Weight of (2, 3) =0.71
o Weight of (1, 2) =0.50
o Weight of (3, 1) =1.00
15
 4. Weighted Voting :
o The predicted class will be based on the weighted vote :
Blue has a weight of 0.71.
Red has a weight of 0.50.
Green has a weight of 1.00.
Based on the weighted vote, the Green class has the highest weight and will be
predicted as the class for the new point.

Weighted K- NN Example for Regression:

Let's say we are using the same dataset, but the target variable is continuous (e.g.,
house prices).
X Y Price

1 2 100

2 3 150

3 1 200

5 4 250

4 4 300

We want to predict the price for the new point (3, 2).
1. Calculate Distances:
o Calculate the Euclidean distance between the new point (3, 2) and all the
points in the dataset.
2. Find K Nearest Neighbors :
o The 3 nearest neighbors are: (2, 3) [Price = 150], (3, 1) [Price = 200], and
(4, 4) [ Price = 300] .
3. Assign Weights :
o Based on inverse distance, calculate the weights as before:
Weight of (2, 3) =0.71
Weight of (3, 1) =1.00
Weight of (4, 4) =0.45
4. Weighted Average :
o Calculate the weighted average of the prices for these 3 neighbors:
Predicted Price=(0.71×150)+(1.00×200)+(0.45×300)0.71+1.00+0.45

= 441.5 / 2.16

= 204.17

So, the predicted price for the new point (3, 2) is approximately 204.17.
16
Advantages of Weighted K- NN:
1. More Accurate Predictions : By weighting the neighbors based on their distance,
closer neighbors (which are more likely to be similar) have a larger influence on
the prediction.
2. Improves Performance for Non-Uniform Data : When the data has varying
densities, weighted K-NN can give better results by adjusting for local
variations.
3. Flexibility : You can use different weighting schemes (inverse distance, Gaussian
kernel, etc.) to further refine the model's performance.

Disadvantages of Weighted K- NN:

1. Complexity : The computation of weights adds additional complexity to the
algorithm.
2. Choice of Weighting Function : The choice of weighting function can affect the
model's performance. Improper choice of weighting function might lead to
suboptimal results.
3. Still Computationally Expensive : K-NN in general (even with weights) is
computationally expensive, especially for large datasets, as you have to compute
distances between the test point and all training points.

4. Radius distance Near Neighbours Agorithm

Radius Nearest Neighbors is a supervised learning method that classifies a new
(test) data point by looking at all training points that lie within a certain distance from it.

Steps:
1. Choose a radius value r (e.g., 2.0).
2. For the test point, calculate the distance to each training point.
3. Select all training points whose distance ≤ r.

17
 4. Among those selected:
o Do majority voting for classification.
5. If no points are found within radius:
o You may reject the classification, or
o Use the nearest neighbor , or
o Increase the radius dynamically.
For example: Imagine you're in a city and you want to know what most people around
you like to eat - Pizza, Burger, or Biryani).
You set a rule:
I’ll only ask people within 2 km of me.”
If: Most say Pizza, you choose Pizza.
If no one is around you within 2 km, you say: “I can’t decide” (or increase your
search area).

Advantages of Radius- NN:

1. More accurate in uneven data : In dense regions, it selects more neighbors; in
sparse areas, fewer.
2. Good for outlier detection : If no neighbors are found in radius → it might be an
anomaly.
3. Flexible : Works better when clusters have different shapes and densities.

Disadvantages of Radius- NN:

1. Choosing the right radius r is tricky :
o Too small → may find no neighbors
o Too large → may include too many irrelevant points
2. Inefficient with large datasets :
o You need to search all data to check which fall within radius.

Applications:
Pattern recognition
Anomaly detection
Medical diagnosis
Recommender systems
Poi
nt Coordinates Class
A

(1, 2) 0

B (2, 3) 0

18
C (5, 5) 1
D (8, 8) 1
Now, we have a test point T = (2, 2)
Set radius r = 2
Distance from A = 1.0 within radius
Distance from B = 1.41 within radius
Distance from C = 4.24 outside radius
Distance from D = 8.48 outside radius
Only A and B are considered → Class 0 wins
So, test point T is classified as Class 0
5 Tree –Based Nearest Neighbor Algorithm
An FP-Tree helps to find frequently bought items together (frequent patterns)
without scanning the whole database again and again.
Steps
Step 1: Find Frequency of Items
Go through the entire transaction database once.
Count how many times each item appears .
This is called the support count .
Now, remove items that are less frequent (below the user-defined minimum
support).
Sort the remaining items in descending order of frequency.
Example:
Transactions: T1: {Milk, Bread, Butter}
T2: {Bread, Butter}
T3: {Milk, Bread}
T4: {Milk, Bread, Butter}
Frequencies:
Bread: 4
Milk: 3
Butter: 3
Sorted order: Bread > Milk > Butter
Step 2: Reorder Each Transaction
Step 3: Start Building the FP-Tree
Step 4: Add More Transactions

Example Dataset (2D points - like (x, y)):

Let’s say we have the following points:
Poi Coordinates
nt (x, y)

19
A (2, 3)

B (5, 4)

C (9, 6)

D (4, 7)

E (8, 1)

F (7, 2)

Step- by- Step Tree Construction

Step 1: Sort points by x- axis (level 0)

Points sorted by x:
A(2,3), D(4,7), B(5,4), F(7,2), E(8,1), C(9,6)
Middle point (median): B(5,4) → becomes Root

Step 2: Split left and right:

Left of B → A(2,3), D(4,7)
Right of B → F(7,2), E(8,1), C(9,6)

Step 3: Level 1 (split by y- axis)

Left Subtree of B (split by y):
A(2,3), D(4,7)
Sorted by y: A(2,3), D(4,7)
Median: D(4,7) → becomes Left child of B
Left of D → A(2,3)
Right Subtree of B (split by y):
F(7,2), E(8,1), C(9,6)
Sorted by y: E(8,1), F(7,2), C(9,6)
Median: F(7,2) → becomes Right child of B
Left of F → E(8,1)
Right of F → C(9,6)

Final KD-Tree Structure (text- based format)

B(5,4)
/ \
D(4,7) F(7,2)
/ / \
A(2,3) E(8,1) C(9,6)

Nearest Neighbor Search:

Let’s say the query point is Q = (6,3) .
20
Using the KD-Tree:
1. Start at root: B(5,4) → Go right since 6 > 5 (x- axis)
2. At F(7,2) → Go left since 3 > 2 (y- axis)
3. At E(8,1) → No children
4. Backtrack and check distances to other sub trees if needed.
Final result: Nearest neighbor is F(7,2)
1. Branch and Bound Method
Branch and Bound (B&B) is an algorithmic method used for solving combinatorial
optimization problems , where the goal is to find the best (optimal) solution among
many possible ones.
It is more efficient than brute force because it eliminates unnecessary searches using:
Branching - splittin g the problem into subproblems
Bounding - estimating the best p ossible result for subproblems
Pruning - ignoring subproblems that can’ t beat the best found solution
1. Tree Structure : The algorithm organizes the search space as a tree, where:
o The root node represents the complete set of features or variables.
o Each branch represents a decision to include or exclude a feature.
o The leaf nodes represent potential solutions (subsets of features).
2. Bounding : At each node, the algorithm calculates a bound (e.g., an upper or
lower limit) on the objective function (e.g., accuracy, error, or cost). If the bound
indicates that the node cannot lead to a better solution than the current best,
it is pruned (skipped).
3. Branching : The algorithm systematically explores child nodes (subsets of
features) by branching from the current node.
4. Optimality : By pruning suboptimal branches, the algorithm ensures that the
best solution is found without exhaustively searching all possibilities.
Steps
Branch : Divide the problem into smaller parts.
Bound : Compute a bound (minimum or maximum possible value).
Prune : Discard subproblems that can’t beat the best current solution.
Continue until all possibilities are explored or eliminated.

Applications in Machine Learning

1. Feature Selection :
o The goal is to select the most relevant subset of features to improve
model performance while reducing complexity.
o B&B evaluates subsets of features and prunes those that cannot
outperform the current best subset.
2. Model Optimization :
o It can be used to optimize hyperparameters or select variables in
21
 regression and classification models.
3. Combinatorial Problems :
o Problems like clustering, scheduling, or finding the shortest path can
also benefit from B&B.

Advantages
Guarantees finding the optimal solution.
Reduces computational cost by pruning unnecessary branches.
Works well for small to medium- sized feature sets.

Limitations
Computationally expensive for very large feature spaces.
Performance depends on the quality of the bounding function.
Example
A (1,1)
B (2,8)
C (7,2)
D (8,9)
E (6,6)

Step 1 - Build a Tree- like Structure (Clustering)

Calculate the minimum possible distance from T(5,5) to each cluster’s boundary

All Points
/ \
Cluster 1 Cluster 2
(A,B) (C,D,E)

Cluster 1 Cluster 2
/ \ / \
A(1,1) B(2,8) C(7,2) (D,E)
/ \
D(8,9) E(6,6)

22
Step 2 - Search the Most Promising Cluster First
Cluster 1 (A,B) : is A(1,1) → min possible distance ≈ 5.66
Cluster 2 (C,D,E) : Closest point is E(6,6) → min possible distance ≈ 1.41

Step 3 - Update Best Distance

C(7,2) → distance = √((7-5)² + (2-5)²) = √(4 + 9) = 3.61
E(6,6) → distance = √(1 + 1) = 1.41 → Best so far = 1.41
D(8,9) → distance = √(9 + 16) = 5.00
Step 4 – Find nearest neighbor
Nearest neighbor to T(5,5) is E(6,6) at distance 1.41.
1. Leader Clustering:
Clustering is an unsupervised machine learning technique used to group similar data
points into clusters based on their inherent characteristics. Unlike supervised
learning, clustering does not rely on labeled data. Leader clustering is a fast method for
grouping large amounts of data when the computer’s main memory (RAM) is too small
to hold all the data at once. Instead of recalculating centroids like in K-means, it just
keeps adding points to the closest leader — and if a point is too far from all existing
leaders, it becomes a new leader . Instead of loading everything and checking
repeatedly, it reads each data point only once , decides where it belongs, and moves on.
This makes it much quicker because it doesn’t have to keep going back to the slower
storage (like a hard disk). So, the data is kept in secondary storage (like a hard drive)
and is moved to the main memory (RAM) only when needed. Since reading from
secondary storage is much slower than from main memory, algorithms that keep
looking at the same data many times will need more disk reads, which slows them
down.
Some clustering methods look at the data only once — these are called incremental
algorithms . The Leader algorithm is one such fast and effective method. The main idea
of this algorithm is to put points that are close to each other into the same group,
using a set distance limit to decide what “close” means. If a point is close enough
(within a certain distance) to an existing cluster’s leader, it joins that cluster. If it’s not
close to any cluster, it starts a new cluster and becomes the leader of that cluster.
A cluster is simply a group of things (like data points) that are similar or close to each
other in some way. In data science or machine learning, a cluster means a set of data
points that are grouped together because they share common features or are near
23
each other in the data space.
For example:
In a group of fruits, apples might form one cluster, oranges another, and
bananas a third.
In a map of cities, nearby cities form a cluster because they are close
geographically.
Steps
1. Take the first data point and make it the leader of the first cluster.
2. For each new data point:
Measure the distance between the point and all existing cluster leaders.
If the closest leader is within the set distance limit , add the point to that
cluster.
If not, start a new cluster with this point as its leader.
1. Repeat step 2 for all points until every point is in a cluster.
Advantages
Very fast — only one pass through the data.
No recalculations like K- means.
Good for large datasets.
Limitations
Results depend heavily on the order of data .
Choosing a good threshold T is tricky.

Example: Leader Clustering with Points on a Line

Imagine you have the following points on a number line:
2, 3, 10, 12, 11, 30
You choose a threshold distance of 5. This means points less than or equal to 5 units
apart belong to the same cluster.

Step- by- step:

1. The first point 2 becomes the leader of Cluster 1 .
2. Point 3 : distance from leader 2 is |3 - 2| = 1 ≤ 5 → goes to Cluster 1 .
3. Point 10 : distance from leader 2 is |10 - 2| = 8 > 5 → start Cluster 2 with leader
10.
4. Point 12 : distance from leader 10 is |12 - 10| = 2 ≤ 5 → goes to Cluster 2 .
5. Point 11 : distance from leader 10 is |11 - 10| = 1 ≤ 5 → goes to Cluster 2 .
6. Point 30 : distance from leaders 2 and 10 is more than 5 → start Cluster 3 with
leader 30.

Final clusters:
Cluster 1: {2, 3} (leader = 2)
Cluster 2: {10, 12, 11} (leader = 10)
24
 Cluster 3: {30} (leader = 30)

KNN Regression
KNN Regression (K-Nearest Neighbors Regression) is a supervised machine learning
algorithm used to predict numerical (continuous) values based on the values of the k
nearest neighbors in the training data. Instead of predicting a class label like in KNN
Classification, it predicts a number (e.g., house price, temperature, age).

How KNN Regression Works

1. Distance Calculation: For a given input, the algorithm calculates the distance
(e.g., Euclidean, Manhattan) between the input and all points in the dataset.
2. Neighbor Selection : It selects the k nearest data points (neighbors) based on
the calculated distances.
3. Prediction : The output is computed as the average (or weighted average) of
the target values of these k neighbors.

Key Features
Non-parametric : KNN makes no assumptions about the underlying data
distribution.
Lazy Learning: It doesn't train a model explicitly; instead, it stores the dataset
and performs computation during prediction.
Versatile: Works well for both regression and classification tasks.

Advantages
Simple and easy to implement.
Effective for small datasets with low dimensionality.
No training phase, making it computationally inexpensive for training.

Disadvantages
Computationally expensive during prediction for large datasets.
Sensitive to the choice of k and distance metric.
25
 Performance can degrade with high- dimensional data (curse of dimensionality).
Steps
1. Choose the value of k (number of neighbors to consider).
2. For a new data point, find the k closest data points in the training set using a
distance measure (e.g., Euclidean distance).
3. Take the average (or weighted average) of these neighbors’ values.
4. That average becomes the predicted value .
Example: Guess the temperature in a city today based on the temperatures of nearby
cities.

Distance from Temperature

City
target city (km) (°C)
City A 5 30
City B 8 32
City C 3 29
City D 15 35
City E 20 36

Step 1: Choose k k = 3
Step 2: Find nearest neighbors
City C → 29°C
City A → 30°C
City B → 32°C
Step 3: Average their temperatures
Predicted temperature =329+30+32 / 391=30.33 C
The estimated temperature for the target city is 30.33°C.
Performance of Classifiers
The performance of classifiers refers to how well a classification algorithm can correctly
predict the labels (categories) of unseen data. It is usually measured using metrics
that compare the model’s predictions with the actual (true) labels.

1. Confusion Matrix
A table showing how many predictions were correct and how many were wrong,
broken down into:
True Positive (TP) → Correctly predicted positive cases.
True Negative (TN) → Correctly predicted negative cases.
False Positive (FP) → Predicted positive but actually negative (Type I error).
False Negative (FN) → Predicted negative but actually positive (Type II error).

2. Common Performance Metrics

1. Accuracy

26
 Accuracy=TP + TN / Total Predictions.

How many predictions were correct overall.

Good when classes are balanced.
Misleading when data is imbalanced.
2. Precision
Precision=TP / TP + FP

Out of all predicted positives, how many were actually positive.

(Useful when false positives are costly — e.g., spam detection)
3. Recall (Sensitivity)
Recall=TP / TP + FN

Out of all actual positives, how many were predicted correctly.

(Useful when false negatives are costly — e.g., disease detection)
4. F1-Score
Harmonic mean of Precision and Recall:
F1 = 2×Precision×Recall / Precision + Recall

(Balances precision and recall when both matter)

5. ROC Curve & AUC
o ROC Curve : Graph showing trade-off between True Positive Rate and
False Positive Rate.
o AUC : Area under the ROC curve; higher AUC means better classifier.

3. Factors Affecting Classifier Performance

Quality & size of training data.
Class imbalance (more samples in one category than others).
Choice of features.
Overfitting or underfitting.
Noise in data.

Example
Imagine a spam email classifier:
TP → Spam emails correctly marked as spam.
TN → Real emails correctly marked as not spam.
FP → Real emails wrongly marked as spam.
FN → Spam emails wrongly marked as real.
A high-performing classifier will have high TP and TN values while keeping FP and FN
low.

27
Preference of Regression Algorithm
The preference of a regression algorithm depends on the type of data you have, the
problem you’re solving, and the trade-offs you’re willing to accept between accuracy,
interpretability, and computation time.
Mean Squared Error (MSE)
It is a performance metric used to measure how far the predicted values are from the
actual values in regression problems .

Formula
n 2
MSE=1 / n∑ i=1(yi−y^i)

Where:
n = number of data points
yi = actual (true) value
y^ i = predicted value
The squared difference ensures all errors are positive and penalizes large errors
more heavily.
Steps

Take the difference between the real value and the predicted value .
Square it (to remove negatives and punish big mistakes).
Add all these squared errors.
Divide by the number of data points.

Example
Suppose the actual values are: [5, 6, 7]
Predicted values are: [ 4, 8, 6]
28
Step-by-
step:

1. Errors: (5−4) = 1 , (6−8) = −2, (7−6) = 1

2 2 2
2. Squared errors 1 =1 , (-2) = 4, 1 =1
3. Sum of squared errors = 1 + 4 + 1=6
4. Divide by number of data points ( n= 3)
MSE = 6 / 3 = 2

Mean Absolute Error ( MAE)

It is a regression performance metric that measures the average size of the errors
between predicted values and actual values, without considering their direction
(positive or negative).

Formula
n
MAE=1 / n ∑ i=1 yi−y^ i 

Where:

n = number of data points

yi = actual value
y^ i = predicted value
The absolute value ensures all errors are treated as positive.

Steps
Take the difference between real and predicted values.
Ignore whether the difference is positive or negative (use absolute value).
Add up all these absolute differences.
Divide by the number of data points.

Example
Actual values: [5, 6, 7]
Predicted values: [ 4, 8, 6]
1. Errors: 5 − 4 = 1 , 6 – 8 = −2, 7− 6 = 1
2. Absolute errors: 1 =1 , −2 =2 , 1 =1
3. Sum of absolute errors: 1+2+1=4
4. Divide by n=3
MAE = 4 / 3≈1.33

29