Machine Learning

Unit II: Nearest Neighbor-Based Models

Lecture Notes

Department of Computer Science and Engineering (AI & ML)

Madanapalle Institute of Technology & Science
Academic Year 2025-26

Contents
1 Introduction to Proximity Measures 3
1.1 What are Proximity Measures? . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Why Proximity Measures Matter . . . . . . . . . . . . . . . . . . . . . . 3

2 Distance Measures 3
2.1 Properties of a Metric . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Minkowski Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.3 Special Cases of Minkowski Distance . . . . . . . . . . . . . . . . . . . . 4
2.3.1 Manhattan Distance (L1 Norm, p = 1) . . . . . . . . . . . . . . . 4
2.3.2 Euclidean Distance (L2 Norm, p = 2) . . . . . . . . . . . . . . . . 5
2.3.3 Chebyshev Distance (L∞ Norm, p → ∞) . . . . . . . . . . . . . . 5
2.4 Comparison of Distance Measures . . . . . . . . . . . . . . . . . . . . . . 5
2.5 Weighted Minkowski Distance . . . . . . . . . . . . . . . . . . . . . . . . 6
2.6 Mahalanobis Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3 Non-Metric Similarity Functions 7

3.1 Cosine Similarity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2 Cosine Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.3 Pearson Correlation Coefficient . . . . . . . . . . . . . . . . . . . . . . . 8
3.4 Jaccard Similarity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

4 Proximity Between Binary Patterns 8

4.1 Contingency Table for Binary Data . . . . . . . . . . . . . . . . . . . . . 8
4.2 Simple Matching Coefficient (SMC) . . . . . . . . . . . . . . . . . . . . . 9
4.3 Jaccard Coefficient for Binary Data . . . . . . . . . . . . . . . . . . . . . 9
4.4 Other Binary Similarity Measures . . . . . . . . . . . . . . . . . . . . . . 10

5 Different Classification Algorithms Based on Distance Measures 10

5.1 Instance-Based Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5.2 Distance-Based Classifiers Overview . . . . . . . . . . . . . . . . . . . . . 11

1
Machine Learning - Unit II 23CSM104

6 K-Nearest Neighbor Classifier 11

6.1 Basic Concept . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
6.2 KNN Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
6.3 Choice of K . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
6.4 Weighted KNN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
6.5 KNN Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

7 Radius Distance Nearest Neighbor Algorithm 13

7.1 KNN vs RNN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

8 KNN Regression 14
8.1 Basic KNN Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
8.2 Weighted KNN Regression . . . . . . . . . . . . . . . . . . . . . . . . . . 14

9 Performance of Classifiers 15
9.1 Evaluation Metrics for Classification . . . . . . . . . . . . . . . . . . . . 15
9.1.1 Confusion Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
9.1.2 Key Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
9.1.3 Fβ Score . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
9.2 ROC Curve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
9.3 Multi-class Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

10 Performance of Regression Algorithms 16

10.1 Regression Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
10.1.1 Mean Squared Error (MSE) . . . . . . . . . . . . . . . . . . . . . 16
10.1.2 Root Mean Squared Error (RMSE) . . . . . . . . . . . . . . . . . 17
10.1.3 Mean Absolute Error (MAE) . . . . . . . . . . . . . . . . . . . . 17
10.1.4 R-Squared (Coefficient of Determination) . . . . . . . . . . . . . . 17
10.1.5 Mean Absolute Percentage Error (MAPE) . . . . . . . . . . . . . 17
10.2 Comparison of Regression Metrics . . . . . . . . . . . . . . . . . . . . . . 17

11 Computational Considerations for KNN 17

11.1 Time Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
11.2 Efficient Nearest Neighbor Search . . . . . . . . . . . . . . . . . . . . . . 18
11.2.1 KD-Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
11.2.2 Ball Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
11.3 Curse of Dimensionality . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
11.4 Handling High Dimensions . . . . . . . . . . . . . . . . . . . . . . . . . . 19

12 Advantages and Disadvantages of KNN 19

13 Practical Guidelines for KNN 19

