Regression Algorithm — KNN Regressor
Definition
The Nearest Neighbor Regressor is a predictive model that estimates values by averaging the outcomes of nearby data points. It is based on the principle that similar inputs yield similar outputs.
Dataset Used
We illustrate KNN regression with a dataset that predicts the number of golfers visiting based on:
- Weather outlook
- Temperature
- Humidity
- Wind
Target variable: Number of Players
Preprocessing steps include:
- One-hot encoding categorical features like Outlook and Wind.
- Scaling numerical features like Temperature and Humidity.
Main Mechanism
The steps in KNN Regression are:
- Calculate distance between test point and training points.
2. Select the K nearest neighbors.
3. Average their target values for prediction.
👉 The brute-force method compares all points but is slow for large datasets.
KD Tree for KNN Regression
A KD Tree is a binary tree used to organize points in k-dimensional space.
It reduces search complexity from O(n) to O(log n).
Training Steps:
- Build the KD Tree by choosing a splitting feature and midpoint.
- Split recursively until minimal leaf size is reached.
- Store the target values along with each point.
Prediction Steps:
- Traverse the KD Tree starting from the root.
- Compare query point with split dimension and traverse left or right.
- At leaf nodes, add points to candidate set.
- Backtrack and check unexplored branches if necessary.
- Select K nearest neighbors and average their values for prediction.
✅ KD Trees make KNN regression efficient for larger datasets with fewer features.
Ball Tree for KNN Regression
A Ball Tree organizes points into nested hyperspheres, making it effective for high-dimensional data where KD Trees may become less efficient.
Get Athvaitham’s stories in your inbox
Join Medium for free to get updates from this writer.
Training Steps:
- Find centroid of all points (pivot point).
- Choose the furthest point as first center, then another furthest as second center.
- Partition remaining points into two child nodes based on distance to centers.
- Repeat recursively until minimal leaf size is reached.
- Store target values, radius, and centroid for each node.
Prediction Steps:
- Traverse starting at the root, checking distance to child spheres.
- Go into the closest hypersphere first.
- Add leaf points to candidate set.
- If distance + radius is larger than Kth nearest, ignore that sphere.
- Select K nearest neighbors and average their target values.
✅ Ball Trees are more efficient than KD Trees in high-dimensional datasets.
Evaluation
All methods (Brute Force, KD Tree, Ball Tree) produce the same predictions but differ in efficiency.
- Brute force → Works for small datasets (< 1000 samples).
- KD Tree → Faster for larger datasets with few features (< 20).
- Ball Tree → Better for high-dimensional datasets.
Pros & Cons
Pros:
- Simple and intuitive.
- Works for both classification and regression.
- No assumptions about data distribution.
- Quickly incorporates new data without retraining.
- Interpretability: Predictions are explained by neighbors.
Cons:
- Slow for large datasets.
- Suffers in high dimensions (curse of dimensionality).
- Requires large memory to store data.
- Sensitive to feature scaling and irrelevant features.
Sample Code (Python)
import pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsRegressor
from sklearn.preprocessing import StandardScaler
from sklearn.compose import ColumnTransformer# Create dataset and preprocess...knn = KNeighborsRegressor(n_neighbors=5, algorithm='kd_tree', leaf_size=5)
knn.fit(X_train_scaled, y_train)
y_pred = knn.predict(X_test_scaled)
Final Remarks
The KNN Regressor is a basic yet powerful tool in machine learning.
It’s best for small to medium datasets and helps build a strong foundation in regression and nearest neighbor concepts before moving to advanced models.
