k-Nearest Neighbors and Classification Evaluation Metrics

This notebook covers:

Review of k-Nearest Neighbors (kNN) algorithm
Classification evaluation metrics: Accuracy, Precision, Recall, and F1-Score

# Import necessary libraries
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd
from sklearn.datasets import make_classification, make_blobs
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score, precision_score, recall_score, f1_score
from sklearn.metrics import confusion_matrix, ConfusionMatrixDisplay
import seaborn as sns

# Set plotting style
# plt.style.use('seaborn-whitegrid')
sns.set_context("notebook", font_scale=1.5)

Review of k-Nearest Neighbors (kNN)¶

The k-Nearest Neighbors algorithm is a non-parametric, instance-based learning method used for classification and regression. The algorithm works by finding the k training samples closest in distance to a new sample and predicting the class label based on a majority vote.

Key Characteristics of kNN:¶

Non-parametric: The algorithm doesn’t make assumptions about the underlying data distribution.
Instance-based (lazy learning): No explicit training phase; the model simply stores the training data.
Distance-based: Predictions are made based on the distance between points.

The kNN Algorithm:¶

Store all training samples with their class labels.
For a new sample x:
- Calculate the distance between x and all training samples.
- Select the k closest training samples (k-nearest neighbors).
- Assign the class label based on majority voting among the k neighbors.

Distance Metrics:¶

The most common distance metrics used in kNN are:

Euclidean Distance: $d(x, y) = \sqrt{\sum_{i=1}^{n} (x_i - y_i)^2}$
Manhattan Distance: $d(x, y) = \sum_{i=1}^{n} |x_i - y_i|$
Minkowski Distance: $d(x, y) = (\sum_{i=1}^{n} |x_i - y_i|^p)^{1/p}$

Let’s implement and visualize the kNN algorithm:

# Generate a simple dataset
X, y = make_blobs(n_samples=300, centers=3, random_state=42, cluster_std=3)

# Split the data into training and testing sets
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)

# Visualize the dataset
plt.figure(figsize=(10, 6))
plt.scatter(X_train[:, 0], X_train[:, 1], c=y_train, cmap='viridis', s=50, alpha=0.8, edgecolors='k')
plt.scatter(X_test[:, 0], X_test[:, 1], c=y_test, cmap='viridis', s=100, alpha=0.3, marker='s')
plt.title('Dataset with 3 Classes')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.legend(['Training Data', 'Testing Data'])
plt.colorbar(label='Class Label')
plt.show()

# Implement kNN with different values of k
k_values = [1, 5, 15]
fig, axes = plt.subplots(1, 3, figsize=(15, 5))
axes = axes.flatten()

# Create a meshgrid for decision boundary visualization
h = 0.5  # Step size in the mesh
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, h), np.arange(y_min, y_max, h))

for i, k in enumerate(k_values):
    # Train kNN classifier
    knn = KNeighborsClassifier(n_neighbors=k)
    knn.fit(X_train, y_train)
    
    # Predict on the meshgrid
    Z = knn.predict(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)
    
    # Plot decision boundaries
    axes[i].contourf(xx, yy, Z, alpha=0.3, cmap='viridis')
    axes[i].scatter(X_train[:, 0], X_train[:, 1], c=y_train, cmap='viridis', s=50, edgecolors='k')
    axes[i].scatter(X_test[:, 0], X_test[:, 1], c=y_test, cmap='viridis', s=100, alpha=0.3, marker='s')
    axes[i].set_title(f'kNN with k={k}')
    axes[i].set_xlabel('Feature 1')
    axes[i].set_ylabel('Feature 2')
    
    # Calculate and display accuracy
    y_pred = knn.predict(X_test)
    accuracy = accuracy_score(y_test, y_pred)
    axes[i].text(0.05, 0.95, f'Accuracy: {accuracy:.2f}', transform=axes[i].transAxes, 
                 bbox=dict(facecolor='white', alpha=0.8))

plt.tight_layout()
plt.show()

Observations on kNN Behavior:¶