14 Summary 20

2
Machine Learning - Unit II 23CSM104

1 Introduction to Proximity Measures

1.1 What are Proximity Measures?
Definition 1.1 (Proximity). Proximity is a measure that quantifies how “alike” or “dif-
ferent” two data objects are. Proximity measures form the foundation of instance-based
learning algorithms.

Definition 1.2 (Similarity). Similarity is a numerical measure of how alike two data
objects are. Higher values indicate greater similarity. Typically ranges from 0 (no simi-
larity) to 1 (identical).

Definition 1.3 (Dissimilarity (Distance)). Dissimilarity is a numerical measure of how

different two data objects are. Lower values indicate objects are more alike. Minimum
dissimilarity is 0 (identical objects).

Key Point
Similarity and dissimilarity are complementary concepts:

• High similarity ⇔ Low dissimilarity

• If s is similarity, then d = 1 − s can represent dissimilarity (when s ∈ [0, 1])

1.2 Why Proximity Measures Matter

Proximity measures are fundamental to many ML algorithms:

Proximity Measures

K-Nearest Clustering Anomaly

Neighbors Algorithms Detection

Information Recommendation
Retrieval Systems

2 Distance Measures
Distance measures quantify the dissimilarity between data points in a feature space.

2.1 Properties of a Metric

Definition 2.1 (Metric (Distance Function)). A function d : X × X → R is a metric if
it satisfies the following properties for all x, y, z ∈ X:

1. Non-negativity: d(x, y) ≥ 0

3
Machine Learning - Unit II 23CSM104

2. Identity: d(x, y) = 0 ⇔ x = y

3. Symmetry: d(x, y) = d(y, x)

4. Triangle Inequality: d(x, z) ≤ d(x, y) + d(y, z)

d(x, z) d(y, z)

x y
d(x, y)
Triangle Inequality: d(x, z) ≤ d(x, y) + d(y, z)

2.2 Minkowski Distance

Definition 2.2 (Minkowski Distance). The Minkowski distance between two points x =
(x1 , x2 , . . . , xd ) and y = (y1 , y2 , . . . , yd ) in d-dimensional space is:

d
!1/p
X
dp (x, y) = |xi − yi |p (1)
i=1

where p ≥ 1 is a parameter.

2.3 Special Cases of Minkowski Distance

2.3.1 Manhattan Distance (L1 Norm, p = 1)
Definition 2.3 (Manhattan Distance).
d
X
d1 (x, y) = |xi − yi | (2)
i=1

Also called City Block Distance or Taxicab Distance.

x2

y(4, 3)

Euclidean

x(1, 1) Manhattan
x1

4
Machine Learning - Unit II 23CSM104

Manhattan Distance Calculation

For x = (1, 1) and y = (4, 3):

d1 (x, y) = |1 − 4| + |1 − 3|
=3+2=5

2.3.2 Euclidean Distance (L2 Norm, p = 2)

Definition 2.4 (Euclidean Distance).
v
u d
uX
d2 (x, y) = t (xi − yi )2 (3)
i=1

This is the most commonly used distance measure, representing the straight-line distance.

Euclidean Distance Calculation

For x = (1, 1) and y = (4, 3):
p
d2 (x, y) = (1 − 4)2 + (1 − 3)2
√ √
= 9 + 4 = 13 ≈ 3.61

2.3.3 Chebyshev Distance (L∞ Norm, p → ∞)

Definition 2.5 (Chebyshev Distance).
d
d∞ (x, y) = max |xi − yi | (4)
i=1

Also called Maximum Distance or Chessboard Distance.

Chebyshev Distance Calculation

For x = (1, 1) and y = (4, 3):

d∞ (x, y) = max(|1 − 4|, |1 − 3|)

= max(3, 2) = 3

2.4 Comparison of Distance Measures

Table 1: Comparison of Minkowski Distance Variants

Distance p Formula Use Case
Manhattan 1 p |xi − yi | Grid-like paths, sparse data
P

