04 K-Nearest Neighbors

The Data-Driven Solution

You are not guessing blindly. Your bank possesses valuable historical data.

• Existing Data: Complete records of thousands of past customers.
  • Features: Income, debt, age, occupation…
  • Outcome: Paid on time ✅ or Defaulted ❌
• Our Approach: Use this data to profile the new customer’s risk. This is where the K-Nearest Neighbors (KNN) algorithm comes into play.

KNN’s Core Idea: ‘Birds of a feather flock together’

The philosophy of the KNN algorithm is very simple: To determine the class of a new sample, just look at which class its nearest ‘neighbors’ belong to.

It’s like trying to figure out a stranger’s hobbies; the easiest way is to see what kind of people their closest friends are.

The Business Analogy for KNN

Our Learning Roadmap Today

1. Core | Define the neighbor rule: how distance, \(k\), and voting jointly produce a prediction.
2. Core | Scale before searching: fit preprocessing on training data only and explain why scale changes the neighbors.
3. Core | Select the model chronologically: choose in advance Euclidean distance and uniform voting, then choose \(k\) with training-only ordered folds.
4. Core | evaluate on the final test period: after choosing the model on validation data, report prevalence, ROC-AUC, AP, and a confusion matrix once and state its limits.
5. Extension | Mechanisms and scale: weighted KNN, regression, KD/Ball Trees, and high-dimensional probability derivations; Core retains one normalized-distance intuition and its algorithmic implication.

4.1 Formal Definition of the k-NN Rule

Given a sample \(x_n\) to be classified, the KNN decision process involves two steps:

1. Find Neighbors: In the entire dataset, identify the \(k\) samples that are closest in distance to \(x_n\).
2. Majority Vote: Among these \(k\) neighbors, use a majority vote to assign the most frequent class as the predicted class for \(x_n\).

\[ \large{y_n = \underset{c \in \mathcal{Y}}{\arg\max} \sum_{i=1}^k I(y_i = c)} \tag{1}\]

Here, \(I(\cdot)\) is an indicator function. It is 1 if the class \(y_i\) of neighbor \(i\) is equal to class \(c\), and 0 otherwise. This formula is essentially counting votes.

Understanding the Three Key Elements of KNN

To successfully apply the KNN algorithm, we must clearly define three core components. They are the building blocks of any KNN model.

• Distance Metric
  • How do we quantify the ‘similarity’ between samples?
• The Choice of \(k\)
  • How many neighbors should we look at? One or ten?
• Decision Rule
  • How do we make the final judgment based on the neighbors? (e.g., simple majority vote)

Key Element 1: The Distance Metric

How do we define ‘close’? This depends on the distance metric we choose.

Key Element 2: The Choice of k

How many neighbors should we consult? This is the critical dial for model complexity.

Key Element 3: The Decision Rule

How do we aggregate the ‘opinions’ of the neighbors? The most common method is ‘majority rules’.

Visualizing Distance Metrics

Euclidean distance is ‘as the crow flies’, while Manhattan distance is ‘walking the blocks’.

Critical Prerequisite: Data Standardization

Important Note: Distance metrics are highly sensitive to the scale of features.

• The Problem: If you directly calculate distance using ‘Annual Income’ (in thousands) and ‘Age’ (in years), the large numerical values of income will completely dominate the calculation, making the effect of age negligible.
• The Solution: Data Standardization. Transform all features to a similar scale (e.g., a mean of 0 and a standard deviation of 1).

Before applying KNN, data standardization is almost always a mandatory step.

Why Standardization Is Crucial

Deep Dive: The Choice of k

The choice of \(k\) directly impacts the model’s performance and represents a Bias-Variance Tradeoff.

• Small \(k\) values:
  • The model is more complex, with a more irregular decision boundary.
  • It is susceptible to noise, leading to Overfitting.
  • Low Bias, High Variance.
• Large \(k\) values:
  • The model is simpler, with a smoother decision boundary.
  • It may ignore local, subtle structures in the data, leading to Underfitting.
  • High Bias, Low Variance.

Small k: High Flexibility, Prone to Overfitting

When k is small (e.g., k=1), the model’s decision boundary becomes highly convoluted, trying to perfectly match every training point, including noise.

Large k: High Stability, Prone to Underfitting