Effect of k:
- Small k: Decision boundaries are more complex and can lead to overfitting
- Large k: Decision boundaries are smoother but may miss important patterns
Computational Complexity:
- Training: O(1) - just stores the data
- Prediction: O(nd) where n is the number of training samples and d is the number of features
Curse of Dimensionality:
- As the number of dimensions increases, the distance metric becomes less meaningful
- In high dimensions, all points tend to be equidistant from each other

Classification Evaluation Metrics¶

To evaluate the performance of classification models, we need appropriate metrics. The choice of metric depends on the problem context and the relative importance of different types of errors.

Confusion Matrix¶

A confusion matrix is a table that describes the performance of a classification model. For a binary classification problem, it contains:

True Positives (TP): Correctly predicted positive cases
False Positives (FP): Incorrectly predicted positive cases (Type I error)
True Negatives (TN): Correctly predicted negative cases
False Negatives (FN): Incorrectly predicted negative cases (Type II error)

Let’s create a binary classification problem using make_classification and visualize its confusion matrix:

# Generate a binary classification dataset
X_binary, y_binary = make_classification(n_samples=1000, n_features=2, n_informative=2, 
                                         n_redundant=0, n_clusters_per_class=1, random_state=42)

# Split the data
X_train_bin, X_test_bin, y_train_bin, y_test_bin = train_test_split(X_binary, y_binary, 
                                                                     test_size=0.3, random_state=42)
# Visualize the dataset
plt.figure(figsize=(10, 6))
plt.scatter(X_train_bin[:, 0], X_train_bin[:, 1], c=y_train_bin, cmap='viridis', s=50, alpha=0.8, edgecolors='k')
plt.scatter(X_test_bin[:, 0], X_test_bin[:, 1], c=y_test_bin, cmap='viridis', s=100, alpha=0.3, marker='s')
plt.title('Dataset with 2 Classes')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.legend(['Training Data', 'Testing Data'])
plt.colorbar(label='Class Label')
plt.show()

# Train a kNN classifier
knn_binary = KNeighborsClassifier(n_neighbors=5)
knn_binary.fit(X_train_bin, y_train_bin)
y_pred_bin = knn_binary.predict(X_test_bin)

# Create and display the confusion matrix
cm = confusion_matrix(y_test_bin, y_pred_bin)
disp = ConfusionMatrixDisplay(confusion_matrix=cm, display_labels=['Class 0', 'Class 1'])

fig, ax = plt.subplots(figsize=(8, 4))
disp.plot(ax=ax, cmap='Blues', values_format='d')
plt.title('Confusion Matrix for Binary Classification')
plt.show()

# Extract values from confusion matrix
tn, fp, fn, tp = cm.ravel()
print(f"True Negatives (TN): {tn}")
print(f"False Positives (FP): {fp}")
print(f"False Negatives (FN): {fn}")
print(f"True Positives (TP): {tp}")

True Negatives (TN): 141
False Positives (FP): 6
False Negatives (FN): 13
True Positives (TP): 140

Accuracy¶

Accuracy is the ratio of correctly predicted instances to the total instances.

\text{Accuracy} = \frac{TP + TN}{TP + TN + FP + FN}

(1)

Pros:

Simple and intuitive
Works well for balanced datasets

Cons:

Misleading for imbalanced datasets
Doesn’t distinguish between types of errors

# Calculate accuracy
acc = accuracy_score(y_test_bin, y_pred_bin)
print(f"Accuracy: {acc:.4f}")

# Manual calculation
acc_manual = (tp + tn) / (tp + tn + fp + fn)
print(f"Manually calculated accuracy: {acc_manual:.4f}")

Accuracy: 0.9367
Manually calculated accuracy: 0.9367

Precision & Recall¶

Precision¶

Precision is the ratio of correctly predicted positive observations to the total predicted positives. It answers the question: “Of all instances predicted as positive, how many are actually positive?”

\text{Precision} = \frac{TP}{TP + FP}

(2)

Key Applications and Examples:

Spam Email Detection - incorrectly flagging important emails is costly
Medical Testing - avoiding false diagnoses that lead to unnecessary treatment
Autonomous Vehicles - misidentifying obstacles could cause dangerous reactions