Euclidean 2 (xi − yi ) General purpose, continuous

P 2

Chebyshev ∞ max |xi − yi | Chess moves, warehousing

5
Machine Learning - Unit II 23CSM104

x2

p=1

p=2
x1
p=∞

Unit “circles” for different p values

2.5 Weighted Minkowski Distance

Definition 2.6 (Weighted Minkowski Distance). When features have different impor-
tance, we can use weighted distance:
d
!1/p
X
dwp (x, y) = wi |xi − yi |p (5)
i=1

where wi > 0 is the weight for feature i.

2.6 Mahalanobis Distance

Definition 2.7 (Mahalanobis Distance). The Mahalanobis distance accounts for corre-
lations between features:
(6)
p
dM (x, y) = (x − y)T Σ−1 (x − y)
where Σ is the covariance matrix of the data.
Key Point
Properties of Mahalanobis Distance:

• Scale-invariant (not affected by feature scaling)

• Accounts for correlations between variables

• Reduces to Euclidean distance when Σ = I

• Useful for detecting outliers

Euclidean

Mahalanobis

6
Machine Learning - Unit II 23CSM104

3 Non-Metric Similarity Functions

Not all similarity measures satisfy the metric properties. These are called non-metric
similarity functions.

3.1 Cosine Similarity

Definition 3.1 (Cosine Similarity). Cosine similarity measures the cosine of the angle
between two vectors:
Pd
x·y xi y i
simcos (x, y) = = qP i=1qP (7)
∥x∥∥y∥ d 2 d 2
x
i=1 i y
i=1 i

Range: [−1, 1] for general vectors, [0, 1] for non-negative vectors.

x2
y

x
θ

x1
cos(θ) = similarity

Important
Cosine similarity:

• Measures orientation, not magnitude

• Popular in text mining and document similarity

• Violates triangle inequality (not a metric)

Cosine Similarity Calculation

For x = (1, 2, 3) and y = (2, 4, 6):

x · y = 1(2) + 2(4) + 3(6) = 2 + 8 + 18 = 28

√ √
∥x∥ = 1 + 4 + 9 = 14
√ √
∥y∥ = 4 + 16 + 36 = 56
28 28 28
simcos = √ √ =√ = =1
14 × 56 784 28

The vectors are parallel (identical direction), hence similarity = 1.

7
Machine Learning - Unit II 23CSM104

3.2 Cosine Distance

Definition 3.2 (Cosine Distance).

dcos (x, y) = 1 − simcos (x, y) (8)

Range: [0, 2] for general vectors, [0, 1] for non-negative vectors.

3.3 Pearson Correlation Coefficient

Definition 3.3 (Pearson Correlation).
Pd
i=1 (xi − x̄)(yi − ȳ)
r(x, y) = qP qP (9)
d 2 d 2
i=1 (xi − x̄) i=1 (yi − ȳ)

where x̄ and ȳ are the means. Range: [−1, 1].

Key Point
Pearson correlation is equivalent to cosine similarity of mean-centered data.

3.4 Jaccard Similarity

Definition 3.4 (Jaccard Similarity). For sets A and B:

|A ∩ B|
J(A, B) = (10)
|A ∪ B|

Range: [0, 1]. Used for comparing sets or binary vectors.

Jaccard Similarity

For A = {1, 2, 3, 4} and B = {2, 3, 5, 6}:

A ∩ B = {2, 3}, |A ∩ B| = 2
A ∪ B = {1, 2, 3, 4, 5, 6}, |A ∪ B| = 6
2
J(A, B) = = 0.333
6

4 Proximity Between Binary Patterns

For binary data (where features take values 0 or 1), specialized proximity measures are
used.

4.1 Contingency Table for Binary Data

For two binary vectors x and y:

8
Machine Learning - Unit II 23CSM104

y
1 0 Total
1 f11 f10 f1+
x
0 f01 f00 f0+
Total f+1 f+0 d

where:

• f11 : Number of features where both xi = 1 and yi = 1

• f00 : Number of features where both xi = 0 and yi = 0