When k is large (e.g., k=N), the model ignores local data structures, and the decision boundary becomes overly simple, failing to capture class differences.

Finding the Optimal k Value

So, how do we find that ‘just right’ value of \(k\)?

• It’s not a guessing game: We can’t choose based on intuition.
• A systematic approach:

  • We typically use Cross-Validation.

  • We split the data into several folds, iteratively use one part as a ‘mini test set’ to evaluate the performance of different \(k\) values, and finally select the \(k\) that performs the best on average.

We will demonstrate this process in the upcoming Python practical session.

Let’s Visualize KNN with an Example

Suppose we have a dataset of tumors, classified as ‘Benign’ or ‘Malignant’. A new patient arrives (represented by ?), and we need to determine if their tumor is benign or malignant.

Code

import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
from sklearn.datasets import make_blobs
input_feature_matrix, target_values = make_blobs(n_samples=50, centers=2, random_state=4, cluster_std=1.5)
new_point = np.array([[-3, 8]])
plt.style.use('seaborn-v0_8-whitegrid')  # 展示当前步骤的结果。
plt.figure(figsize=(10, 6))  # 展示当前步骤的结果。
sns.scatterplot(x=input_feature_matrix[target_values==0, 0], y=input_feature_matrix[target_values==0, 1], s=120, label='Benign', marker='o', color='royalblue', ec='black')  # 展示当前步骤的结果。
sns.scatterplot(x=input_feature_matrix[target_values==1, 0], y=input_feature_matrix[target_values==1, 1], s=120, label='Malignant', marker='X', color='darkorange', ec='black')  # 展示当前步骤的结果。
plt.scatter(new_point[:, 0], new_point[:, 1], s=300, c='red', marker='P', label='Query', ec='black', linewidth=1.5)  # 展示当前步骤的结果。
plt.title('A New Sample to be Classified', fontsize=20, pad=15)  # 展示当前步骤的结果。
plt.xlabel('Feature 1 (Texture)', fontsize=20)  # 保证投影时坐标轴标题可读。
plt.ylabel('Feature 2 (Radius)', fontsize=20)  # 保证投影时坐标轴标题可读。
plt.legend(loc='upper right', fontsize=20)  # 保证投影时图例可读。
plt.tick_params(axis='both', labelsize=20)  # 放大刻度文字以满足投影阅读距离。
plt.gca().set_aspect('equal', adjustable='box')  # 展示当前步骤的结果。
plt.tight_layout()  # 展示当前步骤的结果。
plt.show()  # 展示当前步骤的结果。

4.2 Weighted k-Nearest Neighbors (Weighted k-NN)

Extension: Main lessons to the high-dimensional diagnosis and main case.

Weighted k-NN lets closer neighbors speak more loudly by assigning inverse-distance weights:

\[ \begin{aligned} y_n &= \underset{c \in \mathcal{Y}}{\arg\max}\sum_{i=1}^k w_i I(y_i=c),\\ w_i &= \frac{1}{\operatorname{distance}(x_n,x_i)}. \end{aligned} \]

The Intuition Behind Weighted KNN

Closer neighbors have a ‘louder voice’, while distant neighbors have a ‘quieter voice’.

Implementing Weighted KNN in scikit-learn

In scikit-learn, weights='distance' gives closer neighbors more voting power. This slide shows an executable Extension configuration; the Core Practice chooses in advance uniform voting and never uses test results to choose weighting.

from sklearn.neighbors import KNeighborsClassifier  # Importing a Weighted Nearest Neighbor Classifier
weighted_knn_example = KNeighborsClassifier(n_neighbors=5, weights='distance')  # Set up the weighted-neighbor model before fitting it
weighted_knn_example.get_params()["weights"]  # Check the after-class Extension configuration

'distance'

Any after-class weighting comparison requires a new training-only validation and a separate untouched test period; the current main lesson does not compare that rule.

4.3 KNN for More Than Just Classification: Regression

The core idea of KNN also applies to regression problems, where the goal is to predict a continuous value (like a stock price or house value).

The Mathematics of KNN Regression

For a new sample, the predicted value from a KNN regression model is the average (or weighted average) of the target values of its \(k\) nearest neighbors.

\[ \large{\hat{y}_n = \frac{1}{k} \sum_{i=1}^k y_i} \]