Pros:

Critical when false positives (FP) have severe consequences
Essential for applications where incorrect positive predictions are costly
Particularly valuable in information retrieval systems where relevance is key

Cons:

Ignores false negatives (may miss important cases)
Can be misleadingly high if the model is overly conservative in predictions
Not sufficient alone for imbalanced datasets where negatives dominate

Source: Figure 6 of a Remote Sensing paper

# Calculate precision
prec = precision_score(y_test_bin, y_pred_bin)
print(f"Precision: {prec:.4f}")

# Manual calculation
prec_manual = tp / (tp + fp) if (tp + fp) > 0 else 0
print(f"Manually calculated precision: {prec_manual:.4f}")

Precision: 0.9589
Manually calculated precision: 0.9589

Recall (Sensitivity)¶

Recall is the ratio of correctly predicted positive observations to all actual positives. It answers the question: “Of all actual positive instances, how many did we predict correctly?”

\text{Recall} = \frac{TP}{TP + FN}

(3)

Key Applications and Examples:

Medical Diagnostics
Fraud Detection
Landmine Detection
Security Surveillance
Earthquake Early Warning Systems
Cybersecurity Threat Detection
Search and Rescue Operations

Pros:

Critical when the cost of false negatives (FN) is high (e.g., life-threatening scenarios).
Essential for medical screening and public safety applications.

Cons:

Does not account for false positives (FP) (may lead to unnecessary alerts).
Can be inflated artificially if a model labels everything as positive.

Trade-off Note: In many real-world systems, there’s an inverse relationship between precision and recall - improving one typically worsens the other. The right balance depends on which type of error (FP vs FN) is more costly for your specific application.

# Calculate recall
rec = recall_score(y_test_bin, y_pred_bin)
print(f"Recall: {rec:.4f}")

# Manual calculation
rec_manual = tp / (tp + fn) if (tp + fn) > 0 else 0
print(f"Manually calculated recall: {rec_manual:.4f}")

Recall: 0.9150
Manually calculated recall: 0.9150

F1-Score¶

F1-Score is the harmonic mean of Precision and Recall. It provides a balance between precision and recall.

\text{F1-Score} = 2 \times \frac{\text{Precision} \times \text{Recall}}{\text{Precision} + \text{Recall}}

(4)

Pros:

Balances precision and recall
Works well for imbalanced datasets

Cons:

May not be appropriate if one metric is more important than the other
Doesn’t consider true negatives

# Calculate F1-score
f1 = f1_score(y_test_bin, y_pred_bin)
print(f"F1-Score: {f1:.4f}")

# Manual calculation
f1_manual = 2 * (prec_manual * rec_manual) / (prec_manual + rec_manual) if (prec_manual + rec_manual) > 0 else 0
print(f"Manually calculated F1-Score: {f1_manual:.4f}")

F1-Score: 0.9365
Manually calculated F1-Score: 0.9365

Precision-Recall Trade-off¶

There is often a trade-off between precision and recall. Increasing one typically decreases the other.

Let’s visualize this trade-off by adjusting the decision threshold for a probabilistic classifier:

# Generate a new dataset
X_new, y_new = make_classification(n_samples=1000, n_features=2, n_informative=2, n_clusters_per_class=2,
                                   n_redundant=0, random_state=42, weights=[0.7, 0.3])

# Split the data
X_train_new, X_test_new, y_train_new, y_test_new = train_test_split(X_new, y_new, 
                                                                     test_size=0.3, random_state=42)

# Visualize the dataset
plt.figure(figsize=(10, 6))
plt.scatter(X_train_new[:, 0], X_train_new[:, 1], c=y_train_new, cmap='viridis', s=50, alpha=0.8, edgecolors='k')
plt.scatter(X_test_new[:, 0], X_test_new[:, 1], c=y_test_new, cmap='viridis', s=100, alpha=0.3, marker='s')
plt.title('Dataset with 2 Classes')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.legend(['Training Data', 'Testing Data'])
plt.colorbar(label='Class Label')
plt.show()