• f10 : Number of features where xi = 1 and yi = 0

• f01 : Number of features where xi = 0 and yi = 1

• d = f11 + f10 + f01 + f00 : Total number of features

4.2 Simple Matching Coefficient (SMC)

Definition 4.1 (Simple Matching Coefficient).
f11 + f00 f11 + f00
SMC(x, y) = = (11)
f11 + f10 + f01 + f00 d
Treats both 1-1 matches and 0-0 matches equally.

4.3 Jaccard Coefficient for Binary Data

Definition 4.2 (Jaccard Coefficient).
f11
J(x, y) = (12)
f11 + f10 + f01
Ignores 0-0 matches (useful when 0 represents absence).

SMC vs Jaccard
For binary vectors x = (1, 0, 0, 0, 1, 0, 0, 1) and y = (1, 1, 0, 0, 1, 0, 1, 0):

Position 1 2 3 4 5 6 7 8
x 1 0 0 0 1 0 0 1
y 1 1 0 0 1 0 1 0

• f11 = 2 (positions 1, 5)

• f00 = 2 (positions 3, 6)

• f10 = 1 (position 8)

• f01 = 3 (positions 2, 4, 7) – Wait, position 4 has both 0s.

Let me recalculate:

9
Machine Learning - Unit II 23CSM104

• f11 = 2 (positions 1, 5)

• f00 = 3 (positions 3, 4, 6)

• f10 = 1 (position 8)

• f01 = 2 (positions 2, 7)

2+3 5
SMC = = = 0.625
8 8
2 2
J= = = 0.4
2+1+2 5

4.4 Other Binary Similarity Measures

Table 2: Binary Similarity Measures

Measure Formula
Simple Matching f11 +f00
d

Jaccard f11
f11 +f10 +f01

Dice (Sørensen) 2f11

2f11 +f10 +f01

Rogers-Tanimoto f11 +f00

f11 +2(f10 +f01 )+f00

Russel-Rao f11
d

5 Different Classification Algorithms Based on Distance

Measures
5.1 Instance-Based Learning
Definition 5.1 (Instance-Based Learning). Instance-based learning (also called memory-
based or lazy learning) stores training examples and postpones generalization until a query
is made. Classification is based on the similarity of the query to stored instances.

Key Point
Characteristics of Instance-Based Learning:

• No explicit model is built during training

• All computation happens during prediction (lazy)

• Requires storing all training data

• Local approximation to the target function

10
Machine Learning - Unit II 23CSM104

5.2 Distance-Based Classifiers Overview

Distance-Based
Classifiers

K-Nearest Weighted
Neighbor Radius-Based KNN
NN

6 K-Nearest Neighbor Classifier

6.1 Basic Concept
Definition 6.1 (K-Nearest Neighbor (KNN)). The K-Nearest Neighbor classifier assigns
a class label to a query point based on the majority class among its K nearest neighbors
in the training data.

K=3 Class A
Class B

Query

6.2 KNN Algorithm

Algorithm 1 K-Nearest Neighbor Classification

1: Input: Training set D = {(x1 , y1 ), . . . , (xn , yn )}, query point xq , number of neighbors
K
2: Output: Predicted class ŷ
3:
4: Training Phase: Store all training examples
5:
6: Prediction Phase:
7: for each training example (xi , yi ) ∈ D do
8: Compute distance d(xq , xi )
9: end for
10: Find K nearestP neighbors: NK (xq ) = { K points with smallest distances }
11: ŷ = arg maxc (xi ,yi )∈NK (xq ) I(yi = c)
12: return ŷ

11
Machine Learning - Unit II 23CSM104

6.3 Choice of K
Important
The choice of K significantly affects KNN performance:

• Small K (e.g., K = 1):

– More sensitive to noise

– Complex decision boundary
– Low bias, high variance

• Large K:

– Smoother decision boundary

– May miss local patterns
– High bias, low variance

K=1 K=5 K = 15

6.4 Weighted KNN