Here, \(y_i\) is the actual numerical value of the \(i\)-th neighbor.

4.4 Real-World Challenges and Solutions

So far, we’ve dealt with idealized numerical data. But in the business world, data is often more complex.

• Challenge 1: How do we handle non-numerical features (like ‘City’ or ‘Product Category’)?
• Challenge 2: What if the dataset is massive (millions of records)? KNN predictions become extremely slow.

Challenge 1: Handling Categorical Features

The Problem: How do you calculate the ‘distance’ between samples that include text features like ‘Beijing’ and ‘Shanghai’?

Solutions:

1. One-Hot Encoding: Convert the categorical feature into multiple binary (0/1) features. This is the most common approach.
2. Use a specific distance metric: For example, the Hamming Distance, which counts the number of positions at which two strings of equal length are different.

Visualizing One-Hot Encoding

Challenge 2: Data Scale and Prediction Speed

A major drawback of KNN is its high computational cost.

• Training Phase: Extremely fast. There’s almost no computation, just storing the data.
• Prediction Phase: Extremely slow. For every new sample to be predicted, it must calculate its distance to every single training sample. If the training set has millions of records, this is unacceptable.

The Question: How can we speed up the process of finding nearest neighbors without sacrificing too much accuracy?

The Core Idea: Avoid ‘Brute-Force Search’

Directly calculating the distance from a new sample to all training points is known as a brute-force search.

The core idea behind acceleration strategies is: build intelligent data structures to quickly eliminate large numbers of samples that cannot possibly be the nearest neighbors.

Acceleration Strategy 1: KD-Tree (k-dimensional tree)

A KD-Tree is a classic data structure for partitioning space. It recursively divides the k-dimensional space into a series of hyperrectangles.

• Construction Process:
  1. Select a coordinate axis (e.g., the one with the largest variance).
  2. Find the median of all data points along that axis.
  3. Use a hyperplane perpendicular to that axis to split the space in two.
  4. Repeat this process recursively for the two subspaces until each region contains only a few data points.

How a KD-Tree Partitions 2D Space