# Train a kNN classifier with probability estimates
from sklearn.neighbors import KNeighborsClassifier
knn_prob = KNeighborsClassifier(n_neighbors=5, weights='distance')
knn_prob.fit(X_train_new, y_train_new)

# Get probability estimates
y_proba = knn_prob.predict_proba(X_test_new)[:, 1]

See this example of sklearn about weights in kNN

fig, axes = plt.subplots(2, 3, figsize=(10, 5))
axes = axes.flatten()
axes[0].scatter(X_test_new[:, 0], X_test_new[:, 1], c=y_test_new, cmap='viridis', s=100, alpha=0.3, marker='s')
axes[0].set_title('Test Points')
axes[0].axis('off')

# Calculate precision and recall for different thresholds
thresholds = [0, 0.1, 0.5, 0.9, 1]
precisions = []
recalls = []
f1_scores = []
i = 1
for threshold in thresholds:
    y_pred_threshold = (y_proba >= threshold).astype(int)
    precisions.append(precision_score(y_test_new, y_pred_threshold, zero_division=1))
    recalls.append(recall_score(y_test_new, y_pred_threshold, zero_division=0))
    f1_scores.append(f1_score(y_test_new, y_pred_threshold, zero_division=0))
#     if threshold in [0,thresholds[len(thresholds)//2],1.0]:
    axes[i].scatter(X_test_new[:, 0], X_test_new[:, 1], c=y_pred_threshold, cmap='viridis', 
        vmin=0, vmax=1, s=100, alpha=0.3, marker='s')
    axes[i].set_title(f'Threshold={threshold:.2f}')
    # axes[i].set_xlabel('Feature 1')
    # axes[i].set_ylabel('Feature 2')
    axes[i].axis('off')

    i += 1

plt.tight_layout()
plt.show()


# Plot precision-recall trade-off
plt.figure(figsize=(12, 6))

plt.subplot(1, 2, 1)
plt.plot(thresholds, precisions, 'b-', label='Precision')
plt.plot(thresholds, recalls, 'r-', label='Recall')
plt.plot(thresholds, f1_scores, 'g-', label='F1-Score')
plt.xlabel('Threshold')
plt.ylabel('Score')
plt.title('Precision, Recall, and F1-Score vs. Threshold')
plt.legend()
plt.grid(True)

plt.subplot(1, 2, 2)
plt.plot(recalls, precisions, 'b-')
plt.xlabel('Recall')
plt.ylabel('Precision')
plt.title('Precision-Recall Curve')
plt.grid(True)

for i, threshold in enumerate(thresholds):
    plt.annotate(f'{threshold:.1f}', 
                 (recalls[i], precisions[i]),
                 textcoords="offset points", 
                 xytext=(0, 10), 
                 ha='center',
                 fontsize=9)
plt.grid(True)

plt.tight_layout()
plt.show()

Choosing the Right Metric¶

The choice of evaluation metric depends on the specific problem and the relative costs of different types of errors:

Accuracy: Use when classes are balanced and all types of errors have similar costs
Precision: Use when false positives are more costly (e.g., spam detection)
Recall: Use when false negatives are more costly (e.g., disease detection)
F1-Score: Use when you need a balance between precision and recall

Is There an “Optimal Point” on the Precision-Recall Curve?¶

Short answer: No, there is no single, universally optimal point on a Precision-Recall Curve. However, the concept of an “optimal point” can be defined in several meaningful ways, depending on the problem context.

Why There Is No Absolute Optimal Point¶

1. The Nature of the Trade-off¶

Every point on the Precision-Recall Curve corresponds to a different decision threshold. As we move along the curve:

Increasing the threshold raises Precision but lowers Recall.
Decreasing the threshold raises Recall but lowers Precision.

Therefore, each point represents a different balance between the two metrics, and no single point simultaneously maximizes both (except in the ideal case where the curve reaches the top-right corner).

2. Dependence on Error Costs¶

“Optimal” is defined by the relative cost of False Positives vs. False Negatives in a given application:

If FPs are more costly (e.g., spam detection), a point with high Precision is optimal.
If FNs are more costly (e.g., cancer diagnosis), a point with high Recall is optimal.
If the costs are balanced, the point that maximizes the F1-Score is a reasonable choice.

What Can Be Considered “Optimal”?¶

1. The Point with the Highest F1-Score¶

This is the most common criterion for selecting a point on the curve. F1-Score is the harmonic mean of Precision and Recall, and the point that maximizes it provides a sensible balance between the two.

Looking at the left plot above (Precision, Recall, and F1-Score vs. Threshold), the F1-Score (green line) reaches a peak at a specific threshold. Note that this peak may not occur at 0.5 — especially for imbalanced datasets, the optimal F1 threshold is often lower than 0.5 (in this example, around 0.29–0.32).

2. The Point Closest to the Top-Right Corner¶

In some analyses, the point with the minimum Euclidean distance to (Precision=1, Recall=1) is selected as optimal. This criterion is simple but ignores the actual costs of the problem.

Finding the Optimal Threshold Using a Dense Grid¶

This code evaluates 100 evenly spaced thresholds between 0 and 1 to find the one that maximizes the F1-Score, providing a fine-grained approximation of the optimal decision boundary.

thresholds = np.linspace(0, 1, 100)
precisions = []
recalls = []
f1_scores = []
for threshold in thresholds:
    y_pred_threshold = (y_proba >= threshold).astype(int)
    precisions.append(precision_score(y_test_new, y_pred_threshold, zero_division=1))
    recalls.append(recall_score(y_test_new, y_pred_threshold, zero_division=0))
    f1_scores.append(f1_score(y_test_new, y_pred_threshold, zero_division=0))

best_threshold = thresholds[np.argmax(f1_scores)]
best_f1 = max(f1_scores)
print(f"Best threshold: {best_threshold:.2f}, Best F1: {best_f1:.4f}")

Best threshold: 0.29, Best F1: 0.8757

Finding the Optimal Threshold Using Scikit-learn’s `precision_recall_curve`¶

This code uses Scikit-learn’s built-in precision_recall_curve function, which computes precision and recall at every distinct probability value produced by the model, yielding a more precise and principled estimate of the optimal threshold.

from sklearn.metrics import precision_recall_curve
precision, recall, thresholds = precision_recall_curve(y_test_new, y_proba)
f1 = 2 * precision * recall / (precision + recall + 1e-10)
best_idx = np.argmax(f1)
print(f"Best threshold: {thresholds[best_idx]:.2f}")

Best threshold: 0.32

Why the Visual “Optimal Point” at 0.5 Differs from the Computational Result¶

In the original notebook, only five thresholds (0, 0.1, 0.5, 0.9, 1) were evaluated. The resulting plot is therefore a very coarse approximation — just five points connected by lines. Visually, F1 appears to peak at 0.5 simply because no finer thresholds were tested between 0.1 and 0.5.

When a dense grid of thresholds (e.g., 100 points via np.linspace) or precision_recall_curve is used, the true maximum of F1-Score is found at a lower threshold (around 0.29–0.32 in this example). This is expected for imbalanced datasets:

At a high threshold (e.g., 0.5), the model predicts the positive class only when highly confident, resulting in low Recall.
At a lower threshold (e.g., 0.3), the model predicts the positive class more often, raising Recall at a small cost to Precision. Since F1 is the harmonic mean, this balance typically yields a higher F1-Score.

Small Differences Between the Two Methods (0.29 vs. 0.32)¶

The two approaches find slightly different optimal thresholds:

The np.linspace method evaluates 100 evenly spaced thresholds and returns the closest one (0.29).
The precision_recall_curve method evaluates thresholds at every distinct probability value produced by the model, yielding a more principled estimate (0.32).

The difference of ~0.03 is negligible and both methods point to the same optimal region. For final reporting, precision_recall_curve is generally preferred because it is based on the actual distribution of predicted probabilities rather than an arbitrary grid.

Criterion	Optimal Point
Maximize F1-Score	The point with the highest F1 (≈ 0.29–0.32 in this example)
Minimize total cost	Depends on the relative costs of FP and FN
Closest to (1, 1)	Minimum Euclidean distance to the top-right corner
Maximum Recall with acceptable Precision	The threshold that keeps Precision above a desired level