Definition 6.2 (Distance-Weighted KNN). In weighted KNN, closer neighbors have more
influence on the prediction:
X
ŷ = arg max wi · I(yi = c) (13)
c
(xi ,yi )∈NK (xq )

where the weight is typically:

1 1
wi = or wi = (14)
d(xq , xi )2 d(xq , xi )

6.5 KNN Properties

Theorem 6.1 (Error Bound for 1-NN). As the number of training samples n → ∞, the
error rate of 1-NN is bounded by:

R∗
 
∗ ∗
R ≤ R1-NN ≤ 2R 1 − (15)
C

where R∗ is the Bayes error rate and C is the number of classes.

12
Machine Learning - Unit II 23CSM104

Key Point

For binary classification: R∗ ≤ R1-NN ≤ 2R∗ (1 − R∗ )

This means 1-NN error is at most twice the Bayes optimal error!

7 Radius Distance Nearest Neighbor Algorithm

Definition 7.1 (Radius Nearest Neighbor (RNN)). Instead of fixing the number of neigh-
bors K, RNN uses all neighbors within a fixed radius r of the query point.

Algorithm 2 Radius Nearest Neighbor Classification

1: Input: Training set D, query point xq , radius r
2: Output: Predicted class ŷ
3:
4: Nr (xq ) = {xi : d(xq , xi ) ≤ r}
5: if Nr (xq ) = ∅ then
6: Handle empty neighborhood (use nearest point or default class)
7: else P
8: ŷ = arg maxc (xi ,yi )∈Nr (xq ) I(yi = c)
9: end if
10: return ŷ

Sparse: 0 neighbors
Dense: 3 neighbors

Same radius r, different neighbor counts

7.1 KNN vs RNN

Table 3: Comparison: KNN vs RNN

Aspect KNN RNN
Parameter Fixed K (number of neigh- Fixed r (radius)
bors)
Neighbors Always exactly K Variable (0 to many)
Density Same # neighbors in More neighbors in dense re-
dense/sparse gions
Challenge Choosing optimal K Handling empty neighbor-
hoods

13
Machine Learning - Unit II 23CSM104

8 KNN Regression
Definition 8.1 (KNN Regression). KNN can be extended to regression by predicting the
average (or weighted average) of the target values of the K nearest neighbors.

8.1 Basic KNN Regression

1 X
ŷ(xq ) = yi (16)
K
(xi ,yi )∈NK (xq )

8.2 Weighted KNN Regression

P
i∈NK (xq ) wi yi
ŷ(xq ) = P (17)
i∈NK (xq ) wi
where wi = 1
d(xq ,xi )
or wi = 1
d(xq ,xi )2

Algorithm 3 KNN Regression

1: Input: Training set D = {(x1 , y1 ), . . . , (xn , yn )}, query xq , K
2: Output: Predicted value ŷ
3:
4: for each (xi , yi ) ∈ D do
5: Compute di = d(xq , xi )
6: end for
7: Find KPnearest neighbors NK (xq )
8: ŷ = K1 i∈NK (xq ) yi ▷ or weighted average
9: return ŷ

KNN Regression Example

Given training data: (1, 3), (2, 5), (3, 7), (5, 8), (6, 10)
Query: xq = 4, K = 3
Distances from xq = 4:

• d(4, 1) = 3, y = 3

• d(4, 2) = 2, y = 5

• d(4, 3) = 1, y = 7 ✓

• d(4, 5) = 1, y = 8 ✓

• d(4, 6) = 2, y = 10 ✓

3 nearest neighbors: (3, 7), (5, 8), (6, 10)

Prediction: ŷ = 7+8+10
3
= 25
3
≈ 8.33

14
Machine Learning - Unit II 23CSM104

9 Performance of Classifiers
9.1 Evaluation Metrics for Classification
9.1.1 Confusion Matrix
Predicted
Positive Negative
Positive TP FN
Actual
Negative FP TN

9.1.2 Key Metrics