import numpy as np  # Generate Reproducible 2D Teaching Point Sets
import matplotlib.pyplot as plt  # Draw KD Tree Spatial Partition
np.random.seed(42)  # Fixed Teaching Indicative Random Seeds
data_kd = np.random.rand(25, 2) * 10  # Generate 2D Points for Partitioning Demo
data_sorted_x = data_kd[data_kd[:, 0].argsort()]  # Sort by Horizontal Axis to Determine First Split
median_idx_x = len(data_sorted_x) // 2  # Locate Midpoints on Horizontal Axis
median_val_x = data_sorted_x[median_idx_x, 0]  # Extract First Vertical Split Location
left_data = data_sorted_x[:median_idx_x]  # Obtain First Split Left Side Point
left_data_sorted_y = left_data[left_data[:, 1].argsort()]  # Sort by Vertical Axis Left Point
median_val_ly = left_data_sorted_y[len(left_data_sorted_y) // 2, 1]  # Calculate Left Horizontal Split Position
right_data = data_sorted_x[median_idx_x + 1:]  # Obtain First Split Right Side Point
right_data_sorted_y = right_data[right_data[:, 1].argsort()]  # Sort by Vertical Axis Right Point
median_val_ry = right_data_sorted_y[len(right_data_sorted_y) // 2, 1]  # Calculate Right Horizontal Split Position

Code

plt.style.use('seaborn-v0_8-whitegrid')  # 展示当前步骤的结果。
fig, ax = plt.subplots(figsize=(8, 6.5))
ax.scatter(data_kd[:, 0], data_kd[:, 1], c='navy', s=50, ec='black', alpha=0.8)
ax.plot([median_val_x, median_val_x], [-1, 11], color='red', linestyle='--', linewidth=2, label='1st Split (x-axis)')
ax.plot([-1, median_val_x], [median_val_ly, median_val_ly], color='green', linestyle='--', linewidth=2, label='2nd Split (y-axis)')
ax.plot([median_val_x, 11], [median_val_ry, median_val_ry], color='green', linestyle='--')
ax.set_xlim(-1, 11)
ax.set_ylim(-1, 11)
ax.set_title('KD-Tree Spatial Partitioning Process', fontsize=20, pad=15)
ax.set_xlabel('Feature 1', fontsize=20)
ax.set_ylabel('Feature 2', fontsize=20)
ax.legend(fontsize=20)  # 保证投影时图例可读。
ax.set_aspect('equal', adjustable='box')
plt.tight_layout()  # 展示当前步骤的结果。
plt.show()  # 展示当前步骤的结果。

Extension: The Curse of Dimensionality

After the optional topic: after this branch, continue to the main case without replaying the completed Core diagnosis.

The Core Question: What is ‘Distance’ in High-Dimensional Space?

Optional topic: before entering this branch, the 90-minute Core has completed the minimal relative-distance diagnosis. The boundary-layer, fourth-moment, and sub-gaussian derivations below are after-class work and return only forward to the still-pending main case; probability theory is not assumed in Core.

In high-dimensional spaces, the geometric intuition we’ve built from our low-dimensional (2D or 3D) experience often fails.

• Our Intuition: Points are either near or far; you can always find a ‘nearest neighbor’.
• High-Dimensional Reality: As dimensions increase, the Euclidean distances between pairs of points tend to become very similar to each other.

This lecture aims to reveal this counter-intuitive phenomenon—the failure of distance metrics—through intuitive examples and mathematical derivation.

A Simplified Model: A Corner Cell and a Boundary Layer

Let’s begin with a simple thought experiment: slicing a unit hypercube \([0, 1]^d\) at the midpoint \(0.5\) along each dimension.

This partitions the entire space into \(2^d\) identical ‘small hypercubes’.

The cell \([0,1/2]^d\) is one corner cell, not the entire interior of the cube. This partition illustrates shrinking corner volume; a genuine boundary layer needs a separate definition.

Low-Dimensional Intuition: Corner Partitions for d=1 and d=2

In low dimensions we can see the origin corner cell and its complement directly. This compares one corner with the rest of the cube, not an interior core with a boundary shell.

Conceptual Visualization: Concentration of the Distance Distribution

This phenomenon can be understood visually through the changing distribution of distances.

Practical Implications: Why ‘Nearest Neighbor’ Fails

The failure of distance metrics poses a severe challenge to many algorithms that rely on distance calculations, especially k-Nearest Neighbors (k-NN).

• Goal of k-NN: To find the k neighbors in the feature space that are ‘most similar’ to a query point.
• High-Dimensional Dilemma: If the distances from a query point to all its neighbors are nearly equal, there’s no meaningful difference between the ‘nearest’ and ‘farthest’ neighbors.
• Result: Without low-dimensional structure or useful signal, neighbor ranks can lose contrast and predictions can become unstable; this is not a theorem that k-NN is meaningless in every high-dimensional task.

4.5 Summary: The Pros and Cons of KNN

Optional topic: after Core, optionally enter the weighting/regression/KD-tree branch, then continue to the final summary without replaying completed Core material.

KNN’s Applications in Business Decision-Making

Thanks to its simplicity and flexibility, KNN is widely used in various business domains:

• Finance: Customer credit scoring, fraudulent transaction detection.
• Marketing: Customer segmentation, identifying high-value customer groups.
• Recommendation Systems: ‘Customers who bought product X also bought product Y’ is a classic ‘find the nearest neighbor’ problem.
• Healthcare: Disease diagnosis, genetic pattern recognition.
• Retail: Predicting customer purchasing behavior, inventory optimization.

Chapter Review: Core and Extension Concepts

Final Thoughts: The Keys to Success with KNN

To apply KNN successfully, economists and data scientists need to focus on:

1. Feature Engineering: Selecting the most relevant features for the problem is crucial. Garbage in, garbage out.
2. Distance Metric: Choose a distance metric appropriate for your specific problem. Euclidean distance is not always the best choice.
3. Parameter Tuning: Choose in advance uniform Euclidean majority voting and select only \(k\) in training-only chronological folds, refitting preprocessing inside every fold; finish that choice before evaluating the test period once.
4. Efficiency Considerations: For large datasets, it’s essential to consider acceleration algorithms like KD-Trees or Ball Trees, or to use approximate nearest neighbor search methods.

KNN is an excellent gateway into the world of machine learning—it’s simple, intuitive, and powerful.

Thank You!

Q & A