In short, the “optimal point” is a relative concept that depends on the selection criterion and the error costs of the specific problem. In this notebook, the most reasonable choice is the point that maximizes the F1-Score, which occurs at a threshold around 0.3, not at the default 0.5.

Summary¶

In this notebook, we’ve covered:

k-Nearest Neighbors (kNN):
- A non-parametric, instance-based learning algorithm
- Uses distance metrics to find the k closest training examples
- Makes predictions based on majority voting
- The choice of k affects the complexity of decision boundaries
Classification Evaluation Metrics:
- Confusion Matrix: A table showing the counts of true/false positives/negatives
- Accuracy: The proportion of correct predictions
- Precision: The proportion of true positives among predicted positives
- Recall: The proportion of true positives among actual positives
- F1-Score: The harmonic mean of precision and recall
- Precision-Recall Trade-off: Adjusting the decision threshold affects precision and recall

These concepts form the foundation for understanding classification algorithms and evaluating their performance. In the next notebook, we’ll explore Voronoi diagrams and their connection to kNN and Bayesian decision theory.

References¶

Duda, R. O., Hart, P. E., & Stork, D. G. (2001). Pattern Classification (2nd ed.). Wiley-Interscience.
Precision and Recall - Wikipedia
Confusion Matrix - Wikipedia
Scikit-learn Documentation - Model Evaluation

Review of k-Nearest Neighbors (kNN)¶

Key Characteristics of kNN:¶

The kNN Algorithm:¶

Distance Metrics:¶

Observations on kNN Behavior:¶

Classification Evaluation Metrics¶

Confusion Matrix¶

Accuracy¶

Precision & Recall¶

Precision¶

Recall (Sensitivity)¶

F1-Score¶

Precision-Recall Trade-off¶

Choosing the Right Metric¶

Is There an “Optimal Point” on the Precision-Recall Curve?¶

Why There Is No Absolute Optimal Point¶

1. The Nature of the Trade-off¶

2. Dependence on Error Costs¶

What Can Be Considered “Optimal”?¶

1. The Point with the Highest F1-Score¶

2. The Point Closest to the Top-Right Corner¶

Finding the Optimal Threshold Using a Dense Grid¶

Finding the Optimal Threshold Using Scikit-learn’s `precision_recall_curve`¶

Why the Visual “Optimal Point” at 0.5 Differs from the Computational Result¶

Small Differences Between the Two Methods (0.29 vs. 0.32)¶

Further Reading¶

Metrics for Multi-class Classification¶

Further Reading¶

Metrics for Multi-class Classification¶

Summary¶

References¶

k-Nearest Neighbors and Classification Evaluation Metrics

Review of k-Nearest Neighbors (kNN)¶

Key Characteristics of kNN:¶

The kNN Algorithm:¶

Distance Metrics:¶

Observations on kNN Behavior:¶

Classification Evaluation Metrics¶

Confusion Matrix¶

Accuracy¶

Precision & Recall¶

Precision¶

Recall (Sensitivity)¶

F1-Score¶

Precision-Recall Trade-off¶

Choosing the Right Metric¶

Is There an “Optimal Point” on the Precision-Recall Curve?¶

Why There Is No Absolute Optimal Point¶

1. The Nature of the Trade-off¶

2. Dependence on Error Costs¶

What Can Be Considered “Optimal”?¶

1. The Point with the Highest F1-Score¶

2. The Point Closest to the Top-Right Corner¶

Finding the Optimal Threshold Using a Dense Grid¶

Finding the Optimal Threshold Using Scikit-learn’s precision_recall_curve¶

Why the Visual “Optimal Point” at 0.5 Differs from the Computational Result¶

Small Differences Between the Two Methods (0.29 vs. 0.32)¶

Further Reading¶

Metrics for Multi-class Classification¶

Further Reading¶

Metrics for Multi-class Classification¶

Summary¶

References¶

Finding the Optimal Threshold Using Scikit-learn’s `precision_recall_curve`¶