TP + TN
Accuracy = (18)
TP + TN + FP + FN
FP + FN
Error Rate = 1 − Accuracy = (19)
TP + TN + FP + FN
TP
Precision = (Positive Predictive Value) (20)
TP + FP
TP
Recall = (Sensitivity, True Positive Rate) (21)
TP + FN
TN
Specificity = (True Negative Rate) (22)
TN + FP
2 × Precision × Recall
F1-Score = (23)
Precision + Recall

9.1.3 Fβ Score
Definition 9.1 (Fβ Score).

Precision × Recall
Fβ = (1 + β 2 ) · (24)
β2 · Precision + Recall

• β = 1: Equal weight (F1)

• β < 1: More weight on precision

• β > 1: More weight on recall

9.2 ROC Curve

Definition 9.2 (ROC Curve). The Receiver Operating Characteristic (ROC) curve plots
True Positive Rate (Recall) vs. False Positive Rate at various classification thresholds.

15
Machine Learning - Unit II 23CSM104

TPR

Perfect

Good
Random

FPR

Definition 9.3 (AUC (Area Under ROC Curve)). AUC measures the entire two-dimensional
area underneath the ROC curve.

• AUC = 1.0: Perfect classifier

• AUC = 0.5: Random classifier

• AUC < 0.5: Worse than random

9.3 Multi-class Evaluation

For multi-class problems:

• Macro-averaging: Compute metric for each class, then average

C
1 X
Macro-F1 = F 1c (25)
C c=1

• Micro-averaging: Aggregate TP, FP, FN across all classes, then compute

P
2 c T Pc
Micro-F1 = P P P (26)
2 c T Pc + c F Pc + c F Nc

• Weighted averaging: Weight by class frequency

10 Performance of Regression Algorithms

10.1 Regression Metrics
10.1.1 Mean Squared Error (MSE)
Definition 10.1 (Mean Squared Error).
n
1X
MSE = (yi − ŷi )2 (27)
n i=1

Penalizes larger errors more heavily due to squaring.

16
Machine Learning - Unit II 23CSM104

10.1.2 Root Mean Squared Error (RMSE)

Definition 10.2 (Root Mean Squared Error).
v
u n
√ u1 X
RMSE = MSE = t (yi − ŷi )2 (28)
n i=1

In the same units as the target variable.

10.1.3 Mean Absolute Error (MAE)

Definition 10.3 (Mean Absolute Error).
n
1X
MAE = |yi − ŷi | (29)
n i=1

More robust to outliers than MSE.

10.1.4 R-Squared (Coefficient of Determination)

Definition 10.4 (R-Squared).
Pn
SSres (yi − ŷi )2
2
R =1− = 1 − Pi=1
n 2
(30)
SStot i=1 (yi − ȳ)

• R2 = 1: Perfect prediction

• R2 = 0: Model predicts mean (baseline)

• R2 < 0: Worse than predicting mean

10.1.5 Mean Absolute Percentage Error (MAPE)

Definition 10.5 (MAPE).
n
100% X yi − ŷi
MAPE = (31)
n i=1 yi

Scale-independent, expressed as percentage.

10.2 Comparison of Regression Metrics

11 Computational Considerations for KNN

11.1 Time Complexity
where n = number of training samples, d = number of features

17
Machine Learning - Unit II 23CSM104

Table 4: Comparison of Regression Metrics

Metric Outlier Sensitivity Interpretability Scale
MSE High Low Squared
RMSE High High Same as y
MAE Low High Same as y
R2 Moderate High [0, 1]
MAPE Low High Percentage

Table 5: KNN Complexity Analysis

Phase Time Space
Training O(1) O(nd)
Prediction (brute force) O(nd) per query O(1)
Prediction (with KD-tree) O(d log n) average O(nd)

11.2 Efficient Nearest Neighbor Search

11.2.1 KD-Tree
Definition 11.1 (KD-Tree). A KD-tree (K-dimensional tree) is a binary tree that re-
cursively partitions space along different dimensions, enabling efficient nearest neighbor
queries.

11.2.2 Ball Tree

Definition 11.2 (Ball Tree). A Ball tree partitions data into nested hyperspheres. More
efficient than KD-trees for high-dimensional data.

11.3 Curse of Dimensionality

18
Machine Learning - Unit II 23CSM104

Important
As dimensionality increases, the concept of “nearest neighbor” becomes less mean-
ingful because:
• All points become approximately equidistant

• The ratio of nearest to farthest distance approaches 1

• More data is needed to maintain density

Theorem 11.1 (Distance Concentration). In high-dimensional spaces, for typical distri-

butions:
dmax − dmin
lim →0 (32)
d→∞ dmin

11.4 Handling High Dimensions

1. Dimensionality Reduction: PCA, t-SNE, UMAP
2. Feature Selection: Remove irrelevant features
3. Approximate Nearest Neighbors: LSH, Annoy
4. Use appropriate distance metrics: Cosine similarity, Mahalanobis

12 Advantages and Disadvantages of KNN

Table 6: KNN: Advantages vs Disadvantages

Advantages Disadvantages
Simple to understand and imple- Slow prediction (lazy learning)
ment
No training phase High memory requirement
Naturally handles multi-class Sensitive to irrelevant features
Non-parametric (no assumptions) Sensitive to feature scaling
Can adapt to new data easily Curse of dimensionality
Effective for low-dimensional data Choice of K is critical
Decision boundary can be complex Imbalanced classes problematic

13 Practical Guidelines for KNN

Best Practices for KNN
1. Feature Scaling: Always normalize/standardize features
xi − µ i xi − mini
x′i = or x′i = (33)
σi maxi − mini

2. Choosing K:

19
Machine Learning - Unit II 23CSM104

√
• Start with K = n
• Use cross-validation to tune
• Use odd K for binary classification

3. Distance Metric Selection:

• Euclidean for continuous features

• Manhattan for grid-like data
• Cosine for text/sparse data
• Hamming for categorical/binary

4. Handle Imbalanced Data:

• Use weighted KNN

• Adjust K based on class distribution
• Consider radius-based methods

5. Reduce Dimensionality: Apply PCA or feature selection for high-

dimensional data

14 Summary
Key Takeaways - Unit II
1. Proximity Measures:

• Similarity (higher = more alike) vs Distance (lower = more alike)

• Metrics must satisfy: non-negativity, identity, symmetry, triangle in-
equality

2. Distance Measures:

• Minkowski: dp = ( |xi − yi |p )1/p

P

• Manhattan (p = 1), Euclidean (p = 2), Chebyshev (p = ∞)

• Mahalanobis: Accounts for correlations

3. Non-Metric Measures:

• Cosine similarity: Angle between vectors

• Jaccard: Set intersection over union

4. Binary Data: SMC (includes 0-0 matches), Jaccard (ignores 0-0)

5. KNN Algorithm:

• Classification: Majority vote of K neighbors

20
Machine Learning - Unit II 23CSM104

• Regression: Average of K neighbors’ values

• Weighted variants: Closer neighbors have more influence

6. Key Considerations:

• Always scale features

• Choose K via cross-validation
• Beware of curse of dimensionality

Table 7: Quick Reference: Distance Measures

Measure Formula Best For
Euclidean Continuous, low-dim
pP
2
P (xi − yi )
Manhattan |xi − yi | Grid paths, sparse
Cosine x·y
∥x∥∥y∥
Text, high-dim
|A∩B|
Jaccard |A∪B|
Sets, binary
Mahalanobis (x − y) Σ (x − y) Correlated features
p
T −1

References
1. Murthy, M. N., & Ananthanarayana, V. S. (2024). Machine Learning Theory and
Practice. Universities Press (India).

2. Mitchell, T. M. (2017). Machine Learning. McGraw-Hill Publication.

3. Tan, P. N., Steinbach, M., & Kumar, V. (2019). Introduction to Data Mining (7th
ed.).

4. Cover, T., & Hart, P. (1967). Nearest neighbor pattern classification. IEEE Trans-
actions on Information Theory, 13(1), 21-27.

21